Hausdorff dimension

The intuitive concept of dimension of a geometric object X is the number of independent parameters one needs to pick out a unique point inside. However, any point specified by two parameters can be instead specified by one, because the cardinality of the real plane is equal to the cardinality of the real line (this can be seen by an argument involving interweaving the digits of two numbers to yield a single number encoding the same information). The example of a space-filling curve shows that one can even map the real line to the real plane surjectively (taking one real number into a pair of real numbers in a way so that all pairs of numbers are covered) and continuously, so that a one-dimensional object completely fills up a higher-dimensional object. Every space-filling curve hits some points multiple times and does not have a continuous inverse. It is impossible to map two dimensions onto one in a way that is continuous and continuously invertible. The topological dimension, also called Lebesgue covering dimension, explains why. This dimension is the greatest integer n such that in every covering of X by small open balls there is at least one point where n + 1 balls overlap. For example, when one covers a line with short open intervals, some points must be covered twice, giving dimension n = 1. But topological dimension is a very crude measure of the local size of a space (size near a point). A curve that is almost space-filling can still have topological dimension one, even if it fills up most of the area of a region. A fractal has an integer topological dimension, but in terms of the amount of space it takes up, it behaves like a higher-dimensional space. The Hausdorff dimension measures the local size of a space taking into account the distance between points, the metric. Consider the number N(r) of balls of radius at most r required to cover X completely. When r is very small, N(r) grows polynomially with 1/r. For a sufficiently well-behaved X, the Hausdorff dimension is the unique number d such that N(r) grows as 1/rd as r approaches zero. More precisely, this defines the box-counting dimension, which equals the Hausdorff dimension when the value d is a critical boundary between growth rates that are insufficient to cover the space, and growth rates that are overabundant. For shapes that are smooth, or shapes with a small number of corners, the shapes of traditional geometry and science, the Hausdorff dimension is an integer agreeing with the topological dimension. But Benoit Mandelbrot observed that fractals, sets with noninteger Hausdorff dimensions, are found everywhere in nature. He observed that the proper idealization of most rough shapes one sees is not in terms of smooth idealized shapes, but in terms of fractal idealized shapes: Clouds are not spheres, mountains are not cones, coastlines are not circles, and bark is not smooth, nor does lightning travel in a straight line. For fractals that occur in nature, the Hausdorff and box-counting dimension coincide. The packing dimension is yet another similar notion which gives the same value for many shapes, but there are well-documented exceptions where all these dimensions differ. ==Formal definition==

