Long arithmetic progressions in sumsets: Thresholds and bounds

Szemerédi, E.; Vu, V.

doi:10.1090/S0894-0347-05-00502-3

Long arithmetic progressions in sumsets: Thresholds and bounds
HTML articles powered by AMS MathViewer

by E. Szemerédi and V. Vu;

J. Amer. Math. Soc. 19 (2006), 119-169

DOI: https://doi.org/10.1090/S0894-0347-05-00502-3

Published electronically: September 13, 2005

PDF | 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, RI, 1973. Translated from the Russian. MR 360496
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

Proceedings of London Mathematics Society

to appear in Annals of Mathematics

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

submitted

in preparation