Feeds:
Posts

## Finite index subgroups of the modular group

Two weeks ago we proved the following formula. Let $G$ be a finitely generated group and let $a_n$ be the number of subgroups of $G$ of index $n$. Then

$\displaystyle \sum_{n \ge 0} \frac{|\text{Hom}(G, S_n)|}{n!} z^n = \exp \left( \sum_{n \ge 1} \frac{a_n}{n} z^n \right)$.

This identity reflects, in a way we made precise in the previous post, the decomposition of a finite $G$-set (the terms on the LHS) into a disjoint union of transitive $G$-sets (the terms on the RHS).

Noam Zeilberger commented on the previous post that he had seen results like this for more specific groups in the literature; in particular, Samuel Vidal describes a version of this analysis for $G = \Gamma = PSL_2(\mathbb{Z})$, the modular group. In this post we’ll use the above formula to compute the number of subgroups of index $n$ in $\Gamma$ using a computer algebra system that can manipulate power series. We’ll also say something about how to visualize these subgroups.

The count

The key is that $\Gamma$, as an abstract group, is very easy to describe: it’s isomorphic to the free product $\mathbb{Z}_2 \ast \mathbb{Z}_3$ of a cyclic group of order $2$ and a cyclic group of order $3$. The corresponding elements of $PSL_2(\mathbb{Z})$ of order $2$ and order $3$, regarded as fractional linear transformations $z \mapsto \frac{az + b}{cz + d}$, are

$\displaystyle z \mapsto - \frac{1}{z}, z \mapsto \frac{z - 1}{z}$.

We’ll name them $a$ and $b$ in what follows, so that

$\displaystyle \Gamma \cong PSL_2(\mathbb{Z}) \cong \langle a, b \mid a^2 = b^3 = e \rangle$.

This free product decomposition means that it’s very easy to describe homomorphisms $\Gamma \to S_n$; such a homomorphism is the same thing as a pair $a, b \in S_n$ of permutations such that $a^2 = b^3 = e$. That makes these homomorphisms easy to count. If $o_k(n)$ denotes the number of permutations $\sigma \in S_n$ such that $\sigma^k = e$, then we know (e.g. by applying the general formula above to $G = \mathbb{Z}_k$) that

$\displaystyle \sum_{n \ge 0} \frac{o_k(n)}{n!} z^n = \exp \left( \sum_{d \mid k} \frac{z^d}{d} \right)$

and hence that

$\displaystyle \sum_{n \ge 0} \frac{o_2(n)}{n!} z^n = \exp \left( z + \frac{z^2}{2} \right)$

and that

$\displaystyle \sum_{n \ge 0} \frac{o_3(n)}{n!} z^n = \exp \left( z + \frac{z^3}{3} \right)$.

Finally, we have

$\displaystyle |\text{Hom}(\Gamma, S_n)| = o_2(n) o_3(n)$

and so we can compute the number $a_n$ of subgroups of index $n$ in the modular group $\Gamma$ by extracting the coefficients of the logarithm

$\displaystyle \sum_{n \ge 1} \frac{a_n}{n} z^n = \log \left( \sum_{n \ge 0} \frac{o_2(n) o_3(n)}{n!} z^n \right)$

which is easy to do with a computer algebra system such as WolframAlpha. For example, suppose we wanted to compute the first six terms $a_1, a_2, \dots a_6$. We have

$\displaystyle \exp \left( z + \frac{z^2}{2} \right) = 1 + z + \frac{2 z^2}{2!} + \frac{4z^3}{3!} + \frac{10z^4}{4!} + \frac{26 z^5}{5!} + \frac{76 z^6}{6!} + O(z^7)$

and

$\displaystyle \exp \left( z + \frac{z^3}{3} \right) = 1 + z + \frac{z^2}{2!} + \frac{3 z^3}{3!} + \frac{9 z^4}{4!} + \frac{21 z^5}{5!} + \frac{81 z^6}{6!} + O(z^7)$

