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

$H_{\delta }^{d*}(S):=\inf\{\sum _{i=1}^{\infty }r_{i}^{d}:S\subset \bigcup _{i=1}^{\infty }B_{r_{i}}(x_{i}),r_{i}\leq \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

$H^{d*}(S):=\lim _{\delta \to 0+}H_{\delta }^{d*}(S)$.

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

$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

$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

$\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. $\rho (f(x),f(y))\leq c\rho (x,y)$ as follows

$H^{d}(F)\leq c^{d}H^{d}(F)$

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

$\dim _{H}f(F)\leq \dim _{H}F$.

For bi-Lipschitz maps, i.e. there are positive constants c_1/2 > 0 such that $c_{1}\rho (x,y)\leq \rho (f(x),f(y))\leq 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

$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 :$\rho (S_{i}(x),S_{i}(y)\leq 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

$\rho (A,B):=\inf\{\delta \geq 0: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

$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

$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

$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

${\underline {\dim }}_{B}S:=\varliminf _{\delta \to 0+}{\frac {\log N_{\delta }(S)}{-\log \delta }}$,

${\overline {\dim }}_{B}S:=\varlimsup _{\delta \to 0+}{\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.

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

$\dim _{H}F\leq {\underline {\dim }}_{B}F\leq {\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

${\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 there is an open set x ∈ O ⊂ X such that dim_B (O∩S) = dim_B S, then

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

$P_{\delta }^{d*}(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}\leq \delta \}$,

$P_{0}^{d*}(S):=\lim _{\delta \to 0+}P_{\delta }^{d*}(S)$,

$P^{d*}(S):=\inf\{\sum _{i=1}^{\infty }P_{0}^{d*}(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

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

$\dim _{H}F\leq {\underline {\mathrm {dim} }}_{MB}F\leq \dim _{P}F\leq {\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

$H^{d}(F)\geq {\frac {\mu (F)}{c}}$.

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

$I_{s}(\mu ):=\int _{\mathbb {R} ^{N}}\Phi _{s}(x)\mathrm {d} \mu (x)=\int _{\mathbb {R} ^{N}\times \mathbb {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 image of the projection.

Product formula

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

$\lambda ^{m}\times \lambda ^{n}=\lambda ^{m+n}$.

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

$\dim M\times N=\dim M+\dim N$. (n)

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

$\dim _{H}F\times G\geq \dim _{H}F+\dim _{H}G$

holds.

We obtain an opposite estimate from the box dimension as follows

$\dim _{H}F\times G\leq \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.