## September 5, 2012

### The Spread of a Metric Space

#### Posted by Simon Willerton

Given a finite metric space $X$ we can define the spread $E_0(X)$ by

$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 $q$ with $0\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=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=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 $X$ is a finite metric space with $N$ points, $t \gt 0$ and $t X$ denotes $X$ with the metric scaled by a factor of $t$ then we get the following basic properties of the spread.

• $1\le E_0(X)\le N$;
• $E_0(t X)$ is increasing in $t$;
• $E_0(t X)\to 1$ as $t\to 0$;
• $E_0(t X)\to N$ as $t\to \infty$;
• $E_0(X)\le e^{diam(X)}$.

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

then we get the following plot of the spread as we scale $t$.

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|$ of a metric space $X$ 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,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!

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 $t$ then its length (its size) scales by a factor of $t^1$.

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

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

Of course, the $1$, $2$ and $3$ 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)$ of a metric space $X$ is defined by

$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 $10$ by $4900$ points at various scales, and the above describes exactly the kind of phenomena that we see.

If my computer could handle much bigger matrices then I could calculate the dimension profile for say $1000$ by $100000000$ 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 $ln 4/ ln 3$. So when it’s not too small and it’s not too large, then the finite approximation looks ‘Koch-like’.

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 $X$ 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)\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 $n$-sphere with radius $R$. 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 $M$ is scaled up. These leading order terms depends just on the volume $vol(M)$ and the total scalar curvature $tsc(M)$, in particular we have the following.

$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 $\omega_n$ is the volume of the unit $n$-ball.

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

$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.

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:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2553

### 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 $e$ in the definition to another positive constant $a$, then natural scale should go from around $1$ to around $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_0$ measures really is how ‘spread out’ the $\mu$-mass of $X$ 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 $A$ of $N$-dimensional Euclidean space, up to a factor of $N!$ times the volume of the unit ball, the maximum diversity of $A$ is the same as the “Bessel capacity of $A$ of order $(N+1)/2$ and index $2$”. Or is that index $(N+1)/2$ and order $2$? In any case, it’s sometimes denoted $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_{\alpha, p}$ for which $\alpha p \le N$. When $\alpha p$ is bigger than $N$, 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 = \frac{1}{E_0(1)} \frac{dE_0(1)}{dt}$.

Intuitively, I would expect the dimension to be 1, but I am finding $dim_0$ seems to asymptote around 0.851 (I calculated up to $10^6$ points using the definition of $E_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^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 dim$_0$ for up to $10^6$ points in mathematica using the summation formula from section 2: $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 dim$_0$ in my post above. This is a plot for the dimension dim$_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]

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]\cap \mathbb{N}$, with the obvious metric, so $n$ is distance $d$ from $n+d$. For large $N$ 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:

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.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) := \frac{t}{E_0(tX)}\frac{dE_0(tX)}{dt}$ evaluated at $t=1$”. Am I reading this wrong? If not, why are you allowed to use $t=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 $X$. If we scale the metric by a factor of $\tau$ to get the metric space $\tau X$, we can calculate its dimension with an application of the chain rule:

\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.1$ in the formula we are calculating the dimension of the metric space associated to the linear graph but with a distance of $0.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 $N$ points with adjacent points $t$ units apart, namely $1+(N-1)\tanh(t/2)$.

This means we can calculate the dimension of the linear graph with $N$ points, with adjacency of $1$ unit. We get

$-\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 $N\to \infinity$ gives $-\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.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 $-\frac{\tanh\left(\frac{1}{2}\right)^{2} - 1}{2 \, \tanh\left(\frac{1}{2}\right)}$ simplifies to $\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