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$: \[ 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.

- 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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0012-365X%2893%2990367-3 - 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** - 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 https://doi.org/10.4153/CJM-1966-065-2 - R. L. Graham,
*Complete sequences of polynomial values*, Duke Math. J.**31**(1964), 275–285. MR**162759** - B. Green,
*Arithmetic progressions in sumsets*, Geom. Funct. Anal.**12**(2002), no. 3, 584–597. MR**1924373**, DOI https://doi.org/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** - 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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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** - 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 https://doi.org/10.1007/BF01876039 - A. Sárközy,
*Finite addition theorems. I*, J. Number Theory**32**(1989), no. 1, 114–130. MR**1002119**, DOI https://doi.org/10.1016/0022-314X%2889%2990102-9 - E. Szemerédi,
*On a conjecture of Erdős and Heilbronn*, Acta Arith.**17**(1970), 227–229. MR**268159**, DOI https://doi.org/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**
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*.

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

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.