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.

January 8, 2011

Magnitude of Metric Spaces: A Roundup

Posted by Tom Leinster

Mark Meckes and I have just arXived one paper each on the magnitude of metric spaces:

This blog has played an important part in the development of the theory. I tried to send Jacques an email thanking him for his role in that, but his spam-blocking software blocked it. So Jacques, if you’re reading: thanks!

It’s a tangled story: you can find online at least 8 papers, 10 blog posts and 12 talks related to this subject, and they really didn’t appear in logical order. The purpose of this post is simply to round up the available material.

I hope that Mark, or I, or both of us, will feel like writing something expository about our new papers—but that’s for another day.

First I should clarify the…

Terminology

From the beginning (p. 38), the idea was that an enriched category should have associated to it a certain fundamental quantity, in a way that I won’t describe now.

Enriched categories include ordinary categories, and in that case it makes sense to call that quantity “Euler characteristic”. This was the first case to be investigated in detail. In turn, categories include sets, and in that case the quantity is cardinality; they also include groupoids, where the quantity is cardinality in the sense of Baez and Dolan.

Enriched categories also include metric spaces. At some point (January 2008) it became clear to me that it was really worth thinking about this quantity for metric spaces. Since the quantity is analogous to cardinality of sets, I made the mistake of calling it “cardinality”, not realizing that “the cardinality of a metric space” would be understood by most people to mean the cardinality of its set of points. (Oddly though, I realized that “Euler characteristic” would be similarly ambiguous.) About a year later Simon Willerton and I discussed alternative names. After rejecting such contenders as “fundamental invariant”, “characteristic” and “bigness”, we settled on—or rather, he rightly persuaded me that we should settle on—magnitude.

So now the convention is to use “magnitude” to refer to the quantity associated to an enriched category. In particular, this applies in the special case of metric spaces (categories enriched in [0,][0, \infty]). For ordinary categories (enriched in Set) and algebroids or linear categories (enriched in Vect) it’s appropriate to use “Euler characteristic” as a synonym.

Upshotin the various writings on this, the terms “cardinality”, “Euler characteristic” and “magnitude” are more or less interchangeable.

(To digress slightly, this terminological slipperiness arises from an interesting mathematical phenomenon: forgetful functors don’t preserve magnitude, although free functors do. That’s a rule of thumb rather than a theorem, but it means you need to be super-careful. For example, if XX is a metric space and U(X)U(X) its set of points then you need to distinguish between the magnitude of XX and the magnitude/cardinality of U(X)U(X).)

 

Here now is the list of online materials on magnitude of enriched categories (including categories and metric spaces). Of course there are many precursors in the literature: this didn’t come out of thin air. But I’ll begin where my own involvement began, which is also where (to my knowledge) the definition of the magnitude of an enriched category first appeared.

Papers

I’ll give the arXiv date of each paper, but the chronological order is nothing like the logical order. (E.g. much of my recent paper is really a logical precursor to the other ones about metric spaces, but I took a long time writing it up.)

  1. The Euler characteristic of a category (me, October 2006)
  2. The Euler characteristic of a category as the sum of a divergent series (Clemens Berger and me, July 2007)
  3. On the asymptotic magnitude of subsets of Euclidean space (Simon and me, August 2009)
  4. Heuristic and computer calculations for the magnitude of metric spaces (Simon, October 2009)
  5. A maximum entropy theorem with applications to the measurement of biodiversity (me, October 2009)
  6. On the magnitude of spheres, surfaces and other homogeneous spaces (Simon, May 2010)
  7. Positive definite metric spaces (Mark, December 2010)
  8. The magnitude of metric spaces (me, December 2010).

Blog posts

  1. Euler characteristic of a category (David, October 2006)
  2. This week’s finds in mathematical physics (week 244) (John, February 2007)
  3. Return of the Euler characteristic of a category (David, July 2007)
  4. Metric spaces (me, February 2008)
  5. Entropy, diversity and cardinality (part 1) (me, October 2008)
  6. Entropy, diversity and cardinality (part 2) (me, November 2008)
  7. Asymptotics of the magnitude of metric spaces (me, about the joint paper with Simon, August 2009)
  8. More magnitude of metric spaces and problems with penguins (Simon, October 2009)
  9. An adventure in analysis (me, November 2009)
  10. Intrinsic volumes and Weyl’s tube formula (Simon, March 2010)
  11. On the magnitude of spheres, surfaces and other homogeneous spaces (Simon, April 2010)

Talks

I might have missed some things. Let me know!

Update (7 April 2013)

I’ll add a few more resources that have appeared since I wrote this post.

Papers

Blog posts

