The answer to the puzzle

November 3, 2015 by Qiaochu Yuan

Two days ago, as a puzzle, I asked what the generating function

$\displaystyle \log \sum_{n \ge 0} n! z^n = z + \frac{3}{2} z^2 + \frac{13}{3} z^3 + \frac{71}{4} z^4 + \dots$

counts. Yesterday, I suggested as a hint that it might be useful to interpret that $n!$ as $\frac{n!^2}{n!}$ , 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 $a_n$ appearing in the numerators above is that it counts the number of subgroups of the free group $F_2$ of index $n$ .

For example, when $n = 1$ there is a unique such subgroup, namely $F_2$ itself. When $n = 2$ , writing $a$ and $b$ for two free generators of $F_2$ , the subgroups of index $2$ are precisely the kernels of nonzero homomorphisms $F_2 \to S_2$ , which makes it easy to see that there are three of them, namely

$\displaystyle \langle a^2, b, aba \rangle, \langle a, b^2, bab \rangle, \langle a^2, ab, b^2 \rangle$ .

Via the classification of covering spaces, an equivalent description is that $a_n$ counts the number of connected covering spaces of the wedge of two circles $S^1 \vee S^1$ , 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 $F_2$ come from? For starters, if we think of $n!$ as $\frac{n!^2}{n!}$ , then an obvious combinatorial interpretation of $n!^2$ is that it counts pairs of permutations in $S_n$ , or equivalently that it counts homomorphisms $F_2 \to S_n$ . Topologically such homomorphisms describe covering spaces, not necessarily connected, of the wedge of two circles $S^1 \vee S^1$ .

There are various ways to describe pairs of permutations in $S_n$ 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 $n$ vertices and two sets of directed edges, one for describing each permutation. When you do this you are drawing the corresponding covering space of $S^1 \vee S^1$ . 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 $S^1 \vee S^1$ into its connected components in the topological sense.

More formally, and again in a way that suggests the correct generalization, a homomorphism $F_2 \to S_n$ describes an $F_2$ -set with $n$ elements, and every $F_2$ -set is a disjoint union of transitive $F_2$ -sets. Isomorphism classes of transitive $F_2$ -sets in turn correspond to conjugacy classes of finite index subgroups of $F_2$ . 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 $F_2 \to S_n$ is not quite the same as an $F_2$ -set with $n$ elements; isomorphism classes of the latter correspond to conjugacy classes of homomorphisms $F_2 \to S_n$ . If we don’t quotient by conjugacy, our $F_2$ -set comes with additional structure, namely a total order. When we break it up into a disjoint union of transitive $F_2$ -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 $F_2$ on the nose rather than a conjugacy class.

If this argument holds up, it is in no way specific to $F_2$ , and the following generalization holds.

Theorem: Let $\pi$ be a finitely generated group. Then

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

where $a_n$ counts the number of subgroups of $\pi$ of index $n$ .

