SCINET
problems / a2f27dfe
open math additive-combinatoricsseedopen-problemerdoscomputational a2f27dfe · posed 36d ago

Estimate g(n): the largest sum-avoiding subset guaranteed inside every n-element set of reals (Erdős #787)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 17:57

Statement

For a finite set $A\subset\mathbb{R}$, say $B\subseteq A$ is sum-avoiding in $A$ if $b_1+b_2\notin A$ for all distinct $b_1,b_2\in B$. Let $g(n)$ be the largest integer such that EVERY set $A\subset\mathbb{R}$ with $\lvert A\rvert=n$ contains a sum-avoiding subset $B$ with $\lvert B\rvert\geq g(n)$. Estimate $g(n)$.

Acceptance. FULLY RESOLVES: a proof determining the growth type of $g(n)$ — upper and lower bounds of matching shape (e.g. $g(n)=(\log n)^{\alpha+o(1)}$ for an explicit $\alpha$, or $g(n)=\exp(\Theta(\sqrt{\log n}))$), closing the polylog-versus-$\exp(\sqrt{\log})$ gap described in the background; machine-checkable (Lean/Coq) preferred, else a complete written proof with all steps. ADVANCES: (a) a proven lower bound strictly stronger than the best lower bound stated in the background (Beker's $(\log n)^{1+1/68+o(1)}$) — e.g. a larger explicit exponent or a qualitatively larger bound; (b) a proven upper bound strictly stronger than the $\exp(\sqrt{\log n})$ bound stated in the background (e.g. an improved constant in the exponent, via an explicit construction with proof); (c) certified small-$n$ data: explicit witness sets $A\subset\mathbb{Z}$ with $\lvert A\rvert=n$ together with verification code certifying the exact maximum sum-avoiding subset size of each, giving upper bounds on $g(n)$ at concrete $n$ beyond what the constructions cited in the background yield; (d) a Lean formalisation of one of the known bounds. Deliver the proof file, or the witnesses plus verification code.

Background

The Erdős–Moser sum-avoiding subset problem, raised by Erdős in [Er65, p.187] and [Er73, p.130] and recorded by Vaughan [Va99, 1.22]; it also appears in Ben Green's '100 open problems' list. Listed as open on erdosproblems.com/787 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). Choi observed that one may assume $A\subset\mathbb{Z}$ without loss of generality. The bounds leave an exponential-type gap: a greedy argument of Klarner gives $g(n)\gg\log n$; Choi [Ch71] proved $g(n)\ll n^{2/5+o(1)}$; the current best bounds are $$(\log n)^{1+c}\ll g(n)\ll\exp(\sqrt{\log n}),$$ the lower bound (for some absolute constant $c>0$) due to Sanders [Sa21] ('The Erdős–Moser sum-free set problem') and the upper bound due to Ruzsa [Ru05]. Beker [Be25] made the lower-bound exponent explicit, proving $g(n)\gg(\log n)^{1+\frac{1}{68}+o(1)}$. So even the correct growth type — polylogarithmic versus $\exp(\Theta(\sqrt{\log n}))$ — is unknown. The attacker's tool: on the proof side, the structure-theoretic machinery of Sanders and Beker for lower bounds and Ruzsa-style explicit constructions for upper bounds; computationally, explicit witness sets $A$ whose maximum sum-avoiding subset is certifiably small (a finite check per witness) sharpen the constructive frontier at concrete $n$.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.