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.

August 13, 2009

Asymptotics of the Magnitude of Metric Spaces

Posted by John Baez

guest post by Tom Leinster

Simon Willerton and I have just arXived a new paper, On the asymptotic magnitude of subsets of Euclidean space. It’s about a subject that owes a lot to the nn-Café: the cardinality of metric spaces. Before we submit it to a journal, we’d be interested and grateful to have your comments — anything from typos to matters of philosophy.

Here’s the idea. Cardinality is supposed to play the same kind of role for metric spaces as ordinary cardinality plays for sets. Now, a fundamental property of the cardinality of finite sets is the inclusion-exclusion principle:

|AB|=|A|+|B||AB|. |A \cup B| = |A| + |B| - |A \cap B|.

Here AA and BB are sets and |  ||  | means ordinary cardinality. But what if, say, AA and BB are compact subsets of n\mathbb{R}^n and |  ||  | means metric cardinality? Does the inclusion-exclusion principle hold?

The answer is ‘no’, but it’s a particularly interesting ‘no’ — probably more interesting than ‘yes’ would have been. It’s ‘no, but asymptotically yes’, at least in the cases we’ve succeeded in analyzing.

To explain this I’ll have to back up a bit.

First, Simon and I decided that ‘the cardinality of a metric space’ was too confusing a phrase: people hearing it for the first time think it means the cardinality of the set of points. So, we decided to switch to magnitude.

Second, magnitude was only defined for finite metric spaces. But there’s a rather hands-on strategy for extending the definition to compact metric spaces AA: take a sequence A 0A 1A_0 \subseteq A_1 \subseteq \cdots of finite subspaces, with A n\bigcup A_n dense in AA, and try to define

|A|=lim n|A n|. |A| = \lim_{n \to \infty} |A_n|.

There are all sorts of things that could go wrong with this strategy, but sometimes it works, or at least works well enough to enable us to get somewhere. For example, we use it to calculate the magnitudes of straight line segments, circles, and middle-third Cantor sets.

Third, a lot is known about ‘measures’ satisfying the inclusion-exclusion principle on subsets of n\mathbb{R}^n. These are known as valuations. If you restrict to polyconvex sets (finite unions of compact convex sets) then the valuations are completely classified. This is Hadwiger’s Theorem. (I’m glossing over some details here: really we want the valuations to have a couple of further properties. See the link.) For example, Hadwiger tells us that any valuation on 2\mathbb{R}^2 must be of the form

α 0Eulercharacteristic+α 1perimeter+α 2area \alpha_0 \cdot Euler characteristic + \alpha_1 \cdot perimeter + \alpha_2 \cdot area

where α 0\alpha_0, α 1\alpha_1 and α 2\alpha_2 are constants. We’ll want to go outside the world of polyconvex sets, since there are many common non-polyconvex spaces for which Euler characteristic, perimeter etc. have obvious meanings (e.g. circles). But we’ll continue to use Hadwiger’s Theorem as a guide.

Finally, there’s a pesky technical point that I feel obliged to put in for anyone taking the trouble to follow in detail. Skip it if you’re not. The original definition of magnitude/cardinality involved some terms of the form e 2d(a,b)e^{-2d(a,b)}. We switched to e d(a,b)e^{-d(a,b)}. So if, in what follows, you’re ever surprised by a factor of 22, you know why.

Now I can tell the story! We’ve known for a while that the magnitude of a line segment (closed interval) of length LL is

1+L/2=1Eulercharacteristic+12perimeter. 1 + L/2 = 1 \cdot Euler characteristic + \frac{1}{2} \cdot perimeter.

Let’s consider the magnitude of, say, ‘nice’ subsets of 2\mathbb{R}^2. If magnitude satisfies the inclusion-exclusion principle, then Hadwiger’s Theorem suggests that it is probably a linear combination of Euler characteristic, perimeter and area. The example of the line segment tells us what the first two coefficients must be. So, if circles are ‘nice’ then the magnitude of a circle C LC_L of circumference LL should be

1Eulercharacteristic+12perimeter=10+12L=L/2. 1 \cdot Euler characteristic + \frac{1}{2} \cdot perimeter = 1 \cdot 0 + \frac{1}{2} \cdot L = L/2.

