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 30, 2014

Weightings for Compact Metric Spaces

Posted by Tom Leinster

Guest post by Mark Meckes

A recent paper of Mark’s proved the very substantial result that Minkowski dimension (one of the most important types of fractal dimension) can be derived from magnitude (an invariant ultimately coming from category theory). More exactly, he showed that the Minkowski dimension of a compact subset of n\mathbb{R}^n is exactly equal to its “magnitude dimension” (Cor 7.4). Here, Mark explains not this specific result, but the overall framework that makes such theorems possible. —TL

I’d like to report on some recentish progress in understanding the magnitude of compact metric spaces. To set the stage I’ll recap some background, which will repeat a number of things which have already appeared in posts by Tom and Simon. For those who want to be reminded of more, Tom has provided a reading list.

Background, part I: finite spaces

The magnitude of a finite metric space (A,d)(A, d) is defined as follows. First, define the matrix ζ A=[e d(a,b)] a,bA A×A\zeta_A = \bigl[e^{-d(a,b)} \bigr]_{a,b \in A} \in \mathbb{R}^{A \times A}. A weighting for AA is a vector w Aw \in \mathbb{R}^A such that for each aAa \in A,

(1)(ζ Aw) a= bAe d(a,b)w b=1. (\zeta_A w)_a = \sum_{b\in A} e^{-d(a,b)} w_b = 1.

If ww is a weighting for AA, then the magnitude of AA is defined to be

(2)|A|= aAw a. | A | = \sum_{a \in A} w_a.

In general, there are well-definedness issues with this definition as written. For the purposes of this post I’ll brush them aside by noting that if ζ A\zeta_A happens to be a positive definite matrix, and hence invertible, then AA possesses a unique weighting. When this is the case, we call AA a positive definite metric space, or PDMS. For example, it turns out that all finite subsets of n\mathbb{R}^n (with the usual Euclidean metric) are positive definite metric spaces. PDMSs have the additional nice properties that their magnitude is always at least 1 (if they’re nonempty), and that magnitude is increasing with respect to inclusion.

Background, part II: compact spaces

Given an invariant of finite metric spaces, it’s natural to try to extend it to some class of infinite spaces, say compact spaces. There are two obvious general approaches: approximate a given compact space by finite spaces, or adapt the definition to apply to infinite spaces directly.

Let’s first consider approximation. We’d like to say that if AA is a given compact metric space, we can find a sequence of finite spaces A kA_k which approximate AA in some sense and whose magnitudes |A k|| A_k | converge to some limit, which we could then take as the definition of |A|| A \vert. There are well-definedness issues here, in particular whether different approximating sequences would give different values of |A|| A |. The usual way to handle such an issue, if you can, is by appealing to continuity: if magnitude were a continuous function of a finite metric space (with respect to an appropriate topology), then we could define magnitude on the family of compact spaces as its unique continuous extension.

Fortunately, there is a natural topology on the family of isometry classes of compact metric spaces. Unfortunately, magnitude is not a continuous function of a finite metric space. However, if we restrict to finite PDMSs, it turns out that magnitude is lower semicontinuous, or lsc for short. Like a continuous function, an lsc function has a canonical extension from a domain to its closure—not a unique lsc extension, but a minimal maximal one. So we can naturally define the magnitude of compact PDMSs (a compact space is a PDMS if each of its finite subspaces is) as the minimal lsc extension of the magnitude of finite PDMSs.

Concretely, this means that |A|| A | is well-defined as the limit of |A k|| A_k |, whenever A kA_k is a sequence of finite PDMSs which approximate AA and for which |A k|| A_k | is increasing. Since magnitude is increasing with respect to inclusion for finite PDMSs, the last condition can be guaranteed by taking an increasing sequence A kA_k. (Notice that this minimal lsc extension of magnitude a priori takes values in [1,][1, \infty]. I don’t know whether every compact PDMS has finite magnitude. Tom proved that every compact subset of n\mathbb{R}^n has finite magnitude.)

