The arcs a line crosses on its way to a number

Writing the Stern–Brocot tree as matrices ended on a picture it did not draw. The two matrices generate a group of transformations of the upper half-plane, and that group has a picture — a tessellation — of which the tree is one corner.

The picture is simple to describe. Take every pair of fractions that are neighbours in the Farey sense, and join each pair by a semicircle standing on the number line.

The arcs a line crosses on its way down to a number are the steps of the descent towards it. The figure finds the crossed arcs by sweeping all 115 for the ones whose ends straddle the number, finds the descent’s intervals separately by taking mediants, and requires the two lists to agree term by term. The turns and the continued fraction are read off the arcs and checked against the descent and against the number’s own expansion.

Arcs that never cross #

Two fractions $p/q < r/s$ are neighbours when $rq - ps = 1$ — the condition that made every fraction appear once, and the condition the matrices turned into a determinant. The figure checks each arc it draws twice: the determinant is one, and no fraction with a denominator at most the larger of the two lies strictly between them.

The first thing the picture shows is that the arcs never cross, and the reason is a fact about the intervals. Two intervals between Farey neighbours are either nested or have no interior point in common — they never overlap partway. An interval between neighbours is exactly an interval the descent passes through, and the descent’s intervals are made by repeatedly splitting an interval at its mediant, so any two of them are related the way two intervals in a repeated bisection are. Semicircles over nested or disjoint intervals cannot cross, and so the arcs fit together without a single intersection.

What they fit together into is a set of curved triangles. The arc over $[p/q, r/s]$, the arc over $[p/q, m]$ and the arc over $[m, r/s]$, where $m$ is the mediant, bound a region with three corners on the number line and none above it. Every point of the half-plane above the line lies in exactly one such region or on its boundary, and the regions are all the same shape in a sense the next sections make exact.

Where the Ford circles touch #

The Ford circles were the first picture of the neighbour condition: a circle of diameter $1/q^2$ standing on each fraction $p/q$, touching the circle on $r/s$ exactly when the two are neighbours. The tessellation draws the same condition as an arc, and the two pictures fit together more closely than that shared condition suggests.

Where two Ford circles touch lies on the arc joining their fractions. For $0/1$ and $1/1$ the two circles have radius a half and centres at $(0, \tfrac12)$ and $(1, \tfrac12)$, so they touch at $(\tfrac12, \tfrac12)$ — the top of the arc over $[0, 1]$. For $0/1$ and $1/2$ the second circle has radius $\tfrac18$ and centre $(\tfrac12, \tfrac18)$; the point of contact divides the segment between the centres in the ratio of the radii, four to one, which puts it at $(0.4, 0.2)$, and that point is at distance exactly $\tfrac14$ from $(\tfrac14, 0)$ — on the arc over $[0, \tfrac12]$.

The general statement has a reason in the geometry the arcs belong to. There, the number line is infinitely far from every point above it, and a Ford circle is what an ordinary circle becomes when its centre is moved all the way out to a fraction on that line — a curve every point of which is, in a limiting sense, equally far from the fraction. The arc joining two fractions is the straight line between them. Two such curves that touch do so on the line joining their centres, as two touching circles do in ordinary geometry, and the line joining the two fractions is the arc. The circles are the tessellation’s corners, and the arcs are the lines between the corners, drawn in one picture instead of two.

Why the crossings are the descent #

A vertical line at $x = t$ crosses the semicircle over $[a, b]$ exactly when $a < t < b$. So the arcs it crosses are the Farey intervals that contain $t$, and those are nested — each inside the one before — so the line meets them in order of size, largest first.

The descent towards $t$ starts from $[0, 1]$, takes the mediant, and keeps whichever half contains $t$. Every interval it produces is a Farey interval containing $t$; every Farey interval containing $t$ is one it produces, because the Farey intervals are exactly the intervals repeated splitting at mediants can reach. The line and the descent visit the same intervals in the same order, one geometrically and one arithmetically, which is what the figure’s first check requires.

