Short Egyptian Fractions: How OpenAI’s Proof Solved Erdős’s 76-Year-Old Conjecture and Established the Optimal Double-Logarithmic Bound

How many fractions does a fraction really need? For 76 years, a conjecture of Paul Erdős asked whether every rational number below one could be assembled from remarkably few distinct reciprocals. OpenAI’s September 25, 2026 manuscript, Short Egyptian Fractions, presents a proof that the worst-case minimum length grows like the logarithm of the logarithm of the denominator. Its key contribution is a uniform upper bound, matching Erdős’s classical lower bound. The argument combines prime products, small modular residues, and a way to turn success for most numerators into success for every numerator.

1. What Are Short Egyptian Fractions, and Why Does Length Matter?

An Egyptian fraction is a sum of distinct positive unit fractions: reciprocals of different positive integers. For example, $\frac{5}{6}=\frac{1}{2}+\frac{1}{3}$. Both summands have numerator one, and their denominators differ.

Existence is elementary. Efficiency is harder. A procedure can produce an expansion without producing the shortest Egyptian fraction representation. Here, “short” concerns the number of summands. The theorem places no upper restriction on their denominators, which may become enormous.

1.1. Short Egyptian Fractions: Key Facts

The last distinction matters computationally. Storing a few exceptionally large integers can require substantial memory, even when the expression looks compact on paper.

2. Erdős’s 1950 Conjecture: A 76-Year Question

Let $N(a,b)$ denote the smallest number of distinct unit fractions summing to $\frac{a}{b}$, where $1\le a<b$. Let $N(b)$ be the maximum of these minimum lengths over all permitted numerators. Fractions need not be reduced first.

The order of those operations matters: minimize separately for each fraction, then select the hardest numerator. The theorem does not say every numerator is equally difficult. Indeed, $N(1,b)=1$.

Erdős proposed the double-logarithmic upper bound in 1950 and established the matching lower order. The question is recorded as Erdős Problem 304. Its challenge was uniformity: a method had to handle every numerator over the chosen denominator, including arithmetically awkward cases.

This is a separate question from Erdős’s reciprocal-sum problem about arithmetic progressions. Shared names and reciprocal notation do not make their conclusions interchangeable.

3. What OpenAI Proved: The Optimal Double-Logarithmic Bound

Theorem 1.1 states that positive absolute constants $c_1,c_2$ and a threshold $b_0$ exist such that, for every integer $b\ge b_0$,

All logarithms here are natural. “Absolute” means these constants do not change with the numerator or denominator. The upper inequality guarantees a short expansion for every numerator. The lower inequality says that some numerator requires proportionally that many terms.

Together, these establish $N(b)=\Theta(\log\log b)$, the optimal double-logarithmic bound. Optimality concerns growth order, rather than a sharp leading constant or the exact minimum for a particular input.

For scale, if $b=\exp(\exp(t))$, its double logarithm is $t$. This describes a remarkably slow increase, but unknown constants and a sufficiently large threshold prevent direct numerical promises for everyday fractions. The distinction between asymptotic order and usable thresholds also appears in our irrationality-exponent analysis.

4. Why the Greedy Algorithm Did Not Establish Erdős’s Bound

The Fibonacci–Sylvester greedy algorithm subtracts the largest unit fraction no greater than the current remainder. For $5/6$, it selects one half, then one third. More generally, the reduced positive numerator strictly decreases, ensuring termination.

Termination alone provides no double-logarithmic length guarantee. Choosing the best immediate subtraction does not establish that the complete route is short enough. A locally sensible turn can still produce a lengthy journey.

Erdős obtained a uniform upper bound of order $\frac{\log b}{\log\log b}$. Vose later improved it to $O(\sqrt{\log b})$. That sharper historical comparison is important: the new theorem improves a square-root-logarithmic guarantee, rather than merely replacing a logarithmic estimate.

The new proof still uses greedy subtraction, but only to prepare the fraction. Its decisive improvement comes from a richer supply of denominators and controlled choices among possible remainders.

5. Preparing a Controlled Remainder

Set $S=\log b$. Lemma 2.3 runs greedy subtraction until the expansion finishes or its unreduced denominator reaches a chosen threshold $T$.

For a positive remainder $\frac{A}{C}$, choose $z=\lceil C/A\rceil$. Subtracting $\frac{1}{z}$ leaves numerator $Az-C$ over denominator $Cz$. The new numerator is smaller than $A$, while the new denominator is at most $C^2$.

The remainder’s value satisfies an even stronger contraction:

After the first positive step it is below one half. Repeated squaring then makes it doubly exponentially small in the number of steps. Yet a positive fraction with integer numerator and denominator below $T$ exceeds $\frac{1}{T}$. Those facts force termination or threshold crossing after $O(\log\log T)$ steps.

