Skip to content

Erdős Problem #321

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

Take the reciprocals \(1,1/2,1/3,\ldots,1/N\). We seek the largest set of denominators \(A\subseteq\{1,\ldots,N\}\) for which choosing or not choosing each reciprocal always gives a different total. In symbols, if \(S\) and \(T\) are subsets of \(A\), then

\[ \sum_{n\in S}\frac{1}{n}=\sum_{n\in T}\frac{1}{n} \quad\Longrightarrow\quad S=T. \]

Write the maximum size as \(R(N)\). The empty choice counts, and the sums are ordinary rational sums: there is no approximation or rounding. The question recorded by Erdős and Graham asks for the size of \(R(N)\), or, in modern language, for the growth of the largest dissociated subset of these particular unit fractions with coefficients restricted to \(0\) and \(1\).

This is closely related to, but not identical with, counting every distinct subsum of all the reciprocals up to \(N\). If \(E_N\) denotes the set of all such subsums, then every admissible \(A\) contributes \(2^{|A|}\) different elements of \(E_N\), so

\[ 2^{R(N)}\leq |E_N|. \]

That inequality is useful for upper bounds on \(R(N)\), but a large number of total subsums does not automatically exhibit one large admissible set.

A small example

For \(N=4\), the whole set \(A=\{1,2,3,4\}\) already works. Multiplying every sum by the common denominator \(12\) turns the four available weights into \(12,6,4,3\). Exhaustive exact subset addition gives the sixteen values

\[ 0,3,4,6,7,9,10,12,13,15,16,18,19,21,22,25. \]

They are all different, so the sixteen rational subsums are all different. Since no subset of \(\{1,2,3,4\}\) can have more than four elements, this verifies \(R(4)=4\) exactly. The calculation is finite and uses integers after clearing denominators; it does not say that \(\{1,\ldots,N\}\) works for larger \(N\), nor does it determine the asymptotic size of \(R(N)\).

The obstruction is an exact equality between two different subcollections. For example, once a denominator set contains a suitable relation such as \(1/2=1/3+1/6\), it cannot be admissible. The same principle applies to longer relations, which is why testing pairs alone is insufficient.

What is known

The primary 1975 paper of Bleicher and Erdős studies the number \(S(N)=|E_N|\) and constructs special denominators whose subsums are distinct. Its lemma on the final pages proves uniqueness for sums formed from the constructed set \(Q(N)\); consequently that construction supplies an admissible set and a lower bound for \(R(N)\), not merely a count of unrelated subsums. Their corollary gives iterated-logarithm lower bounds, under explicit conditions on the iterated logarithms.

Their companion 1976 paper gives corresponding upper estimates for the number of distinct subsums. Together with \(2^{R(N)}\leq S(N)\), these results place \(R(N)\) in the same broad iterated-logarithmic scale as \(\log S(N)\), but the exact parameter choices and the transfer from \(S(N)\) to \(R(N)\) must be read with their hypotheses intact.

A newer primary source is Bettin, Grenié, Molteni, and Sanna, A lower bound for the number of Egyptian fractions (arXiv:2509.10030, version dated 12 September 2025). Their Theorem 1 is a lower bound for \(\log |E_N|\), improving the admissible condition on the iterated logarithm and the leading constant. It is important to state its target correctly: the theorem is about \(E_N\), not by itself a theorem giving the exact value of \(R(N)\).

The live Erdős Problems page, last edited 16 July 2026, reports that the correct order of magnitude of \(R(N)\) is known and calls the problem solved in that order-of-growth sense. Its discussion records that the lower bound is implicit in the newer Egyptian-fraction work, while the upper bound is attributed to a GPT-generated argument linked through Problem #320. That is a current external report, not a human-authored primary proof that was independently checked in this audit. The more precise asymptotic questions remain described there as open.

GCL's current state

The frozen catalogue packet is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, with the Problem 321 blob 4e60263a80af6207aca494d2e1388e44fa372889. At that snapshot, dated 31 August 2025, the catalogue says informal status “solved,” formal status “unformalized,” and statement formalized “yes.” The live page has since moved and reports the order-of-growth resolution, so these labels should not be silently treated as a single theorem-level status.

The pinned Formal Conjectures source is google-deepmind/formal-conjectures commit 85f863718beeec7b58a3a1926ee92e3472bc2020, file FormalConjectures/ErdosProblems/321.lean, blob e58fa81d7f81badaeca1e29dde1e1e1435d1d635. It defines \(R(N)\) using injectivity of the subsum map on a finite-set powerset and states R N = answer(sorry) for every \(N\). Its exact and asymptotic variants are tagged research/open; lower and upper variants are tagged solved but still contain sorry. This is a formal interface with unresolved proof obligations, not Lean replay or GCL certification. V2 ledger state, rather than this article, decides accepted coverage.

What remains

A useful next step is a source-locked semantic audit of the claimed order-of-growth theorem. It should write down one exact function \(g(N)\), the quantifiers on all iterated-logarithm parameters, and separate the lower construction for \(R(N)\) from estimates for \(S(N)\). It should then trace the upper argument linked from Problem #320 to a stable, citable mathematical document and check every conversion between logarithm bases and every range condition.

Finite computation remains useful for falsification and for formalization. Exact rational enumeration can extend the verified initial values and test candidate forbidden relations, but it cannot establish an asymptotic theorem. Likewise, translating the Lean definition into a proved theorem would certify only the formal statement actually encoded; it would not certify that the answer(sorry) placeholder has been replaced by the mathematically intended asymptotic claim.

Sources and claim boundaries

No claim here is a mathematical certification, a completed Lean proof, or a publication decision. The article records what the named sources say, what the exact finite check establishes, and where the live status report still needs primary-source reconciliation.

Catalogue and evidence provenance

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