janmr blog

The Stern-Brocot Tree of Fractions

Consider two fractions m1n1\frac{m_1}{n_1} and m2n2\frac{m_2}{n_2} with positive numerators and denominators. The fraction m1+m2n1+n2\frac{m_1+m_2}{n_1+n_2} is called the mediant of m1n1\frac{m_1}{n_1} and m2n2\frac{m_2}{n_2}. It is straightforward to show that the mediant is placed numerically between the original fractions,

(1)
m1n1<m2n2m1n1<m1+m2n1+n2<m2n2.\frac{m_1}{n_1} < \frac{m_2}{n_2} \quad \Rightarrow \quad \frac{m_1}{n_1} < \frac{m_1+m_2}{n_1+n_2} < \frac{m_2}{n_2}.

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

(2)
01,10.\frac{0}{1}, \frac{1}{0}.

(If you don't like calling 10\frac{1}{0} a fraction just consider tuples of integers instead, where inequality (m1,n1)<(m2,n2)(m_1,n_1) < (m_2,n_2), for instance, means m1n2<m2n1m_1 n_2 < m_2 n_1. However, 10\frac{1}{0} is just an auxiliary fraction that makes everything simpler.) Insert now the mediant in between the two,

(3)
01,11,10.\frac{0}{1}, \frac{\mathbf{1}}{\mathbf{1}}, \frac{1}{0}.

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

(4)
01,12,11,21,10,\frac{0}{1}, \frac{\mathbf{1}}{\mathbf{2}}, \frac{1}{1}, \frac{\mathbf{2}}{\mathbf{1}}, \frac{1}{0},
(5)
01,13,12,23,11,32,21,31,10,\frac{0}{1}, \frac{\mathbf{1}}{\mathbf{3}}, \frac{1}{2}, \frac{\mathbf{2}}{\mathbf{3}}, \frac{1}{1}, \frac{\mathbf{3}}{\mathbf{2}}, \frac{2}{1}, \frac{\mathbf{3}}{\mathbf{1}}, \frac{1}{0},

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 2×22 \times 2 matrices with non-negative integers as elements. The initial two fractions from (2) will be represented by

(6)
I=[1001],I=\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix},

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 2×22 \times 2 matrix,

f([m2m1n2n1])=m2+m1n2+n1,f \left( \begin{bmatrix} m_2 & m_1 \\ n_2 & n_1 \end{bmatrix} \right) = \frac{m_2+m_1}{n_2+n_1},

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 f(I)=11f(I) = \frac{1}{1}, leading to (3).

We now introduce

(7)
L=[1011],so[m2m1n2n1]L=[m2+m1m1n2+n1n1]andR=[1101],so[m2m1n2n1]R=[m2m2+m1n2n2+n1].\begin{aligned} L=\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}, \quad \text{so} \quad &\begin{bmatrix} m_2 & m_1 \\ n_2 & n_1 \end{bmatrix} L = \begin{bmatrix} m_2+m_1 & m_1 \\ n_2+n_1 & n_1 \end{bmatrix} \quad \text{and} \\ R=\begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix}, \quad \text{so} \quad &\begin{bmatrix} m_2 & m_1 \\ n_2 & n_1 \end{bmatrix} R = \begin{bmatrix} m_2 & m_2+m_1 \\ n_2 & n_2+n_1 \end{bmatrix}. \end{aligned}

Notice how (right-)multiplication of both LL and RR 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 f(L)=12f(L) = \frac{1}{2} and f(R)=21f(R) = \frac{2}{1} are the left- and rightmost of the newly inserted fractions in (4), respectively. Similarly, f(L2)=13f(L^2) = \frac{1}{3}, f(LR)=23f(L R) = \frac{2}{3}, f(RL)=32f(R L) = \frac{3}{2}, f(R2)=31f(R^2) = \frac{3}{1} are the inserted fractions in (5).

This process is easily generalized:

Definition 1. The Stern-Brocot tree is equal to T(I)T(I), where T(M)T(M) is a binary tree with root f(M)f(M), left subtree T(ML)T(M L), and right subtree T(MR)T(M R).