Using roughly this approach (although before the semicontinuity result was proved), Tom and Simon showed, among other things, that the magnitude of an interval of length \ell is 1+/21 + \ell/2. So it became clear that magnitude knows something about classical geometric invariants.

The approximation approach leads to some nice concrete results, and is justified by semicontinuity. But it’s rather unsatisfactory in at least two ways. On the one hand, it would simply be nicer from an aesthetic point of view to give a direct definition of the magnitude of a compact space, which extends the original definition; it might also shed new light on the original definition. On the other hand, such a direct definition would involve some notion of weighting for a compact space, which would provide a new tool for analyzing magnitude.

Later, Simon gave a definition of magnitude for certain compact spaces which extends the original definition. Given a compact metric space (A,d)(A, d), a weight measure for AA is a measure μ\mu such that for each aAa \in A,

(3) Ae d(a,b)dμ(b)=1. \int_A e^{-d(a,b)} d\mu(b) = 1.

If μ\mu is a weight measure for AA, then we define

(4)|A|=μ(A). | A | = \mu(A).

It turns out that this approach agrees with the approximation approach. That is, if AA is a compact PDMS and has a weight measure, then this definition of |A|| A | agrees with the earlier one. On the other hand, the domains of definition are different: not every compact PDMS has a weight measure, and many spaces which are not positive definite do possess weight measures.

Using this definition, Simon studied magnitudes of homogeneous Riemannian manifolds. Again, he found that magnitude knows about classical geometric invariants. However, the fact that many (probably most, in some sense) spaces don’t have weight measures makes the measure-based definition of magnitude unsatisfactory as well.

Weightings for compact PDMSs

More recently, I found a definition of magnitude for a compact PDMS which directly extends the original definition for a finite space. To begin with, we take inspiration from Simon’s definition and think of the weighting ww of a finite space as the measure (more precisely, as a signed measure, since its components need not be positive)

(5) aAw aδ a, \sum_{a \in A} w_a \delta_a,

where δ a\delta_a is a point mass at aa. We next take inspiration from the finite approximation definition and say that the weighting of a compact space AA should be a limit of weightings of finite spaces. That is, it should be a limit of some sequence of finitely supported signed measures on AA. To make sense of this, we need to put some topology on the space FM(A)F M(A) of finitely supported signed measures. Since it’s a vector space, we’d probably like to make it a topological vector space. The nicest topological vector spaces are inner product spaces, so it makes sense to try to find an inner product on FM(A)F M(A) which will work nicely with magnitude.

If AA is a PDMS, then such an inner product is staring us in the face (although it took many months before I noticed that): if BAB \subseteq A is finite, then

(6) aBv aδ a, bBw bδ b 𝒲:= a,bBv ae d(a,b)w b. \Bigl\langle \sum_{a \in B} v_a \delta_a, \sum_{b \in B} w_b \delta_b \Bigr\rangle_{\mathcal{W}} := \sum_{a, b \in B} v_a e^{-d(a,b)} w_b.

Define 𝒲 A\mathcal{W}_A to be the Hilbert space completion of FM(A)F M(A) with this inner product. A weighting for AA will be an element of 𝒲 A\mathcal{W}_A which satisfies an appropriate analogue of the original condition ζ Aw=1\zeta_A w = 1.

When v= bBv bδ bFM(A)v = \sum_{b \in B} v_b \delta_b \in F M(A), for some finite BAB \subseteq A, we can straightforwardly define the function

(7)Zv(a)= bAe d(a,b)v b Z v(a) = \sum_{b \in A} e^{-d(a,b)} v_b

for aAa \in A. It’s not hard to show that ZvZ v is a bounded continuous function, and that Zv v 𝒲\| Z v \|_\infty \le \| v \|_{\mathcal{W}}, so the linear map Z:FM(A)C(A)Z:F M(A) \to C(A) has a unique continuous linear extension Z:𝒲 AC(A)Z:\mathcal{W}_A \to C(A). We can now define a weighting of AA to be a w𝒲 Aw \in \mathcal{W}_A such that Zw(a)=1Z w(a) = 1 for each aAa \in A.

