Sums of Squares of Integers

We find a formula for the sum of the first n squares:Sn = 12 22 32 42 … n2.We haveS1 = 1, S2 = 12 22 = 5, S3 = l2 22 32 = 14,S4 = 30, S5 = 55, S6 = 91.and so on. To make things a little simpler, we will also use the sum of the squares of the first zero terms , S0 = 02 = 0. Arranging these values in a table,we find thatSince the third differenes △3Sn are constant,these data values must follow a cubic pattern;that is, the formula for the sum of the squares of the first n integers is a cubic function,     

On the Growth of Components of Meromorphic Solutions of Systems of Complex Differential Equations

This paper investigates the problem of the growth of the components of meromorphic solutions of a class of a system of complex algebraic differential equations, and generalized some of N. Toda＇s results concerning the growth of differential equations to the case of systems of differential equations. The paper considers the existence of admissible solutions of the system of differential equations.     

Stability of Solution of a Class of Quasilinear Elliptic Equations

In this paper, using capacity theory and extension theorem of Lipschitz functions we first discuss the uniqueness of weak solution of nonhomogeneous quasilinear elliptic equationsin space W(θ,p)(Ω), which is bigger than W1,p(Ω). Next, using revise reverse Holder inequality we prove that if ωc is uniformly p-think, then there exists a neighborhood U of p, such that for all t ∈U, the weak solutions of equation corresponding t are bounded uniformly. Finally, we get the stability of weak solutions on exponent p.     

Vertices of π-Irreducible Characters of Groups of Odd Order

If G is a group of odd order and χ ∈ Irr(G) lifts an irreducible Brauer character ?, then we associate to χ a canonical pair (Q, δ) up to G-conjugacy, where Q is a vertex of ? and δ ∈ Irr(Q) is a linear character of Q. We show that (Q, δ) is a Navarro vertex for χ. We also discuss examples.     

Estimates of groups of deviations of Faber sums and strong summability of faber series on classes of ψ-integrals

We establish upper bounds for a group of *-deviations of Faber sums on the classes of -integrals in a complex plane introduced by Stepanets.Translated from Ukrainskyi Matematychnyi Zhurnal, Vol. 56, No. 4, pp. 451–461, April, 2004.     

Correlation of zeros of automorphic L-functions

We compute the n-level correlation of normalized nontrivial zeros of a product of L-functions:L(s,π1)···L(s,πk), where πj, j=1,...,k, are automorphic cuspidal representations of GLmj(QA). Here the sizes of the groups GLmj(QA) are not necessarily the same. When these L(s,πj) are distinct, we prove that their nontrivial zeros are uncorrelated, as predicted by random matrix theory and verified numerically. When L(s,πj) are not necessarily distinct, our results will lead to a proof that the n-level correlation of normalized nontrivial zeros of the product L-function follows the superposition of Gaussian Unitary Ensemble (GUE) models of individual L-functions and products of lower rank GUEs. The results are unconditional when m1,...,mk 4,but are under Hypothesis H in other cases.     

Extension of a Theorem of Carleson-Duren

1. Introduction A theorem of Carleson,as generalized by Duren characterizes those positive measure μ on the unit disc U={z∈C:|z|<1} for which the H~p norm domiates the L~q(μ) norm of elements of H~p. Later on, Hasting proved an analogous results with H~p replaced by A~p, the Bergman space of fuctions f     

Dynamics of Polynomial Automorphisms of C~N

ＤｙｎａｍｉｃｓｏｆＰｏｌｙｎｏｍｉａｌＡｕｔｏｍｏｒｐｈｉｓｍｓｏｆＣ~Ｎ￥ＺｈａｎｇＷｅｎｊｕｎ（ＨｅｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｋａｉｆｅｎｇ，Ｐ．Ｒ．Ｃｈｉａｎ，４７５００１）Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｉｓａｓｓｉｇｎｅｄｔｏｄｉｓ?..     

The Degree of Unsolvability of Models

The purpose of this paper is to describe the complexity of models by theirdegrees of unsolvability,J.Richter defined the degree of a structure to be deg ()=sup{deg(),deg(R_i),i=1,…,n},Where is a model for afinite language L={R_i,i=1,…,n}and the universe of is a subset of ω. Shepointed out that, according to her definition, there can be models which areisomorphic but their degrees are different.Also,her discussions are restricted tofinite languages and models whose universes are subsets of ω.     

Applications of random sampling in computational geometry,II

We use random sampling for several new geometric algorithms. The algorithms are Las Vegas, and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requiresO(A+n logn) expected time, whereA is the number of intersecting pairs reported. The algorithm requiresO(n) space in the worst case. Another algorithm computes the convex hull ofn points inE ^d inO(n logn) expected time ford=3, andO(n ^[d/2]) expected time ford>3. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set ofn points inE ³ inO(n logn) expected time, and on the way computes the intersection ofn unit balls inE ³. We show thatO(n logA) expected time suffices to compute the convex hull ofn points inE ³, whereA is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for (k)-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high-order Voronoi diagrams.     

Efficient generation of random nonsingular matrices

