The function that sends fractions to binary

The Stern–Brocot tree between nought and one starts at $1/2$, splits each interval at its mediant, and lists every fraction once. There is another tree of exactly the same shape that nobody would call surprising: start at $1/2$ and split each interval at its midpoint. That tree lists every binary fraction — every number with a finite binary expansion — once.

Two trees of the same shape can be laid on top of each other, node on node. Doing that defines a function.

The function that matches the Stern–Brocot tree to the binary tree is continuous and increasing, and it rises from nought to one while having slope nought at almost every point. Hermann Minkowski introduced it in 1904 and wrote it $?(x)$. It looks, in the figure, like a slightly wavering version of the diagonal. What it actually is, the rest of this page measures.

Two trees laid on top of each other #

At depth one both trees have the single node $1/2$. At depth two the Stern–Brocot tree adds $1/3$ and $2/3$, the mediants of $0/1$ with $1/2$ and of $1/2$ with $1/1$; the binary tree adds $1/4$ and $3/4$. At depth three there are four new nodes in each, and so on — $2^D - 1$ nodes down to depth $D$ in both.

The function sends the $k$th Stern–Brocot node, in left-to-right order, to the $k$th binary node. So $?(1/3) = 1/4$, $?(2/3) = 3/4$, $?(1/4) = 1/8$, $?(2/5) = 3/8$. Because both trees list their nodes in increasing order, the matching preserves order, and because both sets of nodes are dense in the interval, the matching extends in exactly one way to a continuous increasing function on all of $[0, 1]$.

The figure does not compute the function by placing nodes. It computes $?(x)$ from $x$’s continued fraction by a formula, at every one of the 1,023 nodes, and requires the result to equal exactly the binary fraction in that node’s position. The formula and the positions share nothing but the node, and they agree to the last bit at all of them.

From a continued fraction to binary digits #

The formula comes from reading the descent’s word in two languages.

A number between nought and one has a continued fraction $[0; a_1, a_2, a_3, \ldots]$, and the line down to it through the Farey arcs turns left $a_1 - 1$ times, then right $a_2$ times, then left $a_3$ times, and so on. In the binary tree the same sequence of turns is a sequence of binary digits: left is a nought and right is a one. So the binary expansion of $?(x)$ is $a_1 - 1$ noughts after the point’s first one, then $a_2$ ones, then $a_3$ noughts, alternating. Written as a sum,

$$?(x) = 2\left(2^{-a_1} - 2^{-(a_1+a_2)} + 2^{-(a_1+a_2+a_3)} - \cdots\right).$$

For $1/3 = [0; 3]$ that is $2 \cdot 2^{-3} = 1/4$. For $1/2 = [0; 2]$ it is $1/2$. The function replaces a continued fraction’s quotients by run lengths of binary digits — the same information, laid out in a different base of counting.

One fraction followed both ways makes the formula concrete. $2/5 = [0; 2, 2]$, so the formula gives $2(2^{-2} - 2^{-4}) = 3/8$. In the Stern–Brocot tree, $2/5$ is reached by a left turn — its first mediant $1/2$ is too big — then a right turn, since $1/3$ is too small, and then the next mediant is $2/5$ itself. Writing left as nought and right as one, and marking the arrival with a final one, the path reads $0\,1\,1$, and $0.011$ in binary is $3/8$. In the list of the seven nodes to depth three — $1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4$ — $2/5$ is third, and $3/8$ is the third binary fraction with denominator eight. Three computations, one by the continued fraction, one by the path and one by position, give the same number.

Why it is continuous and why it never stalls #

The matching is defined only on the tree’s nodes, and the reason it extends to a continuous increasing function is a comparison of gaps.

At depth $D$, two neighbouring Stern–Brocot nodes $p/q$ and $r/s$ are $1/(qs)$ apart, and their images are neighbouring binary fractions exactly $2^{-D}$ apart. Both gaps shrink to nought as the depth grows — the binary gaps because they halve at every level, the Stern–Brocot gaps because $q$ and $s$ both grow. So between any two nodes the function has only a small range of values it could take, and that range shrinks to a point as the nodes close in: the function is continuous.

It never stalls, either. Every interval of the unit interval, however short, contains a node of the tree, and every pair of distinct nodes is sent to distinct binary fractions. So the function takes different values at any two different points, and it is strictly increasing — it never has a flat stretch of positive length, even though, as the next sections show, it is flat in a different and much stranger sense almost everywhere.

