My question concerns categorical "proofs" or "guessing" of arithmetical identities using category theory. I’m not at all a specialist of CT but I try to put my hands on and to understand something in this fascinating subject. Trying to prove something concrete, the exercise was to prove the identity
$$ \gcd(n,m) \cdot \operatorname{lcm}(n,m) = n\cdot m$$
Using the concepts of product and coproduct in a specific category (objects are integers and arrows is "divisibility") I've been able to prove it with very minimalistic assumptions, only the notion of divisibility of integers. No use of prime numbers or unique factorization with primes or other specific theorems like Bezout theorem, etc…
I'm wondering if someone has other examples like that one. Someone gave me the reference
- Marcelo Fiore, Tom Leinster, Objects of Categories as Complex Numbers, Advances in Mathematics 190 (2005), 264-277, doi:10.1016/j.aim.2004.01.002, arXiv:math/0212377,
which is interesting but it doesn't really answer my question. In that paper, if I've correctly understood, they show that if something is true with complex numbers it is true in more general categories.
I would be interested if someone has some "simple" examples of concrete applications of CT proving or "guessing" arithmetical identities
Thanks a lot for any clue
Best Answer
I don't know what counts as an "arithmetical identity" for you, but there's a rich family of interesting examples coming from groupoid cardinality. 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:
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 are a family of interesting examples of identities proven by computing a groupoid cardinality in two different ways. Let $X$ be a finite set and consider the groupoid of families of finite sets over $X$. On the one hand this is $\text{FinSet}^X$, so it has groupoid cardinality
$$|\text{FinSet}|^{|X|} = \left( \sum_{n \ge 0} \frac{1}{n!} \right)^{|X|} = e^{|X|}.$$
On the other hand this is the groupoid $\text{FinSet}/X$ of finite sets equipped with a map to $X$. (I'm being a little cavalier about notation here; I need the map to $X$ to not necessarily be a bijection but I am only considering bijections as morphisms so this is not really a slice category strictly speaking. What I am really doing is naming various categories and then implicitly taking their cores, I guess.) The groupoid of sets of cardinality $n$ equipped with a map to $X$ has an $n!$-fold cover given by the groupoid of totally ordered sets of cardinality $n$ equipped with a map to $X$, which is discrete and has cardinality $|X|^n$, where the $n!$-foldness comes from the action of the symmetric group $S_n$. The covering property then gives that this groupoid has groupoid cardinality $\frac{|X|^n}{n!}$, which gives
$$e^{|X|} = \sum_{n \ge 0} \frac{|X|^n}{n!}.$$
So we've described an equivalence of groupoids (between $\text{FinSet}^X$ and $\text{FinSet}/X$) which categorifies a familiar basic property of the exponential function, and in particular which gives a conceptual interpretation of the terms of the Taylor series. We similarly have $\text{FinSet}^{X \sqcup Y} \cong \text{FinSet}^X \times \text{FinSet}^Y$ which gives
$$e^{|X| + |Y|} = e^{|X|} e^{|Y|}.$$
Unwinding what this gives in terms of the groupoid of finite sets equipped with a map to $X \sqcup Y$, we get that every set equipped with a map to $X \sqcup Y$ canonically disconnects into two pieces, its fiber over $X$ and its fiber over $Y$, which gives an equivalence $\text{FinSet}/(X \sqcup Y) \cong \text{FinSet}/X \times \text{FinSet}/Y$; this reflects the fact that $\text{FinSet}$ (the usual one, with all functions as morphisms) is an extensive category. The equivalence $\text{FinSet}^X \cong \text{FinSet}/X$ reflects the fact that $\text{FinSet}$ is the "classifying space of finite sets," and can be thought of as a special case of the Grothendieck construction.
One of my favorite generalizations of this circle of ideas is that $X$ can be replaced with a groupoid. In this case we can consider the free symmetric monoidal groupoid on $X$, which explicitly is given by
$$\text{Sym}(X) = \bigsqcup_{n \ge 0} \frac{X^n}{S_n}$$
where the fraction notation denotes taking the action groupoid / homotopy quotient. As the notation suggests, if $X$ is tame we have
$$|\text{Sym}(X)| = \sum_{n \ge 0} \frac{|X|^n}{n!}$$
and equivalences $\text{Sym}(X \sqcup Y) \cong \text{Sym}(X) \times \text{Sym}(Y)$ as before. The connection to the previous construction is that if $X$ is a finite set then the free symmetric monoidal groupoid on $X$ is $\text{FinSet}^X \cong \text{FinSet}/X$ (equipped with disjoint union), and in particular $\text{FinSet}$ itself (the groupoid of finite sets and bijections) is the free symmetric monoidal groupoid on a point.
The significance of this construction at this level of generality is that many groupoids of finite sets with extra structure (which can equivalently be thought of as combinatorial species) are free symmetric monoidal groupoids (with respect to disjoint union); said in a more down-to-earth way, their objects have canonical "connected component" decompositions. The identity $|\text{Sym}(X)| = e^{|X|}$, possibly with some weights thrown in, then becomes a version of the exponential formula in combinatorics.
There are many examples of this; I'll limit myself to one of my favorites, which is taken from this blog post and which also appears as Exercise 5.13a in Stanley's Enumerative Combinatorics, Vol. II. Let $\pi$ be a finitely generated group and consider the groupoid $[B \pi, \text{FinSet}]$ of finite sets equipped with an action of $\pi$. This groupoid is usually not tame, but it is always "weighted tame" in the sense that we can consider its groupoid cardinality weighted by a factor of $x^n$ for finite sets of size $n$ and the coefficients of the corresponding generating function converge (and in fact are sums of finitely many rational numbers and so are rational). We can compute its weighted groupoid cardinality in two ways as follows.
On the one hand, as above, the groupoid of actions of $\pi$ on a set of size $n$ has an $n!$-fold cover given by the groupoid of actions of $\pi$ on a totally ordered set of size $n$, which is discrete with cardinality $|\text{Hom}(\pi, S_n)|$, where again the $n!$-foldness comes from the action of $S_n$. Said another way, the groupoid is equivalent to the action groupoid / homotopy quotient of the action of $S_n$ by conjugation on the set of homomorphisms $\pi \to S_n$. It follows that the weighted groupoid cardinality is
$$\sum_{n \ge 0} \frac{|\text{Hom}(\pi, S_n)|}{n!} x^n.$$
On the other hand, this groupoid is free symmetric monoidal: every $\pi$-set has a canonical decomposition into transitive $\pi$-sets. The groupoid of transitive actions of $\pi$ on a set of size $n$ has an $n$-fold cover given by the groupoid of transitive actions of $\pi$ on a set of size $n$ with a basepoint. The stabilizer of such a basepoint is a subgroup of $\pi$ of index $n$, and this is an equivalence of groupoids; in other words, this groupoid is discrete and has size the number $s_n(\pi)$ of subgroups of $\pi$ of index $n$. It follows that the weighted groupoid cardinality is
$$\exp \left( \sum_{n \ge 1} \frac{s_n(\pi)}{n} x^n \right).$$
So we get an identity
$$\sum_{n \ge 0} \frac{|\text{Hom}(\pi, S_n)|}{n!} x^n = \exp \left( \sum_{n \ge 1} \frac{s_n(\pi)}{n} x^n \right).$$
Specializing to various finitely generated groups $\pi$ gives various interesting identities, as I explain in this blog post. For example if $\pi = \mathbb{Z}$ we are considering the groupoid of finite sets equipped with a bijection, and we get
$$\frac{1}{1 - x} = \sum_{n \ge 0} x^n = \exp \left( \sum_{n \ge 1} \frac{x^n}{n} \right) = \exp \log \frac{1}{1 - x}.$$
This identity expresses the uniqueness of cycle decomposition, and among other things gives a conceptual interpretation of the Taylor series of the logarithm (it is expressing the weighted groupoid cardinality of the groupoid of cycles, or equivalently the groupoid of finite transitive $\mathbb{Z}$-sets). I also take $\pi = C_k, F_2, \mathbb{Z}^2, \pi_1(\Sigma_g)$ in the blog post above. In this blog post I take $\pi = \Gamma \cong C_2 \ast C_3$ to be the modular group, which gives a generating function
$$\sum_{n \ge 1} \frac{s_n(\Gamma)}{n} x^n = \log \left( \sum_{n \ge 0} \frac{o_2(S_n) o_3(S_n)}{n!} x^n \right)$$
for the number of subgroups of $\Gamma$ of index $n$ (A005133 on the OEIS), where $o_k(S_n)$ denotes the number of elements of $S_n$ of order dividing $k$.