Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

June 13, 2011

The Magnitude of an Enriched Category

Posted by Tom Leinster

Enriched category theory is a machine of great power. On the front of that machine is a dial:

hand turning dial

Turning the dial selects the category in which you’re enriching — or more poetically, selects a branch of mathematics. Turning it to {true, false}\{ true,  false \} selects order theory. Turning it to [0,][0, \infty] selects metric geometry. Turning it to AbAb selects homological algebra. Turning it to SetSet selects category theory itself. Turning it to nCatn Cat selects (n+1)(n + 1)-category theory. Any definition framed in the full generality of enriched category theory is, therefore, extremely general.

Most of my work over the last few years has been directed towards understanding size. Many mathematical objects come with a canonical ‘size’ invariant: the cardinality of a set, the Euler characteristic of a topological space, the entropy of a probability space. There is a familial resemblance between these invariants, and I’ve been trying to pin it down.

In Cambridge on Tuesday I’ll give a talk about my best effort so far: a definition of the magnitude of an enriched category. This produces, automatically, many size-like invariants: some old and familiar, some half-familiar, and some that are completely unexplored. I thought I’d prepare for the seminar by telling the story here.

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 R S T \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+ RT|=|S|+|T||R|. |S +_R T| = |S| + |T| - |R|.
  2. Take a finite group GG acting freely on a finite set SS. Then the cardinality of the set of orbits is given by the formula |S/G|=1order(G)|S|. |S/G| = \frac{1}{order(G)} |S|.

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

There’s now an obvious question. Can we do the same for an arbitrary finite category AA? In other words, for an arbitrary finite category AA, can we find a formula for the cardinality of the colimit of any ‘special’ functor X:AFinSetX: A \to FinSet, as a rational linear combination of the cardinalities |X(a)||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 AX|= aAw(a)|X(a)|. |\lim_{\to A} X| = \sum_{a \in A} w(a) |X(a)|. says in the case when XX 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,)X = A(a, -) and changing the name of the variable over which the sum runs, the formula says bA|A(a,b)|w(b)=1. \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 AFinSetA \to FinSet, and if ‘special’ includes representable, then the weights w(a)w(a) must satisfy this last equation for each aAa \in A. Since there are as many equations as there are unknowns w(a)w(a), there’s usually a unique solution ww.

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

(For category theorists at least, it’s particularly natural to think about the functor with constant value 11: the functors ASetA \to Set correspond to the discrete opfibrations over AA, and the functor with constant value 11 is what corresponds to the identity opfibration, id:AAid: 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 kk, assumed commutative. But to speak of an ‘m×nm \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 II and JJ are finite sets then an I×JI \times J matrix over the rig kk amounts to a function I×JkI \times J \to k.

Given a finite set, write u Ik Iu_I \in k^I for the column vector all of whose entries are 11. Write ζ *\zeta^* for the transpose of a matrix ζ\zeta.

Definition  Let ζ\zeta be an I×JI \times J matrix over kk. A weighting on ζ\zeta is a column vector ww such that ζw=u I. \zeta w = u_I. A coweighting is a row vector vv such that vζ=u J *. v \zeta = u_J^*.

Put another way, a weighting on ζ\zeta is a family (w(j)) jJ(w(j))_{j \in J} of elements of kk such that jζ(i,j)w(j)=1 \sum_j \zeta(i, j) w(j) = 1 for each iIi \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×JI \times J matrix. Let ww be a weighting on ζ\zeta, and vv a coweighting. Then iIv(i)= jJw(j). \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 ww and w˜\tilde{w} are weightings then, choosing any coweighting vv, we have w(j)=v(i)=w˜(j). \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 |ζ|=w(j)=v(i) |\zeta| = \sum w(j) = \sum v(i) for any weighting ww and coweighting vv.

We’ll only need to talk about the magnitude of square matrices. Moreover, the rig kk 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 ζw=u Iw=ζ 1u I. \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×II \times I invertible matrix then, writing μ=ζ 1\mu = \zeta^{-1}, we have |ζ|= j,iIμ(j,i). |\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 VV be a monoidal category. We’re going to define the magnitude of a category enriched in VV, or VV-category for short.

There are two caveats. First, we’re only going to attempt this for VV-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 VV, we’ll need to start from a notion of the size of an object of VV.

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

Let AA be a VV-category with finitely many objects. Define the similarity matrix of AA to be the ob(A)×ob(A)ob(A) \times ob(A) matrix ζ A\zeta_A over kk given by |ζ A(a,b)|=|A(a,b)|. |\zeta_A(a, b)| = |A(a, b)|.

Definition  The VV-category AA has magnitude if the matrix ζ A\zeta_A has magnitude. In that case, the magnitude of AA is the magnitude of ζ A\zeta_A: |A|=|ζ 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 VV, 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=FinSetV = FinSet

A VV-category is an ordinary category with finite homsets. Put k=k = \mathbb{Q}, and define ||:ob(V)k |\cdot|: ob(V) \to k by taking |X||X| to be the cardinality of XX, for a finite set XX. 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 AA gives rise to a topological space, the geometric realization of its simplicial nerve. And under certain hypotheses on AA, 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:

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}V = \{ true,   false \}

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

Put k=k = \mathbb{Z} and define ||:ob(V)k |\cdot|: ob(V) \to k by |false|=0,|true|=1. |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|= n0(1) n|{chains a 0<<a n in A}|. |A| = \sum_{n \geq 0} (-1)^n |\{ \text{chains}&nbsp; a_0 &lt; \cdots &lt; a_n &nbsp; \text{in}&nbsp; 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, a,bAμ(a,b)\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,],,+,0)V = ([0, \infty], \geq, +, 0)

