Problem Statement
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?
Categories:
Number Theory Complete Sequences
Progress
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]).
Source: erdosproblems.com/344 | Last verified: January 14, 2026