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:
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,
So the categorical exponential formula gives us the desired result.