Every natural number is a sum of distinct semiprime unit fractions
Shisheng Li
math.NT
Jun 13, 2026 · v2
math.CO
TL;DR
Every result is machine-checked in Lean 4/Mathlib with no sorry, including the finite base-range computations.
Abstract
We prove that every natural number is a finite sum of distinct unit fractions whose denominators are semiprimes (products of two distinct primes). This is the $ω=2$ integer case of a problem of Erdős and Graham, stated only as a conjecture by Butler, Erdős and Graham (Integers 15 (2015), A51), who proved the $ω=3$ analogue. Counterintuitively the problem hardens as $ω$ decreases -- the induction's feed thins -- so $ω=2$ is the hard case; our proof adapts the Butler-Erdős-Graham induction to this thin-feed regime, where the entire content of the induction step reduces to an explicit onset inequality $Y_0(N)\le\min\{β(N),β'(N)\}$, proved for all $N\ge10$ by Olson's addition theorem and elementary Chebyshev bounds above a finite, machine-checked base range. The same engine extends to the rationals: for every squarefree $b$, every $a/b$ above an explicit threshold $\min\{B_{N_b}/6,\,1/5\}$ is $ω=2$ representable, unconditionally. As an application we give the first complete proof of the rational $ω=3$ statement -- every $a/b$ with squarefree $b$ is a sum of distinct sphenic unit fractions -- that Butler, Erdős and Graham conjectured but left unpublished; a descent settles every $ω\ge3$. What remains open is the $ω=2$ regime below this threshold, which we reduce to a single explicit conjecture -- that the gap-free floor of a semiprime subset-sum set tends to zero. This work is a human-AI collaboration: AI tools (notably Anthropic's Claude, used through Claude Code) contributed substantially to the Lean formalisation, the experiments, and the writing; correspondingly, every result is machine-checked in Lean 4 / Mathlib (no sorry; two cited classical axioms, plus the native_decide compiler-trust base for the finite computations), so its correctness is independent of the tools used.
Problem
The omega=2 integer case of an Erdos-Graham problem: whether every natural number is a finite sum of distinct unit fractions whose denominators are semiprimes.
Approach
The proof adapts the Butler-Erdos-Graham induction to the thin-feed omega=2 regime, reducing the induction step to an explicit onset inequality proved for all N>=10 via Olson's addition theorem and Chebyshev bounds above a finite, machine-checked base range. Developed as a human-AI collaboration using Claude, every result is machine-checked in Lean 4/Mathlib.
Results
Proves the omega=2 integer case and extends to the rationals above an explicit threshold; gives the first complete proof of the rational omega=3 statement, with the sub-threshold omega=2 regime reduced to a single explicit conjecture.