Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  758.11007
Autor:  Erdös, Paul; Sárközy, A.
Title:  Arithmetic progressions in subset sums. (In English)
Source:  Discrete Math. 102, No.3, 249-264 (1992).
Review:  For any set A of positive integers, denote by P(A) the set of positive integers n which can be expressed as a sum of distinct elements of A. Let u = F(N,t) be the greatest integer u such that for every A\subset{1,2,...,N} with |A| = t, the set P(A) contains u consecutive multiples of a positive integer d: {(x+1)d,(x+2)d,...,(x+u)d}\subset P(A), for some x and d, and let v = G(N,t) be the greatest integer v such that for every A\subset{1,2,...,N} with |A| = t, the set P(A) contains an arithmetic progression of length v. It is clear that F(N,t) \leq G(N,t) for all N,t.
Extending earlier work of Sárközy, the authors prove:
I. If N \geq N0 and 18(log N)2 < t \leq N. Then F(N,t) > 1/18 {t\over {(log N)2}}.
II. (i). If N > N0 and c log N < t < 1/3 N1/3, then F(N,t) < 16 {t\over{log N}} log ({t\over{log N}}).\par\strut \phantom{II.} (ii). If \epsilon > 0 and t0(\epsilon) < t < (1- \epsilon)N ½, then F(N,t) < (1+\epsilon)t.
III. (i). If N > N0 and \exp(2(log N) ½) < t < N ½, then

G(N,t) < t\exp(4max({{log N}\over {log t}},{{(log t)2} \over {log N}})).

\phantom{III.} (ii). For all t0 < t < 1/2 N ½, G(N,t) < 2t3/2.
Finally, upper and lower bounds are also obtained for certain other functions associated with 3 term arithmetic progressions.
Reviewer:  M.Nair (Glasgow)
Classif.:  * 11B25 Arithmetic progressions
Keywords:  subset sums; sums of distinct elements of a sequence; arithmetic progression

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page