%This is a Plain-TeX file
%producing 2 page output.

\magnification=1200
\hsize=11.25cm


%\nopagenumbers
\centerline{\bf The Farey Graph}

\bigskip

\centerline{\sl Gareth Jones, Southampton, U.K.}

\bigskip

This is joint work with David Singerman and Keith Wicks, subsequently published
in [2]. The modular group 
$$\Gamma=PSL(2,{\bf Z})=SL(2,{\bf Z})/\{\pm I\}$$
acts
on the upper half-plane ${\cal U}=\{z\in{\bf C}\mid {\rm Im}(z)>0\}$ and on the
rational projective line $\hat{\bf Q}={\bf Q}\cup\{\infty\}$ as a group of
M\"obius transformations $$z\mapsto{az+b\over cz+d}\qquad\qquad(a, b, c,
d\in{\bf Z},\; ad-bc=1)\,.\eqno(*)$$ Its action on $\hat{\bf Q}$ is transitive
but imprimitive: for each positive integer $N\neq 2, 5$ there is a
$\Gamma$-invariant equivalence relation on $\hat{\bf Q}$ with $N$ equivalence
classes. We study the action of $\Gamma$ on $\hat{\bf Q}$ by using suborbital
graphs (introduced in 1967 by Sims [3] for finite permutation groups). These are
$\Gamma$-invariant directed graphs with vertex-set $\hat{\bf Q}$, their
edge-sets being the orbits of $\Gamma$ on the cartesian square $\hat{\bf Q}^2$.
Apart from the trivial case, corrresponding to the diagonal orbit, there is one
suborbital graph ${\cal G}_{u,n}$ for each integer $n\geq 1$ and for each of the
$\phi(n)$ units $u$ mod $(n)$: its edge-set is the orbit containing the pair
$(\infty, u/n)$. Reversing edges induces a pairing of suborbital graphs, in
which ${\cal G}_{u,n}$ is paired with ${\cal G}_{v,n}$ where $uv\equiv -1$ mod
$(n)$; thus ${\cal G}_{u,n}$ is self-paired (and can be represented as an
undirected graph) if and only if $u^2\equiv -1$ mod $(n)$.

\medskip

The simplest example is the {\sl Farey graph} ${\cal F}={\cal G}_{1,1}$: the
vertex $\infty$ is joined to the integers, while two rational numbers $r/s$ and
$x/y$ (in reduced form) are adjacent in $\cal F$ if and only if
$ry-sx=\pm 1$, or equivalently if they are consecutive terms in some Farey
sequence $F_m$ (consisting of the rationals $x/y$ with $|y|\leq m$, arranged in
increasing order). If we draw the edges of $\cal F$ as hyperbolic geodesics in
$\cal U$ (euclidean semicircles and half-lines), they do not cross, so we
have an
embedding of $\cal F$; the faces are hyperbolic triangles, giving a
triangulation $\cal T$ of $\cal U$ with `ideal vertices' on the boundary. Both
$\cal F$ and $\cal T$ have automorphism group $PGL(2,{\bf Z})$, which contains
$\Gamma$ as its orientation-preserving subgroup of index $2$. The triangulation
$\cal T$ acts as a universal object for triangular maps, each of which is
isomorphic to a quotient ${\cal T}/M$ for some subgroup $M$ of $PGL(2,{\bf Z})$.
It follows from Bely\u\i's Theorem [1] that the Riemann surfaces defined as
algebraic curves over the field $\overline{\bf Q}$ of algebraic numbers are
those obtained in this way from compact orientable triangular maps, that is,
they are the compactifications of the surfaces ${\cal U}/M$ where $M$ has finite
index in $\Gamma$.

\medskip

The Farey graph ${\cal G}_{1,1}$ is connected, but if $n>1$ then ${\cal
G}_{u,n}$ is a disjoint union of
$$\psi(n)=n\prod_{p|n}\Bigl(1+{1\over p}\Bigr)$$
subgraphs (where $p$ ranges over the distinct primes dividing $n$): their
vertex-sets are the equivalence classes in $\hat{\bf Q}$ where we define
$r/s\equiv_n x/y$ if and only if $ry-sx\equiv 0$ mod $(n)$. For a given $n$
these
subgraphs are permuted transitively by $\Gamma$, so they are all isomorphic to
the subgraph ${\cal F}_{u,n}$ containing $\infty$, consisting of the
vertices $x/y$ with $y\equiv 0$ mod$(n)$. This subgraph is connected if and only
if $n\leq 4$. Each ${\cal F}_{u,n}$ is embedded in $\cal U$ to give a
tessellation ${\cal T}_{u,n}$: for instance ${\cal T}_{1,2}$ is the universal
map [4], in the sense that every map is isomorphic to a quotient of ${\cal
T}_{1,2}$ by some group of automorphisms.

\medskip

${\cal G}_{u,n}$ contains directed triangles if and only if $u^2\pm u+1\equiv 0$
mod$(n)$, a typical example being $\infty\to u/n\to(u\pm 1)/n\to\infty$;
however, only ${\cal G}_{1,1}={\cal F}$ contains anti-directed triangles, such
as $\infty\to 1\leftarrow 2\to\infty$. For $n>1$, ${\cal G}_{u,n}$ is a forest
if it is self-paired or if $n$ is even. We conjecture that ${\cal G}_{u,n}$ is a
forest if and only if it contains no triangles, that is, if and only if $u^2\pm
u+1\not\equiv 0$ mod$(n)$. (This conjecture has subsequently been proved by
Mehmet Akbas.)

\bigskip

\item{[1]} G.~V.~Bely\u\i, `On Galois extensions of a maximal cyclotomic
field', {\sl Izv.~Akad.~Nauk SSSR} 43 (1979), 269--276 (Russian); {\sl
Math.~USSR Izvestiya} 14 (1980), 247--256 (English transl.).
\medskip

\item{[2]} G.~A.~Jones, D.~Singerman and K.~Wicks, `The modular group and
generalized Farey graphs', in {\sl Groups, St. Andrews 1989, Vol.~2} (eds.
C.~M.~Campbell and E.~F.~Robertson), London Math.~Soc.~Lecture Note Ser. 160
(1991), 316--338.
\medskip

\item{[3]} C.~C.~Sims, `Graphs and finite permutation groups' {\sl Math.~Z.}
95 (1967), 76--86.
\medskip

\item{[4]} D.~Singerman, `Universal tessellations', {\sl Revista
Mat.~Univ.~Complutense Madrid} 1 (1988), 111--123.

\bye