Strong Medvedev reducibilities and the KL-randomness problem

[KHW, Theorem 2] shows that $\operatorname{MLR}\leq_{s,tt}\operatorname{KLR}$. The proof demonstrates that $\operatorname{MLR}\leq_{s,tt}\operatorname{Either}(\operatorname{MLR})$ and notes, by citation to [MR2183813], that $\operatorname{KLR}\subseteq\operatorname{Either}(\operatorname{MLR})$. ∎

Let $\Phi^{X}$ be a positive reduction. By definition, for each input $n$, $\sigma_{f(n)}$ can be written in conjunctive normal form: $\sigma_{f(n)}=\bigwedge_{k=1}^{t_{n}}\bigvee_{i=1}^{m_{k}}v_{f(n),i,k}$. We say that a clause of $\sigma_{f(n)}$ is a disjunct $\bigvee_{i=1}^{m_{k}}v_{f(n),i,k}$. There are two cases to consider:

Case 1: There is a parity such that there are infinitely many $n$ such that every clause of $\sigma_{f(n)}$ contains a variable.

Without loss of generality, consider the even case. Let $A=\omega\oplus R$ for $R$ an arbitrary random real. Each $\bigvee_{i=1}^{m_{k}}v_{n,i,k}$ that contains an even variable is true. So for the infinitely many $n$ whose disjunctions all query an even variable, $\sigma_{f(n)}=\bigwedge_{k=1}^{t_{n}}\top=\top$. As these infinitely many $n$ can be found computably, $\Phi^{A}$ is not immune, and so not random.

Set $A=R\oplus\emptyset$ for an arbitrary random real $R$. For almost all inputs, some clause is a disjunction of $\bot$, so that the entire conjunction is false. Thus $\Phi^{A}$ is cofinitely often 0, and hence computable, and so not random.∎

We may assume that $\Phi$ infinitely often queries a bit that it has not queried before (else $\Phi^{A}$ is always computable). Without loss of generality, suppose $\Phi$ infinitely often queries an even bit it has not queried before. We construct $A$ in stages, beginning with $A_{0}=\emptyset\oplus R$ for $R$ an arbitrary random real.

For the infinitely many $n_{i}$ that query an unqueried even bit, let $v_{i}$ be the least such bit. Then at stage $s+1$, set $v_{i}=1$ if $\Phi^{A_{s}}(n_{i})=0$. Changing a single bit in a linear $\sigma_{f(n_{i})}$ changes the output of $\sigma_{f(n_{i})}$, so that $\Phi^{A}(n)=\Phi^{A_{s+1}}(n_{i})=1$.

As these $n_{i}$ form a computable set, $\Phi^{A}$ fails to be immune, and so cannot be random.∎

Suppose that $\Phi$ is a $btt$-reduction from $\operatorname{Either}(\operatorname{MLR})$ to $\operatorname{MLR}$ and let $c$ be its bound on the number of oracle bits queried. We proceed by induction on $c$, working to show that an $X=X_{0}\oplus X_{1}$ exists with $X_{0}$ or $X_{1}$ ML-random, for which $\Phi^{X}$ is not bi-immune.

If for infinitely many $n$, $f_{n}$ is the constant function $1$ or $0$, and the claim is obvious.

Instead, suppose $f_{n}$ is only constant finitely often, i.e. $f_{n}(x)=x$ or $f_{n}(x)=1-x$ cofinitely often. Without loss of generality, there are infinitely many $n$ such that $q(n)$ is even. Let $X=\emptyset\oplus R$, where $R$ is an arbitrary ML-random set.

As $X(q(n))=0$ and $f(x)$ is either identity or $1-x$ infinitely often, there is an infinite computable subset of either $\Phi^{X}$ or $\overline{\Phi^{X}}$ so $\Phi^{X}$ is not bi-immune.

Now there are uniformly computable finite sets $Q(n)=\{q_{1}(n),\dots,q_{d_{n}}(n)\}$ and Boolean functions $f_{n}:\{0,1\}^{d_{n}}\to\{0,1\}$ such that for all $n$, $\Phi^{X}(n)=f_{n}(X({q_{1}(n)}),\dots,X(q_{d_{n}}(n)))$ and $d_{n}\leq c$.

Consider the greedy algorithm that tries to find a collection of pairwise disjoint $Q(n_{i})$ as follows:

• -

  $n_{0}=0$.

• -

  $n_{i+1}$ is the least $n$ such that $Q(n)\cap\bigcup_{k<i}Q(n_{k})=\emptyset$.

