Three unit fractions for every four over n

Every fraction, exactly once built the Stern–Brocot tree from one operation, the mediant, and one invariant. Any two fractions that are neighbours at some stage of the construction, $a/b$ and $c/d$ with $a/b < c/d$, satisfy $bc - ad = 1$. That invariant is why every fraction in the tree is already in lowest terms, and two matrices that generate the tree turned it into the statement that a product of matrices has determinant one.

There is a third way to read it. If $bc - ad = 1$, then

$$\frac{c}{d} - \frac{a}{b} = \frac{bc - ad}{bd} = \frac{1}{bd}.$$

Neighbouring fractions differ by a unit fraction — a fraction with numerator one. That makes the tree a machine for one of the oldest problems in arithmetic: writing a fraction as a sum of unit fractions, the way Egyptian scribes did four thousand years ago.

The figure applies it to $4/17$. Its left neighbour in the tree, the closest fraction below it with a smaller denominator, is $3/13$, and $4/17 - 3/13 = 1/221$. The left neighbour of $3/13$ is $2/9$, and the gap is $1/117$; then $1/5$, with gap $1/45$; then $0/1$, with gap $1/5$. Adding the four gaps back up gives

$$\frac{4}{17} = \frac15 + \frac1{45} + \frac1{117} + \frac1{221}.$$

Every fraction can be taken apart this way, and the parts are always distinct unit fractions, because the denominators strictly decrease along the chain.

The search below the line finds a shorter decomposition of the same number: $4/17 = 1/5 + 1/30 + 1/510$, three unit fractions instead of four. In 1948 Paul Erdős and Ernst Straus asked whether this is always possible: is $4/n$, for every whole number $n \geq 2$, a sum of three unit fractions? The tree gives four. The question is whether three are always enough, and it is still open.

Neighbours differ by a unit fraction #

The identity is the same one that how evenly the fractions spread used for the Farey sequences, the lists of all fractions with denominator up to a bound. In the Farey sequence of order 5 there are eleven fractions, and the ten gaps between neighbours are 1/5, 1/20, 1/12, 1/15, 1/10, 1/10, 1/15, 1/12, 1/20 and 1/5 — every one a unit fraction, every denominator the product of the two neighbours’ denominators. The arches are the semicircles of the arcs a line crosses, and the gap under each is the unit fraction the tree assigns to it.

Adding the gaps from 0 up to any fraction writes it as a sum of unit fractions, but wastefully: reaching $4/5$ by adding every gap takes nine. The chain of left neighbours is the efficient version. From $a/b$, the left neighbour of smallest-possible difference — the one with the largest denominator below $b$ — is reached in one jump, and from there the next. Each jump lowers the numerator — the left neighbour of $a/b$ is $c/d$ with $c = (ad - 1)/b$, which is less than $a$ because $d$ is less than $b$ — so the chain from $4/n$ takes at most four jumps, and the decomposition has at most four terms.

The chain is a consequence of the tree’s structure, not of any cleverness about $4/n$. The left neighbour of $a/b$ is found by solving $ad \equiv 1 \pmod b$ for the largest $d$ below $b$, which is how the figures compute it. That is the same congruence that places $a/b$ in the tree: the tree is a record of which fractions are neighbours, and a decomposition into unit fractions is a walk through that record.

Four terms, two, and the greedy rule #

For odd $n$ — even $n$ reduce to smaller cases, as the identities below show — the tree’s chain has a rigid pattern. When $n$ leaves remainder 3 on division by 4, the left neighbour of $4/n$ is $1/((n+1)/4)$ directly, and the decomposition has two terms:

$$\frac4n = \frac{1}{(n+1)/4} + \frac{1}{n(n+1)/4}.$$

When $n$ leaves remainder 1, the chain passes through $3/m$, $2/m'$ and $1/m''$ on its way down, and the decomposition has four terms. The top row of the figure alternates 4, 2, 4, 2 accordingly.

The second row is the oldest method on record. Fibonacci described it in 1202, and J. J. Sylvester proved in 1880 that it always terminates: take the largest unit fraction that fits, subtract it, and repeat. For $4/17$ it takes $1/5$ first, leaving $3/85$, then $1/29$, leaving $2/2465$, then $1/1233$, and finally $1/3039345$ — four terms, with the denominators roughly squaring at each step. On these 49 values of $n$ the greedy rule uses four terms eight times, three on others, two on the rest. Like the tree, it can need four. Its last denominators grow so fast that the figures compute them with integers of unlimited size.

The third row is the fewest possible, found by searching every decomposition. It is never more than three. It is two on 34 of the 49 values — every $n$ that leaves remainder 3 on division by 4, and some others — and three on the remaining 15. The gap between the second and third rows is the content of the conjecture. Neither the tree nor the greedy rule finds the three; something else does, and for each $n$ in the figure, a search can always find it.

