Maximum size of a minimally-vanishing signed unit-fraction set in $\{1,\ldots,N\}$ (Erdős #319)
Statement
For a set $A\subseteq\{1,\ldots,N\}$, call a sign function $\delta:A\to\{-1,+1\}$ (write $\delta_n=\delta(n)$) minimally vanishing if the full signed reciprocal sum cancels, $$\sum_{n\in A}\frac{\delta_n}{n}=0,$$ while no non-empty proper subset does: $$\sum_{n\in A'}\frac{\delta_n}{n}\neq 0\quad\text{for every non-empty }A'\subsetneq A.$$ What is the largest possible size $\lvert A\rvert$ of a set $A\subseteq\{1,\ldots,N\}$ that admits such a minimally-vanishing sign function? Determine this maximum as a function of $N$, in particular its asymptotic growth.
Acceptance. FULLY RESOLVES: a complete proof determining the maximum size $M(N)$ (at least its asymptotic order, ideally the leading constant) as a function of $N$ — an upper bound matching a construction — with the proof machine-checkable (Lean/Coq preferred, given the existing Lean formalisation) or fully written. ADVANCES: (a) improve the best known lower bound beyond $(1-\tfrac1e+o(1))N$ (the bound stated in background) with a proof or explicit construction; (b) prove any non-trivial upper bound of the form $M(N)\leq(1-c)N$ for a fixed $c>0$; or (c) compute the exact maximum for a new range of $N$ via a reproducible exhaustive search accompanied by a certificate of optimality, extending the known data. Deliver the proof / Lean file, the improved construction, or the search program plus certified optima.
Background
Posed by Erdős and Graham [ErGr80] and listed as open on erdosproblems.com/319 (fetched 2026-07-21, status 'open'); no cash prize. The condition asks for an 'irreducible' signed unit-fraction dependence — a vanishing $\pm 1/n$ relation with no smaller vanishing sub-relation. The best known lower bound, $\lvert A\rvert\geq(1-\tfrac{1}{e}+o(1))N$, was observed by Sarosh Adenwalla as a consequence of Croot's theorem [Cr01]: Croot proved there is a set $B\subset[(\tfrac{1}{e}-o(1))N,\,N]$ with $\sum_{b\in B}1/b=1$, and since the reciprocals of integers in $[c_1N,c_2N]$ sum to $\sim\log(c_2/c_1)$ this forces $\lvert B\rvert\geq(1-\tfrac1e+o(1))N$; taking $A=B\cup\{1\}$ with $\delta\equiv-1$ on $B$ and $\delta(1)=+1$ realises the bound. No matching upper bound is known, so even the leading constant is open. The problem has been formalised in Lean in the DeepMind formal-conjectures project. Attacker's tool: exact ILP / exhaustive search over signed unit-fraction cancellations to compute the true maximum for small $N$ and pin the constant empirically, paired with Croot-type constructions or new upper-bound arguments to close the asymptotic.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #319 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #319 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.