The n-Category Café

Regular readers of this blog will find much of what I’m about to say familiar — though I’ve tried to say it slightly differently, so that it’s not too familiar. But mostly, I’ve tried to write it so that it makes sense to those who’ve never read this blog before.

Background

I could launch in and give the definition of the magnitude of an enriched category straight away. It would then look mysterious and unmotivated. The following background story should dispel the mystery, even though it’s not strictly necessary for what follows.

Here are two elementary combinatorial formulas.

1. Take a diagram $$\begin{matrix} R &\to &S \\ \downarrow& & \\ T& & \end{matrix}$$ of finite sets and injective maps. Then the cardinality of the pushout is given by the formula $$|S +_R T| = |S| + |T| - |R|.$$
2. Take a finite group $G$ acting freely on a finite set $S$. Then the cardinality of the set of orbits is given by the formula $$|S/G| = \frac{1}{order(G)} |S|.$$

In each case, we start with a finite category $A$ and a functor $X: A \to FinSet$. (In the second case, $A$ is the one-object category corresponding to the group $G$.) In each case, we give a formula for the cardinality of the colimit of $X$ as a weighted sum of the cardinalities of the individual sets $X(a)$: $$|\lim_{\to A} X| = \sum_{a \in A} w(a) |X(a)|.$$ Here $(w(a))_{a \in A}$ is some family of rational numbers, independent of $X$. In each case, the formula is only asserted to hold when $X$ is a ‘special’ functor: those are the conditions in italics. It’s clear that no such formula could hold for all functors $X$, since usually $|\displaystyle\lim_{\to A} X|$ will depend on the effect of $X$ on morphisms.

There’s now an obvious question. Can we do the same for an arbitrary finite category $A$? In other words, for an arbitrary finite category $A$, can we find a formula for the cardinality of the colimit of any ‘special’ functor $X: A \to FinSet$, as a rational linear combination of the cardinalities $|X(a)|$?

Part of the answer involves defining ‘special’. I’m not going to tell that part of the story. (You can look it up here.) But whatever a ‘special’ functor is, it surely includes representables. So let’s see what the formula $$|\lim_{\to A} X| = \sum_{a \in A} w(a) |X(a)|.$$ says in the case when $X$ is representable.

It’s an easy exercise to show that the colimit of a representable is a one-element set. So, the left-hand side is 1. Taking $X = A(a, -)$ and changing the name of the variable over which the sum runs, the formula says $$\sum_{b \in A} |A(a, b)| w(b) = 1.$$ So here’s what we’ve learned: if there’s a weighted-sum formula for the cardinality of the colimit of any ‘special’ functor $A \to FinSet$, and if ‘special’ includes representable, then the weights $w(a)$ must satisfy this last equation for each $a \in A$. Since there are as many equations as there are unknowns $w(a)$, there’s usually a unique solution $w$.

Having got this far, you might start wondering about the total weight of the category, $\sum w(a)$. Why might you wonder that? One reason is that even for functors $X: A \to FinSet$ that aren’t special, the formula $$\sum_{a \in A} w(a) |X(a)|$$ still computes something — and the sum of the weights $\sum w(a)$ is that ‘something’ in the case that $X$ has constant value $1$.

(For category theorists at least, it’s particularly natural to think about the functor with constant value $1$: the functors $A \to Set$ correspond to the discrete opfibrations over $A$, and the functor with constant value $1$ is what corresponds to the identity opfibration, $id: A \to A$.)

That’s the end of the background story. You’ll hear echoes of it in what follows, and I hope it will provide motivation, but I won’t mention it explicitly again.

The magnitude of a matrix

This whole ‘size’ programme is about decategorification. It’s about turning a structure into a number that ‘counts’ it. To define the magnitude of an enriched category, we’ll use a certain way of turning a matrix into a number. Of course, we all know several ways of doing this, such as taking the determinant or trace. But this one is less familiar.