If this algorithm cannot find an infinite sequence, let $i$ be least such that $n_{i+1}$ is undefined, and define $H=\bigcup_{k\leq i}Q(n_{k})$. It must be that for $n>n_{i}$ no intersection $Q(n)\cap H$ is empty. Thus there are finitely many bits that are in infinitely many of these intersections, and so are queried infinitely often. We will “hard code” the bits of $H$ as $0$ in a new function $\hat{\Phi}$.

To that end, define $\hat{Q}(n)=Q(n)\setminus H$, and let $\hat{f}$ be the function that outputs the same truth tables as $f$, but for all $n\in H$, $v_{n}$ is replaced with $\bot$. List the elements of $\hat{Q}$ in increasing order as $\{\hat{q}_{1}(n),\dots,\hat{q}_{e_{n}}(n)\}$. Now if $X\cap H=\emptyset$, any $q_{i}(n)\in H$ have $X(q_{i}(n))=0$, so that $\Phi^{X}=\hat{\Phi}^{X}$, as for every $n$,

As $Q$ and the $f_{n}$ are uniformly computable and $H$ is finite, $\hat{Q}$ and the $\hat{f}_{n}$ are also uniformly computable. As no intersection $Q(n)\cap H$ was empty, $e_{n}<d_{n}\leq c$. So $\hat{Q}$ and the $\hat{f}_{n}$ define a $btt(c-1)$-reduction. By the induction hypothesis, there is a real $A\in\operatorname{Either}(\operatorname{MLR})$ such that $\hat{\Phi}^{A}$ is not random. $\operatorname{Either}(\operatorname{MLR})$ is closed under finite differences (as $\operatorname{MLR}$ is), so the set $B=A\setminus H$ witnesses $\Phi^{B}=\hat{\Phi}^{A}$, and $\Phi^{B}$ is not random as desired.

This leaves the case where the algorithm enumerates a sequence of pairwise disjoint $Q(n_{i})$.

Say that a collection of bits $C(n)\subseteq Q(n)$ can control the computation $\Phi^{X}(n)$ if there is a way to assign the bits in $C_{n}$ so that $\Phi^{X}(n)$ is the same no matter what the other bits in $Q(n)$ are. For example, $(a\land b)\lor c$ can be controlled by $\{a,b\}$, by setting $a=b=1$. Note that if the bits in $C(n)$ are assigned appropriately, $\Phi^{X}(n)$ is the same regardless of what the rest of $X$ looks like.

Suppose now that there are infinitely many $n_{i}$ such that some $C(n_{i})$ containing only even bits controls $\Phi^{X}(n_{i})$. Collect these $n_{i}$ into a set $E$. Let $X_{1}$ be an arbitrary ML-random set. As there are infinitely many $n_{i}$, and it is computable to determine whether an assignment of bits controls $\Phi^{X}(n)$, $E$ is an infinite computable set. For $n\in E$, we can assign the bits in $Q(n)$ to control $\Phi^{X}(n)$, as the $Q(n)$ are mutually disjoint. Now one of the sets

is infinite. Both are computable, so in either case $\Phi^{X}$ is not bi-immune.

Now suppose that cofinitely many of the $n_{i}$ cannot be controlled by their even bits. Here let $X_{0}$ be an arbitrary ML-random set. For sufficiently large $n_{i}$, no matter the values of the even bits in $Q(n_{i})$, there is a way to assign the odd bits so that $\Phi^{X}(n_{i})=1$. By pairwise disjointness, we can assign the odd bits of $\bigcup Q(n_{i})$ as needed to ensure this, and assign the rest of the odd bits of $X$ however we wish. Now the $n_{i}$ witness the failure of $\Phi^{X}$ to be immune. ∎

The $\leq_{s,m}$ direction follows from the inclusion $\operatorname{Many}(\mathcal{C})\subseteq\operatorname{Some}(\mathcal{C},\omega)$.

For $\geq_{s,m}$, let $B\in\operatorname{Some}(\mathcal{C},\omega)$ and define $A$ by:

Then $A\leq_{m}B$ and $A\in\operatorname{Many}(\mathcal{C})$, so that $\operatorname{Some}(\mathcal{C},\omega)\geq_{s,m}\operatorname{Many}(\mathcal{C})$. ∎

The $\subseteq$ direction is immediate – if $A$ is random relative to some oracle, it is random relative to having no oracle, so $A\in\operatorname{MLR}$. For the reverse, let $A\in\operatorname{MLR}$. If $B\in\operatorname{MLR}^{A}$, then $A\in\operatorname{MLR}^{B}$ by van Lambalgen’s theorem. Thus $\mu\{B\mid A\in\operatorname{MLR}^{B}\}\geq\mu(\operatorname{MLR}^{A})=1$, so that $A\in\operatorname{a.e.-MLR}$.