OPEN
This is open, and cannot be resolved with a finite computation.
Let $f(n)$ be maximal such that if $B\subset (2n,4n)\cap \mathbb{N}$ there exists some $C\subset (n,2n)\cap \mathbb{N}$ such that $c_1+c_2\not\in B$ for all $c_1\neq c_2\in C$ and $\lvert C\rvert+\lvert B\rvert \geq f(n)$.
Estimate $f(n)$. In particular is it true that $f(n)\leq n^{1/2+o(1)}$?
A conjecture of Choi
[Ch71], who proved $f(n) \ll n^{3/4}$. Adenwalla in the comments has provided a simple construction that proves $f(n) \gg n^{1/2}$.
Hunter in the comments has sketched an argument that gives $f(n) \ll n^{2/3+o(1)}$. The bound\[f(n) \ll (n\log n)^{2/3}\]was proved by Baltz, Schoen, and Srivastav
[BSS00].
View the LaTeX source
This page was last edited 24 October 2025.
Additional thanks to: Sarosh Adenwalla, Zach Hunter, and Mark Sellke
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 #788, https://www.erdosproblems.com/788, accessed 2026-01-16
