1.5 Algorithmic Randomness

We review the tests-based approach to algorithmic randomness, all with respect to a given premeasure.

1.5.1 Weights¶

When working with the $s$-dimensional Hausdorff premeasure $\rho_s$ for some $s \geq 0$, we might simply write $\operatorname{DW}_s(\mathcal{V})$ for the direct $s$-weight of $\mathcal{V}$, and similar for the other weight notions.

For any $\mathcal{V} \subseteq 2^{<\omega}$, we defined $\widehat{\mathcal{V}}$ in Section 1.2 to include only those strings in $\mathcal{V}$ which are minimal with respect to the prefix relation. Then $\widehat{\mathcal{V}}$ is prefix-free and satisfies $[\widehat{\mathcal{V}}] = [\mathcal{V}]$. Using this fact, it is straightforward to verify that the above weight notions are ordered as follows:

These covering weights also relate to the $s$-dimensional Hausdorff outer measures. In particular, if $\mathcal{H}^s(X) < c$ for some dimension parameter $s \geq 0$, constant $c > 0$, and subset $X \subseteq 2^\omega$, then it follows that for every $r \in \omega$, there exists a collection of finite binary strings $S \subseteq 2^{\geq r}$ such that $X \subseteq [S]$ and $\operatorname{DW}_s(S) < c$.

1.5.2 Tests¶

We introduce some test notions, or effective schemes for identifying null-sets with respect to some premeasure. For the rest of the section, we will only consider upper-semicomputable premeasures on $2^\omega$. This restriction is made to ensure the collection of all tests of some type is uniformly-c.e. By relativizing these tests to some oracle, one could expand the class of premeasures considered to those which are upper-semicomputable in $B$.

We use $\mathcal{T}$ as a placeholder for any one of the above test notions. Once again, for any Hausdorff premeasure $\rho_s$ with $s > 0$ being left-c.e., we simplify each of the above terms as $\mathcal{T}$-$s$-tests. And when $s = 1$, we might simply refer to them as $\mathcal{T}$-tests. Furthermore, any one of these test notions may be relativized to an oracle $B \in 2^{\leq \omega}$, regarding computable-enumerability as in $B$. We may refer to such tests as $\mathcal{T}$-$B$-$\rho$-tests.

A Martin-Löf-$\rho$-test (or ML-$\rho$-test) is the strictest notion of test we have defined, meaning from any Martin-Löf-$\rho$-test $\mathcal{U}$, one may produce a $\mathcal{T}$-$\rho$-test for any of the other test notions $\mathcal{T}$. In fact, such a $\mathcal{U}$ is already both a strong and vehement ML-$\rho$-test, and generates the collection $\mathcal{V} := \bigcup_n U_n$ which is a (strong) Solovay-$\rho$-test. Of course, any strong ML-$\rho$-test is also a vehement ML-$\rho$-test, and any Solovay-$\rho$-test is already a strong Solovay-$\rho$-test.

1.5.3 Covers¶

Tests act as effective covers of subsets of Cantor space.

For a fixed test notion $\mathcal{T}$ (e.g., Martin-Löf) and upper-semicomputable premeasure $\rho$ on $2^\omega$, an infinite binary string $x \in 2^\omega$ is said to be $\mathcal{T}$-$\rho$-random if $\seq{x}$ passes all $\mathcal{T}$-$\rho$-tests. Otherwise, $\seq{x}$ is covered by some such test, exhibiting itself to be (effectively) $\mathcal{T}$-$\rho$-null.

Note that if $\rho$ is an upper-semicomputable, Hausdorff premeasure (i.e., the premeasure associated to an upper-semicomputable dimension function $h$ as described in Section 1.3), being $\mathcal{T}$-$\rho$-null for any of the test notions $\mathcal{T}$ defined here implies being $\mathcal{H}^\rho$-null. Suppose, for instance, that $\mathcal{U}$ were a vehement ML-$\rho$-test and $\delta > 0$. Then, it is possible to show that there exists a sequence $(W_n)_{n \in \omega}$ where each $W_n \subseteq 2^{<\omega}$ consists of strings of diameter no greater than $\delta$ and is such that $[U_n] \subseteq [W_n]$ and $\operatorname{DW}_\rho(W_n) \leq 2 \cdot 2^{-n}$. If $\mathcal{V} = \bigcup_n W_n$, then

