Problem Statement
Let $A\subseteq \mathbb{N}$ be an infinite set such that $\lvert A\cap \{1,\ldots,N\}\rvert=o(N)$. Is it true that\[\limsup_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}\geq 3?\]
Categories:
Additive Combinatorics
Progress
Erdős writes it is 'easy to see' that this holds with $3$ replaced by $2$, and that $3$ would be best possible here. We do not see an easy argument that this holds with $2$, but this follows e.g. from the main result of Mann [Ma60].The answer is yes, proved by Freiman [Fr73].
See also [899] for the difference set analogue.
This problem has been formalised in Lean as part of the Google DeepMind Formal Conjectures project.
Source: erdosproblems.com/245 | Last verified: January 14, 2026