Is that true? No! But it’s asymptotically true; that is,

lim L(|C L|L/2)=0. \lim_{L \to \infty} (|C_L| - L/2) = 0.

Crudely put: for large LL,

|C L|1Eulercharacteristic+12perimeter. |C_L| \approx 1 \cdot Euler characteristic + \frac{1}{2} \cdot perimeter.

There’s an infinite family of sensible metrics you can put on the circle, and this result holds for all of them. The proof — even for the plain old subspace metric — uses some techniques of asymptotic analysis. Thanks to Bruce Bartlett for tracking down the key result.

Now let’s try another example: the Cantor set, defined as usual by successively removing middle thirds from a line segment. Let T LT_L be the Cantor set whose endpoints are distance LL apart. This is a different kind of animal from the line or the circle: it’s not obvious what Euler characteristic and perimeter would even mean. (On the other hand, we do expect a nonzero measure of dimension log 32\log_3 2, since that’s the Hausdorff dimension of T LT_L.) Let’s use the self-similarity of the Cantor set instead. Since T LT_L consists of two disjoint copies of T L/3T_{L/3}, the inclusion-exclusion principle suggests

|T L|=2|T L/3|. |T_L| = 2|T_{L/3}|.

Is that true? No! But it’s asymptotically true; that is,

lim L(|T L|p(L))=0 \lim_{L \to \infty}(|T_L| - p(L)) = 0

for a certain function pp satisfying

p(L)=2p(L/3). p(L) = 2p(L/3).

(It follows that |T L||T_L| grows like L log 32L^{\log_3 2}.) Crudely put: for large LL,

|T L|2|T L/3|. |T_L| \approx 2|T_{L/3}|.

Here’s an intuitive explanation. Magnitude respects coproducts, meaning that if AA and BB are metric spaces and we write A+BA + B for their ‘distant union’ (the disjoint union with d(a,b)=d(a, b) = \infty for all aAa \in A and bBb \in B) then |A+B|=|A|+|B||A + B| = |A| + |B|. The union T L=T L/3T L/3T_L = T_{L/3} \cup T_{L/3} is disjoint. It’s not distant, since the two copies of T L/3T_{L/3} are distance L/3L/3, not \infty, apart — but when LL is large, it’s nearly distant, so the magnitude formula nearly holds.

(Incidentally, there’s a little surprise: it turns out that inside the Cantor set, a periodic function is hiding! But you’ll have to read the paper to find out about that.)

All this evidence led us to make a conjecture. Roughly, it says that the inclusion-exclusion principle is satisfied asymptotically for compact subsets of n\mathbb{R}^n, and exactly for convex sets.

Strong Asymptotic Conjecture  There is a unique function P:{compactsubsetsof n}P: \{ compact subsets of \mathbb{R}^n \} \to \mathbb{R} such that

  • lim t(|tA|P(tA))=0\lim_{t \to \infty} (|t A| - P(t A)) = 0 for all AA, where tAt A denotes AA scaled up by a factor of tt
  • PP satisfies the inclusion-exclusion principle: P(AB)=P(A)+P(B)P(AB)P(A \cup B) = P(A) + P(B) - P(A \cap B) and P()=0P(\emptyset) = 0
  • when AA is polyconvex, P(A)P(A) is a certain specific linear combination of the intrinsic volumes of AA
  • when AA is convex, |A|=P(A)|A| = P(A) (i.e. |A||A| is exactly that linear combination of intrinsic volumes).

Atiyah is supposed to have said something like ‘if you don’t understand a conjecture, generalize it’. Our conjecture might be too strong — and we have a Weak Asymptotic Conjecture too — but we believe that something like it is true.

Posted at August 13, 2009 6:31 PM UTC

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

25 Comments & 4 Trackbacks

Re: Asymptotics of the Magnitude of Metric Spaces

the magnitude of a line segment (closed interval) of length LL is 1+L/2=1Eulercharacteristic+12perimeter. 1 + L/2 = 1 \cdot {Euler characteristic} + \frac{1}{2} \cdot {perimeter} .