The map ZZ is injective, so AA has at most one weighting. Moreover, AA has a weighting if and only if there is a uniform bound on the magnitudes of its finite subsets. In other words, AA possesses a weighting iff the magnitude |A|| A |, as defined by finite approximations, is finite. (This also means that I don’t know whether every compact PDMS has a weighting, but I do know that every compact subset of n\mathbb{R}^n does.)

Now that we know what a weighting for AA is, we’re ready to define the magnitude of AA. This is slightly less straightforward, since if w𝒲 Aw \in \mathcal{W}_A is not in FM(A)F M(A), then there is no meaning to w aw_a. To get around this, we notice that the original definition for a finite space can be rewritten as

(8)|A|= aAw a1= aAw a bAe d(a,b)w b= a,bAw ae d(a,b)w b, | A | = \sum_{a \in A} w_a \cdot 1 = \sum_{a \in A} w_a \sum_{b \in A} e^{-d(a,b)} w_b = \sum_{a,b \in A} w_a e^{-d(a,b)} w_b,

and the latter sum fits right into our Hilbert space framework. So, if AA is a compact PDMS with weighting w𝒲 Aw \in \mathcal{W}_A, then we define the magnitude of AA to be

(9)|A|=w,w 𝒲=w 𝒲 2. | A | = \langle w, w \rangle_{\mathcal{W}} = \| w \|_{\mathcal{W}}^2.

This fits with all the previous definitions: if AA is a finite PDMS, this simply repeats the original definition in a more complicated way; if AA is a compact PDMS, this gives the same value of magnitude as finite approximation; and if AA is a compact PDMS with a weight measure μ\mu, then μ\mu is a weighting for AA and μ(A)=μ 𝒲 2\mu(A) = \| \mu \|_{\mathcal{W}}^2.

So what does this give us that we didn’t have before? As hoped for, it’s a definition which works for a broad class of spaces, and is (to me, at least) more elegant than approximation by finite spaces. It may shed a little bit of light on the original definition of magnitude for finite spaces—it suggests that one should think of the magnitude not, as originally written, as the sum of the entries of the weighting ww, but as the double sum

(10) a,bAw ae d(a,b)w b. \sum_{a,b \in A} w_a e^{-d(a,b)} w_b.

In other words, it suggests that the matrix ζ A\zeta_A should be thought of, not as defining a linear map, but as defining a bilinear form. (The same vague, speculative remark applies more generally to the definition of the magnitude of an enriched category.)

What about the hope that the weighting ww of AA would turn out to be a useful tool? Before addressing that, let’s first specialize to subsets of n\mathbb{R}^n.

Weightings and magnitude in Euclidean space

If A nA \subseteq \mathbb{R}^n, then the linear operator ZZ is a convolution operator, which suggests using a bunch of Fourier mumbo-jumbo. If you do that, it turns out that 𝒲 A\mathcal{W}_A is a subspace of the Sobolev space (or more properly, Bessel potential space) H (n+1)/2H^{-(n+1)/2}, and the norm is, up to a constant depending on nn, the standard Sobolev norm on H (n+1)/2H^{-(n+1)/2}. This isn’t the most familiar, classical sort of thing—it’s a Sobolev space, but with a negative, fractional (half the time) exponent—but it is a known and well-understood thing. Its elements are distributions, not functions, but a lot of machinery exists to work with such things.

Even better, ZZ maps 𝒲 A\mathcal{W}_A into the Sobolev space H (n+1)/2H^{(n+1)/2}. This is a Sobolev space whose elements are functions. (Real, honest, continuous functions—not even almost-every-equal equivalence classes!) If ww is the weighting of AA, then h=ZwH (n+1)/2h = Z w \in H^{(n+1)/2} is, by definition, the unique function in Z(𝒲 A)Z(\mathcal{W}_A) such that h(a)=1h(a) = 1 for all aAa \in A. It’s not hard to show that |A|=c nh H (n+1)/2 2| A | = c_n \| h \|^2_{H^{(n+1)/2}}, for an explicit dimensional constant c nc_n. With a bit more work, one can show that

