Long arithmetic progressions in sumsets: Thresholds and bounds

Szemerédi, E.; Vu, V.

doi:10.1090/S0894-0347-05-00502-3

Long arithmetic progressions in sumsets: Thresholds and bounds

Authors: E. Szemerédi and V. Vu
Journal: J. Amer. Math. Soc. 19 (2006), 119-169
MSC (2000): Primary 11B25, 11P70, 11B75
DOI: https://doi.org/10.1090/S0894-0347-05-00502-3
Published electronically: September 13, 2005
MathSciNet review: 2169044
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For a set of integers, the sumset $lA =A+\dots+A$ consists of those numbers which can be represented as a sum of elements of :

$\begin{displaymath}lA =\{a_1+\dots + a_l\vert a_i \in A_i \}. \end{displaymath}$

Closely related and equally interesting notion is that of $l^{\ast}A$ , which is the collection of numbers which can be represented as a sum of different elements of :

$\begin{displaymath}l^{\ast}A =\{a_1+\dots + a_l\vert a_i \in A_i, a_i \neq a_j \}. \end{displaymath}$

The goal of this paper is to investigate the structure of and $l^{\ast}A$ , where is a subset of $\{1,2, \dots, n\}$ . As application, we solve two conjectures by Erdös and Folkman, posed in 1960s.

1. G. Andrews, The theory of partitions. Reprint of the 1976 original. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1998. MR 1634067 (99c:11126)
2. Y. Bilu, Structure of sets with small sumset. Structure theory of set addition, Astérisque, No. 258 (1999), xi, 77-108.MR 1701189 (2000h:11109)
3. J. Bourgain, On arithmetic progressions in sums of sets of integers. A tribute to Paul Erdös, pp. 105-109, Cambridge Univ. Press, Cambridge, 1990.MR 1117007 (92e:11011)
4. J. W. S. Cassels, On the representation of integers as the sums of distinct summands taken from a fixed set, Acta Sci. Math. Szeged 21 (1960), 111-124. MR 0130236 (24:A103)
5. M-C. Chang, A polynomial bound in Freiman's theorem, Duke Math. J. 113 (2002), 399-419.MR 1909605 (2003d:11151)
6. Y. G. Chen, On subset sums of a fixed set, Acta Arith. 106 (3) (2003), 207-211.MR 1957105 (2003j:11019)
7. D. da Silva and Y. O. Hamidoune, Cyclic Spaces for Grassmann Derivatives and Additive Theory, Bull. London Math. Soc. 26 (1994), 140-146.MR 1272299 (95i:11007)
8. P. Erdös, On the representation of large integers as sums of distinct summands taken from a fixed set, Acta. Arith. 7 (1962), 345-354.MR 0144846 (26:2387)
9. P. Erdös and R. Graham, Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathématique 28. Université de Genève, L'Enseignement Mathématique, Geneva, 1980. MR 0592420 (82j:10001)
10. G. Freiman, H. Halberstam, and I. Ruzsa, Integer sum sets containing long arithmetic progressions, J. London Math. Soc. (2) 46 (1992), no. 2, 193-201. MR 1182477 (93j:11008)
11. G. Freiman, New analytical results in subset-sum problem. Combinatorics and algorithms (Jerusalem, 1988). Discrete Math. 114 (1993), no. 1-3, 205-217. MR 1217753 (94b:11013)
12. G. Freiman, Foundations of a structural theory of set addition. Translated from the Russian. Translations of Mathematical Monographs, Vol. 37, American Mathematical Society, Providence, R. I., 1973. vii+108 pp.MR 0360496 (50:12944)
13. G. Freiman, Structure theory of set addition, Astérisque 258 (1999), xi, 1-33. MR 1701187 (2000j:11147)
14. J. Folkman, On the representation of integers as sums of distinct terms from a fixed sequence, Canad. J. Math. 18 (1966), 643-655. MR 0199169 (33:7318)
15. R. Graham, Complete sequences of polynomial values, Duke Math. J. 31 (1964), 275-286.MR 0162759 (29:63)
16. B. Green, Arithmetic progressions in sumsets, Geom. Funct. Anal. 12 (2002), no. 3, 584-597.MR 1924373 (2003i:11148)
17. R. Guy, Unsolved problems in Number Theory, Second Edition, Springer-Verlag 1994.MR 1299330 (96e:11002)
18. N. Hegyvári, On the representation of integers as sums of distinct terms from a fixed set, Acta Arith. 92 (2000), no. 2, 99-104. MR 1750309 (2001c:11014)
19. V. Lev and P. Smeliansky, On addition of two distinct sets of integers, Acta Arithmetica 70 (1) (1995), 85-91. MR 1318763 (96f:11035)
20. V. Lev, Optimal representations by sumsets and subset sums, Journal of Number Theory 62 (1) (1997), 127-143. MR 1430006 (97k:11015)
21. T. $\L$ uczak and T. Schoen, On the maximal density of sum-free sets, Acta Arith. 95 (2000), no. 3, 225-229.MR 1793162 (2001k:11018)
22. J. Olsen, An addition theorem modulo , Journal of Combin. Theory 5 (1968), 53-58.MR 0227130 (37:2715)
23. C. Pomerance and A. Sárközy, Combinatorial number theory, Handbook of combinatorics, Vol. 1, 2, pp. 967-1018, Elsevier, Amsterdam, 1995.MR 1373676 (97e:11032)
24. I. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379-388.MR 1281447 (95k:11011)
25. A. Sárközy, Finite addition theorems I, J. Number Theory 32 (1989), 114-130.MR 1002119 (91f:11007)
26. E. Szemerédi, On a conjecture of Erdös and Heilbronn, Acta Arith. 17 (1970), 227-229.MR 0268159 (42:3058)
27. E. Szemerédi and V. H. Vu, Long arithmetic progressions in sumsets and the number of -sum-free sets, Proceedings of London Mathematics Society 90 (2005), 273-296.
28. E. Szemerédi and V. H. Vu, Finite and infinite arithmetic progressions in sumsets, to appear in Annals of Mathematics.
29. R. Vaughan, The Hardy-Littlewood method. Second edition. Cambridge Tracts in Mathematics, 125. Cambridge University Press, Cambridge, 1997. MR 1435742 (98a:11133)
30. V. H. Vu, Olson's theorem for cyclic groups, submitted.
31. V. H. Vu, New results concerning subset sums, in preparation.