Talks

If I’m really organized, I’ll keep this updated.

Posted at January 8, 2011 2:38 PM UTC

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

25 Comments & 0 Trackbacks

Re: Magnitude of Metric Spaces: A Roundup

If “the chronological order is nothing like the logical order”, is there a good order in which to approach these papers and blog posts, if we’re coming to this for the first time? It looks like the October 2006 paper and post would be a good starting point (or is there something else we should read before those?), but after that where does the story most naturally continue?

Posted by: Stuart on January 10, 2011 7:42 AM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

Since Tom hasn’t tried to answer this yet, I’ll take a stab at it. To make the task simpler, I’ll ignore the blog posts and try to suggest an order in which to read the papers. Here are a few general points to know:

  1. All the later papers are essentially independent of the first two. If you’re primarily interested in metric spaces then you can skip them, although they are the source of the motivation of the theory. (I only read “The Euler characteristic of a category” after writing my own paper on magnitude, although I was aware of the basic ideas since Week 244, and I haven’t read “… as the sum of a divergent series” yet.)

  2. The last paper in Tom’s list, “The magnitude of metric spaces”, includes all the basic motivation and background, although it also addresses some questions raised (implicitly or explicitly) in some of Tom and Simon’s earlier papers.

  3. Most of the papers on magnitude written before “The magnitude of metric spaces” are pretty self-contained and independent of each other, although they would probably seem better motivated if read after “The magnitude of metric spaces”.

  4. My paper, “Positive definite metric spaces”, is mathematically self-contained, but depends crucially on “The magnitude of metric spaces”, and to a lesser extent on all three papers that Simon wrote or co-wrote, for the motivation of many results.

  5. My paper and all the papers Simon was involved in are primarily about infinite metric spaces, whereas “A maximum entropy theorem…” is about finite spaces, so these represent two different threads.

So with all that said, here’s my suggested reading order if you want to see some kind of logical development of the subject.

  1. The Euler characteristic of a category (can be saved for later if you’re primarily interested in metric spaces)

  2. The Euler characteristic of a category as the sum of a divergent series (can be saved for later if you’re primarily interested in metric spaces)

  3. The magnitude of metric spaces

  4. A maximum entropy theorem with applications to the measurement of biodiversity

  5. On the asymptotic magnitude of subsets of Euclidean space

  6. Heuristic and computer calculations for the magnitude of metric spaces

  7. On the magnitude of spheres, surfaces and other homogeneous spaces

  8. Positive definite metric spaces

Posted by: Mark Meckes on January 10, 2011 2:48 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

Ah, that’s a relief. Thanks, Mark. I was finding it pretty difficult to answer Stuart’s question. Next to me is a piece of paper on which I drew, earlier today, an interdependency diagram for the different papers, but I hadn’t managed to make that partial order total.

I’ll add a few things. First, Mark’s being modest about what’s in “Positive definite metric spaces”. Earlier papers on magnitude were beset with the difficulty that it wasn’t clear how to define the magnitude of infinite metric spaces. So, for example, in “The asymptotic magnitude…”, Simon and I have a sequence A 1A 2A_1 \subseteq A_2 \subseteq \cdots of finite subsets of the Cantor set, whose union is dense in the Cantor set, and we simply declare the magnitude of the Cantor set to be the limit of the magnitudes of the A nA_ns. Then again, in “On the magnitude of spheres…”, Simon defines the magnitude of infinite spaces using integration. Among other things, Mark’s paper shows that all these different approaches are guaranteed to give the same result—so there’s no need to worry.

Second, in some ways it’s beneficial that the papers were written in a funny order. Because the paper that goes systematically through the basics (“The magnitude of metric spaces”) has only just appeared, all the previous papers were forced to be self-contained, as Mark observed. So, for example, the historically first paper on magnitude of metric spaces (“Asymptotic”) contains quite a lot of introductory material.

Third, if you want an up-to-date, high-level summary of the results, you should look at Mark’s excellent talk. You can also see a lot of this, together with explanatory graphics and compelling numerical evidence for the conjectures we’ve made, in Simon’s Barcelona talk

Finally, in case you’re the Stuart I think you are, I’ll say a bit about “A maximum entropy theorem…”, which I haven’t said much about previously on this blog. As Mark says, it differs from the others by being about finite spaces. It also differs (I hope) from the others by being somewhat unreadable: it’s just a preliminary version, and whizzes through the results in a theorem-proof-theorem-proof way. The idea is that magnitude can be interpreted as maximum diversity, at least under certain circumstances, and in any case magnitude is closely related to maximum diversity. The “diversity” in question is a close relative of entropy, with links to information theory. The choice of word comes from the study of biological diversity, which we’ve just been discussing over here.

