Skip to content

Erdős Problem #308

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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

For a fixed positive integer \(N\), choose any subset of the denominators \(1,2,\ldots,N\) and add their reciprocals. Which positive integers can occur? Erdős Problem 308 asks for the first positive integer that cannot occur. If

\[ R_N=\left\{k\in\mathbb Z_{>0}: k=\sum_{n\in A}\frac1n\text{ for some }A\subseteq\{1,\ldots,N\}\right\}, \]

then the least missing integer is

\[ f(N)=\min\{k\geq1:k\notin R_N\}. \]

The second question asks whether \(R_N\) is always an initial interval of positive integers: \(\{1,\ldots,m\}\) for some \(m\). The quantifiers matter. The classical result discussed below establishes this shape for all sufficiently large \(N\); it does not, by itself, settle the same assertion for every \(N\geq1\).

The natural comparison quantity is the harmonic sum \(H_N=\sum_{n=1}^N1/n\) and its integer part \(m_N=\lfloor H_N\rfloor\). The problem is about exact sums of distinct unit fractions, not arbitrary fractions, repeated denominators, or representations using denominators larger than \(N\).

A small example

Take \(N=6\). Exact arithmetic gives

\[ H_6=1+\frac12+\frac13+\frac14+\frac15+\frac16=\frac{49}{20}, \]

so \(m_6=2\). The integers \(1\) and \(2\) are represented: \(1=1/1\), and

\[ 2=1+\frac12+\frac13+\frac16. \]

Because every subset sum is between \(0\) and \(H_6<3\), no positive integer other than \(1\) or \(2\) can occur. Thus an exact enumeration of the \(2^6=64\) subsets gives \(R_6=\{1,2\}\) and \(f(6)=3=m_6+1\). A reproducible exact check is:

from fractions import Fraction

N = 6
sums = {Fraction(0)}
for d in range(1, N + 1):
    sums |= {s + Fraction(1, d) for s in list(sums)}
assert {s.numerator for s in sums if s.denominator == 1 and s > 0} == {1, 2}
assert sum((Fraction(1, d) for d in range(1, N + 1)), Fraction(0)) == Fraction(49, 20)

This verifies one finite instance and illustrates why the answer can be \(m_N+1\). It proves neither the eventual theorem nor the stronger assertion for all values of \(N\).

What is known

The live problem record attributes the essential resolution to Ernest S. Croot III, On some questions of Erdős and Graham about Egyptian fractions, Mathematika 46 (1999), 359–372. The paper’s main theorem, on the second page of the accessible author copy, uses the largest integer \(\eta(N)\) such that every integer from \(1\) through \(\eta(N)\) is representable. In the notation above, \(\eta(N)=f(N)-1\). Croot gives two asymptotic bounds with correction size \((\log\log N)^2/\log N\):

\[ \left\lfloor H_N-\frac92(1+o(1))\frac{(\log\log N)^2}{\log N}\right\rfloor \leq \eta(N) \leq \left\lfloor H_N-\frac12(1+o(1))\frac{(\log\log N)^2}{\log N}\right\rfloor. \]

Translating from \(\eta\) to the least missing integer adds one to both bounds. Since the correction tends to zero, the endpoint \(\eta(N)\) is eventually either \(m_N-1\) or \(m_N\), and therefore \(f(N)\) is eventually either \(m_N\) or \(m_N+1\). By the definition of the first missing integer, this also says that \(R_N\) is eventually either \(\{1,\ldots,m_N-1\}\) or \(\{1,\ldots,m_N\}\).

There is a genuine source-normalization issue here. The maintained page and its LaTeX transcription display Croot’s inequalities directly with \(f(N)\) and no visible \(+1\), while the latest FormalConjectures source documents that Croot bounds \(\eta(N)=f(N)-1\) and restores the \(+1\). This audit preserves that discrepancy rather than silently treating the two displays as identical. The primary paper is the authority to revisit if a line-by-line semantic adjudication is required.

GCL's current state

The original GCL issue #1578 is the source-audit packet for this article. At the time of the zero-context preflight it had no comments and no existing RESULT/1; the original SOURCE RESULT/1 citation is therefore authenticated original RESULT/1. The repository registry classifies #308 as OUTSIDE_STRICT_OPEN_TRIAGE and records no protected FormalConjectures file. Accepted coverage is decided by the protected V2 ledger alone; neither this manuscript nor the catalogue label supplies mathematical certification.

The frozen catalogue snapshot, teorth/erdosproblems@536408716724a2402bdfa7c1d764bf83d64a8c89, records proved, formal status unformalized, statement metadata yes, and a 2025-08-31 status date for entry 308. Its data/problems.yaml blob is 4e60263a80af6207aca494d2e1388e44fa372889. The live catalogue head checked here is 76848eddd25687dfc69bb26bec740c35c4a9c6b4; the entry metadata remains the same and has formalized dated 2026-09-20. These are maintained-record reports, not GCL certification.

The admitted FormalConjectures provider snapshot is google-deepmind/formal-conjectures@85f863718beeec7b58a3a1926ee92e3472bc2020; FormalConjectures/ErdosProblems/308.lean is absent there. Current upstream at 817d8a74e6bcd505ac8407388cc12ac3cfda3d0d has the file, blob d9511819fbf7b7ca8d8fe204995fc023c8bae229, but its theorem bodies end in by sorry. It is a useful statement/interface record, not a checked Lean proof. The file points to an external Lean development at plby/lean-proofs@8822f7ddef30fadbd92e1c6ab4ed897af356af5e, blob 21677d57970d100f64a3e1c43acd1ef7827223b3; that reported proof was not replayed here and is not GCL mathematical certification.

What remains

The classical eventual statement has a clear source path, while the variant for every value of \(N\) remains a separate boundary. A bounded successor task should first freeze the corrected normalization: define \(R_N\), \(f(N)\), and \(\eta(N)=f(N)-1\) with exact finite sums; then prove the elementary equivalence between an initial segment \(R_N=\{1,\ldots,m\}\) and the identity \(f(N)=m+1\). The task can use Croot’s published theorem as an external premise and should not imply that its analytic proof has been formalized.

Acceptance should require the exact quantifiers, an explicit comparison with the primary paper’s \(\eta\), and finite checks such as \(R_6=\{1,2\}\). Falsification would be any counterexample to the stated finite lemma, any missing \(+1\) in the translation, or any claim that the eventual result settles all \(N\). Stop after the source-normalized interface and finite checks are recorded; do not spend the bounded task on an exhaustive Lean build or on a new mathematical certification claim.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1578 — 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.

Back to catalogue · Compendium introduction