A fundamental characteristic of many mathematical spaces (e.g. vector spaces, metric spaces, topological spaces, etc.) is their dimension, which measures the “complexity” or “degrees of freedom” inherent in the space. There is no single notion of dimension; instead, there are a variety of different versions of this concept, with different versions being suitable for different classes of mathematical spaces. Typically, a single mathematical object may have several subtly different notions of dimension that one can place on it, which will be related to each other, and which will often agree with each other in “non-pathological” cases, but can also deviate from each other in many other situations. For instance:
- One can define the dimension of a space by seeing how it compares to some standard reference spaces, such as or ; one may view a space as having dimension if it can be (locally or globally) identified with a standard -dimensional space. The dimension of a vector space or a manifold can be defined in this fashion.
- Another way to define dimension of a space is as the largest number of “independent” objects one can place inside that space; this can be used to give an alternate notion of dimension for a vector space, or of an algebraic variety, as well as the closely related notion of the transcendence degree of a field. The concept of VC dimension in machine learning also broadly falls into this category.
- One can also try to define dimension inductively, for instance declaring a space to be -dimensional if it can be “separated” somehow by an -dimensional object; thus an -dimensional object will tend to have “maximal chains” of sub-objects of length (or , depending on how one initialises the chain and how one defines length). This can give a notion of dimension for a topological space or a commutative ring.
The notions of dimension as defined above tend to necessarily take values in the natural numbers (or the cardinal numbers); there is no such space as , for instance, nor can one talk about a basis consisting of linearly independent elements, or a chain of maximal ideals of length . There is however a somewhat different approach to the concept of dimension which makes no distinction between integer and non-integer dimensions, and is suitable for studying “rough” sets such as fractals. The starting point is to observe that in the -dimensional space , the volume of a ball of radius grows like , thus giving the following heuristic relationship
between volume, scale, and dimension. Formalising this heuristic leads to a number of useful notions of dimension for subsets of (or more generally, for metric spaces), including (upper and lower) Minkowski dimension (also known as box-packing dimension or Minkowski-Bougliand dimension), and Hausdorff dimension.
[In -theory, it is also convenient to work with “virtual” vector spaces or vector bundles, such as formal differences of such spaces, and which may therefore have a negative dimension; but as far as I am aware there is no connection between this notion of dimension and the metric ones given here.]
Minkowski dimension can either be defined externally (relating the external volume of -neighbourhoods of a set to the scale ) or internally (relating the internal -entropy of to the scale). Hausdorff dimension is defined internally by first introducing the -dimensional Hausdorff measure of a set for any parameter , which generalises the familiar notions of length, area, and volume to non-integer dimensions, or to rough sets, and is of interest in its own right. Hausdorff dimension has a lengthier definition than its Minkowski counterpart, but is more robust with respect to operations such as countable unions, and is generally accepted as the “standard” notion of dimension in metric spaces. We will compare these concepts against each other later in these notes.
One use of the notion of dimension is to create finer distinctions between various types of “small” subsets of spaces such as , beyond what can be achieved by the usual Lebesgue measure (or Baire category). For instance, a point, line, and plane in all have zero measure with respect to three-dimensional Lebesgue measure (and are nowhere dense), but of course have different dimensions (, , and respectively). (The Kakeya set conjecture, discussed recently on this blog, offers another good example.) This can be used to clarify the nature of various singularities, such as that arising from non-smooth solutions to PDE; a function which is non-smooth on a set of large Hausdorff dimension can be considered less smooth than one which is non-smooth on a set of small Hausdorff dimension, even if both are smooth almost everywhere. While many properties of the singular set of such a function are worth studying (e.g. their rectifiability), understanding their dimension is often an important starting point. The interplay between these types of concepts is the subject of geometric measure theory.
— 1. Minkowski dimension —
Before we study the more standard notion of Hausdorff dimension, we begin with the more elementary concept of the (upper and lower) Minkowski dimension of a subset of a Euclidean space .
There are several equivalent ways to approach Minkowski dimension. We begin with an “external” approach, based on a study of the -neighbourhoods of , where and we use the Euclidean metric on . These are open sets in and therefore have a -dimensional volume (or Lebesgue measure) . To avoid divergences, let us assume for now that is bounded, so that the have finite volume.
Let . Suppose is a bounded portion of a -dimensional subspace, e.g. , where is the unit ball in and we identify with in the usual manner. Then we see from the triangle inequality that
for all , which implies that
for some constants depending only on . In particular, we have
(compare with (1)). This motivates our first definition of Minkowski dimension:
Definition 1 Let be a bounded subset of . The upper Minkowski dimension is defined as
and the lower Minkowski dimension is defined as
If the upper and lower Minkowski dimensions match, we refer to as the Minkowski dimension of . In particular, the empty set has a Minkowski dimension of .
Unwrapping all the definitions, we have the following equivalent formulation, where is a bounded subset of and :
- We have iff for every , one has for all sufficiently small and some .
- We have iff for every , one has for arbitrarily small and some .
- We have iff for every , one has for arbitrarily small and some .
- We have iff for every , one has for all sufficiently small and some .
- (i) Let be the Cantor set consisting of all base strings , where each takes values in . Show that has Minkowski dimension . (Hint: approximate any small by a negative power of .)
- (ii) Let be the Cantor set consisting of all base strings , where each takes values in when for some integer , and is arbitrary for the other values of . Show that has a lower Minkowski dimension of and an upper Minkowski dimension of .
Exercise 2 Suppose that is a compact set with the property that there exist and an integer such that is equal to the union of disjoint translates of . (This is a special case of a self-similar fractal; the Cantor set is a typical example.) Show that has Minkowski dimension .
If the translates of are allowed to overlap, establish the upper bound .
It is clear that we have the inequalities
for non-empty bounded , and the monotonicity properties
Exercise 3 Show that any subset of with lower Minkowski dimension less than has Lebesgue measure zero. In particular, any subset of positive Lebesgue measure must have full Minkowski dimension .
Now we turn to other formulations of Minkowski dimension. Given a bounded set and , we make the following definitions:
- (the external -covering number of ) is the fewest number of open balls of radius with centres in needed to cover .
- (the internal -covering number of ) is the fewest number of open balls of radius with centres in needed to cover .
- (the -metric entropy) is the cardinality of the largest -net in , i.e. the largest set in such that for every .
- (the -packing number of ) is the largest number of disjoint open balls one can find of radius with centres in .
These three quantities are closely related to each other, and to the volumes :
One can now take the formulae (4), (5) as the definition of Minkowski dimension for bounded sets (and then use (2), (3) to extend to unbounded sets). The formulations (4), (5) for have the advantage of being intrinsic – they only involve , rather than the ambient space . For metric spaces, one still has a partial analogue of Exercise 4, namely
As such, these formulations of Minkowski dimension extend without any difficulty to arbitrary bounded metric spaces (at least when the spaces are locally compact), and then to unbounded metric spaces by (2), (3).
Exercise 5 If is a Lipschitz map between metric spaces, show that and for all . Conclude in particular that the graph of any Lipschitz function has Minkowski dimension , and the graph of any measurable function has Minkowski dimension at least .
Note however that the dimension of graphs can become larger than that of the base in the non-Lipschitz case:
Exercise 7 Let be a bounded metric space. For each , let be a maximal -net of (thus the cardinality of is ). Show that for any continuous function and any , one has the inequality
(Hint: For any , define to be the nearest point in to , and use a telescoping series.) This inequality (and variants thereof), which replaces a continuous supremum of a function by a sum of discrete suprema of differences of that function, is the basis of the generic chaining technique in probability, used to estimate the supremum of a continuous family of random processes. It is particularly effective when combined with bounds on the metric entropy , which of course is closely related to the Minkowski dimension of , and with large deviation bounds on the differences . A good reference for generic chaining is the text by Talagrand.
Exercise 8 If and are bounded sets, show that
Give a counterexample that shows that either of the inequalities here can be strict. (Hint: There are many possible constructions; one of them is a modification of Exercise 1(ii).)
It is easy to see that Minkowski dimension reacts well to finite unions, and more precisely that
for any . However, it does not respect countable unions. For instance, the rationals have Minkowski dimension , despite being the countable union of points, which of course have Minkowski dimension . More generally, it is not difficult to see that any set has the same upper or lower Minkowski dimension as its topological closure , since both sets have the same -neighbourhoods. Thus we see that the notion of Minkowski dimension misses some of the fine structure of a set , in particular the presence of “holes” within the set. We now turn to the notion of Hausdorff dimension, which rectifies some of these defects.
— 2. Hausdorff measure —
The Hausdorff approach to dimension begins by noting that -dimensional objects in tend to have a meaningful -dimensional measure to assign to them. For instance, the -dimensional boundary of a polygon has a perimeter, the -dimensional vertices of that polygon have a cardinality, and the polygon itself has an area. So to define the notion of a -Hausdorff dimensional set, we will first define the notion of the -dimensional Hausdorff measure of a set .
To do this, let us quickly review one of the (many) constructions of -dimensional Lebesgue measure, which we are denoting here by . One way to build this measure is to work with half-open boxes in , which we assign a volume of . Given this notion of volume for boxes, we can then define the outer Lebesgue measure of any set by the formula
where the infimum ranges over all at most countable collections of boxes that cover . One easily verifies that is indeed an outer measure (i.e. it is monotone, countably subadditive, and assigns zero to the empty set). We then define a set to be -measurable if one has the additivity property
for all . By Carathéodory’s theorem, the space of -measurable sets is a -algebra, and outer Lebesgue measure is a countably additive measure on this -algebra, which we denote . Furthermore, one easily verifies that every box is -measurable, which soon implies that every Borel set is also; thus Lebesgue measure is a Borel measure (though it can of course measure some non-Borel sets also).
Finally, one needs to verify that the Lebesgue measure of a box is equal to its classical volume ; the above construction trivially gives but the converse is not as obvious. This is in fact a rather delicate matter, relying in particular on the completeness of the reals; if one replaced by the rationals , for instance, then all the above constructions go through but now boxes have Lebesgue measure zero (why?). See Chapter 1 of Folland’s book, for instance, for details.
Anyway, we can use this construction of Lebesgue measure as a model for building -dimensional Hausdorff measure. Instead of using half-open boxes as the building blocks, we will instead work with the open balls . For -dimensional measure, we will assign each ball a measure (cf. (1)). We can then define the unlimited Hausdorff content of a set by the formula
where the infimum ranges over all at most countable families of balls that cover . (Note that if is compact, then it would suffice to use finite coverings, since every open cover of has a finite subcover. But in general, for non-compact we must allow the use of infinitely many balls.)
As with Lebesgue measure, is easily seen to be an outer measure, and one could define the notion of a -measurable set on which Carathéodory’s theorem applies to build a countably additive measre. Unfortunately, a key problem arises: once is less than , most sets cease to be -measurable! We illustrate this in the one-dimensional case with and , and consider the problem of computing the unlimited Hausdorff content . On the one hand, this content is at most , since one can cover by the ball of radius centred at for any . On the other hand, the content is also at least . To see this, suppose we cover by a finite or countable family of balls (one can reduce to the finite case by compactness, though it isn’t necessary to do so here). The total one-dimensional Lebesgue measure of these balls must equal or exceed the Lebesgue measure of the entire interval , thus
From the inequality (which is obvious after expanding the RHS and discarding cross-terms) we see that
and the claim follows.
We now see some serious breakdown of additivity: for instance, the unlimited -dimensional content of is , despite being the disjoint union of and , which each have an unlimited content of . In particular, this shows that (for instance) is not measurable with respect to the unlimited content. The basic problem here is that the most efficient cover of a union such as for the purposes of unlimited -dimensional content is not coming from covers of the separate components and of that union, but is instead coming from one giant ball that covers directly.
To fix this, we will limit the Hausdorff content by working only with small balls. More precisely, for any , we define the Hausdorff content of a set by the formula
where the balls are now restricted to be less than or equal to in radius. This quantity is increasing in , and we then define the Hausdorff outer measure by the formula
(This is analogous to the Riemann integral approach to volume of sets, covering them by balls, boxes, or rectangles of increasingly small size; this latter approach is also closely connected to the Minkowski dimension concept studied earlier. The key difference between the Lebesgue/Hausdorff approach and the Riemann/Minkowski approach is that in the former approach one allows the balls or boxes to be countable in number, and to be variable in size, whereas in the latter approach the cover is finite and uniform in size.)
Exercise 9 Show that if , then for all . Thus -dimensional Hausdorff measure is only a non-trivial concept for subsets of in the regime .
Since each of the are outer measures, is also. But the key advantage of moving to the Hausdorff measure rather than Hausdorff content is that we obtain a lot more additivity. For instance:
Exercise 10 Let be subsets of which have a non-zero separation, i.e. the quantity is strictly positive. Show that . (Hint: one inequality is easy. For the other, observe that any small ball can intersect or intersect , but not both.)
One consequence of this is that there is a large class of measurable sets:
Proposition 2 Let . Then every Borel subset of is -measurable.
Proof: Since the collection of -measurable sets is a -algebra, it suffices to show the claim for closed sets . (It will be slightly more convenient technically to work with closed sets rather than open ones here.) Thus, we take an arbitrary set and seek to show that
We may assume that and are both finite, since the claim is obvious otherwise from monotonicity.
From Exercise 10 and the fact that is an outer measure, we already have
where is the -neighbourhood of . So it suffices to show that
For any , we have the telescoping sum , where , and thus by countable subadditivity and monotonicity
so it suffices to show that the sum is absolutely convergent.
Consider the even-indexed sets . These sets are separated from each other, so by many applications of Exercise 10 followed by monotonicity we have
for all , and thus is absolutely convergent. Similarly for , and the claim follows.
On the -measurable sets , we write for , thus is a Borel measure on . We now study what this measure looks like for various values of . The case is easy:
Now we look at the opposite case . It is easy to see that any Lebesgue-null set of has -dimensional Hausdorff measure zero (since it may be covered by balls of arbitrarily small total content). Thus -dimensional Hausdorff measure is absolutely continuous with respect to Lebesgue measure, and we thus have for some locally integrable function . As Hausdorff measure and Lebesgue measure are clearly translation-invariant, must also be translation-invariant and thus constant. We therefore have
for some constant .
We now compute what this constant is. If denotes the volume of the unit ball , then we have
for any at most countable collection of balls . Taking infima, we conclude that
and so .
In the opposite direction, observe from Exercise 4 that given any , one can cover the unit cube by at most balls of radius , where depends only on ; thus
and so ; in particular, is finite.
We can in fact compute explicitly (although knowing that is finite and non-zero already suffices for many applications):
Proof: Let us consider the Hausdorff measure of the unit cube. By definition, for any one can find an such that
Observe (using Exercise 4) that we can find at least disjoint balls of radius inside the unit cube. We then observe that
On the other hand,
putting all this together, we obtain
which rearranges as
Since is bounded below by , we can then send and conclude that ; since we already showed , the claim follows.
Thus -dimensional Hausdorff measure is an explicit constant multiple of -dimensional Lebesgue measure. The same argument shows that for integers , the restriction of -dimensional Hausdorff measure to any -dimensional linear subspace (or affine subspace) is equal to the constant times -dimensional Lebesgue measure on . (This shows, by the way, that is not a -finite measure on in general, since one can partition into uncountably many -dimensional affine subspaces. In particular, it is not a Radon measure in general).
One can then compute -dimensional Hausdorff measure for other sets than subsets of -dimensional affine subspaces by changes of variable. For instance:
Exercise 12 Let be an integer, let be an open subset of , and let be a smooth injective map which is non-degenerate in the sense that the Hessian (which is a matrix) has full rank at every point of . For any compact subset of , establish the formula
where the Jacobian is the square root of the sum of squares of all the determinants of the minors of the matrix . (Hint: By working locally, one can assume that is the graph of some map from to , and so can be inverted by the projection function; by working even more locally, one can assume that the Jacobian is within an epsilon of being constant. The image of a small ball in then resembles a small ellipsoid in , and conversely the projection of a small ball in is a small ellipsoid in . Use some linear algebra and several variable calculus to relate the content of these ellipsoids to the radius of the ball.) It is possible to extend this formula to Lipschitz maps that are not necessarily injective, leading to the area formula
for such maps, but we will not prove this formula here.
From this exercise we see that -dimensional Hausdorff measure does coincide to a large extent with the -dimensional notion of surface area; for instance, for a simple smooth curve with everywhere non-vanishing derivative, the measure of is equal to its classical length . One can also handle a certain amount of singularity (e.g. piecewise smooth non-degenerate curves rather than everywhere smooth non-degenerate curves) by exploiting the countable additivity of measure, or by using the area formula alluded to earlier.
Now we see how the Hausdorff dimension varies in .
Exercise 13 Let , and let be a Borel set. Show that if is finite, then is zero; equivalently, if is positive, then is infinite.
Example 1 Let be integers. The unit ball has a -dimensional Hausdorff measure of (by Lemma 3), and so it has zero -dimensional Hausdorff dimensional measure for and infinite -dimensional measure for .
On the other hand, we know from Exercise 11 that is positive for any non-empty set , and that for every . We conclude (from the least upper bound property of the reals) that for any Borel set , there exists a unique number in , called the Hausdorff dimension of , such that for all and for all . Note that at the critical dimension itself, we allow to be zero, finite, or infinite, and we shall shortly see in fact that all three possibilities can occur. By convention, we give the empty set a Hausdorff dimension of . One can also assign Hausdorff dimension to non-Borel sets, but we shall not do so to avoid some (very minor) technicalities.
Example 2 The unit ball has Hausdorff dimension , as does itself. Note that the former set has finite -dimensional Hausdorff measure, while the latter has an infinite measure. More generally, any -dimensional smooth manifold in has Hausdorff dimension .
Exercise 14 Show that the graph has Hausdorff dimension ; compare this with Exercise 6.
It is clear that Hausdorff dimension is monotone: if are Borel sets, then . Since Hausdorff measure is countably additive, it is also not hard to see that Hausdorff dimension interacts well with countable unions:
Thus for instance the rationals, being a countable union of -dimensional points, have Hausdorff dimension , in contrast to their Minkowski dimension of . On the other hand, we at least have an inequality between Hausdorff and Minkowski dimension:
Exercise 15 For any Borel set , show that . (Hint: use (5). Which of the choices of is most convenient to use here?)
It is instructive to compare Hausdorff dimension and Minkowski dimension as follows.
Exercise 16 Let be a bounded Borel subset of , and let .
- Show that if and only if, for every and arbitrarily small , one can cover by finitely many balls of radii equal to such that .
- Show that if and only if, for every and all sufficiently small , one can cover by finitely many balls of radii equal to such that .
- Show that if and only if, for every and , one can cover by countably many balls of radii at most such that .
The previous two exercises give ways to upper-bound the Hausdorff dimension; for instance, we see from Exercise 2 that self-similar fractals of the type in that exercise (i.e. is translates of ) have Hausdorff dimension at most . To lower bound the Hausdorff dimension of a set , one convenient way to do so is to find a measure with a certain “dimension” property (analogous to (1)) that assigns a positive mass to :
Exercise 17 Let . A Borel measure on is said to be a Frostman measure of dimension at least if it is compactly supported there exists a constant such that for all balls of radius . Show that if has dimension at least , then any Borel set with has positive -dimensional Hausdorff content; in particular, .
Note that this gives an alternate way to justify the fact that smooth -dimensional manifolds have Hausdorff dimension , since on the one hand they have Minkowski dimension , and on the other hand they support a non-trivial -dimensional measure, namely Lebesgue measure.
Exercise 19 Construct a subset of of Hausdorff dimension that has zero Lebesgue measure. (Hint: A modified Cantor set, vaguely reminiscent of Exercise 1(ii), can work here.)
A useful fact is that Exercise 17 can be reversed:
Lemma 4 (Frostman’s lemma) Let , and let be a compact set with . Then there exists a non-trivial Frostman measure of dimension at least supported on (thus and ).
Proof: Without loss of generality we may place the compact set in the half-open unit cube . It is convenient to work dyadically. For each integer , we subdivide into half-open cubes of sidelength in the usual manner, and refer to such cubes as dyadic cubes. For each and any , we can define the dyadic Hausdorff content to be the quantity
where the range over all at most countable families of dyadic cubes of sidelength at most that cover . By covering cubes by balls and vice versa, it is not hard to see that
for some absolute constants depending only on . Thus, if we define the dyadic Hausdorff measure
then we see that the dyadic and non-dyadic Huausdorff measures are comparable:
In particular, the quantity is strictly positive.
Given any dyadic cube of length , define the upper Frostman content to be the quantity
Then . By covering by , we also have the bound
Finally, by the subadditivity property of Hausdorff content, if we decompose into cubes of sidelength , we have
The quantity behaves like a measure, but is subadditive rather than additive. Nevertheless, one can easily find another quantity to assign to each dyadic cube such that
for all dyadic cubes, and such that
whenever a dyadic cube is decomposed into sub-cubes of half the sidelength. Indeed, such a can be constructed by a greedy algorithms starting at the largest cube and working downward; we omit the details. One can then use this “measure” to integrate any continuous compactly supported function on (by approximating such a function by one which is constant on dyadic cubes of a certain scale), and so by the Riesz representation theorem, it extends to a Radon measure supported on . (One could also have used the Caratheódory extension theorem at this point.) Since , is non-trivial; since for all dyadic cubes , it is not hard to see that is a Frostman measure of dimension at least , as desired.
The study of Hausdorff dimension is then intimately tied to the study of the dimensional properties of various measures. We give some examples in the next few exercises.
Exercise 20 Let , and let be a compact set. Show that if and only if, for every , there exists a compactly supported probability Borel measure with
Show that this condition is also equivalent to lying in the Sobolev space . Thus we see a link here between Hausdorff dimension and Sobolev norms: the lower the dimension of a set, the rougher the measures that it can support, where the Sobolev scale is used to measure roughness.
Exercise 21 Let be a compact subset of , and let be a Borel probability measure supported on . Let .
- Suppose that for every , every , and every subset of with , one could establish the bound for equal to any of (the exact choice of is irrelevant thanks to Exercise 4). Show that has Hausdorff dimension at least . (Hint: cover by small balls, then round the radius of each ball to the nearest power of . Now use countable additivity and the observation that sum is small when ranges over sufficiently small powers of .)
- Show that one can replace with in the previous statement. (Hint: instead of rounding the radius to the nearest power of , round instead to radii of the form for integers .) This trick of using a hyper-dyadic range of scales rather than a dyadic range of scales is due to Bourgain. The exponent in the double logarithm can be replaced by any other exponent strictly greater than .
This should be compared with the task of lower bounding the lower Minkowski dimension, which only requires control on the entropy of itself, rather than of large subsets of . The results of this exercise are exploited to establish lower bounds on the Hausdorff dimension of Kakeya sets (and in particular, to conclude such bounds from the Kakeya maximal function conjecture, as discussed in this previous post).
Exercise 22 Let be a Borel set, and let be a locally Lipschitz map. Show that , and that if has zero -dimensional Hausdorff measure then so does .
Exercise 23 Let be a smooth function, and let be a test function such that on the support of . Establish the co-area formula
(Hint: Subdivide the support of to be small, and then apply a change of variables to make linear, e.g. .) This formula is in fact valid for all absolutely integrable and Lipschitz , but is difficult to prove for this level of generality, requiring a version of Sard’s theorem.
The coarea formula (6) can be used to link geometric inequalities to analytic ones. For instance, the sharp isoperimetric inequality
valid for bounded open sets in , can be combined with the coarea formula (with ) to give the sharp Sobolev inequality
for any test function , the main point being that is the boundary of (one also needs to do some manipulations relating the volume of those level sets to ). We omit the details.