Every fraction, exactly once

Adding the numerators and adding the denominators is the classic schoolroom error. $\tfrac12$ and $\tfrac13$ do not make $\tfrac25$. What that operation does make is worth an essay.

The operation is called the mediant: from $\tfrac{p}{q}$ and $\tfrac{r}{s}$ it makes $\tfrac{p+r}{q+s}$. It is not addition and it is not an average, and unlike either of those it depends on how the fractions are written — $\tfrac12$ and $\tfrac24$ are the same number with different mediants. That looks like a fatal defect and is the source of everything below, because the construction never presents it with a fraction that is not in lowest terms.

The mediant does have one honest property: it lies strictly between its parents. If $\tfrac{p}{q} < \tfrac{r}{s}$ then

$$\frac{p}{q} < \frac{p+r}{q+s} < \frac{r}{s},$$

which follows from cross-multiplying twice. So repeatedly taking mediants fills in the gaps between fractions already present, and never leaves the interval it started in.

Two things about that figure are worth pinning down before going further, because both are surprising and neither is obvious from the rule. Every fraction that appears is in lowest terms — no $\tfrac24$, no $\tfrac36$ — and no fraction appears twice, at any depth, ever. Neither property was designed in. Both fall out of a single identity.

The fence at the right-hand end #

The tree above starts from $\tfrac01$ and $\tfrac10$, and the second of those is not a number. It is a fence: a formal symbol that behaves correctly under the mediant operation and is never evaluated. Its mediant with $\tfrac01$ is $\tfrac11$, which is right, and every subsequent use of it produces something sensible.

This is the only place in this collection where a fraction with denominator zero is allowed to stand, and it earns its place. Without it the construction needs an upper bound and produces only the fractions below that bound; with it the tree covers every positive rational and nothing has to be said about where to stop. The symbol is doing the job that a point at infinity does in the plane extended by one point — closing a construction that would otherwise have a ragged edge — and the resemblance is not a coincidence, since both are the same rational point on a projective line.

Why nothing needs cancelling #

The remarkable property of the tree is that no fraction ever needs reducing. $\tfrac{2}{4}$ never appears; $\tfrac12$ appears once, at the root’s left child, and $\tfrac{2}{4}$ appears nowhere at all.

The reason is a determinant. Call two fractions $\tfrac{p}{q}$ and $\tfrac{r}{s}$ neighbours when

$$rq - ps = 1.$$

The starting pair $\tfrac01$ and $\tfrac10$ are neighbours: $1 \cdot 1 - 0 \cdot 0 = 1$. And if $\tfrac{p}{q}$ and $\tfrac{r}{s}$ are neighbours, then each of them is a neighbour of their mediant:

$$(p+r)q - p(q+s) = rq - ps = 1.$$

So the neighbour relation propagates down the tree, and every node is a neighbour of both its parents forever.

Now the cancelling follows in one line. If a common factor $d$ divided both $p+r$ and $q+s$, it would divide $(p+r)q - p(q+s) = 1$, so $d = 1$. Being in lowest terms is not checked, arranged or maintained: it is a consequence of a determinant that the construction preserves by accident of its own arithmetic.

The same fractions, laid out flat #

The tree can be flattened by taking all the fractions with denominators up to some bound.

Farey sequences and the Stern–Brocot tree are the same object organised differently: the tree is ordered by when a fraction arrives, the sequence by where it sits. Going from $F_n$ to $F_{n+1}$ inserts exactly the mediants whose denominator is $n+1$, and inserts nothing else, which is the sense in which the tree’s levels and the sequence’s orders interleave.

The length of $F_n$ counts something, and counting it two ways is the standard first exercise. Each fraction $p/q$ in lowest terms with $q \le n$ is counted once; grouping by denominator gives $1 + \sum_{q \le n} \varphi(q)$, where $\varphi(q)$ counts the numbers below $q$ that are coprime to it. The two counts are of the same list, so the identity is forced — and it is the same counting-one-thing-twice move that runs through the rest of this field.

Circles that touch #

There is a picture of the Farey sequence that has no business working as well as it does.