Posted by: Tom Leinster on January 10, 2011 3:54 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

I wrote:

Earlier papers on magnitude were beset with the difficulty that it wasn’t clear how to define the magnitude of infinite metric spaces

and that Mark’s paper sorted this out. That’s true, in the sense that his paper shows that the various methods people have used for defining the magnitude of infinite spaces will always give the same result. For instance, Simon and I defined the magnitude of the Cantor set by finite approximations, and Simon defined the magnitude of homogeneous Riemannian manifolds using integration, but it would be equivalent to use integration for the Cantor set and finite approximation for manifolds.

On the other hand, it’s still not clear what the most satisfactory conceptual framework is for the magnitude of infinite spaces. Understanding that is closely related to understanding magnitude for infinite enriched categories of other kinds. At the moment it seems quite mysterious.

Posted by: Tom Leinster on January 10, 2011 4:08 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

There’s a caveat that should be added to Tom’s characterization of what I proved, which is hinted at by the title of my paper. I showed that various methods of defining magnitude of (compact) infinite metric spaces give the same result, if the metric spaces are “positive definite” (which I won’t bother defining here). A lot of interesting metric spaces are positive definite, as was realized partly in the comments to some of the blog posts Tom linked to above.

However, positive definiteness allows a reformulation of the problem which doesn’t work for general metric spaces. This is part of why my results don’t shed as much light on the most satisfactory conceptual framework for magnitude as one might hope. I suppose they may help understand magnitude for some appropriate class of “positive definite infinite enriched categories”, if indeed there is an interesting such class beyond metric spaces.

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

Re: Magnitude of Metric Spaces: A Roundup

One thing that separates metric spaces from other enriched categories is people’s willingness to assume symmetry. Indeed, d(a,b)=d(b,a)d(a, b) = d(b, a) is a classical axiom on metric spaces, but for a general enriched category, asking that Hom(a,b)Hom(b,a)Hom(a, b) \cong Hom(b, a) feels like a strong requirement. There are interesting conditions under which it happens, e.g. when you have some kind of duality. But still, it’s far from the most general situation.

The work we’ve done with positive definite metric spaces presupposes symmetry. I suppose one might define a (not necessarily symmetric) real matrix ZZ to be positive definite if v *Zv>0v^* Z v \gt 0 for all v0v \neq 0 (where v *v^* is the transpose of vv), but that’s equivalent to asking that the symmetrization (Z+Z *)/2(Z + Z^*)/2 of ZZ is positive definite. Is there a useful notion of positive definiteness for non-symmetric matrices?

Posted by: Tom Leinster on January 12, 2011 1:17 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

Is there a useful notion of positive definiteness for non-symmetric matrices?

Not that I know of. In my experience, when forced to deal with non-symmetric matrices one usually looks for something different to substitute for positive definiteness, like the singular value decomposition or Perron-Frobenius theory. The latter is potentially promising in the context of magnitude of enriched categories, since one would typically be working with matrices with nonnegative entries.

Posted by: Mark Meckes on January 12, 2011 4:36 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

Is there a useful notion of positive definiteness for non-symmetric matrices?

What qualities are you looking for in this useful notion?

Posted by: David Corfield on January 13, 2011 11:47 AM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

What I had in my mind was the kind of qualities that would let us define magnitude for infinite enriched categories. That’s what positive definiteness (together with compactness) lets us do for (symmetric) metric spaces.

The key lemma about positive definiteness and magnitude is as follows. Let ZZ be a symmetric positive definite matrix with entries in [0,1][0,1] and 11s down the diagonal. Then the magnitude of ZZ is the maximum of 1/v *Zv 1/v^* Z v over all real column vectors vv such that iv i=1\sum_i v_i = 1. Here ** means transpose. (Proof: basically the Cauchy–Schwarz inequality.)

A non-symmetric generalization of that would be a start.

Posted by: Tom Leinster on January 13, 2011 1:17 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

I should also have given the short answer to Stuart’s question, for those who are in a hurry to get to the punchline about magnitude: read “The magnitude of metric spaces” first, then follows its references, wherever you’re interested, to the other papers.

Posted by: Mark Meckes on January 10, 2011 8:30 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

Do people have a sense of whether magnitude for other cases of enrichment will be interesting, e.g., strict 2-categories enriched in CatCat or dg-categories enriched in chain complexes?

Posted by: David Corfield on January 10, 2011 11:20 AM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

David, you have an uncanny ability to anticipate what people are about to say. When I get round to writing something expository on this, it’ll be on magnitude of enriched categories.

