Stern–Brocot Tree: listing fractions, simplest between, best approximations

Comparing fractions

It’s easy to compare whole numbers: \(25 < 47\). For negatives: \(-47 < -25\).

For fractions it’s easy when they have the same denominator or the same numerator, but what about \(\tfrac{3}{7}\) and \(\tfrac{4}{9}\)? Use cross-multiplication: \[ 3\cdot 9 = 27 \quad\text{and}\quad 4\cdot 7 = 28, \] so \(\tfrac{3}{7} < \tfrac{4}{9}\). Another example: compare \(\tfrac{5}{6}\) and \(\tfrac{4}{5}\): \[ 5\cdot 5 = 25 \quad\text{and}\quad 4\cdot 6 = 24, \] so \(\tfrac{4}{5} < \tfrac{5}{6}\).

Three problems (small denominators)

Once we know how to compare fractions we can arrange them on the number line. For whole numbers we place 0 and then keep adding 1. But for fractions there is no single fraction “just after 0”.

Example: \(\tfrac{13}{20} < \tfrac{31}{47}\). Using decimals, \(\tfrac{13}{20}=0.65\) and \(\tfrac{31}{47}\approx 0.6595\ldots\). One might try \(0.655=\tfrac{655}{1000}=\tfrac{131}{200}\), but there are simpler/better options.

Problem 3: best rational approximations

Some fractions have denominators that are larger than necessary. For example, to approximate \(\pi = 3.141592653589793\ldots\), one could use \(3.1415=\tfrac{31415}{10000}=\tfrac{6283}{2000}\), giving an error about \(0.00009265\ldots\).

Now consider \(\tfrac{355}{113}\). The difference \(\tfrac{355}{113}-\pi\) is about \(0.00000026\ldots\). This is impressive—how do we find it?

The Stern–Brocot tree

We are going to solve all three problems using the Stern–Brocot tree.

We first draw a picture of another math object called a binary tree: start with a root, then branch left (L) and right (R), continuing level by level. There are \(2^n\) nodes at level \(n\).

Imagine a number line at the bottom of the tree; drop a vertical line from each node to the number line. A key point is that the number associated to a node is less than any number obtained later after a right turn, and greater than any number coming from a left turn.

Encoding by L/R moves; Farey addition

Note that any number on the number line is described by a list of L’s and R’s. We will use exponents for repeated L’s or R’s (blocks).

If we can place all the fractions without repetition on the tree, we have solved Problem 1; we can go down levels starting at the top.

This is based on an operation called Farey addition: if \(\tfrac{a}{b}\) and \(\tfrac{c}{d}\) are in lowest terms, define \[ \frac{a}{b} \oplus \frac{c}{d} = \frac{a+c}{b+d}. \] Example: \(\tfrac{3}{5} \oplus \tfrac{7}{2} = \tfrac{10}{7}\).

Parent and nearest distant ancestor (NDA)

Note: \(\oplus\) can be misleading if fractions are not in lowest terms (the notes give examples).

To populate the tree we discuss the parent and the nearest distant ancestor (NDA) of a node.

• The parent is the node directly before (in the L/R description).
• To find the NDA: drop the last block of the same letter, then drop one more letter.

Example rule from the notes (using blocks like \(R^2L^3R^2\)): parent is obtained by dropping the last letter; NDA is obtained by dropping the last block and then one more letter.

We also use two extra nodes above the tree, one on its left and one on its right, to do Farey addition at the root.

Facts about Farey addition and the SB tree

For all other nodes, do: parent \(\oplus\) NDA.

Fact. By placing fractions on the Stern–Brocot tree as in the notes, we get all fractions with no repetitions, and the fractions are always in lowest terms. So we can list fractions: \[ 1,\ \frac{1}{2},\ 2,\ \frac{1}{3},\ \frac{2}{3},\ \frac{3}{2},\ \ldots \]

Facts about \(\oplus\):

1. \(\tfrac{a}{b} \oplus \tfrac{c}{d}\) is always in lowest terms (under the hypotheses in the notes).
2. \(\tfrac{a}{b} \oplus \tfrac{c}{d}\) is always between \(\tfrac{a}{b}\) and \(\tfrac{c}{d}\): \[ \frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}. \]
3. If \(\tfrac{a}{b}\) is the parent or NDA of \(\tfrac{c}{d}\), then \[ \left|\frac{a}{b} - \frac{c}{d}\right| = \frac{1}{bd}. \]