janmr blog

The Stern-Brocot Tree of Fractions

Consider two fractions and with positive numerators and denominators. The fraction is called the mediant of and . It is straightforward to show that the mediant is placed numerically between the original fractions,

(1)

Consider now the following simple procedure. Start with the two fractions,

(2)

(If you don't like calling a fraction just consider tuples of integers instead, where inequality , for instance, means . However, is just an auxiliary fraction that makes everything simpler.) Insert now the mediant in between the two,

(3)

and repeat the process, inserting mediants between any two consequtive fractions, obtaining

(4)

(5)

and so on. At any stage of the process we see that the values of the fractions strictly increase going from left to right, because of (1).

The Stern-Brocot Tree

A lot more can be said about these sequences, but first we arrange the fractions in the so-called Stern-Brocot tree. To simplify the definition and the properties of this structure, we use matrices with non-negative integers as elements. The initial two fractions from (2) will be represented by

(6)

where the numerators and denominators are in the first and second row, respectively. For technical reasons we will always have the larger fraction in the first column and the smaller fraction in the second column. We can now associate a fraction to any matrix,

which is seen to be the mediant of the two fractions represented by the columns of the matrix. So the first mediant we inserted was , leading to (3).

We now introduce

(7)

Notice how (right-)multiplication of both and preserves the fact that the fraction represented by the first column is greater than the fraction represented by the second column. This follows from (1). Notice also how and are the left- and rightmost of the newly inserted fractions in (4), respectively. Similarly, , , , are the inserted fractions in (5).

This process is easily generalized:

Definition 1. The Stern-Brocot tree is equal to , where is a binary tree with root , left subtree , and right subtree .

So the root of the Stern-Brocot tree is with and as left and right subtree, respectively. has root , left subtree and right subtree . has root , left subtree and right subtree . And so on. The top of the tree can be seen in Figure 1.

The Stern-Brocot tree
Figure 1. The Stern-Brocot tree.

Consider any subtree of the Stern-Brocot tree with root . Note that it follows from the definitions that every node in the left subtree is strictly less than and that every node in the right subtree is strictly greater than . Thus, the Stern-Brocot tree is a binary search tree, although an infinite one.

From the definition we see that for any node of the Stern-Brocot tree we have

(8)

for even and non-negative integers . Insisting that must be even is just a technicality which will be clarified later. Any can be zero so its not a restriction. Computing the determinants of the simple matrices in (6) and (7) we get . Since it follows that

(9)

This is an important property. Consider any node of the tree. Then the left subtree is with

for some integers and . But then from (9), which shows that and are relatively prime, . Or, to put it another way, every fraction in the Stern-Brocot tree is in its lowest terms.

A natural question is now: Can any reduced positive fraction be found in the Stern-Brocot tree? Assume there is a fraction with which is not present. Consider now the process of searching for this fraction. This will produce an infinite sequence of matrices of the form (8) for , where the 's are determined from the number of left and right branches chosen during the search. Let one of the matrices be

The inequalities follow from the properties of the Stern-Brocot tree and the search process being performed. They imply that

and we know from (9) that . We now get

This inequality must hold for the infinite sequence of matrices from the search process. This is not possible since the sum of the elements of any matrix of the form (8) strictly increases when multiplied by or . So the Stern-Brocot tree contains all reduced positive fractions.

Relation to Continued Fractions

The Stern-Brocot tree is intimately tied to continued fractions. See the article Continued Fractions and Continuants for some basic properties that we will use below. Especially equations (8) and (10) from that article are essential to the following. Observe that

where is a permutation matrix for which . Recall that any node in the Stern-Brocot is of the form where is as in (8). Using the identities above we get

where we assume that is even. The functions are so-called continuants. We now have

This is a truly remarkable result. There is a one-to-one correspondance between continued fractions and nodes in the Stern-Brocot tree. Indeed, the continued fraction can be found in the tree by starting at the root and then taking right branches, left branches, right branches, and so on, until taking left branches. What if for even ? We have

so a trailing can be simplified to . So all cases are captured in

for even , linking any node from the Stern-Brocot tree to a continued fraction and vice versa.

For instance, , so can be found in the Stern-Brocot tree by going right one time from the root, then 2 times to the left, and finally 1 time to the right. Check Figure 1 to verify. Similarly, we see that is located by going 3 times to the left from the root. What is its continued fraction representation? Since we must start by counting right we rephrase its location to: Go 0 times to the right and then 3 times to the left. This gives us .

Further Reading

The Stern-Brocot tree is mentioned in Exercise 4.5.3-(40) of The Art of Computer Programming, Volume 2, by Donald E. Knuth and treated in more detail in Section 4.5 of Concrete Mathematics by Graham, Knuth, and Patashnik.