The Farey Graph

Gareth Jones, Southampton, U.K.

This is joint work with David Singerman and Keith Wicks, subsequently published in [2]. The modular group

Γ = P SL(2, Z) = SL(2, Z)/{±I}

acts on the upper half-plane U = {z ∈ C | Im(z) > 0} and on the rational projective line Q̂ = Q ∪ {∞} as a group of Möbius transformations

z ↦ \frac{az + b}{cz + d}  (a, b, c, d ∈ Z, ad − bc = 1) .  (∗)

Its action on Q̂ is transitive but imprimitive: for each positive integer N ≠ 2, 5 there is a Γ-invariant equivalence relation on Q̂ with N equivalence classes. We study the action of Γ on Q̂ by using suborbital graphs (introduced in 1967 by Sims [3] for finite permutation groups). These are Γ-invariant directed graphs with vertex-set Q̂, their edge-sets being the orbits of Γ on the cartesian square Q̂^{2}. Apart from the trivial case, corrresponding to the diagonal orbit, there is one suborbital graph G_{u,n} for each integer n ≥ 1 and for each of the ϕ(n) units u mod (n): its edge-set is the orbit containing the pair (∞, u/n). Reversing edges induces a pairing of suborbital graphs, in which G_{u,n} is paired with G_{v,n} where uv ≡ −1 mod (n); thus G_{u,n} is self-paired (and can be represented as an undirected graph) if and only if u^{2} ≡ −1 mod (n).

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

The Farey graph G_{1,1} is connected, but if n > 1 then G_{u,n} is a disjoint union of

ψ(n) = n ∏_{p|n}(1 + \frac{1}{p})

subgraphs (where p ranges over the distinct primes dividing n): their vertex-sets are the equivalence classes in Q̂ where we define r/s ≡_{n} x/y if and only if ry − sx ≡ 0 mod (n). For a given n these subgraphs are permuted transitively by Γ, so they are all isomorphic to the subgraph F_{u,n} containing ∞, consisting of the vertices x/y with y ≡ 0 mod(n). This subgraph is connected if and only if n ≤ 4. Each F_{u,n} is embedded in U to give a tessellation T_{u,n}: for instance T_{1,2} is the universal map [4], in the sense that every map is isomorphic to a quotient of T_{1,2} by some group of automorphisms.

G_{u,n} contains directed triangles if and only if u^{2} ± u + 1 ≡ 0 mod(n), a typical example being ∞ → u/n → (u ± 1)/n → ∞; however, only G_{1,1} = F contains anti-directed triangles, such as ∞ → 1 ← 2 → ∞. For n > 1, G_{u,n} is a forest if it is self-paired or if n is even. We conjecture that G_{u,n} is a forest if and only if it contains no triangles, that is, if and only if u^{2} ± u + 1 ≢ 0 mod(n). (This conjecture has subsequently been proved by Mehmet Akbas.)

[1] G. V. Belyĭ, ‘On Galois extensions of a maximal cyclotomic field’, Izv. Akad. Nauk SSSR 43 (1979), 269–276 (Russian); Math. USSR Izvestiya 14 (1980), 247–256 (English transl.).

[2] G. A. Jones, D. Singerman and K. Wicks, ‘The modular group and generalized Farey graphs’, in Groups, St. Andrews 1989, Vol. 2 (eds. C. M. Campbell and E. F. Robertson), London Math. Soc. Lecture Note Ser. 160 (1991), 316–338.

[3] C. C. Sims, ‘Graphs and finite permutation groups’ Math. Z. 95 (1967), 76–86.

[4] D. Singerman, ‘Universal tessellations’, Revista Mat. Univ. Complutense Madrid 1 (1988), 111–123.