31
$\begingroup$

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

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

$\endgroup$
6
  • 10
    $\begingroup$ "Arithmetical identities" like $(ab)^c = a^c b^c$, $a^{b+c} = a^b a^c$, and $(a^b)^c = a^{bc}$ can all be understood in the light of cartesian closed categories. The binomial identity $(a+b)^n = \sum_j \binom{n}{j} a^j b^{n-j}$ can understood in terms of extensive categories. $\endgroup$ Commented Nov 11, 2020 at 12:59
  • $\begingroup$ Interesting Todd, the fist identities I saw them as a direct application of Yoneda lemma. I didn't know the second one, thanks a lot for it. $\endgroup$ Commented Nov 11, 2020 at 15:07
  • 1
    $\begingroup$ Keywords for google: categorification, categorify $\endgroup$ Commented Nov 12, 2020 at 17:09
  • $\begingroup$ @user2831784 Aren't comments not indexed? $\endgroup$
    – wizzwizz4
    Commented Nov 15, 2020 at 12:51
  • 1
    $\begingroup$ @nasosev yes, I consider the monoid $ (\mathbb Z, \cdot ) $ $\endgroup$ Commented Nov 18, 2020 at 18:51

2 Answers 2

45
$\begingroup$

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:

  • 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 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$.

$\endgroup$
4
  • 1
    $\begingroup$ Really great answer, very instructive, it's exactly what I was looking for. Thanks a lot !! $\endgroup$ Commented Nov 12, 2020 at 10:15
  • $\begingroup$ this is absurd (read this with a positive connotation). how far can this go? can even ramanujan or gosper style identities and summations be categorized if you try hard enough? $\endgroup$ Commented Nov 14, 2020 at 1:05
  • 1
    $\begingroup$ @frogeyedpeas: $e$ turns out to be very special from a categorical point of view, being the groupoid cardinality of the groupoid of finite sets. I am not aware of any categorifications of identities involving $\pi$, by contrast. $\endgroup$ Commented Nov 14, 2020 at 1:44
  • $\begingroup$ If you can categorify $\log \left( 1 + iz \right) $ and $\log \left( 1 - iz \right)$. That might be sufficient (though perhaps impossible/hasn't been done yet?). (This is promising to me since $\log \left( 1 - z \right)$ has been categorified by you in the post and $e^{iz}$ implicitly has been categorified as per: math.stackexchange.com/questions/17311/categorification-of-pi). Combining those expressions gets $\arctan(z)$ and then $\frac{\pi}{4}$ feels within reach. I guess categorifying integration general might be another interesting strategy. This has opened up my eyes for sure! $\endgroup$ Commented Nov 14, 2020 at 5:02
26
$\begingroup$

A classic paper on this topic is Andreas Blass’s Seven trees in one (1994).

It starts with the observation that there is an explicit, constructive bijection between (finite) binary trees and seven-tuples of such trees: $T \cong T^7$. It then shows how this bijection can be obtained from the algebraic proof in $\mathbb{N}[t]$ that $t = 1 + t^2$ implies $t = t^7$. (Here $t = 1 + t^2$ expresses the defining property of finite binary trees: “each tree is either just a leaf, or a joined pair of two trees”.) Finally, it generalises this result, showing that polynomial identities in $\mathbb{N}[t]$ correspond to constructively-definable bijections between suitable polynomial functors on sets, or their initial algebras.

$\endgroup$
3
  • 2
    $\begingroup$ Thanks Peter for your answer. I know this paper. Thanks Peter. M. Fiore and T. Leinster gave an answer to a Blass's question in the above mentioned paper. $\endgroup$ Commented Nov 12, 2020 at 10:20
  • $\begingroup$ @Vincent: That’s the paper named and linked in the original question itself. $\endgroup$ Commented Nov 14, 2020 at 9:16
  • $\begingroup$ O I didn't realize that. Cool $\endgroup$
    – Vincent
    Commented Nov 14, 2020 at 13:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .