Problem Statement
If $A\subseteq \mathbb{N}$ is a multiset of integers such that\[\lvert A\cap \{1,\ldots,N\}\rvert\gg N\]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
A problem of Folkman. Folkman [Fo66] showed that this is true if\[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1+\epsilon}\]for some $\epsilon>0$ and all $N$.The original question was answered by Szemerédi and Vu [SzVu06] (who proved that the answer is yes).
This is best possible, since Folkman [Fo66] showed that for all $\epsilon>0$ there exists a multiset $A$ with\[\lvert A\cap \{1,\ldots,N\}\rvert\gg N^{1-\epsilon}\]for all $N$, such that $A$ is not subcomplete.
Source: erdosproblems.com/343 | Last verified: January 14, 2026