which tells us the first six terms of $o_2(n), o_3(n)$. This gives

$\displaystyle \sum_{n \ge 0} \frac{o_2(n) o_3(n)}{n!} z^n = 1 + z + \frac{2z^2}{2!} + \frac{12 z^3}{3!} + \frac{90 z^4}{4!} + \frac{546 z^5}{5!} + \frac{6156 z^6}{6!} + O(z^7)$

and taking the logarithm of this produces

$\displaystyle \sum_{n \ge 1} \frac{a_n}{n} z^n = z + \frac{z^2}{2} + \frac{4z^3}{3} + \frac{8z^4}{4} + \frac{5z^5}{5} + \frac{22z^6}{6} + O(z^7)$.

That is, the first six terms of the sequence $a_n$ are $1, 1, 4, 8, 5, 22$. Plugging this into the OEIS gives A005133, an entry contributed by Samuel Vidal.

Visuals

Of course we can do better than just count these subgroups: we can also visualize them in various ways. Subgroups of $\Gamma$ of index $n$ are naturally in bijection with pointed transitive $\Gamma$-sets, and we can visualize these using a generalized Cayley graph construction. To describe the action of $\Gamma \cong \mathbb{Z}_2 \ast \mathbb{Z}_3$ on a finite set $X$, we can draw a graph whose vertices are the elements of $X$. The action of the generator $a$ of order $2$ pairs together some disjoint pairs of vertices, and we can draw undirected edges between these. The action of the generator $b$ of order $3$ groups together some disjoint triples of elements of $X$; we can draw directed cycles of length $3$ between these.

The resulting graph is connected iff the action of $\Gamma$ is transitive, and so subgroups of index $n$ correspond to pointed connected graphs of this form with $n$ vertices. Moreover, by changing the basepoint we conjugate the subgroup, so by grouping the pointed connected graphs together according to the isomorphism class of the underlying unpointed graph, we can describe the orbits of $\Gamma$ acting on subgroups by conjugation. The normal subgroups are the orbits of size $1$, and these correspond to graphs whose automorphism groups act transitively on vertices. For a normal subgroup the corresponding graph can be identified with the Cayley graph of the quotient, with generators $a, b$.

There should be a better visualization coming from Bass-Serre theory that will even describe the isomorphism classes of the resulting groups, analogous to how drawing covering spaces of graphs shows that subgroups of free groups are free, but I’m not sure how to describe it rigorously off the top of my head. The analogous statement here, I think, is that subgroups of $\Gamma$ are all free products of copies of $\mathbb{Z}_2, \mathbb{Z}_3$, and $\mathbb{Z}$, but don’t quote me on that. Topologically, the idea is to think of $B \Gamma$ as a 1-dimensional orbifold consisting of an orbifold point with stabilizer $\mathbb{Z}_2$ joined to an orbifold point with stabilizer $\mathbb{Z}_3$ by an edge (reflecting the wedge sum decomposition $B \Gamma \cong B \mathbb{Z}_2 \vee B \mathbb{Z}_3$), and then to consider coverings of this orbifold, which are also 1-dimensional orbifolds.

### 6 Responses

1. on June 12, 2017 at 5:05 pm | Reply Richard Stanley

See “Enumerative Combinatorics,” vol. 2, Exercise 5.13.

2. Should the first instance of the word “subgroup” in the main text just be “group”?

• Oops. Yep. Thanks for the catch!

3. […] Previously we learned how to count the finite index subgroups of the modular group . The worst thing about that post was that it didn’t include any pictures of these subgroups. Today we’ll fix that. […]

4. 1. The best visualization is to draw the dessins d’enfants of the j function. 2. I wonder if there’s a count of congruence subgroups that you can use to compare the asymptotics and show how many more non-congruence ones there are.

• Yeah, I realized how to do it after writing this post and I’ve been drawing them for a few days now. It’s pretty fun.