Arithmetic Progressions in Sumsets of Sparse Sets

Abstract

A set of positive integers $A\subset {\mathbb{Z}}_{>0}$ is \emph{log-sparse} if there is an absolute constant $C$ so that for any positive integer $x$ the sequence contains at most $C$ elements in the interval $[x,2x)$. In this note we study arithmetic progressions in sums of log-sparse subsets of ${\mathbb{Z}}_{>0}$. We prove that for any log-sparse subsets $S_1,\dots ,S_n$ of ${\mathbb{Z}}_{>0},$ the sumset $S=S_1+\cdots +S_n$ cannot contain an arithmetic progression of size greater than $n^{(1+o(1))n}.$ We also show that this is nearly tight by proving that there exist log-sparse sets $S_1,\dots ,S_n$ such that $S_1+\cdots +S_n$ contains an arithmetic progression of size $n^{(1-o(1))n}.$

6 pages. This version: improved upper bound, added one author