Identities that settle whole classes #

The natural way to prove the conjecture is by formula: find an expression for $1/x + 1/y + 1/z$ that works for a whole class of $n$ at once. Two observations make that approach powerful.

The first is that a solution for $n$ gives a solution for every multiple of $n$. If $4/a = 1/x + 1/y + 1/z$, then dividing by $b$ gives $4/(ab) = 1/(bx) + 1/(by) + 1/(bz)$. So it is enough to settle prime $n$, and in particular even $n$ follow from $n = 2$, where $4/2 = 1/1 + 1/2 + 1/2$, and multiples of 3 follow from $4/3 = 1/1 + 1/4 + 1/12$.

The second is that simple identities settle most remainders. For $n \equiv 3 \pmod 4$, the two-term decomposition above, with its first term split as $1/k = 1/(k+1) + 1/(k(k+1))$, gives three. For $n \equiv 2 \pmod 3$,

$$\frac4n = \frac1n + \frac{1}{(n+1)/3} + \frac{1}{n(n+1)/3},$$

which is checked by adding the right-hand side: $\frac{(n+1) + 3n + 3}{n(n+1)} = \frac{4}{n}$. For $n \equiv 5 \pmod 8$, writing $k = (n+3)/4$,

$$\frac4n = \frac1k + \frac{1}{n(n+3)/8} + \frac{1}{n(n+3)/4}.$$

The figure checks each identity on every $n$ of its class up to 5,000. A prime that escapes all three must leave remainder 1 on division by 4, 1 on division by 3, and 1 on division by 8 — so remainder 1 on division by 24. That class, the orange cell, is where every hard case lives.

The hard primes #

Counting every decomposition for every $n$ up to 1,000 shows what the identities predict. The counts grow with $n$ — up to 5,004 ways for the most composite numbers, which inherit decompositions from each of their factors — but the primes that leave remainder 1 on division by 24 sit along the bottom of the cloud. Above 100, the fewest ways of all belong to 193, with six. These primes are not unsolvable; they are only the ones where solutions are scarce, because no identity hands them one and no factor passes one down.

Louis Mordell pushed the identities further in 1967, by working modulo 840 rather than 24. His identities settle every $n$ except those leaving one of six remainders on division by 840: 1, 121, 169, 289, 361 and 529. Those six numbers are $1^2$, $11^2$, $13^2$, $17^2$, $19^2$ and $23^2$ — squares — and the pattern is not a coincidence. A theorem of Andrzej Schinzel shows that no identity of this polynomial kind can cover a class of $n$ that are squares modulo the identity’s modulus, so the approach by identities cannot finish the job, however large a modulus is tried.

The last figure counts decompositions for every prime up to 6,000 in the hard class, 89 of them. Every one has at least six decompositions, and the counts drift upwards with $p$, the sixteen primes in Mordell’s square classes sitting a little lower than the rest. Nothing in the figure suggests a prime with none. Searches by computer have confirmed the conjecture for every $n$ up to $10^{17}$, and in 1970 Robert Vaughan proved that the exceptions, if any exist, are extremely rare: the number of $n$ up to $N$ for which it fails is a vanishing fraction of $N$, smaller than $N$ divided by any fixed power of $\log N$.

Why the tree cannot do it alone #

The tree supplies decompositions mechanically, and the conjecture asks for something the tree’s mechanism cannot see. A chain of left neighbours takes a fixed path determined by $4/n$’s position in the tree. To use three terms instead of four, a decomposition has to jump: the three-term solution for $4/17$ begins with $1/5$, as the tree’s does, and then replaces the tree’s three remaining gaps, 1/45, 1/117 and 1/221, with the two gaps 1/30 and 1/510. On the magnified line in the first figure, 1/30 carries the remainder past both $2/9$ and $3/13$, to a point that is not a neighbour of anything in particular.

That point is $1/5 + 1/30 = 7/30$, and its denominator, 30, has nothing to do with 17. The search found it by trying every possibility. This is the general picture: three-term solutions exist in abundance for most $n$, but they come from arithmetic accidents — a convenient factorisation of $n+1$, or of $n+3$, or of some other expression — rather than from a structure that the tree, or any single identity, can provide for every $n$. The fractions that beat every smaller one were exactly those the tree’s path picks out; the fractions an Egyptian decomposition needs are the ones its path skips.

The contrast with three circles that touch and are not the largest is worth noticing. There a greedy rule turned out to be exactly optimal for every triangle, and the obvious structured alternative was wrong. Here the greedy rule and the structured alternative, the tree, both use four terms where three would do, and the best decompositions are found only by search. Greediness is right in one problem and wasteful in the other, and nothing about either problem announces which — the same lesson as the order a graph’s vertices are coloured in, where the greedy rule is perfect for some orders and arbitrarily bad for others.