We’ll work with matrices over a rig $k$, assumed commutative. But to speak of an ‘$m \times n$ matrix’ implicitly puts an order on its rows and columns, and I don’t want to do this; instead, I’ll index the rows and columns by abstract finite sets. If $I$ and $J$ are finite sets then an $I \times J$ matrix over the rig $k$ amounts to a function $I \times J \to k$.

Given a finite set, write $u_I \in k^I$ for the column vector all of whose entries are $1$. Write $\zeta^*$ for the transpose of a matrix $\zeta$.

Definition  Let $\zeta$ be an $I \times J$ matrix over $k$. A weighting on $\zeta$ is a column vector $w$ such that $$\zeta w = u_I.$$ A coweighting is a row vector $v$ such that $$v \zeta = u_J^*.$$

Put another way, a weighting on $\zeta$ is a family $(w(j))_{j \in J}$ of elements of $k$ such that $$\sum_j \zeta(i, j) w(j) = 1$$ for each $i \in I$.

A matrix may have no weightings, exactly one, or many. The same goes for coweightings. But there’s a crucial constraint:

Lemma  Let $\zeta$ be an $I \times J$ matrix. Let $w$ be a weighting on $\zeta$, and $v$ a coweighting. Then $$\sum_{i \in I} v(i) = \sum_{j \in J} w(j).$$

In other words: the total weight is the total coweight. The proof is one line of algebra. If you want to look it up, you’ll find it — along with much of the rest of this post — written up in Section 1 of my paper The magnitude of metric spaces.

It follows that, for a matrix with both a weighting and a coweighting, the total weight is independent of the weighting chosen. For if $w$ and $\tilde{w}$ are weightings then, choosing any coweighting $v$, we have $$\sum w(j) = \sum v(i) = \sum \tilde{w}(j).$$ This makes the following definition possible.

Definition  A matrix $\zeta$ has magnitude if it has at least one weighting and at least one coweighting. In that case, its magnitude is $$|\zeta| = \sum w(j) = \sum v(i)$$ for any weighting $w$ and coweighting $v$.

We’ll only need to talk about the magnitude of square matrices. Moreover, the rig $k$ will usually be an infinite field. A generic square matrix over an infinite field is invertible, since the probability of a linear dependence between two columns is zero. So it’s especially worth thinking about magnitude for invertible matrices $\zeta$.

And it turns out that the magnitude of invertible matrices is very simple. Any invertible matrix $\zeta$ has a unique weighting, since $$\zeta w = u_I \iff w = \zeta^{-1} u_I.$$ Similarly, $\zeta$ has a unique coweighting. In fact:

Lemma  Every invertible matrix has magnitude. If $\zeta$ is an $I \times I$ invertible matrix then, writing $\mu = \zeta^{-1}$, we have $$|\zeta| = \sum_{j, i \in I} \mu(j, i).$$

If you remember no other part of this section, remember this.

The magnitude of an enriched category

Let $V$ be a monoidal category. We’re going to define the magnitude of a category enriched in $V$, or $V$-category for short.

There are two caveats. First, we’re only going to attempt this for $V$-categories with finitely many objects. So the large categories of the type that most people associate with category theory — groups, topological spaces, etc — are beside the point. We’re more interested in things like a poset regarded as a category, or a group regarded as a one-object category: categories as mathematical structures, not categories of mathematical structures.

The other caveat is that in order to get a notion of the size of a category enriched in $V$, we’ll need to start from a notion of the size of an object of $V$.

So, we assume given a rig $k$ and a function $$| \cdot | : ob(V) \to k,$$ to be thought of as assigning to each object $X \in V$ its ‘size’ $|X|$. We demand that size is isomorphism-invariant: if $X \cong Y$ then $|X| = |Y|$. We also demand that it is a monoid homomorphism: $$| X \otimes Y | = |X| \cdot |Y|, \quad |I| = 1.$$

Let $A$ be a $V$-category with finitely many objects. Define the similarity matrix of $A$ to be the $ob(A) \times ob(A)$ matrix $\zeta_A$ over $k$ given by $$|\zeta_A(a, b)| = |A(a, b)|.$$

