Logo
All Random Solved Random Open
SOLVED
If $A\subseteq \mathbb{N}$ is a set of integers such that \[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1/2}\] for all $N$ then must $A$ be subcomplete? That is, must \[P(A) = \left\{\sum_{n\in B}n : B\subseteq A\textrm{ finite }\right\}\] contain an infinite arithmetic progression?
Folkman proved this under the stronger assumption that \[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1/2+\epsilon}\] for some $\epsilon>0$.

This is true, and was proved by Szemerédi and Vu [SzVu06]. The stronger conjecture that this is true under \[\lvert A\cap \{1,\ldots,N\}\rvert\geq (2N)^{1/2}\] seems to be still open (this would be best possible as shown by [Er61b].