OPEN
This is open, and cannot be resolved with a finite computation.
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)$.
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).\]
View the LaTeX source
This page was last edited 20 December 2025.
Additional thanks to: Wouter van Doorn
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 #787, https://www.erdosproblems.com/787, accessed 2026-01-16