Definition  The $V$-category $A$ has magnitude if the matrix $\zeta_A$ has magnitude. In that case, the magnitude of $A$ is the magnitude of $\zeta_A$: $$|A| = |\zeta_A|.$$

That’s the definition. The rest of this post explores its implications.

Turning the dial

Here I’ll turn the dial to several different values of $V$, explaining what magnitude means for each. Actually, some positions on the dial represent unexplored territory, in which case I can’t explain what it means. I’ll indicate the present state of knowledge, too, hoping to tempt you to increase it.

$V = FinSet$

A $V$-category is an ordinary category with finite homsets. Put $k = \mathbb{Q}$, and define $$|\cdot|: ob(V) \to k$$ by taking $|X|$ to be the cardinality of $X$, for a finite set $X$. We get a rational-valued invariant of (most) finite categories: magnitude.

The magnitude of finite categories is compatible with all sorts of existing size-like invariants. The simplest example is that the cardinality of a set is equal to the magnitude of the resulting discrete category. When a monoid is viewed as a one-object category, the magnitude of the category is the reciprocal of the order of the monoid. (There are good reasons for that reciprocal to be there.) The Euler characteristic of a directed graph is the magnitude of the free category on it.

Some more sophisticated compatibility theorems hold, showing, for instance, how the notion of the Euler characteristic of an orbifold arises from the notion of the magnitude of a category. But perhaps most significant is the following. Every small category $A$ gives rise to a topological space, the geometric realization of its simplicial nerve. And under certain hypotheses on $A$, the Euler characteristic of that space is equal to the magnitude of the category. For this reason, the magnitude of a category is also called its Euler characteristic.

All this and more was set out in a paper I wrote a few years ago: The Euler characteristic of a category. It’s been taken in different directions by a bunch of people:

• Clemens Berger and Tom Leinster, The Euler characteristic of a category as the sum of a divergent series
• Tom Fiore, Wolfgang Lück, Roman Sauer, Finiteness obstructions and Euler characteristics of categories
• Tom Fiore, Wolfgang Lück, Roman Sauer, Euler characteristics of categories and homotopy colimits
• Martin Wedel Jacobsen, Jesper Møller, Euler characteristics of $p$-subgroup categories
• Kazunori Noguchi, The Euler characteristic of infinite acyclic categories with filtrations
• Kazunori Noguchi, The Euler characteristics of categories and the barycentric subdivision

Still, all this has happened quite recently, and I’m sure there’s a lot that no one yet understands. So my verdict on it is:

Status:  Partly explored.

$V = \{ true,   false \}$

Here $V$ is the category with two objects, $true$ and $false$, and one non-identity arrow, $$false \to true.$$ The monoidal structure is conjunction (the logical operator ‘and’), with $true$ as its unit. A $V$-category is, then, a partially ordered set. (Strictly speaking it’s a preordered set, but it makes no difference up to equivalence.)

Put $k = \mathbb{Z}$ and define $$|\cdot|: ob(V) \to k$$ by $$|false| = 0, \quad |true| = 1.$$ Then we obtain a notion of the magnitude of a poset. It’s an integer-valued invariant, and can also be reasonably be called the Euler characteristic. In fact, there’s an alternating-sum formula: $$|A| = \sum_{n \geq 0} (-1)^n |\{ \text{chains}  a_0 < \cdots < a_n   \text{in}  A\}|.$$ It’s also equal to the magnitude, or Euler characteristic, of the category corresponding to the poset. And if you know about Möbius inversion for posets, it’s equal to the sum of all the values of the Möbius function, $\sum_{a, b \in A} \mu(a, b)$.

This invariant has been known to combinatorialists, and the developers of poset homology, for decades.

Status:  Very well explored.

$V = ([0, \infty], \geq, +, 0)$

This is the poset $([0, \infty], \geq)$ with monoidal structure given by addition. As Lawvere observed long ago, a $V$-category is a (generalized) metric space. We take $k = \mathbb{R}$ and define $$|x| = e^{-x}$$ ($x \in \mathbb{R}$). (Since $|\cdot|$ is supposed to convert tensor product in $V$ into multiplication, we don’t have much choice in the matter.)