So the root of the Stern-Brocot tree is f(I)=11f(I)=\frac{1}{1} with T(L)T(L) and T(R)T(R) as left and right subtree, respectively. T(L)T(L) has root f(L)=12f(L)=\frac{1}{2}, left subtree T(L2)T(L^2) and right subtree T(LR)T(L R). T(R)T(R) has root f(R)=21f(R)=\frac{2}{1}, left subtree T(RL)T(R L) and right subtree T(R2)T(R^2). 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 T(M)T(M) of the Stern-Brocot tree with root f(M)f(M). Note that it follows from the definitions that every node in the left subtree T(ML)T(M L) is strictly less than f(M)f(M) and that every node in the right subtree T(MR)T(M R) is strictly greater than f(M)f(M). Thus, the Stern-Brocot tree is a binary search tree, although an infinite one.

From the definition we see that for any node f(M)f(M) of the Stern-Brocot tree we have

(8)
M=Ra0La1Ra2La3Lan1,M=R^{a_0} L^{a_1} R^{a_2} L^{a_3} \cdots L^{a_{n-1}},

for even nn and non-negative integers aka_k. Insisting that nn must be even is just a technicality which will be clarified later. Any aka_k can be zero so its not a restriction. Computing the determinants of the simple matrices in (6) and (7) we get detI=detL=detR=1\det I = \det L = \det R = 1. Since det(AB)=detAdetB\det (A B) = \det A \, \det B it follows that

(9)
detM=1 for any subtree T(M) of the Stern-Brocot tree.\det M = 1 \text{ for any subtree } T(M) \text{ of the Stern-Brocot tree.}

This is an important property. Consider any node mn\frac{m}{n} of the tree. Then the left subtree is T(M)T(M') with

M=[mmnn]M' = \begin{bmatrix} m' & m \\ n' & n \end{bmatrix}

for some integers mm' and nn'. But then mnmn=1m' n - m n' = 1 from (9), which shows that mm and nn are relatively prime, mnm \perp n. 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 pq\frac{p}{q} with pqp \perp q 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 n=0,1,n=0, 1, \ldots, where the aka_k's are determined from the number of left and right branches chosen during the search. Let one of the matrices be

M=[m2m1n2n1] where m1n1<pq<m2n2.M = \begin{bmatrix} m_2 & m_1 \\ n_2 & n_1 \end{bmatrix} \text{ where } \frac{m_1}{n_1} < \frac{p}{q} < \frac{m_2}{n_2}.

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

pn1qm11 and qm2pn21p n_1 - q m_1 \geq 1 \text{ and } q m_2 - p n_2 \geq 1

and we know from (9) that n1m2m1n2=1n_1 m_2 - m_1 n_2 = 1. We now get

p+q=p(n1m2m1n2)+q(n1m2m1n2)=(m1+n1)(qm2pn2)+(m2+n2)(pn1qm1)m1+n1+m2+n2.\begin{aligned} p + q &= p (n_1 m_2 - m_1 n_2) + q (n_1 m_2 - m_1 n_2) \\ &= (m_1 + n_1) (q m_2 - p n_2) + (m_2 + n_2) (p n_1 - q m_1) \\ &\geq m_1 + n_1 + m_2 + n_2. \end{aligned}

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 LL or RR. 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

PLa=[0110][10a1]=[a110],RaP=[1a01][0110]=[a110],\begin{aligned} P L^a &= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 \\ a & 1 \end{bmatrix} = \begin{bmatrix} a & 1 \\ 1 & 0 \end{bmatrix}, \\ R^a P &= \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} a & 1 \\ 1 & 0 \end{bmatrix}, \end{aligned}

where PP is a permutation matrix for which P2=IP^2 = I. Recall that any node in the Stern-Brocot is of the form f(M)f(M) where MM is as in (8). Using the identities above we get

M=Ra0La1Ra2La3Lan1=(Ra0P)(PLa1)(Ra2P)(PLa3)(Ran2P)(PLan1)=[a0110][a1110][an1110]=[Kn(a0,,an1)Kn1(a0,,an2)Kn1(a1,,an1)Kn2(a1,,an2)]\begin{aligned} M &= R^{a_0} L^{a_1} R^{a_2} L^{a_3} \cdots L^{a_{n-1}} \\ &= (R^{a_0} P) (P L^{a_1}) (R^{a_2} P) (P L^{a_3}) \cdots (R^{a_{n-2}} P) (P L^{a_{n-1}}) \\ &= \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} a_1 & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} a_{n-1} & 1 \\ 1 & 0 \end{bmatrix} \\ &= \begin{bmatrix} K_n(a_0, \ldots, a_{n-1}) & K_{n-1}(a_0, \ldots, a_{n-2}) \\ K_{n-1}(a_1, \ldots, a_{n-1}) & K_{n-2}(a_1, \ldots, a_{n-2}) \end{bmatrix} \end{aligned}

