Two days ago, as a puzzle, I asked what the generating function
counts. Yesterday, I suggested as a hint that it might be useful to interpret that as , and to use the exponential formula.
The answer to the puzzle can be described in several ways. Below I’ll use a description that suggests a generalization I particularly like.
My favorite description
My favorite description of the sequence appearing in the numerators above is that it counts the number of subgroups of the free group of index .
For example, when there is a unique such subgroup, namely itself. When , writing and for two free generators of , the subgroups of index are precisely the kernels of nonzero homomorphisms , which makes it easy to see that there are three of them, namely
Via the classification of covering spaces, an equivalent description is that counts the number of connected covering spaces of the wedge of two circles , where we need to be careful to pick both a basepoint of the wedge of two circles (the wedge point will do nicely) and a lift of that basepoint to the covering space. This lets us draw some pretty pictures of what we’re counting (e.g. the ones in Hatcher).
Gesturing at a proof
Where did come from? For starters, if we think of as , then an obvious combinatorial interpretation of is that it counts pairs of permutations in , or equivalently that it counts homomorphisms . Topologically such homomorphisms describe covering spaces, not necessarily connected, of the wedge of two circles .
There are various ways to describe pairs of permutations in in a way that suggests what their “connected components” decomposition ought to be. For example, given such a permutation you can build a graph with vertices and two sets of directed edges, one for describing each permutation. When you do this you are drawing the corresponding covering space of . Then intuitively you’d like to break this graph up into its connected components, and when you do this you are breaking up a covering space of into its connected components in the topological sense.
More formally, and again in a way that suggests the correct generalization, a homomorphism describes an -set with elements, and every -set is a disjoint union of transitive -sets. Isomorphism classes of transitive -sets in turn correspond to conjugacy classes of finite index subgroups of . But I didn’t claim that we were counting conjugacy classes; I claimed that we were counting finite index subgroups on the nose. What gives?
The beginning of the answer is that a homomorphism is not quite the same as an -set with elements; isomorphism classes of the latter correspond to conjugacy classes of homomorphisms . If we don’t quotient by conjugacy, our -set comes with additional structure, namely a total order. When we break it up into a disjoint union of transitive -sets, each of these “connected components” has a distinguished point in it (say, the smallest point with respect to the total order), and we can take the stabilizer of that point, getting a finite index subgroup of on the nose rather than a conjugacy class.
If this argument holds up, it is in no way specific to , and the following generalization holds.
Theorem: Let be a finitely generated group. Then
where counts the number of subgroups of of index .
(The notation is meant to evoke a fundamental group, and hence the relationship between the above counts and covering spaces.)
But we should be a bit suspicious of everything that’s been said so far. It doesn’t quite explain why the correct denominator on the LHS is , but the correct denominator on the RHS is . Intuitively these come from forgetting the total order on our points above resp. forgetting the distinguished point we took the stabilizer of. But can we be more precise about this?
To my category theorist’s mind, this whole discussion could really benefit from a more careful examination of the category of finite -sets. So here is the real puzzle.
Puzzle: How can the above theorem be proven using categorical ideas applied to the category of finite -sets?
Regardless of how we feel about the proof, we can give lots of interesting examples of special cases of the above formula. Here are a few.
Example. Let . Then and has exactly one subgroup of each finite index. This gives the familiar
Note that decomposing a finite -set into transitive -sets is precisely the same thing as decomposing a permutation into cycles.
Example. Let . Then counts the number of permutations in of order dividing , or equivalently with cycle decomposition consisting of cycles of length dividing . On the other hand, has exactly one subgroup of each index dividing . This gives
which is a familiar application of the exponential formula as it was given in this blog post, as a statement about the cycle index polynomials of the symmetric groups.
Example. Let . Then counts the number of pairs of commuting permutations in . It’s a nice exercise to show that in a finite group this is equal to times the number of conjugacy classes of elements in . When this is equal to , the number of partitions of , so the LHS of our generating function is
The RHS involves counting the number of subgroups of of index . All such subgroups are abstractly isomorphic to themselves; inclusions of such subgroups correspond to the images of injective homomorphisms , which can in turn be identified with matrices . The corresponding subgroup has index iff , but we also need to quotient out by acting on the right (because we only care about the image of , rather than the image together with a distinguished basis of it); that is, we want to identify column equivalence classes of matrices over with nonzero determinant.
Using column operations, we can perform the Euclidean algorithm on the top two entries of our matrix; when we finish doing this, we’ll be left with the of those entries and zero. Hence we can assume WLOG that our matrices have the lower triangular form
Further column operations can guarantee that and that . The condition that is equivalent to the condition that , so there is a choice of (which determines ) for every divisor of , and then for each such divisor there are choices for . Altogether, the number of subgroups of of index is counted by the divisor function
and hence we get
which we can also prove by taking the logarithm of the product expansion for the LHS.
Example. Let to be the fundamental group of a closed surface of genus ; this means subgroups of index correspond to connected covering spaces of of degree . Then can be expressed in terms of the representation theory of using Mednykh’s formula, which asserts more generally that if is a finite group, then
where the sum runs over all complex irreducible representations of , and is the Euler characteristic.
Setting shows that can be computed from the dimensions of the irreducible representations of , which are in turn given by the hook length formula. So the LHS of our generating function can be written
where denotes a hook length. Taking the logarithm of this counts finite index subgroups of .