Maybe I should read your paper first, but I would have said that that's 1/41/4 of the perimeter. Otherwise you'll be claiming that the limit of the magnitude of a very thin rectangle as its width (and hence area) goes to zero is almost twice the magnitude of a line segment: lim W0(11+12(2L+2W)+α 2LW)=1+L1+L/2, \lim_{W \to 0} \left(1 \cdot 1 + \frac{1}{2} \cdot (2L + 2W) + \alpha_2 \cdot LW\right) = 1 + L \ne 1 + L/2 , which I find hard to believe if this is supposed to measure compact subsets of 2\mathbb{R}^2.

Posted by: Toby Bartels on August 13, 2009 8:03 PM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

Thanks, Toby. You’re right. The word ‘perimeter’ doesn’t actually appear in our paper, so this is purely a problem with the post.

Rather than say ‘1/41/4 of the perimeter’, as you suggest, I’d prefer to say ‘1/21/2 of the semiperimeter’. Let me explain…

First I’ll state Hadwiger’s Theorem precisely.

Fix n0n \geq 0. Write P n\mathbf{P}_n for the set of polyconvex (== finite unions of compact convex) subsets of n\mathbb{R}^n. Let V nV_n be the set of all functions P n\mathbf{P}_n \to \mathbb{R} that:

  1. are valuations (that is, obey the inclusion-exclusion principle, including sending \emptyset to 00)
  2. are invariant under rotations and translations
  3. when restricted to convex subsets of n\mathbb{R}^n, are continuous with respect to the Hausdorff metric.

(I glossed over the last two points in the post.) Then V nV_n is naturally a real vector space.

Hadwiger’s Theorem states that V nV_n is (n+1)(n+1)-dimensional and has a basis μ 0 n,μ 1 n,,μ n n\mu_0^n, \mu_1^n, \ldots, \mu_n^n such that μ d n\mu_d^n is dd-dimensional (meaning that μ d n(tA)=t dμ d n(A)\mu_d^n(t A) = t^d \mu_d^n(A) for all polyconvex AA and t>0t > 0).

The valuations μ d n\mu_d^n are uniquely determined up to multiplication by a nonzero scalar. So we have to choose a normalization. It’s best to choose one that gets along well with the usual embedding of n\mathbb{R}^n into n+1\mathbb{R}^{n + 1}. For example, if you had a subset A 2A \subseteq \mathbb{R}^2 you might sometimes want to regard it as a subset of 3\mathbb{R}^3, and it would be nice not to have to fuss over whether ‘the 11-dimensional measure of AA’ meant μ 1 2(A)\mu_1^2(A) or μ 1 3(A)\mu_1^3(A). In other words, it would be good to be able to drop the superscripts and talk about ‘the dd-dimensional measure μ d\mu_d’.

The usual way to arrange this is as follows. In each dimension nn, the top-dimensional measure μ n n\mu_n^n is a multiple of Lebesgue measure. So, let’s take it to be Lebesgue measure. If we insist on this and the property in the previous paragraph then we’ve tied everything down. Thus, for each d0d \geq 0 we have a measure μ d\mu_d of polyconvex subsets of n\mathbb{R}^n (ndn \geq d), normalized so that μ d([0,1] d)=1\mu_d([0, 1]^d) = 1.

Now to come to your point! Taking d=1d = 1, this says μ 1([0,1])=1\mu_1([0, 1]) = 1. One can also show that μ 1([0,L]×[0,W])=LW. \mu_1([0, L] \times [0, W]) = L W. There deserves to be a name for μ 1\mu_1, and there kind of already is: semiperimeter. I guess I’d got so used to thinking of semiperimeter as being ‘the normalized version of perimeter’ that I simply used the word ‘perimeter’, which was a mistake.

Posted by: Tom Leinster on August 13, 2009 10:26 PM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

Tom Leinster wrote in part:

μ 1([0,L]×[0,W])=LW\mu_1([0,L] \times [0,W]) = L W

Now I'm sure that you mean μ 1([0,L]×[0,W])=L+W\mu_1([0,L] \times [0,W]) = L + W (and μ 2([0,L]×[0,W])=LW\mu_2([0,L] \times [0,W]) = L W).

Posted by: Toby Bartels on August 14, 2009 1:12 AM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

Yes, sorry. L+WL + W it is.

Glad to learn that you read (to?) the end of my comment though :-)

Posted by: Tom Leinster on August 14, 2009 3:00 AM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

