# The modular group

Example:

Requirements: cairocffi.

This program draws the hyperbolic tiling of the upper plane by fundamental domains of the modular group.

# Math behind this image

The modular group $\mathrm{PSL}_2(\mathbb{Z})$ is an infinite group acts discretely on the upper plane by fractional linear transformations:

$\mathrm{PSL}_2(\mathbb{Z}) = \{\frac{az+b}{cz+d},\ a,b,c,d\in\mathbb{Z}, ad-bc=1\}.$

It can be generated by two elements $S: z\to -1/z$ and $T: z\to z+1$: $\mathrm{PSL}_2(\mathbb{Z}) = \langle S,T \,|\, S^2=(ST)^3=1\rangle,$ using $S$ and $ST$ as generators instead shows this group is isomorphic to the free product of the two cyclic groups $\mathbb{Z}_2$ and $\mathbb{Z}_3$: $\mathrm{PSL}_2(\mathbb{Z})\cong \mathbb{Z}_2\ast\mathbb{Z}_3.$

All the math above can be found on the wiki page, and these are almost enough for drawing our image: to draw the hyperbolic tiling, one just choose any fundamental domain $D$ of $\mathrm{PSL}_2(\mathbb{Z})$ (the classical choice is the region colored gray in the example image), and for each element $g$ in $\mathrm{PSL}_2(\mathbb{Z})$ (in practice we only iterate $g$ up to a given length.), represent $g$ as a word in $\{A,B\}$ where $A=S$ and $B=ST$, then draw the transformed domain $gD$.

Note that the word representation of $g$ by $A,B$ is generally not unique, so we have to be careful to make sure each element is traversed exactly once. This is easy in the case of using the free product representation: each element $g$ can be uniquely expressed in the form $g=x_1x_2\cdots x_n$ where each $x_i$ is either $A$ or $B$ and no two successive $A$'s and no three successive $B$'s occur in this representation.

The problem of this approach is that the resulting $gD$'s are not symmetrically distributed on the two sides of the $y$ axis, some parts of the upper plane are densely tiled by the $gD$'s whereas other parts got very sparse, which is not aesthetically pleasing. I learned a similar approach from Bill Casselman's expository essay which used another presentation of $\mathrm{PSL}_2(\mathbb{Z})$: $\mathrm{PSL}_2(\mathbb{Z})=\langle A,B,C \,|\, C^2=AB=(CA)^3=1\rangle.$ Where $C: z\to -1/z$, $A: z\to z+1$, and $B: z\to z-1$ (the only difference is we have included $B=A^{-1}$ as a generator).

But then how to traverse the modular group using this representation? Here is some deep math got involved: the modular group is an automatic group, which means there exists a finite state automata that recognize the language of the modular group. This automata is shown below (image credits to Casselman also):

So traversing the words in the modular group up to a given length is equivalent to traversing this automata by breadth-first search up to a given number of steps, that's much easier now.