We present an efficient algorithm for generating an n × n nonsingular matrix uniformly over a finite field. This algorithm is useful for several cryptographic and checking applications. Over GF[2] our algorithm runs in expected time M(n) + O(n²), where M(n) is the time needed to multiply two n × n matrices, and the expected number of random bits it uses is n² + 3. (Over other finite fields we use n² + O(1) random field elements on average.) This is more efficient than the standard method for solving this problem, both in terms of expected running time and the expected number of random bits used. The standard method is to generate random n × n matrices until we produce one with nonzero determinant. In contrast, our technique directly produces a random matrix guaranteed to have nonzero determinant. We also introduce efficient algorithms for related problems such as uniformly generating singular matrices or matrices with fixed determinant. © 1993 John Wiley & Sons, Inc.     

Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphs

In [1] it is proved that an uncrowded (k + 1)-hypergraph of average degree t^k contains an independent set of size (cn/t)(1n t)^1/k. We present a polynomial time algorithm that finds such an independent set by derandomizing the original probabilistic proof. The technique that we use can be applied to derandomize other random algorithms that use several random variables having sufficiently small variances. © 1996 John Wiley & Sons, Inc.     

Valuation of some random search methods

The problem of finding a local minimum:of a function F(x), xßR ⁿis studied. The paper deals with some member of Rastrigin's random search, family and with the method of random search with reversals. A new practical Adaptive Step Size Random Search, with Reversals (ASSRSB) is.proposed arid analyzed* Computational experience is also reported. ASSRSR is compareD with the adaptive step size random search algorithms of Schumer-steiglitz And White-day, and with the Newton-Raphson and Fletcher-Powell, methods.     

Probabilistic analysis of a new class of strip packing algorithms

A new class of algorithms for online packing of rectangles into a strip is proposed and studied. It is proved that the expectation of the unfilled area for this class of algorithms is O(N ^2/3) in the standard (for this type of problems) probabilistic model for N random rectangles.     

On Linear Programming Bounds for Spherical Codes and Designs

We investigate universal bounds on spherical codes and spherical designs that could be obtained using Delsartes linear programming methods. We give a lower estimate for the LP upper bound on codes, and an upper estimate for the LP lower bound on designs. Specifically, when the distance of the code is fixed and the dimension goes to infinity, the LP upper bound on codes is at least as large as the average of the best known upper and lower bounds. When the dimension n of the design is fixed, and the strength k goes to infinity, the LP bound on designs turns out, in conjunction with known lower bounds, to be proportional to k^n-1.     

A fast and simple randomized parallel algorithm for the maximal independent set problem

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|d_max) processors is O(log n), where d_max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log²n). Previously, an O(log⁴n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log²n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.     

Algorithms for coloring semi-random graphs

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require n^δ (δ>0) colors even for bounded chromatic (k-colorable for fixed k) n-vertex graphs. The situation changes dramatically if we look at the average performance of an algorithm rather than its worst case performance. A k-colorable graph drawn from certain classes of distributions can be k-colored almost surely in polynomial time. It is also possible to k-color such random graphs in polynomial average time. In this paper, we present polynomial time algorithms for k-coloring graphs drawn from the semirandom model. In this model, the graph is supplied by an adversary each of whose decisions regarding inclusion of edges is reversed with some probability p. In terms of randomness, this model lies between the worst case model and the usual random model where each edge is chosen with equal probability. We present polynomial time algorithms of two different types. The first type of algorithms always run in polynomial time and succeed almost surely. Blum and Spencer [J. Algorithms, 19 , 204–234 (1995)] have also obtained independently such algorithms, but our results are based on different proof techniques which are interesting in their own right. The second type of algorithms always succeed and have polynomial running time on the average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work for semirandom graphs drawn from a wide range of distributions and work as long as p≥n^−α(k)+ϵ where α(k)=(2k)/((k−1)(k+2)) and ϵ is a positive constant. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 125–158 (1998)     

EXPECTED NUMBER OF ITERATIONS OF INTERIOR-POINT ALGORITHMS FOR LINEAR PROGRAMMING

We study the behavior of some polynomial interior-point algorithms for solving random linear programming (LP) problems. We show that the expected and anticipated number of iterations of theseTodd‘s probabilisticalgorithms is bounded above by O(n^1.5). The random LP problem is model with the Cauchy distribution.     

Generating functions and duality for integer programs

We consider the integer program P→max c^′x|Ax=y;xNⁿ . Using the generating function of an associated counting problem, and a generalized residue formula of Brion and Vergne, we explicitly relate P with its continuous linear programming (LP) analogue and provide a characterization of its optimal value. In particular, dual variables λR^m have discrete analogues zC^m, related in a simple manner. Moreover, both optimal values of P and the LP obey the same formula, using z for P and |z| for the LP. One retrieves (and refines) the so-called group-relaxations of Gomory which, in this dual approach, arise naturally from a detailed analysis of a generalized residue formula of Brion and Vergne. Finally, we also provide an explicit formulation of a dual problem P^*, the analogue of the dual LP in linear programming.