For $\sqrt2 - 1$ the intervals can be followed by hand. The descent starts from $[0, 1]$ and its mediant $1/2$ is too big, so it keeps $[0, 1/2]$ — a left turn. The next mediant, $1/3$, is too small, so it keeps $[1/3, 1/2]$; the next, $2/5$, is too small again, giving $[2/5, 1/2]$; then $3/7$ is too big, giving $[2/5, 3/7]$, and $5/12$ is too big, giving $[2/5, 5/12]$. The next mediant would be $7/17$, beyond the drawing’s largest denominator of 13. Those six intervals are the six thick arcs in the first figure, from the largest down, and the turns taken between them spell $LRRLL$.

The turns follow. Between one crossed arc and the next, the line passes through one curved triangle: in through its top side, the arc over $[a, b]$, and out through one of its two lower sides, the arcs over $[a, m]$ and $[m, b]$. It leaves by the left side when $t < m$ and by the right side when $t > m$ — and those are the descent’s turns, left when the mediant is too big and right when it is too small. The figure reads each turn from which endpoint the next crossed arc shares with the current one, and requires the word to be the descent’s.

The golden ratio’s line zigzags as tightly as a line can, which is the picture of the rectangle that eats itself cutting off one square at a time. Every triangle it enters, it leaves by the side it did not use last time.

Runs are fans around one corner #

A run of identical turns has a picture too. When the line leaves several triangles in a row by the left side, it keeps the same right-hand endpoint throughout — every arc it crosses in that run ends at one fixed fraction on the number line. The triangles it passes form a fan around that fraction: a sequence of arcs all standing on the same point, each smaller than the last, squeezed in beside it.

The length of each fan is a quotient of the continued fraction. The line to $\pi - 3$ runs down a fan of six triangles around $0$ before it can turn, because $\pi - 3$ lies between $1/8$ and $1/7$; then a fan of fifteen around $1/7$, of which the drawing shows three before its arcs become too small to include. The first run is one shorter than the first quotient because the drawing starts inside the arc over the whole interval $[0, 1]$, which is already the first triangle of that fan. The figure compares every complete run with the quotient the number’s own expansion gives.

That makes the continued fraction a count of fans, and the long fan of 292 further down the line to $\pi$ is the reason the fraction $355/113$ is so good: the line spends a long time turning around one corner, and the corner is an extraordinarily close approximation.

What the fans’ corners are #

The fraction a fan stands on is where the line turns, and the fractions where the line turns are the ones the descent passes at the ends of its runs.

A fan’s corner is a best approximation, because the line stays near it for a whole run: every triangle in the fan has that fraction as a vertex, and the line cannot pass through them without the fraction being the closest simple one available. The records the descent finds are the corners of the fans the line passes, and how close a fraction can get is decided by how long the fans are.

Two symmetries of the whole picture #

The drawing shows the tessellation over the unit interval, and the rest of it is determined by two symmetries that the neighbour condition respects.

Shifting by one keeps every pair of neighbours neighbours. If $rq - ps = 1$, then replacing $p/q$ and $r/s$ by $(p + q)/q$ and $(r + s)/s$ leaves $rq - ps$ unchanged. So the picture over $[1, 2]$, over $[2, 3]$ and over every interval between whole numbers is the picture over $[0, 1]$ moved sideways. A line down to a number above one first crosses the tall arcs over $[0, 1]$, $[1, 2]$ and so on — one for each whole number it passes — and then enters the copy of the drawn picture over its own unit interval. That is the run of right turns the descent takes first, and its length is the number’s whole part, the continued fraction’s first entry.

Turning each fraction upside down also keeps neighbours neighbours. Sending $p/q$ to $q/p$ changes $rq - ps$ to $ps - rq$, so the determinant keeps its size and changes only its sign. The map $x \mapsto 1/x$ carries the part of the tessellation above $[0, 1]$ to the part above $[1, \infty)$ and reverses left and right, so the descent to $1/x$ is the descent to $x$ with every left turn replaced by a right turn. That is the same symmetry the continued fraction has — $1/x$ is $x$’s expansion with its entries shifted along by one — seen as a reflection of the picture.

Both symmetries are transformations of the form $z \mapsto (az + b)/(cz + d)$ with whole-number entries, the shift with determinant one and the inversion with determinant minus one. They are the same kind of transformation that moves points around the sphere the complex numbers live on, restricted to the ones with whole-number entries, and the whole tessellation is what those restricted transformations do to the single arc over $[0, 1]$.

