Skip to content

Erdős Problem #296

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.

Editorial authority: Publication and admission status are determined only by the protected V2 ledger. This documentary explanation is not mathematical certification.

The question in plain language

For an integer \(N\geq 1\), let \(k(N)\) be the largest number of pairwise disjoint subsets \(A_1,\ldots,A_{k(N)}\) of \(\{1,\ldots,N\}\) for which every reciprocal sum is exactly \(1\):

\[ \sum_{n\in A_i}\frac{1}{n}=1. \]

“Pairwise disjoint” means that no integer from \(\{1,\ldots,N\}\) may be used in two different sets. The original question asks how large \(k(N)\) can be and, specifically, whether \(k(N)=o(\log N)\). The latter would mean that \(k(N)/\log N\) tends to \(0\) as \(N\) grows.

The resolved asymptotic is instead

\[ k(N)=(1+o(1))\log N. \]

Equivalently, for every fixed \(\varepsilon>0\), all sufficiently large \(N\) satisfy

\[ (1-\varepsilon)\log N\leq k(N)\leq(1+\varepsilon)\log N. \]

Thus Problem 296 is proved in the mathematical source record, and the proposed \(o(\log N)\) answer is false. The lower bound comes from extracting many disjoint unit-fraction sets; the upper bound is simply the total reciprocal mass available in \(\{1,\ldots,N\}\).

A small example

At \(N=6\), two disjoint qualifying sets are

\[ A_1=\{1\},\qquad A_2=\{2,3,6\}, \]

because

\[ \frac{1}{1}=1,\qquad \frac{1}{2}+\frac{1}{3}+\frac{1}{6}=\frac{3+2+1}{6}=1. \]

There cannot be three. If three disjoint sets each had reciprocal sum \(1\), their combined reciprocal mass would be \(3\). But exact integer arithmetic gives

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

Therefore \(k(6)=2\). This finite calculation does not prove the asymptotic theorem, but it makes the disjointness upper bound concrete. The exact reproducible check recorded in the authenticated audit is:

from fractions import Fraction

H6 = sum((Fraction(1, n) for n in range(1, 7)), Fraction(0))
assert H6 == Fraction(49, 20)
assert Fraction(1, 1) == 1
assert sum((Fraction(1, n) for n in (2, 3, 6)), Fraction(0)) == 1
assert H6 < 3

The calculation and the conclusion \(k(6)=2\) are also stated in the exact RESULT/1 audit comment, which is the reproducibility reference for this fixture.

What is known

The upper estimate is immediate. Every qualifying set consumes reciprocal mass \(1\), and disjoint sets consume different terms, so

\[ k(N)\leq\sum_{n=1}^{N}\frac1n=H_N=\log N+\gamma+o(1). \]

In particular, \(k(N)\leq(1+o(1))\log N\).

The lower estimate is the substantive part. Bloom’s Theorem 3 states that there is an absolute constant \(C>0\) such that if \(A\subseteq\{1,\ldots,N\}\) satisfies

\[ \sum_{n\in A}\frac1n\geq C\frac{\log\log\log N}{\log\log N}\log N, \]

then \(A\) contains a subset \(S\) with reciprocal sum \(1\). This is a quantitative extraction theorem, not merely an assertion that one unit-fraction set exists.

Fix \(\varepsilon>0\). Start with \(\{1,\ldots,N\}\) and repeatedly remove a unit-sum subset while Bloom’s threshold is still met. After \(m=\lfloor(1-\varepsilon)\log N\rfloor\) removals, the remaining reciprocal mass is

\[ H_N-m=\varepsilon\log N+O(1). \]

For sufficiently large \(N\), this dominates Bloom’s threshold because \(\log\log\log N/\log\log N\) tends to \(0\). Hence at least \(m\) pairwise disjoint sets can be removed. Since \(\varepsilon\) is arbitrary, the lower bound is \(k(N)\geq(1-o(1))\log N\), and the two estimates combine to give the displayed asymptotic.

I inspected Bloom, “On a density conjecture about unit fractions,” arXiv:2112.03726v2: Theorem 3 is on PDF p. 2 and its deduction is in §2.1, pp. 6–7. The maintained Erdős Problems entry gives the same statement and attributes the greedy consequence to Hunter and Sawhney. The original Erdős–Graham monograph is the historical citation, but its relevant page was not obtained in this audit; no page-specific claim from that unavailable source is presented as directly inspected.

GCL's current state

The authenticated identity used for the readback was fyremael. The original MATH-PROGRAMME issue #1566 is open and binds Problem 296 to the pinned catalogue packet teorth/erdosproblems@536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889. Its protected registry entry records status proved, topics number theory and unit fractions, and issue-body SHA-256 cfff6440b785288e9dbd8997aaa647d55c7392ac36420cb0e9629c706428bcef.

The exact authenticated source return is RESULT/1, assignment ERDOS-CATALOGUE-0296-S01, with disposition SOURCE_LOCK_READY. It reports the mathematical resolution through Bloom’s theorem and greedy extraction, while identifying the formal replay and source-access limits. The issue being open is an operational/documentary fact; it does not turn the mathematical result back into an open conjecture.

The pinned Formal Conjectures file is at commit 85f863718beeec7b58a3a1926ee92e3472bc2020, blob a043a9185efc8703ed8325d730f412a3e8f3b079, raw-file SHA-256 db90dc6304258490b7fa977c06dccdab84251b03d888abf4c694679910e467d6. It formalizes the harmonic upper bound and an eventual lower bound, but its theorem ends in by sorry. It also states HasDisjointUnitDecomps directly rather than defining a maximum and proving equivalence with the informal \(k(N)\). That semantic gap matters: a formal statement can match the intended conclusion without by itself certifying that every informal definition and quantifier has been captured.

What remains

The mathematical question is resolved at the asymptotic level, but several documentary and formal boundaries remain. The exact finite function \(k(N)\) is not determined by the asymptotic formula. Bloom’s theorem supplies an eventual lower bound with an unspecified absolute constant in the published statement, while the harmonic argument supplies a simple upper bound; neither is an exact algorithm for computing \(k(N)\) at a given \(N\).

A bounded formalization task is to replay the pinned statement with the natural-number interval, rational reciprocal sum, eventual quantifier, floor, and logarithm all checked against the informal definition. In particular, one should define the maximum explicitly, prove it exists for each finite \(N\), and prove that the existence of \(k\) disjoint sets is equivalent to the inequality \(k\leq k(N)\). A successful replay would establish source and semantic consistency. It would not convert the sorry-containing pinned file, an external proof repository, or a self-reporting CI result into GCL mathematical certification.

The external no-sorry Lean source named by the audit is evidence for a possible successor replay, not an accepted proof record. The audit did not claim a successful compilation of that exact dependency closure. The original monograph’s unavailable page is likewise a retained source exception, not permission to fill historical details from memory. The supported conclusion is therefore precise: the proof status is proved by the inspected Bloom theorem plus the elementary greedy deduction, while formal certification, exact semantic replay, and editorial admission remain separate matters.

Sources and claim boundaries

The mathematical status stated here is proved, with the exact qualification that it rests on the inspected primary theorem and an elementary deduction. The protected registry and editorial ledger govern documentary status; neither this manuscript, the source audit, the pinned formal file, nor an external formal repository grants mathematical certification.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1566 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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.

Back to catalogue · Compendium introduction