(11)|A|=inf{c nf H (n+1)/2 2:fH (n+1)/2,f1onA}, | A | = \inf \left\{c_n \| f \|_{H^{(n+1)/2}}^2 \,:\, f \in H^{(n+1)/2},\,\, f \equiv 1 \, on \, A \right\},

and the infimum is uniquely achieved when f=hf = h.

This reformulation of magnitude in terms of a variational problem for functions turns out to be extremely useful. It opens the door to using tools from Hilbert space geometry, Fourier analysis, potential theory, and PDEs to study magnitude. But this post has gotten to be rather long, so I’ll leave it to you to read the paper (and hopefully future papers and posts) to see how!

Posted at January 30, 2014 4:45 PM UTC

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

17 Comments & 0 Trackbacks

Re: Weightings for Compact Metric Spaces

Coincidentally, I’ve just been learning about the conjecture that every Kakeya set in n\mathbb{R}^n has Minkowski dimension nn. We now have another line of attack on this… not that I’m getting my hopes up :-)

Posted by: Tom Leinster on January 30, 2014 8:08 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

Yes, I’ve thought about this a little. I haven’t made any progress myself so far, but I’m not an expert on Kakeya sets.

Posted by: Mark Meckes on January 30, 2014 9:01 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

Mark, remember when I read an early draft of your paper I made some comment about feeling a bit lost in the analysis because I wasn’t really in the intended audience of analysts? Well, I certainly felt like I was squarely in the right audience for this post! I look forward to a post on the Minkowski dimension.

Posted by: Simon Willerton on January 31, 2014 11:35 AM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

Good, then I aimed well! I don’t know whether I’ll find the time to write a post about the Minkowski dimension result, but I’ll keep the request in mind.

Posted by: Mark Meckes on January 31, 2014 2:33 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

Here’s a question. How did we not think of taking the Hilbert space completion of the space of finitely supported measures much earlier?

My impression is that we floundered around for a long while, looking for a suitable space of measure-like things in which weightings should live, trying out lots of possibilities motivated in different ways. Some we rejected, others we kept as “maybes”. Then, after perhaps a couple of years, you discovered that this rather simple construction was the right one.

I’d like to learn a lesson from this, if possible. With hindsight, was there an alternative to simple trial and error? Could we have done better?

Posted by: Tom Leinster on January 31, 2014 12:16 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

I’d say your impression is completely accurate.

I think part of the problem was trying to extend the original definition to arbitrary compact spaces, maybe with the idea in the back of our minds that something might go wrong at some point for non-PDMSs. So we were thinking about spaces of measure-like things which could be defined for an arbitrary space AA. For a long time, I, at least, didn’t consider that we could make crucial use of positive definiteness from the very beginning of the construction.

(It may well be that the construction can be made to work more generally, using the not-necessarily-positive-definite bilinear form defined by (6). But I don’t know anything about spaces built around indefinite bilinear forms. If anyone here does, please let me know!)

One narrow lesson to draw from this is that, if you have a positive definite matrix lying around, it doesn’t really want to be used as a linear map—it wants to be used as an inner product!

Posted by: Mark Meckes on January 31, 2014 2:29 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

One narrow lesson to draw from this is that, if you have a positive definite matrix lying around, it doesn’t really want to be used as a linear map—it wants to be used as an inner product!

As a wise man once said…

Posted by: Tom Leinster on January 31, 2014 4:14 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

But I don’t know anything about spaces built around indefinite bilinear forms.

Yes, you do! L pL^p “function” spaces are traditionally built on indefinite norms, as the quotient by the norm-zero subspace of the suitably-summable measurable functions. While I usually prefer the completion-of-compact-supported-continuous functions, this notably doesn’t capture L L^\infty space because of that delightful feature that uniform limits of continuous functions are continuous.

