Closest a distinct-unit-fraction sub-sum can get to 1: is δ(N) = e^{-(c+o(1))N}? (Erdős #311)
Statement
For $N\ge 1$ let $\delta(N)$ be the minimal non-zero value of $\left\lvert 1-\sum_{n\in A}\frac{1}{n}\right\rvert$ as $A$ ranges over all subsets of $\{1,\ldots,N\}$ — i.e. how close, but not equal, to $1$ a sub-sum of $1,\tfrac12,\ldots,\tfrac1N$ can get. Is it true that $$\delta(N)=e^{-(c+o(1))N}$$ for some constant $c\in(0,1)$?
Acceptance. FULLY RESOLVES: a complete proof establishing $\delta(N)=e^{-(c+o(1))N}$ for an explicit constant $c\in(0,1)$ (both the exponential rate and the value of $c$), or a proof that no such clean exponential asymptotic holds; machine-checkable preferred, else a full written proof. ADVANCES (each independently checkable): (a) prove a genuine exponential upper bound $\delta(N)\le e^{-cN}$ for some explicit $c>0$, strictly stronger than Tang's $\exp(-cN/(\log N\log\log N)^3)$; (b) improve the lower bound strictly above the trivial $e^{-(1+o(1))N}$; (c) extend an exact table of $\delta(N)$ to a new record $N$ with the search program and a certificate that the reported value is optimal. Deliver the proof, the improved bound with proof, or the code + certified values.
Background
Posed by Erdős and Graham [ErGr80, p.40]; listed as open on erdosproblems.com/311 (fetched 2026-07-21, status 'open'). Trivially $\delta(N)\ge \frac{1}{[1,\ldots,N]}=e^{-(1+o(1))N}$, since every non-zero sub-sum has denominator dividing the least common multiple $[1,\ldots,N]$, whose logarithm is $(1+o(1))N$ by the prime number theorem. The original [ErGr80] formulation additionally forbade $A$ from containing a subset $S$ with $\sum_{n\in S}\frac1n=1$; Kovač observed in the site comments that this restriction is unnecessary (the two formulations are equivalent). Tang has shown the upper bound $\delta(N)\le\exp\!\left(-c\frac{N}{(\log N\log\log N)^3}\right)$ for some $c>0$; this beats every fixed power of $1/N$ in the exponent but is still short of the conjectured genuine exponential decay $e^{-(c+o(1))N}$, so both the exponential rate and the value of the constant $c\in(0,1)$ remain open. Attacker's tool: exact computation of $\delta(N)$ for small $N$ by working over the common denominator $[1,\ldots,N]$ and searching (subset-sum dynamic programming / meet-in-the-middle) for the sub-sum whose numerator is closest to $[1,\ldots,N]$ without equalling it, extending an exact table and empirically fitting $c$, together with analytic constructions sharpening Tang's upper bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #311 (T. F. Bloom) | website |
| REF-02 | Q. Tang, note on Erdős problem #311 (upper bound on δ(N)) | paper |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.