where we assume that n2n \geq 2 is even. The KnK_n functions are so-called continuants. We now have

f(M)=f(Ra0La1Ra2La3Lan1)=f([Kn(a0,,an1)Kn1(a0,,an2)Kn1(a1,,an1)Kn2(a1,,an2)])=Kn(a0,,an1)+Kn1(a0,,an2)Kn1(a1,,an1)+Kn2(a1,,an2)=Kn(a0,,an1,1)Kn1(a1,,an1,1)=a0+/ ⁣/a1,,an1,1/ ⁣/.\begin{aligned} f(M) &= f(R^{a_0} L^{a_1} R^{a_2} L^{a_3} \cdots L^{a_{n-1}}) \\ &= f \left( \begin{bmatrix} K_n(a_0, \ldots, a_{n-1}) & K_{n-1}(a_0, \ldots, a_{n-2}) \\ K_{n-1}(a_1, \ldots, a_{n-1}) & K_{n-2}(a_1, \ldots, a_{n-2}) \end{bmatrix} \right) \\ &= \frac{K_n(a_0, \ldots, a_{n-1}) + K_{n-1}(a_0, \ldots, a_{n-2})}{K_{n-1}(a_1, \ldots, a_{n-1}) + K_{n-2}(a_1, \ldots, a_{n-2})} \\ &= \frac{K_n(a_0, \ldots, a_{n-1}, 1)}{K_{n-1}(a_1, \ldots, a_{n-1}, 1)} \\ &= a_0 + /\!/ a_1, \ldots, a_{n-1}, 1 /\!/. \end{aligned}

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 a0+/ ⁣/a1,,an1,1/ ⁣/a_0 + /\!/ a_1, \ldots, a_{n-1}, 1 /\!/ can be found in the tree by starting at the root 11\frac{1}{1} and then taking a0a_0 right branches, a1a_1 left branches, a2a_2 right branches, and so on, until taking an1a_{n-1} left branches. What if an1=0a_{n-1} = 0 for even n2n \geq 2? We have

a0+/ ⁣/a1,,an2,0,1/ ⁣/=a0+/ ⁣/a1,,an2,1/ ⁣/,a_0 + /\!/ a_1, \ldots, a_{n-2}, 0, 1 /\!/ = a_0 + /\!/ a_1, \ldots, a_{n-2}, 1 /\!/,

so a trailing / ⁣/,0,1/ ⁣//\!/ \ldots, 0, 1 /\!/ can be simplified to / ⁣/,1/ ⁣//\!/ \ldots, 1 /\!/. So all cases are captured in

f(Ra0La1Ra2La3Ran2Lan1)=a0+/ ⁣/a1,,an2,an1,1/ ⁣/,f(Ra0La1Ra2La3Ran2)=a0+/ ⁣/a1,,an2,1/ ⁣/,\begin{aligned} f(R^{a_0} L^{a_1} R^{a_2} L^{a_3} \cdots R^{a_{n-2}} L^{a_{n-1}}) &= a_0 + /\!/ a_1, \ldots, a_{n-2}, a_{n-1}, 1 /\!/, \\ f(R^{a_0} L^{a_1} R^{a_2} L^{a_3} \cdots R^{a_{n-2}}) &= a_0 + /\!/ a_1, \ldots, a_{n-2}, 1 /\!/, \end{aligned}

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

For instance, 75=1+/ ⁣/2,2/ ⁣/=1+/ ⁣/2,1,1/ ⁣/\frac{7}{5} = 1 + /\!/ 2, 2 /\!/ = 1 + /\!/ 2, 1, 1 /\!/, so 75\frac{7}{5} 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 14\frac{1}{4} 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 14=0+/ ⁣/3,1/ ⁣/=/ ⁣/4/ ⁣/\frac{1}{4} = 0 + /\!/ 3, 1 /\!/ = /\!/ 4 /\!/.

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.

Commenting is not possible for this post, but feel free to leave a question, correction or any comment by using the contact page