(The notation $\pi$ 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 $n!$ , but the correct denominator on the RHS is $n$ . Intuitively these come from forgetting the total order on our $n$ 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 $\pi$ -sets. So here is the real puzzle.

Puzzle: How can the above theorem be proven using categorical ideas applied to the category of finite $\pi$ -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 $\pi = \mathbb{Z}$ . Then $|\text{Hom}(\mathbb{Z}, S_n)| = n!$ and $\mathbb{Z}$ has exactly one subgroup of each finite index. This gives the familiar

$\displaystyle \frac{1}{1 - x} = \exp \sum_{n \ge 1} \frac{x^n}{n}$ .

Note that decomposing a finite $\mathbb{Z}$ -set into transitive $\mathbb{Z}$ -sets is precisely the same thing as decomposing a permutation into cycles.

Example. Let $\pi = \mathbb{Z}_k$ . Then $|\text{Hom}(\mathbb{Z}_k, S_n)|$ counts the number of permutations in $S_n$ of order dividing $k$ , or equivalently with cycle decomposition consisting of cycles of length dividing $k$ . On the other hand, $\mathbb{Z}_k$ has exactly one subgroup of each index dividing $k$ . This gives

$\displaystyle \sum_{n \ge 0} \frac{|\text{Hom}(\mathbb{Z}_k, S_n)|}{n!} z^n = \exp \left( \sum_{d | k} \frac{z^d}{d} \right)$

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 $\pi = \mathbb{Z}^2$ . Then $|\text{Hom}(\mathbb{Z}^2, S_n)|$ counts the number of pairs of commuting permutations in $S_n$ . It’s a nice exercise to show that in a finite group $H$ this is equal to $|H|$ times the number of conjugacy classes of elements in $H$ . When $H = S_n$ this is equal to $p(n)$ , the number of partitions of $n$ , so the LHS of our generating function is

$\displaystyle \sum_{n \ge 0} p(n) z^n = \prod_{n \ge 1} \frac{1}{(1 - z^n)}$ .

The RHS involves counting the number of subgroups of $\mathbb{Z}^2$ of index $n$ . All such subgroups are abstractly isomorphic to $\mathbb{Z}^2$ themselves; inclusions of such subgroups correspond to the images of injective homomorphisms $f : \mathbb{Z}^2 \to \mathbb{Z}^2$ , which can in turn be identified with matrices $M \in M_2(\mathbb{Z})$ . The corresponding subgroup has index $n$ iff $|\det(M)| = n$ , but we also need to quotient out by $GL_2(\mathbb{Z})$ acting on the right (because we only care about the image $\text{im}(M)$ of $M$ , rather than the image together with a distinguished basis of it); that is, we want to identify column equivalence classes of $2 \times 2$ matrices over $\mathbb{Z}$ 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 $\gcd$ of those entries and zero. Hence we can assume WLOG that our matrices have the lower triangular form

$\displaystyle M = \left[ \begin{array}{cc} a & 0 \\ c & d \end{array} \right]$ .

Further column operations can guarantee that $a, d > 0$ and that $0 \le c < d$ . The condition that $|\det(M)| = n$ is equivalent to the condition that $ad = n$ , so there is a choice of $d$ (which determines $a$ ) for every divisor of $n$ , and then for each such divisor $d$ there are $d$ choices for $c$ . Altogether, the number of subgroups of $\mathbb{Z}^2$ of index $n$ is counted by the divisor function

$\sigma_1(n) = \sum_{d | n} d$

and hence we get

$\displaystyle \sum_{n \ge 0} p(n) z^n = \exp \left( \sum_{n \ge 1} \sigma_1(n) \frac{z^n}{n} \right)$

which we can also prove by taking the logarithm of the product expansion for the LHS.

Example. Let $\pi = \pi_1(\Sigma_g)$ to be the fundamental group of a closed surface of genus $g$ ; this means subgroups of index $n$ correspond to connected covering spaces of $\Sigma_g$ of degree $n$ . Then $|\text{Hom}(\pi, S_n)|$ can be expressed in terms of the representation theory of $S_n$ using Mednykh’s formula, which asserts more generally that if $G$ is a finite group, then

$\displaystyle \frac{|\text{Hom}(\pi_1(\Sigma_g), G)|}{|G|} = \sum_V \left( \frac{\dim V}{|G|} \right)^{\chi(\Sigma_g)}$

where the sum runs over all complex irreducible representations $V$ of $G$ , and $\chi(\Sigma_g) = 2 - 2g$ is the Euler characteristic.

Setting $G = S_n$ shows that $|\text{Hom}(\pi_1(\Sigma_g), S_n)|$ can be computed from the dimensions of the irreducible representations of $S_n$ , which are in turn given by the hook length formula. So the LHS of our generating function can be written

$\displaystyle \sum_{n \ge 0} \sum_{\lambda \vdash n} \left( \prod h_{\lambda}(i, j) \right)^{2g - 2} z^n$

where $h_{\lambda}(i, j)$ denotes a hook length. Taking the logarithm of this counts finite index subgroups of $\Sigma_g$ .

Posted in math.CO, math.GR | Tagged MaBloWriMo | 4 Comments

4 Responses

on May 20, 2016 at 5:49 pm | Reply 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 | Reply Omar

Fix 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 | Reply Qiaochu Yuan
  
  Yep! 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 | Reply The categorical exponential formula | Annoying Precision

[…] « The answer to the puzzle […]

Comments RSS

	ZW on The double commutant theo…
	auto on More about the Schrödinger equ…
	Jaromir Kuben on Meditation on the Sylow theore…
	Qiaochu Yuan on Meditation on the Sylow theore…
	Qiaochu Yuan on Some remarks on the infinitude…

Annoying Precision

"A good stock of examples, as large as possible, is indispensable for a thorough understanding of any concept, and when I want to learn something new, I make it my first job to build one." – Paul Halmos