Finite and infinite arithmetic progressions in sumsets

Abstract

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.

Authors

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