The n-Category Café

Recap

First, a quick recap of last time. A weighting on a finite category $A$ is a function $w_A: ob(A) \to \mathbb{Q}$ such that

$$\sum_{a \in A} |A(b, a)| w_A(a) = 1$$

for all $b \in A$. This is a system of linear equations with as many equations as unknowns, so there’s usually a unique weighting $w_A$ on $A$. The magnitude of a functor $X: A \to FinSet$ is defined to be

$$|X| = \sum_a w_A(a) |X(a)| \in \mathbb{Q}.$$

This is equal to the cardinality of the colimit of $X$ when $X$ is a coproduct of representables. Examples of this equality include the inclusion-exclusion principle and the simple formula for the number of orbits of a free action of a group on a finite set. But even when $X$ isn’t a coproduct of representables, $|X|$ means something, and I gave a few examples involving entropy.

There’s also a definition of the magnitude (or Euler characteristic) of a finite category $A$: it’s the total weight

$$|A| = \sum_{a \in A} w_A(a).$$

This is equal to the magnitude of the constant functor $\Delta 1: A \to FinSet$ that sends everything to the one-element set.

But in the other direction, the definition of the magnitude of a set-valued functor can also be seen as a special case of the definition of the magnitude of a category: $|X|$ is equal to the magnitude of $\mathbb{E}(X)$, the category of elements of $X$. In a comment on the last post, Mike Shulman pointed to work of his and Kate Ponto’s showing that it’s also equal to the Euler characteristic of the homotopy colimit of $X$, under some fairly mild additional hypotheses on $A$.

Aside   The two results in the last paragraph are easily deduced from each other, up to some small changes in the hypotheses on $A$. This isn’t entirely surprising, as $\mathbb{E}(X)$ is the colax colimit of $X: A \to Cat$ (where I’ve changed the codomain of $X$ from $Set$ to $Cat$ by viewing sets as discrete categories). In any case, Thomason proved that the nerve of $\mathbb{E}(X)$ is homotopy equivalent to $hocolim(X)$, so in particular, they have the same Euler characteristic. But the Euler characteristic of the nerve of a category is its magnitude (under hypotheses), so

$$|\mathbb{E}(X)| = \chi(hocolim(X)).$$

Thus, if we know that one side of this equation is equal to $|X|$, then so is the other. A few more details of this argument are in my comment here.

But there’s a but! Whereas magnitude can be defined for categories as well as set-valued functors, it will turn out that comagnitude can’t be, as far as I can see. We’ll get to this later.

The cardinality of a limit

Let’s play a dual game to the one we played last time: given a finite category $A$ and a functor $X: A \to FinSet$, can we find a formula for the cardinality of the limit of $X$, in terms of $A$ and the cardinalities of the sets $X(a)$ ($a \in A$) only?

Of course, we can’t in general: $|lim X|$ depends on what $X$ does to the maps in $A$ as well as the objects. But there are significant cases where we can:

Examples

• If $A$ is the two-object discrete category $(0 \quad 1)$ then a functor $X: A \to FinSet$ is a pair $(X_0, X_1)$ of finite sets, and

  $$|X_0 \times X_1| = |X_0| \times |X_1|.$$

