Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  725.11012
Autor:  Erdös, Paul; Sárközy, A.
Title:  On a problem of Straus. (In English)
Source:  Disorder in physical systems, Vol. in Honour of J. M. Hammersley 70th Birthday, 55-66 (1990).
Review:  [For the entire collection see Zbl 714.00019.]
If A is a set of integers with the property that no element ai is the average of any subset of A consisting of two or more elements, then A is said to be non-averaging. Let f(N) denote the maximum cardinality of a non-averaging subset of {0,1,2,...,N}. The best estimates for f(N) are due to Á.P.Bosznay (1989; Zbl 682.10049) and P.Erdös and E.G.Straus (1970; Zbl 216.01503) who showed that f(N) >> N1/4 and f(N) << N2/3 respectively. In this paper, the authors improve this last estimate to: For N > N0, f(N) < 403(N log N) ½.
Denote by P(A) the set of distinct integers n which can be represented in the form n = suma in A\epsilonaa where \epsilona = 0 or 1 for all a and 0 < suma in A\epsilona < oo. The above estimate for f(N) is obtained via a bound for F(N) which is defined to be the largest k such that there exist two subsets A = {a1,...,ak}, B = {b1,...,bk} of {0,1,...,N} with P(A)\cap P(B) = Ø. The infinite analogue of this problem is: If A,B are infinite sets of positive integers with P(A)\cap P(B) = Ø then how large can max (A(x),B(x)) be? Here A(x), B(x) are the counting functions of A,B respectively. The authors conjecture that

liminfx ––> oo\frac{max (A(x),B(x))}{x ½} = 0

and show by an interesting construction that the x ½ in the conjecture cannot be replaced by x ½(log x)- ½-\epsilon.
Reviewer:  M.Nair (Glasgow)
Classif.:  * 11B99 Sequences and sets
05D05 Extremal set theory
00A07 Problem books
Keywords:  non-averaging sets; maximum cardinality
Citations:  Zbl 714.00019

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag