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.
Additional thanks to: Zachary Chase, Zach Hunter
Proof expositions (0)
If you would like to contribute an exposition of a proof related to this problem, please message a moderator or leave your exposition as a comment.

No proof expositions yet.
Comments (1) Proof claims (0)
More information and links
(View history) (View the LaTeX source)

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-09-02

From the external database. (You can help update this.)
Formalised statement? Yes
Reactions
Likes None
Open to collaboration None
Currently working on None
Looks difficult None
Looks tractable None
Could be formalisable None
Working on formalising None