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.

March 11, 2015

A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Posted by Simon Willerton

Consider the following shape that we are zooming into and out of. What dimension would you say it was?

zooming dots

At small scales (or when it is very far away) it appears as a point, so seems zero-dimensional. At bigger scales it appears to be a line, so seems one-dimensional. At even bigger scales it appears to have breadth as well as length, so seems two-dimensional. Then, finally, at very large scales it appears to be made from many widely separated points, so seems zero-dimensional again.

We arrive at an important observation:

The perceived dimension varies with the scale at which the shape is viewed.

Here is a graph of my attempt to capture this perceived notion of dimension mathematically.

A graph

Hopefully you can see that, moving from the left, you start off at zero, then move into a region where the function takes value around one, then briefly moves up to two then drops down to zero again.

The ‘shape’ that we are zooming into above is actually a grid of 3000×163000\times 16 points as that’s all my computer could handle easily in making the above picture. If I’d had a much bigger computer and used say 10 7×10 210^{7}\times 10^{2} points then I would have got something that more obviously had both a one-dimensional and two-dimensional regime.

In this post I want to explain how this idea of dimension comes about. It relies on a notion of ‘size’ of metric spaces, for instance, you could use Tom’s notion of magnitude, but the above picture uses my notion of 22-spread.

I have mentioned this idea before at the Café in the post on my spread paper, but I wanted to expand on it somewhat.

What do we mean by dimension?

First we should try to understand how we think of dimension. We are used to thinking of it in terms of ‘degrees of freedom’, or the number of different directions you can go in, so a line is one dimensional and a square is two dimensional. This will always give us an integer dimension.

It was realised that there were spaces that could be given meaningful non-integer dimensions by using a different approach to what dimension is. Let’s follow one train of thought. If we think about the square and the line again, we can see that they have different scaling properties. If we scale up a line by a factor of two, then we can fit exactly two copies of the original line in. If we scale up a square by a factor of two then we can fit four copies of the original square in.

A square and a line

More generally if we scale up the line by a factor of nn then we can fit n=n 1n=n^{1} copies of the original line in and if we similarly scale up the square by a factor of nn we can fit n 2n^{2} copies of the original square. The indices 11 and 22 coincide with the dimensions of the spaces.

Let’s take that as the basis of a different notion of dimension and see what happens when we scale up some fractally shapes.

A first attempt at defining dimension

Let’s take a not well defined notion of scale dimension to be the following. Say that the scale dimension is DD if when we scale up by a factor of nn (for suitable nn) we get n Dn^{D} copies of our original space back.

We see that the Koch curve is scaled by a factor of 33 we can fit four copies of the original in, or more generally when scaled by a factor of n=3 kn=3^{k} we can fit 4 k=(3 log 3(4)) k=n log 3(4)4^{k}=(3^{\log _{3}(4)})^{k}= n^{\log _{3}(4)} copies in. So this says that the scale dimension is log 3(4)\log _{3}(4).

Koch

Similarly for the Cantor set. If you scale it by a factor of three you can fit two copies of the original in, more generally if we scale it by a factor of n=3 kn=3^{k} we can fit 2 k=(3 log 3(2)) k=n log 3(2)2^{k}=(3^{\log _{3}(2)})^{k}= n^{\log _{3}(2)} copies in. So this says that the scale dimension is log 3(2)\log _{3}(2).

Cantor

The above idea, although appealing, has several flaws. One flaw is that it is not clear what is meant by having nn-copies of our original shape: for instance, when we scale up the square and decompose into smaller squares the boundaries overlap, so we get a bit less than four copies. Another flaw is that the above idea only works for certain special shapes: for instance, if we scale up a disk by a factor of two we don’t get a shape we can decompose into four of our original shapes. Indeed, there is no n>1n\gt 1 such that when we scale up a disk by a factor of nn we get a shape that can be decomposed into n 2n^{2} copies of our original disk.

A second attempt

We could address these two flaws by observing that when we scale up a plane shape such as a square or a disk by a factor of two we get a shape which is four times the area of the original shape. Similarly, when we scale all lengths by a factor of nn we get a shape which has n 2n^{2} the area. More generally, for a shape in DD-dimensional Euclidean space, when we scale all lengths by a factor of nn we get a shape which has n Dn^{D} times the volume.

