Short Egyptian fractions

The explanation

Take the fraction 4/5. It can be written as 1/2 + 1/4 + 1/20. Each piece is a unit fraction, meaning 1 over a whole number. The bottom numbers are all different. A sum like this is called an Egyptian-fraction expansion. A computer search shows 4/5 needs three pieces; two will not do. Some fractions need more. By the same search, 16/17 needs five: 1/2 + 1/3 + 1/10 + 1/128 + 1/32640.

Here is the question. Fix the bottom number b of a fraction a/b, with a smaller than b. Try every top number a. Ask for the worst case: how many pieces can the hardest fraction need? The paper calls this count N(b). For b = 17, the search above gives five. Some top numbers are easy. For example, 1/b needs only one piece.

A simple method always finishes. It is the greedy method: take the largest unit fraction that fits, then repeat on what is left. But it can waste pieces. For 5/121 it uses five pieces, and the last bottom number has 25 digits. Yet 5/121 = 1/33 + 1/121 + 1/363 uses only three. So the real question is how short the best expansion can be.

Here is what was known before. In 1950, Paul Erdős reported a bound due to de Bruijn and improved it. He proposed that about log log b pieces should always be enough. A logarithm (log) of a number roughly tracks how many digits it has. So log log b roughly tracks how many digits that digit count has. It grows extremely slowly. For b with 100 digits, log log b is about 5.4. Erdős also proved that you cannot do better. The fraction (b−1)/b already needs that many pieces, up to a fixed multiplier. Vose later reached a bound of order the square root of log b, in 1985. For a 100-digit b that is about 15.2, ignoring fixed multipliers. The question is listed as Erdős Problem 304.

This paper proves Erdős's guess, with a Lean proof listedSource 1. There are fixed numbers c1 and c2 that work for every large enough b. The worst case N(b) always lies between c1 times log log b and c2 times log log b. The upper bound holds for every top number aSource 2. The lower bound was already known. The new part is the upper bound, for all top numbers at onceSource 3. The paper does not compute c2Source 4. So it gives no exact piece count for any particular b.

What made this hard? The proof cuts off one unit fraction at a time, shrinking the top numberSource 5. Each cut works for most top numbers, but some fail. Across many cuts, those failures could pile up. The paper claims they stay rare at every stageSource 6. It ends with a large range in which almost every top number has a short expansionSource 7. Any target top number, after scaling, is then the sum of two good onesSource 8. Two short expansions together make one short expansion.

The bottom numbers are left unrestrictedSource 9. The expansion is short, but its pieces may have enormous bottom numbers. Earlier work by Tenenbaum and Yokota also kept the bottom numbers small. This paper does not try to.

The paper also counts ways to write 1 itself. Let F(k) count the expansions of 1 with exactly k different pieces. A short search gives F(3) = 1, from 1/2 + 1/3 + 1/6, and F(5) = 72. The paper proves F(k) grows doubly exponentially, with a Lean proof listedSource 10. That means log log F(k) is about a fixed multiple of k. It also studies v(k). This is the smallest whole number from 2 up that is never a bottom number in such an expansion. For every large enough k, v(k) is at least e to the power e^(k/600)Source 11. Van Doorn and Tang had earlier proved a lower bound of the form e^(c·k²).

How sure is this? The Lean scope note says a computer proof checker called Lean has a formal proof of the main statement. It covers the log log b order of the worst case. It also covers the count F(k) and the bounds on v(k). No specialist review has been published yet.

What it doesn't show. This does not give the exact piece count for any particular fraction, or keep the bottom numbers small.