## Long arithmetic progressions in sumsets: Thresholds and bounds

HTML articles powered by AMS MathViewer

- by E. Szemerédi and V. Vu PDF
- J. Amer. Math. Soc.
**19**(2006), 119-169 Request permission

## 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$: \[ lA =\{a_1+\dots + a_l| a_i \in A_i \}. \] 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$: \[ l^{\ast }A =\{a_1+\dots + a_l| a_i \in A_i, a_i \neq a_j \}. \] 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

- George E. Andrews,
*The theory of partitions*, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1998. Reprint of the 1976 original. MR**1634067** - 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** - 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** - 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**130236** - Mei-Chu Chang,
*A polynomial bound in Freiman’s theorem*, Duke Math. J.**113**(2002), no. 3, 399–419. MR**1909605**, DOI 10.1215/S0012-7094-02-11331-3 - Yong-Gao Chen,
*On subset sums of a fixed set*, Acta Arith.**106**(2003), no. 3, 207–211. MR**1957105**, DOI 10.4064/aa106-3-1 - 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**, DOI 10.1112/blms/26.2.140 - P. Erdős,
*On the representation of large integers as sums of distinct summands taken from a fixed set*, Acta Arith.**7**(1961/62), 345–354. MR**144846**, DOI 10.4064/aa-7-4-345-354 - 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** - 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**, DOI 10.1112/jlms/s2-46.2.193 - 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**, DOI 10.1016/0012-365X(93)90367-3 - G. A. Freĭman,
*Foundations of a structural theory of set addition*, Translations of Mathematical Monographs, Vol 37, American Mathematical Society, Providence, R.I., 1973. Translated from the Russian. MR**0360496** - 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** - Jon Folkman,
*On the representation of integers as sums of distinct terms from a fixed sequence*, Canadian J. Math.**18**(1966), 643–655. MR**199169**, DOI 10.4153/CJM-1966-065-2 - R. L. Graham,
*Complete sequences of polynomial values*, Duke Math. J.**31**(1964), 275–285. MR**162759**, DOI 10.1215/S0012-7094-64-03126-6 - B. Green,
*Arithmetic progressions in sumsets*, Geom. Funct. Anal.**12**(2002), no. 3, 584–597. MR**1924373**, DOI 10.1007/s00039-002-8258-4 - 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**, DOI 10.1007/978-1-4899-3585-4 - 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**, DOI 10.4064/aa-92-2-99-104 - 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**, DOI 10.4064/aa-70-1-85-91 - Vsevolod F. Lev,
*Optimal representations by sumsets and subset sums*, J. Number Theory**62**(1997), no. 1, 127–143. MR**1430006**, DOI 10.1006/jnth.1997.2012 - Tomasz Łuczak and Tomasz Schoen,
*On the maximal density of sum-free sets*, Acta Arith.**95**(2000), no. 3, 225–229. MR**1793162**, DOI 10.4064/aa-95-3-225-229 - John E. Olson,
*An addition theorem for the elementary Abelian group*, J. Combinatorial Theory**5**(1968), 53–58. MR**227130**, DOI 10.1016/S0021-9800(68)80028-6 - 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** - I. Z. Ruzsa,
*Generalized arithmetical progressions and sumsets*, Acta Math. Hungar.**65**(1994), no. 4, 379–388. MR**1281447**, DOI 10.1007/BF01876039 - A. Sárközy,
*Finite addition theorems. I*, J. Number Theory**32**(1989), no. 1, 114–130. MR**1002119**, DOI 10.1016/0022-314X(89)90102-9 - E. Szemerédi,
*On a conjecture of Erdős and Heilbronn*, Acta Arith.**17**(1970), 227–229. MR**268159**, DOI 10.4064/aa-17-3-227-229
szemvu E. Szemerédi and V. H. Vu, Long arithmetic progressions in sumsets and the number of $x$-sum-free sets, - R. C. Vaughan,
*The Hardy-Littlewood method*, 2nd ed., Cambridge Tracts in Mathematics, vol. 125, Cambridge University Press, Cambridge, 1997. MR**1435742**, DOI 10.1017/CBO9780511470929
Vunew1 V. H. Vu, Olson’s theorem for cyclic groups,

*Proceedings of London Mathematics Society*90 (2005), 273-296. szemvu2 E. Szemerédi and V. H. Vu, Finite and infinite arithmetic progressions in sumsets,

*to appear in Annals of Mathematics*.

*submitted*. Vunew2 V. H. Vu, New results concerning subset sums,

*in preparation*.

## 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
- 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. - © Copyright 2005
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2169044