OPEN
This is open, and cannot be resolved with a finite computation.
Let $l(n)$ be maximal such that if $A\subset\mathbb{Z}$ with $\lvert A\rvert=n$ then there exists a sum-free $B\subseteq A$ with $\lvert B\rvert \geq l(n)$ - that is, $B$ is such that there are no solutions to\[a_1=a_2+\cdots+a_r\]with $a_i\in B$ all distinct.
Estimate $l(n)$. In particular, is it true that $l(n)n^{-1/2}\to \infty$? Is it true that $l(n)< n^{1-c}$ for some $c>0$?
Erdős observed that $l(n)\geq (n/2)^{1/2}$, which Choi improved to $l(n)>(1+c)n^{1/2}$ for some $c>0$. Erdős
[Er73] thought he could prove $l(n)=o(n)$ but had 'difficulties in reconstructing [his] proof'. (In
[Er65] he wrote 'by complicated arguments we can show $l(n)=o(n)$'.)
Choi, Komlós, and Szemerédi
[CKS75] proved\[\left(\frac{\log n}{\log\log n}n\right)^{1/2}\ll l(n) \ll \frac{n}{\log n}.\]They further conjecture that $l(n)\geq n^{1-o(1)}$.
See also
[876].
View the LaTeX source
This page was last edited 31 October 2025.
Additional thanks to: Stijn Cambie
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 #790, https://www.erdosproblems.com/790, accessed 2026-01-16
