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

Largest subset where equal sums force equally many summands: estimate $h(n)$ (Erdős #789)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 18:20

Statement

Let $h(n)$ be maximal such that if $A\subseteq \mathbb{Z}$ with $\lvert A\rvert=n$ then there is $B\subseteq A$ with $\lvert B\rvert \geq h(n)$ such that if $a_1+\cdots+a_r=b_1+\cdots+b_s$ with $a_i,b_i\in B$ then $r=s$. (That is, every $n$-element set of integers contains a subset $B$ of size at least $h(n)$ in which a sum of $r$ elements of $B$ can never equal a sum of $s$ elements of $B$ unless $r=s$ — the number of summands is determined by the value of the sum.) Estimate $h(n)$.

Acceptance. FULLY RESOLVES: determine the order of growth of $h(n)$ up to $n^{o(1)}$ — a proof of matching upper and lower bounds $h(n) = n^{c+o(1)}$ for an explicit constant $c$. Machine-checkable (Lean/Coq) proof preferred; otherwise a complete written proof with all steps. ADVANCES: (a) an upper bound with exponent strictly below the best upper bound stated in the background, with full proof; (b) a lower-bound construction asymptotically strictly better than the best lower bound stated in the background, with proof of the distinct-length-sums property; (c) exact values of $h(n)$ for small $n$ via reproducible exhaustive search with an exhaustiveness certificate, plus an empirical exponent estimate; (d) a Lean formalization of Straus's upper bound or the Choi lower bound compatible with the existing formalized statement. Deliver the proof file, or the construction + verification, or the search code + table of exact values.

Background

Posed by Erdős [Er65], [Er73]; listed as open on erdosproblems.com/789 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). The known frontier leaves a polynomial gap. Upper bounds: Erdős [Er62c] first proved $h(n) \ll n^{5/6}$, and Straus [St66] improved this to $h(n) \ll n^{1/2}$, which remains the record. Lower bounds: Erdős observed $h(n) \gg n^{1/3}$ via a random-dilation construction — take $B=\{ a: \{ \alpha a\} \in n^{-1/3}+\tfrac{1}{2} (-n^{-2/3},n^{-2/3})\}$ for a random $\alpha\in [0,1]$ (here $\{x\}$ is the fractional part); [Er62c] and Choi [Ch74b] sharpened this to $h(n) \gg (n\log n)^{1/3}$, the current record. So $(n\log n)^{1/3} \ll h(n) \ll n^{1/2}$ and the true exponent (between $1/3$ and $1/2$) is unknown. Related problems on the same site: Erdős #186 (erdosproblems.com/186) and Erdős #874 (erdosproblems.com/874). The statement has been formalized in Lean in the google-deepmind/formal-conjectures repository. The attacker's tools: exact computation of $h(n)$ for small $n$ by exhaustive/SAT-style min-max search over subsets to reveal the empirical exponent, optimization of the random-dilation construction, and Lean formalization of the known partial results.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.