# The Farey Graph

June 27, 2021

The Farey graph, or Farey diagram, is an object that appears in many guises throughout math. For me, it appears several times as a complex related to the outer automorphism group of a free group of rank two, but it has connections to things like continued fractions as well. The purpose of this post is introduce the Farey graph and prove a couple of basic properties of it.

The Farey graph has as vertices all rational numbers expressed as fractions $\frac{p}{q}$ in lowest terms with $q \ge 0$ , together with a vertex for $\frac{1}{0}$ . Two vertices $\frac{a}{b}$ and $\frac{c}{d}$ span an edge when the matrix $\begin{pmatrix} a & c \\ b & d \end{pmatrix}$ has determinant $\pm 1$ . Above is a picture; thanks to StackExchange user marchetto for the TikZ code for producing the Farey diagram, to which I mainly added numbers. I’d like to demonstrate that the visual properties of the Farey graph hold: namely, that every edge belongs to exactly two triangles, and that edges do not cross.

## Edges belong to two triangles

In this section we will show that every edge of the Farey graph belongs to two triangles.
The key tool will be a lemma I learned from
Allen Hatcher’s *Topology of Numbers*.

Lemma.Suppose $a$ and $b$ are integers with no common divisor. If one integral solution of $ay - bx = n$ is $(x,y) = (c,d)$ , then the general integral solution is $(x,y) = (c + ka, d + kb)$ for integer $k$ .

*Proof.* Consider a general solution $(x,y)$
.
Given our known solution $(c,d)$
, we see that $a(y-d) - b(x -c) = n - n = 0$
.
Since $a$
and $b$
have no common factors, it follows that $a$
divides $x-c$
and $b$
divides $y-d$
.
In fact, we have $a(y-d) = abk = b(x-c)$
, from which the result follows. $\blacksquare$

A variant on the proof shows that if $ac - bd = -n$ , then the general integral solution for $ax - by = n$ is $(ka - c,kb - d)$ .

Proposition.Suppose that $\frac ab$ and $\frac cd$ are in the Farey graph, and that $ad > bc$ . If $\frac xy$ is adjacent to both $\frac ab$ and $\frac bc$ , then $\frac xy = \frac{a\pm c}{b\pm d}$ .

*Proof.*
Suppose $\frac ab$
and $\frac cd$
are as in the statement.
Now suppose $\frac xy$
is adjacent to both $\frac ab$
and $\frac cd$
.
Suppose first for definiteness that $ay - bx = 1$
.
By the lemma, we have that $(x,y) = (ka + c, kb + d)$
for some integer $k$
.
By assumption, we have $cy - dx = \pm 1$
, so the lemma shows that $(x,y) = (\ell c \mp a,\ell d \mp b)$
for some integer $\ell.$
Therefore we have $a(k \pm 1) = (\ell - 1)c$
and $b(k \pm 1) = (\ell-1)d$
,
from which it follows that $(k \pm 1)(\ell - 1)(ad - bc) = 0$
.
Therefore either $k = \mp 1$
or $\ell = 1$
,
both of which imply $(x,y) = (c \mp a,d \mp b)$
.
If instead we have $ay-bx = -1$
, then the conclusion is the same.
We of course have $\frac{c \mp a}{d \mp b} = \frac{a \pm c}{b \pm d}$
. $\blacksquare$

## The action of $\operatorname{SL}_2(\mathbb{Z})$

In this section we analyze the action of $\operatorname{SL}_2(\mathbb{Z})$ on the Farey diagram, proving that it is transitive on edges and triangles.

First let us define the action of $\operatorname{SL}_2(\mathbb{Z})$ on the Farey diagram. The action of $\operatorname{SL}_2(\mathbb{Z})$ on $\mathbb{Z}^2$ restricts to an action on the vertex set of the Farey diagram. Indeed, $a$ and $b$ are relatively prime if and only if there exists integers $x$ and $y$ such that $ax + by = 1$ if and only if $(a,b)$ is the first column of a matrix in $\operatorname{SL}_2(\mathbb{Z})$ if and only if there is an element of $\operatorname{SL}_2(\mathbb{Z})$ taking $(1,0)$ to $(a,b)$ . In terms of fractions, if $z = \frac{p}{q}$ is a vertex of the Farey diagram, then the action of $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ sends $z$ to

$\frac{az + b}{cz + d} = \frac{ap + bq}{cp + dq}.$This action preserves adjacency: the reader is encouraged to figure out why. Indeed, the action is transitive on edges: can you show that if $\frac ab$ and $\frac cd$ are adjacent in the diagram, there is an element of $\operatorname{SL}_2(\mathbb{Z})$ sending the edge between $\frac 01$ and $\frac 10$ to the edge between $\frac ab$ and $\frac cd$ ?

