Yesterday I described the answer to the puzzle of what the generating function

counts by sketching a proof of the following more general identity: if is a finitely generated group and is the number of subgroups of of index , then

.

The main ingredient is the exponential formula, but the discussion of the proof involved some careful juggling to make sure we weren’t inappropriately quotienting out by various symmetries, and one might find this conceptually unsatisfying. The goal of today’s post is to state a categorical result which describes exactly how to juggle these symmetries and gives a conceptually clean proof of the above identity.

The key is to describe in exactly what sense a finite -set (corresponding to the LHS) has a canonical “connected components” decomposition as a disjoint union of transitive -sets (corresponding to the RHS), which is the following.

**Claim:** The symmetric monoidal groupoid of finite -sets, with symmetric monoidal structure given by disjoint union, is the free symmetric monoidal groupoid on the groupoid of transitive finite -sets.

From here, we’ll use a version of the exponential formula that comes from relating (weighted) groupoid cardinalities of a groupoid and of the free symmetric monoidal groupoid on it.

**The free symmetric monoidal groupoid**

Given a groupoid , the free symmetric monoidal groupoid on , which we’ll denote by , can be defined in the following very suggestive-looking way:

.

Here by we mean the homotopy quotient or action groupoid of the action of on by permutations. Explicitly, beginning with the groupoid , whose objects we will write as , we add an extra morphism

for every permutation , composing in the obvious way, and natural in the sense that, if is a tuple of morphisms in , then

as morphisms .

The symmetric monoidal structure on is the obvious thing implied by the above notation.

One way to describe as a groupoid is to describe its isomorphism classes and, for each isomorphism class, describe its automorphism group. It’s not hard to see that its isomorphism classes are unordered multisets of isomorphism classes of objects in . Given such a multiset, suppose that the object occurs with multiplicity . Then the automorphism group of the corresponding object

is the product, over all , of the wreath products

.

Here acts on componentwise, while acts by permutation.

*Example.* , the free symmetric monoidal groupoid on a point, is the symmetric monoidal category of finite sets and bijections, equipped with the disjoint union. More generally, if is a finite set, then is the is the symmetric monoidal category of -indexed families of finite sets and bijections.

There are several ways in which really deserves its name; for example, there is a natural isomorphism

which reflects the more general fact that is the left adjoint to the forgetful (2-)functor from symmetric monoidal groupoids to groupoids, and hence preserves (2-)colimits.

The claim of this blog post is that this construction is the correct way to describe the sense in which various sorts of objects, such as finite graphs or finite -sets, have a “connected components” decomposition. This means, among other things, that the automorphism group of these objects decomposes as a product of wreath products in the above way based on which “connected components” appear.

**Weighted groupoid cardinality**

Recall that the groupoid cardinality of a groupoid is, if it converges, the sum

where denotes the set of isomorphism classes of objects in . One of its many pleasant features is that it behaves as nicely as possible with respect to homotopy quotients (in addition to disjoint unions and cartesian products): in particular, we have

(assuming that exists), and hence, if it converges, the groupoid cardinality of the free symmetric monoidal groupoid satisfies

.

This is our first pass at a categorical exponential formula. But we can do much better than this, thanks to the universal property of the free symmetric monoidal groupoid. Suppose is a groupoid and is a “weight function” from isomorphism classes of objects of to tuples of non-negative integers. Given such a tuple , write

(to be later interpreted as a term in a formal power series).

By the universal property, naturally extends (by additivity) to a function . Now instead of the groupoid cardinality we can consider the **weighted groupoid cardinality**, which we’ll denote using the integral notation

.

Provided that the appropriate operations are performed on weight functions, the weighted groupoid cardinality satisfies appropriate analogues of the properties of groupoid cardinality. For example, the groupoid cardinality property becomes the “Fubini theorem”

.

Now we have the following result, although the hypotheses on the weight function are not by any means maximally general.

**Categorical exponential formula:** Let be a groupoid and be a weight function as above such that converges. Extend to a weight function as above. Then converges, and

.

This interpretation of the exponential formula is, as far as I know, not in the literature. Does anyone know if it appears somewhere?

**Application to finite -sets**

To apply the categorical exponential formula to the case of finite -sets, take to be the symmetric monoidal groupoid of finite -sets, hence is the groupoid of finite transitive -sets. The weight function takes values in and is given by the cardinality of the underlying set.

What is the weighted groupoid cardinality of the groupoid of finite -sets? The subgroupoid of finite -sets with elements is the homotopy quotient

of the set of group homomorphisms by the conjugacy action of , so its weighted groupoid cardinality is . Hence

.

Similarly, what is the weighted groupoid cardinality of the groupoid of transitive finite -sets? The subgroupoid of transitive finite -sets with elements has an -fold cover, namely the groupoid of pointed transitive finite -sets with elements. is discrete: that is, objects in it have no nontrivial automorphisms. This is because a pointed transitive finite -set can canonically be written in the form , where is the stabilizer of the distinguished point (and so the distinguished point is the identity coset ). The automorphisms are all given by right multiplication by some (more specifically, by some in the normalizer ), and this fixes the identity coset iff , in which case it acts trivially. (This is an important point that was ignored in the previous discussion.)

Hence is the number of isomorphism classes of pointed transitive finite -sets with elements, and by taking the stabilizer of the distinguished point these are canonically in bijection with subgroups of of index . Writing for the number of such subgroups as above, and taking the -fold cover into consideration, then,

.

Hence

.

So the categorical exponential formula gives us the desired result.

on October 18, 2016 at 10:06 am |anonThe G-set automorphisms of G/H are right multiplication by elements of N_G(H)/H, not left multiplication by elements g of G. Also left multiplication by h in H generally does not act trivially on G/H. But the desired conclusion (automorphism fixes H implies acts trivially) still holds.

on October 19, 2016 at 11:59 am |Qiaochu YuanThanks for the correction! I intended to say “right multiplication,” and didn’t intend to imply that every element of worked.

on November 25, 2015 at 9:40 pm |Conjugacy classes of finite index subgroups | Annoying Precision[…] Previously we learned how to count the number of finite index subgroups of a finitely generated group . But for various purposes we might instead want to count conjugacy classes of finite index subgroups, e.g. if we wanted to count isomorphism classes of connected covers of a connected space with fundamental group . […]

on November 15, 2015 at 9:25 pm |Finite index subgroups of the modular group | Annoying Precision[…] Two weeks ago we proved the following formula. Let be a finitely generated subgroup and let be the number of subgroups of of index . Then […]

on November 5, 2015 at 2:44 am |Noam ZeilbergerI just wanted to say that I find this post (and the last) quite illuminating — thank you! There is a lot of literature on the combinatorics of rooted maps and hypermaps (= pointed transitive G-sets for different values of “cartographic group” G, sometimes with additional properties), and I’m only familiar with a bit of it, but I haven’t yet seen this kind of analysis. (The closest thing I’ve seen might be Samuel Vidal’s work on subgroups of the modular group PSL(2,Z) and trivalent diagrams/triangular maps, which is based on the theory of species.)

on November 5, 2015 at 11:34 am |Qiaochu YuanThanks for the comment; I haven’t been able to figure out whether this is worth writing up, so it’s good to know that it’s at least not super easily findable in the literature.