Asymptotic density and the coarse computability bound

Abstract

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

Keywords

Asymptotic density coarse computability Turing degrees

1. Introduction

There are two natural models of “imperfect computability” defined in terms of the standard notion of asymptotic density, which we now review. For $A \subseteq ω$ and $n \in ω ∖ {0}$ , define $ρ_{n} (A)$ , the density of A below n, by $ρ_{n} (A) = \frac{| A ↾ n |}{n}$ , where $A ↾ n = A \cap {0, 1, \dots, n - 1}$ . Then $\begin{matrix} \underline{ρ} (A) = \underset{n}{lim inf} ρ_{n} (A) and \overline{ρ} (A) = \underset{n}{lim sup} ρ_{n} (A) \end{matrix}$ are respectively the lower density of A and the upper density of A. The (asymptotic) density of A is $ρ (A) = {lim}_{n} ρ_{n} (A)$ provided the limit exists.

The idea of generic computability was introduced and studied in connection with group theory in [11] and then studied in connection with arbitrary subsets of ω in [10]. In generic computability we have a partial algorithm that is always correct when it gives an answer but may fail to answer on a set of density 0. The paper [5] began studying computability at densities less than 1 and introduced the following definitions.

Definition 1.1 ([5, Definition 5.9]).

Let A be a set of natural numbers and let r be a real number in the unit interval $[0, 1]$ . The set A is partially computable at density r if there is a partial computable function φ such that $φ (n) = A (n)$ for all n in the domain of φ and the domain of φ has lower density at least r.

Thus A is generically computable if and only if A is partially computable at density 1.

Definition 1.2 ([5, Definition 6.9]).

If $A \subseteq ω$ , the partial computability bound of A is $\begin{matrix} α (A) = sup {r : A is partially computable at density r} . \end{matrix}$

In the paper [5] the term “partially computable at density r” was simply called “computable at density r” and the “partial computability bound” was called the “asymptotic computability bound”. That paper considered only partial computability at densities less than 1, but since we are here comparing the partial computability concepts with their coarse analogs, the present terminology is more exact.

If A is generically computable, then $α (A) = 1$ . The converse fails by [5, Observation 5.10]. There are sets that are partially computable at every density less than 1 but are not generically computable.

Definition 1.3.
If $A, B \subseteq N$ , then A and B are coarsely similar, written $A ∽_{c} B$ , if the density of the symmetric difference of A and B is 0, that is, $ρ (A △ B) = 0$ . Given A, any set B such that $B ∽_{c} A$ is called a coarse description of A.

It is easy to check that coarse similarity is indeed an equivalence relation. Coarse similarity was called generic similarity in [10], but the current terminology seems better.

Coarse computability considers algorithms that always give an answer, but may give an incorrect answer on a set of density 0. We have the following definition.
Definition 1.4 ([10, Definition 2.13]).

The set A is coarsely computable if there is a computable set C such that the density of ${n : A (n) = C (n)}$ is 1. That is, A is coarsely computable if it has a computable coarse description C.

The following definitions are similar to those for partial computability.

Definition 1.5.
If $A \subseteq ω$ and $r \in [0, 1]$ , an r-description of A is any set B such that the lower density of ${n : A (n) = B (n)}$ is at least r. A set A is coarsely computable at density r if there is a computable r-description B of A.

Note that A is coarsely computable if and only A is coarsely computable at density 1.
Definition 1.6.
If $A \subseteq ω$ , the coarse computability bound of A is $\begin{matrix} γ (A) = sup {r : A is coarsely computable at density r} . \end{matrix}$

If A is coarsely computable, then $γ (A) = 1$ , but the next lemma implies that the converse fails.

It is shown in [10, Proposition 2.15 and Theorem 2.26] that neither of generic computability and coarse computability implies the other, even among c.e. sets. Nonetheless, the following lemma gives an inequality between α and γ.
Lemma 1.7.
For any $A \subseteq ω$ , $α (A) ⩽ γ (A)$ . In particular, if A is generically computable then $γ (A) = 1$ .
Proof.
Fix $ϵ > 0$ . If $α (A) = r$ then there is a partial algorithm φ for A such that the lower density of the c.e. set $D = dom φ$ is greater than or equal to $r - ϵ$ . Theorem 3.9 of [5] shows that if D is a c.e. set there is a computable set $C \subseteq D$ such that $\underline{ρ} (C) > \underline{ρ} (D) - ϵ$ . Let $C_{1} = {n \in C : φ (n) = 1}$ . Then $C_{1}$ is a computable set and ${n : A (n) = C_{1} (n)} \supseteq C$ . It follows that $\underline{ρ} ({n : A (n) = C_{1} (n)}) ⩾ \underline{ρ} (C) > \underline{ρ} (D) - ϵ ⩾ r - 2 ϵ$ , and hence A is coarsely computable at density $r - 2 ϵ$ . Since $ϵ > 0$ was arbitrary, it follows that $γ (A) ⩾ r = α (A)$ . □

One consequence of this lemma is that any set that is generically computable but not coarsely computable is an example of a set A such that $γ (A) = 1$ but A is not coarsely computable.
Definition 1.8.
If $A, B \subseteq N$ , let $D (A, B) = \overline{ρ} (A △ B)$ .

It is shown in [5, remarks after Proposition 3.2] that D is a pseudometric on subsets of ω and, since $D (A, B) = 0$ exactly when A and B are coarsely similar, D is actually a metric on the space of coarse similarity classes. Note that γ is an invariant of coarse similarity classes.

Although easy, the following is useful enough to be stated as a lemma.
Lemma 1.9.
If $A \subseteq ω$ then $\underline{ρ} (A) = 1 - \overline{ρ} (\overline{A})$ .
Proof.
Note that $ρ_{n} (A) = 1 - ρ_{n} (\overline{A})$ for all $n ⩾ 1$ . The lemma follows by taking the lim inf of both sides of this equation. □

Since we have a pseudometric space, we can consider the distance from a single point to a subset of the space in the usual way.
Definition 1.10.
If $A \subseteq ω$ and $S \subseteq P (N)$ , let $\begin{matrix} δ (A, S) = inf {D (A, S) : S \in S} . \end{matrix}$

The above lemma shows that $\begin{matrix} γ (A) = 1 - δ (A, C), \end{matrix}$ where $C$ is the class of computable sets. Thus $γ (A) = 1$ if and only if A is a limit of computable sets in the pseudometric. A set A is coarsely computable at density r if and only if $δ (A, C) ⩽ 1 - r$ .

The symmetric difference $A △ B = {n : A (n) \neq B (n)}$ is the subset of ω where A and B disagree. There does not seem to be a standard notation for the complement of $A △ B$ , which is ${n : A (n) = B (n)}$ , the “symmetric agreement” of A and B. We find it useful to use $A ▽ B$ to denote ${n : A (n) = B (n)}$ .

We assume that the reader is familiar with basic computability theory. See, for example, [14]. If S is a set of finite binary strings and $A \subseteq ω$ we say that A meets S if A extends some string in S and that A avoids S if A extends a string that has no extension in S.
2. Turing degrees, coarse computability, and γ

It is easily seen that every Turing degree contains a set that is both coarsely and generically computable and hence a set A with $α (A) = γ (A) = 1$ . In the other direction it is shown in Theorem 2.20 of [10] that every nonzero Turing degree contains a set that is neither generically computable nor coarsely computable. The same construction now yields a quantitative version of that result.

Theorem 2.1.
Every nonzero Turing degree contains a set whose partial computability bound is 0 but whose coarse computability bound is $1 / 2$ .
Proof.
Let $I_{n} = [n!, (n + 1)!)$ . Suppose that A is not computable, and let $I (A) = ⋃_{n \in A} I_{n}$ . It is clear that $I (A)$ is Turing equivalent to A. We prove first that $γ (I (A)) ⩽ \frac{1}{2}$ . If there is a computable C with $\underline{ρ} (I (A) ▽ C) > \frac{1}{2}$ we can compute A by “majority vote”. That is, for all sufficiently large n, we have that n is in A if and only if more than half of the elements of $I_{n}$ are in C. (For any n for which this equivalence fails, we have $ρ_{(n + 1)!} (I (A) ▽ C) ⩽ (1 + {(n + 1)}^{- 1}) / 2$ .) It follows that A is computable, a contradiction. If C is the set of even numbers, then it is easily seen that $ρ (C ▽ I (A)) = \frac{1}{2}$ , so $γ (I (A)) ⩾ \frac{1}{2}$ . It follows that $γ (I (A)) = \frac{1}{2}$ . To see that $α (I (A)) = 0$ , note that any set of positive lower density intersects $I_{n}$ for all but finitely many n, and apply this observation to the domain of any partial computable function that agrees with $I (A)$ on its domain. □

