Fairy Lights on the Farey Tree

Fairy Lights on the Farey Tree. Parity types are coloured as follows: Even: Blue; Odd: Green; None: Red.

The rational numbers ${\mathbb{Q}}$ are dense in the real numbers ${\mathbb{R}}$ . The cardinality of rational numbers in the interval ${(0,1)}$ is ${\boldsymbol{\aleph}_0}$ . We cannot list them in ascending order, because there is no least rational number greater than ${0}$ .

However, there are several ways of enumerating the rational numbers. The best-known are

The Calkin-Wilf Tree
The Stern Brocot Tree
The Farey sequences.

Fig. 1. Structures of the CW Tree (left) and SB Tree (right).

In Fig. 1 we show the first two of these enumerations. For the Calkin-Wilf Tree (left panel), we start with ${\frac{1}{2}}$ . Then, each number branches to two “children”. Below the rational number ${p/q}$ we have ${p/(p+q)}$ and ${(p+q)/q}$ . The mnemonic for this is: The children are “top over sum” and “sum over bottom”.

The Calkin-Wilf Tree has the structure of a pure binary tree. The Stern-Brocot tree (right panel) differs from this: each number has two “parents” and is formed as the mediant: the parents ${p_1/q_1}$ and ${p_2/q_2}$ produce ${(p_1+p_2)/(q_1+q_2)}$ .

The Farey Sequences

The Farey sequence of order ${n}$ is the sequence of (reduced) fractions between ${0}$ and ${1}$ which have denominators less than or equal to ${n}$ , arranged in order of increasing size. Each Farey sequence starts with the value ${0}$ or ${\frac{0}{1}}$ and ends with the value ${1}$ or ${\frac{1}{1}}$ . Thus, the eighth Farey Sequence is

$\displaystyle F_8 = \biggl\{ \frac{0}{1}, \frac{1}{8}, \frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{2}{7}, \frac{1}{3}, \frac{3}{8}, \frac{2}{5}, \frac{3}{7}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{5}{8}, \frac{2}{3}, \frac{5}{7}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \frac{7}{8}, \frac{1}{1} \biggr\}$

A table of all the sequences up to order eight is shown here:

$\displaystyle \begin{array}{ccccccccccccccccccccccccc} \phantom{\biggl[} F_1 = \bigl\{ & \frac{0}{1} & & & & & & & & & & & & & & & & & & & & & & \frac{1}{1} & \bigr\} \\ \phantom{\biggl[} F_2 = \bigl\{ & \frac{0}{1} & & & & & & & & & & & \frac{1}{2} & & & & & & & & & & & \frac{1}{1} & \bigr\} \\ \phantom{\biggl[} F_3 = \bigl\{ & \frac{0}{1} & & & & & & & \frac{1}{3} & & & & \frac{1}{2} & & & & \frac{2}{3} & & & & & & & \frac{1}{1} & \bigr\} \\ \phantom{\biggl[} F_4 = \bigl\{ & \frac{0}{1} & & & & & \frac{1}{4} & & \frac{1}{3} & & & & \frac{1}{2} & & & & \frac{2}{3} & & \frac{3}{4} & & & & & \frac{1}{1} & \bigr\} \\ \phantom{\biggl[} F_5 = \bigl\{ & \frac{0}{1} & & & & \frac{1}{5} & \frac{1}{4} & & \frac{1}{3} & & \frac{2}{5} & & \frac{1}{2} & & \frac{3}{5} & & \frac{2}{3} & & \frac{3}{4} & \frac{4}{5} & & & & \frac{1}{1} & \bigr\} \\ \phantom{\biggl[} F_6 = \bigl\{ & \frac{0}{1} & & & \frac{1}{6} & \frac{1}{5} & \frac{1}{4} & & \frac{1}{3} & & \frac{2}{5} & & \frac{1}{2} & & \frac{3}{5} & & \frac{2}{3} & & \frac{3}{4} & \frac{4}{5} & \frac{5}{6} & & & \frac{1}{1} & \bigr\} \\ \phantom{\biggl[} F_7 = \bigl\{ & \frac{0}{1} & & \frac{1}{7} & \frac{1}{6} & \frac{1}{5} & \frac{1}{4} & \frac{2}{7} & \frac{1}{3} & & \frac{2}{5} & \frac{3}{7} & \frac{1}{2} & \frac{4}{7} & \frac{3}{5} & & \frac{2}{3} & \frac{5}{7} & \frac{3}{4} & \frac{4}{5} & \frac{5}{6} & \frac{6}{7} & & \frac{1}{1} & \bigr\} \\ \phantom{\biggl[} F_8 = \bigl\{ & \frac{0}{1} & \frac{1}{8} & \frac{1}{7} & \frac{1}{6} & \frac{1}{5} & \frac{1}{4} & \frac{2}{7} & \frac{1}{3} & \frac{3}{8} & \frac{2}{5} & \frac{3}{7} & \frac{1}{2} & \frac{4}{7} & \frac{3}{5} & \frac{5}{8} & \frac{2}{3} & \frac{5}{7} & \frac{3}{4} & \frac{4}{5} & \frac{5}{6} & \frac{6}{7} & \frac{7}{8} & \frac{1}{1} & \bigr\} \end{array}$

Farey sequences of orders 1 to 8, arranged to show new entries at each stage.

The numbers in this table are arranged to show, at the top of each column, the new rationals entering at each stage. John Farey speculated, in 1816, that each new entry is the mediant of its neighbours.

The Fairy Lights

We now eliminate from each row, any entry that has already appeared above it:

$\displaystyle \begin{array}{ccccccccccccccccccccccccc} \bigl\{ & \frac{0}{1} & & & & & & & & & & & & & & & & & & & & & & \frac{1}{1} & \bigr\} \\ \bigl\{ & & & & & & & & & & & & \frac{1}{2} & & & & & & & & & & & & \bigr\} \\ \bigl\{ & & & & & & & & \frac{1}{3} & & & & & & & & \frac{2}{3} & & & & & & & & \bigr\} \\ \bigl\{ & & & & & & \frac{1}{4} & & & & & & & & & & & & \frac{3}{4} & & & & & & \bigr\} \\ \bigl\{ & & & & & \frac{1}{5} & & & & & \frac{2}{5} & & & & \frac{3}{5} & & & & & \frac{4}{5} & & & & & \bigr\} \\ \bigl\{ & & & & \frac{1}{6} & & & & & & & & & & & & & & & & \frac{5}{6} & & & & \bigr\} \\ \bigl\{ & & & \frac{1}{7} & & & & \frac{2}{7} & & & & \frac{3}{7} & & \frac{4}{7} & & & & \frac{5}{7} & & & & \frac{6}{7} & & & \bigr\} \\ \bigl\{ & & \frac{1}{8} & & & & & & & \frac{3}{8} & & & & & & \frac{5}{8} & & & & & & & \frac{7}{8} & & \bigr\} \end{array}$

In an earlier post we showed how there are three parity classes for the rational numbers:

$\displaystyle \mbox{Odd} = \frac{o}{o} \qquad \mbox{Even} = \frac{e}{o} \qquad \mbox{None} = \frac{o}{e} \qquad$

where ${o}$ and ${e}$ represent arbitrary odd and even integers. Replacing each entry by its parity, odd, even or none, now denoted by ${o}$ , ${e}$ and ${n}$ , we obtain the following tree:

$\displaystyle \begin{array}{ccccccccccccccccccccccccc} \bigl\{ & e & & & & & & & & & & & & & & & & & & & & & & o & \bigr\} \\ \bigl\{ & & & & & & & & & & & & n & & & & & & & & & & & & \bigr\} \\ \bigl\{ & & & & & & & & o & & & & & & & & e & & & & & & & & \bigr\} \\ \bigl\{ & & & & & & n & & & & & & & & & & & & n & & & & & & \bigr\} \\ \bigl\{ & & & & & o & & & & & e & & & & o & & & & & e & & & & & \bigr\} \\ \bigl\{ & & & & n & & & & & & & & & & & & & & & & n & & & & \bigr\} \\ \bigl\{ & & & o & & & & e & & & & o & & e & & & & o & & & & e & & & \bigr\} \\ \bigl\{ & & n & & & & & & & n & & & & & & n & & & & & & & n & & \bigr\} \end{array}$

It appears that the three parity types occur with about the same frequency. Indeed, counting the proportions for increading values of the denominators, we find that they all tend to the limit ${\frac{1}{3}}$ . This is shown in the Figure below:

Parity ratio ${r}$ for rationals ${m/n}$ of parity even (solid blue), odd (dashed red) and none (dotted black) for ${n\le n_{\mathrm{max}}=20}$ .

The pattern of parities in the Farey Tree are seen by colouring the three types as follows: Even ${\rightarrow}$ Blue; Odd ${\rightarrow}$ Green; None ${\rightarrow}$ Red. This is shown in the Figure at the head of this post.

The Farey sequences are closely related to the Stern-Brocot Tree and the Calkin-Wilf Tree, discussed in earlier posts to this blog. In Chapter 3 of An Introduction to the Theory of Numbers, Hardy and Wright give a short account of the curious history of Farey Sequences. John Farey stated the key properties without proving them. Cauchy provided proofs and ascribed the credit to Farey. But the theorems had been stated and proved much earlier by Haros (Hardy and Wright, p. 36).

Sources

${\bullet}$ Hardy, Godfrey Harold and Wright, E. M. (1960): An Introduction to the Theory of Numbers (Fourth Ed.), Oxford, at the Clarendon Press.

${\bullet}$ Wikipedia article Farey Sequences: \url{http://www.wikipedia.org/}

ThatsMaths