Take the circles on $\tfrac{p}{q}$ and $\tfrac{r}{s}$, with centres $(p/q, 1/2q^2)$ and $(r/s, 1/2s^2)$. The squared distance between the centres is

$$\left(\frac{p}{q} - \frac{r}{s}\right)^2 + \left(\frac{1}{2q^2} - \frac{1}{2s^2}\right)^2,$$

and the squared sum of the radii is $\left(\frac{1}{2q^2} + \frac{1}{2s^2}\right)^2$. Subtracting and clearing denominators, the two are equal exactly when $(ps - rq)^2 = 1$ — the determinant again, now as a statement about tangency.

So a fact about arithmetic and a fact about geometry are the same fact. That is the surprise this essay is built around: the determinant that keeps fractions in lowest terms is the condition for two circles to touch, and the size of a fraction’s circle is decided by the denominator that makes the arithmetic work. Nothing about the construction of the tree suggested a picture like this existed.

The circles also explain, at a glance, why good rational approximations are scarce. A number on the line is approximated well by $p/q$ when it sits under a large circle; large circles have small denominators; and the circles fill the strip without overlapping, so there is only so much room. How close a fraction can get makes that argument exactly.

The path is a continued fraction #

Each node in the tree is reached by a sequence of left and right turns. Writing those turns down — $\mathrm{L}\mathrm{L}\mathrm{R}\mathrm{L}$, and so on — gives a code for the fraction, and the code is not new.

Group the turns into runs: three lefts, then two rights, then one left. The run lengths are the continued fraction expansion. The fraction $\tfrac{5}{3} = [1; 1, 2]$ sits at $\mathrm{R}\mathrm{L}\mathrm{R}\mathrm{R}$, whose runs are $1, 1, 2$.

That is the second time in two essays that the same sequence of quotients has appeared from a construction that did not mention it. The tree is built by mediants and knows nothing about Euclid’s algorithm; the algorithm peels squares and knows nothing about trees. They agree because both are recording the same thing — how many times one quantity fits inside another before the roles swap — and each step of the algorithm is a run of turns in one direction.

The golden ratio, whose expansion is all ones, is the path that alternates $\mathrm{L}\mathrm{R}\mathrm{L}\mathrm{R}$ forever: the most balanced possible descent, never committing to a side. Its convergents are the Fibonacci fractions and they are the nodes this alternating path passes through.

Where the mediant is the right operation #

The mediant is the wrong way to add fractions and the right way to combine two ratios of counts, and confusing the two is the source of a well-known statistical paradox.

A player with $3$ hits from $10$ attempts and then $1$ hit from $3$ attempts has a season record of $4$ hits from $13$ attempts. That is the mediant of $\tfrac{3}{10}$ and $\tfrac13$, and it is correct: the totals really do add separately, because a hit is a hit and an attempt is an attempt. Nothing is being averaged.

Now suppose a second player beats the first in both halves of the season — a better ratio in the first, a better ratio in the second — and loses on the year. That is not a contradiction, because the mediant is not monotone in the way an average is: it slides towards whichever parent has the larger denominator. If the second player’s attempts are concentrated in the half where everybody’s ratio is low, the mediant drags their season figure down and nothing was measured wrongly.

This is Simpson’s paradox, and the drawing at the top of this essay is a picture of why it happens. The mediant sits strictly between its parents, but where between depends on the denominators, so two mediants can be ordered oppositely to both of their pairs of parents. Every entry in the Stern–Brocot tree is that effect used deliberately, to move as slowly as possible between two neighbours.

The moral is a small and general one. An operation is not wrong because it is not the operation somebody expected; it is wrong when applied to the wrong things. Mediants of fractions are meaningless — $\tfrac12$ and $\tfrac24$ would give different answers for the same numbers. Mediants of pairs of counts are exactly right, and the tree only ever handles pairs of counts, which is why it never has to cancel anything.

The same fractions in a different order #

There is a second tree that enumerates every positive rational exactly once, and comparing the two says something about what the property is worth.

