Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Journal of the American Mathematical Society
Journal of the American Mathematical Society
ISSN 1088-6834(online) ISSN 0894-0347(print)

 

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
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$:

\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 [Enhancements On Off] (What's this?)


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: http://dx.doi.org/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
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.