Glad to learn that you read (to?) the end of my comment though :-)

Oh yes, I certainly read your comment. I'll probably even read your paper, tomorrow or Saturday.

Posted by: Toby Bartels on August 14, 2009 6:29 AM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

Very nice paper! I am thinking about how to formalize the notion that all the different metrics on the circle give the same asymptotic magnitude. Here is a conjecture:

Let d and d’ be two equivalent metrics on the same underlying set, and let that set be compact in the resulting topology. Let’s say that d and d’ are “strongly equivalent” if, for every epsilon>0, there is a delta > 0 such that,

(1) whenever d(x,y) < delta than (1-epsilon) d’(x,y) < d(x,y) < (1+epsilon) d’(x,y)

and

(2) same as (1), with d and d’ interchanged.

Conjecture: your function P only depends on the strong equivalence class of your metric.

Basically, this says that P(A) only depends on the local structure of the metric involved.

Posted by: David Speyer on August 14, 2009 5:24 PM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

Hmmm, I was too optimistic. Here are some strange examples.

Let f be a concave, increasing, function from 0\mathbb{R}_{\geq 0} to itself, with latexf(x)=xax 2+O(x 3)latex f(x) = x - a x^2 + O(x^3) for small xx. For example, ff could be 1+2x1\sqrt{1+2x}-1 or log(1+x)\log(1+x).

Put a metric on the real line by d(x,y)=f(|xy|)d(x,y) = f(|x-y|), and put the quotient metric on the circle /\mathbb{R}/\ell \mathbb{Z}. Call the resulting space S()S(\ell), and let rS()r S(\ell) be the space where we rescale the metric by rr.

Using n equally spaced points, and converting the sum to an integral, the magnitude of rS()r S(\ell) is

/ /2 /2e rf(t)dt=/(2 0 /2e rf(t)dt)\ell / \integral_{- \ell/2}^{\ell/2} e^{- r f(t)} dt = \ell/\left(2 \integral_0^{\ell/2} e^{-r f(t)} dt \right).

Let’s look at that integral. For r large, all of the interest is near zero, so it is roughly

0 e rt+art 2+dt=(1/r) 0 e u+au 2/r+\integral_0^{\infty} e^{-rt + a r t^2 + \ldots} dt = (1/r) \integral_0^{\infty} e^{-u+a u^2/r + \ldots} =(1/r) 0 e u(1+au 2/r+)=1/r+2a/r 2=(1/r) \integral_0^{\infty} e^{-u} (1+a u^2/r + \ldots) = 1/r + 2a/r^2.

So the magnitude of rS()r S(\ell) is r/2a\ell r/2 - \ell a. In particular, the magnitude can see that funny convexity.

Posted by: David Speyer on August 14, 2009 9:40 PM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

That’s very interesting! When I first saw your conjecture, I could see no reason for it not to be true.

I think the conjectures of our paper can be generalized in a different direction. For each p[1,]p \in [1, \infty] you can put the ‘d pd_p’ metric on n\mathbb{R}^n, where distance is defined as a ppth root of sums of ppth powers. The d 1d_1 metric is the one that comes immediately out of regarding metric spaces as enriched categories; this choice of pp tends to make life easiest. The d 2d_2 metric is the one we’re by far the most used to, and is the subject of our paper. One can try to formulate a version of our conjectures for arbitrary pp. I have some ideas about how to do this. More another time maybe…

Posted by: Tom Leinster on August 15, 2009 11:23 PM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

Continuing with the odd examples, I think the embedded and intrinsic metrics on a sphere should give different answers. (By embedded I mean measuring through space, whereas by intrinsic I mean along the sphere.) Heuristically, if XX is a homogoeneous metric space, with invariant measure dAdA, we should expect the magnitude of rXr X to be

dA/e rd(p,x)dA\integral dA/\integral e^{-r d(p,x)} dA

where pp is (any) given point of XX and xx is the variable of integration.

For the intrinsic sphere, I get the denominator to be

0 πe rθ2πsinθdθ\integral_0^{\pi} e^{-r \theta} 2 \pi \sin \theta d \theta

whereas, for the embedded sphere, I get

0 πe r2sin(θ/2)2πsinθ\integral_0^{\pi} e^{- r 2 \sin(\theta/2)} 2 \pi \sin \theta

