Abstract:
Let $G$ be a subgroup of $\Gamma=SL_2(\mathbb{Z})$.
We will describe an algorithm for constructing fundamental domains for the action of a subgroup $G$ of $PSL_2(\mathbb{Z})$ on the upper half-plane $\mathbb{H}$. The algorithm requires is $O(n P(log n))$ operations where $n$ is the index of $G$ and $P$ is a polynomial; this is quadratically faster than the naive procedure. The main observation is that one can construct a combinatorial model for the quotient $\mathbb{H}/G$ in terms of double cosets. This remark also allows one to handle several related problems, such as finding a free system of generators of $G$ and writing a given element of $G$ in terms of of these generators. We will present an implementation of the algorithm, and discuss possible generalisations
