1.9 Effective Hausdorff Dimension

J. Lutz was the first to introduce a refinement to Hausdorff dimension in the form of constructive dimension Lutz, 2000, which could distinguish between subsets of zero Hausdorff dimension by their algorithmically-exploitable patterns. Shortly after, E. Mayordomo demonstrated this quantity matched an algorithmic information density involving Kolmogorov complexity first studied by L. Staiger Mayordomo, 2002Staiger, 1989. In this section, we review a few of the characterizations for effective dimension, but not necessarily in their historical order.

For simplicity, we define the effective dimension notions in this section over $2^\omega$. With slight adjustments, some may be extended to any $\mathbb{R}^m$.

Inspired by the definition of the local dimension of an outer measure in K. Falconer’s book Falconer, 1990, define local dimension for outer measures and semimeasures as follows.

In the language of supergales, the map $\boldsymbol{\delta}(\sigma) := 2^{s \cdot \operatorname{len}(\sigma)} \cdot \mathbf{M}(\sigma)$ is an optimal constructive $s$-supergale whenever $s \geq 0$ is left-c.e. It follows from our Theorem 1.8.3 that $\dim_{\operatorname{loc}} \mathbf{M}$ matches J. Lutz’s constructive dimension Lutz, 2000Lutz, 2003. That is, for any $X \subseteq 2^\omega$,

In light of (1.8.5), we may consider $\operatorname{cdim}$ to be an effective version of Hausdorff dimension. We will cite some other asymptotic coincidences further justifying this view.

In Mayordomo (2002), Mayordomo proved that Lutz’s constructive dimension of a point $x$ matches the lower incompressibility ratio of prefix Kolmogorov complexity of $x$:

where the last equality follows from the Coding Theorem 1.8.2. So $\mathbf{M}$ and $\mathbf{m}$ produce the same local dimension notion on $2^\omega$.

Note that by definition, $\dim_{\operatorname{loc}} \mathbf{M}$ is itself the lower incompressibility ratio with respect to a priori complexity:

One might also attempt to effectivize the definition of classical Hausdorff dimension directly. Suppose $\mathcal{U}$ is a Martin-Löf-$s$-test covering $X \subseteq 2^\omega$. Then, $\mathcal{U}$ acts as an effective witness to $X$ being $s$-null. In analogy with the definition of Hausdorff dimension in (1.3.1), define the effective Hausdorff dimension of $X \in 2^\omega$ to be:

Note that the same could be done for any other of the effective test notions defined above. We prefer to work with Martin-Löf-randomness because it admits universal tests. In particular, for each left-c.e. $s > 0$, there exists a universal ML-$s$-test $\mathcal{U}^s$. This means that if $\mathcal{U}$ is an ML-$s$-test covering some subset $X \subseteq 2^\omega$, then so too will $\mathcal{U}^s$ cover $X$. The existence of such a $\mathcal{U}^s$ implies the pointwise stability of effective Hausdorff dimension. That is, for any $X \subseteq 2^{\omega}$,

Martin-Löf-$s$-randomness relates to success by constructive $s$-supergales. That is, if there exists a constructive $s$-supergale succeeding on $X$, then $X$ will be ML-$t$-null for all left-c.e. $t > s$. Conversely, if $s$ is left-c.e. and $X$ is ML-$s$-null, then there exists a constructive $s$-supergale succeeding on $X$. Therefore, $\operatorname{cdim}(X) = \operatorname{effdim}(X)$ on all sets $X \subseteq 2^\omega$.

In his doctoral dissertation, N. Lutz introduced the map $\boldsymbol{\kappa}(X) := 2^{-K(X)}$, an outer measure on $2^\omega$ (originally, $\mathbb{R}^m$) which possesses many algorithmic optimality properties as explored in both Lutz, 2017Lutz & Lutz, 2020. In particular, J. Lutz and N. Lutz showed that $\boldsymbol{\kappa}(X)$ is locally optimal among all the other strongly finite, lower-semicomputable outer measures on $2^\omega$, and that any locally optimal outer measure $\boldsymbol{\mu}$ has local dimension $\dim_{\operatorname{loc}}\boldsymbol{\mu}$ matching the lower incompressibility ratio of prefix complexity Lutz & Lutz, 2020.

We now summarize these standard asymptotic coincidences in the following theorem.

We will use $\dim(\cdot)$ as a generic placeholder for any one of those listed in Theorem 1.9.2 over either Cantor space or Euclidean space. And $\dim(x)$ will stand for $\dim(\seq{x})$ for any $x \in 2^\omega$.

We further note that effectivized packing dimension (or strong dimension) coincides with the upper incompressibility ratio of prefix complexity, as first shown in Athreya et al. (2007). So, we fix the notation: