Listing the Rational Numbers: I. Farey Sequences

We know, thanks to Georg Cantor, that the rational numbers — ratios of integers — are countable: they can be put into one-to-one correspondence with the natural numbers.

Rational-Numbers-Small

How can we make a list that includes all rationals? For the present, let us consider rationals in the interval ${[0,1]}$ . It would be nice if we could list all these rationals in order from smallest to largest. But for any rational ${r\in(0,1)}$ we have ${\textstyle{\frac{1}{2}}r < r}$ ; there is no smallest such rational. Indeed, the rationals are dense in ${\mathbb{R}}$ . Between any two rationals lies another, and the closure of the set of rationals is ${\mathbb{R}}$ .

Following Cantor

One method of listing all rationals in the interval ${[0,1]}$ is to follow the example of Cantor. We write a 2-dimensional array, with all rationals having equal denominators in a single row.

$\displaystyle \begin{array}{rcl} \qquad &&\frac{0}{0} \\ \\ &&\frac{0}{1}\qquad\frac{1}{1} \\ \\ &&\frac{0}{2}\qquad\frac{1}{2}\qquad\frac{2}{2} \\ \\ &&\frac{0}{3}\qquad\frac{1}{3}\qquad\frac{2}{3}\qquad\frac{3}{3} \\ \\ &&\frac{0}{4}\qquad\frac{1}{4}\qquad\frac{2}{4}\qquad\frac{3}{4}\qquad\frac{4}{4} \\ \\ &&\frac{0}{5}\qquad\frac{1}{5}\qquad\frac{2}{5}\qquad\frac{3}{5}\qquad\frac{4}{5}\qquad\frac{5}{5} \\ \\ &&\frac{0}{6}\qquad\frac{1}{6}\qquad\frac{2}{6}\qquad\frac{3}{6}\qquad\frac{4}{6}\qquad\frac{5}{6}\qquad\frac{6}{6} \\ \\ &&\frac{0}{7}\qquad\frac{1}{7}\qquad\frac{2}{7}\qquad\frac{3}{7}\qquad\frac{4}{7}\qquad\frac{5}{7}\qquad\frac{6}{7}\qquad\frac{7}{7} \\ \\ &&\frac{0}{8}\qquad\frac{1}{8}\qquad\frac{2}{8}\qquad\frac{3}{8}\qquad\frac{4}{8}\qquad\frac{5}{8}\qquad\frac{6}{8}\qquad\frac{7}{8}\qquad\frac{8}{8} \qquad \end{array}$

Fig 1: Array of rational numbers between 0 and 1.

The ratio ${\frac{0}{0}}$ is interpreted as the number ${0}$ . Many numbers occur more than once in this array, for example ${\frac{1}{2} = \frac{2}{4} }$ and so on. We replace duplicates by the symbol ${\frac{\bullet}{\bullet}}$ to indicate that they are to be ignored. Then every rational number in ${[0,1]}$ occurs precisely once:

$\displaystyle \begin{array}{rcl} \qquad &&\frac{\bullet}{\bullet} \\ \\ &&\frac{0}{1}\qquad\frac{1}{1} \\ \\ &&\frac{\bullet}{\bullet}\qquad\frac{1}{2}\qquad\frac{\bullet}{\bullet} \\ \\ &&\frac{\bullet}{\bullet}\qquad\frac{1}{3}\qquad\frac{2}{3}\qquad\frac{\bullet}{\bullet} \\ \\ &&\frac{\bullet}{\bullet}\qquad\frac{1}{4}\qquad\frac{\bullet}{\bullet}\qquad\frac{3}{4}\qquad\frac{\bullet}{\bullet} \\ \\ &&\frac{\bullet}{\bullet}\qquad\frac{1}{5}\qquad\frac{2}{5}\qquad\frac{3}{5}\qquad\frac{4}{5}\qquad\frac{\bullet}{\bullet} \\ \\ &&\frac{\bullet}{\bullet}\qquad\frac{1}{6}\qquad\frac{\bullet}{\bullet}\qquad\frac{\bullet}{\bullet}\qquad\frac{\bullet}{\bullet}\qquad\frac{5}{6}\qquad\frac{\bullet}{\bullet} \\ \\ &&\frac{\bullet}{\bullet}\qquad\frac{1}{7}\qquad\frac{2}{7}\qquad\frac{3}{7}\qquad\frac{4}{7}\qquad\frac{5}{7}\qquad\frac{6}{7}\qquad\frac{\bullet}{\bullet} \\ \\ &&\frac{\bullet}{\bullet}\qquad\frac{1}{8}\qquad\frac{\bullet}{\bullet}\qquad\frac{3}{8}\qquad\frac{\bullet}{\bullet}\qquad\frac{5}{8}\qquad\frac{\bullet}{\bullet}\qquad\frac{7}{8}\qquad\frac{\bullet}{\bullet} \qquad \end{array}$

Now it is a simple matter to list all rational numbers with denominators up to 8 by taking the entries in the above table row by row:

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

These are not in order of magnitude. If we rearrange them in ascending order, we get what is known as the eighth Farey Sequence:

$\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\}$

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 (=0/1) and ends with the value 1 (=1/1). There are 23 terms in the eighth Farey sequence. A table of sequences of orders up to 8 is shown below.

$\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. That is, for two adjacent fractions ${m_1 / n_1}$ and ${m_2 / n_2}$ , the new number is ${(m_1+m_2) / (n_1+n_2)}$ :

$\displaystyle \mbox{Mediant}\left(\frac{m_1}{n_1},\frac{m_2}{n_2}\right) = \frac{m_1+m_2}{n_1+n_2}$

For example, between 3/5 and 2/3, the next rational to appear is 5/8. It is a consequence of this relationship that, at any stage, if ${m_1/n_1}$ and ${m_2/n_2}$ are two neighbouring entries with ${m_1/n_1<m_2/n_2}$ , then ${(m_2n_1-m_1n_2) = 1}$ .

The mediant property allows us to build up the successive Farey sequences. The Farey sequence ${F_{n}}$ is formed by computing the mediant of each pair of consecutive values in ${F_{n-1}}$ and placing each value with denominator ${n}$ between the two fractions from which it was formed.

Chapter III of Hardy and Wright (1960) is devoted to Farey Sequences. They give a short account of the curious history of the naming of the 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).

The Farey sequences are closely related to the Stern-Brocot tree, a topic to which I hope to return in a subsequent post.

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.

ThatsMaths