Finite and infinite arithmetic progressions in sumsets


We prove that if $A$ is a subset of at least $cn^{1/2}$ elements of $\{1, \dots, n\}$, where $c$ is a sufficiently large constant, then the collection of subset sums of $A$ contains an arithmetic progression of length $n$. As an application, we confirm a long standing conjecture of Erdős and Folkman on complete sequences.


Endre Szemerédi

Computer Science Department
Rutgers University
Piscataway, NJ 08854
United States

Van H. Vu

Department of Mathematics
La Jolla, CA 92093
United States