Combinatorics of double cosets and fundamental domains for the subgroups of the modular group

Abstract

As noticed by R.~Kulkarni, the conjugacy classes of subgroups of the modular group correspond bijectively to bipartite cuboid graphs. We'll explain how to recover the graph corresponding to a subgroup $G$ of ${\mathrm{PSL}}_2(\mathbb{Z})$ from the combinatorics of the right action of ${\mathrm{PSL}}_2(\mathbb{Z})$ on the right cosets $G\backslash {\mathrm{PSL}}_2(\mathbb{Z})$. This gives a method of constructing nice fundamental domains (which Kulkarni calls "special polygons") for the action of $G$ on the upper half plane. For the classical congruence subgroups ${\Gamma }_0(N)$, ${\Gamma }_1(N)$, $\Gamma (N)$ etc. the number of operations the method requires is the index times something that grows not faster than a polynomial in $\log N$. This is roughly the square root of the number of operations required by the naive procedure. We give algorithms to locate an element of the upper half-plane on the fundamental domain and to write a given element of $G$ as a product of independent generators. We also (re)prove a few related results about the automorphism groups of modular curves. For example, we give a simple proof that the automorphism group of $X(N)$ is ${\mathrm{SL}}_2(\mathbb{Z}/N)/\{\pm I\}$.

24 pages, 6 figures. Typo fixes and small improvements throughout. More examples have been added. Construction of the fundamental domain has been reverted to v1. Slightly longer than the journal version (to appear in Sbornik Mathematics)