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

.

This identity reflects, in a way we made precise in the previous post, the decomposition of a finite -set (the terms on the LHS) into a disjoint union of transitive -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 , the modular group. In this post we’ll use the above formula to compute the number of subgroups of index in 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 , as an abstract group, is very easy to describe: it’s isomorphic to the free product of a cyclic group of order and a cyclic group of order . The corresponding elements of of order and order , regarded as fractional linear transformations , are

.

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

.

This free product decomposition means that it’s very easy to describe homomorphisms ; such a homomorphism is the same thing as a pair of permutations such that . That makes these homomorphisms easy to count. If denotes the number of permutations such that , then we know (e.g. by applying the general formula above to ) that

and hence that

and that

.

Finally, we have

and so we can compute the number of subgroups of index in the modular group by extracting the coefficients of the logarithm

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

and

which tells us the first six terms of . This gives

and taking the logarithm of this produces

.

That is, the first six terms of the sequence are . 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 of index are naturally in bijection with pointed transitive -sets, and we can visualize these using a generalized Cayley graph construction. To describe the action of on a finite set , we can draw a graph whose vertices are the elements of . The action of the generator of order pairs together some disjoint pairs of vertices, and we can draw undirected edges between these. The action of the generator of order groups together some disjoint triples of elements of ; we can draw directed cycles of length between these.

The resulting graph is connected iff the action of is transitive, and so subgroups of index correspond to pointed connected graphs of this form with 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 acting on subgroups by conjugation. The normal subgroups are the orbits of size , 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 .

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 are all free products of copies of , and , but don’t quote me on that. Topologically, the idea is to think of as a 1-dimensional orbifold consisting of an orbifold point with stabilizer joined to an orbifold point with stabilizer by an edge (reflecting the wedge sum decomposition ), and then to consider coverings of this orbifold, which are also 1-dimensional orbifolds.

on June 12, 2017 at 5:05 pm |Richard StanleySee “Enumerative Combinatorics,” vol. 2, Exercise 5.13.

on November 29, 2015 at 7:43 am |eka-markShould the first instance of the word “subgroup” in the main text just be “group”?

on November 29, 2015 at 10:49 am |Qiaochu YuanOops. Yep. Thanks for the catch!

on November 29, 2015 at 12:30 am |Drawing subgroups of the modular group | Annoying Precision[…] 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. […]

on November 20, 2015 at 6:34 pm |Will Sawin1. 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.

on November 20, 2015 at 9:54 pm |Qiaochu YuanYeah, 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.