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