The Calkin–Wilf tree puts $\tfrac11$ at the root and gives $\tfrac{p}{q}$ the children $\tfrac{p}{p+q}$ and $\tfrac{p+q}{q}$. It also produces every positive rational once and always in lowest terms, and its nodes read in breadth-first order form a single sequence in which the denominator of each fraction is the numerator of the next — a property the Stern–Brocot tree does not have.

What it lacks is order. Reading the Calkin–Wilf tree left to right does not read the fractions in increasing order, so it cannot be flattened into a Farey sequence and it says nothing about approximation. The two trees contain the same nodes and carry different information, and the one worth using depends entirely on the question: enumeration wants Calkin–Wilf, approximation wants Stern–Brocot.

It is worth noticing that both are enumerations of the rationals, which is to say both are proofs that the rationals are countable — a fact usually demonstrated with a zigzag through a grid that visits many fractions twice and needs cancelling afterwards. Either tree does it without repetition and without reduction, which is a tidier proof of a result that is normally proved untidily.

What the picture cannot show #

The tree drawn here has four levels and fifteen nodes. The fraction $\tfrac{355}{113}$, which approximates $\pi$ to seven places, sits at depth $292$ — the tree is exponentially wide and the interesting fractions are exponentially deep, so no drawing shows a node worth naming.

That depth is not a drawing problem. It is why the tree is a poor way to find a fraction and an excellent way to understand one: reaching $\tfrac{355}{113}$ by descending the tree takes $292$ steps, while Euclid’s algorithm reaches it in five, because the algorithm takes a whole run of turns at once. The tree and the algorithm carry the same information at different granularities, and the algorithm’s is the useful one.

There is also something the picture actively misleads about. Drawn on a page, the tree looks as though it fills the interval evenly. It does not fill it at all — the rationals are countable, and the tree enumerates them, so every irrational number is a path down the tree that never lands anywhere. The figure shows a set of measure zero looking dense, which is exactly the illusion more things than boxes exists to dispel.

Where it came from, twice #

Moritz Stern published the construction in 1858; Achille Brocot, a French clockmaker, published it independently in 1861. Brocot was not doing number theory. He was building clocks, and needed gear ratios approximating a required ratio with tooth counts that could actually be cut — the same problem Huygens solved with continued fractions two centuries earlier.

Brocot’s version is a table rather than a tree, and it is used the way a navigator uses a chart: find the target ratio between two entries, take the mediant, and repeat until the approximation is good enough or the teeth get too numerous. Every entry in the table is automatically in lowest terms, which for a clockmaker is not an elegance but a requirement, since a gear pair sharing a factor wears unevenly.

The tree therefore has two independent discoveries, one from arithmetic and one from a workshop, five years apart. That happens often enough in this subject to be worth noticing: the constructions that survive tend to be the ones that somebody needed.

The Farey half of the story has a still stranger history. John Farey, a geologist, published a note in 1816 observing that each fraction in the sequence is the mediant of its neighbours, and admitted he could not prove it. Cauchy proved it and attached Farey’s name. But the sequences had been published fourteen years earlier by Charles Haros, who used them to build a table of decimal equivalents for fractions with denominators up to a hundred — and whose name is on nothing. Hardy’s remark that Farey “was not a mathematician” and that his one contribution to the subject was an unproved observation is unkind and roughly accurate, and the name has stuck anyway.

None of that affects the mathematics, and it affects how the mathematics is found. Both Haros and Brocot arrived at the construction while making a table, which is what people did before they had calculating machines, and a table of fractions in lowest terms is exactly what the mediant produces without being asked.

Where the ladder goes next #

The determinant of one is the thread out of here. It makes the tree’s fractions irreducible, it makes Ford circles tangent, and it is the same condition that makes a lattice basis unimodular — the matrices $L = \left(\begin{smallmatrix}1&0\\1&1\end{smallmatrix}\right)$ and $R = \left(\begin{smallmatrix}1&1\\0&1\end{smallmatrix}\right)$ are the tree’s left and right steps, and they generate the whole group of integer matrices with determinant one.

The other direction is approximation. The tree produces every fraction; the question of which ones are worth having is how close a fraction can get, and the answer is a pigeonhole argument that finds the same fractions the tree’s alternating paths pass through.