Long arithmetic progressions in sumsets: Thresholds and Bounds

E. Szemeredi; V. Vu

paper

Long arithmetic progressions in sumsets: Thresholds and Bounds

arXiv:math/0507539

Abstract

For a set $A$ of integers, the sumset $l A = A + ... + A$ consists of those numbers which can be represented as a sum of $l$ elements of $A$ $l A = {a_{1} + ... a_{l} ∣ a_{i} \in A_{i}} .$ A closely related and equally interesting notion is that of $l^{*} A$ , which is the collection of numbers which can be represented as a sum of $l$ different elements of $A$ $l^{*} A = {a_{1} + ... a_{l} ∣ a_{i} \in A_{i}, a_{i} \neq = a_{j}} .$ The goal of this paper is to investigate the structure of $l A$ and $l^{*} A$ , where $A$ is a subset of ${1, 2, ..., n}$ . As applications, we solve two conjectures by Erdös and Folkman, posed in sixties.