What a solution for a prime looks like #

The decompositions that the search finds for a prime are not shapeless, and their shape explains both why they are plentiful and why they are hard to guarantee. For $p = 17$ there are four: $1/5 + 1/30 + 1/510$, $1/5 + 1/34 + 1/170$, $1/6 + 1/15 + 1/510$, and $1/6 + 1/17 + 1/102$. In every one, either one or two of the three denominators is a multiple of 17 — 510 alone in the first, 34 and 170 in the second — and never none and never all three. The same holds for 73 and for 193, and it holds for every prime: if no denominator were divisible by $p$, the sum $1/x + 1/y + 1/z$ would have a denominator free of $p$ and could not equal $4/p$, and if all three were, the sum would be at most $3/p$.

So the decompositions of $4/p$ fall into two families, according to whether one denominator or two carries the factor $p$. In each family, a solution amounts to finding whole numbers that satisfy a single multiplicative condition — a divisor of some expression in $p$ lying in a particular residue class — and that is a question about the factorisation of numbers like $p + 3$ or $p + 7$, or of products of them. For most primes such a divisor exists many times over. For a prime in the hard class, the residue class needed is one that the small expressions refuse to hit, and the search has to go further out before a suitable divisor turns up. That is why the hard primes sit low in the counts, and why, so far, they always have a few solutions rather than none.

The two families are also the reason the problem is a question about primes in residue classes. Which primes have a divisor of the right kind is the same sort of question as which primes a quadratic form takes, where the answer for $x^2 + y^2$ is a congruence — and where, for slightly more complicated forms, no congruence suffices. The Erdős–Straus conjecture for a given prime asks for one of infinitely many such conditions to hold. Each condition is easy to test and none is known to hold for every prime.

Why four, and not five #

The question is asked for numerator 4 because smaller numerators are easy. Every $2/n$ is a sum of two unit fractions — $2/n = 1/((n+1)/2) + 1/(n(n+1)/2)$ for odd $n$ — which is the formula behind the table of $2/n$ decompositions in the Rhind papyrus, written about 1550 BC. Every $3/n$ is a sum of at most three, by a similar argument. For 4 the cheap arguments stop working on the class of 1 mod 24, and that is where the conjecture sits.

Wacław Sierpiński asked the same question for numerator 5: is $5/n$ always a sum of three unit fractions? It is also open, with the same pattern — identities settle most classes, searches settle every $n$ tried, and a class of squares remains. The general conjecture that $m/n$ is a sum of three unit fractions for all large enough $n$, for every fixed $m$, is also open. The question with 4 is the first of an infinite family, and the hardest-looking one has the easiest statement.

Even a single case can be surprisingly expensive to settle by hand. The sum that steps over every whole number showed that a run of consecutive unit fractions never adds up to a whole number, and one structural reason — a single number in the run divisible by a higher power of 2 than any other — settles every case at once. The decompositions of 4/n have no such structure: they are scattered, with no visible rule for which $x$ works, and the only reliable way to find one for a given prime in the hard class is to try values of $x$ until one does. That the search has never failed is the evidence; that it has never been explained is the problem.

What the figures show and do not #

The figures compute the tree’s chain of left neighbours exactly, the greedy expansion in integers of unlimited size, and every three-term decomposition by exhaustive search, for each $n$ shown. They check the three identities on every $n$ in their classes up to 5,000, which is a check of the algebra, already proved by adding fractions. They establish the counts for $n$ up to 1,000 and for the hard primes up to 6,000. Mordell’s list of six classes, Schinzel’s theorem about squares, Vaughan’s bound and the verification to $10^{17}$ are results from the literature; the figure marks which primes fall in Mordell’s classes, and does not reprove why the others are covered.

Still open: three unit fractions for every n #

Whether $4/n$ is a sum of three unit fractions for every $n \geq 2$ is open. The Erdős–Straus conjecture is settled for every $n$ outside six classes modulo 840, for every $n$ up to $10^{17}$, and for all but a vanishing fraction of $n$ in general. What is missing is an argument for the primes that leave remainder 1 on division by 24 — specifically those in Mordell’s six square classes — that does not reduce to searching.

The obstruction is understood. Schinzel’s theorem rules out the identities that settle everything else, so a proof has to use something that a polynomial formula cannot: the multiplicative structure of the particular prime, the existence of a suitable divisor of some number built from it. Christian Elsholtz and Terence Tao showed in 2013 that the number of decompositions of $4/p$, averaged over primes, grows like a power of $\log p$ — so solutions become more plentiful, not less, as $p$ grows, and the counts in the last figure drift upwards as that predicts. An average is not a guarantee for each prime, and turning plenty on average into at least one every time is the step nobody has found.