Continued fractions

4 Farey Sequences and Hyperbolic Geometry

A finite continued fraction with integer coefficients takes values in \(\QQ \PP ^1=\QQ \cup \infty \). We can define a symmetric relation on \(\QQ \PP ^1\) by saying that \(a \sim b\) iff \(a = [a_0,\dots ,a_n],b = [a_0,\dots ,a_{n-1}]\) for some integers \(a_0,\dots ,a_n\). Here are axioms for this relation:

Lemma 4.1. \(\sim \) is the least symmetric relation that is invariant under the action of \(\SL _2(\ZZ )\) (via fractional linear transformations) such that \(0 \sim \infty \). the action on \(\QQ \PP ^1\) is transitive.

Proof. Clearly \(0 \sim \infty \). Moreover, \([a_0,\dots ,a_n]\sim [a_0,\dots ,a_{n-1}] \implies [a_0+m,\dots ,a_{n-1}] \simeq [a_0+m,\dots ,a_n]\) so the relation is invariant under \(\begin {pmatrix} 1 & m \\ 0 & 1 \end {pmatrix}\). Moreover, \([a_0,\dots ,a_n]\sim [a_0,\dots ,a_{n-1}] \implies [0,-a_0,\dots ,-a_{n-1}]\sim [0,-a_0,\dots ,-a_{n}] \), so it is invariant under \(\begin {pmatrix} 0 & -1\\ 1 & 0 \end {pmatrix}\) so it is invariant under \(\SL _2(\ZZ )\). Conversely, if \(0 \sim \infty \), then \([] \sim [0]\), and we can build our relation up from the two operations above. □

Here is another characterization.

Lemma 4.2. \(\sim \) is the symmetrization of the relation \(\frac {a}{b}\sim \frac {c}{d}\) iff \(ad-bc= 1\) for reduced fractions. \(\SL _2(\ZZ )\) acts transitively on pairs that are related.

Proof. This is clearly \(\SL _2(\ZZ )\)-invariant, and \(\frac {n}{1}\) is related to \(\frac {1}{0}\), so the relation described is contained in the one we want. Conversely, we can apply \(\begin {pmatrix} a & c\\ b & d \end {pmatrix}\) to \(\infty \sim 0\) to get the other direction, and that the action is transitive. □

Here is another characterization of the relation using Farey sequences.

Lemma 4.3. \(a \sim \infty \iff a \in \ZZ \), \(a,b \in \QQ , a \sim b \implies |a-b|\leq 1\), \(a\sim b \iff a+n \sim b+n\), and if \(0 \leq a,b \leq 1\), \(a\sim b\) iff \(a\) and \(b\) are consecutive in some Farey sequence.

Proof. First note that need to observe that by Lemma 2.1, if \(\frac {a}{b},\frac {c}{d}\) are consecutive in a Farey sequence, \(\SL _2(\ZZ )\), then \(ad-bc = 1\), so we can apply the the transformation \(\frac {(a-c)z+c}{(b-d)z+d}\) to \(0 \sim 1\). Thus the relation defined in the theorem is contained in the relation \(\sim \). Conversely, if \(ad-bc =1\), \(\frac {a}{b},\frac {c}{d}\) are within \(1\) of each other, so after subtracting them, they will be in the unit interval, at which Lemma 2.1 applies again to say that they are consecutive. □

Lemma 4.4 (Compatibility with the order). If \(a\sim b,c \sim d\) and \(a \leq c \leq b\), then \(a \leq d \leq b\).

Proof. We can assume \(a,b \in [0,1]\), for which it follows from Lemma 2.1. □

Our relation determines some undirected graph on \(\QQ \cup \infty \). We can embed this graph onto the upper graph by taking the geodesics between the two points on the boundary of the upper half plane. This is called the Farey tiling of the upper half plane. Note that if \(\gamma _1\) is the geodesic between two real numbers \(\alpha \leq \beta \), and \(\gamma _2\) is the geodesic between \(a\leq b\), and \(a \in [\alpha ,\beta ]\), then the interiors of \(\gamma _1,\gamma _2\) intersect iff \(b \geq \beta \).The previous lemma shows that none of these geodesics intersect each other except at the boundary in the Farey tiling.

Lemma 4.5. If \(\frac {a}{b}\sim \frac {c}{d}, \frac {a}{b} < \frac {c}{d}\), then \(\frac {a+c}{b+d}\) is the unique number between them related to both.

Proof. That this is related to both and in between is obvious. To show it is unique, by transitivity of the \(\SL _2(\ZZ )\) action and due to its preservation of the cyclic order on \(\QQ \PP ^1\), it is enough to consider \(0 = \frac {0}{1} \sim \frac {1}{0} = \infty \). In this case, it follows since the only positive number \(0,\infty \) are both related to is \(1\). □

Define \(m|M\) for rationals \(m,M\) to be the unique number in the lemma above.

Theorem 4.6. Begin with \(m = 0\) and \(M = \infty \), and let \(\alpha \geq 0\). We will construct a sequence of letters \(R\)s and \(L\)s as follows: If \(\alpha \) is greater than or equal to \(m|M\), then we replace \(m\) with \(m|M\) and record a \(R\). Otherwise, we replace \(M\) with \(m|M\) and record an \(L\). Repeating this process gives an infinite collection of \(L\)s and \(Rs\). Now count the number of times \(L\)s or \(R\)s happens consecutively, and let \(c_i\) be these numbers. \(c_1\) is the number of times \(R\) happens at the beginning. Then \([c_0,c_1,\dots ]\) is the continued fraction for \(\alpha \).

Proof. Observe that the number of times \(R\) will appear at the beginning is \(\floor \alpha \). Then, apply the transformation \(z \mapsto \frac {1}{z-\alpha }\), and observe that the number of rights that appear by starting over except using \(\frac {1}{\alpha -\floor \alpha }\) is exactly the number of lefts that would have appeared right after. Moreover, if \(\alpha = [a_0,\dots ]\), then \(\frac {1}{\alpha -\floor \alpha } = [a_1,\dots ]\), so by induction we are done. □

Note that this has the following geometric interpretation: we can find the sequence of \(R,L\)s by taking the geodesic connecting \(\alpha \) and \(-\alpha \) and looking at how it intersects the Farey tiling.