On sums of subsets of a set of integers

Forr2 letp(n, r) denote the maximum cardinality of a subsetA ofN={1, 2,...,n} such that there are noBA and an integery with b=y ^r. It is shown that for any>0 andn>n(), (1+o(1))2^1/(r+1) n ^{(r–1)/(r+1)}p(n, r)n ^+2/3 for allr5, and that for every fixedr6,p(n, r)=(1+o(1))·2^1/(r+1) n ^{(r–1)/(r+1)} asn. Letf(n, m) denote the maximum cardinality of a subsetA ofN such that there is noBA the sum of whose elements ism. It is proved that for 3n ^6/3+mn ²/20 log² n andn>n(), f(n, m)=[n/s]+s–2, wheres is the smallest integer that does not dividem. A special case of this result establishes a conjecture of Erds and Graham.Research supported in part by Allon Fellowship, by a Bat-Sheva de Rothschild Grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

Sharp bounds for the partition function of integer sequences

By means of a new criterion for higher multiplicities of additive representations of integers as sums of distinct terms of a fixed integer sequence sharp bounds are determined for the partition function of many sequences with the aid of a computer.     

A non-analytic proof of the newman—znám result for disjoint covering systems

A direct combinatorial proof is given to a generalization of the fact that the largest modulusN of a disjoint covering system appears at leastp times in the system, wherep is the smallest prime dividingN. The method is based on geometric properties of lattice parallelotopes. This research was supported by grant 85-00368 from the United States-Is rael Binational Science Foundation, Jerusalem, Israel.     

On Lovász’ lattice reduction and the nearest lattice point problem

Answering a question of Vera Sós, we show how Lovász’ lattice reduction can be used to find a point of a given lattice, nearest within a factor ofc ^d (c = const.) to a given point in R ^d . We prove that each of two straightforward fast heuristic procedures achieves this goal when applied to a lattice given by a Lovász-reduced basis. The verification of one of them requires proving a geometric feature of Lovász-reduced bases: ac ₁ ^d lower bound on the angle between any member of the basis and the hyperplane generated by the other members, wherec ₁ = √2/3. As an application, we obtain a solution to the nonhomogeneous simultaneous diophantine approximation problem, optimal within a factor ofC ^d . In another application, we improve the Grötschel-Lovász-Schrijver version of H. W. Lenstra’s integer linear programming algorithm. The algorithms, when applied to rational input vectors, run in polynomial time.     

A fixed point theorem for discontinuous functions

Any function from a non-empty polytope into itself that is locally gross direction preserving is shown to have the fixed point property. Brouwer's fixed point theorem for continuous functions is a special case. We discuss the application of the result in the area of non-cooperative game theory.     

On Taylor series and Kapteyn series of the first and second type

We study the relation between the coefficients of Taylor series and Kapteyn series representing the same function. We compute explicit formulas for expressing one in terms of the other and give examples to illustrate our method.     

Maximum entropy characterizations of the multivariate Liouville distributions

A random vector X=(X₁,X₂,…,X_n) with positive components has a Liouville distribution with parameter θ=(θ₁,θ₂,…,θ_n) if its joint probability density function is proportional to , θ_i>0 [R.D. Gupta, D.S.P. Richards, Multivariate Liouville distributions, J. Multivariate Anal. 23 (1987) 233-256]. Examples include correlated gamma variables, Dirichlet and inverted Dirichlet distributions. We derive appropriate constraints which establish the maximum entropy characterization of the Liouville distributions among all multivariate distributions. Matrix analogs of the Liouville distributions are considered. Some interesting results related to I-projection from a Liouville distribution are presented.     

Adaptive polynomial preconditioning for hermitian indefinite linear systems

