Problem Statement
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)}$?
Estimate $f(n)$. In particular is it true that $f(n)\leq n^{1/2+o(1)}$?
Categories:
Additive Combinatorics
Progress
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].
Source: erdosproblems.com/788 | Last verified: January 16, 2026