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