Choosing $T=\exp(D_CS)$, with a fixed construction constant $D_C$, therefore costs $O(\log S)$ terms. The resulting numerator remains at most $b$, and the denominator lies between $T$ and $T^2$. This prepares exactly the input needed by the main construction.

6. The Dense-Family Breakthrough

Proposition 2.1 builds a common auxiliary denominator $M$ and a large collection $G$ of good numerators. Each good fraction $\frac{u}{MC}$ has an expansion using at most $L\log S$ unit fractions, initially allowing repetitions.

More precisely, fixed constants give $e^S<M\le e^{D_MS}$ and a cutoff $X=e^{(D_M+2)S}$. Among the positive integers up to $X$, at most $X/8$ are outside $G$. The stronger estimates underlying the proposition make the exceptional proportion tend to zero.

This reverses the obvious approach. Instead of solving each difficult numerator independently, the proof constructs a common environment in which almost every numerator is easy. The remaining task becomes an additive question: can the original target be assembled from two good members?

That final conversion is elementary. Establishing enough good members, with the same denominator and the same length bound, requires most of the paper’s technical work.

7. How Prime Products and Small Residues Reduce the Numerator

The engine is a unit fraction decomposition controlled by a divisor $t$ of $M$. Choose $z=\lceil Qt/u\rceil$ and put $h=uz-Qt$. Then

To check it, place both right-hand terms over $zMQ$. Their numerators add to $Qt+h=uz$. Because $t$ divides $M$, the first term really is a unit fraction with integer denominator.

The remainder numerator $h$ is the least nonnegative residue of $-Qt$ modulo $u$. Ordinarily it could be almost as large as $u$. The proof engineers many divisor choices so that a useful share produce much smaller residues.

For an arithmetic illustration, take $M=30$, $Q=7$, $u=11$, and $t=3$. Then $z=2$ and $h=1$, giving $\frac{11}{210}=\frac{1}{20}+\frac{1}{420}$. A numerator of eleven becomes one after a single subtraction. These small numbers illustrate the identity, rather than the asymptotic construction’s size conditions. Its real achievement is guaranteeing useful choices across many successive ranges.

For large numerator ranges, $Q=C$. Products of selected distinct primes generate a deterministic list of divisors. Exponential-sum and discrepancy estimates show that their residues are sufficiently distributed for most numerators. Discrepancy measures departure from uniform distribution around the modular circle.

At lower ranges, $Q=1$, and independent random prime-product blocks supply the required divisors. These are probabilistic existence arguments for suitable fixed lists. Their use does not make the final theorem probabilistically true.

The construction descends through $O(\log S)$ ranges. Several independent blocks cover every numerator in the terminal range. Finally, a sufficiently large power of two dividing $M$ handles the smallest numerators through binary expansion. Scaling denominators reconnects the lower-range expansions to the original denominator factor $C$.

8. The Technical Barrier: Divisor Moments and Exceptional Sets

A small residue helps only if it already has a short expansion. What prevents many larger numerators from landing in the same small collection of failures?

For fixed $t$ and $h$, every predecessor $u$ satisfies $u\mid Qt+h$. Thus predecessor multiplicity is bounded by the truncated divisor count $d_X(n)$, the number of positive divisors of $n$ no greater than $X$.

Lemma 3.1 controls the average of high powers of this count on shifted intervals. Under its specified size conditions, for each fixed moment order $r$, the sum of $d_X(N+h)^r$ over $1\le h\le Y$ is at most $Y\exp(S^{1/4})$.

The shift matters. Relevant integers can sit far from zero, so an estimate available only for initial intervals would not suffice. Uniformity also matters because the same bound must apply to every divisor list at every stage.

Hölder’s inequality turns that moment estimate into control over the total predecessor count of an exceptional set. If its proportion is $\delta$, its contribution carries a factor $\delta^{1-1/r}$, alongside controlled losses.

Section 5 iterates the resulting recurrence. The moment order is chosen sufficiently large before $S$ grows. The exponentially small initial error dominates the accumulated losses across the descent, leaving at most one eighth of the top range exceptional. Merely knowing that most individual steps work would not establish this compatibility.

The moment estimate itself separates prime factors by size and bounds their possible contributions to small divisors. This truncation is tailored to the predecessor problem: only divisors that could be numerators in the current range count. Keeping the list indices also matters, since random products can repeat. Both sides of the counting argument must retain those multiplicities.

9. From Almost Every Numerator to Every Fraction