So we could try to say that a shape has volume dimension DD if when you scale it up by a factor of nn the volume changes by a factor of n Dn^{D}. Unfortunately, that doesn’t work for various reasons. Firstly, you have to specify the kind of volume you need for each shape, so you need length for lines and area for squares, so you’re presupposing the dimension when you pick the volume to use! Secondly, this is not going to work for fractals as none of these volumes make sense for a fractal. The Koch curve does not have a meaningfully non-trivial length or area. (To define fractal dimensions such as the Hausdorff or Minkowski dimension you’d take a different turn at this point, but we’ll carry on the way we’re going.)

Defining dimension using a notion of size

An alternative would be if we had a single notion of size which we could use for all shapes simultaneously. For a given shape we could then see how this size changes under scaling and use that to define a notion of dimension. This is the approach I used as I know of several appropriate notions of size.

  • Tom Leinster introduced ‘magnitude’ |||\cdot | which is a notion of size which is defined for every compact subset of a Euclidean space — and more generally, for every compact, positive definite metric space. I’ll not give the definition here.

  • Tom also introduced ‘maximum diversity’ which is based on magnitude, is a bit more complicated to define but is somewhat better behaved on all metric spaces. He gives the definition in this post if you are interested.

  • I introduced a one-parameter family {E q} q0\{ E_{q}\} _{q\ge 0} of notions of size which are defined for every finite metric space — and I suspect for every compact subset of Euclidean space as well. These are easier to define and calculate, but I’ll just give the definitions for E 0E_{0} and E 2E_{2}, which are particularly nice to write down. If (X,d)(X,d) is a finite metric space with NN points then the 00-spread and 22-spread are defined as follows: E 0(X) xX1 yXe d(x,y);E 2(X)N 2 x,yXe d(x,y). E_{0}(X)\coloneqq \sum _{x\in X}\frac{1}{\displaystyle\sum _{y\in X}e^{-d(x,y)}}; \qquad E_{2}(X)\coloneqq \frac{N^{2}}{\displaystyle\sum _{x,y\in X}e^{-d(x,y)}}.

Once we have a notion of size SS, we want to use this to define a notion of dimension which tells us how the size alters under scaling. Typically we can’t do anything as naive as finding a DD such that if we scale by a factor of nn then the size scales by a factor of n Dn^{D}, the sizes described above are generally more interesting than that!

For a shape XX and t>0t\gt 0 we define tXt X to be the shape XX scaled up by a factor of tt. We then have the size S(tX)S(t X) being a function of tt and we define the dimension of XX to be the growth rate of this function at t=1t=1. By growth rate I mean some number associated to a function such that the growth rate of t Dt^{D} is DD. Recalling from school that the way to calculate the growth rate of a function is to plot the function on log-log paper and measure the gradient, we take the instantaneous growth rate of a function to be the logarithmic derivative, d(ln(f(t)))dln(t)\frac{d (\ln (f(t)))}{d \ln (t)}. A couple of applications of the chain rule tell us that this is just df(t)dttf(t)\frac{d f(t)}{dt}\frac{t}{f(t)}.

For a notion of size SS, this leads us to define the S-dimension of a shape XX by dim S(X)dln(S(tX))dln(t)| t=1=dS(tX)dttS(tX)| t=1. \dim _{S}(X)\coloneqq \frac{d \ln (S(t X))}{d \ln (t)}\bigg | _{t=1}=\frac{d S(t X)}{dt}\frac{t}{S(t X)}\bigg |_{t=1}.

The graph in the introduction is the E 2E_2-dimension of the 3000×163000\times 16 lattice of points in the animation plotted as we scale the set of points, i.e. it’s the graph of dim S(tX)dim_S(t X) as we vary tt.

In practice, it seems that the magnitude, E 0E_{0} and E 2E_{2} dimensions of a given shape look very similar. They have different advantages over each over: for instance, we know, or have conjectured, closed forms for magnitudes of several shapes; but in the case of things that we don’t have a closed form for it is quicker to calculate the 00- or 22-spread dimension.

Next time…

Next time I’ll give more examples. I’ll also say something about connections with Minkowski dimension, although I don’t understand the full story there.

Posted at March 11, 2015 3:25 PM UTC

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

19 Comments & 0 Trackbacks

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

If your growth rate graph width was scaled from 400 to 380, HTML layout wouldn’t create all that blank space and position it after the right side bar ends.

Posted by: RodMcGuire on March 11, 2015 4:52 PM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Thanks Rod, I don’t actually see the problem, which is why I hadn’t fixed it!

