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?

**Some examples**

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 .

on May 20, 2016 at 5:49 pm |The man who knew partition asymptotics | Annoying Precision[…] derivative of , so let’s try to understand the logarithm. ( previously appeared on this blog here as the generating function of the number of subgroups of of index , although that won’t be […]

on November 13, 2015 at 7:53 pm |OmarFix a finitely generated group π and consider the species A of actions of π.

and the species T of transitive actions of π.

An action is definitely nothing more than a disjoint union of transitive ones, so the the exponential formula says A(z) = exp(T(z)). Let’s show that that is precisely the formula you want.

First A(z) is the LHS of your formula: the number of actions of π on a set with n elements is exactly |Hom(π,S_n)|.

Now for the RHS to match, we must show the number t_n of transitive actions on a set with n elements is given by (n-1)! a_n, where a_n is the number of index n subgroups of π.

This is because if X has n elements there is a bijection between pairs (transitive action of π on X, point x in X) and pairs (index n subgroup G of π, bijection between X and π/G). Given a pair of the first kind, you can take the stabilizer of x as the subgroup G in a pair of the second kind, and use the action to get the required bijection. In the opposite direction, the bijection lets you transport the action on π/G to X, and you can pick x to be the image of the coset of the identity.

That bijection shows that n t_n = n! a_n, and so t_n = (n-1)! a_n as desired.

on November 14, 2015 at 8:34 am |Qiaochu YuanYep! You might also be interested in my take on a more complete solution here. The main takeaway is that we can get away with considering a bit less structure than a species, namely a groupoid equipped with a “weight function.”

on November 4, 2015 at 10:42 pm |The categorical exponential formula | Annoying Precision[…] « The answer to the puzzle […]