Available in electronic format
Available in print format		 Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN: 1088-6834(e) ISSN: 0894-0347(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Long arithmetic progressions in sumsets: Thresholds and bounds

Author(s): E. Szemerédi; V. Vu
Journal: J. Amer. Math. Soc. 19 (2006), 119-169.
MSC (2000): Primary 11B25, 11P70, 11B75
Posted: September 13, 2005
Retrieve article in: PDF DVI PostScript

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:

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: 10.1090/S0894-0347-05-00502-3
PII: S 0894-0347(05)00502-3
Keywords: Sumsets, arithmetic progressions, generalized arithmetic progressions, complete and subcomplete sequences, inverse theorems.
Received by editor(s): October 6, 2004
Posted: 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 of article: Copyright 2005, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google