I do usually make graphics 300pt in the introductory part because I know the problem exists – I did it for the animation but not for the graph. Hopefully it’s now fixed.

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

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Can one make scale dimension precise like this: for a metric space XX and t>0t\gt 0, let tXtX be the scaled space as in your post. Then let C(t)C(t) be the smallest natural number for which there exists a short surjection from the C(t)C(t)-fold coproduct of XX to tXtX. So C(t)C(t) measures how many copies of XX one needs in order to cover tXtX. Then if C(t)C(t) grows like a power in tt, we can define the scale dimension to be this exponent. Does this give anything reasonable? (In order for the coproduct to exist, we need to allow the metrics to assume the value \infty.)

On a different note, I recall having heard of scale-dependent dimensions before: as you might already know, physicists study them in the context of quantum gravity! Figure 3 on page 16 in the link shows plots of the “spectral dimension” and “walk dimension” as a function of a parameter tt, where the direction of increasing tt corresponds to an exponential decrease in length scale. So roughly, their tt is the logarithm of yours, while your tt is their kk ;)

Posted by: Tobias Fritz on March 11, 2015 4:56 PM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Physicists also study scale-dependent notions of dimension in the context of Jackson Pollack paintings.

Posted by: Mark Meckes on March 11, 2015 7:27 PM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Haha, those don’t even look so different from how some people depict quantum gravity:

liquid quantum gravity

Posted by: Tobias Fritz on March 11, 2015 9:11 PM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Tobias, can you calculate your candidate scale dimension for a disk?

I wasn’t familiar with quantum gravity scaling, thanks.

Posted by: Simon Willerton on March 12, 2015 10:19 AM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Here’s a sketch of an argument showing that my candidate scale dimension is 22 for the unit disc D 2D^2. Maybe somebody knows how to make it rigorous?

Let C(t)C(t) be the smallest number of unit discs needed to cover tD 2t D^2, where “cover” is in the sense of my definition in terms of a surjective short map. First, I claim that C(t)C(t) is upper bounded by some multiple of t 2t^2. To see this, we can first cover tD 2tD^2 by something like πt 2\pi t^2 unit squares aligned with the grid; at the boundary of the disc, they need to be squashed a bit in order for them to fit into tD 2tD^2. Second, we can cover each square by 44 copies of D 2D^2 or less. Taken together, this should give something like C(t)4πt 2C(t)\leq 4\pi t^2 for large enough tt.

On the other hand, I believe that the area of the image of a short map D 2tD 2D^2\to t D^2 cannot exceed the area of D 2D^2 itself. This should give a lower bound C(t)t 2C(t)\geq t^2. Together with the upper bound, this suggests that C(t)C(t) grows quadratically in tt, so that the scale dimension of the disc is 22.

Other examples for which it is easier to find a rigorous argument include finite metric spaces and the unit interval. For finite XX, the dimension is zero, since any tXt X can be covered by |X||X| many copies of XX: just map every copy of XX to a single point. Hence the corresponding C(t)C(t) is bounded by |X||X| as tt grows, and the dimension is zero. For the unit interval, one can make a similar argument as for the disc, but it’s much easier to make rigorous: C(t)tC(t)\leq t for integer tt follows from covering t[0,1]=[0,t]t[0,1]=[0,t] by tt copies of [0,1][0,1] in the obvious way; and C(t)tC(t)\geq t is also clear since the image of [0,1][0,1] under a short map is again an interval of length 1\leq 1, and therefore one cannot do better than with the previous covering. In conclusion, we have C(t)=tC(t)=t for the unit interval and integer tt, and the interval’s scale dimension is 11.

Posted by: Tobias Fritz on March 12, 2015 2:51 PM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

I’m confused: your definition of the SS-dimension looks like it is defining a number, but then you say that the E 2E_2 dimension of some shape is a graph or function. Do you mean that the graph is the function tdim S(tX)t \mapsto dim_S(t X)?

Posted by: Mike Shulman on March 11, 2015 8:46 PM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Yes, thanks. I’ll edit to make that clear.

Posted by: Simon Willerton on March 12, 2015 10:13 AM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

This is a little bit like persistent homology, c.f. Robert Ghrist’s stuff.

Posted by: Jake on March 11, 2015 9:41 PM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

It is a little like that, indeed. But what it is not clear is if there is any tangible connection.

Posted by: Simon Willerton on March 12, 2015 10:12 AM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Jake: You should also mention Gunnar Carlsson. I also had had a thought along the same lines. It also relates to shape theory a la Borsuk (1970s) where features are studied at a range of scales. The insight from Persistant homology might be related to the change in ‘dimension’ as the scale changes, i.e. some sort of generalised ‘bar graph’ as you get in papers on Persistence. (I know Simon has thought about this.)

Posted by: Tim Porter on March 13, 2015 7:33 AM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Hi, that’s a very compact and nice definition.