Here are the base categories (the “𝒱\mathcal{V}s”) that have crossed my mind:

  • SetSet, giving ordinary categories and their Euler characteristics.
  • [0,][0, \infty], giving metric spaces and their magnitudes.
  • 2\mathbf{2} (the 2-element totally ordered set), giving posets and their Euler characteristics. This was largely explored by Rota and his school, and is a special case of each of the first two theories (as long as we allow non-symmetric metrics, à la Lawvere).
  • VectVect, giving algebroids/linear categories and their Euler characteristics. Catharina Stroppel and I found some results here connecting this with homological invariants of associative algebras. This has yet to be written up.
  • Set Set^{\mathbb{N}}, giving “\mathbb{N}-graded categories” and their Euler characteristics. I know a little bit about this, and it appears as an example in something I’m writing at the moment.
  • TopTop (or probably some subcategory such as finite CW-complexes), giving topological categories and their Euler characteristic. I don’t really know anything about this.
  • (n1)Cat(n - 1)Cat, giving nn-categories and their Euler characteristics. Almost everything I know about this (not much!) is in the 2006 paper. A nice example is that if S nS^n denotes the nn-category generated by a parallel pair of nn-cells, then the Euler characteristic of S nS^n is equal to the topological Euler characteristic of the nn-sphere (that is, 1+(1) n1 + (-1)^n).
  • [0,][0, \infty] with maxmax as the tensor, giving ultrametric spaces. I had some not very productive thoughts about this, but Mark has recently made some interesting discoveries here.
  • Vect Vect^\mathbb{N}, giving graded linear categories. Don’t know anything special about this.
  • SSetSSet (simplicial sets), giving simplicial categories. Don’t know anything special about this either.
  • ChCh (chain complexes), giving differential graded categories. Equally ignorant here.
Posted by: Tom Leinster on January 10, 2011 12:09 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

One check for strict 2-categories (enrichment over CatCat) would be whether they yield the Baez-Dolan cardinality in the case of overlap with 2-groupoids, just as your cardinality of a category agrees with theirs for groupoids.

The infinity-groupoid cardinality for a homotopy 2-type is

|X|:= [x]1|π 1(X,x)||π 2(X,x)|. |X| := \sum_{[x]} \frac{1}{|\pi_1(X,x)|} |\pi_2(X,x)|.

Posted by: David Corfield on January 10, 2011 1:07 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

OK, good question.

Let’s make sure we agree on definitions. A 2-groupoid is a 2-category (strict or weak, doesn’t matter here) in which every 1-cell is an equivalence and every 2-cell is an isomorphism. Given an object xx of a 2-groupoid XX, π 1(X,x)\pi_1(X, x) is the group of isomorphism classes of 1-cells xxx \to x, and π 2(X,x)\pi_2(X, x) is the group of 2-cells 1 x1 x1_x \to 1_x.

Here’s what I hope is a fact: for a 1-cell f:xxf: x \to x, the group of 2-cells fff \to f is isomorphic to π 2(X,x)\pi_2(X, x). (It shouldn’t be difficult to settle and I’m sure it’s standard, but I’m being lazy.) I’ll assume that in what follows; maybe someone could confirm?

In that case, the answer to your question is yes.

Since both 2-groupoid cardinality |||\cdot| and Euler characteristic (== magnitude) χ\chi respect sums, it suffices to consider the case that XX has precisely one connected-component. Since they’re both also invariant under 2-equivalence, it suffices to consider the case that XX has precisely one object, xx say.

Now χ(X)=1/χ(X(x,x))\chi(X) = 1/\chi(X(x, x)) immediately from the definition, where the denominator here is the Euler characteristic of the groupoid X(x,x)X(x, x). But we already know that the Euler characteristic of a groupoid is the same as its Baez–Dolan cardinality, namely [f]1|Aut(f)| \sum_{[f]} \frac{1}{|Aut(f)|} where the sum is over representatives of isomorphism classes of 1-cells f:xxf: x \to x, and the denominator is the order of the group of 2-cells fff \to f. By the “fact”, Aut(f)π 2(X,x)Aut(f) \cong \pi_2(X, x) for all ff. The number of terms in the sum is the order of the group π 1(X,x)\pi_1(X, x). Hence χ(X(x,x))=|π 1(X,x)||π 2(X,x)| \chi(X(x, x)) = \frac{|\pi_1(X, x)|}{|\pi_2(X, x)|} (where as in your formula, both uses of |||\cdot| mean the order of a group). So χ(X)=1χ(X(x,x))=|X|, \chi(X) = \frac{1}{\chi(X(x, x))} = |X|, as required.

