Injective randomness-preserving one-way functions — Problem 1.5

1. George Barmpalias

The following problems concern Turing ideals generated by sufficiently random reals.

Notation 1.1.

If $\alpha\in 2^{\omega}$, let $\alpha^{(i)}$ denote the real obtained from $\alpha$ by deleting the digits $\alpha(k)$ at positions $k$ that are divisible by $2^{i}$.

A chain is a sequence $(x_{i})_{i\in\mathbb{N}}$ of reals such that

for every $i\in\mathbb{N}$.

If $B$ is a chain of reals, the Turing ideal generated by $B$ is

In particular, for a chain $(x_{i})_{i\in\mathbb{N}}$,

For each real $\alpha$, define

The notation $z\approx x$ means that $z$ and $x$ differ on finitely many bits.

The real $\bigoplus_{i}x_{i}$ is the infinite join of all the reals $x_{i}$.

Proposition 1.2 (Barmpalias–Zhang, unpublished).

If $(x_{i})_{i\in\mathbb{N}}$ is a sequence of reals and $\bigoplus_{i\leq n}x_{i}$ is random for each $n$, then there are reals $z_{i}\approx x_{i}$ so that $\bigoplus_{i}z_{i}$ is random. The same conclusion holds for $k$-randomness and weak $k$-randomness for each $k\in\mathbb{N}$.

This proposition gives a partial positive answer to Question 1(1) under the additional assumption of relative randomness. Question 1(2) asks for the stronger conclusion that the ideal generated by a random chain is exactly of the form $[\alpha]$ for some random real $\alpha$.

The class $\mathrm{ML}(\emptyset^{\prime})$ of $\emptyset^{\prime}$-random reals, equivalently the class of $2$-random reals, is a special case.

There are two obstacles to constructing such a chain. If $\alpha$ is $2$-random, then the ideal $[\alpha]$ has the following properties:

For every $x\in[\alpha]$, the ideal $[\alpha]$ contains an $x^{\prime}$-random real.

The jumps of the columns $\alpha^{(i)}$ form a chain and, in particular, are pairwise distinct.

Such a function can be used to produce a chain of $2$-random reals with the same jump in the Turing degrees.

Current research status is unassessed. The dated source poses this question; inclusion does not certify that it remains open today.