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.

September 5, 2012

The Spread of a Metric Space

Posted by Simon Willerton

Given a finite metric space XX we can define the spread E 0(X)E_0(X) by

E 0(X) x1 ye d(x,y).E_0(X)\coloneqq \sum_x \frac{1}{\sum_{y} e^{-d(x,y)}}.

This turns out to be a nice measure of the ‘size’ of the metric space. I’ve just finished a paper on this:

In this post I’ll give a quick overview of the paper, mentioning connections to biodiversity; magnitude; volume and total scalar curvature; and Hausdorff dimension.

A few of these ideas are looked at in a slightly more dynamic way in my recent talk at the CRM Exploratory programme on the mathematics of biodiversity: Magnitude and other measures of metric spaces.

I should say that Tom Leinster convinced me to switch to using the word ‘spread’ as prior to that I had been using the much more uncouth word ‘bigness’.

The following five snapshots of the spread are more-or-less independent of each other.

Diversity

The definition of spread was motivated by Tom Leinster and Christina Cobbold’s definition of diversity measures for ecosystems in which they take into account the relative abundances of the species and the relatedness of each pair of species, or in math-speak, we can use these to assign a number to each finite metric space with a probability measure on it – the points represent the species, the metric describes the relatedness and the probability measure describes the relative abundances.

Tom and Christina give us a diversity measure for each number qq with 0q0\le q \le\infty, so for a finite metric space we can use the uniform probabiltiy measure on it and take the diversity measure for q=0q=0: that is precisely the spread.

The more classical version of the Tom and Christina’s measures – the Hill numbers – only takes into account relative abundances of species and not the relatedness of species, so these are defined for probability spaces with no metric on them (or with the discrete metric on them, if you prefer). In that case, the q=0q=0 diversity measure is just the number of species present. So from that point of view, the spread can be seen as an analogue of the number of species in an ecosystem.

Basic behaviour

If XX is a finite metric space with NN points, t>0t \gt 0 and tXt X denotes XX with the metric scaled by a factor of tt then we get the following basic properties of the spread.

  • 1E 0(X)N1\le E_0(X)\le N;
  • E 0(tX)E_0(t X) is increasing in tt;
  • E 0(tX)1E_0(t X)\to 1 as t0t\to 0;
  • E 0(tX)NE_0(t X)\to N as tt\to \infty;
  • E 0(X)e diam(X)E_0(X)\le e^{diam(X)}.

For instance, if tRt R is the following three-point metric space

3 point space

then we get the following plot of the spread as we scale tt.

spread profile

So when the space is scaled very small it looks like there is one point, at medium scales it looks like there are two points, and at large scales all three points are distinctly visible.

Magnitude

Long-time readers of this blog will not be surprised to hear that spread is connected to Tom Leinster’s notion of magnitude (called cardinality in some early blog posts). The magnitude |X||X| of a metric space XX is not always defined; for instance, Tom showed that there is no magnitude defined for a certain scaling of the five-point metric space coming from the complete bipartite graph K 3,2K_{3,2}. If we plot the magnitude of the scalings of this space together with the spread of these scalings then we see that the spread is rather more nicely behaved!

spread profile

Tom Leinster said he thinks this shows that the spread is more suave than the magnitude.

For well-behaved metric spaces the magnitude is an upper bound for the spread – in this case ‘well behaved’ means ‘positive definite’ and such spaces include subspaces of Euclidean space. For homogeneous metric spaces the magnitude and the spread actually coincide.

Dimension

As we have a notion of size, we can associate a notion of dimension.

  • If we scale a line by a factor of tt then its length (its size) scales by a factor of t 1t^1.

  • If we scale a rectangle by a factor of tt then its area (its size) scales by a factor of t 2t^2.

  • If we scale a cuboid by a factor of tt then its volume (its size) scales by a factor of t 3t^3.

Of course, the 11, 22 and 33 appearing there are our usual concept of dimension of those three spaces. So given a notion of size of metric spaces, the associated dimension of a metric space is the growth rate of the size. One has to be precise about what growth rate is here, but you can think of it as the (instantaneous) slope of the log-log plot of size versus scale.

In particular, the spread dimension dim 0(X)dim_0(X) of a metric space XX is defined by

dim 0(X)dlog(E 0(tX))dlog(t)| t=1=tE 0(tX)dE 0(tX)dt| t=1.dim_0(X)\,\coloneqq\, \left.\frac{\mathrm{d} \,log(E_0(t X))}{\mathrm{d} \,log(t)}\right|_{t=1} \, =\, \left.\frac{t}{E_0(t X)}\frac{\mathrm{d}E_0(tX)}{\mathrm{d}t}\right|_{t=1}.