Since $\delta > 0$ was arbitrary, $\mathcal{H}^\rho$ is an outer measure, and $X \subseteq \limsup_{\sigma \in \mathcal{V}} [\sigma]$, the (first) Borel-Cantelli lemma implies $\mathcal{H}^\rho(X) = 0$. Additionally, supposing $\mathcal{V}$ were a strong Solovay-$\rho$-test covering $X$ and $\delta > 0$, then we could restrict $\mathcal{V}$ to only those strings of diameter no more than $\delta$ while maintaining $\mathcal{V}$ being a strong Solovay-$\rho$-test covering $X$. Then, for each $\varepsilon > 0$, it is possible to show that there exists a prefix-free subset $\mathcal{P} \subseteq \mathcal{V}$ such that $[\mathcal{V}] \subseteq [\mathcal{P}]$ and $\operatorname{DW}_\rho(\mathcal{P}) < \varepsilon$. Then, by monotonicity, $\mathcal{H}^\rho_\delta(X) \leq \operatorname{DW}_\rho(\mathcal{P}) < \varepsilon$. And since both $\delta, \varepsilon > 0$ were arbitrary, we conclude $X$ is $\mathcal{H}^\rho$-null.

For any upper-semicomputable premeasure $\rho$ on $2^\omega$ and any of the above test notions $\mathcal{T}$, it follows from the property that $\mathcal{H}^\rho$ is an outer measure that the set of non-$\mathcal{T}$-$\rho$-randoms is $\mathcal{H}^\rho$-null.

Weaker randomness notions come from stricter test notions. So, the class of Martin-Löf-$\rho$-randoms contains all the other classes of $\mathcal{T}$-$\rho$-randoms discussed here.

1.5.4 More Covering Notions¶

Let us start by reviewing some definitions originally appearing in Katz & Tao (2001) (and re-appearing slightly differently in Orponen (2021)).

Note that in Definition 1.5.3, we consider $X$ to be covered by a Solovay-type test if that test strongly covers $X$ in the sense of Definition 1.5.4.

The quantity $N(X, \delta)$ is exactly what appears in the definitions of the box-counting dimensions, as it captures the least number of $\delta$-balls required to cover $X$ (see Falconer, 1990). This fractal dimension always bounds the Hausdorff dimension from above.

Suppose that $X \subseteq \mathbb{R}^m$ has $\dim_{\operatorname{H}} X = s$. Then any $(C, \delta, s)$-set will have no more points in $X$ than a constant times what any $\delta$-net on $X$ would. That is, $(C, \delta, s)$-sets are spread out such that they never dedicate many points to sets of small Hausdorff dimension.

Note that it is not vital that we use $r$-balls in these definitions for $N(X, \delta)$ or $(C, \delta, s)$-sets. For instance, replacing these with dyadic cubes of comparable side-lengths would produce roughly equivalent notions.

Over Euclidean space, there is a relationship between Hausdorff dimension and $(C, \delta, s)$-sets. For instance, a set of Hausdorff dimension less than $s$ will have a $(C, \delta, s)$-set whose $\delta$-neighborhood strongly covers the set. The precise result originally appeared in Katz & Tao (2001) by N. Katz and T. Tao, but was simplified and slightly generalized by T. Orponen in Orponen (2021).

The above lemma was leveraged by Orponen to generalize a weak form of the Marstrand-Mattila Projection Theorem for arbitrary subsets of Euclidean space Orponen, 2021 (see Theorem 5.1.2). We will present an effective proof of the Katz-Tao lemma later in Section 5.1.

Also recall the related notion of an optimal cover originally by J. Miller Miller, 2011.

Optimal covers witness the vehement $\rho$-weight of a set. In general, it is unclear whether optimal covers exist. However, a result by P. Hudelson proves a necessary condition for the existence of optimal covers.

Essential to the proof of Lemma 1.5.9 is the fact that whenever $\rho$ is convex and $\sigma \in 2^{<\omega}$, then $\seq{\sigma}$ is the $\operatorname{DW}_\rho$-minimal cover of $[\sigma]$ among all other collections $S \subseteq \bbrk{\sigma}$ covering $[\sigma]$.

Observe that an optimal cover will necessarily be prefix-free by minimality. When $\rho = \rho^s$, simplify the term to an $s$-optimal cover. Optimal covers were originally employed by Miller to construct a $\Delta^0_2$-definable real with effective dimension equal to $1 / 2$ yet unable to compute any real of greater effective dimension Miller, 2011. We will make use of optimal covers for effectivizing Lemma 1.5.7 in Section 5.1.