This gives a notion of the magnitude of a finite metric space. This has played a quiet role since the mid-1990s in the literature on measuring biodiversity, but seems only to have been studied in mathematics in the last few years. I wrote a paper about the magnitude of metric spaces in December, and gave a roundup of available resources on the subject here.

Its geometric significance becomes clear when we pass from finite to infinite metric spaces. There are several ways you might think of extending the definition of magnitude from finite to infinite spaces. Roughly speaking, the paper Positive definite metric spaces by Mark Meckes shows that they all give the same answer. This might not be true in total generality, but (for instance) there’s a good solid definition of the magnitude of a compact subset of $\mathbb{R}^n$. For example, the magnitude of a line segment of length $\ell$ is $1 + \ell/2$.

Simon Willerton and I have a conjecture that claims to give the magnitude of any compact convex subset of $\mathbb{R}^n$ in terms of some classical geometric invariants. For example, it predicts that the magnitude of a nonempty compact convex subset $A \subseteq \mathbb{R}^2$ is $$1 + \frac{1}{4} perimeter(A) + \frac{1}{2\pi} area(A).$$ In some ways, we have quite compelling evidence for this. But in another way, we have almost no evidence at all: apart from subsets of the line, there is not a single convex subset of $\mathbb{R}^n$ whose magnitude is known. This is a major obstacle to progress.

Status:  Some areas explored, but large parts of the territory cut off by a mountain range.

$V = ([0, \infty], \geq, max, 0)$

This is the same as the last example except that the monoidal structure has changed: $+$ has become $max$. What this means is that $V$-categories are now ultrametric spaces, that is, metric spaces satisfying the stronger triangle inequality $$\max\{ d(a, b), d(b, c) \} \geq d(a, c).$$ (The $p$-adic integers are an important example.) Mark Meckes has worked out probably everything there is to be worked out about the magnitude of finite ultrametric spaces, in work that’s unpublished so far. I’ll let Mark explain this if he feels like it.

Status:  Well explored.

$V = FDVect$

Take the category of finite-dimensional vector spaces, say over $\mathbb{C}$. Put $k = \mathbb{Q}$, and for a vector space $X$, define $|X| = \dim X$. Then magnitude is a rational-valued invariant of finite $\mathbb{C}$-linear categories.

Catharina Stroppel and I found out a little bit about the magnitude of linear categories. Here’s a sample theorem. Take an associative algebra R over $\mathbb{C}$, and let $A$ be the $\mathbb{C}$-linear category of projective indecomposable $R$-modules — or rather, a skeleton thereof. Then $A$ is finite.

Theorem: if $R$ is Koszul and has finite dimension and global dimension, then $$|A| = \sum_{i = 0}^\infty (-1)^i \dim (Ext_R^i (R_0, R_0)).$$ (Here $R_0$ is the degree $0$ part of $R$.) This result suggests that the magnitude of a linear category could, again, reasonably be called the Euler characteristic.

We came up with a couple more results, but still:

Status:  Only slightly explored.

$V = FinSet^{\mathbb{N}}$

This whole programme is about glorified counting, and counting tends to work better when things are finite. Nevertheless, finiteness conditions can sometimes be annoyingly restrictive. Consider, for instance, the free category on a directed graph. Even if the graph is finite, the free category on it might not be — it will be infinite if the graph contains circuits. This position on the dial provides a way to handle this situation, nevertheless.

The additive structure on $\mathbb{N}$ gives a monoidal structure to the category $V = FinSet^{\mathbb{N}}$ of sequences of finite sets: $$(X \otimes Y)_n = \sum_{k + m = n} X_k \times Y_m.$$ A $V$-category is a category in which every map $f$ has a degree $deg(f) \in \mathbb{N}$, with $deg(g \circ f) = deg(g) + deg(f)$. We might say that a $V$-category is an ‘$\mathbb{N}$-graded category’.