Posted by: Jesse C. McKeown on January 31, 2014 9:11 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

That’s not the kind of situation I’m talking about. There’s an unfortunate ambiguity in the terminology here. (I think this came up a while ago in another comment thread here.) What I mean by “indefinite” in this case isn’t just that the quadratic form v,v 𝒲\langle v, v \rangle_{\mathcal{W}} may be 00 for nonzero vv, but that it takes on both positive and negative values. This is what happens in general for AL pA \subseteq L^p when p>2p > 2. (Notice that L pL^p is being used here just as an ambient metric space, and this issue is completely unrelated to exactly how one defines L pL^p.)

Posted by: Mark Meckes on February 1, 2014 9:24 AM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

Oh, I beg your pardon.

Posted by: Jesse C. McKeown on February 1, 2014 7:36 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

Another reason it took a long time before I thought of anything like this approach is that my background is in the geometry of Banach spaces. (Not in the sense that I’ve ever actually worked precisely on the geometry of Banach spaces, but it’s the mathematical culture I grew up in.) To many mathematicians—including most analysts, I think—it feels like rather a nuisance that most norms don’t come from inner products, and consequently they like to work with Hilbert spaces whenever it’s feasible. But when Banach spaces themselves are the main objects of study, Hilbert spaces appear instead as the least interesting examples of the theory. So coming from that warped perspective, it simply didn’t occur to me for a long time to look for a nice inner product, as opposed to a norm with more uniformy behavior.

I wrote above “The nicest topological vector spaces are inner product spaces, so it makes sense to try to find an inner product on FM(A)FM(A) which will work nicely with magnitude,” precisely because that’s a lesson I, personally, need to internalize. More generally, it’s worth keeping in mind that when you need an xx to do a job for you, you should try to find the simplest possible sort of xx, and not the scary sorts of things that xx theorists spend their time studying.

Posted by: Mark Meckes on February 4, 2014 3:37 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

The nicest topological vector spaces are inner product spaces

Blasphemy! Everyone knows free Banach spaces are the best ones :D

Posted by: Yemon Choi on February 4, 2014 10:34 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

As a functional analyst, Yemon, your opinion on the matter carries no weight!

Posted by: Mark Meckes on February 5, 2014 7:31 AM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

“when you need an xx to do a job for you, you should try to find the simplest possible sort of xx, and not the scary sorts of things that xx theorists spend their time studying.”

This is a valuable lesson in all areas of math. Relatedly, if you love the simplest kinds of x, don’t become an x theorist! Figure out which fields need x’s, and supply them. I know a lot of people who loved classical number theory, representation theory or algebraic geometry, and found that their best role in current research was explaining the nicest parts of these fields to cryptographers, combinatorialists or knot theorists.

Posted by: David Speyer on March 14, 2014 8:01 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

I forgot to say that there’s a typo in (7). Two of the aas should be bbs, I think.

Posted by: Simon Willerton on January 31, 2014 5:12 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

You can’t hide from me, Simon. With my superpowers, I can see that your comment initially said “there’s a type”, not “there’s a typo”. Then you corrected it, using your own superpowers. Muphry’s Law strikes again.

Also: fixed. Thanks.

Posted by: Tom Leinster on January 31, 2014 5:18 PM | Permalink | Reply to this

Re: Weightings for Compact Metric Spaces

Like a continuous function, an lsc function has a canonical extension from a domain to its closure—not a unique lsc extension, but a minimal one.

Whoops, as someone recently pointed out to me, I misspelled “maximal” as “minimal” there.

Seriously, if anyone knows a way to write about semicontinuity without ever making mistakes like that, I’d love to learn it. (I even know famous papers by famous authors making that sort of mistake.)

Posted by: Mark Meckes on March 12, 2014 8:37 AM | Permalink | Reply to this

Post a New Comment