Hausdorff dimension

In mathematics, the Hausdorff dimension is a way of defining a possibly fractional exponent for all figures in a metric space such that the dimension partially describes the amount that the set fills the space around it. For example, a plane would have a Hausdorff dimension of 2, because it fills a 2-parameter subset. However, it would not make sense to give the Sierpiński triangle fractal a dimension of 2, since it does not fully occupy the 2-dimensional realm. The Hausdorff dimension describes this mathematically by measuring the size of the set. For self-similar sets there is a relationship to the number of self-similar subsets and their scale.

Informal definition

Intuitively, the dimension of a set is the number of independent parameters one has to pick in order to fix a point. This is made rigorously with the notion of d-dimensional (topological) manifold which are particularly regular sets. The problem with the classical notion is that you can easily break up the digits of a real number to map it bijectively to two (or d) real numbers. The example of space filling curves shows that it is even possible to do this in a continuous (but non-bijective) way.

The notion of Hausdorff dimension refines this notion of dimension such that the dimension can be any non-negative number.

Benoît Mandelbrot discovered that many objects in nature are not strictly classical smooth bodies, but best approximated as fractal sets, i.e. subsets of R^N whose Hausdorff dimension is strictly greater than its topological dimension.

Hausdorff measure and dimension

Let d be a non-negative real number and S ⊂ X a subset of a metric space (X,ρ). The d-dimensional Hausdorff measure of scale δ>0 is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H^{d*}_\delta(S) := \inf \{\sum_{i=1}^\infty r_i^d : S\subset\bigcup_{i=1}^\infty B_{r_i}(x_i), r_i\le\delta \}}

where B_ri(xi) is the open ball around x_i ∈ X of radius r_i. The d-dimensional Hausdorff measure is now the limit

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H^{d*}(S) := \lim_{\delta\to0+} H^{d*}_\delta(S)} .

As in the Carathéodory construction a set S ⊂ X is called d-measurable iff

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H^{d*}(T) = H^{d*}(S\cap T)+ H^{d*}(T\cap X\setminus S)} for all T ⊂ X.

A set S ⊂ X is called Hausdorff measurable if it is H^d-measurable for all d≥0.

In general it is quite difficult to determine the Hausdorff measure of a set S ⊂ X. However the following two comparisons to the Lebesgue measure are helpful: H⁰ is the counting measure, i.e. the number of points in S ⊂ X and in particular all sets are H⁰-measurable. Let X = R^N and N, d ∈ N natural numbers, then

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H^d = c_d\lambda^d} ,

i.e. the d-dimensional Hausdorff measure is the d-dimensional Lebesgue measure up to a scaling factor c_d which is the volume of the unit ball in R^d.

The Hausdorff measures fulfill the following monotonicity properties:

For S ⊂ T, H^d(S) ≤ H^d(T). If H^d(S) > 0, then H^e(S) = ∞ for all e<d. If H^d(S) < ∞, then H^e(S) = 0 for all e > d.

The Hausdorff dimension of a Hausdorff measurable set S ⊂ X is the non-negative real number d such that H^e(S)= ∞ for e < d and H^e(S) = 0 for e > d. Also the Hausdorff dimension fulfills the monotonicity property: For S ⊂ T Hausdorff measurable, dim_H S ≤ dim_H T.

Elementary properties

1. The Hausdorff dimension of d-dimensional embedded submanifolds of R^N is d.

2. The Hausdorff dimension of a countable union is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathrm{dim}_H \bigcup_{i=1}^\infty F_i = \sup_i \mathrm{dim}_H F_i}

where F_i ⊂ X are Hausdorff measurable sets. In particular the Hausdorff dimension is monotone. Also the Hausdorff dimension of a countable set is 0.

3. The Hausdorff measure behaves under a Lipschitz continuous map f: X→X, i.e. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(f(x),f(y))\le c\rho(x,y)} as follows

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H^d(F) \le c^d H^d(F)}

for every Hausdorff measurable set F ⊂ X. Therefore the Hausdorff dimension can be estimated from above as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dim_H f(F)\le \dim_H F} .

For bi-Lipschitz maps, i.e. there are positive constants c_1/2 > 0 such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_1\rho(x,y)\le\rho(f(x),f(y))\le c_2\rho(x,y)} from a complete metric space (X,ρ), the dimension is preserved, because the inverse map is also bi-Lipschitz.

Examples

Iterated function systems