Finally, put a cyclic order on the vertex set of the Farey diagram
by taking the cyclic order induced by the linear order on $\mathbb{Q} \cup \{\infty\}$
.
That is, given three distinct elements $p$
, $q$
and $r$
in $\mathbb{Q}\cup\infty$
,
say $(p,q,r)$
is *cyclically ordered* if
$a < b < c$
or $b < c < a$
or $c < a < b$
holds.
For example $(\infty,-2,0)$
is cyclically ordered.

Proposition.Suppose $p$ , $q$ and $r$ are the vertices of a triangle in the Farey diagram and that $(p,q,r)$ is cyclically ordered. Then there is an element of $\operatorname{SL}_2(\mathbb{Z})$ sending $(0,1,\infty)$ to $(p,q,r)$ .

*Proof.*
Suppose $p = \frac cd$
and $r = \frac ab$
.
Because $p$
and $r$
are adjacent in the Farey diagram,
the matrix $\begin{pmatrix} a & c \\ b & d \end{pmatrix}$
has determinant $\pm 1$
.

Assume first that $ad-bc = 1$ , i.e. that $p < r$ . Then the claim is that $q = \frac{a+c}{b+d}$ , which is the image of $\frac 11$ under the matrix $\begin{pmatrix} a & c \\ b & d\end{pmatrix}$ . In other words, the claim is that $(p,\frac{a-c}{b-d},r)$ is not circularly ordered, for which we need to show that $p<\frac{a-c}{b-d}<r$ is false. Assume first that $b-d$ is nonnegative. Then $ad > bc$ implies $ab - ad < ab - bc$ , which implies $\frac ab < \frac{a-c}{b-d}$ , and the claim follows. Next assume that $b-d$ is negative. Then $ad > bc$ implies that $ad - dc > bc - dc$ , which implies $\frac{a-c}{b-d} < \frac cd$ , and the claim follows (Note that we assume that $d$ is nonnegative.)

Next assume that $ad - bc = -1$ , i.e. that $r < p$ . Then the claim is that $q = \frac{a-c}{b-d}$ , which is the image of $\frac 11$ under the matrix $\begin{pmatrix} a & - c \\ b & -d\end{pmatrix}$ in $\operatorname{SL}_2(\mathbb{Z})$ . In other words, the claim is that $(p,\frac{a+c}{b+d},r)$ is not circularly ordered, for which we need to show that it neither $\frac{a+c}{b+d} < r < p$ nor $r < p < \frac{a+c}{b+d}$ holds. In fact, $ad < bc$ implies $ab + bc > ab + ad$ holds, which implies $\frac{a+c}{b+d} > \frac ab$ . But, $ad < bc$ implies that $ad + dc < bc + dc$ , which implies that $\frac{a+c}{b+d} < \frac cd$ , and the claim follows. $\blacksquare$

In fact, the proof above shows that the matrix in $\operatorname{SL}_2(\mathbb{Z})$
is unique up to multiplication of all the entries by $-1$
.
This corresponds to the matrix $\begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix}$
,
which generates the *center* of $\operatorname{SL}_2(\mathbb{Z})$
.

Corollary.The stabilizer of a triangle is isomorphic to $C_3 \times C_2 \cong C_6$ .

An explicit generator for the cyclic group of order $6$ stabilizing the triangle spanned by $(0,1,\infty)$ is $\begin{pmatrix} 1 & -1 \\ 1 & 0 \end{pmatrix}$ .

The proposition also yields an element of $\operatorname{SL}_2(\mathbb{Z})$ interchanging $0$ and $\infty$ : this element is $\begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix}$ . This element is unique up to multiplication by $-1$ and has order $4$ , so we have proven the following.

Corollary.The stabilizer of an edge is isomorphic to $C_4$ .

## Edges do not cross

We finish this post by proving that edges of the Farey diagram do not cross, in the sense that if $p$ and $q$ are adjacent and $r$ and $s$ are adjacent and $p$ , $q$ , $r$ and $s$ are all distinct, then if $(p,r,q)$ is cyclically ordered, then $(p,s,q)$ is also cyclically ordered. By results in the previous section, we may assume $p = 0$ and $q = \infty$ . That is, if $r = \frac ab$ is positive and $\frac cd$ is adjacent to $\frac ab$ , then $\frac cd$ is also positive. By swapping the roles of $r$ and $s$ if necessary, we may assume that $ad - bc = 1$ . Since we assume that $a$ , $b$ , and $d$ are positive integers, then we must have $c \ge 0$ in order to satisfy $ad -bc = 1$ .