The group behind the picture #

The arcs are not arbitrary curves. In the upper half-plane with the geometry in which the shortest path between two points is a semicircle standing on the boundary — a geometry in which the parallel postulate fails — every arc of the figure is a straight line, and every curved triangle is a triangle whose three corners have gone off to the boundary.

In that geometry all the triangles are congruent. The transformations $z \mapsto (az + b)/(cz + d)$ with whole-number entries and $ad - bc = 1$ — the modular group the two matrices generate — are its rigid motions, they carry every Farey pair to another Farey pair, and they move any triangle of the tessellation onto any other. The picture looks crowded towards the number line only because the drawing is not in the geometry the picture belongs to; measured in that geometry, the triangles are identical, and a line crossing them passes through one after another at a steady rate.

Caroline Series made this reading exact in 1985: the sequence of lefts and rights a line records as it cuts through the tessellation is the continued fraction of where it is going, for every line, not only vertical ones. A line running between two points on the boundary cuts the tessellation in a sequence infinite in both directions, and the two halves are the continued fractions of its two ends.

Where the picture needs care #

The line must head to an irrational number to cross infinitely many arcs. A line down to a fraction ends at a corner of the tessellation after finitely many crossings, and its word is finite, as a fraction’s continued fraction is.

The drawing stops at a largest denominator. The tessellation has infinitely many arcs, crowding towards every fraction, and a drawing of arcs with denominators up to 13 or 24 is a finite piece. The line’s later crossings are among the arcs not drawn, and the figures compare only the runs the drawing completes.

The first run is one short. The drawing starts inside the arc over the whole unit interval, which the descent counts as its starting interval rather than as a turn. That offset is a choice of where to start, and it is the same offset that makes the descent to a number above one begin with a run of rights.

And the geometry is not the drawing’s. In the drawn picture the arcs near the line shrink and crowd; in the geometry they belong to, every triangle is the same. The figures are drawn in the ordinary plane, where the crowding is real, and the congruence of the triangles is a statement about the other geometry that the drawing cannot show.

Four lines drawn, and a symmetry the flat drawing hides #

Four lines are drawn, and a line to every number between nought and one does the same thing. The figures check the crossings, turns and runs for those four, and the statement for every number is the argument above about nested intervals, which is prose.

Nor can the pictures show the tessellation’s symmetry. A drawing that made all the triangles look alike would have to be drawn in the disc or the half-plane with its own geometry, where they are, and in that drawing the number line becomes a circle and the fractions crowd around it in a way no finite drawing resolves.

Still open: whether every denominator has a fraction with short fans #

The fans a line passes on its way to $p/q$ are the quotients of $p/q$’s continued fraction, and a fraction whose quotients are all small is one whose line never turns around the same corner for long. Stanisław Zaremba conjectured in 1971 that every whole number $q$ is the denominator of some fraction $p/q$ whose quotients are all at most 5 — that for every $q$, some line to a fraction with that denominator crosses fans of at most five triangles all the way down.

The conjecture is open. Jean Bourgain and Alex Kontorovich proved in 2014 that it holds for almost every $q$, in a precise density sense, if the bound 5 is replaced by 50, and later work has lowered that bound, but a proof for every $q$ with any fixed bound has not been found. It is a question about which paths through this picture exist, and the picture makes clear why it is hard: short fans are easy to find for most denominators, and nothing forces them to exist for all.

A construction was a picture in another geometry #

The habit is about where a construction’s natural picture lives.

The Stern–Brocot tree was built by an operation on pairs of whole numbers, drawn as a tree, rewritten as matrices and flattened into a sequence, and each of those was a faithful account of it. None of them showed why the descent’s turns are the continued fraction’s quotients; that was proved in each case by algebra. In the tessellation it is simply visible: a run is a fan, a turn is a change of corner, and a quotient is how many triangles share a corner.

The picture was available the whole time, and it lives in a geometry other than the one the numbers were written in. When a construction keeps producing identities that its own pictures have to prove, it is worth asking whether there is a space in which those identities are the shapes of things — and the matrices with determinant one were the hint that such a space existed here.