This paper explores the use of polynomial preconditioned CG methods for hermitian indefinite linear systems,Ax=b. Polynomial preconditioning is attractive for several reasons. First, it is well-suited to vector and/or parallel architectures. It is also easy to employ, requiring only matrix-vector multiplication and vector addition. To obtain an optimum polynomial preconditioner we solve a minimax approximation problem. The preconditioning polynomial,C(), is optimum in that it minimizes a bound on the condition number of the preconditioned matrix,C(A)A. We also characterize the behavior of this minimax polynomial, which makes possible a thorough understanding of the associated CG methods. This characterization is also essential to the development of an adaptive procedure for dynamically determining the optimum polynomial preconditioner. Finally, we demonstrate the effectiveness of polynomial preconditioning in a variety of numerical experiments on a Cray X-MP/48. Our results suggest that high degree (20–50) polynomials are usually best.This research was supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Dept. of Energy, by Lawrence Livermore National Laboratory under contract W-7405-ENG-48.This research was supported in part by the Dept. of Energy and the National Science Foundation under grant DMS 8704169.This research was supported in part by U.S. Dept. of Energy grant DEFG02-87ER25026 and by National Science Foundation grant DMS 8703226.     

Multivariate quadratic forms of random vectors

We obtain the distribution of the sum of n random vectors and the distribution of their quadratic forms: their densities are expanded in series of Hermite and Laguerre polynomials. We do not suppose that these vectors are independent. In particular, we apply these results to multivariate quadratic forms of Gaussian vectors. We obtain also their densities expanded in Mac Laurin series or in the form of an integral. By this last result, we introduce a new method of computation which can be much simpler than the previously known techniques. In particular, we introduce a new method in the very classical univariate case. We remark that we do not assume the independence of normal variables.     

A martingale decomposition for quadratic forms of Markov chains (with applications)

We develop a martingale-based decomposition for a general class of quadratic forms of Markov chains, which resembles the well-known Hoeffding decomposition of U$U$-statistics of i.i.d. data up to a reminder term. To illustrate the applicability of our results, we discuss how this decomposition may be used to studying the large-sample properties of certain statistics in two problems: (i) we examine the asymptotic behavior of lag-window estimators in time series, and (ii) we derive an asymptotic linear representation and limiting distribution of U$U$-statistics with varying kernels in time series. We also discuss simplified examples of interest in statistics and econometrics.     

Accelerated Landweber iterations for the solution of ill-posed equations

Summary In this paper, the potentials of so-calledlinear semiiterative methods are considered for the approximate solution of linear ill-posed problems and ill conditioned matrix equations. Several efficient two-step methods are presented, most of which have been introduced earlier in the literature. Stipulating certain conditions concerning the smoothness of the solution, a notion of optimal speed of convergence may be formulated. Various direct and converse results are derived to illustrate the properties of this concept.If the problem's right hand side data are contaminated by noise, semiiterative methods may be used asregularization methods. Assuming optimal rate of convergence of the iteration for the unperturbed problem, the regularized approximations will be of order optimal accuracy.To derive these results, specific properties of polynomials are used in connection with the basic theory of solving ill-posed problems. Rather recent results onfast decreasing polynomials are applied to answer an open question of Brakhage.Numerical examples are given including a comparison to the method of conjugate gradients.This research was sponsored by the Deutsche Forschungsgemeinschaft (DFG).     

Extensions of the conjugate prior through the Kullback-Leibler separators

The conjugate prior for the exponential family, referred to also as the natural conjugate prior, is represented in terms of the Kullback-Leibler separator. This representation permits us to extend the conjugate prior to that for a general family of sampling distributions. Further, by replacing the Kullback-Leibler separator with its dual form, we define another form of a prior, which will be called the mean conjugate prior. Various results on duality between the two conjugate priors are shown. Implications of this approach include richer families of prior distributions induced by a sampling distribution and the empirical Bayes estimation of a high-dimensional mean parameter.     

OnM-functions and nonlinear relaxation methods

Globally convergent nonlinear relaxation methods are considered for a class of nonlinear boundary value problems (BVPs), where the discretizations are continuousM-functions.It is shown that the equations with one variable occurring in the nonlinear relaxation methods can always be solved by Newton's method combined with the Bisection method. The nonlinear relaxation methods are used to get an initial approximation in the domain of attraction of Newton's method. Numerical examples are given.