Long arithmetic progressions in sumsets: Thresholds and bounds

Szemerédi, E.¹ ; Vu, V.²

¹ Department of Computer Science, Rutgers University, New Brunswick, New Jersey 08854
² Department of Mathematics, University of California, San Diego, La Jolla, California 92093-0112

Journal of the American Mathematical Society, Tome 19 (2006) no. 1, pp. 119-169

Résumé

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.

Détail

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

Bibliographie

[1] Andrews, George E. The theory of partitions 1998

[2] Bilu, Yuri Structure of sets with small sumset Astérisque 1999

[3] Bourgain, J. On arithmetic progressions in sums of sets of integers 1990 105 109

[4] Cassels, J. W. S. On the representation of integers as the sums of distinct summands taken from a fixed set Acta Sci. Math. (Szeged) 1960 111 124

[5] Chang, Mei-Chu A polynomial bound in Freiman’s theorem Duke Math. J. 2002 399 419

[6] Chen, Yong-Gao On subset sums of a fixed set Acta Arith. 2003 207 211

[7] Dias Da Silva, J. A., Hamidoune, Y. O. Cyclic spaces for Grassmann derivatives and additive theory Bull. London Math. Soc. 1994 140 146

[8] Erdå‘S, P. On the representation of large integers as sums of distinct summands taken from a fixed set Acta Arith. 1961/62 345 354

[9] Erdå‘S, P., Graham, R. L. Old and new problems and results in combinatorial number theory 1980 128

[10] Freiman, G. A., Halberstam, H., Ruzsa, I. Z. Integer sum sets containing long arithmetic progressions J. London Math. Soc. (2) 1992 193 201

[11] Freiman, Gregory A. New analytical results in subset-sum problem Discrete Math. 1993 205 217

[12] Freä­Man, G. A. Foundations of a structural theory of set addition 1973

[13] Freiman, Gregory A. Structure theory of set addition Astérisque 1999

[14] Folkman, Jon On the representation of integers as sums of distinct terms from a fixed sequence Canadian J. Math. 1966 643 655

[15] Graham, R. L. Complete sequences of polynomial values Duke Math. J. 1964 275 285

[16] Green, B. Arithmetic progressions in sumsets Geom. Funct. Anal. 2002 584 597

[17] Guy, Richard K. Unsolved problems in number theory 1994

[18] Hegyvã¡Ri, Norbert On the representation of integers as sums of distinct terms from a fixed set Acta Arith. 2000 99 104

[19] Lev, Vsevolod F., Smeliansky, Pavel Y. On addition of two distinct sets of integers Acta Arith. 1995 85 91

[20] Lev, Vsevolod F. Optimal representations by sumsets and subset sums J. Number Theory 1997 127 143

[21] ŁUczak, Tomasz, Schoen, Tomasz On the maximal density of sum-free sets Acta Arith. 2000 225 229

[22] Olson, John E. An addition theorem for the elementary Abelian group J. Combinatorial Theory 1968 53 58

[23] Pomerance, Carl, Sã¡Rkã¶Zy, Andrã¡S Combinatorial number theory 1995 967 1018

[24] Ruzsa, I. Z. Generalized arithmetical progressions and sumsets Acta Math. Hungar. 1994 379 388

[25] Sã¡Rkã¶Zy, A. Finite addition theorems. I J. Number Theory 1989 114 130

[26] Szemerã©Di, E. On a conjecture of Erdős and Heilbronn Acta Arith. 1970 227 229

[27] Vaughan, R. C. The Hardy-Littlewood method 1997