Erdős Problem #302
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
Take the integers from \(1\) through \(N\), and choose as many as possible while avoiding three different chosen integers \(a\), \(b\), and \(c\) satisfying
Write the largest possible size as \(f(N)\). Erdős Problem 302 asks for the asymptotic size of \(f(N)\): does it have a limiting density, and in particular is \(f(N) = (1/2+o(1))N\)? “Distinct” matters. If \(b=c\) were allowed, the elementary identity \(1/n = 1/(2n)+1/(2n)\) would change the problem completely. The intended ambient set is the positive integers in the finite interval \([1,N]\), with no ordering imposed on the three variables beyond their being pairwise different.
The equation is also a divisibility condition. Multiplying by \(abc\) gives \(bc=a(b+c)\), so a triple is forbidden exactly when \(b+c\) divides \(bc\) and the resulting quotient is \(a\). This reformulation is useful for finite searches, but it does not turn the asymptotic extremal question into a finite computation.
The historical source is Erdős and Graham’s Old and New Problems and Results in Combinatorial Number Theory (1980), Unit Fractions chapter. The accessible scan places the relevant discussion on printed pages 38–39 and explicitly compares the question with the odd integers. The maintained page attributes the catalogue entry to that source as [ErGr80].
A small example
Here is an exact finite check, performed with rational arithmetic rather than floating-point approximations. For every three-element subset of \([1,12]\), I tested \(1/a=1/b+1/c\) by cross-multiplying; then I tested every one of the \(2^{12}\) subsets for the absence of a forbidden triple. The only forbidden triples are
The exhaustive result is \(f(12)=10\). One attaining set is \(\{1,2,3,4,5,7,8,9,10,11\}\): it omits \(6\) and \(12\), thereby hitting all three forbidden triples. For example, the first triple is checked exactly by \(1/2=1/3+1/6\), and the last by \(1/4=1/6+1/12\).
This illustrates the finite hypergraph viewpoint: integers are vertices and unit-fraction triples are hyperedges, and \(f(N)\) is the independence number. It establishes only the stated value at \(N=12\). It neither estimates the limiting density nor validates any claimed asymptotic constant. A finite search can miss configurations that first appear at much larger scales.
What is known
The basic lower bound is \(f(N)\geq (1/2+o(1))N\). Two simple constructions give it: all odd integers up to \(N\), or all integers in the upper half of the interval. In either case the equation cannot occur among three selected values for elementary parity or size reasons.
The maintained problem page records a stronger construction due to Stijn Cambie: take the odd integers at most \(N/4\) together with all integers in \([N/2,N]\). It gives \(f(N)\geq (5/8+o(1))N\), so the proposed half-density asymptotic is false as a specific conjecture, even though the general request to estimate \(f(N)\) remains open.
The same page records Wouter van Doorn’s upper bound \(f(N)\leq (9/10+o(1))N\), attributed to a short note titled “Two-colouring and density lead to solutions to an equation in unit fractions.” The note is an external source report, not a GCL-certified result in this article. A newer external repository by Kenta Kitamura reports a stronger upper constant, approximately \(0.8461739827964009\), with a large Lean development and finite certificates. Its README says the result has not yet received independent human review. This audit did not build or replay it, so the claim is recorded as unverified external evidence.
The related colouring problem is different: Brown and Rödl proved that every finite colouring contains a monochromatic solution. That result does not settle the density extremal problem, because a large triple-free set is not the same object as a colour class in a fixed finite colouring.
GCL's current state
The frozen source packet in original issue #1572 locks teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, file blob 4e60263a80af6207aca494d2e1388e44fa372889. Its entry says informal status open, last updated 2025-08-31, with formal status unformalized and statement-formalized metadata yes. The programme registry class is FORMAL_SOURCE_REFRESH_REQUIRED.
The exact pinned FormalConjectures commit named by the programme is 85f863718beeec7b58a3a1926ee92e3472bc2020. No FormalConjectures/ErdosProblems/302.lean exists at that commit. The current upstream file exists at a different revision, blob f950f23c2b275ba3a9244455e9ae498728ae7d89; it defines a finite triple-free predicate and a maximum-cardinality predicate, and then states the asymptotic theorem and variants. Its research theorem bodies contain sorry. One lower-half construction is filled in, but that is an elementary bound and not a solution.
There is also a metadata discrepancy: the current catalogue marks the statement formalized on 2026-08-05, while the maintained page has displayed “Formalised statement? No” in the live page snapshot used for this audit. These are publication and provider-status fields, not mathematical certification. V2 ledger state alone decides accepted coverage. No GCL mathematical certification is supplied here.
What remains
The smallest useful successor task is a source-locked semantic review of the upper-bound interface. Its input should be the exact triple predicate, the van Doorn note at its pinned file hash, and Kitamura’s external repository at commit 9447ceb28138949b2fb32442cec506a6f53104f9, file blob 3f6dde05ee0da00dcb6ddab7b1004bd8572bccb0. The target is one written comparison proving that the source’s pairwise-distinct positive-integer formulation, the catalogue wording, and the formal Finset predicate are equivalent for every relevant \(N\).
Acceptance requires the hypotheses and quantifiers to be copied verbatim, the finite-to-asymptotic passage to be identified, and every external theorem or certificate dependency to have a stable source identity. Falsification is any counterexample to the predicate translation, an unavailable cited source, or a proof step that silently assumes \(N>0\) or permits repeated variables. Stop after that semantic comparison and a bounded finite regression; do not launch a full Lean build. The unresolved mathematical question is still the true asymptotic value of \(f(N)\), not the already-refuted half-density guess.
Sources and claim boundaries
- Erdős–Graham, Old and New Problems and Results in Combinatorial Number Theory, with an accessible scan/OCR, Unit Fractions chapter, printed pp. 38–39.
- Maintained Erdős Problem 302 page, used for the current displayed wording and remarks; its live metadata is not silently substituted for the frozen catalogue lock.
- Frozen catalogue file, blob
4e60263a80af6207aca494d2e1388e44fa372889. - Van Doorn note, file blob
a89182a5e35887654f744f439e4236ff19550c91, SHA-2563d9b12d29829673adece98d8457e5993e51476ee88bf49775c0d148eba1c4cc3. - Current FormalConjectures file, blob
f950f23c2b275ba3a9244455e9ae498728ae7d89; it is an unpinned statement/proof-interface record containingsorry. - Original SOURCE RESULT/1 citation: authenticated original RESULT/1. This local article is not that comment and does not claim acceptance, publication, proof certification, or priority.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1572 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: FORMAL_SOURCE_REFRESH_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.