Problem Statement
Let $g(n)$ be maximal such that given any set $A\subset \mathbb{R}$ with $\lvert A\rvert=n$ there exists some $B\subseteq A$ of size $\lvert B\rvert\geq g(n)$ such that $b_1+b_2\not\in A$ for all $b_1\neq b_2\in B$.
Estimate $g(n)$.
Estimate $g(n)$.
Categories:
Additive Combinatorics
Progress
This function was considered by Erdős and Moser. Choi observed that, without loss of generality, one can assume that $A\subset \mathbb{Z}$.Klarner proved $g(n) \gg \log n$ (indeed, a greedy construction suffices). Choi [Ch71] proved $g(n) \ll n^{2/5+o(1)}$. The current best bounds known are\[(\log n)^{1+c} \ll g(n) \ll \exp(\sqrt{\log n})\]for some constant $c>0$, the lower bound due to Sanders [Sa21] and the upper bound due to Ruzsa [Ru05]. Beker [Be25] has proved\[(\log n)^{1+\tfrac{1}{68}+o(1)} \ll g(n).\]
Source: erdosproblems.com/787 | Last verified: January 16, 2026