Substituting θ=u/r\theta = u/r, I get

2π/r 2 0 e u(uu 3/6r 2+)du2 \pi/r^2 \integral_0^{\infty} e^{-u} (u-u^3/6 r^2+\cdots) du

and

2π/r 2 0 e u+u 3/24r 2+(uu 3/6r 2+)du=2π/r 2 0 e u(uu 3/8r 2+)du2 \pi/r^2 \integral_0^{\infty} e^{-u + u^3/24 r^2 + \cdots} (u-u^3/6 r^2+\cdots) du = 2 \pi/r^2 \integral_0^{\infty} e^{-u} (u-u^3/8 r^2+\cdots) du

These should be

2π/r 2+a/r 4+2 \pi/r^2 + a/r^4 + \cdots and 2π/r 2+b/r 42 \pi/r^2 + b / r^4 for different numbers aa and bb (which are easy enough to compute, but I am lazy.) When we take reciprocals, that should give different constant terms.

So the constant term in the magnitude of the embedded sphere and the intrinsic sphere should be different. I find this discomforting …

Posted by: David Speyer on August 14, 2009 9:59 PM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

One more thought: you talk a lot about taking a function |t*A| and splitting it into a growing component and a decaying component. That reminds me of things people do in Fourier analysis; something like frequencies in the left half plane and frequencies in the right half plane?

This is not my strength, but people who understand the Fourier picture should look at section 3 and see if it gives them any good ideas.

Posted by: David Speyer on August 14, 2009 5:37 PM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

I’ve been playing around a bit with the bent line.

This is the metric space consisting of two line segments of length L, joined at an angle of theta. Notice that inclusion-exclusion says that this should have magnitude L+1, regardless of the angle. I found that surprising, which is why I started playing.

At this point, I would be willing to bet against inclusion-exclusion, but only at very weak odds. In this chart, the angle ranges from 0 to Pi in steps of Pi/36. L is 10, and I used 101 sample points. Inclusion-exclusion predicts the value should be near 11. Increasing the number of sample points raises the value very slightly. For example, for Pi/2, going from 101 to 201 to 401 goes from 10.7306 to 10.7532 to 10.7589. My guess is that this is not approaching 11, but it is hard to be confident. Increasing L makes the discrepancy seem more dramatic for the same number of points. For Pi/2 and L=20, using the same numbers of points again, I get 20.5102, 20.6974, 20.7449

I have run some more experiments, which I will put in a separate comment.

Posted by: David Speyer on August 16, 2009 11:45 PM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

I looked at what the weighting function looks like in the case of the right angle.

As in the case of the straight line, the values at the endpoint approach 1/2.

