Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

1.1 Measures and Hausdorff Dimension

Geometric measure theory studies fractal measures and dimensions. We outline here a standard method for building outer meaures from premeasures, which guides the standard construction of Hausdorff measures and dimension. These notes are biased to put a spotlight on Hausdorff dimension as a principal quantity of fractal geometry. This is despite the established importance of other fractal measures/dimensions and their established connections with AIT.

1.1.1Measures

We begin by reviewing premeasures and their associated outer measures. For more details, refer to Reimann, 2008 and Rogers, 1970.

In the setting of Cantor space, it is customary to consider a premeasure on 2ω2^\omega to be any non-negative mapping defined on the cylinder sets ρ:B→[0,+∞]\rho : \mathcal{B} \to [0, +\infty]. Of course, such maps are in one-to-one correspondence with maps defined on the finite binary strings ρ:2<ω→[0,+∞]\rho: 2^{<\omega} \to [0, +\infty]. We may freely interchange between these two types by identifying any σ∈2<ω\sigma \in 2^{<\omega} with its cylinder set [σ]∈B[\sigma] \in \mathcal{B}.

In metric spaces, there is a standard, general method (introduced as “Method II” in Rogers (1970)) to induce an outer measure from a given premeasure.

We call Hρ\mathcal{H}^\rho the Method II outer measure associated to the premeasure ρ\rho. And for each δ>0\delta > 0, we also call Hδρ\mathcal{H}^\rho_\delta the ρ\rho-dimensional δ\delta-content measure.

An outer measure μ\mu on a metric space is metric if μ(E∪F)=μ(E)+μ(F)\mu(E \cup F) = \mu(E) + \mu(F) whenever EE and FF are a positive distance apart. Every Method II outer measure is metric: if EE and FF are a distance d>0d > 0 apart, then no set of diameter less than dd meets both, so Hδρ(E∪F)=Hδρ(E)+Hδρ(F)\mathcal{H}^\rho_\delta(E \cup F) = \mathcal{H}^\rho_\delta(E) + \mathcal{H}^\rho_\delta(F) for every δ<d\delta < d. By Carathéodory’s criterion, an outer measure is metric if and only if every Borel set BB is μ\mu-measurable, meaning μ(E)=μ(E∩B)+μ(E∖B)\mu(E) = \mu(E \cap B) + \mu(E \setminus B) for every EE. Every Method II outer measure is metric Rogers, 1970.

In Rogers (1970), C. Rogers also defines an alternative “Method I” which differs from Method II in that it does not enforce any upper bound on the diameter of the cover elements used in the infimum:

HI⁡ρ(X):=inf⁡(Ci)i∈ω⊆C{∑iρ(Ci):⋃iCi⊇X}.\begin{aligned} \mathcal{H}^\rho_{\operatorname{I}}(X) &:= \inf_{(C_i)_{i \in \omega} \subseteq \mathcal{C}} \set{\sum_{i} \rho(C_i)}{\bigcup_i C_i \supseteq X}. \end{aligned}

This outer measure is also sometimes denoted H∞ρ\mathcal{H}^\rho_\infty. While this method also produces an outer measure from a premeasure ρ\rho which agrees on null sets with Hρ\mathcal{H}^\rho, Rogers points out that only the results of Method II can be guaranteed to be additive on sets which are separated by positive distance Rogers, 1970. We proceed with Method II as our preferred way to produce outer measures from premeasures.

Cantor space: 2ω2^\omega, is a metric space when imbued with the standard metric,