This notion of spread dimension is scale dependent, but that is not unreasonable. Think of a very long and very thin rectangle. If it is scaled very, very small you might think it looks like a point, so is zero-dimensional. As it is scaled up you start to notice its length but not its width, so it seems one-dimensional. As it is scaled even more it finally looks two-dimensional. If this rectangle is actually made from, say, atoms, then if it scaled even more then you start to see the individual points and it begins to look zero-dimensional again.

We can numerically calculate the spread dimension for a rectangle of 1010 by 49004900 points at various scales, and the above describes exactly the kind of phenomena that we see.

dimension profile

If my computer could handle much bigger matrices then I could calculate the dimension profile for say 10001000 by 100000000100000000 points and see a much more pronounced step-like behaviour from zero to one to two to zero dimensions.

We don’t have to stick to boring old shapes like rectangles. We can try fractals! We can take a finite metric space with lots of points which approximates say the Koch curve, get maple to calculate the spread dimension at various scales and plot the result. At medium scales the spread dimension is shockingly close to the Hausdorff dimension of the Koch curve, namely ln4/ln3ln 4/ ln 3. So when it’s not too small and it’s not too large, then the finite approximation looks ‘Koch-like’.

dimension profile

The same phenomemon is seem for finite approximations to Cantor sets and Sierpinski triangles, so there seems to be some geometric content to the spread dimension.

Non-finite metric spaces

There is an obvious way to generalize the notion of spread to a non-finite metric space XX provided that the metric space comes equipped with a canonical measure μ\mu such that the total measure of the space is finite. In that case we just define the spread as follows.

E 0(X) xXdμ(x) yXe d(x,y)dμ(y).E_0(X)\coloneqq\int_{x\in X} \frac{\mathrm{d}\mu(x)}{\int_{y\in X} e^{-d(x,y)} \,\mathrm{d}\mu(y)}.

From that one can calculate the spread of a length \ell straight line segment and of an nn-sphere with radius RR. As it’s getting late, I won’t put the details here, but let the interested reader find out the answers by looking in the paper.

One class of metric spaces with a canonical measure is the class compact Riemannian manifolds. For this class of spaces it is possible to calculate the leading order terms in the asymptotic behaviour of the spread as a space MM is scaled up. These leading order terms depends just on the volume vol(M)vol(M) and the total scalar curvature tsc(M)tsc(M), in particular we have the following.

E 0(tM)=1n!ω n(t nvol(M)+n+16t n2tsc(M)+O(t n4))as t,E_0(t M) = \frac{1}{n!\,\omega_n}\left(t^n vol(M) + \frac{n+1}{6}t^{n-2} tsc(M) +O(t^{n-4})\right) \quad \text{as }\quad t\to\infty,

where ω n\omega_n is the volume of the unit nn-ball.

In particular, for a Riemannian surface Σ\Sigma we have:

E 0(tΣ)=area(Σ)2πt 2+χ(Σ)+O(t 2)as t,E_0(t\Sigma)=\frac{area(\Sigma)}{2\pi}t^2+\chi(\Sigma)+O(t^{-2})\quad \text{as } \quad t\to\infty,

where χ\chi is the Euler characteristic.

Final comments

In conclusion, it seems that this easy to write down measure of size of a metric space has many interesting properties.

Posted at September 5, 2012 5:09 PM UTC

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

20 Comments & 1 Trackback

Re: The Spread of a Metric Space

This looks quite neat. I gather from your graphs and examples that the spread has an “intrinsic length scale” of about 1 — in the sense that it considers distinct points to “cohere together” roughly when they are less than distance 1 apart. Is that a correct intuition? Is it possible to write down variants of the spread for which this intrinsic scale is some other number?

Posted by: Mike Shulman on September 5, 2012 10:02 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

There does seem to be a natural length at that kind of scale you mention. I tend think of the units as being centimeters with the metric space being held in my hands, that seems to give a reasonable intuition, but I’ve not got anything much stronger than that to say.

If you change the ee in the definition to another positive constant aa, then natural scale should go from around 11 to around 1/ln(a)1/ln(a).

Posted by: Simon Willerton on September 5, 2012 10:50 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Hooray!

Posted by: Tom Leinster on September 6, 2012 1:58 AM | Permalink | Reply to this

Re: The Spread of a Metric Space

I should say that Tom Leinster convinced me to switch to using the word ‘spread’ as prior to that I had been using the much more uncouth word ‘bigness’.

Part of me is really sad that you switched. Would’ve loved ‘bigness’.

