PROVED
This has been solved in the affirmative.
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?
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.
View the LaTeX source
This page was last edited 02 December 2025.
Additional thanks to: Zach Hunter
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #343, https://www.erdosproblems.com/343, accessed 2026-02-13