Return to the prepared remainder $\frac{A}{C}$. Choose $g=\lfloor X/(AM)\rfloor$ and set $n=gAM$. The construction ensures $X/2\le n\le X$.

There are $n-1$ positive ordered splits $n=u+(n-u)$. At most $X/8$ integers in the entire range are bad. A bad integer can invalidate a split in either position, so at most $X/4$ splits fail for that reason.

For sufficiently large $X$, more candidate splits exist than can be invalidated. Hence some split has both numerators in $G$. Their expansions add to

Multiplying every unit-fraction denominator by $g$ divides the sum by $g$, recovering $\frac{A}{C}$. Adding the greedy prefix still uses only $O(\log S)$ terms.

Repeated denominators remain a potential problem. Lemma 2.2 removes repetitions while preserving the number of terms for any positive total below one. Its replacement identities strictly increase the sum of denominators, while only finitely many denominator lists represent a fixed total at fixed length. Termination therefore yields distinct denominators.

This completes the uniform upper bound. The passage from a dense family to every target is the logical bridge that an average-case result alone would lack.

10. Why the Double Logarithm Cannot Be Improved in Order

Take any $k$-term expansion of $\frac{b-1}{b}$ and append $\frac{1}{b}$. The resulting $s=k+1$ terms sum to one. Sort their denominators and let $L_j$ be the product of the first $j$.

Before each term, the remaining positive rational has denominator dividing the preceding product. Its value is therefore at least the reciprocal of that product. Ordering the remaining terms supplies the opposite bound, giving $d_j\le sL_{j-1}$ and $L_j\le sL_{j-1}^2$.

Iterating these inequalities bounds denominator growth. Since $b$ itself occurs among the denominators,

Taking logarithms twice forces $k$ to be at least a positive constant times $\log\log b$. Thus the numerator immediately below one witnesses the lower bound. The paper closes the upper-bound gap while reusing this classical obstruction.

11. Counting Expansions and Preserving Denominators

The uniform theorem has two different consequences. Let $F(k)$ count increasing denominator lists whose exactly $k$ distinct reciprocals sum to one. The paper proves

A short expansion containing a denominator with many prime factors supplies many divisors. Divisor-indexed splitting then creates many different expansions. An injective padding operation extends them to every sufficiently large exact length without merging different outputs. Elementary denominator bounds supply the matching upper order.

Specifically, $F(k)\le k^{2^k-1}$. Thus the number is finite for each fixed length, even though denominators are not restricted in the definition. The matching double-exponential lower order measures how many choices exist, rather than how quickly an algorithm can enumerate them.

11.1. Two Double-Exponential Results, Different Questions

For the second quantity, the paper establishes

Every integer from two up to, but excluding, $v(k)$ occurs somewhere in an exact $k$-term expansion of one. Different prescribed integers may require different expansions. No single expansion is claimed to contain them all. Corollary 1.3 gives the eventual lower estimate $v(k)\ge\exp(\exp(k/600))$.

Keeping an exact denominator is stricter than retaining a multiple of it. Section 7 reserves $\frac{1}{m}$, uses a greedy prefix that avoids denominator $m$, and expands a tail smaller than every reserved reciprocal. A separate padding lemma preserves the marker while increasing the length.

Section 8 constructs a quantitative version directly. Prime-product residue collisions and a quantitative form of Vinogradov’s three-prime theorem provide rational building blocks. Divisors of the unreduced greedy denominator group the remaining numerator into few pieces.

The resulting eventual length coefficient is $\frac{257}{\log2}+\varepsilon$, for every fixed $\varepsilon>0$. This controls prescribed-denominator expansions. It is not an explicit value of the main theorem’s upper constant $c_2$.

12. What Lean Verifies and What Remains Unresolved

OpenAI’s formalization scope document covers the main asymptotic theorem, counting expansions, denominator bounds, marker-preserving padding, and the quantitative prescribed-denominator results. The published implementation contains corresponding proofs. Comparator files specify target statements with placeholders, while a separate solution module supplies the arguments.

This article checks those published materials without claiming an independent Lean build or a line-by-line audit of the manuscript. As our Fermat formalization explainer discusses, discovering mathematics, formalizing it, and independently validating an artifact are distinct activities.

OpenAI places this paper within its October mathematics release, produced by an internal frontier model. That provenance does not establish a practical shortest-expansion solver. Exact optimization, useful numerical thresholds, and restricted denominator sizes remain separate requirements. The paper reports no application benchmark demonstrating computational gains.

Short Egyptian Fractions matters because a uniform existence theorem now reaches the predicted growth order through explicit mathematical mechanisms. Follow Binary Verse AI’s mathematical-proof coverage for explanations that keep the theorem, its verification scope, and its practical implications in view.