Posted by: Todd Trimble on September 6, 2012 6:51 AM | Permalink | Reply to this

Re: The Spread of a Metric Space

‘Bigness’ is a nice word, but I like ‘spread’ better here. This is partly for the boring, pedantic reason that ‘bigness’ sounds too general for any one quantity — why should this be called ‘bigness’ instead of any other quantity? But it’s also because I think what E 0E_0 measures really is how ‘spread out’ the μ\mu-mass of XX is.

Posted by: Mark Meckes on September 6, 2012 3:43 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Figure 3 on page 7 suggests why spread might not be a bad name. The two spaces shown there have the same magnitude, simply because they’re trees with the same number of vertices. (That’s Theorem 4.) But the spread of the spread-out one is greater than that of the clustered-up one.

Posted by: Tom Leinster on September 6, 2012 4:16 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

A minor terminological note: in recent years, “metric measure space” has become a standard term for a metric space equipped with a canonical finite measure.

Posted by: Mark Meckes on September 6, 2012 3:49 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Thanks Mark. Talking of terminological things, Tom said that you’d found the ‘maximum diversity’ in the literature under a somewhat different name. What was it called?

Posted by: Simon Willerton on September 6, 2012 9:31 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Get ready for a mouthful. For a subset AA of NN-dimensional Euclidean space, up to a factor of N!N! times the volume of the unit ball, the maximum diversity of AA is the same as the “Bessel capacity of AA of order (N+1)/2(N+1)/2 and index 22”. Or is that index (N+1)/2(N+1)/2 and order 22? In any case, it’s sometimes denoted B (N+1)/2,2(A)B_{(N+1)/2,2}(A). As far as I can tell, it’s not very well-studied as such —- the main interest seems to be on capacities B α,pB_{\alpha, p} for which αpN\alpha p \le N. When αp\alpha p is bigger than NN, the capacity has some behaviors which seem to be pathological from the point of view of the usual applications of capacities.

Posted by: Mark Meckes on September 7, 2012 1:16 AM | Permalink | Reply to this
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:55 PM

Re: The Spread of a Metric Space

Hi,

The idea of defining dimension via a notion of ‘size’ of a metric space is very interesting.

I tried to calculate the spread dimension of a linear tree graph defined at the end of section 4.1 of your paper: dim 0=1E 0(1)dE 0(1)dtdim_0 = \frac{1}{E_0(1)} \frac{dE_0(1)}{dt}.

Intuitively, I would expect the dimension to be 1, but I am finding dim 0dim_0 seems to asymptote around 0.851 (I calculated up to 10 610^6 points using the definition of E 0E_0 for a linear tree graph graph via the summation in your paper and the equation above). Is there a reason that a tree graph would not have a dimensionality of 1 (even after 10 610^6 points)?

Posted by: Bob on July 16, 2015 7:56 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Hi Bob, you don’t say what metric you’ve put on the linear tree graph. The dimension is very much scale dependent. A very long line interval should have dimension close to one, but a very short line should have dimension close to zero: intermediate length lines should have intermediate dimensions. What length was your linear graph?

Posted by: Simon Willerton on July 22, 2015 9:22 AM | Permalink | Reply to this

Re: The Spread of a Metric Space

Hi Simon, Thanks for the reply.

I agree that long intervals should approach dim = 1, and short intervals should approach dim = 0.

I calculated dim0_0 for up to 10 610^6 points in mathematica using the summation formula from section 2: E 0= j=1 j=Ne t11+e te t(j1)e t(Nj)E_0=\sum_{j=1}^{j=N} \frac{e^t-1}{1+e^t-e^{-t(j-1)}-e^{-t(N-j)}} and the equation for dim0_0 in my post above. This is a plot for the dimension dim0_0 vs number of points in my linear tree. file:///Users/Bob/Desktop/dim%20E0%20line.jpg Best, Bob

Posted by: Bob on July 25, 2015 6:28 AM | Permalink | Reply to this

Re: The Spread of a Metric Space

Hi Simon, I’m not sure why the image is not loading. I can’t see any of the svg image edit options on the preview screen. I’ll email the plot of dimension vs points on a linear tree. Basically it starts at 0, grows, but than asymptotes around 0.85.

[Edit by Simon: Here is the plot]

graph

Posted by: Bob on July 25, 2015 6:50 AM | Permalink | Reply to this

Re: The Spread of a Metric Space

Hi Bob,

