# 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.