Asymptotic density and the coarse computability bound

Abstract

For $\mathit{r}\in [0\mathrm{,}1]$ we say that a set $\mathit{A}\subseteq \mathit{\omega }$ is coarsely computable at density r if there is a computable set C such that $\{\mathit{n}:\mathit{C}\mathrm{(}\mathit{n}\mathrm{)}=\mathit{A}\mathrm{(}\mathit{n}\mathrm{)}\}$ has lower density at least r. Let $\mathit{\gamma }\mathrm{(}\mathit{A}\mathrm{)}=sup\{\mathit{r}:\mathit{A}\text{is coarsely computable at density}\mathit{r}\}$ . We study the interactions of these concepts with Turing reducibility. For example, we show that if $\mathit{r}\in \mathrm{(}0\mathrm{,}1]$ there are sets ${\mathit{A}}_0$ , ${\mathit{A}}_1$ such that $\mathit{\gamma }\mathrm{(}{\mathit{A}}_0\mathrm{)}=\mathit{\gamma }\mathrm{(}{\mathit{A}}_1\mathrm{)}=\mathit{r}$ where ${\mathit{A}}_0$ is coarsely computable at density r while ${\mathit{A}}_1$ is not coarsely computable at density r. We show that a real $\mathit{r}\in [0\mathrm{,}1]$ is equal to $\mathit{\gamma }\mathrm{(}\mathit{A}\mathrm{)}$ for some c.e. set A if and only if r is left- ${\mathrm{\Sigma }}_3^0$ . A surprising result is that if G is a ${\mathrm{\Delta }}_2^0$ 1-generic set, and $\mathit{A}{⩽}_{\mathrm{T}}\mathit{G}$ with $\mathit{\gamma }\mathrm{(}\mathit{A}\mathrm{)}=1$ , then A is coarsely computable at density 1.