The categorical exponential formula

A monad is just a monoid in the category of endofunctors, what’s the problem? »

The categorical exponential formula

November 4, 2015 by Qiaochu Yuan

Yesterday I described the answer to the puzzle of 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 by sketching a proof of the following more general identity: if $G$ is a finitely generated group and $a_n$ is the number of subgroups of $G$ of index $n$ , then

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

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 $G$ -set (corresponding to the LHS) has a canonical “connected components” decomposition as a disjoint union of transitive $G$ -sets (corresponding to the RHS), which is the following.

Claim: The symmetric monoidal groupoid of finite $G$ -sets, with symmetric monoidal structure given by disjoint union, is the free symmetric monoidal groupoid on the groupoid of transitive finite $G$ -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 $X$ , the free symmetric monoidal groupoid on $X$ , which we’ll denote by $\exp(X)$ , can be defined in the following very suggestive-looking way:

$\displaystyle \exp(X) = \coprod_{n \ge 0} \frac{X^n}{S_n}$ .

Here by $\frac{X^n}{S_n}$ we mean the homotopy quotient or action groupoid of the action of $S_n$ on $X^n$ by permutations. Explicitly, beginning with the groupoid $X^n$ , whose objects we will write as $x_1 \otimes \dots \otimes x_n, x_i \in X$ , we add an extra morphism

$\displaystyle \sigma : x_1 \otimes \dots \otimes x_n \to x_{\sigma^{-1}(1)} \otimes \dots \otimes x_{\sigma^{-1}(n)}$

for every permutation $\sigma \in S_n$ , composing in the obvious way, and natural in the sense that, if $f_i : x_i \to y_i$ is a tuple of morphisms in $X$ , then

$\displaystyle \sigma \circ (f_1 \otimes \dots \otimes f_i) = (f_1 \otimes \dots \otimes f_i) \circ \sigma$

as morphisms $\displaystyle x_1 \otimes \dots \otimes x_i \to y_{\sigma^{-1}(1)} \otimes \dots \otimes y_{\sigma^{-1}(i)}$ .

The symmetric monoidal structure on $\exp(X)$ is the obvious thing implied by the above notation.

One way to describe $\exp(X)$ 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 $X$ . Given such a multiset, suppose that the object $x_i \in X$ occurs with multiplicity $m_i$ . Then the automorphism group of the corresponding object

$\displaystyle \bigotimes_i x_i^{\otimes m_i}$

is the product, over all $i$ , of the wreath products

$\displaystyle \text{Aut}(x_i) \wr S_{m_i} \cong \text{Aut}(x_i)^{m_i} \rtimes S_{m_i}$ .

Here $\text{Aut}(x_i)^{m_i}$ acts on $x_i^{\otimes m_i}$ componentwise, while $S_{m_i}$ acts by permutation.

Example. $\exp(1)$ , 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 $X$ is a finite set, then $\exp(X) \cong \exp(1)^X$ is the symmetric monoidal category of $X$ -indexed families of finite sets and bijections.

There are several ways in which $\exp(X)$ really deserves its name; for example, there is a natural isomorphism

$\displaystyle \exp(X \sqcup Y) = \exp(X) \times \exp(Y)$

which reflects the more general fact that $X \mapsto \exp(X)$ 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 $G$ -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 $X$ is, if it converges, the sum

$\displaystyle |X| = \sum_{x \in \pi_0(X)} \frac{1}{|\text{Aut}(x))|}$

where $\pi_0(X)$ denotes the set of isomorphism classes of objects in $X$ . 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

$\displaystyle \left| \frac{X^n}{S_n} \right| = \frac{|X|^n}{n!}$

(assuming that $|X|$ exists), and hence, if it converges, the groupoid cardinality of the free symmetric monoidal groupoid $\exp(X)$ satisfies