Consider the map

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S\colon 2^X\to 2^X: F\mapsto \bigcup_{i=1}^n S_i(F)}

where each S_i: X→X is a contraction, i.e. there is a number 0≤c<1 such that :Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(S_i(x),S_i(y) \le c\rho(x,y) \forall x, y\in X} . It is not hard to prove that there is a unique compact nonempty set F ⊂ X such that S(F) = F, i.e. a fixed-point. In order to prove that one uses the Hausdorff metric

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(A,B) :=\inf\{\delta\ge0: A\subset B_\delta \land B\subset A_\delta\}}

where A_δ is the δ-parallel extension of A.

Given the simplest case X=R^N and the S_i scalings with factor c_i each, then we see that the whole set F is the union of n scaled copies of itself. Assuming that F has finite positive Hausdorff measure, this must fulfill

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H^d(F) = \sum_{i=1}^n H^d(S_i(F)) = \sum_{i=1}^n c_i^d H^d(F)}

and thus the dimension d of F

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 = \sum_{i=1}^n c_i^d} . (d)

This heuristic argument is justified if the subsets F_i := S_i(F) are not too strongly overlapping. This can be ensured if there is a bounded nonempty open set O ⊂ X such that

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle O \supset \bigcup_{i=1}^n S_i(O)} (O)

where the union is a disjoint union. The heuristic estimate remains an upper bound if we cannot find a separating open set O.

As more particular examples consider the following:

1. The mid-third Cantor set. This is constructed from the interval [0,1] where in the first step we remove the inner third (1/3,2/3) and in the Nth step we remove the inner part of length 1/3^N from each of the 2^N-1 intervals. The intersection of all the intermediate steps is the mid-third Cantor set. Obviously this is the fixed-point set under the two maps: S₁:R→R:x→x/3 and S₂:R→R:x→(x+2)/3 which each have contraction factor c=1/3. The heuristic argument gives the dimension equation: 1=2•(1/3)^d with the unique solution d = log2/log3. The heuristic argument is justified because for O=(0,1) the equation (O) is fulfilled.

2. Von Koch's snowflake is the " infinite curve" obtained from the following construction: Start with the unit interval [0,1] in R². In each step partition each line segment into thirds and replace the middle third by the other two sides of the equilateral triangle over it. Obviously the snowflake is the fixed point of the union of 4 scalings with factor 1/3 each. The heuristic equation is therefore: 1=4(1/3)^d with the unique solution d = log4/log3 > 1. Again the heuristic argument is justified, because the open set that covers the unit line segment without the endpoints is mapped into four disjoint pieces within itself if the ends lie within 60º angles.

3. The Sierpiński triangle is the limit of the following process. Start with a solid equilateral triangle. In each step divide each equilateral triangle into 4 equilateral pieces (by dividing the edges into halves) and remove the inner head-down piece. Obviously this is the fixed-point figure of the union of the three scalings with factor 1/2. The heuristic equation is therefore 1 = 3(1/2)^d with the unique solution d = log3/log2. The heuristic argument is justified, because the open equilateral triangle (i.e. without border) fulfills the equation (O).

Comparison to the box dimension

The box dimension arises from the following measuring process. Let S ⊂ X be given and determine for δ>0 the minimum number N_δ(S) of balls of radius δ that cover S. If S is a rectifiable curve, then N_δ grows with decreasing δ as N ≈ cδ^-1 (for small δ). If S is a rectifiable d dimensional hypersurface, then N ≈ cδ^-d (for small δ). We therefore define the box dimension as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \underline\dim_B S := \varliminf_{\delta\to0+} \frac{\log N_\delta(S)}{-\log\delta} } ,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \overline\dim_B S := \varlimsup_{\delta\to0+} \frac{\log N_\delta(S)}{-\log\delta} }

and dim_B S the common value if the lower and upper box dimension coincide.

The box dimension also remains the same with the following modifications:

1. instead of balls we take cubes in R^N,
2. we take lattice cubes in R^N,
3. the smallest amount of sets of diameter δ that cover S,
4. the largest amount of disjoint balls of diameter δ whose centers are in S.

The problem of the box dimension is that it is only stable under finite union, i.e.

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dim_B F_1\cup F_2 = \max(\dim F_1,\dim F_2)} .

In particular the box dimension of a countable but dense set in R^N is already N.

In comparison to the Hausdorff dimension we have

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dim_H F\le \underline{\dim}_B F\le \overline{\dim}_B F} .

Comparison to the packing dimension