On the interior of the line segment, the weighting seems to behave like f(x)/N for some continuous function f(x). (For the unbent line, f(x)=1/2. In this image, I have plotted the supposed function f for L=10 and theta=Pi/2. I used both 101 sample points and 201 (plotted in different colors); notice the close convergence.

There is a spike at the very center, which seems to be approaching 1/3. For L=10 and using 801 sample points, it is 0.333808. The values right next to the endpoints and the spike are much smaller:
0.0124992 and 0.00127575 respectively.

Other values of theta seem to have the same qualitative behavior: 1/2 at the endpoints, a spike in the middle, and g(theta,x)/N for all other values.

This value at the center point is interesting, and I don’t know what to make of it. Here it is for several different angles. My angle ranges
from 0 to Pi, in steps of Pi/36. The line segments each have length 10 and I use 101 points. If I conjecture that Pi/2 should give exactly 1/3, then this data probably has a bit less than 2 significant
digits, as I get 0.349805 numerically.

Posted by: David Speyer on August 17, 2009 12:10 AM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

Darn it, I had planned on just making this an afternoon diversion! Tomorrow I was supposed to be back at work, meeting my obligations to my coauthors. But this question of the bent line keeps growing on me.

I just realized that I didn’t run one very important experiment: I never generated the analogue of this figure for values of L other than 10. It is quite possible that, as L grows, that dip becomes narrower and narrower. I don’t have mathematica at home, so I’ll have to wait until tomorrow to check that – unless someone else does it first.

Posted by: David Speyer on August 17, 2009 1:32 AM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

David, yes it is rather addictive! I’ve done quite a bit of this kind of experimentation and I hope to get it written up by the end of the month – but I haven’t played with this specific example. I’m actually “on holiday” at the moment, which is why I haven’t responded to any of your fun posts. I’ve been doing calculations with around 20,000 points on a parallel array of computers in Sheffield, but I would guess that for a 1-dimension figure like the bent line you wouldn’t need so many points for a reasonably accurate answer.

I will reply more fully later in the week, but keep on building up your intuition…

Posted by: Simon Willerton on August 17, 2009 11:36 AM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

OK, I have now done the experiment. What it looks like is that the corner causes a certain local effect in the weights which doesn’t depend on how large a line segment we are embedded in.

What you are seeing here is the limiting weights for L=5 (blue) and L=10 (red and green). They are displayed on the same scale, which is why the blue plot is half as long. The green plot uses 41 sample points, the others use 81. The vertical axis is rescaled by the distance between the sample points. In other words, if we were approaching a limiting measure f(x) dx, I would be plotting dx.

The key observation is that they all seem to be approaching roughly the same function. This suggests to me that a local change in the metric space, like introducing a corner, creates a local change in the limiting weights.

In particular, I would expect the effect on the overall magnitude to be O(1), as compared to a limiting weight which was simply (1/2) dx on the line segment and (1/2)*delta on each end point. According to the inclusion-exclusion conjecture, the effect should approach 0. If that’s true, it will be quite a miracle!

Posted by: David Speyer on August 17, 2009 3:57 PM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

This is amazing stuff! Unfortunately I can’t help with the calculations: Simon’s the half of this partnership that can do that kind of thing. The furthest I’ve got is to figure out how to use gnuplot, which (in my hands at least) is pretty labour-intensive.

Posted by: Tom Leinster on August 17, 2009 3:00 AM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

There are a bunch of different polynomials showing up in this picture. Can someone remind me how they are all related?

Namely:

If A is a convex subset of Euclidean space, then Leinster and Willerton conjecture that |r A| is given by a polynomial in r; if A is polyconvex, they conjecture that |r A| is aymptopically given by said polynomial. This uses only the metric space structure on A.

In Federer’s article on sets of positive reach, he considers certain subsets of Euclidean space. He takes the tube formed by thickening his set by epsilon, and computes it volume as a polynomial in epsilon. This uses the embedding in n-space, but he also gives formulas in terms of intrinsic curvature, which only uses the internal structure of a Riemmannian manifold. I wasn’t able to follow enough of Federer’s writing to see how these two formulas are related.

Shanuel’s article on the length of a potato suggests he is doing the same thing as Federer, but he isn’t very precise.

Hadwiger proves that the space of valuations is n-dimensional, and the action of dilation on this space is diagonalizable. So, if we like, we can write the universal valuation of t*A as a polynomial in t.

Klain and Rota is checked out from the MIT library but, from what I can gather, they consider the measure of the set of k-planes intersecting t*A.

Each of these measures the sense of t*A in some sense, but the relations aren’t obvious. Can someone tie them together for me?

By the way, there are two other important notions: the Erhart polynomial and McMullen’s polytope algebra. I think these are related but different. All of the above concepts are invariant under rotation and translation. The polytope algebra is invariant under translation alone. The Erhart polynomial is invariant under translation and GL_n(Z) action, but not rotation. So I think that the polytope algebra is more general than the above ideas, and the Erhart polynomial is a different specialization of the polytope algebra idea.

Posted by: David Speyer on August 17, 2009 7:43 PM | Permalink | Reply to this

Reading suggestions?

Let me second that.

I too have tried to read Federer’s work without much success. I get the impression that it all goes back to Weyl’s 1939 work On the Volume of Tubes – here a tube is just a thickening of a submanifold – which involves integrals of polynomials in the curvature and which apparently was a forerunner to characteristic classes.

So does anyone know of any good reference for this kind of thing that is somewhat more readable than Federer and with a bit more detail than Schanuel?

Posted by: Simon Willerton on August 25, 2009 1:51 PM | Permalink | Reply to this

Re: Reading suggestions?

Tubes by Alfred Gray comes to mind.

Birkhäuser Basel; 2nd edition (January 22, 2004), ISBN-10: 3764369078 ISBN-13: 978-3764369071

Posted by: Eugene Lerman on August 25, 2009 4:27 PM | Permalink | Reply to this

Re: Reading suggestions?

Thanks, that had grabbed my eye, so I’ll definitely have a look. The other book that I’ve found is Generalized Curvatures by Jean-Marie Morvan. It looks similar to the book by Gray. Maybe I should have a look at that as well.

Posted by: Simon Willerton on August 25, 2009 6:23 PM | Permalink | Reply to this

Errors

Near the top of page 8, in the first line of the Proof, we have

Firstly, 0- and 1-point spaces have cardinality 0 and 1 respectively

but it should be

Firstly, 0- and 1-point spaces have magnitude 0 and 1 respectively

Posted by: Toby Bartels on August 18, 2009 1:57 AM | Permalink | Reply to this

Re: Errors

Thanks, Toby!

Posted by: Tom Leinster on August 19, 2009 4:00 PM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

Darn, I missed the “debut day” of this post! Thanks for the acknowledgement, it was indeed a “cunning piece of Google” which enabled me to find a reference which proved the calculation Simon had heuristically guessed. I swear by gazillions of tabs for web browsing, and colourful tabs dear reader, colourful tabs! Now to sit back and read the paper. Nothing like some asymptotics to quell the soul.

Posted by: Bruce Bartlett on August 18, 2009 11:23 AM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

Simon and I have been corresponding a great deal offline. Here’s something I’m particularly happy about finding: there are metric spaces for which asymptotic inclusion-exclusion does not hold.

Here is the counterexample. Take the interval [L,L][-L, L] and impose the following metric: if x and y are on the same side of 0, then d(x,y)=|xy|d(x,y) = |x-y|. If they are on opposite sides, then d(x,y)=max(|x|,|y|)d(x,y) = \max(|x|, |y|). I like to think of this as the bent line in the sup metric. Since this is glued from two ordinary line segments of length LL, the inclusion-exclusion conjecture predicts that it should have magnitude L+1L+1. In fact, it has magnitude L+1log(3/2)+O(e L)L+1-\log (3/2) + O(e^{-L}).

I should say a little more carefully what I proved. On any metric space MM, define a weighting to be a measure μ\mu such that xMe d(x,y)μ(x)\int_{x \in M} e^{-d(x,y)} \mu(x) is 11 for all yMy \in M. As in the finite case, weightings may not exist and may not be unique but, if a weighting exists, then μ\int \mu is a well defined number. I take this to be the definition of magnitude. I very strongly believe, but have not proved, that this is equivalent to Simon and Tom’s definition. (They use this definition for finite metric spaces, and deal with infinite metric spaces as limits of finite ones.)

What I was able to do is to compute an explicit weighting for the bent line in the sup metric. See this note for details. This weighting bends down near 00, and also has a positive atomic component at 00. Computer experiments show that the bent line in the Euclidean plane has similar features. However, we don’t have any explicit formula in that case, so we can’t compute the magnitude.

Posted by: David Speyer on August 30, 2009 1:48 AM | Permalink | Reply to this

Re: Asymptotics of the Magnitude of Metric Spaces

See this note for details.

I corrected the link above.

Posted by: Toby Bartels on August 30, 2009 7:35 AM | Permalink | Reply to this
Read the post More Magnitude of Metric Spaces and Problems with Penguins
Weblog: The n-Category Café
Excerpt: Learn about the tenuous link between emperor penguins and the magnitude of metric spaces.
Tracked: October 11, 2009 11:08 PM
Read the post The 1000th Post on the n-Category Café
Weblog: The n-Category Café
Excerpt: Meet our new hosts: Alex Hoffnung, Tom Leinster, Mike Shulman and Simon Willerton!
Tracked: November 13, 2009 3:27 AM
Read the post The 1000th Post on the n-Category Cafe
Weblog: The n-Category Café
Excerpt: Meet our new hosts: Alex Hoffnung, Tom Leinster, Mike Shulman and Simon Willerton!
Tracked: November 13, 2009 3:39 AM
Read the post Magnitude of Metric Spaces: A Roundup
Weblog: The n-Category Café
Excerpt: Resources on magnitude of metric spaces.
Tracked: January 12, 2011 1:20 PM

Post a New Comment