The same comparison of gaps says where the function is steep and where it is gentle. Near a fraction with a small denominator, like $1/2$, the tree’s intervals are long for their depth, so a long stretch of $x$ is squeezed into a short range of values. Deep inside a fan — near a fraction the descent reaches only after a long run of identical turns — the intervals are tiny while their images are still $2^{-D}$, and the function climbs steeply there.

Periodic in, rational out #

That reading explains the strangest property of $?$ on sight.

A number has an eventually periodic binary expansion exactly when it is a fraction. A number has an eventually periodic continued fraction exactly when it is a quadratic irrational — a root of a quadratic equation with whole-number coefficients — which is Lagrange’s theorem. Since $?$ turns quotients into runs of binary digits, it turns every quadratic irrational into a fraction, and every fraction into a binary fraction.

The two examples in the figure are the simplest. $\varphi - 1 = [0; 1, 1, 1, \ldots]$ has every run of length one, so its image is $0.101010\ldots$ in binary, which is $2/3$. $\sqrt2 - 1 = [0; 2, 2, 2, \ldots]$ has its image $0.0110\,0110\ldots$, which is $2/5$. Minkowski’s reason for defining the function was exactly this: it converts one kind of number that repeats — in its continued fraction — into another kind that repeats, in its digits.

The figures compute those two values in a way that separates the two claims inside them. A double-precision number carries only about thirty-eight of $\varphi - 1$’s quotients before they turn to noise, and reading $?$ straight off the double missed $2/3$ by $1.7 \times 10^{-12}$ — a statement about rounding rather than about $?$. So the figure checks on the doubles that the first twenty quotients are all ones or all twos, and evaluates $?$ on the exact periodic expansions, where it gives $2/3$ and $2/5$ to fifteen places.

The same graph inside itself #

The function has two symmetries, and each is a symmetry of both trees at once.

Reflecting the Stern–Brocot tree left to right sends $x$ to $1 - x$; reflecting the binary tree sends $y$ to $1 - y$. So $?(1 - x) = 1 - ?(x)$. And the left half of the Stern–Brocot tree, the part below $1/2$, is the whole tree carried by $x \mapsto x/(1 + x)$, while the left half of the binary tree is the whole tree carried by $y \mapsto y/2$. So $?(x/(1+x)) = ?(x)/2$.

The two symmetries are the tree’s two ways of being made of copies of itself, one for each tree, and $?$ is the function that turns the first kind of copying into the second. The horizontal squeeze $x \mapsto x/(1 + x)$ is not a linear map: it squeezes the part of the interval near nought much less than the part near one. The vertical squeeze is a plain halving. That mismatch — a curved copy on one side, a straight copy on the other — is what makes the graph waver instead of being a straight line.

A map of the interval turned into the tent #

The two symmetries combine into something with dynamics in it. The Farey map sends $x$ to $x/(1-x)$ on the left half of the interval and to $(1-x)/x$ on the right half: it undoes one step of the descent, sending each node of the tree to its parent. The tent map sends $y$ to $2y$ on the left half and to $2 - 2y$ on the right: it undoes one step of the binary tree.

The question-mark function turns one into the other. Applying the Farey map and then $?$ gives the same result as applying $?$ and then the tent map, which follows from the two identities checked in the figures. So every orbit of the Farey map is carried by $?$ onto an orbit of the tent map, and the tent map’s orbits are read off binary digits in the way the doubling map’s orbit is its binary expansion.

That makes $?$ a dictionary between two dynamical systems that behave, as sequences of left and right, identically — and it says something sharp about how different their measurements can be. The tent map spreads the ordinary length of the interval evenly as it runs; the Farey map, measured by ordinary length, does not. The function that matches their orbits is forced to distort length at every scale, and the next section is about how far the distortion goes.

Increasing, and flat almost everywhere #

The function is continuous and increasing, so it is differentiable at almost every point — every increasing function is. Raphaël Salem proved in 1943 that at almost every point its derivative is nought. A function that rises from nought to one doing all of its rising where its slope is not nought does all of it on a set of total length nought.

That is the kind of object that a lopsided mass was: a measure spread over the whole interval, in the sense that no subinterval gets nothing, and concentrated on almost none of it. The rise of $?$ over an interval is exactly such a measure, and the figure measures its concentration directly.

The pieces at depth $d$ are the intervals between neighbouring nodes, of length $1/(qs)$ for neighbours $p/q$ and $r/s$, and the figure checks that their lengths add to one. Every piece carries the same rise, but their lengths are wildly unequal — the pieces near fractions with small denominators are long, and the pieces deep inside fans of long runs are very short. Half the rise sits on the short pieces, and the short pieces get shorter faster than they get more numerous.

