Sum-free subsets: how much bigger than $n/3$ can one always find? Estimate $f(n)$ (Erdős #792)
Statement
Let $f(n)$ be maximal such that in any $A\subset \mathbb{Z}$ with $\lvert A\rvert=n$ there exists some sum-free subset $B\subseteq A$ with $\lvert B\rvert \geq f(n)$, so that there are no solutions to $$a+b=c$$ with $a,b,c\in B$. Estimate $f(n)$. (The constant is known: $f(n)=n/3+o(n)$; the problem is the second-order term $f(n)-n/3$.)
Acceptance. FULLY RESOLVES: determine the order of the second-order term — a proof that $f(n) = n/3 + \Theta(g(n))$ for an explicit function $g$, i.e. matching (up to constant factors) upper and lower bounds on $f(n)-n/3$. Machine-checkable (Lean/Coq) proof preferred; otherwise a complete written proof with all steps. ADVANCES: (a) a lower bound on $f(n)-n/3$ asymptotically strictly better than the best lower bound stated in the background, with full proof; (b) the first explicit quantitative upper bound $f(n) \leq n/3 + h(n)$ with a named function $h(n)=o(n)$, improving on the qualitative $o(n)$ bound stated in the background — e.g. via an explicit family of sets $A$ together with a proof or machine-verifiable certificate that every sum-free subset of $A$ is small; (c) exact values of $f(n)$ for small $n$, via a rigorous reduction to a finite search plus reproducible code and an exhaustiveness certificate. Deliver the proof file, or the adversarial construction + certification, or the search code + table of exact values.
Background
A classic problem of Erdős [Er65], [Er73], [Er92c], also recorded as Problem 1.22 in [Va99], and Problem 1 on Ben Green's open problems list; listed as open on erdosproblems.com/792 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). The history is a long fight over lower-order terms. Erdős [Er65] gave a simple argument (random dilation into the middle third mod $p$) showing $f(n) \geq n/3$. Alon and Kleitman [AlKl90] improved this to $f(n)\geq \frac{n+1}{3}$, and Bourgain [Bo97] to $\frac{n+2}{3}$. The current record lower bound is a 2025 breakthrough of Bedert [Be25b]: $$f(n)\geq \frac{n}{3}+c\log\log n$$ for some constant $c>0$ — the first unbounded gain over $n/3$. On the other side, Eberhard, Green, and Manners [EGM14] proved $$f(n) \leq \frac{n}{3}+o(n),$$ so the constant $1/3$ is sharp, but no explicit second-order upper bound is known: the truth lies somewhere between $n/3+c\log\log n$ and $n/3+o(n)$. The attacker's tools: on the upper-bound side, explicit adversarial sets $A$ whose maximum sum-free subset can be certified small (for a candidate $A$, the maximum sum-free subset is a maximum independent set in a 3-uniform hypergraph, computable by ILP/SAT for moderate $n$); on the lower-bound side, sharpening Bedert's structural analysis.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #792 (T. F. Bloom) | website |
| REF-02 | Ben Green, 100 open problems — Problem 1 | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.