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. George E. Andrews, The theory of partitions, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998. Reprint of the 1976 original. MR 1634067
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
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
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
5. Mei-Chu Chang, A polynomial bound in Freiman’s theorem, Duke Math. J. 113 (2002), no. 3, 399–419. MR 1909605, https://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, https://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, https://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, https://doi.org/10.4064/aa-7-4-345-354
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. 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, https://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, https://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
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
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, https://doi.org/10.4153/CJM-1966-065-2
15. R. L. Graham, Complete sequences of polynomial values, Duke Math. J. 31 (1964), 275–285. MR 0162759
16. B. Green, Arithmetic progressions in sumsets, Geom. Funct. Anal. 12 (2002), no. 3, 584–597. MR 1924373, https://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
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, https://doi.org/10.4064/aa-92-2-99-104
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, https://doi.org/10.4064/aa-70-1-85-91
20. Vsevolod F. Lev, Optimal representations by sumsets and subset sums, J. Number Theory 62 (1997), no. 1, 127–143. MR 1430006, https://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, https://doi.org/10.4064/aa-95-3-225-229
22. John E. Olson, An addition theorem for the elementary Abelian group, J. Combinatorial Theory 5 (1968), 53–58. MR 0227130
23. Carl Pomerance and András Sárközy, Combinatorial number theory, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 967–1018. MR 1373676
24. I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379–388. MR 1281447, https://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, https://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, https://doi.org/10.4064/aa-17-3-227-229
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
30. V. H. Vu, Olson's theorem for cyclic groups, submitted.
31. V. H. Vu, New results concerning subset sums, in preparation.