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$ .