Ah. You’re doing something completely different to what I thought you were doing, and it’s something that I’d not thought about. You’re calculating the dimension of a large interval in the integers, ie. [1,N][1,N]\cap \mathbb{N}, with the obvious metric, so nn is distance dd from n+dn+d. For large NN this looks kind of linear, so it goes off in both directions (if you’re looking at a typical point), but it’s very definitely discrete as there’s a very visible distance between the points. This means that the dimension is neither zero nor one, but somewhere between.

If we make the gap between the points smaller then the dimension gets closer to one. So with 8192 points and 0.1 units between adjacent points we get an approximate dimension of 0.99664085486.

It took me a while to code this up as I’m trying to wean myself off Maple and onto Sage. If anyone is interested in playing with the very basic code it’s available on SageMathCloud:

Big linear graph spread dimension.sagews

It would be interesting to see exactly what the limiting behaviour is, but at the moment it looks like you could argue that “The spread-dimension of the integers is about 0.850.85.”

Posted by: Simon Willerton on July 30, 2015 5:34 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Hi Simon,

I agree that it makes sense that you want to points to lie close together so that the figure approximates a line. The way I read your paper, the equation just before section 4.2 reads “dim 0(X):=tE 0(tX)dE 0(tX)dtdim_0(X) := \frac{t}{E_0(tX)}\frac{dE_0(tX)}{dt} evaluated at t=1t=1”. Am I reading this wrong? If not, why are you allowed to use t=0.1t=0.1?

Best, bob

Posted by: Bob on July 31, 2015 4:29 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

The formula gives the dimension for a metric space XX. If we scale the metric by a factor of τ\tau to get the metric space τX\tau X, we can calculate its dimension with an application of the chain rule:

dim 0(τX) tE 0(t(τX))dE 0(t(τX))dt| t=1 =tE 0((tτ)X))dE 0((tτ)X)dt| t=1 =tE 0(tX)dE 0(tX)dt| t=τ. \begin{aligned} dim_0(\tau X) &\coloneqq \frac{t}{E_0(t(\tau X))}\frac{d E_0(t(\tau X))}{d t}\biggr |_{t=1}\\ &=\frac{t}{E_0((t\tau) X))}\frac{d E_0((t\tau) X)}{d t}\biggr |_{t=1}\\ &= \frac{t}{E_0(t X)}\frac{d E_0(t X)}{d t}\biggr |_{t=\tau}. \end{aligned}

So putting t=0.1t=0.1 in the formula we are calculating the dimension of the metric space associated to the linear graph but with a distance of 0.10.1 between adjacent points.

Posted by: Simon Willerton on August 3, 2015 3:32 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Hmm. We can work out the magnitude dimension of the integers in the same way. We have an exact formula for the magnitude of the linear graph with NN points with adjacent points tt units apart, namely 1+(N1)tanh(t/2)1+(N-1)\tanh(t/2).

This means we can calculate the dimension of the linear graph with NN points, with adjacency of 11 unit. We get

(tanh(12) 21)(N1)2((N1)tanh(12)+1) -\frac{{\left(\tanh\left(\frac{1}{2}\right)^{2} - 1\right)} {\left(N - 1\right)}}{2 \, {\left({\left(N - 1\right)} \tanh\left(\frac{1}{2}\right) + 1\right)}}

Taking the limit as NN\to \infinity gives tanh(12) 212tanh(12)0.850918. -\frac{\tanh\left(\frac{1}{2}\right)^{2} - 1}{2 \, \tanh\left(\frac{1}{2}\right)}\, \simeq\, 0.850918.

So that gives us an argument that “The magnitude dimension of the integers is about 0.850.85.”

Posted by: Simon Willerton on July 30, 2015 6:04 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

To be clear, it should be pointed out that what you’re calling “magnitude dimension” here is different from what we’ve called “magnitude dimension” before. Here you’re dealing with an “instantaneous” dimension, whereas earlier we’ve considered an “asymptotic” dimension which is 0 for any discrete space.

Posted by: Mark Meckes on July 31, 2015 1:41 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Your formula tanh(12) 212tanh(12) -\frac{\tanh\left(\frac{1}{2}\right)^{2} - 1}{2 \, \tanh\left(\frac{1}{2}\right)} simplifies to 2ee 1=cosech(1). \frac{2}{e - e^{-1}} = cosech(1).

Posted by: Tom Leinster on July 31, 2015 1:43 PM | Permalink | Reply to this

Re: The Spread of a Metric Space

Mark said

what you’re calling “magnitude dimension” here is different from what we’ve called “magnitude dimension” before

Yes, indeed. I was thinking that I was replying in my other post in which it is perhaps more clear what I was referring to.

Posted by: Simon Willerton on July 31, 2015 3:12 PM | Permalink | Reply to this

Post a New Comment