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