Skip to content

Erdős Problem #301

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.

The question in plain language

Erdős Problem 301 asks how large a set of small positive integers can be while avoiding all nontrivial Egyptian-fraction identities internal to the set. For a positive integer \(N\), let \(f(N)\) be the largest size of a set \(A\) contained in \(\{1,\ldots,N\}\) for which there do not exist an integer \(k\geq 1\) and pairwise distinct integers \(a,b_1,\ldots,b_k\) in \(A\) satisfying

\[ \frac{1}{a}=\frac{1}{b_1}+\cdots+\frac{1}{b_k}. \]

The case \(k=1\) is automatically impossible because \(a\) and \(b_1\) must be distinct, so the substance begins with two or more summands. The question is to estimate \(f(N)\) as \(N\) grows. Its most pointed form asks whether

\[ f(N)=\left(\frac{1}{2}+o(1)\right)N. \]

Here \(o(1)\) means a quantity tending to zero as \(N\) tends to infinity. Thus the conjectural answer says that the largest avoiding set has asymptotic density one half: it may be a little larger or smaller than \(N/2\) at any particular finite \(N\), but its relative excess should disappear.

A small example

Take \(N=6\) and \(A=\{4,5,6\}\). This is the upper half of the interval, and it has three elements. An exact check is short because, for each possible left-hand denominator, there are only two other elements. For \(a=4\), the possible sums using at least one distinct denominator are \(1/5\), \(1/6\), and \(1/5+1/6=11/30\); none is \(1/4\). For \(a=5\), the corresponding values are \(1/4\), \(1/6\), and \(1/4+1/6=5/12\), none equal to \(1/5\). For \(a=6\), they are \(1/4\), \(1/5\), and \(1/4+1/5=9/20\), none equal to \(1/6\).

This is reproducible exact arithmetic rather than a decimal approximation. The complete finite check can be written as:

from fractions import Fraction
from itertools import combinations

A = (4, 5, 6)
relations = []
for a in A:
    others = tuple(b for b in A if b != a)
    for k in range(1, len(others) + 1):
        for bs in combinations(others, k):
            s = sum((Fraction(1, b) for b in bs), Fraction(0))
            if s == Fraction(1, a):
                relations.append((a, bs))
print(relations)

The verified output is []. This establishes only that this particular finite set is avoiding, and hence gives the elementary lower bound \(f(6)\geq 3\). It says nothing about the asymptotic estimate, nor does it show that the upper-half construction is always optimal.

What is known

The primary source is P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory (1980), especially the Unit Fractions discussion on printed pages 32 and 36–37. There the authors introduce families of finite sets whose elements have reciprocal sum one and ask how large a subset of \(\{1,\ldots,n\}\) can avoid such a configuration. The maintained Problem 301 wording is a modern normalization of that question, with the quantifiers made explicit.

One basic construction is \(A=(N/2,N]\cap\mathbb{N}\), which the maintained entry records as giving \(f(N)\geq N/2\) (with the harmless integer-rounding interpretation at odd \(N\)). Intuitively, the construction removes the small denominators that make short reciprocal identities easiest; the exact finite example above illustrates the same direction without relying on intuition.

The maintained entry also records an elementary upper bound attributed to Wouter van Doorn: \(f(N)\leq (25/28+o(1))N\). Its described mechanism partitions suitable multiples into disjoint sets \(S_a=\{2a,3a,4a,6a,12a\}\cap[1,N]\), where \(a\) ranges over numbers of the form \(8^b9^cd\) with \((d,6)=1\). An avoiding set must omit enough elements from each such block, and summing those omissions yields the stated constant. This is a live-site report of attributed progress, not a result independently certified in this article.

These bounds leave a substantial gap between one half and twenty-five twenty-eighths. The live page says the problem is open and cannot be resolved by a finite computation alone. A computation can test particular \(N\) and suggest structure, but the requested asymptotic statement concerns all sufficiently large \(N\).

GCL's current state

The source packet in original issue #1571 freezes the catalogue evidence at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml, entry number: "301", Git blob 4e60263a80af6207aca494d2e1388e44fa372889, with source SHA-256 be65b0db56fe13becec3178f2937685ee7e6a2f5df9325712474722c279c4182. That snapshot calls the problem open, last updated 2025-08-31, and marks it unformalized.

The maintained live entry, last edited 2026-01-16, still labels the problem open and says that no formalized statement is present. It supplies the lower bound and the van Doorn report described above, so it is richer than the frozen snapshot but does not overturn its status. The local GCL triage record consequently classifies #301 as STATEMENT_CAPTURE_REQUIRED; no Solve authorization, certification, or accepted mathematical result follows from that label. At the worker preflight there was no original issue source return; an authenticated return was later posted. The original SOURCE RESULT/1 citation is therefore authenticated original RESULT/1.

What remains

The central unresolved task is an asymptotic upper bound of \((1/2+o(1))N\), or a counterexample showing that the proposed constant is wrong. Before a theorem-level campaign, the smallest useful source task is to lock the exact distinctness convention and turn the block argument behind \(25/28\) into a finite, checkable packing lemma. A successor worker could then test the lemma for explicit ranges of \(N\), identify exactly which omitted elements are forced by each reciprocal identity, and record whether the finite inequalities support an improved constant. Such checks would be evidence for a route, not a proof of the asymptotic claim.

Any stronger claim needs a primary proof or a complete new argument. In particular, the existence of a finite avoiding set, an integer-programming optimum at selected \(N\), or a formal statement in Lean would not by itself establish the limit. The semantic distinction between distinct and non-distinct \(b_i\) is essential: the live page notes that allowing repetition changes the extremal problem and gives a different half-density threshold.

Sources and claim boundaries

The original statement and attribution are taken from Erdős and Graham's primary source, the scan at mathweb.ucsd.edu/~ronspubs/80_11_number_theory.pdf, retrieved with SHA-256 0cbf0c32f0ab1e1c71db5121a88bac905bf976c4a6ab6bb6d7d9cf9ddd184ed3. The modern wording, date, and reported bounds are from erdosproblems.com/301, accessed 2026-10-12. The frozen catalogue identity and hash are recorded above; the issue is the operative GCL source packet.

The admitted FormalConjectures provider snapshot is upstream commit 85f863718beeec7b58a3a1926ee92e3472bc2020, but an exact lookup for FormalConjectures/ErdosProblems/301.lean at that commit returned no file, consistent with the packet's statement that no protected #301 file exists. The current upstream path is absent as well. Therefore there is no Lean theorem, even a sorry-bearing statement, to summarize for #301 here. This article reports source evidence and finite arithmetic only; it does not certify the mathematics, validate the attributed upper-bound proof, or decide the V2 ledger's accepted coverage.

Catalogue and evidence provenance

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