Take $k = \mathbb{Q}[t]$, the ring of formal power series over $\mathbb{Q}$. Define $$|X| = \sum_{n = 0}^\infty |X_n| t^n.$$ Then we obtain a $\mathbb{Q}[t]$-valued invariant of $\mathbb{N}$-graded categories.

Let’s come back to that problem of free categories. Take a finite graph $G$, and let $A$ be the free category on $G$. Each map in $A$ is a path in $G$, so naturally has a degree: the length of that path. So $A$ is naturally $\mathbb{N}$-graded. And it’s a little theorem that its magnitude is $$|A| = V + E t$$ where $V$ is the number of vertices in $G$ and $E$ is the number of edges. Putting $t = -1$ gives $V - E$, the Euler characteristic of $G$.

There seems to be some connection between this calculation and the kind of arguments in a paper by Kazunori Noguchi, The Euler characteristic of infinite acyclic categories with filtrations.

I don’t know how much there is to say about $\mathbb{N}$-graded categories, so I’ll neutrally pronounce:

Status:  Partly explored.

$V = FDVect^{\mathbb{N}}$

This example is similar: a $V$-category is a graded linear category. Since graded vector spaces are important, I expect there are interesting results to be found here. But I haven’t looked.

Status:  Completely unexplored.

$V = Ch$, $V = SSet$, $V = Top$

These three $V$s are all categories of spaces. In each case, the function $$|\cdot|: ob(V) \to k$$ is Euler characteristic (taking $k = \mathbb{Q}$). We obtain notions of the magnitude of a differential graded category, of a simplicial category, and of a topologically-enriched category. (I’m not bothering to mention the necessary finiteness conditions.) But as far as I know, no one’s ever looked into this.

Status:  Completely unexplored.

$V = n Cat$

Recall the strategy: starting from a function $$|\cdot|: ob(V) \to k$$ we obtain a function $$|\cdot|: ob(V\text{-}Cat) \to k,$$ namely, magnitude. (To be precise, magnitude is a partially-defined function, and it only stands a chance of being defined on $V$-categories with finite object-sets. But let me gloss over that.) So we can iterate.

In particular, we can iterate starting with $V = Set = 0 Cat$. First this gives us the notion of the magnitude of a (1-)category. Then it gives us the notion of the magnitude of a $Cat$-category, that is, a 2-category. Continuing, it gives us the notion of the magnitude of an $n$-category.

The only example I know is this. For each $n$ there is an $n$-category that deserves to be called $S^n$, consisting of two parallel $n$-morphisms. For example, $S^1$ is the 1-category $\bullet \stackrel{\to}{\to} \bullet$. It’s not hard to show that $$|S^n| = 1 + (-1)^n,$$ which is the same as the Euler characteristic of the topological $n$-sphere.

There must be much, much more to say about the magnitude of finite $n$-categories.

Status:  Barely explored.

$V = \infty Cat$

This is a tricky one. The category $\infty Cat$ of $\infty$-categories ($\omega$-categories) is a fixed point of the process $V \mapsto V\text{-}Cat$. (In fact, it’s the terminal coalgebra.) So our usual procedure doesn’t help at all: in order to get a notion of size for $V$-categories, we’d need a notion of size for objects of $V$… but in this case, $V$-categories and objects of $V$ are the same thing!

But what we can hope for is an invariant $|\cdot|$ of finite $\infty$-categories which, when fed into our procedure, produces the same invariant $|\cdot|$.

This basically says the following. Let $A$ be a finite $\infty$-category. For objects $a, b$ of $A$, the hom-thing $A(a, b)$ is also a finite $\infty$-category. Let $\zeta$ be the $ob(A) \times ob(A)$ matrix whose $(a, b)$-entry is $|Hom(a, b)|$. Suppose that $\zeta$ is invertible over $\mathbb{Q}$, as it usually will be, and write $\mu = \zeta^{-1}$. Then we demand that $$|A| = \sum_{a, b} \mu(a, b).$$ We seek an invariant $|\cdot|$ satisfying this equation for every $A$.

I’ve got as far as posing that problem, but I have no idea what the answer might be. I’d love it if someone could solve it.

Status: Completely unexplored.