Long arithmetic progressions in sumsets: Thresholds and bounds

Szemerédi, E.; Vu, V.

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

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6834(online) ISSN 0894-0347(print)

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
Posted: September 13, 2005
MathSciNet review: 2169044
Full-text PDF Free Access

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. George E. Andrews, The theory of partitions, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998. Reprint of the 1976 original. MR 1634067 (99c:11126)
2. Yuri Bilu, Structure of sets with small sumset, Astérisque 258 (1999), xi, 77–108 (English, with English and French summaries). Structure theory of set addition. MR 1701189 (2000h:11109)
3. J. Bourgain, On arithmetic progressions in sums of sets of integers, A tribute to Paul Erdős, Cambridge Univ. Press, Cambridge, 1990, pp. 105–109. 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. Mei-Chu Chang, A polynomial bound in Freiman’s theorem, Duke Math. J. 113 (2002), no. 3, 399–419. MR 1909605 (2003d:11151), http://dx.doi.org/10.1215/S0012-7094-02-11331-3
6. Yong-Gao Chen, On subset sums of a fixed set, Acta Arith. 106 (2003), no. 3, 207–211. MR 1957105 (2003j:11019), http://dx.doi.org/10.4064/aa106-3-1
7. J. A. Dias da Silva and Y. O. Hamidoune, Cyclic spaces for Grassmann derivatives and additive theory, Bull. London Math. Soc. 26 (1994), no. 2, 140–146. MR 1272299 (95i:11007), http://dx.doi.org/10.1112/blms/26.2.140
8. P. Erdős, On the representation of large integers as sums of distinct summands taken from a fixed set, Acta Arith. 7 (1961/1962), 345–354. MR 0144846 (26 #2387)
9. P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L’Enseignement Mathématique [Monographs of L’Enseignement Mathématique], vol. 28, Université de Genève L’Enseignement Mathématique, Geneva, 1980. MR 592420 (82j:10001)
10. G. A. Freiman, H. Halberstam, and I. Z. Ruzsa, Integer sum sets containing long arithmetic progressions, J. London Math. Soc. (2) 46 (1992), no. 2, 193–201. MR 1182477 (93j:11008), http://dx.doi.org/10.1112/jlms/s2-46.2.193
11. Gregory A. Freiman, New analytical results in subset-sum problem, Discrete Math. 114 (1993), no. 1-3, 205–217. Combinatorics and algorithms (Jerusalem, 1988). MR 1217753 (94b:11013), http://dx.doi.org/10.1016/0012-365X(93)90367-3
12. G. A. Freĭman, Foundations of a structural theory of set addition, American Mathematical Society, Providence, R. I., 1973. Translated from the Russian; Translations of Mathematical Monographs, Vol 37. MR 0360496 (50 #12944)
13. Gregory A. Freiman, Structure theory of set addition, Astérisque 258 (1999), xi, 1–33 (English, with English and French summaries). Structure theory of set addition. MR 1701187 (2000j:11147)
14. Jon 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. L. Graham, Complete sequences of polynomial values, Duke Math. J. 31 (1964), 275–285. MR 0162759 (29 #63)
16. B. Green, Arithmetic progressions in sumsets, Geom. Funct. Anal. 12 (2002), no. 3, 584–597. MR 1924373 (2003i:11148), http://dx.doi.org/10.1007/s00039-002-8258-4
17. Richard K. Guy, Unsolved problems in number theory, 2nd ed., Problem Books in Mathematics, Springer-Verlag, New York, 1994. Unsolved Problems in Intuitive Mathematics, I. MR 1299330 (96e:11002)
18. Norbert 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. Vsevolod F. Lev and Pavel Y. Smeliansky, On addition of two distinct sets of integers, Acta Arith. 70 (1995), no. 1, 85–91. MR 1318763 (96f:11035)
20. Vsevolod F. Lev, Optimal representations by sumsets and subset sums, J. Number Theory 62 (1997), no. 1, 127–143. MR 1430006 (97k:11015), http://dx.doi.org/10.1006/jnth.1997.2012
21. Tomasz Łuczak and Tomasz Schoen, On the maximal density of sum-free sets, Acta Arith. 95 (2000), no. 3, 225–229. MR 1793162 (2001k:11018)
22. John E. Olson, An addition theorem for the elementary Abelian group, J. Combinatorial Theory 5 (1968), 53–58. MR 0227130 (37 #2715)
23. Carl Pomerance and András Sárközy, Combinatorial number theory, Handbook of combinatorics, Vol. 1, 2, Elsevier, Amsterdam, 1995, pp. 967–1018. MR 1373676 (97e:11032)
24. I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379–388. MR 1281447 (95k:11011), http://dx.doi.org/10.1007/BF01876039
25. A. Sárközy, Finite addition theorems. I, J. Number Theory 32 (1989), no. 1, 114–130. MR 1002119 (91f:11007), http://dx.doi.org/10.1016/0022-314X(89)90102-9
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. C. Vaughan, The Hardy-Littlewood method, 2nd ed., Cambridge Tracts in Mathematics, vol. 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.