The shortcoming of the box dimension is that it is not countably stable. This can be enforced by modifying the definition in the following sense

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \underline\dim_{MB} F:= \inf \{\sup_i \underline\dim_B F_i: F\subset \bigcup_{i=1}^\infty F_i \}} .

Unfortunately the computation of the modified box dimension is now as complicated as of the Hausdorff dimension, however the modified box dimension is countably stable. It turns out that the modified box dimension can be easily computed for compact dimensionally homogeneous sets, i.e.: Suppose that S ⊂ X is box measurable and for every point x ∈ S and every sufficiently small open set x ∈ O ⊂ X we have dim_B (O∩S) = dim_B S, then

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dim_{MB} S = \dim_B S} .

The main difference between the Hausdorff and box dimension is the definition of the underlying "measure". In the box dimension case we try to exhaust the set with balls of equal radius δ, while in the Hausdorff measure we cover with balls of radius at most δ and weigh corresponding to the radius. The Hausdorff analogue of the box dimension is the following packing measure

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P^{d*}_\delta(S) := \sup\{\sum_{i=1}^\infty r_i^d : \bigcup_{i=1}^\infty B_{r_i}(x_i)\text{ disjoint and }x_i\in S, r_i\le\delta \}} ,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P^{d*}_0(S) := \lim_{\delta\to0+} P^{d*}_\delta(S)} ,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P^{d*}(S) := \inf\{\sum_{i=1}^\infty P^{d*}_0(F_i): S\subset\bigcup_{i=1}^\infty F_i\}} .

The problem is that P₀^d* is not yet an (outer) measure, but P^d* is. The packing measure has properties analogue to the Hausdorff measure and the packing dimension dim_P is defined analogue to the Hausdorff dimension as the border where the packing measures change from 0 to ∞.

Unfortunately the computation of the packing measure is even more difficult than that of the Hausdorff measure. However it is easy to relate the packing dimension to the upper modified box dimension as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dim_P = \overline\mathrm{dim}_{MB}} .

In total we obtain the following comparison between the Hausdorff, lower modified box dimension, and packing dimension for Hausdorff measurable sets F ⊂ X

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dim_H F\le \underline\mathrm{dim}_{MB} F\le \dim_P F\le \overline\mathrm{dim}_B F} .

Means of computing the Hausdorff dimension

Given the definition of (lower modified) box dimension it is often not too hard to find an upper bound for the Hausdorff dimension. It is however usually much harder to find a lower bound. The following method can be used to achieve that.

Let μ be any measure on F ⊂ X such that μ(B_r(x)) ≤ r^d, then

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H^d(F)\ge \frac{\mu(F)}{c}} .

The s-potential of a measure μ on R^N is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I_s(\mu) := \int_{\R^N} \Phi_s(x)\mathrm{d}\mu(x) = \int_{\R^N\times\R^N} \frac{\mathrm{d}\mu(x)\,\mathrm{d}\mu(y)}{|x-y|^s}} .

If there is a positive measure μ on F ⊂ R^N with I_s(μ) < ∞, then H^s(F) = ∞, and in particular dim_H F ≥ s.

Conversely, if H^d(F) > 0, then there is a measure μ on F ⊂ R^N with I_s(μ) < ∞ for all s < d.

It is also possible to capitalize from Fourier transforms in the estimate of Hausdorff measures in R^N, see e.g. Triebel

Behavior under projection

Given R^N, then an orthogonal projection is a Lipschitz map with C=1. Therefore the dimension of a projected set cannot be bigger than the dimension of the original set. Note that the dimension of the image is also restricted by the dimension of the range of the projection.

Product formula

Remember that the Lebesgue measures (which are equivalent to the Hausdorff measures of integral dimension) fulfill the relation

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \lambda^m\times\lambda^n = \lambda^{m+n}} .

This is related to the dimension theory of embedded submanifolds M and N as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dim M\times N = \dim M+\dim N} . (n)

However for arbitrary Hausdorff measurable sets F and G, the weaker condition

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dim_H F\times G\ge \dim_H F +\dim_H G}

holds.

We obtain an opposite estimate from the box dimension as follows

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dim_H F\times G\le \dim_H F+\overline\mathrm{dim}_B\, G} ,

i.e. if we have a set G for which the upper box dimension and the Hausdorff dimension coincide, then the naive product formula (n) also holds.

Literature

3. K.J. Falconer: Fractal geometry, Wiley & Sons (2003), 2nd edition, ISBN 0-470-84861-8.