Paper detail

Computing from projections of random points: a dense hierarchy of subideals of the $K$-trivial degrees

We study the sets that are computable from both halves of some (Martin-Löf) random sequence, which we call \emph{$1/2$-bases}. We show that the collection of such sets forms an ideal in the Turing degrees that is generated by its c.e.\ elements. It is a proper subideal of the $K$-trivial sets. We characterise $1/2$-bases as the sets computable from both halves of Chaitin's $Ω$, and as the sets that obey the cost function $\mathbf c(x,s) = \sqrt{Ω_s - Ω_x}$. Generalising these results yields a dense hierarchy of subideals in the $K$-trivial degrees: For $k< n$, let $B_{k/n}$ be the collection of sets that are below any $k$ out of $n$ columns of some random sequence. As before, this is an ideal generated by its c.e.\ elements and the random sequence in the definition can always be taken to be $Ω$. Furthermore, the corresponding cost function characterisation reveals that $B_{k/n}$ is independent of the particular representation of the rational $k/n$, and that $B_p$ is properly contained in $B_q$ for rational numbers $p< q$. These results are proved using a generalisation of the Loomis--Whitney inequality, which bounds the measure of an open set in terms of the measures of its projections. The generality allows us to analyse arbitrary families of orthogonal projections. As it turns out, these do not give us new subideals of the $K$-trivial sets, we can calculate from the family which $B_p$ it characterises. We finish by showing that the the union of $B_p$ for $p<1$ is the collection of sets which are robustly computable from a random, a class previously studied by Hirschfeldt, Jockusch, Kuyper, and Schupp.