Long arithmetic progressions in sumsets and the Erdos-Folkman Conjecture

Van Vu, UCSD

Let A be a subset of {1,2, ...,n}. The Erdos-Turan Conjecture (proved by different methods by Szemeredi, Furstenberg, Gowers and Rodl et. al.) asserts that if A has constant positive density, then it contains a long arithmetic progression. The current best estimate for the length (due to Gowers) is an iterated-logarithmic function of n. The situation changes significantly if one is allowed to add A to itself a few times. Let kA (resp. k*A) denote the set of numbers which can be represented as a sum of k elements (resp. k different elements) of A. For instance, Bourgain showed that if A has constant positive density then 2A contains an arithmetic progression of length exp(c ln^{1/3}n). Similar results have been obtained by many researchers, including Halberstam, Freiman, Green, Lev, Ruzsa and Sarkozi. Recently we were able to prove sharp bounds on the length of the longest arithmetic progression in both kA and k*A, (as a function of k, |A| and n) for a wide range of k and |A|. In this talk, we will survey these results. We will also discuss some applications, including a conjecture of Erdos and Folkman on complete sequences. An infinite sequence A of positive integers is complete if every sufficiently large integer can be represented as a sum of distinct elements of A. Erdos and Folkman conjectured (back in 1960s) that if a sequence is sufficiently dense and satisfies a trivial modularity assumption, then it is complete. We were able to prove this conjecture, using the above mentioned (sharp bound) results. Joint work with Endre Szemeredi.