Dual View Random Solved Random Open
DISPROVED (LEAN) This has been solved in the negative and the proof verified in Lean.
Let $A\subseteq \mathbb{N}$ be an additive basis (of any finite order) such that $\lvert A\cap \{1,\ldots,N\}\rvert=o(N)$. Is it true that\[\lim_{N\to \infty}\frac{\lvert (A+A)\cap \{1,\ldots,N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}=\infty?\]
The answer is no, and a counterexample was provided by Turjányi [Tu84]. This was generalised (to the replacement of $A+A$ by the $h$-fold sumset $hA$ for any $h\geq 2$) by Ruzsa and Turjányi [RT85]. Ruzsa and Turjányi do prove (under the same hypotheses) that\[\lim_{N\to \infty}\frac{\lvert (A+A+A)\cap \{1,\ldots,3N\}\rvert}{\lvert A\cap \{1,\ldots,N\}\rvert}=\infty,\]and conjecture that the same should be true with $(A+A)\cap \{1,\ldots,2N\}$ in the numerator.

View the LaTeX source

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None

Additional thanks to: Zachary Chase, 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 #337, https://www.erdosproblems.com/337, accessed 2026-01-14