Strongly sum-free subsets of every $n$-set: is $l(n)<n^{1-c}$, or is $l(n)\ge n^{1-o(1)}$? (Erdős #790)
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)$ — here sum-free means (in the strong sense) that there are no solutions to $$a_1=a_2+\cdots+a_r$$ with $a_i\in B$ all distinct, i.e. no element of $B$ is a sum of distinct other elements of $B$. 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$?
Acceptance. FULLY RESOLVES: a complete proof either that $l(n) < n^{1-c}$ for some explicit $c>0$, or that $l(n) \geq n^{1-o(1)}$ (the Choi–Komlós–Szemerédi conjecture) — settling the dichotomy in the problem. Machine-checkable (Lean/Coq) proof preferred; otherwise a complete written proof with all steps. ADVANCES: (a) an upper bound asymptotically strictly better than the best upper bound stated in the background, via an explicit family of sets $A$ with proof that every strongly-sum-free subset is small; (b) a lower bound asymptotically strictly better than the best lower bound stated in the background, with full proof; (c) exact values of $l(n)$ for small $n$ computed by reproducible exhaustive or SAT-based min-max search with an exhaustiveness certificate, plus an empirical growth estimate. Deliver the proof file, or the construction + proof, or the search code + table of exact values.
Background
Posed by Erdős [Er65, p.188], [Er73, p.130]; also recorded as Problem 1.22 in [Va99]. Listed as open on erdosproblems.com/790 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). Note this 'sum-free' is stronger than the usual $x+y=z$ notion: sums of arbitrarily many distinct elements are forbidden. Frontier: Erdős observed $l(n)\geq (n/2)^{1/2}$, and Choi improved this to $l(n)>(1+c)n^{1/2}$ for some $c>0$. Erdős [Er73] believed he could prove $l(n)=o(n)$ but reported 'difficulties in reconstructing [his] proof' (in [Er65] he wrote that 'by complicated arguments we can show $l(n)=o(n)$'). Choi, Komlós, and Szemerédi [CKS75] then proved $$\left(\frac{\log n}{\log\log n}n\right)^{1/2}\ll l(n) \ll \frac{n}{\log n},$$ which both answers the first sub-question affirmatively ($l(n)n^{-1/2}\to\infty$) and confirms $l(n)=o(n)$. What remains is the polynomial-scale dichotomy: [CKS75] conjecture $l(n)\geq n^{1-o(1)}$, while the problem asks whether $l(n)<n^{1-c}$ for some fixed $c>0$ — the gap between $n^{1/2}(\log n/\log\log n)^{1/2}$ and $n/\log n$ is wide open. Closely related: Erdős #876 (erdosproblems.com/876). The attacker's tools: adversarial constructions of sets $A$ with only small strongly-sum-free subsets (to push the upper bound below $n/\log n$), and exact computation of $l(n)$ for small $n$ via SAT/ILP min-max search to reveal the empirical growth.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #790 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.