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, UCSD, La Jolla, CA 92093<, United States