Posted by: Tom Leinster on January 10, 2011 2:02 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

Your guess about π 2\pi_2 is correct, Tom. It’s shown in one of the Hardie-Kamps-Kieboom papers on fundamental 2-/bigroupoids.

Posted by: David Roberts on January 11, 2011 1:13 AM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

Thanks, David.

Posted by: Tom Leinster on January 11, 2011 7:29 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

One check for strict 2-categories (enrichment over Cat) would be whether they yield […] the \infty-groupoid cardinality

Two or three years back I had used Tom’s definition to find the 2-groupoid cardinality of the 2-groupoid of configurations of the Yetter model and showed that it yields the path integral measure for that theory. See here. I think I checked this back then.

This is in direct analogy to how the 1-groupoid measure of the groupoid of configurations of Dijkgraaf-Wittemn theory yields its path integral measure.

There is meanwhile a grand continuation of this story indicated in the last part of TQFT from compact Lie groups.

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

Re: Magnitude of Metric Spaces: A Roundup

Ah yes, there it is.

Posted by: Tom Leinster on January 10, 2011 4:11 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

Any scope for magnitudes of categories more generally enriched, perhaps up to enrichment in your fc-multicategories?

Was that example of Simon’s about bakeries and shops not an example of enrichment over a bicategory with two objects, BB and SS, with morphisms possible transport costs?

Posted by: David Corfield on January 11, 2011 9:12 AM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

When enriching over a bicategory, you could consider for each pair of objects, aa and bb, a monoid homomorphism from the decategorification of whatever Hom(a,b)Hom(a, b) takes values in to a common rig kk.

Posted by: David Corfield on January 11, 2011 11:24 AM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

Good questions… but don’t know the answers! I also wondered about Simon’s enrichment in categories of subsets.

Posted by: Tom Leinster on January 11, 2011 7:36 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

I might have missed some things. Let me know!

Under blog posts, you could also include Week 244.

Posted by: Mark Meckes on January 10, 2011 2:15 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

How could I have missed that? Included now. Thanks!

Posted by: Tom Leinster on January 10, 2011 3:58 PM | Permalink | Reply to this

Re: Magnitude of Metric Spaces: A Roundup

I just updated the list of available resources, adding some more at the end of the post. Perhaps I’ll try to keep doing this, as and when new papers, posts, etc. appear.

Posted by: Tom Leinster on April 7, 2013 10:02 PM | Permalink | Reply to this

Magnitude for spaces with action or “squared distance”

Has anyone tried to study the notion of magnitude for the following class of non-symmetric metric spaces:

S=C×[0,1]S = C \times [0,1], where CC is, say, a compact convex subset of d\mathbb{R}^d, and the distance is given by the least action:

ρ((x 1,t 1),(x 2,t 2))={+, t 1t 2or(t 1=t 2andx 1x 2) 0, (x 1,t 1)=(x 2,t 2) x 1x 2 22(t 2t 1), t 1t 2\rho((x_1,t_1),(x_2,t_2)) = \begin{cases}+\infty, & t_1 \gneq t_2 \, \text{or} \, (t_1=t_2 \, \text{and} \, x_1\neq x_2)\\0, & (x_1,t_1)=(x_2,t_2)\\\frac {\left\Vert x_1-x_2\right\Vert^2} {2 (t_2-t_1)}, & t_1 \lneq t_2\end{cases}

(sorry for \gneq, it should be replaced by “>”, but I couldn’t get it right inside the formula)

The reasons why I’m interested in that are both conceptual and technical:

1. It looks like the natural setting for both mechanics and the study of diffusion processes is that of an “action space” instead of a metric space, so this may be thought of, as you say, decategorification of something where hom-objects are spaces of curves.
2. It should be easier: the similarity matrix is triangular, therefore invertible; squared distances also behave better under Euclidean products.

Another argument for squared distances is the following: sometimes we don’t have a distance at all, but we do have a kind of squared distance. For example, if KK is a positive definite kernel, then it defines a metric space with ρ(x,y)=(K(x,x)+K(y,y)2K(x,y)) 1/2\rho(x,y) = (K(x,x) + K(y,y) - 2K(x,y))^{1/2} that is embeddable into Hilbert space. If, however, KK is still positive definite, but only defined almost everywhere and has a blowup on the diagonal (i.e. it’s not trace class), then there are no distances anymore, but expK\exp K may serve as a substitute for exp(ρ 2/2)\exp (-\rho^2/2) for the purpose of measuring a kind of rescaled magnitude.

Posted by: Alexander Shamov on January 22, 2014 10:43 PM | Permalink | Reply to this

Post a New Comment