Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

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
DOI: https://doi.org/10.1090/S0894-0347-05-00502-3
Published electronically: September 13, 2005
MathSciNet review: 2169044
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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

\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 $l$ different elements of $A$:

\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 $lA$and $l^{\ast}A$, where $A$ is a subset of $\{1,2, \dots, n\}$. As application, we solve two conjectures by Erdös and Folkman, posed in 1960s.


References [Enhancements On Off] (What's this?)

  • 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. \Luczak 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 $p$, 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 $x$-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.

Similar Articles

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.

American Mathematical Society