The fall is slow, and a picture drawn at any depth still shows a function that seems to have slopes everywhere. That is the honest limit of the evidence: the figure shows the half-rise length falling across fifteen levels of the tree, and the theorem that it tends to nought — which is what singularity means — is Salem’s.

Why the slope is nought #

The reason has a rough form that explains which numbers are flat and which are steep.

Around a typical number, the interval the descent confines it to after $n$ quotients has length roughly $1/q_n^2$, where $q_n$ is the $n$th convergent’s denominator, and Paul Lévy showed that $q_n$ grows geometrically for almost every number — its $n$th root settles at a fixed constant. So the interval shrinks exponentially in $n$. The rise of $?$ over that interval is $2^{-(a_1 + \cdots + a_n)}$, and for almost every number the quotients have no finite average: large quotients keep appearing often enough that $a_1 + \cdots + a_n$ grows faster than any multiple of $n$. The rise shrinks faster than any exponential in $n$ while the interval shrinks only exponentially, so the slope over those intervals falls to nought.

The numbers where $?$ is steep are the ones whose quotients stay small — $\varphi - 1$, with every quotient one, is the steepest kind. Those are exactly the badly approximable numbers, the ones the descent approaches slowly, and they form a set of length nought. $?$ rises where approximation is hard and stays flat where it is easy, and since almost every number has occasional huge quotients, almost everywhere is flat.

That is also the contrast with a curve with a corner at every point. Weierstrass’s function has no slope anywhere; $?$ has a slope almost everywhere, and the slope is nought. Both are continuous, both are built from a self-similar rule, and they fail to be ordinary in opposite directions.

Where it needs care #

The function is defined on the unit interval. It extends to all the reals by the same matching applied to the whole Stern–Brocot tree, and the extension is also increasing and singular; the figures draw only $[0, 1]$.

The graph is drawn from the tree’s nodes. The polyline passes through the 1,025 points at depth ten and the two ends, and between them the true function wavers in ways the line does not show. Its monotonicity is checked separately, at 400 real numbers sampled independently of the tree.

Almost everywhere is a statement about length. The derivative is not nought at every point — at points like $\varphi - 1$ the difference quotients grow without bound — and the set of such points, while it has length nought, is uncountable and dense.

And the concentration figures are finite. They show the half-rise length falling across the depths drawn; that it tends to nought is the theorem, not the measurement.

The flatness is finer than any drawing #

The flatness cannot be seen. At the resolution of any drawing the graph of $?$ looks like a wavering diagonal with slopes everywhere, because the intervals on which it is flat are interleaved with the ones on which it rises at every scale down to the pixel. The half-rise measurement is the nearest a figure can come to showing the set where the rise happens: it cannot draw that set, but it can say how little room the rise is squeezed into.

Nor do the pictures show the matching of the two trees. The graph is the result of the matching, and the trees themselves — the Stern–Brocot tree and the binary tree — are drawn elsewhere or not at all.

Still open: a closed form for how thin the rise is #

The rise of $?$ is a measure on the interval that lives on a set of length nought, and the natural question about such a measure is its dimension — how many boxes of size $\varepsilon$ its mass essentially needs, in the sense of the dimension of a measure rather than of a set. John Kinney showed in 1960 that the answer is strictly less than one, and it has since been computed numerically to be about $0.875$.

No closed form for that number is known. It is determined by the growth of continued-fraction quotients against the halving of the binary tree, and it can be written as a ratio of two integrals involving the distribution of quotients, but no expression for it in terms of familiar constants has been found, and none is known to exist. The measure is completely explicit and its most basic numerical invariant is known only by computation.

Matching two things of the same shape #

The habit is about what a correspondence between shapes can carry.

The Stern–Brocot tree and the binary tree were built for different purposes — one to list fractions, the other to list binary numbers — and they turn out to be the same tree with different labels. Matching the labels node for node produces a function, and the function inherits everything each labelling knew: from the binary side, that repeating digits mean a fraction; from the continued-fraction side, that repeating quotients mean a quadratic irrational. The function’s surprising properties were not added; they were already present in the two labellings, and the matching lined them up.

When two structures have the same shape, the map between their labels is worth constructing even when it looks like a formality. It is a dictionary between two ways of describing the same thing, and a dictionary between languages is where a statement that is hard in one becomes obvious in the other.