We next observe that a large class of degrees contain sets A with $γ (A) = 0$ .
Theorem 2.2.
Every hyperimmune degree contains a set whose coarse computability bound is 0 .
Proof.
A set $S \subseteq 2^{< ω}$ of finite binary strings is dense if every string has some extension in S. Stuart Kurtz [12] defined a set A to be weakly 1-generic if A meets every dense c.e. set S of finite binary strings and proved that the weakly 1-generic degrees coincide with the hyperimmune degrees. Hence, it suffices to show that every weakly 1-generic set A satisfies $γ (A) = 0$ . Assume that A is weakly 1-generic.

If f is a computable function then, for each $n, j > 0$ , define $\begin{matrix} S_{n, j} = {σ \in 2^{< ω} : | σ | ⩾ j and ρ_{| σ |} ({k < | σ | : σ (k) = f (k)}) < \frac{1}{n}} . \end{matrix}$ Each set $S_{n, j}$ is computable and dense so A meets each $S_{n, j}$ . Thus ${k : f (k) = A (k)}$ has lower density 0. □

In view of the preceding result, it is natural to ask whether every nonzero degree contains a set A such that $γ (A) = 0$ . This question is answered in the negative in [1] where it is shown that every computably traceable set is coarsely computable at density $\frac{1}{2}$ , and also that every set computable from a 1-random set of hyperimmune-free degree is coarsely computable at density $\frac{1}{2}$ . Each of these results implies that there is a nonzero degree $a ⩽ 0^{″}$ such that every a-computable set is coarsely computable at density $\frac{1}{2}$ . Here it is not possible to replace $\frac{1}{2}$ by any larger number, by Theorem 2.1. In [1], the following definition is made for Turing degrees a: $\begin{matrix} Γ (a) = inf {γ (A) : A is a -computable} . \end{matrix}$ By the above, Γ takes on the values 0 and $\frac{1}{2}$ , and of course $Γ (0) = 1$ . By Theorem 2.1, Γ does not take on any values in the open interval $(\frac{1}{2}, 1)$ . An open question posed in [1] is whether Γ takes on any values other than 0, $\frac{1}{2}$ , and 1.
3. Coarse computability at density $γ (A)$

If A is any set, it follows from the definition of $γ (A)$ that A is coarsely computable at every density less than $γ (A)$ and at no density greater than $γ (A)$ . What happens at $γ (A)$ ? Let us say that A is extremal for coarse computability if it is coarsely computable at density $γ (A)$ . In this section, we show that extremal and non-extremal sets exist. Moreover, we also show that every real in $(0, 1]$ is the coarse computability bound of an extremal set and of a non-extremal set. We also explore the distribution of these cases in the Turing degrees. Roughly speaking, we show that hyperimmune degrees yield extremal sets and high degrees yield non-extremal sets.

Theorem 3.1.
Every real in $[0, 1]$ is the coarse computability bound of a set that is extremal for coarse computability.
Proof.
Suppose $0 ⩽ r ⩽ 1$ . By Corollary 2.9 of [10] there is a set $A_{1}$ such that $ρ (A_{1}) = r$ . Let Z be a set with $γ (Z) = 0$ , which exists by Theorem 2.2, and let $A = A_{1} \cup Z$ . Note first that A is coarsely computable at density r via the computable set ω since $\begin{matrix} \underline{ρ} (A ▽ ω) = \underline{ρ} (A) ⩾ \underline{ρ} (A_{1}) = r . \end{matrix}$ It follows that $γ (A) ⩾ r$ , so it remains only to show that $γ (A) ⩽ r$ .

Suppose for a contradiction that $γ (A) > r$ , so A is coarsely computable at some density $r^{'} > r$ . Let C be a computable set such that $\underline{ρ} (A ▽ C) ⩾ r^{'}$ . Let: $\begin{array}{rcl} S_{1} = A_{1} \cap C, \\ S_{2} = (Z ∖ A_{1}) \cap C, \\ S_{3} = \overline{A} \cap \overline{C} . \end{array}$ Note that $A ▽ C$ is the disjoint union of $S_{1}$ , $S_{2}$ , and $S_{3}$ so $\begin{matrix} ρ_{n} (A ▽ C) = ρ_{n} (S_{1}) + ρ_{n} (S_{2}) + ρ_{n} (S_{3}) \end{matrix}$ for all n.

