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
consists of those numbers which can be represented as a sum of
elements of
:

Closely related and equally interesting notion is that of , which is the collection of numbers which can be represented as a sum of
different elements of
:

The goal of this paper is to investigate the structure of and
, where
is a subset of
. 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.
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.
Retrieve articles in Journal of the American Mathematical Society with MSC (2000): 11B25, 11P70, 11B75
Retrieve articles in all journals with MSC (2000): 11B25, 11P70, 11B75
Additional Information
E. Szemerédi
Affiliation:
Department of Computer Science, Rutgers University, New Brunswick, New Jersey 08854
Email:
szemered@cs.rutgers.edu
V. Vu
Affiliation:
Department of Mathematics, University of California, San Diego, La Jolla, California 92093-0112
Email:
vanvu@ucsd.edu, vanvu@math.rutgers.edu
DOI:
https://doi.org/10.1090/S0894-0347-05-00502-3
Keywords:
Sumsets,
arithmetic progressions,
generalized arithmetic progressions,
complete and subcomplete sequences,
inverse theorems.
Received by editor(s):
October 6, 2004
Published electronically:
September 13, 2005
Additional Notes:
The first author is supported by an NSF grant.
The second author is an A. Sloan Fellow and is supported by an NSF Career Grant.
Article copyright:
© Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.