Martin-Löf tests

For each $n$, let $m_n$ be the least $m$ with $q_m \leq 2^{-n}$; it exists since $q_m$ tends to $0$, and is computable from $n$. The sequence $\mathcal U_n = \mathcal V_{m_n}$ is uniformly $\Sigma^0_1$, with $\lambda(\mathcal U_n) \leq 2^{-n}$, and $\bigcap_m \mathcal V_m \subseteq \bigcap_n \mathcal U_n$.

Let $(W_e)$ be the standard enumeration of the c.e. subsets of $\nat \times \bstr$. Every Martin-Löf test is of the form $([W_e^{[n]}]^{\prec})_n$ for some $e$, but most indices $e$ do not define tests. We transform each $W_e$ into a test, without changing those that already are.

Fix $e$ and $n$, and let $\sigma_0, \sigma_1, \dots$ be the elements of $W_e^{[n]}$ in the order of their enumeration (the list may be finite). Define finite sets $F_0 = \emptyset$, and $F_{i+1} = F_i \cup \{ \sigma_i \}$ if $\lambda([F_i \cup \{ \sigma_i \}]^{\prec}) \leq 2^{-n}$, and $F_{i+1} = F_i$ otherwise. The measure of the open class generated by a finite set of strings is a rational computable from the set, so the sets $F_i$ are computable from $e$, $n$ and $i$. Let $\mathcal V^e_n = \bigcup_i [F_i]^{\prec}$. Then:

• $(\mathcal V^e_n)_n$ is uniformly $\Sigma^0_1$, uniformly in $e$;
• $\lambda(\mathcal V^e_n) \leq 2^{-n}$, as the supremum of the measures of the increasing classes $[F_i]^{\prec}$, each at most $2^{-n}$;
• if $\lambda([W_e^{[n]}]^{\prec}) \leq 2^{-n}$, then every $\sigma_i$ is accepted, since $[F_i \cup \{ \sigma_i \}]^{\prec} \subseteq [W_e^{[n]}]^{\prec}$; so $\mathcal V^e_n = [W_e^{[n]}]^{\prec}$.

So $(\mathcal V^e_n)_n$ is a Martin-Löf test for every $e$, and every Martin-Löf test is one of them. Let

It is uniformly $\Sigma^0_1$, and $\lambda(\mathcal U_n) \leq \sum_e 2^{-n-e-1} = 2^{-n}$. If $X$ is captured by the test $(\mathcal V^e_m)_m$, then $X \in \mathcal V^e_{n+e+1} \subseteq \mathcal U_n$ for every $n$.

1. The complement of MLR is $\bigcap_n \mathcal U_n$, which is null.
2. The complement of a $\Sigma^0_1$ class is a $\Pi^0_1$ class (Proposition 1.7 of “Trees and Π⁰₁ classes”). A sequence outside $\mathcal U_n$ is outside $\bigcap_m \mathcal U_m$, hence random by universality. A sequence is random if and only if it is outside $\bigcap_n \mathcal U_n$, that is, in some $\mathcal P_n$.
3. $\mathcal P_1$ is a non-empty $\Pi^0_1$ class, since its measure is at least $1/2$. Apply the low basis theorem (Low basis theorem) and the computably dominated basis theorem (Computably dominated basis theorem).

Fix a rational $\varepsilon > 0$, let $C_m$ be the computable set of strings of length $m$ described in Fact 2.6, and let $\mathcal V_n = \bigcup_{m > n} [C_m]^{\prec}$, a uniformly $\Sigma^0_1$ sequence. Let $a = e^{-2\varepsilon^2} < 1$. By subadditivity,

One computes rationals $q_n$ with $2a^{n+1} / (1 - a) \leq q_n \leq 2a^{n+1} / (1-a) + 2^{-n}$; they tend to $0$. If the frequency of ones in $X \uh m$ differs from $\frac12$ by more than $\varepsilon$ for infinitely many $m$, then $X \in \mathcal V_n$ for every $n$, and $X$ is not random by Lemma 2.3. A random $X$ therefore has frequencies eventually within $\varepsilon$ of $\frac12$, for every rational $\varepsilon > 0$.

($\Leftarrow$) A Martin-Löf test is a Solovay test, and a sequence captured by it as a Martin-Löf test is captured by it as a Solovay test.

($\Rightarrow$) Let $(\mathcal S_n)$ be a Solovay test, and let $d$ be such that $\sum_n \lambda(\mathcal S_n) \leq 2^d$. Let $\mathcal V_k$ be the class of sequences that belong to $\mathcal S_n$ for at least $2^k$ values of $n$. A sequence captured by the Solovay test belongs to every $\mathcal V_k$. We show that $(\mathcal V_{k + d})_k$ is a Martin-Löf test.

Fix an enumeration of the c.e. set defining $(\mathcal S_n)$. For a stage $s$, let $\mathcal S_{n,s}$ be the clopen class generated by the strings enumerated into the $n$-th component by stage $s$, for $n \leq s$, and $\mathcal S_{n,s} = \emptyset$ for $n > s$. Delaying the enumeration of each string $\sigma$ to a stage at least $|\sigma|$ does not change the classes $\mathcal S_n$; so we may assume that the strings enumerated by stage $s$ have length at most $s$. Each $\mathcal S_{n,s}$ is then a union of cylinders $[\tau]$ with $|\tau| = s$. Let $D_s$ be the set of strings $\tau$ of length $s$ such that $[\tau] \subseteq \mathcal S_{n,s}$ for at least $2^k$ values of $n$; it is computable from $s$ and $k$. Counting pairs $(\tau, n)$ with $|\tau| = s$ and $[\tau] \subseteq \mathcal S_{n,s}$ in two ways gives

so $\lambda([D_s]^{\prec}) \leq 2^{d - k}$. The classes $[D_s]^{\prec}$ increase with $s$, since the classes $\mathcal S_{n,s}$ do. If $X$ belongs to $2^k$ classes $\mathcal S_n$, all these memberships are witnessed at some stage $s$, and then $X \uh s \in D_s$. So $\mathcal V_k = \bigcup_s [D_s]^{\prec}$: it is uniformly $\Sigma^0_1$, and $\lambda(\mathcal V_k) \leq 2^{d-k}$ by continuity. Hence $(\mathcal V_{k+d})_k$ is a Martin-Löf test, and it captures every sequence captured by $(\mathcal S_n)$.