The formal definition of the Hausdorff dimension is arrived at by defining first the d-dimensional Hausdorff measure, a fractional-dimension analogue of the Lebesgue measure. First, an outer measure is constructed: Let X be a metric space. If S\subset X and d\in [0,\infty), :H^d_\delta(S)=\inf\left \{\sum_{i=1}^\infty (\operatorname{diam} U_i)^d: \bigcup_{i=1}^\infty U_i\supseteq S, \operatorname{diam} U_i where the infimum is taken over all countable covers U of S. The Hausdorff d-dimensional outer measure is then defined as \mathcal{H}^d(S)=\lim_{\delta\to 0}H^d_\delta(S), and the restriction of the mapping to measurable sets justifies it as a measure, called the d-dimensional Hausdorff Measure. Hausdorff dimension The Hausdorff dimension \dim_{\operatorname{H}}{(X)} of X is defined by :\dim_{\operatorname{H}}{(X)}:=\inf\{d\ge 0: \mathcal{H}^d(X)=0\}. This is the same as the supremum of the set of d\in [0,\infty) such that the d-dimensional Hausdorff measure of X is infinite (except that when this latter set of numbers d is empty the Hausdorff dimension is zero). Hausdorff content The d-dimensional unlimited Hausdorff content of S is defined by :C_H^d(S):= H_\infty^d(S) = \inf\left \{ \sum_{k=1}^\infty (\operatorname{diam} U_k)^d: \bigcup_{k=1}^\infty U_k\supseteq S \right \} In other words, C_H^d(S) has the construction of the Hausdorff measure where the covering sets are allowed to have arbitrarily large sizes. (Here we use the standard convention that \inf\varnothing=\infty.) The Hausdorff measure and the Hausdorff content can both be used to determine the dimension of a set, but if the measure of the set is non-zero, their actual values may disagree. ==Examples==

example. The Sierpinski triangle, an object with Hausdorff dimension of log(3)/log(2)≈1.58. • The Euclidean space \R^n has Hausdorff dimension n, and the circle S^1 has Hausdorff dimension 1. The Sierpinski triangle is a union of three copies of itself, each copy shrunk by a factor of 1/2; this yields a Hausdorff dimension of ln(3)/ln(2) ≈ 1.58. • Lewis Fry Richardson performed detailed experiments to measure the approximate Hausdorff dimension for various coastlines. His results have varied from 1.02 for the coastline of South Africa to 1.25 for the west coast of Great Britain. ==Properties of Hausdorff dimension==

Hausdorff dimension and inductive dimension Let X be an arbitrary separable metric space. There is a topological notion of inductive dimension for X which is defined recursively. It is always an integer (or +∞) and is denoted dimind(X). Theorem. Suppose X is non-empty. Then : \dim_{\mathrm{Haus}}(X) \geq \dim_{\operatorname{ind}}(X). Moreover, : \inf_Y \dim_{\operatorname{Haus}}(Y) =\dim_{\operatorname{ind}}(X), where Y ranges over metric spaces homeomorphic to X. In other words, X and Y have the same underlying set of points and the metric dY of Y is topologically equivalent to dX. These results were originally established by Edward Szpilrajn (1907–1976), e.g., see Hurewicz and Wallman, Chapter VII. Hausdorff dimension and Minkowski dimension The Minkowski dimension is similar to, and at least as large as, the Hausdorff dimension, and they are equal in many situations. However, the set of rational points in [0, 1] has Hausdorff dimension zero and Minkowski dimension one. There are also compact sets for which the Minkowski dimension is strictly larger than the Hausdorff dimension. Hausdorff dimensions and Frostman measures If there is a measure μ defined on Borel subsets of a metric space X such that μ(X) > 0 and μ(B(x, r)) ≤ rs holds for some constant s > 0 and for every ball B(x, r) in X, then dimHaus(X) ≥ s. A partial converse is provided by Frostman's lemma. Behaviour under unions and products If X=\bigcup_{i\in I}X_i is a finite or countable union, then : \dim_{\operatorname{Haus}}(X) =\sup_{i\in I} \dim_{\operatorname{Haus}}(X_i). This can be verified directly from the definition. If X and Y are non-empty metric spaces, then the Hausdorff dimension of their product satisfies : \dim_{\operatorname{Haus}}(X\times Y)\ge \dim_{\operatorname{Haus}}(X)+ \dim_{\operatorname{Haus}}(Y). This inequality can be strict. It is possible to find two sets of dimension 0 whose product has dimension 1. In the opposite direction, it is known that when X and Y are Borel subsets of Rn, the Hausdorff dimension of X × Y is bounded from above by the Hausdorff dimension of X plus the upper packing dimension of Y. These facts are discussed in Mattila (1995). ==Self-similar sets==

Many sets defined by a self-similarity condition have dimensions which can be determined explicitly. Roughly, a set E is self-similar if it is the fixed point of a set-valued transformation ψ, that is ψ(E) = E, although the exact definition is given below. Theorem. Suppose : \psi_i: \mathbf{R}^n \rightarrow \mathbf{R}^n, \quad i=1, \ldots , m are each a contraction mapping on Rn with contraction constant ri A = \bigcup_{i=1}^m \psi_i (A). The theorem follows from Stefan Banach's contractive mapping fixed point theorem applied to the complete metric space of non-empty compact subsets of Rn with the Hausdorff distance. The open set condition To determine the dimension of the self-similar set A (in certain cases), we need a technical condition called the open set condition (OSC) on the sequence of contractions ψi. There is an open set V with compact closure, such that : \bigcup_{i=1}^m\psi_i (V) \subseteq V, where the sets in union on the left are pairwise disjoint. The open set condition is a separation condition that ensures the images ψi(V) do not overlap "too much". Theorem. Suppose the open set condition holds and each ψi is a similitude, that is a composition of an isometry and a dilation around some point. Then the unique fixed point of ψ is a set whose Hausdorff dimension is s where s is the unique solution of : \sum_{i=1}^m r_i^s = 1. The contraction coefficient of a similitude is the magnitude of the dilation. In general, a set E which is carried onto itself by a mapping : A \mapsto \psi(A) = \bigcup_{i=1}^m \psi_i(A) is self-similar if and only if the intersections satisfy the following condition: : H^s\left(\psi_i(E)\cap \psi_j(E)\right) =0, where s is the Hausdorff dimension of E and Hs denotes s-dimensional Hausdorff measure. This is clear in the case of the Sierpinski gasket (the intersections are just points), but is also true more generally: Theorem. Under the same conditions as the previous theorem, the unique fixed point of ψ is self-similar. == The Moran Equation ==

For self-similar sets satisfying the Open set condition, the Hausdorff dimension d can be determined using the Moran equation. If a fractal is composed of m self-similar copies with contraction ratios r_1, r_2, \dots, r_m , the dimension d is the unique positive solution to the equation: \sum_{i=1}^{m} r_i^d = 1 This framework is particularly useful for calculating the dimensions of fractals generated by substitution tilings, such as those based on the metallic mean family. ==See also==