Erdős Problem #295
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory, unit fractions.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
Editorial authority: Publication status comes exclusively from the protected V2 ledger. This explanation does not constitute mathematical certification.
The question in plain language
An Egyptian fraction is a sum of reciprocals of distinct positive integers. For each integer \(N\geq 1\), define \(k(N)\) to be the smallest number of terms in such a sum for \(1\) whose denominators all start at \(N\):
The strict inequalities make the denominators distinct, and there is no imposed upper bound on the largest denominator. The question is whether the excess over the natural linear scale grows without bound:
Here “limit \(=+\infty\)” means that for every real threshold \(B\), all sufficiently large \(N\) satisfy \(k(N)-(e-1)N>B\). It is stronger than saying that \(k(N)\) is approximately \((e-1)N\): the proposed excess must eventually exceed every fixed constant. The maintained Problem 295 page gives this statement and cites Erdős and Graham as the original reference.
A small example
For \(N=2\),
so \(k(2)\leq 3\). In fact \(k(2)=3\). One term would require the denominator \(1\), which is below \(N\). If two terms existed, then for \(2\leq a<b\),
The only positive factorization on the right gives \(a=b=2\), contradicting distinctness. This finite argument illustrates the quantifiers, but it says nothing by itself about the limit.
The source audit also records a larger exact certificate. Let
There are \(32\) elements, the least is \(17\), and exact rational arithmetic gives \(\sum_{a\in A}1/a=1\). Thus \(k(17)\leq32\); it is only an upper bound unless a matching exclusion is supplied. The calculation was independently checked with Python’s arbitrary-precision Fraction type:
from fractions import Fraction
from math import gcd
A = [17,18,19,20,21,22,23,24,25,26,27,28,29,30,32,33,34,35,36,
38,39,42,43,44,45,48,50,52,54,63,1735650,68479214496]
L = 1
for n in A:
L = L // gcd(L, n) * n
assert sum((Fraction(1, n) for n in A), Fraction()) == 1
assert sum(L // n for n in A) == L == 200301702400800
What is known
The directly inspected primary historical source is P. Erdős and R. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 35. It denotes the same minimum by \(U_n\), asks whether \(U_n-(e-1)n\) tends to infinity, and says that this was not proved there. On that page it reports the known two-sided estimate, attributed to Erdős and Straus, that for suitable positive constants \(c,c'\),
The lower inequality keeps the excess from being permanently too negative, while the upper estimate says the excess is at most of order \(N/\log N\). Neither bound makes the excess unbounded, so neither resolves Problem 295.
The cited earlier paper is H. D. Ruderman, P. Erdős, and E. Straus, “E2232,” The American Mathematical Monthly 78, no. 3 (1971), pp. 302–303, DOI 10.2307/2317539. The audit confirmed this bibliographic record, but the article itself was behind a JSTOR access challenge; therefore this manuscript does not claim to have independently inspected its proof. The p. 35 Erdős–Graham exposition is the directly checked source for the statement and the displayed bound.
GCL's current state
The protected catalogue registry records Problem 295 as open, in the PROTECTED_READY_BACKLOG triage class, with topics number theory and unit fractions. Its exact registry entry binds issue #1565 to source-registry hash 69641c765232ef89a71ff59a414985c8f6074ffd75175dc1b09a6e96a6db5def. The original GCL issue #1565 pins the catalogue at teorth/erdosproblems@536408716724a2402bdfa7c1d764bf83d64a8c89, including data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889, and records the formal-status report as unformalized with a formalized statement.
The authenticated source-audit return by fyremael, exact RESULT/1 comment, is explicitly DISPOSITION: PARTIAL with TIMEBOX_OBSERVED: YES. Its finite certificates and source comparisons are useful documentary evidence, not a proof of the asymptotic claim. In particular, the externally reported Lean file is not GCL mathematical certification, and no successful external CI run or author manuscript changes that boundary.
The pinned Formal Conjectures file at commit 85f863718beeec7b58a3a1926ee92e3472bc2020 defines exists_k using n : Fin k.succ. That supplies \(k+1\) denominators while the surrounding prose calls the parameter \(k\) the number of terms, an off-by-one mismatch. Its lemmas and theorem also end in by sorry. The current main file uses Fin k, but it still contains sorry; comparing files is not a kernel proof. The catalogue’s “formalized” marker and a category research open annotation are metadata only.
What remains
The original mathematical target remains the unbounded lower excess. A successful resolution would need a proof that, for every fixed \(B\), the inequality \(k(N)>(e-1)N+B\) eventually holds. The known upper construction and the Erdős–Straus estimate do not supply that conclusion. Finite values can guide the search but cannot establish an asymptotic statement.
A bounded documentary successor is to audit the cited exact-search claim against its pinned external source, with arbitrary-size rational arithmetic and no hidden denominator ceiling. The target finite assertion is
A valid audit must show that every branch in the finite exclusion is covered; a timeout or a search that merely finds no example is inconclusive. The source report's certificate with 34 terms gives only \(k(18)\leq34\), so even a verified lower bound would need to be stated with its exact strength and method.
The formalization also needs a semantic repair: define the number of summands with Fin k, prove existence separately, and then relate any corrected formal definition to the source statement. This is a statement-and-index task, not a claim that the analytic argument has been formalized. No current evidence here closes the open problem, certifies an external Lean proof, or promotes the article to an accepted or published page.
Sources and claim boundaries
- Problem 295 — maintained statement, tags, and the reported Erdős–Straus bound; its page is a reference source, not GCL certification.
- Original GCL issue #1565 — exact assignment, pinned source packet, and authority boundary; the protected registry hash is
69641c765232ef89a71ff59a414985c8f6074ffd75175dc1b09a6e96a6db5def. - Authenticated source-audit RESULT/1 — exact
PARTIALdisposition, source-page reading, finite certificates, and formalization caveats. It is evidence, not certification. - Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory, 1980, p. 35 — directly inspected source for \(U_n\), the limit question, and the reported two-sided estimate. The audited PDF SHA-256 is
0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3. - Ruderman–Erdős–Straus, E2232, American Mathematical Monthly 78 (1971), 302–303 — confirmed DOI and page metadata; its proof was not directly read in this audit.
- External \(k(18)\) search source — cited by RESULT/1 for a finite lower-bound audit; its claimed exhaustion remains unreplayed and is not GCL certification.
- Pinned Formal Conjectures source and current file — formal statement scaffolding containing unfinished proofs; neither is GCL certification.
All mathematical claims above are bounded by these sources and the displayed exact checks. This file is a source-qualified explanation: writing it does not constitute proof, editorial admission, protected merge, publication, or a claim that Problem 295 has been solved.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1565 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: PROTECTED_READY_BACKLOG.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.