I want to keep a mini class on category theory, and I would be very satisfied to have a class of examples in which some theorems - or just the reformulation in categorical terms - yields numerical results or answers.

To be explicit, I would have such an example, but it is too advanced for my target. Here it is: suppose $G$ is a finite group acting on a finite set $X$. Let $V(X)$ be the vector space freely generated by elements in $X$. What is the dimension of $V(X)^G$? Is it for example equal to $V(X^G)$?

Answer. Recall that orbits of $G$ writes as $G/H$ for some $H$, so that we can write $X= \cup_{i\in I} G/H_i$. Also, we have that $$V(X) = \bigoplus_{i \in I} V(G/H_i) = \bigoplus_{i \in I} \text{Ind}_{H_i}^G( \mathbb{C} ) $$

And now $$ \dim_{\mathbb{C}} V(X)^G = \dim_{\mathbb{C}} Hom_G(V(X),\mathbb{C}) = \sum_{i \in I} \dim_{\mathbb{C}} Hom_G( \text{Ind}_{H_i}^G(\mathbb{C}), \mathbb{C}) = $$ $$ = \sum_i \dim_{\mathbb{C}}Hom_{H_i}(\mathbb{C}, \mathbb{C}) = |I| = \#\{\text{orbits}\} = |X/G| $$

So that the frobenius adjunction yields a very numerical result, and indeed all this adjunction can be reformulated "numerically".

In general, a number of examples can arise when you consider adjoint functors between categories that have finite dimensional vector spaces.

I look for something that could be ok for people that know one or two years of university math. Something combinatorial, or number theoretical, would be perfect, for example; something about K-theory, definitely not. Hope I have not been too vague!


I give several examples involving groupoid cardinality in this MO answer. Here's another example which is not in that answer. First I'll quote the brief introduction to groupoid cardinality from over there:

To say it very tersely, if $X$ is a groupoid with at most countably many isomorphism classes of objects, such that each automorphism group $\text{Aut}(x)$ is finite, we can define its groupoid cardinality

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

if this sum converges, where $\pi_0(X)$ denotes the set of isomorphism classes of objects. Groupoids such that this sum converges are called tame. Groupoid cardinality has the following properties:

  • Normalization: $|\bullet| = 1$, where $\bullet$ denotes the terminal groupoid.
  • Additivity: $|X \sqcup Y| = |X| + |Y|$.
  • Multiplicativity: $|X \times Y| = |X| |Y|$.
  • Covering: If $f : X \to Y$ is an $n$-fold covering map of groupoids then $n |X| = |Y|$.

These properties (in fact just normalization, additivity and covering) uniquely determine $|X|$ for finite groupoids (finitely many objects and morphisms). $|X|$ is even countably additive and this together with normalization and covering determines it for tame groupoids.

Now here is the example. Dobinski's formula for the Bell numbers $B_n$, which count the number of partitions of an $n$-element set, is

$$B_n = \frac{1}{e} \sum_{k \ge 0} \frac{k^n}{k!}.$$

This formula can be given a "bijective proof" using groupoid cardinality as follows; what we will prove is that

$$B_n \sum_{k \ge 0} \frac{1}{k!} = \sum_{k \ge 0} \frac{k^n}{k!}$$

by calculating the groupoid cardinality of a specific groupoid in two different ways. Fix a set $N$ of size $n$. The groupoid we'll consider is the groupoid whose objects are maps $N \to K$ from $N$ to another finite set $K$, and whose morphisms are isomorphisms between these.

On the one hand, if the cardinality $|K| = k$ of $K$ is fixed, the groupoid of maps $N \to K$ and isomorphisms has a $k!$-fold cover given by the groupoid of maps $N \to K$ where $K$ is equipped with a total order and isomorphisms are required to preserve this order. This groupoid is discrete (has no nontrivial automorphisms) and has exactly $k^n$ isomorphism classes of objects, and the groupoid of maps $N \to K$ is the quotient of it by the action of $\text{Aut}(K)$, so the groupoid cardinality is $\frac{k^n}{k!}$. Summing over all $k$ produces the RHS.

On the other hand, a map $f : N \to K$ produces a partition of $N$ given by its fibers, together with a finite set given by the complement of the image of $f$. Our groupoid is in fact equivalent to the groupoid whose objects are pairs consisting of a partition of $N$ and a finite set, and whose morphisms are isomorphisms of the finite set only (the morphisms involving the partition are "canceled out" by the fact that, if the image $K' \subseteq K$ of $f$ is fixed, $\text{Aut}(K')$ acts freely on the set of surjections $N \to K'$, with quotient the set of partitions of $N$ into $|K'|$ nonempty blocks). This groupoid has groupoid cardinality $B_n \sum_{k \ge 0} \frac{1}{k!}$ which is the LHS as desired.

Performing this second identification more carefully gives a bijective proof (in the ordinary, non-groupoid sense) of the identity

$$k^n = \sum_{j=0}^n \left\{ n \atop j \right\} (k)_j$$

where $(k)_j = k(k-1) \dots (k-(j-1))$ is the falling factorial and $\left\{ n \atop j \right\}$ is the Stirling number of the second kind counting the number of partitions of $n$ into $j$ parts; this identity corresponds exactly to counting functions $f : N \to K$ based on the size $j$ of the image. Substituting this expression into $\sum_{k \ge 0} \frac{k^n}{k!}$ gives a "traditional" proof of Dobinski's formula, but to my mind the groupoid cardinality argument is cleaner because it explains the meaning of this proof.

  • $\begingroup$ Cool! That's exactly what I was thinking for "combinatorial answer": the main transformation and concepts are heavily involved. I was a bit confused by the use of "cardinality" and $1/|Aut(x) |$ but ok, that's just a name. I then saw that covers somehow should have smaller cardinality than original objects, is this why are we using 1/aut ? $\endgroup$ – Andrea Marino Dec 25 '20 at 14:30
  • $\begingroup$ However, I'd also love to see if someone have a number theoretical answer; what I have in mind is that some Galois questions in algebraic number theory could be categorified and solved by abstract means, then come back via grothendieck ring or something like that. Maybe this would be advanced but it can be simplified in some special cases. Do you think this deserves a separate thread? $\endgroup$ – Andrea Marino Dec 25 '20 at 14:36
  • $\begingroup$ @Andrea: I guess you could ask a separate quesrion, but this seems more advanced than the group action example you give. $\endgroup$ – Qiaochu Yuan Dec 25 '20 at 18:21
  • $\begingroup$ Yes, I kind of changed my mind from the beginning. For example, the case of the group if you take $G=Z/nZ$ can be stated almost without defining representations, but taking the category of "twisted vector spaces $V = \oplus_{i=0}^{n-1} V_i$ , where $V_i$ basically represent the component where j acts as $\zeta^{ji}$. Maybe something similar is possible for advanced examples. However, about combinatorial world your example is perfect. I like your answers :) $\endgroup$ – Andrea Marino Dec 25 '20 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.