Problem Statement
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$?
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$?
Categories:
Additive Combinatorics
Progress
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].
Source: erdosproblems.com/790 | Last verified: January 16, 2026