Enumerating cosets of the modular group

Question

Suppose we chose the generators $f(z) = z+1, g(z) = z-1, h(z) = -1/z$ for the modular group $\Gamma$ (i.e. the group of fractional linear tranformations $z \mapsto (az +b)/(cz+d)$ with $a,b,c,d \in \mathbb{Z}$ and $ad - bc = 1$).

I would like to know of an algorithm for producing "words" in (i.e. compositions of) the generators $f,g,h$ such that one obtains exactly one element of each coset of $\Gamma/H$ where $H$ is the subgroup generated by $f$.

I'm interested in this because it would help me make better pictures of the modular group. I wrote a program (available here) for making pictures in the hyperbolic plane such as the following:

(source)

The above picture was generated by applying all words of length less than a certain length (maybe 12 or something) to a single "triangle+stickman". The chosen generators were $h$ and $h \circ f$ which give the modular group the structure of a free product of finite cyclic groups.

However the pictures are unsatisfactory and do not improve as much as one would like by increasing the "depth" (i.e. max length of words chosen). It seems better to go deep into each coset (i.e. apply $f$ and its inverse a bunch of times) and then transform that. Here's a picture with just 8 cosets (but many transformations were chosen for each):

(source)

Answer 1

Since, as you say, you are talking about "fractional linear transformations not matrices", you are really interested in the group $PSL(2,\mathbb Z)$ rather than $SL(2,\mathbb Z)$. As it has already been pointed out, it is isomorphic to the free product of cyclic groups of orders 2 and 3. Let me denote the generator of order 2 by $a$, and the generator of order 3 by $b$. In these terms you are looking for a transversal (a system of coset representatives) to the cyclic group generated by $ab$. The simplest is the transversal which consists of $e,a$ and all words in the free product which begin with $b$ (i.e., all words of the form $bab^{\epsilon_1}ab^{\epsilon_2}\dots$ with $\epsilon_i=1,2$).

Answer 2

The specific question you asked has been answered, but you asked for an algorithm, and there does exist an implemented algorithm that can solve problems of this type.

Under certain conditions, which are roughly equivalent to $H$ being a finitely generated quasiconvex subgroup of an automatic group $G$, you can construct a "coset word acceptor" as part of a "coset automatic structure" for $H$ in $G$, where $G$ is defined by a finite presentation, and $H$ is defined by a finite set of generating words. The coset word acceptor is a finite state automaton which accepts a unique word over the generators of $G$ for each right coset of $H$ in $G$. In particular, this will work for any finitely generated subgroup of a virtually free group, as in your example.

The algorithm is implemented as part of the $\mathtt{kbmag}$ package, which is available as a standalone or as a $\mathsf{GAP}$ package. With your example, the coset word acceptor has $6$ states.

Answer 3

There are three relations for $T:z\to z+1$, and $S:z\to -1/z$ (see, for example Koblitz, Introduction to elliptic curves and modular forms, Ch. III) $$S^2=-I,\quad (ST)^3=-I,\quad (TS)^3=-I.$$ So in $PSL_2(\mathbb{Z})=SL_2(\mathbb{Z})/\pm I$ we have only to relations $S^2=I$ and $(ST)^3=I$.