d(x,y):={2−Nif x≠y and N=min⁡{n∈ω:x(n)≠y(n)},0if x=y.\begin{aligned} d(x, y) := \begin{cases} 2^{-N} & \text{if $x \neq y$ and $N = \min\set{n \in \omega}{x(n) \neq y(n)}$},\\ 0 & \text{if $x = y$}. \end{cases} \end{aligned}

Note that this metric is compatible with the product topology generated by the cylinder sets in B\mathcal{B}.

1.1.2Hausdorff Measures

An important class of outer measures on any metric space (Ω,d)(\Omega, d) are the Hausdorff outer measures, which are those Method II outer measures induced from premeasures whose values depend only on the diameter of the set. First, declare a dimension function (a.k.a., gauge) to be any non-negative, non-decreasing, continuous-on-the-right function hh defined on all non-negative real numbers and satisfying h(t)=0  ⟺  t=0h(t) = 0 \iff t = 0. One may associate to any dimension function hh its Hausdorff premeasure defined on all X⊆ΩX \subseteq \Omega as follows:

ρh(X):=(h∘diam⁡d)(X).\begin{aligned} \rho_h(X) := (h \circ \diam_d)(X). \end{aligned}

Denote by Hh:=Hρh\mathcal{H}^h := \mathcal{H}^{\rho_h} the Hausdorff outer measure associated to hh.

In Cantor space, ρh(σ)=h(2−len⁡(σ))\rho_h(\sigma) = h\p{2^{- \operatorname{len}(\sigma)}} for any σ∈2<ω\sigma \in 2^{<\omega}. So, any Hausdorff premeasure on 2ω2^\omega is length-invariant, in that ρh(σ)\rho_h(\sigma) only depends on the length of σ\sigma.

Later, we will briefly focus on convex Hausdorff premeasures ρ\rho over Cantor space, which satisfy:

ρ(σ)≤ρ(σ⌢0)+ρ(σ⌢1),\begin{aligned} \rho(\sigma) \leq \rho(\sigma^\smallfrown 0) + \rho(\sigma^\smallfrown 1), \end{aligned}

for all σ∈2<ω\sigma \in 2^{<\omega}. It is easy to see that all length-invariant, convex Hausdorff premeasures over 2ω2^\omega are also strongly convex, meaning for all σ∈2<ω\sigma \in 2^{<\omega} and i∈{0,1}i \in \seq{0, 1},

ρ(σ⌢i)≥ρ(σ)2.\begin{aligned} \rho(\sigma ^\smallfrown i) \geq \frac{\rho(\sigma)}{2}. \end{aligned}

Essential to fractal geometry is the family of ss-dimensional Hausdorff premeasures ρs:=ρhs\rho_s := \rho_{h_s}, where hs:t↦tsh_s : t \mapsto t^s is the dimension function associated to s≥0s \geq 0. If δ>0\delta > 0, let Hδs:=Hδρs\mathcal{H}^s_{\delta} := \mathcal{H}^{\rho_s}_\delta denote the ss-dimensional Hausdorff δ\delta-content, and Hs:=Hρs\mathcal{H}^s := \mathcal{H}^{\rho_s} the ss-dimensional Hausdorff outer measure.

For any outer measure μ\mu on a metric space (Ω,d)(\Omega, d), we say a set X⊆ΩX \subseteq \Omega is μ\mu-null if μ(X)=0\mu(X) = 0. Any Hs\mathcal{H}^s-null XX is also called ss-null. And, if μ\mu and ν\nu are outer measures on Ω\Omega, then ν\nu is said to be absolutely continuous with respect to μ\mu, written ν≪μ\nu \ll \mu, if every μ\mu-null set is also ν\nu-null. A set X⊆ΩX \subseteq \Omega is μ\mu-conull if Ω∖X\Omega \setminus X is μ\mu-null. More generally, a subset Y⊆XY \subseteq X is μ\mu-conull in XX if X∖YX \setminus Y is μ\mu-null.

Suppose Hs(X)<∞\mathcal{H}^s(X) < \infty for some s≥0s \geq 0. This implies that XX is s+s_+-null for any s+>ss_+ > s too. Alternatively, if Hs(X)>0\mathcal{H}^s(X) > 0 for some s≥0s \geq 0, then it must be that Hs−(X)=∞\mathcal{H}^{s_-}(X) = \infty for all 0≤s−<s0 \leq s_- < s. So, the shape of the function s↦Hs(X)s \mapsto \mathcal{H}^s(X) is either constant with value 0 or ∞\infty, or a step from ∞\infty to 0 (where, at the critical value of ss where the step occurs, Hs(X)\mathcal{H}^s(X) could take on any value in [0,∞][0, \infty]). This motivates the following definition for the Hausdorff dimension of a set XX Hausdorff, 1919Falconer, 1990:

dim⁡H⁡(X):=inf⁡{s≥0:X is s-null},\begin{aligned} \dim_{\operatorname{H}}(X) := \inf\set{s \geq 0}{\text{$X$ is $s$-null}}, \end{aligned}

or +∞+\infty if the infimum is taken over the empty set.

Consider now how some sets fall between the cracks of the power functions hsh_s: a set of Hausdorff dimension ss could have Hs(X)∈{0,+∞}\mathcal{H}^s(X) \in \seq{0, +\infty} (i.e., be ss-null or have infinite Hs\mathcal{H}^s-measure). In either case, no power function hs′h_{s'} assigns XX a positive, finite measure. Still, it is possible that some dimension function does: call a dimension function hh an exact gauge for XX if 0<Hh(X)<+∞0 < \mathcal{H}^h(X) < +\infty. In particular, if the gauge hsh_s is exact for a set XX, then it is common to call XX and ss-set.

And exact gauges still relate back to Hausdorff dimension through their relationship with power laws.

If XX is a set for which there exists an exact gauge hh for XX with lim inf⁡t→0+log⁡h(t)log⁡t=dim⁡H⁡(X)\liminf_{t \to 0^+} \frac{\log h(t)}{\log t} = \dim_{\operatorname{H}}(X), let us consider XX to be Hausdorff gauge-regular. In particular, every ss-set is Hausdorff gauge-regular, as witnessed by hsh_s.

1.1.3Packing Dimension

Over Euclidean space, a second standard fractal dimension is built from the covering numbers:

While Tricot (1982) originally introduced packing dimension through packing measures, the formula above is its equivalent characterization as the modified upper box-counting dimension Falconer, 1990. We always have that dim⁡H⁡(X)≤dim⁡P⁡(X)\dim_{\operatorname{H}}(X) \leq \dim_{\operatorname{P}}(X), and dim⁡P⁡(X)≤dim⁡‾B⁡(X)\dim_{\operatorname{P}}(X) \leq \overline{\dim}_{\operatorname{B}}(X) whenever XX is bounded. Following Fiedler & Stull (2024), a set X⊆RmX \subseteq \mathbb{R}^m is said to be weakly regular if dim⁡H⁡(X)=dim⁡P⁡(X)\dim_{\operatorname{H}}(X) = \dim_{\operatorname{P}}(X).

1.1.4Hausdorff Dimension of Measures

An outer measure inherits Hausdorff dimension from the sets that carry its mass.

Intuitively, the lower Hausdorff dimension is small when at least some of its mass sits on a set of small dimension; whereas the upper Hausdorff dimension is small when all of its mass does. These definitions are usually stated for finite Borel measures over Rm\mathbb{R}^m Falconer, 1997.

Notice that every μ\mu-conull set EE has μ(E)=μ(Ω)>0\mu(E) = \mu(\Omega) > 0, so we always have dim⁡‾H⁡(μ)≤dim⁡‾H⁡(μ)\underline{\dim}_{\operatorname{H}}(\mu) \leq \overline{\dim}_{\operatorname{H}}(\mu).

For an outer measure μ\mu on Ω\Omega and a set X⊆ΩX \subseteq \Omega, let the restriction of μ\mu to XX be the outer measure μ⌞X:E↦μ(E∩X)\mu \llcorner X : E \mapsto \mu(E \cap X). We can also relate the dimension of μ⌞X\mu \llcorner X back to that of XX. Fix X⊆ΩX \subseteq \Omega with μ(X)>0\mu(X) > 0. Notice that a set EE is (μ⌞X)(\mu \llcorner X)-conull exactly when E∩XE \cap X is μ\mu-conull in XX, so

dim⁡‾H⁡(μ⌞X)=inf⁡{dim⁡H⁡(Y):Y⊆X is μ-conull in X}=inf⁡{dim⁡H⁡(X∖N):N⊆X is μ-null}≤dim⁡H⁡(X).\begin{aligned} \overline{\dim}_{\operatorname{H}}(\mu \llcorner X) &= \inf \set{\dim_{\operatorname{H}}(Y)}{\text{$Y \subseteq X$ is $\mu$-conull in $X$}}\\ &= \inf \set{\dim_{\operatorname{H}}(X \setminus N)}{\text{$N \subseteq X$ is $\mu$-null}}\\ &\leq \dim_{\operatorname{H}}(X). \end{aligned}

Equality here holds exactly when deleting a μ\mu-null set NN from XX never lowers its Hausdorff dimension. Let’s call a set XX Hausdorff measure-regular if there exists a metric outer measure μ\mu on Ω\Omega with 0<μ(X)<∞0 < \mu(X) < \infty and dim⁡‾H⁡(μ⌞X)=dim⁡H⁡(X)\overline{\dim}_{\operatorname{H}}(\mu \llcorner X) = \dim_{\operatorname{H}}(X).

The following proposition gives two sufficient conditions for this:

Stull (2022) assumes these two conditions, for a metric outer measure μ\mu with 0<μ(X)<∞0 < \mu(X) < \infty, in his sufficient condition for the existence of optimal Hausdorff oracles.

Note that while the first condition actually proves equality for lower Hausdorff dimension as well, the second condition does not control the lower dimension. To be concrete, suppose s>0s > 0, that Hs(X)>0\mathcal{H}^s(X) > 0, and x∈Xx \in X. Then μ:=Hs+δx\mu := \mathcal{H}^s + \delta_x (where δx\delta_x is the point mass at xx) satisfies the second condition while dim⁡‾H⁡(μ⌞X)=0\underline{\dim}_{\operatorname{H}}(\mu \llcorner X) = 0.

Moreover, Hausdorff gauge-regularity implies Hausdorff measure-regularity.

References
  1. Reimann, J. (2008). Effectively closed sets of measures and randomness. Annals of Pure and Applied Logic, 156(1), 170–182. https://doi.org/10.1016/j.apal.2008.06.015
  2. Rogers, C. A. (1970). Hausdorff Measures. Cambridge Mathematical Library.
  3. Hausdorff, Felix. (1919). Dimension und äußeres Maß. Mathematische Annalen, 79, 157–179. http://eudml.org/doc/158784
  4. Falconer, K. (1990). Fractal geometry - mathematical foundations and applications. (p. I–XXII, 1–288). Wiley.
  5. Tricot, C. (1982). Two definitions of fractional dimension. Mathematical Proceedings of the Cambridge Philosophical Society, 91(1), 57–74. 10.1017/S0305004100059119
  6. Fiedler, J. B., & Stull, D. M. (2024). Universal Sets for Projections.
  7. Falconer, K. (1997). Techniques in Fractal Geometry. Wiley.
  8. Stull, Donald. M. (2022). Optimal Oracles for Point-To-Set Principles. In P. Berenbrink & B. Monmege (Eds.), 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) (Vol. 219, p. 57:1-57:17). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. 10.4230/LIPIcs.STACS.2022.57