Let $ϵ = r^{'} - r$ . For all sufficiently large n we have $ρ_{n} (A ▽ C) > r + \frac{ϵ}{2}$ . Since $S_{1} \subseteq A_{1}$ and $ρ_{n} (A_{1}) < r + \frac{ϵ}{3}$ for all sufficiently large n, we have $ρ_{n} (S_{2}) + ρ_{n} (S_{3}) > \frac{ϵ}{6}$ for all sufficiently large n. Hence $\underline{ρ} (S_{2} \cup S_{3}) > 0$ . But $S_{2} \cup S_{3} \subseteq C ▽ Z$ so $\underline{ρ} (C ▽ Z) > 0$ , contradicting $γ (Z) = 0$ . This contradiction shows that $γ (A) ⩽ r$ , and the proof is complete. □
Corollary 3.2 (To proof).

Suppose a is a hyperimmune degree. Then, every $Δ_{2}^{0}$ real in $[0, 1]$ is the coarse computability bound of a set in a that is extremal for coarse computability.

Proof.
Just note that the proof of the theorem can be carried out effectively in a. In more detail, by Theorem 2.21 of [10] there is a computable set $A_{1}$ of density r. Further, by Theorem 2.2 there is an a-computable set Z such that $γ (Z) = 0$ . Then $A = A_{1} \cup Z$ satisfies the theorem and is a-computable. We can ensure that $A \in a$ by coding a set in a into A on a set of density 0. □

We now consider sets that are not extremal for coarse computability. We first consider the degrees of the sets A such that $γ (A) = 1$ but A is not coarsely computable.

Define $\begin{matrix} R_{n} = {k : 2^{n} ∣ k and 2^{n + 1} ∤ k} . \end{matrix}$ The sets $R_{n}$ were heavily used in [10] and [5]. Note that they are uniformly computable and pairwise disjoint, and $ρ (R_{n}) = 2^{- (n + 1)}$ . As in [10] and [5], define $\begin{matrix} R (A) = ⋃_{n \in A} R_{n} . \end{matrix}$ Note that, for all A, we have that $A \equiv_{T} R (A)$ and $α (R (A)) = γ (R (A)) = 1$ . To see the latter (which was pointed out by Asher Kach), note that if $C_{k} = ⋃ {R_{n} : n \in A and n < k}$ , then $C_{k}$ is computable and agrees with $R (A)$ on $⋃_{n < k} R_{n}$ , and the latter has density $1 - 2^{- k}$ .
Theorem 3.3.

If $a$ is a degree such that $a ≰ 0^{'}$ , then $a$ contains a set that is not coarsely computable but whose coarse computability bound is 1 .

If $a$ is a nonzero c.e. degree, then $a$ contains a c.e. set that is not coarsely computable but whose coarse computability bound is 1 .

Proof.
It is shown in Theorem 2.19 of [10] that $R (B)$ is coarsely computable if and only if B is $Δ_{2}^{0}$ . If $a ≰ 0^{'}$ and B has degree a, then $R (B)$ is a set of degree a that is not coarsely computable even though its coarse computability bound is 1. Part (i) follows.

Theorem 4.5 of [5] shows that every nonzero c.e. degree contains a c.e. set A that is generically computable but not coarsely computable. Then $α (A) = 1$ , so by Lemma 1.7, $γ (A) = 1$ . This proves part (ii). □

This result raises the natural question: Does every nonzero Turing degree contain a set A such that $γ (A) = 1$ but A is not coarsely computable? We will later obtain a negative answer in Theorem 5.12. In fact, we will show that if G is 1-generic and $Δ_{2}^{0}$ , and $A ⩽_{T} G$ has $γ (A) = 1$ , then A is coarsely computable.

We now consider the coarse computability bounds of non-extremal sets.
Theorem 3.4.
Every real in $(0, 1]$ is the coarse computability bound of a set that is not extremal for coarse computability.
Proof.
Suppose $0 < r ⩽ 1$ . We construct a set A so that $γ (A) = r$ but A is not coarsely computable at density r. As an auxiliary for defining A, we first use the technique of Corollary 2.9 of [10] to define a set S of density r. To this end, we turn r into a set B in the natural way. That is, since $r > 0$ , it has a non-terminating binary expansion $r = 0 . b_{0} b_{1} \dots$ . We then set $B = {i : b_{i} = 1}$ . By restricted countable additivity (Lemma 2.6 of [10]), $R (B)$ has density r. Set $S = R (B)$ .

We now divide S into “slices” $S_{0}, S_{1}, \dots$ as follows. Let $c_{0} < c_{1} < \dots$ be the increasing enumeration of B. Set $S_{e} = R_{c_{e}}$ . Note that the $S_{e}$ ’s are pairwise disjoint and that $S = ⋃_{e} S_{e}$ . Note also that each $S_{e}$ is computable (though not necessarily computable uniformly in e).

We now define A. We first choose a set Z so that $γ (Z) = 0$ . Such a set exists by Theorem 2.2. Let $C_{0}, C_{1}, \dots$ be an enumeration of the computable sets. We then set $\begin{matrix} A = (\overline{S} \cap Z) \cup ⋃_{e} (S_{e} \cap \overline{C_{e}}) . \end{matrix}$

We now claim that A is coarsely computable at density q whenever $0 ⩽ q < r$ . For, suppose $0 ⩽ q < r$ . Since the density of S is r, there is a number n so that $ρ (⋃_{e < n} S_{e}) ⩾ q$ . Let $C = ⋃_{e < n} (S_{e} \cap \overline{C_{e}})$ . Then, C is a computable set. Also A and C agree on each $S_{e}$ for $e < n$ , so $\underline{ρ} (A ▽ C) ⩾ \underline{ρ} (⋃_{e < n} S_{e}) ⩾ q$ . Hence, C witnesses that A is coarsely computable at density q.

To complete the proof, it suffices to show that A is not coarsely computable at density r. To this end, it suffices to show that the lower density of $A ▽ C_{e}$ is smaller than r for each e. Fix $e \in N$ . By construction, $(A ▽ C_{e}) \cap S$ is disjoint from $S_{e}$ and so has upper density less than r. At the same time, note that $(A ▽ C_{e}) \cap \overline{S} \subseteq C_{e} ▽ Z$ . Since $γ (Z) = 0$ , it follows that for each $ϵ > 0$ there are infinitely many n such that $ρ_{n} ((A ▽ C_{e}) \cap \overline{S}) < ϵ / 3$ , as we will use below. Let $r_{0} = \overline{ρ} ((A ▽ C_{e}) \cap S)$ , and let $ϵ = r - r_{0}$ . Then for infinitely many n we have $\begin{matrix} ρ_{n} (A ▽ C_{e}) = ρ_{n} ((A ▽ C_{e}) \cap S) + ρ_{n} ((A ▽ C_{e}) \cap \overline{S}) < (r_{0} + \frac{ϵ}{2}) + \frac{ϵ}{3} < r . \end{matrix}$ It follows that $\underline{ρ} (A ▽ C_{e}) < r$ . Hence A is not coarsely computable at density r, which completes the proof. □
Corollary 3.5 (To proof).

Suppose a is a high degree. Then, every computable real in $(0, 1]$ is the coarse computability bound of a set in a that is not extremal for coarse computability.

Proof.
We just observe that the preceding proof can be carried out in an a-computable fashion. By Theorem 1 of [9], there is a listing $C_{0}, C_{1}, \dots$ of the computable sets that is uniformly a-computable. Also, since r is computable, the sequence $S_{0}, S_{1}, \dots$ in the proof of the theorem is also uniformly a-computable. Each $S_{e}$ contains only multiples of $2^{e}$ and hence only numbers exceeding $2^{e}$ . It follows that $S = ⋃_{e} S_{e}$ is a-computable. Finally, every high degree is hyperimmune by a result of D.A. Martin [13], and so every high degree computes a set Z with $γ (Z) = 0$ by Theorem 2.2. Hence the set A defined in the proof of the theorem can be chosen to be a-computable. By coding a set in a into A on a set of density 0 we can ensure that $A \in a$ . □

By using suitable computable approximations, the previous corollary can be extended from computable reals to $Δ_{2}^{0}$ reals. We omit the details.

It was shown in Theorem 4.5 of [5] that every nonzero c.e. degree contains a c.e. set that is generically computable but not coarsely computable. It follows at once from Lemma 1.7 that every nonzero c.e. degree contains a c.e. set A such that $γ (A) = 1$ but A is not coarsely computable. We now use the method of Theorem 3.4 to extend this result to the case where $γ (A)$ is a given computable real. Theorem 3.6.
Suppose a is a nonzero c.e. degree. Then, every computable real in $(0, 1]$ is the coarse computability bound and the partial computability bound of a c.e. set in a that is not extremal for coarse computability.
Proof.
Define the sets $S, S_{0}, S_{1}, \dots$ as in the proof of Theorem 3.4 so that $S = ⋃_{e} S_{e}$ and so that $ρ (S) = r$ . Let B be a c.e. set of degree a, and let ${B_{s}}$ be a computable enumeration of B. We construct the desired set $A ⩽_{T} B$ using ordinary permitting; i.e. if $x \in A_{s + 1} ∖ A_{s}$ , then there exists $y ⩽ x$ such that $y \in B_{s + 1} ∖ B_{s}$ . To ensure that $B ⩽_{T} A$ , we code B into A on a set of density zero.

Let the requirement $N_{e}$ assert that if $Φ_{e}$ is total, then the lower density of the set on which it agrees with A is smaller than r. Thus, if $N_{e}$ is met for every e, then A is not coarsely computable at density r. We meet $N_{e}$ by appropriately defining A on $S_{e}$ and on $\overline{S}$ . If $Φ_{e}$ is total, we meet $N_{e}$ by making A completely disagree with $Φ_{e}$ on infinitely many large finite sets $I \subseteq S_{e} \cup \overline{S}$ . To this end, we effectively choose finite sets $I_{e, i}$ such that the following hold for all e, i, $e^{'}$ , and $i^{'}$ :
$I_{e, i} \subseteq (S_{e} \cup \overline{S})$ .

$min I_{e, i + 1} > max I_{e, i}$ .

$ρ_{m} (I_{e, i}) ⩾ \frac{i}{i + 1} ρ_{m} (S_{e} \cup \overline{S})$ where $m = max I_{e, i} + 1$ .

If $(e, i) \neq (e^{'}, i^{'})$ , then $I_{e, i} \cap I_{e^{'}, i^{'}} = \emptyset$ .

The sets $I_{e, i}$ may be obtained by intersecting appropriately large intervals with $S_{e} \cup \overline{S}$ while preserving pairwise disjointness, and we will call the sets $I_{e, i}$ “intervals”. During the construction we will designate an interval $I_{e, i}$ as “successful” if we have ensured that $Φ_{e}$ and A totally disagree on $I_{e, i}$ . The construction is as follows:

Stage 0. Let $A_{0} = \emptyset$ .

Stage $s + 1$ . For each $e, i ⩽ s$ , declare $I_{e, i}$ to be successful if it has not yet been declared successful and if the following conditions are met.
$Φ_{e, s}$ is defined on all elements of $I_{e, i}$ .

$min (I_{e, i})$ exceeds all elements of $A_{s} \cap S_{e}$ .

At least one number in $B_{s + 1} ∖ B_{s}$ is less than or equal to $min (I_{e, i})$ .
If $I_{e, i}$ is declared to be successful at stage $s + 1$ , then enumerate into A all $x \in I_{e, i}$ with $Φ_{e} (x) = 0$ .

The set A is clearly c.e., and $A ⩽_{T} B$ by ordinary permitting. If the interval $I_{e, i}$ is ever declared to be successful, then A and $Φ_{e}$ totally disagree on $I_{e, i}$ , by the action taken when it is declared successful and the disjointness condition (iv), which ensures that no elements of $I_{e, i}$ are enumerated into A except by this action.

Note that (2) ensures that $A \cap S_{e}$ is computable for each e. It follows that $γ (A) ⩾ α (A) ⩾ r$ as in the proof of Theorem 3.4.

It remains to show that every requirement $N_{e}$ is met. Suppose that $Φ_{e}$ is total. We claim first that the interval $I_{e, i}$ is declared successful for infinitely many i. Suppose not. Then $A \cap S_{e}$ is finite. It follows that B is computable, since, for all sufficiently large i, if $s ⩾ i$ and $Φ_{e, s}$ is defined on all elements of $I_{e, i}$ , then no number less than $min (I_{e, i})$ enters B after stage s. Since we assumed that B is noncomputable, the claim follows.

Suppose $I_{e, i}$ is successful. Set $I = I_{e, i}$ . Then $A △ Φ_{e} \supseteq I$ , so $\begin{matrix} ρ_{m} (A △ Φ_{e}) ⩾ ρ_{m} (I) ⩾ \frac{i}{i + 1} ρ_{m} (S_{e} \cup \overline{S}), \end{matrix}$ where $m = max I_{e, i} + 1$ . There are infinitely many such i’s, and as i tends to infinity, the right-hand side of the above inequality tends to $ρ (S_{e}) + ρ (\overline{S})$ . It follows that $\overline{ρ} (A △ Φ_{e}) ⩾ ρ (S_{e}) + (1 - r)$ , and so by Lemma 1.9, $\underline{ρ} (A ▽ Φ_{e}) ⩽ r - ρ (S_{e}) < r$ , as needed to complete the proof. □

4. Coarse computability and lowness

We now consider the coarse computability properties of c.e. sets that have a density.

Proposition 4.1.
Every low c.e. set having a density is coarsely computable. Every c.e. set having a density has coarse computability bound 1 .
Proof.
The first statement is Corollary 3.16 of [5]. Let A be a c.e. set that has a density and let $ϵ > 0$ . Theorem 3.9 of [5] shows that A has a computable subset C such that $\underline{ρ} (C) > ρ (A) - ϵ$ . Then $C △ A = A ∖ C$ . Hence, by Lemma 1.9, $\underline{ρ} (A ▽ C) = 1 - \overline{ρ} (A ∖ C)$ . But by Lemma 3.3(iii) of [5], $\begin{matrix} \overline{ρ} (A ∖ C) ⩽ ρ (A) - \underline{ρ} (C) < ϵ . \end{matrix}$ Hence $\underline{ρ} (A ▽ C) > 1 - ϵ$ . Since $ϵ > 0$ was arbitrary, we conclude that $γ (A) = 1$ . □

The next result shows that the lowness assumption is strongly required in the first part of Proposition 4.1.
Theorem 4.2.
Every nonlow c.e. Turing degree a contains a c.e. set of density $1 / 2$ that is not coarsely computable.
Proof.
The proof of the theorem is similar to the proof in Theorem 4.3 of [5] that every nonlow c.e. degree contains a c.e. set A such that $ρ (A) = 1$ but A has no computable subset of density 1. Hence we give only a sketch. Let C be a c.e. set of degree a. We ensure that $A ⩽_{T} C$ by a slight variation of ordinary permitting: If x enters A at stage s, then either some number $y ⩽ x$ enters C at s or $x = s$ . This implies that $A ⩽_{T} C$ , and by coding C into A on a set of density 0 we can ensure that $A \equiv_{T} C$ without disturbing the other desired properties of A.

To ensure that $ρ (A) = \frac{1}{2}$ , we arrange that $ρ (A \cap R_{n}) = \frac{ρ (R_{n})}{2}$ for all n. Then by restricted countable additivity (Lemma 2.6 of [10]), $\begin{matrix} ρ (A) = \sum_{n} ρ (A \cap R_{n}) = \sum_{n} \frac{ρ (R_{n})}{2} = \frac{\sum_{n} ρ (R_{n})}{2} = \frac{1}{2} . \end{matrix}$ Let $R_{n}$ be listed in increasing order as $r_{n, 0}, r_{n, 1}, \dots$ . We require that, for all n and all sufficiently large k, exactly one of $r_{n, 2 k}$ and $r_{n, 2 k + 1}$ is in A. This clearly implies that $ρ (A \cap R_{n}) = \frac{ρ (R_{n})}{2}$ .

Let $N_{e}$ be the requirement that $\overline{ρ} (A △ Φ_{e}) > 0$ if $Φ_{e}$ is total. So, if $N_{e}$ is met, then A is not coarsely computable via $Φ_{e}$ . We will define a ternary computable function $g (e, i, s)$ to help us meet this requirement by “threatening” to witness that C is low. Let $N_{e, i}$ be the requirement that either $N_{e}$ is met or $C^{'} (i) = {lim}_{s} g (e, i, s)$ . Since C is not low, to meet $N_{e}$ it suffices to meet all of its subrequirements $N_{e, i}$ . Let $R_{e, i}$ denote $R_{⟨ e, i ⟩}$ . We use $R_{e, i}$ to meet $N_{e, i}$ .

Fix e, i. Our module for satisfying $N_{e, i}$ proceeds as follows. Let $s_{0}$ be the least number so that $Φ_{i, s_{0}}^{C_{s_{0}}} (i) ↓$ ; if there is no such number, then let $s_{0} = \infty$ . For each $s < s_{0}$ , let $g (e, i, s) = 0$ and put s into A if s is of the form $r_{⟨ e, i ⟩, 2 k}$ for some k. If $s_{0}$ is infinite, that is if the search for $s_{0}$ fails, then no other work is done on $N_{e, i}$ . (Note that in this case ${lim}_{s} g (e, i, s) = 0 = C^{'} (i)$ , so $N_{e, i}$ is met.) Suppose $s_{0}$ is finite (that is, the search for $s_{0}$ succeeds). We choose an interval $I_{0} \subseteq R_{e, i}$ as follows. Let $I_{0}$ be of the form ${r_{⟨ e, i ⟩, 2 j}, \dots, r_{⟨ e, i ⟩, 2 k + 1}}$ so that $min (I_{0}) > s_{0}$ and so that $ρ_{m} (I_{0}) ⩾ ρ_{m} (R_{e, i}) / 2$ where $m = r_{⟨ e, i ⟩, 2 k + 1} + 1$ . Let $u_{0}$ be the use of the computation $Φ_{i, s_{0}}^{C_{s_{0}}} (i)$ . Note that $u_{0} < s_{0}$ by a standard convention and that no element of $I_{0}$ has been enumerated in A. We then restrain all elements of $I_{0}$ from entering A but continue putting alternate elements of $R_{e, i}$ above $max I_{0}$ into A as before.

We then continue by searching for the least number $s_{1} > s_{0}$ so that $Φ_{e, s_{1}} (x) ↓$ for every $x \in I_{0}$ or some number less than $u_{0}$ is enumerated into C at stage $s_{1}$ . If no such number $s_{1}$ exists, then let $s_{1} = \infty$ . Set $g (e, i, s) = 0$ whenever $s_{0} ⩽ s < s_{1}$ . If $s_{1}$ is infinite, then no other work is done on $N_{e, i}$ . (In this case, $N_{e}$ is met because $Φ_{e}$ is not total.) Suppose $s_{1}$ is finite (that is, this search succeeds). There are two cases. First, suppose some number less than $u_{0}$ is enumerated in C at stage $s_{1}$ . We then have permission from C to enumerate numbers in $I_{0}$ into A. Accordingly, we cancel the restraint on $I_{0}$ and put $r_{⟨ e, i ⟩, 2 j^{'}}$ into A whenever $j ⩽ j^{'} ⩽ k$ . In this case the interval $I_{0}$ has become useless to us, and we go back to our first step but now starting at stage $s_{1}$ . If we find a stage $s_{2} ⩾ s_{1}$ with $Φ_{i, s_{2}}^{C_{s_{2}}} (i) ↓$ , say with use $u_{1}$ , we choose a new interval $I_{1}$ of the same form as before, but now with $min (I_{1}) > s_{2}$ and proceed as before with $I_{1}$ in place of $I_{0}$ , and setting $g (e, i, s) = 0$ for $s_{1} ⩽ s < s_{2}$ .

Now, suppose no number smaller than $u_{0}$ is enumerated into C at $s_{1}$ . Then, $Φ_{e, s_{1}} (x) ↓$ for all $x \in I_{0}$ . We are now in a position to make progress on $N_{e}$ provided that C later permits us to change A on $I_{0}$ . We then search for the least number $s_{2} ⩾ s_{1}$ so that some number less than $u_{0}$ is enumerated in C at stage $s_{2}$ . If there is no such number then let $s_{2} = \infty$ . We set $g (e, i, s) = 1$ whenever $s_{1} ⩽ s < s_{2}$ in order to force C to give us the desired permission. If $s_{2}$ is infinite, then no other work is done on $N_{e, i}$ . (In this case, we have ${lim}_{s} g (e, i, s) = 1 = C^{'} (i)$ .) Suppose $s_{2}$ is finite (that is, this search succeeds). We then declare the interval $I_{0}$ to be successful and cancel the restraint on $I_{0}$ . Since a number smaller than $u_{0} < min (I_{0})$ has now entered C, we have permission to enumerate elements of $I_{0}$ into A. So, for each $j ⩽ j^{'} ⩽ k$ put exactly one of $r_{⟨ e, i ⟩, 2 j^{'}}$ , $r_{⟨ e, i ⟩, 2 j^{'} + 1}$ into A so that A and $Φ_{e}$ differ on at least one of these numbers. (This ensures that at least half of the elements of $I_{0}$ are in $A △ Φ_{e}$ and hence that $ρ_{m} (A △ Φ_{e}) > \frac{ρ_{m} (R_{e, i})}{4}$ where $m = max I_{0} + 1$ .) We now restart our process as above. We continue in this fashion, defining a sequence of intervals. Note that, in general, $g (e, i, s) = 1$ if at stage s the most recently chosen interval has been declared successful and we are awaiting a C-change below it, and otherwise $g (e, i, s) = 0$ .

This strategy clearly succeeds if any of its searches fail, by the parenthetical remarks in the construction. Also, if there are infinitely many successful intervals, it ensures that $\overline{ρ} (A △ Φ_{e}) ⩾ \frac{ρ (R_{e, i})}{4} > 0$ , so $N_{e}$ is met. If all searches are successful but there are only finitely many successful intervals, then $C^{'} (i) = 0 = {lim}_{s} g (e, i, s)$ and $N_{e, i}$ is met. Only finitely many elements of $R_{e, i}$ are permanently restrained from entering A (namely the elements of the final interval, if any), so $ρ (A) = \frac{1}{2}$ for reasons already given. □

We now obtain the following from Proposition 4.1 and Theorem 4.2.
Corollary 4.3.
If a is a c.e. degree, then a is low if and only if every c.e. set in a that has a density is coarsely computable.

For an application of this result to a degree structure arising from the notion of coarse computability, see Hirschfeldt, Jockusch, Kuyper, and Schupp [6].
5. Density, 1-genericity, and randomness

As we have already mentioned, it is easily seen that every degree contains a set that is both coarsely computable and generically computable, and every nonzero degree contains a set with neither of these properties. On the other hand, the next two results show that for “most” degrees a, every a-computable set that is generically computable is also coarsely computable. A set A is called 1-generic if for every c.e. set S of binary strings, A either meets or avoids S.

Theorem 5.1.
Let A be a 1-generic set and let $r \in [0, 1]$ . Suppose that $B ⩽_{T} A$ and B is partially computable at density r. Then B is coarsely computable at density r.
Proof.
Fix a Turing functional Φ with $B = Φ^{A}$ and a partial computable function φ such that $φ (n) = B (n)$ for all n in the domain of φ, and $\underline{ρ} (dom φ) ⩾ r$ . Let $\begin{matrix} S = {σ \in 2^{< ω} : Φ^{σ} is incompatible with φ} . \end{matrix}$ Then S is a c.e. set of strings so A either meets or avoids S. If A meets S, then B disagrees with φ on some argument, a contradiction. Hence A avoids S. Fix a string $γ ≺ A$ such that no string extending γ is in S. Now define a computable set C as follows. Given n, search for a string σ extending γ such that $Φ^{σ} (n) ↓$ and put $C (n) = Φ^{σ} (n)$ for the first such σ that is found. Then C is total because A extends γ and $Φ^{A}$ is total. Hence C is a computable set. Further, if $φ (n) ↓$ then $B (n) = C (n)$ since no extension of γ is in S. Hence $C ▽ B \supseteq dom φ$ , so $\underline{ρ} (C ▽ B) ⩾ r$ , and hence B is coarsely computable at density r. □
Corollary 5.2.
If A is 1-generic and $B ⩽_{T} A$ is generically computable, then B is coarsely computable.

We do not need the definition of n-randomness here, but we simply point out the easy result that if A is 1-random, then $γ (A) = \frac{1}{2}$ . A set A is called weakly n-random if A does not belong to any $Π_{n}^{0}$ class of measure 0.
Theorem 5.3.

If A is weakly 1-random, $B ⩽_{tt} A$ , and B is partially computable at density r, then B is coarsely computable at density r.

If A is weakly 2-random, $B ⩽_{T} A$ , and B is partially computable at density r, then B is coarsely computable at density r.

Proof.
To prove (i), fix a Turing functional Φ such that $B = Φ^{A}$ and $Φ^{X}$ is total for all $X \subseteq ω$ . Let φ be a partial computable function that witnesses that B is partially computable at density r, and define $\begin{matrix} P = {X : Φ^{X} is compatible with φ} . \end{matrix}$ Then P is a $Π_{1}^{0}$ class and $A \in P$ , so $μ (P) > 0$ , where μ is Lebesgue measure. By the Lebesgue density theorem, there is a string γ such that $\frac{μ (P \cap [γ])}{μ ([γ])} > \frac{1}{2}$ , where $[γ] = {X \in 2^{ω} : γ ≺ X}$ . Define $\begin{matrix} C = {n : \frac{μ ({Z ≻ γ : Φ^{Z} (n) = 1})}{μ ([γ])} ⩾ \frac{1}{2}} . \end{matrix}$ Then it is easily seen that C is a computable set and $C ▽ B$ contains the domain of φ, so B is coarsely computable at density r.

To prove (ii), fix a Turing functional Φ with $B = Φ^{A}$ and fix a partial computable function φ that witnesses that B is partially computable at density r. Define $\begin{matrix} P = {X : Φ^{X} is total and compatible with φ} . \end{matrix}$ Then P is a $Π_{2}^{0}$ class and $A \in P$ , so $μ (P) > 0$ . Then for notational convenience assume that $μ (P) > \frac{2}{3}$ , applying the Lebesgue density theorem as in part (a). It follows that for every n there exists $i ⩽ 1$ such that $μ ({X : Φ^{X} (n) = i}) ⩾ \frac{1}{3}$ . Given n, one can compute such an i effectively, and then put n into C if and only if $i = 1$ . One can easily check that C is computable and $C ▽ B \supseteq dom φ$ , so $\underline{ρ} (C ▽ B) ⩾ \underline{ρ} (dom φ) ⩾ r$ . Hence B is coarsely computable at density r. □

Note that 1-randomness does not suffice in part (ii) of the above theorem, since every set is computable from some 1-random set.

Since the 1-generic sets are comeager and the weakly 2-random sets have measure 1, it follows from the last two theorems that generic computability implies coarse computability below almost every set, both in the sense of Baire category and in the sense of measure. The next result, due to Igusa [7], shows that the situation is entirely different for the converse implication.
Theorem 5.4 (Igusa [7, Proposition 2.4]).

For every degree $a > 0$ there is an a-computable set B such that B has density 1 but B has no c.e. subset of density 1. Hence, every nonzero degree computes a set that is coarsely computable but not generically computable.

The next result has a stronger hypothesis and a stronger conclusion.

Theorem 5.5.
If the degree a is hyperimmune, there is an a-computable set B such that B is of density 1 and is bi-immune.

We omit the proof, which is an easy variation of Jockusch’s proof in [8, Theorem 3] that every hyperimmune set computes a bi-immune set.

Bienvenu, Day, and Hölzl [2] proved the beautiful theorem that every nonzero Turing degree contains an absolutely undecidable set A; that is, a set such that every partial computable function that agrees with A on its domain has a domain of density 0. Of course, absolutely undecidable sets fail badly to be generically computable. We now consider the degrees of sets that are both absolutely undecidable and coarsely computable.
Corollary 5.6.
In the sense of Lebesgue measure, almost every set A computes a set B that is absolutely undecidable and coarsely computable.
Proof.
D.A. Martin (see [3, Theorem 8.21.1]) proved that almost every set has hyperimmune degree. It is obvious that every bi-immune set is absolutely undecidable. □

On the other hand, Igusa has proved the following theorem using forcing with computable perfect trees.
Theorem 5.7 (Igusa, private communication).

There is a noncomputable set A such that no set $B ⩽_{T} A$ is both coarsely computable and absolutely undecidable.

We now turn to studying the degrees of sets A such that $γ (A) = 1$ but A is not coarsely computable. As shown in Theorem 3.3, if either $a ≰ 0^{'}$ or a is a nonzero c.e. degree, then a contains such a set. This observation might lead one to conjecture that every nonzero degree computes such a set, but we shall prove the opposite for $Δ_{2}^{0}$ 1-generic degrees. We will reach this result by first considering sets for which $γ (A) = 1$ is witnessed constructively.

Definition 5.8.
We say that $γ (A) = 1$ constructively if there is a uniformly computable sequence of computable sets $C_{0}, C_{1}, \dots$ such that $\overline{ρ} (A △ C_{n}) < 2^{- n}$ for all n.

Of course, if A is coarsely computable, then $γ (A) = 1$ constructively. Although the converse appears unlikely, it was proved by Joe Miller.
Theorem 5.9 (Joe Miller, private communication).

If $γ (A) = 1$ constructively, then A is coarsely computable.

Proof.
We present Miller’s proof in essentially the form in which he gave it. Let $I_{k}$ be the interval $[2^{k} - 1, 2^{k + 1} - 1)$ . For any set C, let $d_{k} (C)$ be the density of C on $I_{k}$ , so $d_{k} (C) = \frac{| C \cap I_{k} |}{2^{k}}$ . The following lemma, which will also be useful in the proof of Theorem 5.12, relates $\overline{ρ} (C)$ to $\overline{d} (C)$ , where $\overline{d} (C) = {lim sup}_{k} d_{k} (C)$ . Lemma 5.10.
For every set C, $\begin{matrix} \frac{\overline{d} (C)}{2} ⩽ \overline{ρ} (C) ⩽ 2 \overline{d} (C) . \end{matrix}$
Proof.
For all k, $\begin{matrix} d_{k} (C) = \frac{| C \cap I_{k} |}{2^{k}} ⩽ \frac{| C ↾ (2^{k + 1} - 1) |}{2^{k}} ⩽ 2 ρ_{2^{k + 1} - 1} (C) . \end{matrix}$ Dividing both sides of this inequality by 2 and then taking the lim sup of both sides yields that $\frac{\overline{d} (C)}{2} ⩽ \overline{ρ} (C)$ .

To prove that $\overline{ρ} (C) ⩽ 2 \overline{d} (C)$ , assume that $k - 1 \in I_{n}$ , so $2^{n} ⩽ k < 2^{n + 1}$ . Then $\begin{matrix} ρ_{k} (C) = \frac{| C ↾ k |}{k} ⩽ \frac{| C ↾ (2^{n + 1} - 1) |}{2^{n}} = \frac{\sum_{0 ⩽ i ⩽ n} 2^{i} d_{i} (C)}{2^{n}} < 2 max_{i ⩽ n} d_{i} (C) . \end{matrix}$

Let $ϵ > 0$ be given. Then $d_{i} (C) < \overline{d} (C) + ϵ$ for all sufficiently large i. Hence there is a finite set F such that $d_{i} (C ∖ F) < \overline{d} (C ∖ F) + ϵ$ for all i. Then, by the above inequality applied to $C ∖ F$ , we have $ρ_{k} (C ∖ F) < 2 (\overline{d} (C ∖ F) + ϵ)$ for all k, so $\overline{ρ} (C ∖ F) ⩽ 2 \overline{d} (C ∖ F)$ . As $\overline{ρ}$ and $\overline{d}$ are invariant under finite changes of their arguments and $ϵ > 0$ is arbitrary, it follows that $\overline{ρ} (C) ⩽ 2 \overline{d} (C)$ . □

We now complete the proof of Theorem 5.9. Let the sequence $C_{n}$ witness that $γ (A) = 1$ constructively, so ${C_{n}}$ is uniformly computable and $\overline{ρ} (A △ C_{n}) < 2^{- n}$ for all n. It follows from the lemma that $\overline{d} (A △ C_{n}) < 2^{- n + 1}$ . Hence, for each n, if k is sufficiently large, we have $d_{k} (A △ C_{n}) < 2^{- n + 1}$ .

For $m < n$ , we say that $C_{m}$ trusts $C_{n}$ on $I_{k}$ if $d_{k} (C_{n} △ C_{m}) < 2^{- m + 2}$ . We say that $C_{n}$ is trusted on $I_{k}$ if $C_{m}$ trusts $C_{n}$ for all $m < n$ . Note that $C_{0}$ is trusted on every interval $I_{k}$ . We now define a computable set C that will witness that A is coarsely computable. For each k, let $N ⩽ k$ be maximal such that $C_{N}$ is trusted on $I_{k}$ , and let $C ↾ I_{k} = C_{N} ↾ I_{k}$ .

We claim that $ρ (A △ C) = 0$ . Fix n. Let $k ⩾ n$ be large enough that $d_{k} (A △ C_{m}) < 2^{- m + 1}$ for all $m ⩽ n$ . Then $d_{k} (C_{n} △ C_{m}) ⩽ d_{k} (A △ C_{n}) + d_{k} (A △ C_{m}) < 2^{- m + 1} + 2^{- n + 1} < 2^{- m + 2}$ for all $m < n$ . Therefore, $C_{n}$ is trusted on $I_{k}$ . Hence $C ↾ I_{k} = C_{N} ↾ I_{k}$ for some $N ⩾ n$ such that $C_{N}$ is trusted on $I_{k}$ . Therefore, $C_{n}$ trusts $C_{N}$ on $I_{k}$ , so $d_{k} (C_{n} △ C_{N}) < 2^{- n + 2}$ . It follows that $d_{k} (A △ C) = d_{k} (A △ C_{N}) ⩽ d_{k} (A △ C_{n}) + d_{k} (C_{n} △ C_{N}) < 2^{- n + 1} + 2^{- n + 2} < 2^{- n + 3}$ . Because this is true for every sufficiently large k, we have $\overline{d} (A △ C) ⩽ 2^{- n + 3}$ . Since n was arbitrary, it follows that $\overline{d} (A △ C) = 0$ and hence, by the lemma, $ρ (A △ C) = 0$ . Thus A is coarsely computable. □
Corollary 5.11.
Suppose there is a $0^{'}$ -computable function f such that, for all e, we have that $Φ_{f (e)}$ is total and ${0, 1}$ -valued, and $\overline{ρ} (A △ Φ_{f (e)}) ⩽ 2^{- e}$ . Then A is coarsely computable.
Proof.
By the theorem, it suffices to show that $γ (A) = 1$ constructively. Let g be a computable function such that $f (e) = {lim}_{s} g (e, s)$ . We now define a computable function h such that, for all e, we have that $Φ_{h (e)}$ is total and differs on only finitely many arguments from $Φ_{f (e)}$ , so that $Φ_{h (0)}, Φ_{h (1)}, \dots$ witnesses that $γ (A) = 1$ constructively. To compute $Φ_{h (e)} (n)$ , search for $s ⩾ n$ such that $Φ_{g (e, s)} (n)$ converges in at most s many steps, and let $Φ_{h (e)} (n) = Φ_{g (e, s)} (n)$ . The s-m-n theorem gives us such an h, and clearly h has the desired properties. □

We now have the tools to prove the following result, which we did not initially expect to be true. Theorem 5.12.
Let G be a $Δ_{2}^{0}$ 1-generic set, and suppose that $A ⩽_{T} G$ and $γ (A) = 1$ . Then A is coarsely computable.
Proof.
Fix Φ such that $A = Φ^{G}$ . As in the proof of Theorem 5.9 let $I_{k}$ be the interval $[2^{k} - 1, 2^{k + 1} - 1)$ and define $d_{k} (C) = \frac{| C ↾ I_{k} |}{2^{k}}$ and $\overline{d} (C) = {lim sup}_{k} d_{k} (C)$ .

Consider first the case that for some $ϵ > 0$ and for every computable set C and every number k, we have that G meets the set $S_{ϵ, C, k}$ of strings defined below: $\begin{matrix} S_{ϵ, C, k} = {ν : (\exists l > k) [d_{l} (Φ^{ν} △ C) ⩾ ϵ]} . \end{matrix}$

Of course, ν must be such that $Φ^{ν} (j) ↓$ for all $j \in I_{l}$ for the above to make sense. We claim that $γ (A) < 1$ in this case, so that this case cannot arise. Let C be a computable set and fix ϵ as in the case hypothesis. Then, for every k there exists $l > k$ such that $d_{l} (A △ C) ⩾ ϵ$ by the choice of ϵ. It follows that $\overline{d} (A △ C) ⩾ ϵ$ , so $\overline{ρ} (A △ C) ⩾ \frac{ϵ}{2}$ by Lemma 5.10. By Lemma 1.9 it follows that $\underline{ρ} (A ▽ C) ⩽ 1 - \frac{ϵ}{2}$ . Hence $γ (A) ⩽ 1 - \frac{ϵ}{2} < 1$ . Since $γ (A) = 1$ by assumption, this case cannot arise.

Since G is 1-generic, it follows that for every n there is a computable set C and a number k such that G avoids $S_{2^{- (n + 2)}, C, k}$ ; i.e., there exists $γ ≺ G$ such that γ has no extension in $S_{2^{- (n + 2)}, C, k}$ . Given $l > k$ , let $ν_{0}$ and $ν_{1}$ be strings extending γ such that $Φ^{ν_{i}} (x) ↓$ for all $x \in I_{l}$ and $i ⩽ 1$ . Then $\begin{matrix} d_{l} (Φ^{ν_{0}} △ Φ^{ν_{1}}) ⩽ d_{l} (Φ^{ν_{0}} △ C) + d_{l} (C △ Φ^{ν_{1}}) < 2^{- (n + 2)} + 2^{- (n + 2)} = 2^{- (n + 1)} . \end{matrix}$ Since G is $Δ_{2}^{0}$ , using an oracle for $0^{'}$ we can find $γ_{n} ≺ G$ and $k_{n}$ such that for all $ν_{0}$ , $ν_{1}$ extending $γ_{n}$ and all $l > k_{n}$ , if $Φ^{ν_{i}} (x) ↓$ for all $x \in I_{l}$ and $i ⩽ 1$ then $d_{l} (Φ^{ν_{0}} △ Φ^{ν_{1}}) ⩽ 2^{- (n + 1)}$ . Note that if we take $ν_{0} ≺ G$ then $d_{l} (Φ^{ν_{1}} △ A) < 2^{- (n + 1)}$ .

For each n, define a computable set $B_{n}$ as follows. On each interval $I_{k}$ search for $ν_{1} ≽ γ_{n}$ such that $Φ^{ν_{1}}$ converges on $I_{k}$ . Note that such a $ν_{1}$ exists because $γ_{n} ≺ G$ and $Φ^{G}$ is total. Let $B_{n} ↾ I_{k} = Φ^{ν_{1}} ↾ I_{k}$ . Then $B_{n}$ is a computable set, since the only non-effective part of its definition is the use of the single string $γ_{n}$ . Furthermore, an index for $B_{n}$ as a computable set can be effectively computed from $γ_{n}$ and hence from $0^{'}$ .

We claim that $\overline{ρ} (B_{n} △ A) ⩽ 2^{- n}$ . Fix n. By Lemma 5.10, it suffices to show that $\overline{d} (B_{n} △ A) ⩽ 2^{- (n + 1)}$ . For all k, we have that $d_{k} (B_{n} △ A) = d_{k} (Φ^{ν_{1}} △ A)$ for some string $ν_{1}$ extending $γ_{n}$ . Hence, if k is sufficiently large, it follows that $d_{k} (B_{n} △ A) ⩽ 2^{- n + 1}$ , and hence $\overline{d} (B_{n} △ A) ⩽ 2^{- (n + 1)}$ , so $\overline{ρ} (B_{n} △ A) ⩽ 2^{- n}$ . It now follows from Corollary 5.11 with $Φ_{f (e)} = B_{e}$ that A is coarsely computable. □

6. Further results

In this section we investigate the complexity of $γ (A)$ as a real number when A is c.e. and look at the distribution of values of $γ (B)$ as B ranges over all sets computable from a given set A. A real r is left- $Σ_{3}^{0}$ if ${q \in Q : q < r}$ is $Σ_{3}^{0}$ .

Proposition 6.1.

If A is a c.e. set, then $γ (A)$ is a left- $Σ_{3}^{0}$ real.

Proof.

Let A be a c.e. set, and let q be a rational number. Then the following two statements are equivalent:

$q < γ (A)$ .

There is a computable set C and a rational number $r > q$ such that $ρ_{n} (A ▽ C) ⩾ r$ for all sufficiently large n.

It is immediate that (ii) implies (i) since (ii) implies that A is coarsely computable at density r and so $q < r ⩽ γ (A)$ .

Now assume (i) in order to prove (ii). Let r and s be rational numbers with $q < r < s < γ (A)$ . Then A is coarsely computable at density s, so there is a computable set C such that $A ▽ C$ has lower density at least s. Since $r < s$ , it follows that $ρ_{n} (A ▽ C) ⩾ r$ for all sufficiently large n. Hence C and r witness the truth of (ii).

Routine expansion shows that the set of rational numbers q satisfying (ii) is $Σ_{3}^{0}$ , so $γ (A)$ is left- $Σ_{3}^{0}$ by definition. □

In the next result, we prove the converse and thus characterize the reals of the form $γ (A)$ for A c.e.

Theorem 6.2.

Suppose $0 ⩽ r ⩽ 1$ . Then the following are equivalent:

$r = γ (A)$ for some c.e. set A.

r is left- $Σ_{3}^{0}$ .

Proof.

It was shown in the previous proposition that (i) implies (ii), so it remains to be shown that (ii) implies (i). Let r be left- $Σ_{3}^{0}$ . Our proof is based on that of Theorem 5.7 of [5], which shows that r is the lower density of some c.e. set. That proof consists in taking a $Δ_{2}^{0}$ set B such that $\underline{ρ} (B) = r$ (which exists by the relativized form of Theorem 5.1 of [5]) and constructing a strictly increasing $Δ_{2}^{0}$ function t and a c.e. set $A_{0}$ such that for each n,

$ρ_{t (n)} (A_{0}) = ρ_{n} (B)$ .

$A_{0} \cap [t (n), t (n + 1))$ is an initial segment of $[t (n), t (n + 1))$ .

It then follows easily that

\underline{ρ} (A_{0}) = \underline{ρ} (B) = r

Let S be the set of all pairs $(k, e)$ such that $e ⩽ k$ . Let f be a computable bijection between S and ω. We can easily adapt the proof of Theorem 5.7 of [5] to replace (1) by

$ρ_{t (f (k, e))} (A_{0}) = ρ_{k} (B)$ for each k and $e ⩽ k$ ,

while still having (2) hold for each n. Furthermore, we can also ensure that when a new approximation

t (n, s + 1)

t (n)

is defined, it is chosen to be greater than both

2^{t (n - 1, s + 1)}

and

2^{t (s, s)}

(because for each instance of Lemma 5.8 of [5], there are infinitely many c witnessing the truth of the lemma).

We now define a c.e. set C. At stage s, proceed as follows for each pair $(k, e)$ with $f (k, e) ⩽ s$ . Let $n = f (k, e)$ . If $Φ_{e, s} (x) ↓$ for all $x \in [t (n - 1, s), t (n, s))$ , then for each such x for which $Φ_{e} (x) = 0$ , enumerate x into C (if x is not already in C). We say that x is put into C for the sake of $(k, e)$ .

Let $A = A_{0} \cup C$ . Then A is a c.e. set, and $\underline{ρ} (A) ⩾ \underline{ρ} (A_{0}) = r$ . By Theorem 3.9 of [5], for each $ϵ > 0$ , there is a computable subset of A with lower density greater than $r - ϵ$ . It follows that $γ (A) ⩾ r$ .

Now let e be such that $Φ_{e}$ is total. Fix k and let $n = f (k, e)$ . Let s be least such that $t (n, s + 1) = t (n)$ . Every number put into C by the end of stage s is less than $t (s, s)$ . Every number put into C after stage s for the sake of any pair other than $(k, e)$ is either less than $t (n - 1) = t (n - 1, s + 1)$ or greater than or equal to $t (n)$ . By our assumption on the size of $t (n)$ , it follows that $C (x) \neq Φ_{e} (x)$ for every $x \in [{log}_{2} t (n), t (n))$ , so $ρ_{t (n)} (C ▽ Φ_{e}) ⩽ \frac{{log}_{2} t (n)}{t (n)}$ , and hence $\begin{matrix} ρ_{t (n)} (A ▽ Φ_{e}) ⩽ ρ_{t (n)} (C ▽ Φ_{e}) + ρ_{t (n)} (A_{0}) ⩽ \frac{{log}_{2} t (n)}{t (n)} + ρ_{t (n)} (A_{0}) = \frac{{log}_{2} t (n)}{t (n)} + ρ_{k} (B) . \end{matrix}$ Since ${lim}_{n} \frac{{log}_{2} t (n)}{t (n)} = 0$ , we have $\underline{ρ} (A ▽ Φ_{e}) ⩽ \underline{ρ} (B) = r$ . Since e is arbitrary, $γ (A) ⩽ r$ . □

Definition 6.3.

If $A \subseteq N$ we call $\begin{matrix} S (A) = {γ (B) : B ⩽_{T} A} \subseteq [0, 1] \end{matrix}$ the coarse spectrum of A.

Theorem 6.4.

For any set A and any $Δ_{2}^{0}$ real $s \in [0, 1]$ , we have that $s \cdot γ (A) + (1 - s) \in S (A)$ . It follows that $S (A)$ is dense in the interval $[γ (A), 1]$ .

Proof.

We may assume that $s > 0$ , since any computable $B ⩽_{T} A$ witnesses the fact that $1 \in S (A)$ . By Theorem 2.21 of [10] there is a computable set R of density s. Note that R is infinite. Let h be an increasing computable function with range R, and let $B = h (A)$ . Then $B ⩽_{T} A$ , so it suffices to prove that $γ (B) = s \cdot γ (A) + (1 - s)$ . For this, we need the following lemma, which relates the lower density of $h (X)$ to that of X. The corresponding lemma for density was proved as Lemma 3.4 of [4], and the proof here is almost the same. Lemma 6.5.

Let h be a strictly increasing function and let $X \subseteq ω$ . Then $\underline{ρ} (h (X)) = ρ (rng (h)) \underline{ρ} (X)$ , provided that the range of h has a density.

Proof.

Let Y be the range of h, and for each u, let $g (u)$ be the least k such that $h (k) ⩾ u$ . As shown in the proof of Lemma 3.4 of [4], $ρ_{u} (h (X)) = ρ_{u} (Y) ρ_{g (u)} (X)$ for all u, via bijections induced by h. Taking the lim inf of both sides and using the fact that $ρ (Y)$ exists, we see that $\begin{matrix} \underline{ρ} (h (X)) = ρ (Y) (lim inf ⟨ ρ_{g (0)} (X), ρ_{g (1)} (X), \dots ⟩) . \end{matrix}$ It is easily seen that the function g is finite-one and $g (h (x)) = x$ for all x, and $g (u + 1) ⩽ g (u) + 1$ for all u. Hence the sequence on the right-hand side of the above equation can be obtained from the sequence $ρ_{0} (X), ρ_{1} (X), \dots$ by replacing each term by a finite, nonempty sequence of terms with the same value. Thus the two sequences have the same lim inf, and we obtain $\underline{ρ} (h (X)) = ρ (Y) \underline{ρ} (X)$ , as needed to prove the lemma. □

To prove that $γ (B) = s \cdot γ (A) + (1 - s)$ , it suffices to show that for each $t \in [0, 1]$ , A is coarsely computable at density t if and only if B is coarsely computable at density $s t + 1 - s$ . Suppose first that A is coarsely computable at density t, and let C be a computable set such that $\underline{ρ} (A ▽ C) ⩾ t$ . Let $\hat{C} = h (C)$ . Then $\hat{C}$ is a computable set and $\begin{matrix} \underline{ρ} (\hat{C} ▽ B) = \underline{ρ} (h (C ▽ A) \cup \overline{R}) = \underline{ρ} (h (C ▽ A)) + ρ (\overline{R}) = s \underline{ρ} (C ▽ A) + 1 - s ⩾ s t + (1 - s) . \end{matrix}$ It follows that B is coarsely computable at density $s t + (1 - s)$ .

Conversely, suppose a computable set $\hat{C}$ witnesses that B is coarsely computable at density $s t + (1 - s)$ . Since $B = h (A) \subseteq rng (h) = R$ , we may assume without loss of generality that $\hat{C} \subseteq R$ . Let $C = h^{- 1} (\hat{C})$ . Then $\begin{matrix} s t + 1 - s ⩽ \underline{ρ} (\hat{C} ▽ B) = \underline{ρ} (h (C ▽ A) \cup \overline{R}) = \underline{ρ} (h (C ▽ A)) + ρ (\overline{R}) = s \underline{ρ} (C ▽ A) + 1 - s . \end{matrix}$ Solving for t (using the fact that $s \neq 0$ ), we obtain $t ⩽ \underline{ρ} (C ▽ A)$ , and it follows that C witnesses that A is coarsely computable at density t. □

Footnotes

Acknowledgements

Hirschfeldt was partially supported by grant DMS-1101458 from the National Science Foundation of the United States. McNicholl was partially supported by a Simons Foundation Collaboration Grant for Mathematicians.

References

[1]

Andrews,

Cai,

Diamondstone,

Jockusch and

Lempp, Asymptotic density, computable traceability, and 1-randomness, submitted for publication.

[2]

Bienvenu,

Day and

Hölzl, From bi-immunity to absolute undecidability, Journal of Symbolic Logic 78 (2013), 1218–1228.

[3]

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Complexity and Randomness, Theory and Applications of Computability, Springer, New York, 2010.

[4]

R.G.

Downey,

C.G.

JockuschJr.,

T.H.

McNicholl and

P.E.

Schupp, Asymptotic density and the Ershov hierarchy, Mathematical Logic Quarterly 61 (2015), 189–195.

[5]

R.G.

Downey,

C.G.

JockuschJr. and

P.E.

Schupp, Asymptotic density and computably enumerable sets, Journal of Mathematical Logic 13 (2013), 1350005, (43 pages).

[6]

D.R.

Hirschfeldt,

C.G.

JockuschJr.,

Kuyper and

P.E.

Schupp, Coarse reducibility and algorithmic randomness, submitted for publication.

[7]

Igusa, Nonexistence of minimal pairs for generic computability, Journal of Symbolic Logic 78 (2013), 511–522.

[8]

C.G.

JockuschJr., The degrees of bi-immune sets, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 15 (1969), 135–140.

[9]

C.G.

JockuschJr., Degrees in which the recursive sets are uniformly recursive, Canadian Journal of Mathematics 24 (1972), 1092–1099.

10.

[10]

C.G.

JockuschJr. and

P.E.

Schupp, Generic computability, Turing degrees, and asymptotic density, Journal of the London Mathematical Society, Second Series 85 (2012), 472–490.

11.

[11]

Kapovich,

Myasnikov,

Schupp and

Shpilrain, Generic-case complexity, decision problems in group theory, and random walks, Journal of Algebra 264 (2003), 665–694.

12.

[12]

S.A.

Kurtz, Notions of weak genericity, Journal of Symbolic Logic 48 (1983), 764–770.

13.

[13]

D.A.

Martin, Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 12 (1966), 295–310.

14.

[14]

R.I.

Soare, Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987.