• What about pullbacks? Take finite sets and functions

  $$X_0 \stackrel{f}{\rightarrow} X_1 \stackrel{g}{\leftarrow} X_2.$$

  Suppose $f$ is uniform, meaning that all its fibres are isomorphic: $f^{-1}(y) \cong f^{-1}(y')$ for all $y, y' \in X_1$. This is equivalent to the condition that $f$ is a product projection $X_1 \times F \to X_1$, a condition I talked about here, using the word “projection” instead of “uniform”. Using the uniformity of $f$, it’s a little exercise to show that the pullback of our diagram has cardinality

  $$\frac{{|X_0|} \cdot {|X_2|}}{|X_1|}.$$

• In a similar way, we can show that the equalizer of a pair of functions $f, g: X_0 \to X_1$ has cardinality ${|X_0|}/{|X_1|}$ if the function $(f, g): X_0 \to X_1 \times X_1$ is uniform.

  You can think of this condition as saying that given an element $x_0 \in X_0$ chosen uniformly at random, all pairs $(f(x_0), g(x_0))$ are equally likely. In particular, the probability that $(f(x_0), g(x_0))$ lies on the diagonal of $X_1 \times X_1$ is

  $$\frac{|diagonal|}{|X_1 \times X_1|} = \frac{|X_1|}{{|X_1|}\cdot {|X_1|}} = \frac{1}{|X_1|}.$$

  Since an element $x_0 \in X_0$ is in the equalizer if and only if $(f(x_0), g(x_0))$ lies on the diagonal, we’d expect the equalizer to have cardinality ${|X_0|}/{|X_1|}$, and it does. I’ll come back to this probabilistic idea later, rigorously.

• Now let’s consider cofree actions of a group $G$ on a set. By definition, the cofree $G$-set generated by a set $S$ is the set $S^G$ of $G$-indexed families $(s_g)_{g \in G}$ of elements of $S$ (or functions $G \to S$ if you prefer), with action

  $$h \cdot (s_g)_{g \in G} = (s_{g h})_{g \in G}.$$

  The fixed points of this $G$-set are the constant families $(s)_{g \in G}$, for $s \in S$. So, if we’re given just the $G$-set $S^G$ and not told what $S$ is, we can reconstruct $S$ anyway: it’s the set of fixed points. In particular, when everything is finite, $|S|$ is the cardinality of the $G$-set to the power of $1/o(G)$ (writing $o$ for order).

  Now, when a $G$-set is regarded as a functor $B G \to Set$, the set of fixed points is the limit of the functor. So for a functor $X: B G \to FinSet$ corresponding to a cofree action of a group $G$ on a finite set $X_0$,

  $$|lim X| = |X_0|^{1/o(G)}.$$

Let me digress briefly to ask an elementary question:

Question   How do you recognize a cofree group action?

What I mean is this. Define a $G$-set to be free if it’s isomorphic to $G \times S$ (with its usual action) for some set $S$. It’s a useful little theorem that a $G$-set $X$ is free if and only if:

for all $g \in G$, if $g x = x$ for some $x \in X$ then $g = 1$.

Is there an analogous result for cofree actions?

As I mentioned above, if you’ve got a cofree $G$-set $X$ and you want to find the set $S$ such that $X \cong S^G$, it’s easy: $S$ is the set of fixed points. But I can’t get any further than that, or obtain any non-tautological necessary and sufficient condition for a $G$-set to be cofree.

Back to the cardinality of limits! In all the examples above, for functors $X: A \to FinSet$ satisfying certain conditions, we had

$$|lim X| = \prod_{a \in A} |X(a)|^{q(a)}$$

for some rational numbers $q(a)$ ($a \in A$) depending only on $A$, not $X$. If you read Part 1, you might be able to guess both what these numbers $q(a)$ are and what condition on $X$ guarantees that this equation holds. So I’ll just jump to the answer and state the definitions that make it all work.

Here goes. A coweighting on $A$ is a weighting on $A^{op}$, or explicitly, a function $w^A: ob(A) \to \mathbb{Q}$ such that

$$\sum_{a \in A} |A(a, b)| w^A(a) = 1$$

for all $b \in A$. As for weightings, I’ll assume throughout that $A$ has exactly one coweighting, which is generically true.

As I explained in a previous post, the forgetful functor

$$Set^A \to Set^{ob(A)}$$

has both a left adjoint $L$ and a right adjoint $R$. A functor $A \to Set$ is in the image of $L$ if and only if it’s a coproduct of representables; these were the functors that made the formula for the cardinality of a colimit work. I’ll say a functor $A \to Set$ is cofree if it’s in the image of $R$. These are the ones that make the formula for the magnitude of a limit work:

Theorem   Let $A$ be a finite category and $X: A \to FinSet$ a cofree functor. Then

$$|lim X| = \prod_{a \in A} |X(a)|^{w^A(a)}.$$

What do the cofree functors actually look like? I don’t know a really easily testable condition — and that’s why I asked the question above about cofree actions by a group. But they’re not the products of representables. In fact, given a family of sets

$$(S(a))_{a \in A} \in Set^{ob(A)},$$

the cofree functor $X = R(S)$ is given by

$$X(a) = \prod_b S(b)^{A(a, b)}.$$

You can see from this formula how $X(a)$ is functorial in $a$. (The right-hand side is doubly contravariant in $a$, which means it’s covariant.) In examples, the functions

$$X(a) \stackrel{X(u)}{\to} X(b)$$

arising from maps $a \stackrel{u}{\to} b$ in $A$ have a strong tendency to be uniform, in the sense I defined in the pullback example above. In fact, as I mentioned in a previous post, $X(u)$ is always uniform if $u$ is epic, and in the kinds of category $A$ that we often take limits over, the maps often are epic.

Examples

• When $A$ is a two-object discrete category, so that limits over $A$ are binary products, every functor $A \to FinSet$ is cofree, the coweights of the objects of $A$ are both $1$, and the theorem gives the usual formula for the cardinality of a product of two finite sets.

• For pullbacks, we’re taking $A$ to be $(0 \rightarrow 1 \leftarrow 2)$, whose coweighting is $(1, -1, 1)$. A functor $A \to FinSet$ is a diagram $(X_0 \rightarrow X_1 \leftarrow X_2)$ of finite sets, and it’s cofree if and only if both these functions are uniform. In that case, the theorem gives us the formula we saw before for the cardinality of a pullback: it’s

  $$\frac{{|X_0|}\cdot {|X_2|}}{|X_1|}.$$

• Similarly, a functor from $A = (0 \rightrightarrows 1)$ to $FinSet$ consists of finite sets and functions $f, g: X_0 \to X_1$, it’s cofree if and only if $(f, g): X_0 \to X_1 \times X_1$ is uniform, and the theorem tells us that the equalizer has cardinality

  $$\frac{|X_0|}{|X_1|}.$$

• Finally, when $A$ is the one-object category corresponding to a group $G$, the single coweight is $1/o(G)$, a functor $A \to FinSet$ is a finite $G$-set $X$, and the theorem tells us that if the action is cofree then the number of fixed points is

  $$|X_0|^{1/o(G)}$$

  (where $|X_0|$ means the cardinality of the underlying set $X_0$ of $X$).

Comagnitude: definition and examples

Given an arbitrary functor $X: A \to FinSet$, not necessarily cofree, it’s typically not true that

$$|lim X| = \prod_{a \in A} |X(a)|^{w^A(a)}.$$

But we can still think about the right-hand side! So I’ll define the comagnitude $\|X\|$ of $X$ by

$$\|X\| = \prod_{a \in A} |X(a)|^{w^A(a)} \in \mathbb{R}^+.$$

(The notation $\|X\|$ isn’t great, and isn’t intended to suggest a norm. I just wanted something that looked similar to but different from $\|X\|$. Suggestions are welcome.)

Examples

• If $X$ is cofree then $\|X\| = {|lim X|}$.

• For a diagram $X = (X_0 \rightarrow X_1 \leftarrow X_2)$ of finite sets, seen as a set-valued functor in the usual way,

  $$\|X\| = \frac{{|X_0|}\cdot {|X_2|}}{|X_1|}.$$

• Similarly, for a diagram $X = (X_0 \rightrightarrows X_1)$ of finite sets,

  $$\|X\| = \frac{|X_0|}{|X_1|}.$$

• For a finite set $X_0$ equipped with an action of a finite monoid $G$, the comagnitude of the corresponding functor $X: B G \to FinSet$ is given by

  $$\|X\| = |X_0|^{1/o(G)}.$$

• Let $A$ be any finite category and $S$ any finite set. The constant functor $\Delta S: A \to FinSet$ with value $S$ has comagnitude

  $$\prod_a |S|^{w^A(a)} = |S|^{\sum_a w^A(a)}.$$

  Now it’s a tiny lemma that the total coweight of a category $A$ is equal to the total weight (try it!), which by definition is the magnitude of $A$. So

  $$\| A \stackrel{\Delta S}{\to} FinSet \| = |S|^{|A|}.$$

For the next example, I have in my head an imaginary dialogue.

Me: Find me a formula for the cardinality of the limit of a functor $X: A \to FinSet$, but one that only depends on $A$ and the sets $X(a)$.

You: That’s impossible! There are loads of examples of functors $X, Y: A \to FinSet$ such that $X(a) \cong Y(a)$ for all $a \in A$, but ${|lim X|} \neq {|lim Y|}$.

Me: Try anyway.

You: Well, okay. If the only information I’m allowed to use is which set each object of $A$ gets sent to, and I’m supposed to calculate the cardinality of the limit, then the best I can do is to consider all functors that do the prescribed thing on the objects of $A$, calculate the cardinality of the limit of each one, and take the average.

This suggests an idea: could the comagnitude of a functor $X: A \to FinSet$ be the expected value of $|lim Y|$ for a random functor $Y: A \to FinSet$ satisfying ${|Y(a)|} = {|X(a)|}$?

Sadly not, in general (regardless of what probability distribution you use). Bu there’s a significant case where the answer is yes: you can characterize comagnitude in terms of random functors:

Example   Let $Q$ be a quiver (directed multigraph). We can form the free category $F Q$ on $Q$, whose objects are the vertices of $Q$ and whose maps are the directed paths of edges in $Q$. Assuming that $Q$ is finite and acyclic, the category $F Q$ is finite too.

It’s a theorem that for a functor $X: F Q \to FinSet$, the comagnitude $\|X\|$ is the expected value of $|lim Y|$ for a functor $Y: A \to FinSet$ chosen uniformly at random subject to the condition that $Y(a) = X(a)$ for all $a \in A$.

This covers cases such as products, pullbacks and equalizers: all those categories $A$ are free on a quiver.

(Incidentally, the cofree functors on $F Q$ have a simple explicit description, which I gave here. For those, the cardinality of the limit is equal to the expected value: it’s “what you’d expect”.)

(Co)magnitude of functors vs. (co)magnitude of categories

I mentioned earlier that the constant functor $\Delta S: A \to FinSet$ has comagnitude $|S|^{|A|}$, for any finite set $S$. In this sense, the definition of the magnitude of a category is a special case of the definition of the comagnitude of a set-valued functor (sort of; maybe “special case” is slightly overstating it). With the situation for magnitude in mind, you might wonder whether, in the other direction, the definition of the comagnitude of a set-valued functor is a special case of the definition of the magnitude of a category, or of some notion of the “comagnitude of a category”.

Not as far as I can see. For a start, two set-valued functors can have the same category of elements but different comagnitudes; so for a functor $X: A \to FinSet$, there’s no way we’re going to be able to extract the comagnitude of $X$ from its category of elements. Now the category of elements is a colax colimit, so you might think of using the lax limit instead. Or you might remember the result of Ponto and Shulman that the magnitude of $X$ is the Euler characteristic of its homotopy colimit (under hypotheses on $A$), and hope for some dual result involving homotopy limits instead.

But I don’t think any of that works. For a start, if we view $X: A \to Set$ as a functor $A \to Cat$ taking values in discrete categories, then its lax limit is simply the discrete category on the set $lim X$. That’s too trivial to help. But more importantly, coweights can be fractional, which means that comagnitudes

$$\|X\| = \prod_a |X(a)|^{w^A(a)}$$

are in general irrational. Since the magnitude of a finite category is always rational, there’s no finite category in the world whose magnitude is going to be $\|X\|$.

Properties of comagnitude

In any case, comagnitude of set-valued functors has some good properties. Most simply, if $X \cong Y: A \to FinSet$ then $\|X\| = \|Y\|$. Also, given functors

$$A \stackrel{F}{\to} B \stackrel{Y}{\to} FinSet,$$

we have $\|Y \circ F\| = \|Y\|$ if $F$ is an equivalence, or even just if $F$ has a right adjoint. Comagnitude also behaves well with respect to limits. For example, given functors $X, Y, Z: A \to FinSet$ and natural transformations

$$X \rightarrow Y \leftarrow Z$$

such that the diagram

$$X(a) \rightarrow Y(a) \leftarrow Z(a)$$

is cofree for each $a$ (meaning that both functions are uniform), then the comagnitude of the pullback

$$X \times_Y Z : A \to FinSet$$

is given by

$$\|X \times_Y Z\| = \frac{\|X\| \cdot \|Z\|}{\|Y\|}.$$

A similar result holds for any other limit shape.

Codiscrepancy

The last idea I want to share is about “codiscrepancy”. For a functor $X: A \to FinSet$, typically ${|lim X|} \neq \|X\|$ unless $X$ is cofree. We can measure the extent to which this equation fails by defining the codiscrepancy of $X$ to be

$$\frac{|lim X|}{\|X\|} \in \mathbb{R}^+.$$

(I’ll ignore the possibility that this is $0/0$.) In my last post, I used the word “discrepancy” for the difference between the cardinality of the colimit and the magnitude. For limits and comagnitude, taking the ratio seems more appropriate than taking the difference.

Examples

• Take an equalizer diagram $E \to X_0 \rightrightarrows X_1$ in $FinSet$. Its codiscrepancy is

  $$\frac{|E|}{{|X_0|}/{|X_1|}} = \frac{{|E|} \cdot {|X_1|}}{|X_0|}.$$

  In the case of discrepancy and magnitude last time, there was some discussion in both the post and the comments about the relationship between discrepancy and the Euler characteristic of chain complexes. Codiscrepancy seems more related to homotopy cardinality, where we take an alternating product of cardinalities of homotopy groups rather than an alternating sum of ranks of homology groups. But I’m still absorbing the comments from last time and won’t try to say more now.

• For a pullback diagram

  $$\begin{array}{ccc} P & \rightarrow & X_0 \\ \downarrow & & \downarrow \\ X_2 & \rightarrow & X_1 \end{array}$$

  in FinSet, the codiscrepancy is

  $$\frac{|P|}{{|X_0|}\cdot {|X_2|}/{|X_1|}} = \frac{{|P|}\cdot{|X_1|}}{{|X_0|}\cdot{|X_2|}}.$$

  This provides an answer — although maybe not a completely satisfying one — to the question I posed at the end of part 1: can mutual information be seen as some kind of magnitude?

  Here’s how. As explained in the example on conditional entropy in part 1, an integer-valued measure on a product $I \times J$ of finite sets can be seen as a set $A$ together with a function $A \to I \times J$, or equivalently a pair of functions $I \leftarrow A \rightarrow J$. The pullback square

  $$\begin{array}{ccc} I \times J & \rightarrow & I \\ \downarrow & & \downarrow \\ J & \rightarrow & 1 \end{array}$$

  of sets gives rise to a pullback square of monoids

  $$\begin{array}{ccc} End_{I \times J}(A) & \rightarrow & End_I(A) \\ \downarrow & & \downarrow \\ End_J(A) & \rightarrow & End(A), \end{array}$$

  where, for instance, $End_I(A)$ is the monoid of endomorphisms of $A$ over $I$. And the codiscrepancy of this pullback square is

  $$\frac{{|End(A)|}\cdot{|End_{I \times J}(A)|}}{{|End_I(A)|}\cdot{|End_J(A)|}},$$

  This is exactly the mutual information of our measure on $I \times J$. So that gives the definition of the mutual information of an integer-valued measure, and by the same kind of argument we used last time, we can easily get from this the definition for arbitrary measures, including probability measures.

Reflections

Zooming out now and contemplating everything in this post and the last, the big question in my mind is: what’s this all good for? Do the magnitude and comagnitude of set-valued functors have significance beyond the examples I’ve given?

And what about the world of enriched categories and functors? The most novel and startling results in the theory of magnitude have come from thinking about metric spaces as enriched categories. So what happens in that setting? Are there interesting results?