Do I understand right that in order to define size S(tX) in your 0-spread and 2-spread you simply rescale the distance function by t?

I am confused about how you apply this to fractals though… you motivated your definitions also by saying that “the Koch curve does not have a meaningfully non-trivial length”, but for your definition you need a notion of distance… is this distance not the same as a length along the curve? or you use the distance in an embedding space?

Do you know anything about a possible relation between your spreads and the spectral dimension? After all the exponential of a distance does appear also in the heat kernel. I ask because the spectral dimension is much used in quantum gravity these days…as somebody already pointed out (see for example also this one http://arxiv.org/abs/hep-th/0505113 ).

Posted by: Dario Benedetti on March 12, 2015 8:19 PM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Dario, a quick reply for now.

You said

Do I understand right that in order to define size S(tX) in your 0-spread and 2-spread you simply rescale the distance function by t?

Yes the size S(tX)S(t X) is just the rescaling the distance by tt, so for the 22-spread we have

E 2(tX)N 2 x,yXe td(x,y). E_{2}(t X)\coloneqq \frac{N^{2}}{\displaystyle\sum _{x,y\in X}e^{-t d(x,y)}}.

Then you asked

is this distance not the same as a length along the curve?

The Koch curve is not rectifiable – you can’t measure the length along the curve. However, it does sit naturally in 2\mathbb{R}^2 as a compact subset and you can equip it with the subset metric where 2\mathbb{R}^2 has the usual Euclidean metric.

Finally you said

the exponential of a distance does appear also in the heat kernel

It’s actually the exponential of the square of the metric that appears in the heat kernel. This seems to make quite a difference. However, you can look at the asymptotics of the spread of a Riemannian manifold as you scale the metric and the terms in the asymptotic expansion are the same sort of curvature terms that appear in the asymptotic expansion of the heat kernel. This is mentioned in my post on spread in the section on “Non-finite metric spaces”

Posted by: Simon Willerton on March 13, 2015 11:55 AM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Could you make a looped gif where a point expands into a line which turns out to be made of a grid of points which expand leaving just a single point…

which expands into a line hich turns out to be made of a grid of points which expand leaving just a single point…

ad infinitum?

This would be a nice illustration of a set whose dimension keeps looping from 0 to 1 to 2 as we keep zooming in. I think some people would find this exciting.

Posted by: John Baez on March 14, 2015 1:43 AM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Your wish is my command.

zooming picture

One thing that seems right up your street is the formula for the E 2E_2-dimension of a metric space:

dim E 2(X)= x,yXd(x,y)e d(x,y) x,yXe d(x,y). dim_{E_2}(X)=\frac{\sum_{x,y\in X} d(x,y) e^{-d(x,y)}} {\sum_{x,y\in X} e^{-d(x,y)}}.

It looks like some sort of expected value of energy.

Posted by: Simon Willerton on March 16, 2015 10:52 AM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Nice—thanks! I may post this to G+ with a link to your article here.

Yes, that formula is analogous to the expected value of a Hamiltonian, except that the analogy would be better if you had

x,yXd(x,y)e βd(x,y) x,yXe βd(x,y). \frac{\sum_{x,y\in X} d(x,y) e^{-\beta d(x,y)}} {\sum_{x,y\in X} e^{-\beta d(x,y)}}.

where β\beta is an adjustable parameter. In the analogy, β\beta would be 1/kT1/ k T where TT is temperature and kk is Boltzmann’s constant. kTk T has units of energy, and this serves to make βd(x,y)\beta d(x,y) dimensionless, as you want for something that you’re taking the exponential of.

But in your actual problem, β\beta would be an adjustable parameter with units of inverse length. I believe a quantity of this nature appears in your work, since you’re talking about ‘scale-dependent’ quantities: β\beta sets the scale.

Posted by: John Baez on March 20, 2015 2:48 AM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Simon — I posted something about this article on G+, and people are asking some questions I hope you can help me with.

Posted by: John Baez on March 20, 2015 9:01 PM | Permalink | Reply to this

Re: A Scale-Dependent Notion of Dimension for Metric Spaces (Part 1)

Obviously the idea that dimension in the general case varies with scale (and with position) is not new, but I think your size formula (E(X)) is new. To me E2(X) looks a bit like the correlation dimension, but with the step function (point less than 1/t apart) replaced with the soft dropoff e^-td(x,y). This seems like a nice move, as smoother functions are always less subject to noise. Would it work to use a gaussian instead? this would avoid the non-smooth point at d=0.

Posted by: Tom on March 24, 2015 10:31 AM | Permalink | Reply to this

Post a New Comment