$\displaystyle |\exp(X)| = \exp(|X|)$ .

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 $X$ is a groupoid and $f : \pi_0(X) \to \mathbb{Z}_{\ge 0}^k$ is a “weight function” from isomorphism classes of objects of $X$ to tuples of non-negative integers. Given such a tuple $n = (n_1, \dots n_k)$ , write

$\displaystyle z^n = z_1^{n_1} \dots z_n^{n_k}$

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

By the universal property, $f$ naturally extends (by additivity) to a function $f : \pi_0(\exp(X)) \to \mathbb{Z}_{\ge 0}^k$ . Now instead of the groupoid cardinality we can consider the weighted groupoid cardinality, which we’ll denote using the integral notation

$\displaystyle \int_X z^{f} = \sum_{x \in \pi_0(X)} \frac{z^{f(x)}}{|\text{Aut}(x)|} \in \mathbb{R}[[z_1, \dots z_k]]$ .

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 $|X \times Y| = |X| |Y|$ becomes the “Fubini theorem”

$\displaystyle \int_{X \times Y} z^{f(x, y)} = \int_X \int_Y z^{f(x, y)}$ .

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

Categorical exponential formula: Let $X$ be a groupoid and $f : \pi_0(X) \to \mathbb{Z}_{\ge 0}^k$ be a weight function as above such that $\int_X z^f$ converges. Extend $f$ to a weight function $f : \pi_0(\exp(X)) \to \mathbb{Z}_{\ge 0}^k$ as above. Then $\int_{\exp(X)} z^f$ converges, and

$\displaystyle \int_{\exp(X)} z^f = \exp \int_X z^f$ .

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 $G$ -sets

To apply the categorical exponential formula to the case of finite $G$ -sets, take $\exp(X)$ to be the symmetric monoidal groupoid of finite $G$ -sets, hence $X$ is the groupoid of finite transitive $G$ -sets. The weight function $f$ takes values in $\mathbb{Z}_{\ge 0}$ and is given by the cardinality of the underlying set.

What is the weighted groupoid cardinality of the groupoid $\exp(X)$ of finite $G$ -sets? The subgroupoid $\exp(X)_n$ of finite $G$ -sets with $n$ elements is the homotopy quotient

$\displaystyle \exp(X)_n \cong \frac{\text{Hom}(G, S_n)}{S_n}$

of the set $\text{Hom}(G, S_n)$ of group homomorphisms $G \to S_n$ by the conjugacy action of $S_n$ , so its weighted groupoid cardinality is $\frac{|\text{Hom}(G, S_n)|}{n!} z^n$ . Hence

$\displaystyle \int_{\exp(X)} z^f = \sum_{n \ge 0} \frac{|\text{Hom}(G, S_n)|}{n!} z^n$ .

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

Hence $|\widetilde{X}_n|$ is the number of isomorphism classes of pointed transitive finite $G$ -sets with $n$ elements, and by taking the stabilizer of the distinguished point these are canonically in bijection with subgroups of $G$ of index $n$ . Writing $a_n$ for the number of such subgroups as above, and taking the $n$ -fold cover into consideration, then,

$\displaystyle \int_{X_n} z^f = \frac{1}{n} \int_{\widetilde{X}_n} z^f = \frac{a_n}{n} z^n$ .

Hence

$\displaystyle \exp \int_X z^f = \exp \left( \sum_{n \ge 1} \frac{a_n}{n} z^n \right)$ .

So the categorical exponential formula gives us the desired result.

Posted in math.CO, math.CT, math.GR | Tagged adjoint functors, MaBloWriMo | 6 Comments

6 Responses

on October 18, 2016 at 10:06 am | Reply anon

The 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 | Reply Qiaochu Yuan
  
  Thanks for the correction! I intended to say “right multiplication,” and didn’t intend to imply that every element of $G$ worked.
on November 25, 2015 at 9:40 pm | Reply 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 | Reply 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 | Reply Noam Zeilberger

I 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 | Reply Qiaochu Yuan
  
  Thanks 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.

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