Erdős Problem #309
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (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.
The question in plain language
Erdős Problem #309 studies the integers that can be made by adding distinct unit fractions whose denominators are at most a given bound. For a positive integer \(N\), let
and write \(F(N)=|\mathcal{R}(N)|\). The denominators are distinct because \(S\) is a set; every coefficient is either \(0\) or \(1\). The empty set contributes \(0\) under the modern formal definition. Counting only positive integers changes the count by at most one, so it does not affect the asymptotic question.
The registered question is whether there are \(o(\log N)\) such integers as \(N\) grows. In plain language, \(o(\log N)\) would mean that the number of representable integers becomes negligible compared with \(\log N\): the ratio \(F(N)/\log N\) would tend to zero. The question is not asking how many different decompositions a single integer has. It asks how many integer values occur at all when all subsets of the first \(N\) denominators are allowed.
This distinction matters. The total reciprocal mass is about \(\log N\), but many subsets can have the same sum, and most subset sums are not integers. The problem asks whether these collisions and integrality restrictions reduce the number of integer values below logarithmic scale.
A small example
For \(N=6\) there are only \(2^6=64\) subsets, so the question can be checked by exact rational arithmetic. Enumerating each subset with rational numbers gives
The nonzero values have especially simple witnesses:
The second identity is checked by putting everything over \(6\):
The actual finite verification used Python's fractions.Fraction, not floating-point arithmetic. Its output was integer sums=[0, 1, 2], count=3, with witnesses 0=() , 1=(1,), and 2=(1,2,3,6). This confirms the finite example and the interpretation of “distinct.” It does not estimate the limit of \(F(N)/\log N\), prove the theorem for large \(N\), or check the published analytic arguments.
What is known
The primary source that settles the direction of the answer is Hisashi Yokota's “On Number of Integers Representable as Sums of Unit Fractions,” Canadian Mathematical Bulletin 33 (1990), 235–241. Its abstract and opening statement define the same set using coefficients \(\varepsilon_i\in\{0,1\}\) and prove a lower bound of the form \((1/2-\varepsilon(N))\log N\), where \(\varepsilon(N)\to0\). That lower bound alone rules out \(o(\log N)\): eventually the ratio is at least close to \(1/2\).
Yokota's later “On Number of Integers Representable as a Sum of Unit Fractions, II,” Journal of Number Theory 67 (1997), 162–169, reports the sharper conclusion \(F(N)\sim\log N\) in its publisher abstract. Thus the negative answer is not based only on a catalogue label. It has a primary published argument at logarithmic scale, with a later primary refinement giving the natural asymptotic order. Croot's “On some questions of Erdős and Graham about Egyptian fractions,” Mathematika 46 (1999), 359–372, is a related primary source: it proves strong coverage of consecutive integers below the harmonic sum, but it is not needed to infer the negative answer from Yokota's lower bound.
These are external mathematical results. This article does not reproduce their proofs, and it does not turn a bibliographic or formalization record into GCL mathematical certification.
GCL's current state
The frozen catalogue evidence supplied by original issue #1579 is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file data/problems.yaml, entry blob 4e60263a80af6207aca494d2e1388e44fa372889, with source-file SHA-256 be65b0db56fe13becec3178f2937685ee7e6a2f5df9325712474722c279c4182. That snapshot records informal status disproved dated 2025-08-31, and later metadata records disproved (Lean) and formalized: yes. The issue also records the protected triage class OUTSIDE_STRICT_OPEN_TRIAGE.
The maintained live entry agrees on the mathematical direction and displays “DISPROVED,” citing Yokota and Croot. Its page, last edited 20 December 2025, currently says “Formalised statement? No.” This is a metadata discrepancy, not a contradiction in Yokota's mathematical result. The issue packet says that no #309 statement file exists in GCL's admitted FC-GDM-85F86371 provider snapshot, so that absence is preserved here.
An unpinned upstream FormalConjectures addition exists at commit b86fdb9a8f2f83d2bb2b4281586705896c0c8208, blob 1ba5ef4d6e6e4c4947308002e67fff021bd36ca1, source SHA-256 84c276a1d343feeaba3675bab44cc92a2b3751ff12756692db66a24078c78440. Its theorem statements end in by sorry and link to an external Lean proof report at commit 8822f7ddef30fadbd92e1c6ab4ed897af356af5e. That report is recorded as an unverified external formal-status claim, not as a replay or GCL certification.
What remains
The mathematical question has a clear source-based answer, but the formal provenance needs a bounded reconciliation. A successor should compare the frozen intended definition, the upstream F(N) definition, and the linked external implementation: whether \(0\) is counted, whether the ambient set is natural numbers or integers, how denominators are bounded, and whether the bridge from a representable sum to the counted integer set is exact. The comparison should record the exact file hashes and theorem names, without rerunning a full Lean build.
One reusable interface is the finite exact enumeration above: a test fixture can expose the set of values produced by subsets of Icc 1 6 and verify the witnesses for \(0\), \(1\), and \(2\). A stronger formal successor could prove only the elementary bridge that the finite-set definition and the coefficient function definition enumerate the same values. That would support later formal reuse while remaining separate from the analytic theorem \(F(N)\sim\log N\).
Sources and claim boundaries
- Original issue #1579, including the frozen source packet and labels. Original SOURCE RESULT/1 citation: authenticated original RESULT/1.
- Erdős and Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), the original catalogue source; the fetched scan has SHA-256
0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3. - Yokota 1990, primary paper, pp. 235–241; fetched PDF SHA-256
c962770d9ca8cda6bc91971eaf4f64457e1666b4d239e33637e1da3c30452490. - Yokota 1997, primary journal record, pp. 162–169, and Yokota 2002, pp. 351–372, for the sharper asymptotic context.
- Croot 1999, primary paper, pp. 359–372; fetched copy SHA-256
695e8fd2519b53703e3f91a092231f06911596e0a7832d3d5376961361c7ff5.
The published results, catalogue snapshot, live page, and unpinned formal report are kept as separate evidence classes. No claim here is a Lean replay, GCL mathematical certification, publication decision, or acceptance decision; the V2 ledger alone decides accepted editorial coverage.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1579 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.