This is the poset ([0,],)([0, \infty], \geq) with monoidal structure given by addition. As Lawvere observed long ago, a VV-category is a (generalized) metric space. We take k=k = \mathbb{R} and define |x|=e x |x| = e^{-x} (xx \in \mathbb{R}). (Since |||\cdot| is supposed to convert tensor product in VV 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 n\mathbb{R}^n. For example, the magnitude of a line segment of length \ell is 1+/21 + \ell/2.

Simon Willerton and I have a conjecture that claims to give the magnitude of any compact convex subset of n\mathbb{R}^n in terms of some classical geometric invariants. For example, it predicts that the magnitude of a nonempty compact convex subset A 2A \subseteq \mathbb{R}^2 is 1+14perimeter(A)+12πarea(A). 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 n\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,],,max,0)V = ([0, \infty], \geq, max, 0)

This is the same as the last example except that the monoidal structure has changed: ++ has become maxmax. What this means is that VV-categories are now ultrametric spaces, that is, metric spaces satisfying the stronger triangle inequality max{d(a,b),d(b,c)}d(a,c). \max\{ d(a, b), d(b, c) \} \geq d(a, c). (The pp-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=FDVectV = FDVect

Take the category of finite-dimensional vector spaces, say over \mathbb{C}. Put k=k = \mathbb{Q}, and for a vector space XX, define |X|=dimX|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 AA be the \mathbb{C}-linear category of projective indecomposable RR-modules — or rather, a skeleton thereof. Then AA is finite.

Theorem: if RR is Koszul and has finite dimension and global dimension, then |A|= i=0 (1) idim(Ext R i(R 0,R 0)). |A| = \sum_{i = 0}^\infty (-1)^i \dim (Ext_R^i (R_0, R_0)). (Here R 0R_0 is the degree 00 part of RR.) 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 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 V = FinSet^{\mathbb{N}} of sequences of finite sets: (XY) n= k+m=nX k×Y m. (X \otimes Y)_n = \sum_{k + m = n} X_k \times Y_m. A VV-category is a category in which every map ff has a degree deg(f)deg(f) \in \mathbb{N}, with deg(gf)=deg(g)+deg(f)deg(g \circ f) = deg(g) + deg(f). We might say that a VV-category is an ‘\mathbb{N}-graded category’.

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

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

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 V = FDVect^{\mathbb{N}}

This example is similar: a VV-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=ChV = Ch, V=SSetV = SSet, V=TopV = Top

These three VVs are all categories of spaces. In each case, the function ||:ob(V)k |\cdot|: ob(V) \to k is Euler characteristic (taking k=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=nCatV = n Cat

Recall the strategy: starting from a function ||:ob(V)k |\cdot|: ob(V) \to k we obtain a function ||:ob(V-Cat)k, |\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 VV-categories with finite object-sets. But let me gloss over that.) So we can iterate.

In particular, we can iterate starting with V=Set=0CatV = 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 CatCat-category, that is, a 2-category. Continuing, it gives us the notion of the magnitude of an nn-category.

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

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

Status:  Barely explored.

V=CatV = \infty Cat

This is a tricky one. The category Cat\infty Cat of \infty-categories (ω\omega-categories) is a fixed point of the process VV-CatV \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 VV-categories, we’d need a notion of size for objects of VV… but in this case, VV-categories and objects of VV 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 AA be a finite \infty-category. For objects a,ba, b of AA, the hom-thing A(a,b)A(a, b) is also a finite \infty-category. Let ζ\zeta be the ob(A)×ob(A)ob(A) \times ob(A) matrix whose (a,b)(a, b)-entry is |Hom(a,b)||Hom(a, b)|. Suppose that ζ\zeta is invertible over \mathbb{Q}, as it usually will be, and write μ=ζ 1\mu = \zeta^{-1}. Then we demand that |A|= a,bμ(a,b). |A| = \sum_{a, b} \mu(a, b). We seek an invariant |||\cdot| satisfying this equation for every AA.

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.

Posted at June 13, 2011 6:20 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2408

41 Comments & 2 Trackbacks

Re: The Magnitude of an Enriched Category

Nice post!

I feel guilty for bringing up entropy again, but your formalism reminds me so much of that question of mine that I’m sure that there has to be a relation. Potentially the answer to that question could be another example on your list, with VV equal to FinProb\Fin\Prob or some other category related to FinProb\Fin\Prob. So far I haven’t been able to make it work, though. What do you think? Does it also seem related to you?

Posted by: Tobias Fritz on June 13, 2011 2:18 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Tobias wrote:

I feel guilty for bringing up entropy again

Don’t! Entropy is most definitely a part of this size programme. That’s why I’m interested in entropy.

In fact, it’s a particularly intriguing part, because probability spaces and measure spaces seem not to be viewable as enriched categories in any useful way. It’s also intriguing because there’s the recurrent question of what the right general definition of Shannon entropy really is, beyond the rather degenerate finite case.

I’d like to think again about your question of assigning an entropy to any commutative diagram in FinProbFinProb. I think it’s a good one.

Here are some other thoughts.

  1. To be more precise, it’s not entropy but diversity that I regard as the primary notion of the ‘size’ of a finite probability space. The diversity (of order 1) of a finite probability space p=(A,p)p = (A, p) is

    D(p)= iAp i p i. D(p) = \prod_{i \in A} p_i^{-p_i}.

    This is the exponential of Shannon entropy, at least if you’re defining Shannon entropy using natural logarithms. If you’re defining it using logarithms to base bb then it’s bb to the power of Shannon entropy. But unlike entropy, diversity doesn’t depend on a choice of base. It’s also an effective number:

    D((1/n,,1/n))=n D((1/n, \ldots, 1/n)) = n

    for all nn.

  2. We already have some connections between entropy — or rather, diversity — and magnitude. The very simplest one is that for a finite set AA,

    max pD(p)=|A| max_p D(p) = |A|

    where the maximum is over all probability measures pp on AA. That is: the maximum diversity of a probability distribution on a finite set is the cardinality of that set.

    There’s a similar but more sophisticated connection when you use metric spaces rather than sets. Take a finite metric space AA and, as the post above indicates, define an A×AA \times A matrix ζ A\zeta_A by

    ζ A(i,j)=e d(i,j). \zeta_A(i, j) = e^{-d(i, j)}.

    The diversity (of order 11) of a probability distribution pp on AA is

    D(p)= iA(ζp) i p i. D(p) = \prod_{i \in A} (\zeta p)_i^{-p_i}.

    Then max pD(p)max_p D(p) isn’t always equal to the magnitude |A||A| of the metric space AA: it’s a bit more subtle than that. But, to give you a flavour of the connection, max pD(p)max_p D(p) is always equal to the magnitude of some subspace of AA.

    There’s more to say about this, but I won’t say it now.

  3. The magnitude of stochastic matrices is interestingly uninteresting.

    Write u nu_n for the n×1n \times 1 column vector all of whose entries are 11. Almost by definition, an m×nm \times n matrix ζ\zeta is row-stochastic if and only if u nu_n is a weighting: that is,

    ζu n=u m. \zeta u_n = u_m.

    So if an m×nm \times n row-stochastic matrix has a magnitude, it’s nn.

Posted by: Tom Leinster on June 14, 2011 12:31 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

I also wanted to point out that you definitely shouldn’t feel guilty about bringing up entropy here; I just wanted to wait and see what Tom said about it first.

The word “entropy” also appears in my comment below about magnitude of ultrametric spaces. This isn’t a coincidence! The notion of rr-entropy, which as I pointed out applies to general metric spaces, was motivated by similar considerations to Shannon entropy and named so because of the relationship. Roughly, it’s supposed to describe how much information you need to describe a metric space, looking at it at a given scale. I’ve also recently come across a way* of looking at rr-entropy which is very similar to Tom’s description of magnitude of a metric space as (something like) maximum diversity. Basically, the rr-entropy of a metric space AA is the maximum over probability measures on AA of something which everyone should recognize as a close cousin of Shannon entropy.

*I’m not sure whether it’s a new observation.

Posted by: Mark Meckes on June 14, 2011 3:01 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

I’ll take up Tom on his invitation to spell out the theory of magnitude for ultrametric spaces. The following is an edited version of notes I wrote for my own use; hopefully it comes out reasonably consistent with Tom’s exposition in this post.

There’s a terminological danger here, since ultrametric spaces are in particular metric spaces. I’ll use the term “ultramagnitude” to emphasize that I’m thinking of the magnitude of ultrametric spaces considered as categories enriched over [0,][0,\infty] with the monoidal structure given by max\max. I’ll only consider symmetric ultrametric spaces, and restrict distances to be finite. The finiteness restriction is just a matter of convenience, but the symmetry restriction is significant. (As Tom has pointed out to me, dropping both symmetry and finiteness means that posets become a special case, significantly increasing the richness and difficulty of the theory.)

Here is one of the most important basic facts about ultrametric spaces. The proof is an easy exercise.

Let (A,d)(A,d) be an ultrametric space, and for each aAa \in A, r>0r &gt; 0 let B(a,r)={bAd(a,b)<r}B(a,r) = \{b\in A \mid d(a,b) &lt; r\}. Then for any r>0r &gt; 0, the sets {B(a,r)aA}\{ B(a,r) \mid a \in A\} form a partition of AA. The same is true of the closed balls B¯(a,r)\overline{B}(a,r).

Let N(A,r)N(A,r) denote the number of distinct open balls of radius rr in AA. Then logN(A,r)\log N(A,r) is called the rr-entropy or rr-capacity of AA. (For general metric spaces entropy and capacity are different, although closely related, quantities, but due to the lemma above they coincide for ultrametric spaces.)

Now to define ultramagnitude we need a monoid homomorphism

(1)||:([0,],max,0)(k,,1) |\cdot| : ([0,\infty], \max, 0) \to (k, \cdot, 1)

for some rig kk with multiplication \cdot and multiplicative identity 11. That is, for any x,y[0,]x,y \in [0,\infty] with, say, xyx\le y, we must have

(2)|y|=|max{x,y}|=|x||y|. |y| = |\max\{x,y\}| = |x| |y|.

In particular, |y|=|y| 2|y| = |y|^2 for every yy, which means that if kk is an integral domain then |||\cdot| takes its values in {0,1}\{0,1\}. Furthermore, if |y|=1|y| = 1 then |x|=1|x| = 1 for every xyx \le y, and if |x|=0|x| = 0 then |y|=0|y| = 0 for every yxy \ge x. This implies that |||\cdot| has one of the following forms, for some fixed z[0,]z \in [0,\infty]: |x|={1 if xz, 0 if x>z, |x| = \begin{cases} 1 & \text{if } \; x\le z, \\ 0 & \text{if } \; x &gt; z, \end{cases} or |x|={1 if x<z, 0 if xz. |x| = \begin{cases} 1 & \text{if } \; x &lt; z, \\ 0 & \text{if } \; x \ge z. \end{cases}

I will make an arbitrary choice of scale by setting z=1z=1. I will also assume the second form of |x||x|; this just amounts to a choice to use open balls in the following, as opposed to closed balls.

The similarity matrix ζ A\zeta_A of an ultrametric space thus has entries

(3)ζ A(a,b)={1 if d(a,b)<1, 0 if d(a,b)1. \zeta_A(a,b) = \begin{cases} 1 & \text{if } \; d(a,b) &lt; 1, \\ 0 & \text{if } \; d(a,b) \ge 1.\end{cases}

This can be thought of as a “discretization” of the similarity matrix of AA when considered as an enriched category over ([0,],+,0)([0,\infty],+,0), suggesting that one should expect metric space magnitude to reflect finer information than ultramagnitude. Since ζ A\zeta_A is symmetric a weighting will automatically be (the transpose of) a coweighting.

If #B(a,1)1k\# B(a,1) \cdot 1 \in k is a unit for each aAa\in A, then a weighting is given by

(4)w(a)=(#B(a,1)1) 1. w(a) = \bigl( \# B(a,1) \cdot 1 \bigr)^{-1}.

To ensure that every ultrametric space has a weighting it thus suffices that kk contain an isomorphic copy of \mathbb{Q}, and then we may as well take k=k = \mathbb{Q}. The magnitude of AA is then

(5)|A|= aAw(a)= distinct B(a,1)1=N(A,1). |A| = \sum_{a\in A} w(a) = \sum_{\text{distinct } \; B(a,1)} 1 = N(A,1).

For t>0t &gt; 0, it follows that |tA|=N(A,1/t)|tA| = N(A,1/t), where tAtA is shorthand for the ultrametric space (A,td)(A, t\cdot d). Thus for ultrametric spaces, knowing the “ultramagnitude function” t|tA|t \mapsto |tA| is equivalent to knowing the rr-entropy function rlogN(A,r)r \mapsto \log N(A,r). (The corresponding notion of “magnitude function” plays a major role in Tom’s paper on magnitude of metric spaces.)

Posted by: Mark Meckes on June 13, 2011 4:10 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Wonderful! Thanks very much, Mark.

Posted by: Tom Leinster on June 13, 2011 4:37 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Mark, that’s really nice. It really does mean that the ultramagnitude is the “number of points you can see if you squint your eyes” which is how I sort of think of magnitude.

I don’t have much intuition for ultrametric spaces, and I believe the only example I know of is the metric induced on the leaves of a tree, so I’m going to spell out what happens, in biological example, for those who aren’t familiar with this stuff.

Given some population of organisms, for instance the fauna and flora in your garden, we build a finite ultra-metric space AA using a standard biological taxonomic hierarchy:

Species, Genus, Family, Order, Class, Phylum, Kingdom, Domain.

There is one point in AA for each species in your garden. The distance between two points in AA is defined as follows. They are a distance 11 apart if and only if they correspond to different species which are in the same genus. They are a distance 22 apart if they are in different genera, but in the same family. And so on. (In fact, the actual numbers 11, 22, and so on in the definition won’t matter in what follows, as long as they form a strictly increasing sequence.) This gives an ultrametric space.

Now you can calculate the ultramagnitude function |tA||t A|. For very small tt this will be precisely the number of different domains in your garden. As tt increases it will suddenly jump to the number of different kingdoms in your garden. Then it will suddenly jump to the number of different phyla. And so on. Eventually, for t0t\gg 0 then |tA||t A| will just give the number of different species in your garden, or, in other words, just the number of points in AA.

Posted by: Simon Willerton on June 29, 2011 3:24 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

I wonder whether this notion of a scaled magnitude could be made to relate to the scaled cohomology discussed in Hodge Theory on Metric Spaces in section 7. Is there then a scaled Euler characteristic?

Posted by: David Corfield on June 30, 2011 8:53 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

The authors say there

A closely related point of view is that of persistent homology…

Persistent homology was given an airing at the Notices of the AMS. It seems that there is a notion of Euler characteristic for persistent homology.

Posted by: David Corfield on June 30, 2011 9:40 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Thanks for those, David. But you’re linking to a lot there—three different papers—and while I’ve now looked at all of them, I obviously haven’t understood as much as you have. Could you give a quick sketch of the rough idea?

Posted by: Tom Leinster on June 30, 2011 7:03 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

It’s probably a case of fishing for connections, but
there’s a methodological point which interests me in this. How do you decide on a threshold so that when you hear of a piece of mathematics that appears to deal similarly enough with something you’re working on, you feel you should take a look at it? From the other perspective, how common is it for you as a mathematician to think of someone else’s work that he or she really should have looked into an approach you know about before proceeding?

Say, I tell you that there’s a scale based cohomological treatment of metric spaces such that in the case of finite metric spaces, at scale α=\alpha = \infty, zeroth degree cohomology has dimension 1, other degrees being trivial, while for small α\alpha, zeroth degree has dimension the cardinality of the metric space, other degrees being trivial. At intermediate scales there may be higher cohomology.

So, we have an approach which, as the scale varies, moves from seeing a finite metric space as a set of nn distinct points to seeing it as a single point, just as figure 1 of The magnitude of metric spaces shows for a two point space. Does that pique your interest?

Perhaps in this case that’s not similar enough. Your figure 1 shows a smooth curve, where intermediate stages of scaled cohomology will involve jumps. But I’m interested in people’s thoughts on the general methodological question.

Posted by: David Corfield on July 1, 2011 10:16 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Simon wrote:

I don’t have much intuition for ultrametric spaces, and I believe the only example I know of is the metric induced on the leaves of a tree

No need for modesty: you actually know all the examples of finite ultrametric spaces. They’re all of the type you describe.

Take a finite ultrametric space XX. Only finitely many real numbers arise as distances, and we can put them in order:

0=d 0<d 1<<d k. 0 = d_0 \lt d_1 \lt \cdots \lt d_k.

As Mark said, “being at most distance δ\delta apart” is an equivalence relation on any ultrametric space, for any δ0\delta \geq 0. In particular, we have for each i{0,,k}i \in \{0, \ldots, k\} an equivalence relation i\sim_i on XX:

x iyd(x,y)d i. x \sim_i y \Leftrightarrow d(x, y) \leq d_i.

The equivalence relations are successively coarser:

0 1 k. \sim_0 \subseteq \sim_1 \subseteq \cdots \subseteq \sim_k.

A nested sequence of equivalence relations on a set is just a tree structure on it. And if you take this tree and apply your garden construction (using the distances d id_i instead of the integers ii), you get back the original ultrametric space.

Posted by: Tom Leinster on June 29, 2011 5:37 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Thanks, this is great! I had not really understood the “background story” before.

You, or someone, must have noticed that your combinatorial formulas are at least sometimes correct for non-special (or at least “less special”) functors, if instead of colimits in Set we take homotopy colimits in spaces (\infty-groupoids), and replace cardinality of finite sets by Euler characteristic or homotopy cardinality? In the case of a group acting on a finite set, this is one of the motivating properties of homotopy/groupoid cardinality. But also in the case of pushouts; for instance the homotopy pushout of 2 1 1 \array{ 2 & \to & 1 \\ \downarrow && \\ 1 & & } is B=S 1B \mathbb{Z} = S^1, which has Euler characteristic 0=1+120 = 1 + 1 - 2.

In fact, Peter May proved that given any homotopy pushout X Y Z W\array{ X & \to & Y \\ \downarrow &&\downarrow \\ Z & \to & W} in a closed symmetric monoidal triangulated category, if XX, YY, and ZZ are dualizable, then so is WW, and χ(W)=χ(Y)+χ(Z)χ(X)\chi(W) = \chi(Y) + \chi(Z) - \chi(X), where χ\chi refers to the Euler characteristic defined as the trace of the identity map. (Actually he proved this in the special case Z=0Z=0, where what we have is a distinguished triangle XYWΣXX\to Y\to W\to \Sigma X, but the general case follows.) This means the combinatorial formula for pushouts is true for any diagram at all, if we are in a “sufficiently homotopical” setting. In particular, recalling the interpretation of classical Euler characteristics in the stable homotopy category, we get the combinatorial formula for any homotopy pushout diagram of finite spaces.

Insofar as this is true, it also “explains” why the Euler characteristic of a category, as you defined it, computes the Euler characteristic of its classifying space. To wit, the homotopy colimit of the constant-at-1 diagram of any shape is exactly (up to homotopy) the classifying space of the diagram shape.

But looking through your paper, it seems that even the homotopical version of the colimit-cardinality formula can’t always be true, right? For instance, homotopy colimits should be invariant under Morita equivalence, but the Euler characteristic of a category is not. And the Euler characteristic of a homotopy colimit is not in general determined by the Euler characteristics of the input spaces, without knowing anything about the morphisms involved in the colimit.

This makes me want to ask some question like “Given a symmetric monoidal derivator DD, a category AA, and a diagram XD(A)X\in D(A) of dualizable objects, under what conditions can the Euler characteristic of hocolim AXhocolim_A X be computed in terms of the Euler characteristics of the objects in XX and a weighting of AA?” In particular, can May’s theorem be extended to other diagram shapes? This would be even more interesting if we could incorporate homotopy cardinality into the same sort of picture.

Posted by: Mike Shulman on June 13, 2011 9:04 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

That’s very nice. I have very briefly recorded that statement here.

Concerning your last question:

  1. do we have a page on the definition of “symmetric monoidal derivator”? Or else: what is known about this?

  2. is it intentional that you drop the stability requirement (as in “stable derivator”)?

Posted by: Urs Schreiber on June 13, 2011 10:35 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

do we have a page on the definition of “symmetric monoidal derivator”?

We do now.

is it intentional that you drop the stability requirement?

I was thinking of stability as probably one of the “conditions” under which the result would hold. We certainly need the derivator to be “additive” so that adding up Euler characteristics makes sense, but conceivably stability might be more than is necessary.

Posted by: Mike Shulman on June 14, 2011 7:14 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Mike wrote:

This means the combinatorial formula for pushouts is true for any diagram at all, if we are in a “sufficiently homotopical” setting.

That’s very interesting. I hadn’t noticed that.

The closest I’d come was the following. Take a category AA and a functor X:ACatX: A \to Cat. (It needn’t be a strict functor; colax will do.) Write E(X)E(X) for the category of elements of XX. Then, supposing that everything in sight has well-defined magnitude/Euler characteristic, we have

|E(X)|= aAw(a)|X(a)| |E(X)| = \sum_{a \in A} w(a) |X(a)|

where ww is a weighting on AA. And that’s true for any X:ACatX: A \to Cat.

homotopy colimits should be invariant under Morita equivalence, but the Euler characteristic of a category is not

Indeed. I’ll repeat the example here, as it’s so simple. Take the two-element monoid consisting of the identity and an idempotent, regarded as a one-object category AA. The Euler characteristic of a monoid-as-category is the reciprocal of its order, so

|A|=1/2. |A| = 1/2.

Now AA, like any other category, is Morita-equivalent to its Cauchy completion A¯\bar{A}. Explicitly, A¯\bar{A} is the two-object category consisting of an epi 010 \to 1, a mono splitting it, the idempotent on 00 that is their composite, and the two identities. Then A¯\bar{A} has a terminal object, so

|A¯|=1. |\bar{A}| = 1.

Hence magnitude/Euler characteristic is not invariant under Morita equivalence.

On the other hand, the magnitude of a category (or in general, an enriched category) has a different invariance property: if AA and BB are two categories with magnitude and there exists an adjunction between them, then |A|=|B||A| = |B|.

Posted by: Tom Leinster on June 14, 2011 12:51 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

On the other hand, the magnitude of a category (or in general, an enriched category) has a different invariance property:…

or, considering the relationship between the magnitude of a category and the Euler characteristic of the geometric realisation of its nerve, one sees that if categories AA and BB are in the same connected component of the subcategory 𝒲 Cat\mathcal{W}_\infty \subset Cat, the so-called ‘smallest basic localiser’ (consisting of weak equivalences in the Thomason model structure), then they have the same magnitude.

In particular, one can use Quillen’s theorem A to check whether a functor induces an equality of magnitudes.

Posted by: David Roberts on June 14, 2011 4:00 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

David R. wrote:

[…] then they have the same magnitude.

Is this clear?

There are strong assumptions on a category for its magntiude to coincide with the Euler characteristic of its realization: it may have no nontrivial endomorphisms. For instance for GG a finite group there is on th one hand the corresponding one-object groupoid and on the other hand there is a poset, such that both present the space BGB G. But the magnitude of the latter is the actual Euler characteristic of BGB G, while the magnitude of the former is 1/|G|1/\vert G \vert, the homotopy cardinality of BGB G.

Posted by: Urs Schreiber on June 14, 2011 6:47 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

I may have meant Euler characteristic of the category instead of magnitude (if these are even different). I was basing this remark on what Mike said:

Insofar as this is true, it also “explains” why the Euler characteristic of a category, as you defined it, computes the Euler characteristic of its classifying space.

and so I may have overstated the case (not to mention using overblown language! [hangs head in shame])

In any case, it should be an interesting exercise to see if Quillen A has a bearing on this situation.

Posted by: David Roberts on June 14, 2011 8:02 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Urs wrote:

But the magnitude of the latter is the actual Euler characteristic of BGB G, while the magnitude of the former is 1/G1/&#8739;G&#8739;, the homotopy cardinality of BGB G.

What’s your definition of ‘the actual Euler characteristic of BGB G’? If it’s the alternating sum of the ranks of the rational cohomology groups, then we get zero when G=/2G = \mathbb{Z}/2. If it’s the alternating sum of the numbers of cells in a CW decomposition, the answer is ill-defined: we get an alternating series that doesn’t converge. For example, using the most obvious CW decomposition, we get

11+11+ 1 - 1 + 1 - 1 + \cdots

However, if we use Cesaro or Abel sumation, we can resum this alternating series. Using that approach, we get 12\frac{1}{2}. And this matches the homotopy cardinality of GG!

This is not only true for /2\mathbb{Z}/2; it works for any finite group.

You probably know this, because I keep saying it over and over: there’s a mysterious way in which the Euler characteristic and homotopy cardinality are trying to be ‘the same’. But you’re right that they’re not ‘the same’ in the simple obvious sense sense of that term.

Posted by: John Baez on June 14, 2011 8:44 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Right, I didn’t say that well. David R. claimed that Tom’s characteristic for categories is invariant under Thomason weak equivalences. But this is not clear. One could hope that some improvement of it is, but by itself it is not even defined on all of these.

Posted by: Urs Schreiber on June 14, 2011 11:35 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Thanks, John - I meant to say something to the effect that your quest to find the meaning of the equality of Euler char. and homotopy cardinality had some bearing here, but I forgot.

Urs - restricting to the class of categories that have a well-defined Euler characteristic, the natural question to ask is whether this gives us all homotopy types.

Posted by: David Roberts on June 15, 2011 12:41 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Hi David,

Urs - restricting to the class of categories that have a well-defined Euler characteristic, the natural question to ask is whether this gives us all homotopy types.

Yes, I agree, and whether one can then find a prescription that would say something like “to compute the Euler characteristic of this category, first replace it with this nice one and then…”. Maybe something like Mike suggested above.

I’ll let the experts figure this out, I really need to be concentrating on something else now. Also, I apologize for apparently repeatedly jumping on your original statement. I think it is a great motivating statement and just wanted to indicate that it is not clear that is has been already achieved. Apparently I didn’t do this well and it gave rise to lots of back and forth.

Posted by: Urs Schreiber on June 15, 2011 6:39 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Urs wrote:

There are strong assumptions on a category for its magntiude to coincide with the Euler characteristic of its realization: it may have no nontrivial endomorphisms.

Well, kinda sorta. The result in my first paper did indeed assume this. But there’s also another result (as you know): the magnitude of a finite group, viewed as a one-object category, is the reciprocal of its order. And back in 1961, Terry Wall provided a framework in which BGB G really does have Euler characteristic 1/order(G)1/order(G):

C.T.C. Wall, Rational Euler characteristic, Proc. Cambridge Philos. Soc. 57 (1961), 182-184.

Personally, the only reason I made such strong assumptions on the category was so that its geometric realization would have well-defined Euler characteristic. (It wasn’t to force its Euler characteristic to be equal to the category’s magnitude.) If we adopt Wall’s framework, then the result about the magnitude of a one-object groupoid contradicts what you wrote.

(Incidentally, apologies to those who have commented here and received in return an out-of-office autoreply from me. That’s because I’m away, and the Cafe software sends me an email notification whenever someone comments. The email notification is set up to look like it comes from you, so it’s you who gets the auto-reply. I’ll try to fix it some time.)

Posted by: Tom Leinster on June 14, 2011 6:39 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

If we adopt Wall’s framework, then the result about the magnitude of a one-object groupoid contradicts what you wrote.

So you are saying that “if we adopt Wall’s framework” (I have to check what this means) then David R.’s assertion is right, that your category cardinality is well defined and invariant on all Thomason weak equivalences? Because that’s the contradiction to what I wrote, it seems.

Posted by: Urs Schreiber on June 14, 2011 9:08 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Sorry, I’m not keeping up, so I don’t know the answer to your question. What I meant was that we have an equality between the magnitude of the one-object groupoid GG and the Euler characteristic of the classifying space of GG, if we define that Euler characteristic à la Wall. By “contradict” all I meant was that this equality holds even though the hypothesis “it may have no nontrivial endomorphisms” isn’t satisfied.

Posted by: Tom Leinster on June 14, 2011 9:47 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

back in 1961, Terry Wall provided a framework in which BGB G really does have Euler characteristic 1/order(G)1/order(G)

When I first read this sentence I was extremely excited! But then I looked up the paper and found that this is his definition:

Let [GG be a group] having a subgroup KK of finite index rr which [has a finite complex as a classifying space, so that BKB K has an Euler characteristic in the usual sense]. We define χ(G)=(1/r)χ(K)\chi(G) = (1/r) \chi(K).

I think it’s a bit of a stretch to call that a “framework”. (-:

Posted by: Mike Shulman on June 17, 2011 5:15 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Russell’s observation comes to mind:

The method of ‘postulating’ what we want has many advantages; they are the same as the advantages of theft over honest toil. Let us leave them to others and proceed with our honest toil.

Posted by: David Corfield on June 17, 2011 10:06 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Russell’s observation is funny, but I think it’s unfair to apply it to Wall’s paper. Let me summarize what Wall does.

Wall takes the class L of groups that admit a finite complex as classifying space. For groups in this class, the Euler characteristic may consistently be defined as the Euler characteristic of such a finite complex. He observes that L is closed under taking finite products, finite coproducts, and subgroups of finite index, and that the three equations

χ(G×H) =χ(G)χ(H) χ(G*H) =χ(G)+χ(H)1 χ(K) =rχ(G) \begin{aligned} \chi(G \times H) &= \chi(G) \chi(H) \\ \chi(G * H) &= \chi(G) + \chi(H) - 1\\ \chi(K) &= r\chi(G) \end{aligned}

hold, where G,HG, H \inL and KK is a subgroup of GG of index rr.

So far, nothing is new. But he then extends the definition of Euler characteristic to a larger class M of groups. It consists of all those groups GG admitting some finite-index subgroup belonging to L. As Mike said, the Euler characteristic is extended to M as follows: if, say, GG is a group with an index rr subgroup KK belonging to L, then he defines χ(G)=χ(K)/r\chi(G) = \chi(K)/r.

That’s “postulating”, yes, but then comes the “honest toil”. He verifies that this definition is consistent, and he proves that the three equations above remain true on this larger class M. So he doesn’t just make up a definition: he shows that this definition is reasonable.

It’s been a few years since I first read Wall’s paper, and I agree that the word “framework” was badly chosen. (The paper is less than two pages.) But there’s genuine content there.

There’s more about rational-valued — indeed, real-valued — Euler characteristic here:

Joel M. Cohen, La caratteristica di Eulero a valori reali, Rend. Sem. Mat. Fis. Milano 47 (1977), 233-239.

I’ve completely forgotten what Cohen does there. All I remember is that despite not knowing any Italian, I could read it without too much trouble. I suspect from the author’s name that he’s not a native speaker, which probably makes it easier.

Posted by: Tom Leinster on June 20, 2011 5:27 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Yes, I didn’t mean to suggest that I thought Wall’s work was worthless. Just that my conclusion from reading that paper is something along the lines of “there might be a framework for Euler characteristics that applies to more spaces and gives fractional resuls, and here’s some evidence in favor of believing that such a thing might exist: if we make a guess at what sort of answers it would give for some classifying spaces of groups, then the resulting numbers satisfy some of the same identities as the Euler characteristics of classifying spaces to which the existing framework applies.” So it’s definitely encouraging to those of us on the quest for such a more general framework; it’s just not “the answer” that I originally thought it might be when I saw your mention of it.

Posted by: Mike Shulman on June 21, 2011 4:58 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

if categories A and B are in the same connected component of the subcategory 𝒲 ∞⊂Cat, the so-called ‘smallest basic localiser’ (consisting of weak equivalences in the Thomason model structure)

Or, in less hifalutin’ language, if A and B have homotopy equivalent nerves.

On the other hand, the equivalence of the Euler characteristic of a category with that of its nerve doesn’t hold for all categories (right?), so invariance under adjunction for all categories is a stronger statement than you get by just looking at nerves.

The closest I’d come was the following.

Interesting! Of course, the category of elements is a lax colimit, which models a homotopy colimit upon passage to nerves, so that’s indeed very similar.

I feel like there is some bigger picture here that we are only catching glimpses of so far.

I’ll repeat the example here, as it’s so simple.

It is quite a simple example. Moreover, unless I’m mistaken, it is in a certain sense the only example, since if we split all idempotents, making our categories Cauchy complete, then Morita equivalence becomes simply categorical equivalence, and as you said, the Euler characteristic is invariant under that.

This makes me wonder: is the Euler characteristic of a non-Cauchy-complete category, as you define it, “correct”? Or would it be more correct to apply the construction to its Cauchy completion and call the result “the Euler characteristic” of the original category? Are there reasons to believe that the direct definition of Euler characteristic for non-Cauchy-complete categories is correct/interesting/important?

Posted by: Mike Shulman on June 14, 2011 7:14 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Mike wrote:

it is in a certain sense the only example

I agree.

This makes me wonder: is the Euler characteristic of a non-Cauchy-complete category, as you define it, “correct”? Or would it be more correct to apply the construction to its Cauchy completion and call the result “the Euler characteristic” of the original category?

I’ve wondered the same thing myself, though I can’t remember what I decided. Perhaps it’s worth thinking about finite monoids here.

Posted by: Tom Leinster on June 14, 2011 6:46 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Something I forgot to mention in the post was what we know about the magnitude of 22-groupoids. See this comment of Urs and this more recent conversation. For a 2-groupoid XX, we have |X|= [x]1|π 1(X,x)||π 2(X,x)| |X| = \sum_{[x]} \frac{1}{|\pi_1(X, x)|} |\pi_2(X, x)| where the sum is over representatives xx of the connected-components of XX and the bars on the right-hand side denote orders of groups.

The seminar went fine, I think, give or take some loud snoring from the audience.

Posted by: Tom Leinster on June 15, 2011 8:32 AM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Something I forgot to mention

Thanks for mentioning this. I guess if I were as quick with publishing insight as you guys are, I might have published this result about 2-groupoid cardinality in the path integral of the Yetter model about, what is it, three years ago? Somebody should.

Posted by: Urs Schreiber on June 15, 2011 2:36 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Very interesting post !!

If size and metric is possible, what about its dual notion as some kind of “momentum” ? Perhaps there are many questions of this kind. To me enriched category is a little bit like our physical world as a network of physical objects or a condensed matter system. Maybe one should try to define for a nice enriched category many physical notions we know, such as entropy, equilibrium state, etc.

Posted by: Liang Kong on June 26, 2011 2:22 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

I like the finitely generated nCat case. You basically get to simultaneously assign weights to all of the objects, morphisms, 2-morphisms and so on. And then the ∑ζ(i,j)w(j)=1 conditions for nCats, (n-1)-Cats, … connect all of these weights in different “dimension” together.

So if we have vertices A and B, 1-morphisms f,g:A→B and 2-morphism T:f⇒g we get

w(A)=1 (1Cat - summing over all paths to A)
w(f)=1 (2Cat - summing over all paths to f)
w(g)+w(T)w(f)=1 (2Cat - summing over all paths to g)
w(B)+w(f)w(A)+w(g)w(A)=1 (1Cat - summing over all paths to B)

which gives a total magnitude w(A)+w(B)=w(T). The 2-morphism is an element of a 0Cat so it makes sense to assign w(T)=1 giving total magnitude 1. Just what we’d expect for the Euler characteristic of a disk. (Setting w(T)=0 gives 0, what you’d expect for a circle.)

w looks like a bunch of cochains for simplicial cohomology so there’s probably an easy way to see what’s going on from that point of view.

Posted by: Dan P on June 27, 2011 3:18 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

Hi Dan, long time no see. Seeing your name made me remember that you had some posts on Hadwiger’s theorem. I’ll link to them in the other thread.

Until you just pointed it out, I hadn’t realized quite what it meant to find a weighting on an nn-category. As you say, you have to attach weights to ii-morphisms for all i=0,,n1i = 0, \ldots, n - 1.

Let me say that a bit more precisely. A weighting on a finite nn-category consists of a weight w(a)w(a) for each object aa. But those weights have to satisfy some equations, and the equations involve the Euler characteristics or magnitudes of the hom-things Hom(a,b)Hom(a, b), which are (n1)(n - 1)-categories. To compute those, you have to assign a weight to each object of each Hom(a,b)Hom(a, b), that is, to each 11-morphism of the original nn-category. And so it goes on.

I wonder if there’s a nice non-inductive way of stating the equations that all these weights must satisfy. If so, there might be a chance of figuring out how to define the Euler characteristic of an \infty-category.

Posted by: Tom Leinster on June 30, 2011 1:34 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

I’m not sure I’d expect to see something that works for all \infty-categories. Even if you bound the size of the levels as you go up you could still do wildly different things at each stage and I find it hard to imagine something stable emerging. (But I don’t know much about this subject and my intuitions could be way off.)

I think you can give a sensible definition for \infty-categories constructed through a fixed point process. Like the way S S^\infty is a fixed point for the operation of popping out the objects and dropping a level. With such a definition, |S |=1|S^\infty|=1.

Posted by: Dan P on July 1, 2011 4:07 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

S S^{\infty} is contractible, so that’s reassuring.

Something to aim for is to equate the Euler characteristic and homotopy cardinality of S 2S^2 to confirm the Baez-Dolan conjecture.

Posted by: David Corfield on July 1, 2011 5:49 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

David, didn’t we sort out S 2S^2 a while ago? See e.g. this comment and references therein. Or were you after something else?

Posted by: Tom Leinster on July 3, 2011 2:38 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

They had the wacky idea that there should be a sense in which the alternating product of homotopy groups of S 2S^2 should equal 2. So if you form the fundamental infinity groupoid and find its magnitude, there should be some limiting process leading to 2.

At least the two non-torsion parts in degrees 2 and 3 should cancel.

Posted by: David Corfield on July 3, 2011 8:43 PM | Permalink | Reply to this

Re: The Magnitude of an Enriched Category

OK, got you. I hadn’t realized you wanted to treat S 2S^2 as an \infty-groupoid. In the post above I talked about S nS^n as an nn-category, so I assumed you were talking about S 2S^2 as a 2-category. But I think I understand what you’re asking now.

Posted by: Tom Leinster on July 3, 2011 10:34 PM | Permalink | Reply to this
Read the post What is the most beautiful number, and why?
Weblog: Quora
Excerpt: I wonder if I can connect that argument to some of the shenanigans going on over here: http://golem.ph.utexas.edu/category/2011/06/the_magnitude_of_an_enriched_c.html The alternating sums look a lot like computations of Euler characteristics for ∞-ca...
Tracked: July 2, 2011 2:50 PM
Read the post Magnitude of Metric Spaces: A Roundup
Weblog: The n-Category Café
Excerpt: Resources on magnitude of metric spaces.
Tracked: April 7, 2013 9:56 PM

Post a New Comment