Asymptotic density,immunity and randomness

Abstract

In 2012, inspired by developments in group theory and complexity, Jockusch and Schupp introduced generic computability, capturing the idea that an algorithm might work correctly except for a vanishing fraction of cases. However, we observe that their definition of a negligible set is not computably invariant (and thus not well-defined on the 1-degrees), resulting in some failures of intuition and a break with standard expectations in computability theory.

To strengthen their approach, we introduce a new notion of intrinsic asymptotic density, with rich relations to both randomness and classical computability theory. We then apply these ideas to propose alternative foundations for further development in (intrinsic) generic computability.

Toward these goals, we classify intrinsic density 0 as a new immunity property, specifying its position in the standard hierarchy from immune to cohesive for both general and $Δ_{2}^{0}$ sets, and identify intrinsic density $\frac{1}{2}$ as the stochasticity corresponding to permutation randomness. We also prove that Rice’s Theorem extends to all intrinsic variations of generic computability, demonstrating in particular that no such notion considers $\emptyset^{'}$ to be “computable”.

Keywords

Asymptotic density generic computability intrinsic density immunity Rice’s Theorem

1. Introduction

For years, there has been strong interest in the distinction between the idealized world of computation and complexity and that of its real-world applications, particularly in problems or algorithms where we find a separation between the worst-case complexity (or, more broadly, difficulty) and the worst cases actually encountered in practice. The simplex algorithm for linear programming is the classic example; there is a family of examples on which the algorithm takes exponential time [13], yet in practice, every problem actually encountered is solved within polynomial time bounds. Even more extreme examples are known, including several problems in group theory (including some variants of the word problem) that are non-computable in general, but for which a low-complexity algorithm solves all examples encountered in practice [12]. In complexity theory, current methods for exploring such structure include the average-case complexity introduced by Gurevich [7] and Levin [14], though this is sensitive to one’s choice of probability measure, as well as the smoothed analysis of Spielman and Tang [22]; however, none of these methods have been adapted to computability theory, and it may well be that none are well-suited to such problems.

Taking a more direct approach, several researchers have begun work on the question of whether an algorithm’s problematic behavior might be restricted to a negligible set. This is clearly related to the analysts’ notion of “almost everywhere”, whereby one works modulo sets of measure 0 so as to disregard problematic variations with no practical effect. In a sense, this study is motivated by envy of their methods – in recent years, we have discovered problems that seem to be “computable almost everywhere”, and are working to find the right definition for the phrase. In this paper, we take the direct approach, studying a new definition of negligibility as applied to the non-negative integers; we will spend most of our time fitting this idea into its proper computability-theoretic context, and then lay the foundations for further investigation into our motivating problem.

The essential difficulty in defining “computable almost everywhere” is that there is no uniform probability measure on the integers, and thus no natural notion of a null set. Instead, if we want a uniform measurement of the size of a subset of ω, we are forced to abandon countable additivity and fall back to pseudo-measures. One of the most practical is asymptotic density.

Definition 1.1.
Let $S \subseteq ω$ , where $ω = {0, 1, 2, \dots}$ is the set of natural numbers. For every $n ⩾ 0$ , we denote $S \cap [0, n)$ by $S ↾ n$ .

We define the nth partial density of S as $ρ_{n} (S) : = \frac{| S ↾ n |}{n} .$ The lower density $\underline{ρ} (S)$ of S is $\underline{ρ} (S) : = \underset{n \to \infty}{lim inf} ρ_{n} (S) = \underset{n \to \infty}{lim inf} \frac{| S ↾ n |}{n},$ and the upper density $\overline{ρ} (S)$ of S is $\overline{ρ} (S) : = \underset{n \to \infty}{lim sup} ρ_{n} (S) = \underset{n \to \infty}{lim sup} \frac{| S ↾ n |}{n} .$

If the limit of the partial densities exists (i.e., $\underline{ρ} (S) = \overline{ρ} (S)$ ), then we say that S has (asymptotic) density $ρ (S) : = lim_{n \to \infty} ρ_{n} (S) = lim_{n \to \infty} \frac{| S ↾ n |}{n} .$

Of course, $0 ⩽ \underline{ρ} (S) ⩽ \overline{ρ} (S) ⩽ 1$ for all $S \subseteq ω$ . In an unfortunate collision of terms, at least for computability-theoretic work, a set is said to be generic if it has density 1 (equivalently, $\underline{ρ} (S) = 1$ ). The name is motivated by the fact that given a generic set S, the probability that a random integer selected from $[0, n)$ will lie in S approaches 1 as n increases; thus, in some sense, such a set contains all generic integers. The complement of this notion is more useful for our purposes:
Definition 1.2.
A set $S \subset ω$ is said to be negligible if it has density 0 (equivalently, if $\overline{ρ} (S) = 0$ ).

In 2003, Kapovich, Myasnikov, Schupp and Shpilrain introduced generic-case complexity [12], considering problems modulo sets of density 0. They showed that this captured the phenomenon observed in several group-theoretic problems that are known to have non-computable instances while being simple to solve for every case encountered in practice; for instance, they demonstrated that for any G in an extremely large class of groups, the word problem for G has linear-time generic-case complexity. Myasnikov, in collaboration with Hamkins, went on to apply these ideas to Turing’s halting problem [8], and proved that (for reasons having to do with the prevalence of trivially halting or trivially non-halting programs in many models of computation) the halting problem is “generic-case decidable” in said models. This was later refined by Rybalov [20], who proved that the halting problem is not “strongly generic-case decidable” (that is, decidable modulo sets with partial density converging to 0 exponentially fast); this proof, by contrast, is valid for all Turing-machine models of computation.

Jockusch and Schupp [10] have since defined and begun the study of the computability theory corresponding to generic-case complexity, and more generally the relations between asymptotic density and computability. Their work has been further developed in collaboration with Downey [6] and McNicholl [5], and refined in specific cases by Igusa [9] and Bienvenu, Hölzl and Day. [1]

However, we return the focus to the notion of negligibility, since one would expect such a definition to have interesting ties to classical computability theory. For one, a negligible set might be said to be “small”, “sparse”, or even “thin”. Such “thinness” properties have historically been of great interest in computability; they were the focus of Post’s program [18], the first attempt to construct an incomplete c.e. set, and have since proven to be of interest for unrelated reasons.

Negligibility (in the sense of asymptotic density) is closed downwards under the subset relation; any subset of a negligible set is itself negligible. It seems natural that it should be in the same family as the classical immunity properties, which provide the unifying computability-theoretic model for “thinness”. However, negligibility does not lend itself to the same analysis that we apply to immunity. Choosing an alternate coding for the parameters of a membership problem is equivalent to applying a computable permutation to the underlying set, which can dramatically alter its asymptotic density. The most extreme example comes when we consider the class of infinite, co-infinite computable sets; the resulting consequences for c.e. and co-c.e. sets are essential to the remainder of this paper. We will need one standard definition of computability theory to incorporate a result of Downey, Jockusch and Schupp: we say that a real a is left- $Σ_{2}^{0}$ (left- $Π_{2}^{0}$ ) if its left cut is $Σ_{2}^{0}$ ( $Π_{2}^{0}$ ).
Proposition 1.3.
Suppose A is an infinite, co-infinite computable set. For any left- $Σ_{2}^{0}$ real a and any left- $Π_{2}^{0}$ real b with $0 ⩽ a ⩽ b ⩽ 1$ , there is a computable permutation $π : ω \to ω$ such that $π (A)$ has lower density a and upper density b.
Proof.
We note first that there is an infinite, co-infinite computable set B with lower density a and upper density b. In fact, this is nearly a theorem of Downey, Jockusch and Schupp [6], which states that for any a and b meeting our preconditions, there is a computable set B with lower density a and upper density b. Unless $a = b = 0$ or $a = b = 1$ , this already ensures that B is both infinite and co-infinite; if considering one of these cases, let B be the set of perfect squares or its complement, respectively.

Since the infinite, co-infinite computable sets form an orbit under computable permutations, there is a computable permutation $π : ω \to ω$ such that $π (A) = B$ ; therefore, $π (A)$ has lower density a and upper density b. □
Corollary 1.4.
If A is infinite and c.e., there is a computable permutation $π : ω \to ω$ such that $π (A)$ has density 1.
Proof.
Since A is infinite and c.e., A has an infinite (and co-infinite) computable subset B. By Proposition 1.3, there is a computable permutation $π : ω \to ω$ such that $π (B)$ has density 1. Since $B \subseteq A$ , $π (B) \subseteq π (A)$ , so $π (A)$ must also have density 1. □
Corollary 1.5.
If A is co-infinite and co-c.e., there is a computable permutation $π : ω \to ω$ such that $π (A)$ has density 0.

Since any infinite c.e. set has density 1 under some computable permutation, any problem that is decidable on some infinite c.e. subset of ω is in fact generic-case decidable if we choose the “correct” coding of the input. The corresponding coding is usually highly artificial, having little to do with the problem at hand.

In short, due to the sensitivity of asymptotic density to computable permutation, generic-case computability is sensitive to the coding we choose for a given problem. As some of the great strengths of Turing computability come from its invariance under choice of coding, we might hope to strengthen generic-case computability in such a way as to recover this invariance. To do so, we need to develop a stronger concept of negligibility, considering not only the upper and lower densities of a set, but those of all its images under computable permutations of ω.

In Section 2, we follow this approach and obtain a new pseudo-measure, intrinsic density, which is invariant under computable permutations of ω. We discuss various classes of sets that have intrinsic density, including the 1-random sets, which provide the foundation for our investigations in the rest of this paper.

For the remainder of the paper, we turn our focus to the new properties of intrinsic density. In Section 3, we begin with intrinsic density 0, the natural notion of being intrinsically negligible, discussing it in the context of classical computability theory. In fact, intrinsic density 0 is an immunity property, fitting naturally into the hierarchy between immunity and cohesiveness, and we determine its place in the hierarchy for both unrestricted and $Δ_{2}^{0}$ sets. In order to complete our description, we improve on a result of Downey, Jockusch and Schupp [6], constructing a strongly hyperhyperimmune set with upper density at least $1 - ε$ below $\emptyset^{'}$ .

In Section 4, we reflect on the relation between intrinsic density and randomness, and the connection it provides between classical computability and randomness. In fact, intrinsic density provides a continuum from immunity to stochasticity, as any intrinsic density from the range $(0, 1)$ is a version of stochasticity (modulo a fixed bias), while intrinsic density 0 is a form of immunity (as discussed in the previous section). In fact, this correspondence can be reversed to extract various strengthenings of asymptotic density from the assorted notions of stochasticity – some of which may prove fruitful topics of interest for future research.

Lastly, in Section 5, we return to our motivating problem: the task of strengthening generic-case computability. After discussing some additional reasons for considering computably invariant notions of generic-case computability, we propose four such definitions, varying in degree of uniformity. All are strictly weaker than ordinary Turing computability, but even the weakest of our notions does not consider the halting problem (or, in fact, any nontrivial index set) to be computable.

In the remainder of the Introduction, we collect notation and definitions that will be used for the rest of this paper. We will denote the eth partial computable function by $φ_{e}$ .

We will routinely identify a set $S \subseteq ω$ with its characteristic function, $S (n)$ , and also with the infinite binary sequence defining its characteristic function, ${S (n)}_{n \in ω}$ . By $S ↾ n$ , we mean either $S \cap [0, n)$ or the string consisting of the initial n bits of the infinite sequence; which notation we are using at a given moment will be made clear by context. Two sets S and T have finite difference, denoted $S =^{} T$ , if $S (n) = T (n)$ for all sufficiently large n.

Given two finite binary strings v and w, we say v is a prefix* of w, denoted $v ⪯ w$ , if there is a binary string x such that the concatenation of v followed by x is w (i.e., $v x = w$ ); this definition extends to infinite binary sequences w in the natural way.

The prefix-free Kolmogorov complexity of a binary string w is denoted as $K (w)$ ; we refer to Downey and Hirschfeldt [3] or Nies [17] for the details of its definition and properties, but note that it does relativize: we can consider the prefix-free Kolmogorov complexity of w with respect to A, denoted $K^{A} (w)$ . Both of these books also provide many equivalent characterizations of a 1-random set; for this paper, we will take the characterization in terms of the Kolmogorov complexity of initial segments as our definition. A set $S \subseteq ω$ is 1-random if there is some constant c such that $K (S ↾ n) ⩾ n - c$ for all n. This definition inherits a natural relativization from prefix-free complexity: S is 1-random relative to A if there is some c such that $K^{A} (S ↾ n) ⩾ n - c$ for all n.

A set $S \subseteq ω$ is 1-generic if, for every c.e. set X of finite binary strings, there is some initial segment $σ ≺ S$ such that either $σ \in X$ or $σ ⋠ τ$ for every $τ \in X$ .
2. Intrinsic density

Definition 2.1.
Let $S \subseteq ω$ . The absolute lower density $\underline{ρ} (S)$ of S is $\underline{ρ} (S) : = inf_{π} \underline{ρ} (π (S)),$ and the absolute upper density $\overline{ρ} (S)$ of S is $\overline{ρ} (S) : = sup_{π} \overline{ρ} (π (S)),$ where $π : ω \to ω$ is taken to vary over the set of computable permutations.

If the absolute upper and lower densities are equal, then we say that S has intrinsic (asymptotic) density $ρ (S)$ , where $ρ (S) : = \overline{ρ} (S) = \underline{ρ} (S) .$ In this case, not only does S have a density, but its density is fixed under all computable permutations. We can develop analogous definitions for lower and upper densities; if $\underline{ρ} (S) = \underline{ρ} (π (S))$ for all computable permutations $π : ω \to ω$ , we say that S has intrinsic lower density $\underline{ρ} (S)$ , and similarly for upper density.

If a set has intrinsic density 0, we say it is intrinsically negligible.

By Proposition 1.3, all infinite, co-infinite computable sets have absolute lower density 0 and absolute upper density 1. Thus, they are “as far as possible” from having an intrinsic density, at least in the sense that, under computable permutations, their densities range as widely as possible.

However, some might argue that 1-generic sets are further from having an intrinsic density than computable sets. It is simple to show that all 1-generic sets have lower density 0 and upper density 1. Since the class of 1-generic sets is closed under computable permutation, we can conclude that all 1-generic sets in fact have intrinsic lower density 0 and intrinsic upper density 1. This puts them “as far as possible” from having an intrinsic density, in the sense that no computable permutation can bring their upper and lower densities together.

For the rest of our work in this paper, we will focus primarily on sets that have an intrinsic density, rather than classes of sets that do not. With a few examples, we begin to establish the connections between intrinsic density and other computability-theoretic properties, and (particularly in discussing sets with intrinsic density strictly between 0 and 1) lay the groundwork for our later results.

We start with the r-cohesive and r-maximal sets. Recall that an infinite set C is r-cohesive if there is no computable set R such that $R \cap C$ and $\overline{R} \cap C$ are both infinite, while a c.e. set C is r-maximal if its complement is r-cohesive.
Theorem 2.2 (Jockusch, private correspondence).

Every r-cohesive set has intrinsic density 0.

Proof.
We note that if a set C is r-cohesive, then its image under any computable permutation of ω is also r-cohesive; it thus suffices to prove that every r-cohesive set has density 0.

If we have a finite computable partition of ω (i.e., ${R_{0}, R_{1}, \dots, R_{n - 1}}$ computable and pairwise disjoint, with union ω), C must have finite intersection with all but one of these $R_{i}$ , say $R_{j}$ . By the finite subadditivity of upper density, $\overline{ρ} (C) ⩽ 0 + \overline{ρ} (C \cap R_{j}) ⩽ \overline{ρ} (R_{j})$ . If we take $R_{i} = {k n + i ∣ k \in ω}$ , we have that $ρ (R_{i}) = \frac{1}{n}$ , so $\overline{ρ} (C) ⩽ \frac{1}{n}$ . Since n was an arbitrary natural number, the upper density of C must be 0, so $ρ (C) = 0$ . □
Corollary 2.3.
Every r-maximal set has intrinsic density 1.

However, sets of intermediate intrinsic density (strictly between 0 and 1) provide a more versatile basis for further investigation; as such, the 1-random sets will be essential to certain constructions later in this paper.
Proposition 2.4.
Every 1-random set has intrinsic density $\frac{1}{2}$ .
Proof.
Any 1-random set obeys the Law of Large Numbers, in the sense that it has density $\frac{1}{2}$ [17, Prop. 3.2.13]. Since the class of 1-random sets is closed under computable permutations of ω, every 1-random set has intrinsic density $\frac{1}{2}$ . □

We can use 1-randoms to construct sets of other intermediate intrinsic densities as well, by means of the following lemma and its corollaries.
Lemma 2.5.
If A has density d, and B is 1-random relative to A, then $A \cap B$ has density $\frac{d}{2}$ .
Proof.
Interpreting B as a binary sequence, consider the A-computable subsequence $\hat{B}$ selected by the rule “If $n \in A$ , select $B (n)$ ”. Since B is 1-random relative to A, we see that $\hat{B}$ must be an unbiased sequence; in other words, $ρ (\hat{B}) = \frac{1}{2}$ .

However, by the definition of $\hat{B}$ and asymptotic density, $ρ (\hat{B}) = lim_{n \to \infty} \frac{| (A \cap B) ↾ n |}{| A ↾ n |},$ so $\begin{array}{rcl} ρ (A) ρ (\hat{B}) & = & (lim_{n \to \infty} \frac{| A ↾ n |}{n}) (lim_{n \to \infty} \frac{| (A \cap B) ↾ n |}{| A ↾ n |}) \\ = & lim_{n \to \infty} \frac{| (A \cap B) ↾ n |}{n} \\ = & ρ (A \cap B) . \end{array}$ Therefore, $A \cap B$ has density $ρ (A) ρ (\hat{B}) = \frac{d}{2}$ . □

Since being 1-random is invariant under computable permutation, we obtain one more pair of corollaries:
Corollary 2.6.
If A has intrinsic density d, and B is 1-random relative to A, then $A \cap B$ has intrinsic density $\frac{d}{2}$ .
Corollary 2.7.
If ${A_{1}, \dots, A_{n}}$ are mutually relatively 1-random sets (i.e., each set is 1-random relative to the join of the others), then $⋂_{1 ⩽ i ⩽ n} A_{i}$ has intrinsic density $2^{- n}$ .

Having established a few tools to use in controlling the intrinsic density of sets (in this paper, largely useful for the construction of counterexamples), we can now proceed to consider intrinsic density in a broader context.
3. Intrinsic density and immunity

As discussed in the Introduction, asymptotic density was defined as a substitute for a probability measure on a countable space. Its use in generic-case computability (and other topics) is in defining a density-0 set to be negligible, in the sense that its elements are eventually scarce. This provides one of the more practical notions of a “small” or “thin” subset of the integers, in some senses more natural than asserting that a set has no infinite c.e. subset (i.e., is immune).

Unfortunately, having density 0 is not computably invariant. From the perspective of computability theory, set properties that vary under computable permutation have limited applications. By addressing this one issue, having intrinsic density 0 proves to be more powerful; for example, any infinite set having intrinsic density 0 (or, in fact, any intrinsic lower density other than 1) must be immune.

Proposition 3.1.
Any infinite non-immune set has density 1 under some computable permutation.
Proof.
This immediately follows from Corollary 1.4. If S is infinite and not immune, it contains an infinite c.e. subset A. By Corollary 1.4, $π (A)$ has density 1 for some computable permutation π. Since $S \supseteq A$ , $π (S) \supseteq π (A)$ , so $π (S)$ must also have density 1. □
Corollary 3.2.
Any infinite set with intrinsic lower density 0, and hence, any infinite set with intrinsic density 0, is immune.

It is clear that the upper density of a set bounds the upper density of any of its subsets, so intrinsic density 0 is closed downwards under the subset relation. Since having intrinsic density 0 is a computably invariant property, closed under subsets, and implies immunity, intrinsic density 0 (here abbreviated id0) is a natural new immunity property, describing a strong notion of “thinness”.

We therefore seek to determine its relation to the classical immunity properties:
Definition 3.3.
A c.e. list of pairwise disjoint finite sets ${D_{i}}$ (indexed as finite sets, so that the sets $D_{i}$ and the function $i \mapsto max D_{i}$ are computable) is said to be a strong array. Similarly, a uniformly c.e. list of pairwise disjoint c.e. sets ${U_{i}}$ is a weak array. There appears to be no standard name for the intermediate concept, which we here term a computable array: a c.e. list of pairwise disjoint computable sets ${C_{i}}$ (indexed appropriately), with union $⋃ C_{i}$ also computable.

An infinite set A is hyperimmune (sometimes abbreviated h-immune) if for every strong array ${D_{i}}$ , there is some j such that $A \cap D_{j} = \emptyset$ ; in this case, we say that ${D_{i}}$ fails to meet A. Similarly, A is said to be strongly hyperimmune (sh-immune) if no computable array meets A, and strongly hyperhyperimmune (shh-immune) if no weak array meets A. In a slight generalization, we say A is finitely strong hyperimmune (fsh-immune) if no computable array ${C_{i}}$ with all $C_{i}$ finite meets A, and hyperhyperimmune if no weak array ${U_{i}}$ with all $U_{i}$ finite meets A.

It was quickly noted that a set A is hyperimmune iff no computable function dominates its principal function $p_{A} (n) : = (μ x) [| S ↾ x | ⩾ n]$ ; that is, for all computable functions f, we have $p_{A} (n) ⩾ f (n)$ infinitely often. Strengthening this, we say that an infinite set A is dense immune if its principal function dominates all computable functions: for all computable functions f and all sufficiently large n, we have $p_{A} (n) ⩾ f (n)$ .

An infinite set A is cohesive if, for all c.e. sets $U_{i}$ , either $A \cap U_{i}$ or $A \cap \overline{U_{i}}$ is finite. We can weaken this in a few standard ways: A is r-cohesive if the same property holds for computable sets $C_{i}$ , or quasicohesive (q-cohesive) if A is a finite union of cohesive sets.

These properties are organized in a natural hierarchy of implication, shown as Fig. 1. Chapter XI.1 of Soare [21] provides an excellent reference for this hierarchy (though focused on co-c.e. sets). We note that in the general case, the lack of implication between cohesiveness and dense immunity is witnessed by the existence of a non-high cohesive set, as constructed by Jockusch and Stephan [11]. Also, shh-immunity and hh-immunity are distinguishable in the general case, but by a remark of Cooper [2], are equivalent for $Δ_{2}^{0}$ sets (and thus for co-c.e. sets).

Figure 1.
The graphs of the implications between the classical immunity properties; for $Δ_{2}^{0}$ sets, the implications are the same as in the general case, except that shh-immunity and hh-immunity become equivalent. All implications are strict, and any not shown (excepting those implied by transitivity) are false.

By Theorem 2.2, r-cohesiveness implies intrinsic density 0. This has a simple corollary, included here for completeness:
Corollary 3.4.
Every quasi-cohesive set has intrinsic density 0.
Proof.
As a finite union of cohesive (and thus r-cohesive) sets, any quasi-cohesive set Q is a finite union of sets of intrinsic density 0. Since density is finitely subadditive, Q must also have intrinsic density 0. □

It is slightly more interesting to note that dense immunity also implies intrinsic density 0. To show this, we note that dense immunity is computably invariant, and that a certain domination property is equivalent to having density 0.
Lemma 3.5.
For any infinite set $S \subseteq ω$ , $\overline{ρ} (S) : = \underset{n \to \infty}{lim sup} \frac{| S ↾ n |}{n} = \underset{n \to \infty}{lim sup} \frac{n}{p_{S} (n)},$ where $p_{S} : = (μ x) [| S ↾ x | ⩾ n]$ is the principal function of S.
Proof.
Consider the sequence ${a_{n}} = {\frac{| S ↾ n |}{n}}_{n \in ω}$ . We note that ${b_{n}} = {\frac{n}{p_{S} (n)}}_{n \in ω}$ is an infinite subsequence – in fact, $b_{n} = a_{p_{S} (n)}$ for all $n \in ω$ – so $\underset{n \to \infty}{lim sup} b_{n} ⩽ \underset{n \to \infty}{lim sup} a_{n} = \overline{ρ} (S) .$ The sequence $a_{n}$ may increase only at n in the image of $p_{S}$ (and thus at points also in the subsequence $b_{n}$ ), so these limits must be equal. □
Proposition 3.6.
An infinite set $S \subseteq ω$ has density 0 iff its principal function dominates all linear functions.(In standard asymptotic [“Big-O”] notation, S has density 0 iff $p_{S} (n) \in ω (n)$ . )
Proof.
S has density 0 iff $\overline{ρ} (S) = 0$ , and by the preceding lemma, $\overline{ρ} (S) = \underset{n \to \infty}{lim sup} \frac{n}{p_{S} (n)} .$ However, for all $k > 0$ , ${lim sup}_{n \to \infty} \frac{n}{p_{S} (n)} < \frac{1}{k}$ iff for all $c \in R$ , $p_{S} (n)$ dominates $k n + c$ ; therefore, $\overline{ρ} (S) = 0$ iff $p_{S} (n)$ dominates $k n + c$ for all $k > 0$ and $c \in R$ . □
Proposition 3.7.
If the set A is dense immune, $π (A)$ is also dense immune for any computable permutation π.
Proof.
Let π be a computable permutation, and consider a computable function f. We define $\hat{f} (n) = 1 + max_{x \in [0, f (n))} π^{- 1} (x) .$ Since $\hat{f}$ is a computable function, the principal function of A must dominate $\hat{f}$ ; that is, $p_{A} (n) > \hat{f} (n)$ for all but finitely many n. In other words, for all sufficiently large n, there are fewer than n elements of A less than $\hat{f} (n)$ .

However, by construction of $\hat{f}$ , every element of $π (A)$ less than $f (n)$ must come from an element of A below $\hat{f} (n)$ . Since for almost all n, there are fewer than n elements of A below $\hat{f} (n)$ , we see that $p_{π (A)}$ dominates f. Since both f and π were arbitrary, every computable permutation of A is dense immune. □
Corollary 3.8.
If $S \subseteq ω$ is dense immune, S has intrinsic density 0.
Proof.
By Proposition 3.7, dense immunity is a computably invariant property. It therefore suffices to show that dense immunity implies density 0. However, this is an immediate consequence of Proposition 3.6, as all linear functions are bounded by computable functions, and so are dominated by the principal function of any dense immune set. □

None of the remaining standard immunity properties imply intrinsic density 0. In fact, as demonstrated by Downey, Jockusch and Schupp [6], for every $ε > 0$ , there is a strongly hyperhyperimmune set with upper density at least $1 - ε$ (though none have upper density 1), constructed by Mathias forcing. We here extend their result, using a direct $\emptyset^{'}$ -computable construction, to show that we may assume these sets to be $Δ_{2}^{0}$ . Of course, per the aforementioned remark of Cooper [2], any $Δ_{2}^{0}$ hh-immune set is in fact shh-immune; this apparently does not simplify the argument required, so we will make no use of this fact.
Theorem 3.9.
For all $ε > 0$ , there is a $Δ_{2}^{0}$ (s)hh-immune set A with upper density at least $1 - ε$ .
Proof.
We assume that ε is rational; if not, we can replace it by any rational less than ε. We will construct A as a $\emptyset^{'}$ -computable set, consulting $\emptyset^{'}$ as an oracle during our otherwise-computable construction.

We work to satisfy the requirements: $\begin{array}{rcl} P_{e} : (\exists n > e) [ρ_{n} (A) ⩾ 1 - ε], \\ N_{e} : (\forall i, j) [(i \neq j) ⟹ (U_{e, i} \cap U_{e, j} = \emptyset)] ⟹ (\exists k_{e}) [A \cap U_{e, k_{e}} = \emptyset], \end{array}$ where ${U_{e, i}}$ is a listing of the uniformly c.e. sequences of sets. (In other words, every uniformly c.e. sequence of sets is of the form ${U_{e, i}}_{i \in ω}$ for some e.)

The negative requirements $N_{e}$ together assert that every weak array fails to meet A; this is the definition of shh-immunity.

Our negative requirements should, in principle, be simple to satisfy. We simply omit a set from each weak array of small lower density, thus leaving us with a set A with high upper density. There are slight complications in ensuring that taking all of these requirements still cannot force A’s upper density to fall below $1 - ε$ , but these are easily addressed. After all, at any given point n, only q disjoint sets can have partial density exceeding $\frac{1}{q}$ ; therefore, for any weak array ${U_{e, i}}_{i = 0}^{\infty}$ , there must be some $U_{e, k}$ with lower density less than $2^{- e} ε$ .

The trouble comes in attempting to identify the $U_{e, k}$ in question. $\emptyset^{'}$ is incapable of resolving whether a c.e. set has lower density below some bound; in fact, this problem is $Σ_{2}^{0}$ -hard, as it would allow us to distinguish finite c.e. sets from total c.e. sets. Therefore, we cannot search directly for such a $U_{k}$ in our weak array, and must use more indirect methods.

Towards this end, we will make heavy use of the following sentence, for varying values of e, n, and r: $\begin{array}{rclr} (\exists x_{n} > x_{n - 1} > \dots > x_{1} ⩾ r) (\exists s) (\exists t > s) \\ [t \in C_{e - 1, s} \land (\forall i ⩽ n) [ρ_{t} (U_{e, x_{i}}) ⩾ d_{e}]] . & () \end{array}$ $C_{e - 1, s}$ will be defined in the course of our construction, but is c.e. The $U_{e, i}$ ’s are taken from our listing of uniformly c.e. sequences of sets. As all sets involved are c.e., and we only ask whether a c.e. set has partial density exceeding some lower bound, () is a $Σ_{1}^{0}$ sentence, and thus decidable by $\emptyset^{'}$ .

Putting () in context, we understand it to say that there are n elements of our weak array ${U_{e, i}}$ , not including any with index less than r, which all have high partial density (exceeding $d_{e}$ ) at a single point $t > s$ , where t is chosen from some c.e. set $C_{e - 1}$ of possibilities. Clearly, this sentence is vacuously true for $n = 0$ , and (presuming our $U_{e, i}$ ’s to be disjoint) necessarily false for $n > \frac{1}{d_{e}}$ . Therefore, for any fixed r and e, the maximum n for which this sentence holds is computable in $\emptyset^{'}$ by a simple bounded search; let us refer to it as N. If we have N such elements of a weak array, we refer to them together as a maximal tuple for that array under the conditions $C_{e - 1}$ , r, and e.

If we have a maximal tuple for our weak array, and $U_{e, k}$ is not among its members, then we know that $ρ_{t} (U_{e, k}) < d_{e}$ for some $t \in C_{e - 1}$ with $t > s$ . Otherwise, () would be satisfied with $n = N + 1$ . This will be our primary tool for controlling the lower density of the sets we omit as we build A to avoid meeting the weak array ${U_{e, i}}_{i = 0}^{\infty}$ .

Organization:

As we combine multiple negative requirements, we allow finite injury of each negative requirement by higher-priority requirements, though never revoking any previous decisions as to whether $s \in A$ . We activate the requirements in order of decreasing priority, activating at most one at each stage. At stage s, each active requirement independently decides whether to allow s into A; we put s into A if none of these requirements object. For convenience, we denote $A ↾ s$ by $A_{s}$ .

Each requirement $N_{e}$ will maintain a c.e. set $S_{e, s}$ of elements such that, if $A \cap S_{e, s} = \emptyset$ , then $N_{e}$ will be satisfied. For internal reference, we will also keep track of $k_{e, s}$ , which determines which element of the weak array ${U_{e, i}}$ we are actually restricting out of A. Lastly, we will maintain a c.e. set $C_{e, s}$ of locations where the partial density of $U_{e, k_{e, s}}$ is known to be strictly less than $2^{- e - 3} ε$ , while guaranteeing that $C_{e, s} \subseteq C_{e - 1, s}$ at all stages s.

$N_{e}$ ’s basic goal is to prevent the weak array ${U_{e, i}}$ from meeting A, while ensuring that the lower density of its restricted set does not exceed $d_{e} = 2^{- e - 3} ε$ . To do so, $N_{e}$ will repeatedly consult $\emptyset^{'}$ regarding (). In context, we can now see that we choose $t \in C_{e - 1, s}$ to ensure that the density of the set we omit for $N_{e}$ falls below $d_{e}$ at the same time as the densities of the previously-chosen sets fall below their critical values; this will make certain that the density of our set A rises above its goal of $1 - ε$ .

Module for* $N_{e}$ :

On activation at stage s: We first consult $\emptyset^{'}$ , asking whether the sets ${U_{e, i}}$ are in fact pairwise disjoint (i.e., ${U_{e, i}}$ is a weak array). If not, then $N_{e}$ is trivially satisfied. In this case, $N_{e}$ will never restrict anything out of A; it simply maintains $S_{e, t} = \emptyset$ and $C_{e, t} = C_{e - 1, t}$ at all stages $t ⩾ s$ , while voting to allow all elements into A.

If ${U_{e, i}}$ is a weak array, we define $k_{e, s - 1}$ to be the least k such that $U_{e, k} ↾ s = \emptyset$ . We then set $S_{e, s - 1} = U_{e, k_{e, s - 1}}$ , and let $C_{e, s - 1} = \emptyset$ , as we do not yet know of any locations where $ρ_{t} (S_{e, s}) < d_{e}$ .

At stage s: We assume that $A_{s} = A ↾ s$ has already been determined, and consider only whether to allow s into A. Before making this decision, we must first determine whether we can still believe that we can restrict $S_{e, s - 1}$ out of A while keeping $\overline{ρ} (A)$ close to 1. In fact, we want to verify that $S_{e, s - 1}$ will again appear to have partial density less than $d_{e}$ at some point $t > s$ where the partial density of $S_{i, s}$ (for all $i < e$ ) is also small.

If $C_{e, s - 1} \cap (s, \infty) \neq \emptyset$ (a $\emptyset^{'}$ -computable question), we have already verified this at some previous stage. We simply define $S_{e, s} = S_{e, s - 1}$ , set $k_{e, s} = k_{e, s - 1}$ , and let $C_{e, s} = C_{e, s - 1}$ . We then allow s into A iff $s \notin S_{e, s}$ .

If $C_{e, s - 1} \subseteq [0, s]$ , though, we must attempt to verify that the partial density of $S_{e, s - 1}$ will fall below $d_{e}$ at some point in the future. We know that $\emptyset^{'}$ cannot answer this question directly, as it cannot determine whether a c.e. set will ever have partial density less than some critical value. We instead use () to attack from a different angle. We will need to reference $k_{e, s - 1}$ several times in the remainder of the procedure; for simplicity’s sake, we will abbreviate it by $k = k_{e, s - 1}$ .

We first determine $n_{e, s}$ , the greatest value of n for which () holds with $r = k$ . Since at most $⌊ 1 / d_{e} ⌋$ disjoint sets can have partial density exceeding $d_{e}$ at the same location t, this is a bounded search on a parameter of a $Σ_{1}^{0}$ statement; thus, $\emptyset^{'}$ suffices to compute $n_{e, s}$ .

We then ask $\emptyset^{'}$ whether () holds with $n = n_{e, s}$ and $r = k + 1$ . If so, then we have a maximal tuple (within the array ${U_{e, i}}$ for $i > k$ ) in which every set has high partial density at the same point $t > s$ . Since we cannot add $U_{e, k}$ to this collection, we must have $ρ_{t} (U_{e, k}) < d_{e}$ . We define $C_{e, s}$ to be the set of all $t > s$ for which there is such a collection (along with all $t ⩽ s$ for which $ρ_{t} (S_{e, s}) < d_{e}$ ), set $k_{e, s} = k_{e, s - 1}$ and $S_{e, s} = S_{e, s - 1}$ , and allow s into A iff $s \notin S_{e, s}$ . If this case occurs immediately following injury or initialization of $N_{e}$ at stage $s - 1$ , we say that s was a “recovery stage” for $N_{e}$ ; otherwise, we deactivate all lower-priority requirements $N_{i}$ ( $i > e$ ), as $C_{e, s}$ has changed.

Otherwise, the () does not hold with $n = n_{e, s}$ and $x_{1}$ strictly greater than k. In this case, we have no way to verify that the density of $U_{e, k}$ again drops below $d_{e}$ , and so consider $N_{e}$ to be injured. We vote to allow s into A, and deactivate all lower-priority requirements $N_{i}$ ( $i > e$ ). We then effectively reset our procedure for $N_{e}$ ; we define $k_{e, s}$ to be the least $k > k_{e, s - 1}$ such that $U_{e, k} \cap [0, s] = \emptyset$ , set $S_{e, s} = (S_{e, s - 1} \cap [0, s)) \cup U_{e, k},$ and let $C_{e, s} = \emptyset$ .

Verification of the basic module:

Suppose that the module for $N_{e}$ is at some point activated and never again deactivated (i.e., $C_{e - 1, s}$ does not change at any later stage s). We assume that ${U_{e, i}}$ is in fact a weak array; if it is not, $N_{e}$ is trivially satisfied, $S_{e, s} = \emptyset$ has partial density identically 0 for all s, and $C_{e, s} = C_{e - 1, s}$ does not change at any later stage s.

By the construction of $S_{e, s}$ , we know that $S_{e} = {lim}_{s \to \infty} S_{e, s}$ exists, and consists of all elements restricted out of A by $N_{e}$ . We will show that there is some stage $s_{0}$ at which $C_{e, s_{0}}$ is infinite, thus ensuring that $C_{e, s}$ will not change at any later stage and preventing future injury to $N_{e}$ . This will also guarantee that $S_{e} = S_{e, s_{0}}$ and $k_{e} = {lim}_{s \to \infty} k_{e, s} = k_{e, s_{0}}$ .

Given such an $s_{0}$ , since A does not intersect $S_{e, s_{0}} \supseteq U_{e, k_{e}}$ , we have satisfied $N_{e}$ . Furthermore, the partial density of $S_{e}$ approaches that of $U_{e, k_{e}}$ , as the sets agree on all $x ⩾ s_{0}$ ; therefore, if the partial density of $U_{e, k_{e}}$ drops below $d_{e}$ infinitely often, the partial density of $S_{e} = S_{e, s_{0}}$ must be less than $2 d_{e}$ at all but finitely many of the same points.

We note that the sequence ${n_{e, s}}$ is nonincreasing, as we monotonically reduce the set of witnesses for () at successive stages s. In fact, the sequence must decrease each time $C_{e, s}$ changes (except at recovery stages); this can only happen when we have run out of witnessing collections of size $n_{e, s - 1}$ . As for recovery stages, they can only occur immediately after initialization of $N_{e}$ , or immediately after an injury to $N_{e}$ ; since injuries cause $n_{e, s}$ to decrease, any recovery stage is still associated with a corresponding decrease in $n_{e, s}$ . Since for $n = 0$ , () is vacuously true, $n_{e, s}$ is always a non-negative integer and so cannot decrease infinitely often. Therefore, there must be some stage $s_{0}$ such that $C_{e, t} = C_{e, s_{0}} \neq \emptyset$ for all $t > s_{0}$ , which is only possible if $C_{e, s_{0}}$ is infinite.

Lastly, the module must force $A \cap S_{e} = \emptyset$ . Whenever we choose a new $k_{e, s}$ , we always choose a value k such that $A_{s} \cap U_{e, k} = \emptyset$ , and redefine $S_{e, s}$ accordingly to remain disjoint from $A_{s}$ . When we keep the same k, we allow elements into A iff they are not in $S_{e, s}$ . Therefore, as long as $N_{e}$ is active, we are assured that $A_{s} \cap S_{e, s} = \emptyset$ for all s; since $S_{e} ↾ s = S_{e, s} ↾ s$ , we will always have $A \cap S_{e} = \emptyset$ .

Construction of A:

At stage 0, begin by activating $N_{0}$ .

At stage s, check whether $ρ_{s} (A) ⩾ 1 - ε$ . If so, determine the highest-priority inactive requirement $N_{e}$ . If $N_{e}$ was deactivated in stage $s - 1$ , do not activate any requirements; otherwise, activate $N_{e}$ . (This delay in $N_{e}$ ’s reactivation ensures that $N_{e}$ is not activated during a recovery stage for $N_{e - 1}$ .)

Next, consult all active requirements in priority order. If any restrict s out of A, we declare that $s \notin A$ ; if all allow s to enter A, we put s into A.

Verification:

Nothing can deactivate $N_{0}$ , so $N_{0}$ is permanently activated. By the correctness of the basic module, if the module for $N_{e}$ is permanently activated, $N_{e}$ will be satisfied. Furthermore, there is some stage $s_{0}$ after which $C_{e, s}$ does not change, so that $N_{e + 1}$ will never again be deactivated. Therefore, as long as there are infinitely many stages at which we activate some inactive requirement, every module will be permanently activated at some point, and thus every $N_{e}$ will be satisfied.

Suppose, towards a contradiction, that some requirement is never permanently activated. Let $N_{e}$ be the highest-priority such requirement, so that only modules $N_{0}$ through $N_{e - 1}$ are permanently activated. We consider the construction at stage $s_{0}$ , after the last such module has been permanently activated and $C_{e - 1, s}$ has stopped changing (and is infinite).

At this stage, $N_{e}$ can never again be deactivated, so since $N_{e}$ is not permanently activated, $N_{e}$ must never again be activated. This can only be because the construction will never reach another stage where it activates the highest-priority inactive requirement; therefore, it must be that $A \cap (s, \infty)$ contains all elements except those in $S = ⋃_{i < e} S_{i}$ , and $ρ_{t} (A) < 1 - ε$ for all $t > s$ . For all sufficiently large n, we have that $ρ_{n} (A) < 1 - ε$ implies $ρ_{n} (S) > \frac{1}{2} ε$ ; thus, $ρ_{n} (S) > \frac{1}{2} ε$ for all sufficiently large n.

However, $ρ_{n} (S) = ρ_{n} (⋃_{i < e} S_{i}) ⩽ \sum_{i < e} ρ_{n} (S_{i})$ . Recall that for all but finitely many $n \in C_{e - 1}$ , we have $ρ_{n} (S_{i}) < 2 d_{e} = 2^{- n - 2} ε$ , so $ρ_{n} (S) ⩽ \sum_{i < e} 2^{- i - 2} ε < \frac{1}{2} ε .$ Since $C_{e - 1}$ is infinite, this is a contradiction; therefore, all modules $N_{e}$ must be permanently activated eventually.

Finally, since every module is eventually activated, we must activate a new module infinitely often. This can only happen if $ρ_{s} (A) ⩾ 1 - ε$ infinitely often, so every requirement $P_{e}$ is also satisfied; A must have upper density at least $1 - ε$ . □

We have yet to consider implications in the other direction; what immunity properties are implied by intrinsic density 0? The first such result is simple; as established above in Corollary 3.2, intrinsic density 0 at least implies immunity for infinite sets.

On the other hand, we already know that hyperimmunity (even shh-immunity) does not imply intrinsic density 0. We can further prove that a set of intrinsic density 0 need not be hyperimmune; we can construct $Δ_{2}^{0}$ counterexamples, and in fact will build a counterexample below every 1-random set.
Theorem 3.10.
For every 1-random set R, there is an infinite set $A ⩽_{T} R$ with intrinsic density 0 that is not hyperimmune.
Proof.
Suppose that $K (R ↾ n) ⩾ n - c$ for all n.

By van Lambalgen’s Theorem [23], given a 1-random set R, there exists a uniformly R-computable sequence of sets ${R_{j}}_{j \in ω}$ that are mutually relatively 1-random. In fact, defining ${\hat{R}}_{j} = ⨁_{i < j} R_{i}$ , we have that $K^{{\hat{R}}_{j}} (R_{j} ↾ n) ⩾ n - d_{j}$ for all n, where $d_{j}$ is uniformly computable from j and c; this can be shown by a simple inspection of a proof of van Lambalgen’s Theorem.

Let $A_{0} = R_{0}$ . Since $A_{0}$ is 1-random, it has intrinsic density $\frac{1}{2}$ . Given $d_{0}$ and using the incompressibility of $R_{0}$ , we can compute $k_{0}$ such that $| R_{0} ↾ k_{0} | ⩾ 1$ , ensuring that $A_{0} \cap [0, k_{0}) \neq \emptyset$ . Since $k_{0}$ is computable, we can use $[0, k_{0})$ as the first partition in a weak array that will witness that the set we construct A is not hyperimmune.

We then define $A_{1} = A_{0} \cap ([0, k_{0}) \cup R_{1}) .$ Since $A_{1} =^{} R_{0} \cap R_{1}$ , and $R_{0}$ and $R_{1}$ are mutually relatively 1-random, $A_{1}$ must have intrinsic density $\frac{1}{4}$ by Corollary 2.7. Using $d_{0}$ and $d_{1}$ along with the incompressibility of $R_{1}$ (relative to $R_{0}$ ), we can compute $k_{1}$ such that $| A_{1} \cap [k_{0}, k_{1}) | \neq \emptyset$ .

Repeating this process, we see that $A = ⋂_{j} A_{j}$ is computable in R, since $A ↾ k_{j} = A_{j} ↾ k_{j}$ . For all j, we have that $A \cap [k_{j - 1}, k_{j}) \neq \emptyset$ , so A is infinite. Furthermore, since the $k_{j}$ ’s are uniformly computable from c, an integer, this partition of ω is in fact computable, demonstrating that A is not hyperimmune.

Finally, $A \subseteq A_{j}$ for all j. Since $A_{j} =^{} ⋂_{i ⩽ j} R_{i}$ , and the $R_{i}$ ’s are mutually relatively 1-random, $A_{j}$ has intrinsic density $2^{- j - 1}$ ; therefore, A must have intrinsic density 0. □

As a convenient side effect, this theorem immediately gives us some information on the Turing degrees of infinite sets with intrinsic density 0: such sets exist below every 1-random Turing degree, but cannot be computable. Among other things, this implies that there are infinite id0 sets in non-computable $Δ_{2}^{0}$ , low, and even hyperimmune-free degrees (where our construction of a non-hyperimmune A becomes rather superfluous, though it at least ensures that A is infinite).

It still eliminates any hopes we might have of further positive implications between the immunity properties and intrinsic density, as we will discuss in our summary below. By falling back to intrinsic lower density, we can recover one more positive implication, as shown by Jockusch in private correspondence.
Theorem 3.11.
Every hyperimmune set has intrinsic lower density 0.
Proof.
Since hyperimmunity is computably invariant, it suffices to show that every hyperimmune set has lower density 0.

Suppose A is hyperimmune. Consider the strong array $D_{n} = [n!, (n + 1)!) .$ Since A is hyperimmune, $A \cap D_{n} = \emptyset$ for infinitely many n. For all such n, we have that $| A ↾ (n + 1)! | ⩽ n!$ ; therefore, $ρ_{(n + 1)!} (A) ⩽ \frac{1}{n}$ . Since this occurs infinitely often, we conclude that $\underline{ρ} (A) = 0$ . □

The above results, along with earlier work [10], [6], will suffice to disprove all other potential implications between intrinsic density 0, intrinsic lower density 0, and the standard immunity properties.

We first repeat, per Jockusch and Schupp [10], that any 1-generic set has lower density 0 and upper density 1; since 1-genericity is computably invariant, 1-generics in fact have intrinsic lower density 0 and intrinsic upper density 1. Therefore, intrinsic lower density 0 does not imply intrinsic density 0, even for $Δ_{2}^{0}$ sets.

In addition, all 1-random sets are immune; otherwise, there would be a 1-random R with an infinite computable subset, which admits a trivial computable martingale that succeeds on R. Since 1-randoms have intrinsic density $\frac{1}{2}$ , immunity does not imply intrinsic lower density 0, even for $Δ_{2}^{0}$ sets.

Lastly, Theorem 3.9 above demonstrates that for every $ε > 0$ , there is a shh-immune set (in fact, a $Δ_{2}^{0}$ hh-immune set) with upper density at least $1 - ε$ . In particular, shh-immunity does not imply intrinsic density 0, even for $Δ_{2}^{0}$ sets.

Figure 2.
The graph of implications between the classical immunity properties and intrinsic density 0. Again, for $Δ_{2}^{0}$ sets, shh-immunity and hh-immunity become equivalent; all other implications are as depicted. (We abbreviate intrinsic [lower] density 0 for infinite sets by I[L]D0.)

Combining these counterexamples with our results above, we exhaust all possible implications between intrinsic density 0, intrinsic lower density 0, and the standard immunity properties. The graph of the resulting implications for infinite sets is shown in Fig. 2; all implications depicted are strict, and counterexamples are discussed above for all arrows not present in the diagram.

Unfortunately, in the co-c.e. case (well-studied due to Post’s Program), the majority of our proofs of failures of implication collapse. Since hh-immunity does imply dense immunity for co-c.e. sets, it seems unlikely that our proof method from Theorem 3.9 will help separate the higher immunity properties from intrinsic density 0. In fact, most of our other failures of implication are exhibited by 1-generics or derived from 1-randoms, examples that are inherently not co-c.e. This leaves the co-c.e. diagram incomplete, with a few interesting open questions.
Open Question 3.1.
Is there an infinite c.e. set with intrinsic density 1 that is not hypersimple? (f)sh-simple?
Open Question 3.2.
Is there a hypersimple set with lower density less than 1? Equal to 0? For all $ε > 0$ , is there a hypersimple set with lower density less than ε?
4. Intrinsic density and randomness

Let us move from the extremes of density (density 0 or 1) to the intermediate densities, as exemplified by density $\frac{1}{2}$ .

The notion of “density $\frac{1}{2}$ ” is easily recognized as the Law of Large Numbers, as applied to a sequence of flips of a fair coin. We might hope that having density $\frac{1}{2}$ would be in some way related to a randomness-theoretic property, and stochasticity is the obvious candidate. This follows von Mises [24] in establishing the existence of limiting frequencies as the key property of a random sequence and, more specifically, the preservation of limiting frequencies under place-selection rules that determine the next bit sampled based only on the values previously sampled. If $C$ is such a class of selection rules, we say that a sequence S is $C$ -stochastic if no selection rule in $C$ can select a biased (non-density- $\frac{1}{2}$ ) subsequence from S. We say that a selection rule is monotonic if the places it selects are always in increasing order, and oblivious if the places it selects are independent of S, the sequence subject to the selection rule.

There are several standard notions of stochasticity that will be useful to keep in mind. Church-stochastic sequences are stochastic under computable monotonic selection rules, whereas von Mises–Wald–Church-stochastic sequences are stochastic under partial computable monotonic selection rules. By this definition, sets with density $\frac{1}{2}$ might be termed “trivially stochastic”; that is to say, they are unbiased under the single selection rule that selects all positions in order. However, this is rarely considered, as stochasticity is generally taken to require selection of proper subsequences.

Passing to intrinsic density $\frac{1}{2}$ , we find something more practical: stochasticity under the class of all computable permutations, represented as oblivious selection rules. In fact, this is the class of non-monotonic oblivious selection rules that must eventually select every position. The corresponding notion of randomness, that no computable martingale succeeds on the sequence of bits selected by such a rule, is permutation randomness as defined by Miller and Nies [15]; intrinsic density $\frac{1}{2}$ is thus the natural notion of permutation stochasticity.

As mentioned above, stochasticity is generally taken to require selection of proper subsequences to preserve density $\frac{1}{2}$ ; this would seem to be an obstacle to considering intrinsic density $\frac{1}{2}$ as a valid notion of stochasticity. Fortunately, permutation stochasticity in fact ensures that many proper subsequences are also unbiased, including all computably-sampled subsequences. We can be fully precise about this with one more definition in hand, and a combinatorial lemma to relate it to our previous work.

Definition 4.1.
Given a total computable injection p and an infinite binary sequence $X (n)$ , we say that the subsequence of X sampled by p is $p^{- 1} (S) = {X (p (n))}_{n \in ω} .$ Abusing notation as noted in the introduction, we can apply this directly to any set $S \subseteq ω$ . In set notation, this gives $p^{- 1} (S) = {n \in ω : p (n) \in S} .$

However, even though this new method of sampling generalizes our previous method of considering sets under computable permutations of ω, it has no additional power as far as density is concerned.
Lemma 4.2.
Given any total computable injection p, there is a computable permutation π such that, for any set S, $π^{- 1} (S)$ has upper and lower density equal to those of $p^{- 1} (S)$ .
Proof.
Given a total computable injection p, we define a computable permutation π by assigning values $π (j)$ in increasing order of j. If j is a non-square integer, and $p (j)$ has not already been assigned to $π (i)$ for some $i < j$ , define $π (j) = p (j)$ . Otherwise, define $π (j)$ to be the least value not assigned to any $π (i)$ with $i < j$ .

The sizes of $π ([0, n)) \cap S$ and $p ([0, n)) \cap S$ differ by at most $⌈ \sqrt{n} ⌉$ . Thus, $ρ_{n} (π^{- 1} (S))$ differs from $ρ_{n} (p^{- 1} (S))$ by less than $\frac{2}{\sqrt{n}}$ . Therefore, $\underset{n \to \infty}{lim sup} ρ_{n} (π^{- 1} (S)) = \underset{n \to \infty}{lim sup} ρ_{n} (p^{- 1} (S))$ and $\underset{n \to \infty}{lim inf} ρ_{n} (π^{- 1} (S)) = \underset{n \to \infty}{lim inf} ρ_{n} (p^{- 1} (S)) .$ □

From this minor lemma, we note that in fact, any set with intrinsic density has constant density not only under all computable permutations of ω, but also under all computable “samplings” of ω. To be more precise:
Corollary 4.3.
A set A has intrinsic density d iff $ρ (p^{- 1} (A)) = d$ for every total computable injection p.
Proof.
The reverse direction is obvious by definition, since computable permutations of ω are also total computable injections.

The forward direction is, at this point, also quite straightforward. Fix a total computable injection p. By Lemma 4.2, there is a computable permutation π such that $π^{- 1} (S)$ has the same upper and lower densities as $p^{- 1} (S)$ for any set S, and in particular for A. Since A has intrinsic density d, we know that $ρ (π^{- 1} (A)) = d$ , and so that $ρ (p^{- 1} (A)) = d$ . □

This corollary reveals that intrinsic density $\frac{1}{2}$ coincides with another form of stochasticity: stochasticity under all computable injections, or equivalently the class of all oblivious non-monotonic selection rules. The corresponding notion of randomness is injection randomness, also as defined by Miller and Nies [15]. Thus, we see that:
Corollary 4.4.
Permutation stochasticity and injection stochasticity coincide, and are both equivalent to intrinsic density $\frac{1}{2}$ .

Considering this interpretation of intermediate intrinsic densities (strictly between 0 and 1) as a form of stochasticity, we find that intrinsic density provides an interesting link between the immunity properties and randomness-theoretic ideas. As discussed above, intrinsic density 0 is an immunity-type property, and so intrinsic density 1 is a form of co-immunity (or, as it is called for c.e. sets, simplicity). Thus, intrinsic density illustrates the relations between immunity, randomness and simplicity, and provides a continuum of intermediate concepts, all of which follow in the spirit of stochasticity as established by von Mises. This calls our attention to the fact that all of these properties are, in essence, descriptions of unpredictability: a set is immune if it is sufficiently difficult for a computable enumeration to stay within the set, co-immune if it is difficult to avoid the set, and stochastic if it is difficult to achieve any sort of persistent pattern of biased intersection with the set or its complement.

Of course, all of this relies fundamentally on our use of intrinsic density. Considering asymptotic density alone, we find no useful connection to computability or randomness. A set with density 0 need not be immune in any useful sense, as is made clear by considering the computable set of perfect squares. Taking the complement, we obtain a set with density 1 that is trivial to avoid. Moreover, density $\frac{1}{2}$ is a poor notion of randomness, as recognized by and before von Mises, carrying no real implications for unpredictability; for instance, the set of even numbers is “stochastic” in this sense, and yet is trivially predictable.
5. Strong variants of generic-case computability

Having begun by investigating the implications of adding computable invariance to asymptotic density, we end by returning to the motivating problem with which we began: strengthening Jockusch and Schupp’s generic-case computability to obtain similar invariance. They defined generic-case computability as follows:

Definition 5.1.

A partial function $f : ω \to {0, 1}$ is a partial description of $A \subset ω$ if $f (n) = A (n)$ whenever $f (n)$ converges.

We say that $A \subseteq ω$ is computable in the generic case, or generic-case computable, if A has a computable partial description with density-1 domain. We call such a description a generic-case description [10].

In practical terms, the weakness of generic-case computability was shown by Hamkins and Miasnikov [8], who demonstrated that, in several reasonable codings, the halting problem is in fact decidable on a set of asymptotic density 1, due to the density of trivially non-halting programs. This suggests that we should strengthen generic-case computability, to avoid rendering the halting problem “decidable” for trivial reasons.

Rybalov [20] has shown that if we insist on convergence on a set with density exponentially approaching 1 (also known as strong generic-case computability), then the halting problem is instead undecidable. Of course, his analysis makes use of asymptotic density on the set of Turing programs, considering the programs with at most n non-final states; strong generic-case computability is not directly applicable to arbitrary subsets of ω, so we must look for an alternative approach.

Furthermore, Corollary 1.4 has a somewhat unfortunate consequence for generic-case computability. For any problem, if there is an algorithm that converges on an infinite set of inputs, that algorithm becomes a generic-case solution for the problem under some alternate coding of the input. After all, the domain of the algorithm is necessarily c.e.; there is therefore some coding of the underlying problem (corresponding to a permutation of ω) under which the algorithm converges on a set of density 1. In other words, most natural problems have generic-case computable solutions (as defined by Jockusch and Schupp [10]) under some computable permutation. This gives us another reason to use a stricter notion of generic-case computability.

Returning to the original definition of generic-case complexity for group-theoretic problems, from Kapovich, Myasnikov, Schupp and Shpilrain [12], we note that the authors defined a problem in a finitely generated group to have generic-case complexity $C$ if and only if this complexity is independent of the choice of generating set. They specifically state that, though the worst-case complexity for most group-theoretic problems does not depend on one’s choice of generating set, there is no reason to assume that this should also hold for generic-case complexity. As this choice directly corresponds to a coding of the input to the generic-case algorithm, a natural translation would require that our set be generic-case computable under every computable permutation of ω. Equivalently, by the Myhill Isomorphism Theorem, A should not be considered generic-case decidable unless all of the 1-equivalent sets are as well. Fortunately, this coincides with the standard idea that most computability-theoretic definitions are (or “should be”) invariant under computable permutation.

We will call this new notion intrinsic generic-case computability, as it must be preserved under computable permutations of ω. Below, we propose four definitions, varying in degree of uniformity.

Our weakest candidate notion of intrinsic generic-case computability is the direct translation of the definition by Kapovich, Myasnikov, Schupp and Shpilrain:

Definition 5.2.

A set A is (weakly) intrinsically generic-case computable iff $π (A)$ is generic-case computable for every computable permutation $π : ω \to ω$ .

Note that we place no requirements on the relationships between the generic-case descriptions for each such image $π (A)$ ; the algorithms may be essentially unrelated.

Insisting on a bare minimum of uniformity, we obtain our next candidate definition:

Definition 5.3.

A set A is (uniformly) intrinsically generic-case computable iff there is a uniformly computable family of functions $f_{e}$ such that, if $φ_{e}$ is a computable permutation, $f_{e}$ is a generic-case description of $φ_{e} (A)$ ; that is, $f_{e}$ has density-1 domain and wherever $f_{e} (n)$ converges, it converges to $(φ_{e} (A)) (n)$ .

On the other hand, allowing our description to require an index may weaken our notion of uniformity; after all, this means that our description f cannot be given only a black-box oracle specifying the computable permutation, but actually requires knowledge of how the permutation can be computed – and in particular may depend on the specific program provided to compute the permutation.

Requiring the description to work with only an oracle might seem a trivial variation, but significant differences have been observed in analogous situations; specifically, in computable model theory, the index-based definition of uniform computable categoricity has been shown to be strictly weaker (and less natural) than the definition providing only an oracle. [4] (In general, any oracle-based definition must be at least as strong as the corresponding index-based definition, since it is well-established that there is a Turing-machine procedure allowing us to convert an index into an effective oracle.) We therefore include this option in our list of candidate notions. In this case, we would say that:

Definition 5.4.

A set A is (oracle) intrinsically generic-case computable iff there is a Turing functional $Φ^{X}$ such that, for any computable permutation π (represented as a set of pairs), $Φ^{π}$ is a generic-case description of $π (A)$ .

Finally, we might insist on complete uniformity, and require that a single algorithm provide a description of A on a set that has density 1 under all computable permutations; in other words, that the algorithm converge on a set of intrinsic density 1.

Definition 5.5.

A set A is (strongly) intrinsically generic-case computable iff it has a description $φ_{e}$ that converges on a set of intrinsic density 1. (Equivalently, $φ_{e} \circ π^{- 1}$ is a generic-case description of $π (A)$ for all computable permutations π.)

Since r-maximal sets are c.e. and have intrinsic density 1, any r-maximal set is in fact strongly intrinsically generic-case computable. This provides a convenient demonstration that even this strongest definition is weaker than ordinary computability.

More work will be required to distinguish these definitions of intrinsic generic-case computability, and some of them may prove to be equivalent. At this point, though, there are no reasons to presume any equivalences. The author personally expects that the uniform and strong definitions of intrinsic generic-case computability will be the most useful of these four.

On the other hand, even our weakest definition has a certain demonstrable strength. A set $S \subseteq ω$ is said to be an index set if $S (e) = S (e^{'})$ for all $e, e^{'} \in ω$ where e and $e^{'}$ are indices for equivalent Turing machines. Rice’s Theorem [19] states that the only computable index sets are ∅ and ω. We can easily extend this to intrinsic generic-case computability, showing that no non-trivial index set can be weakly intrinsically generic-case computable. Therefore, the halting problem is not intrinsically generic-case computable under any of these definitions.

Theorem 5.6.

Suppose $S \subseteq ω$ is an index set (i.e., $S (e) = S (e^{'})$ for all e, $e^{'}$ such that $φ_{e} = φ_{e^{'}}$ ) . $π (S)$ is generic-case computable for all computable permutations π iff S is computable, and thus iff $S = \emptyset$ or $S = ω$ .

Sketch of proof.

The reverse implication is obvious; we will only consider the forward implication.

By the Padding Lemma for Turing machines [21], for any e, we can enumerate a set ${x_{e, 0} = e, x_{e, 1}, \dots}$ such that $φ_{e} = φ_{x_{e, i}}$ for all i. Consider the computable sets $R_{e} = {2^{e} m ∣ m odd}$ , and note that $ρ (R_{e}) = 2^{- e - 1}$ ; these, along with the singleton ${0}$ , comprise a partition of ω. One can easily construct a computable permutation of ω such that $π^{- 1} (R_{e + 1}) \subseteq {x_{e, 1}, x_{e, 2}, \dots}$ for all e, and $R_{0}$ is filled with the “waste” of the process.

Suppose $π (S)$ is generic-case computable, with generic-case description Ψ. Since $R_{e + 1}$ has positive density for all e, there must be some $k_{e} \in R_{e + 1}$ for which $Ψ (k_{e})$ converges. To determine whether $e \in S$ , wait until $Ψ (k_{e})$ converges for some such $k_{e}$ ; we then have $S (e) = S (π^{- 1} (k_{e})) = Ψ (k_{e})$ , since $φ_{π^{- 1} (k_{e})} = φ_{e}$ . This shows that S is computable, so by Rice’s Theorem, $S = \emptyset$ or $S = ω$ . □

Corollary 5.7.

The halting problem is not (weakly) intrinsically generic-case computable.

Proof.

The halting problem is 1-equivalent to a non-computable index set (e.g. , ${e ∣ (\exists x) [φ_{e} (x) ↓]}$ ). By the Myhill Isomorphism Theorem [16], this means that its image under some computable permutation is a non-computable index set. Composing this with the permutation from the proof of Theorem 5.6, we obtain a computable permutation under which the image of the halting problem is not generic-case computable. Thus, the halting problem is not even weakly intrinsically generic-case computable. □

Footnotes

Acknowledgements

Significant thanks are owed to Denis Hirschfeldt and Robert Soare for innumerable helpful discussions on both the broad strokes and details of the work found herein; in particular, the proof of Theorem is based on an approach suggested by Hirschfeldt. The author is also grateful to Carl Jockusch, Paul Schupp and Rod Downey, for the work that inspired this research and for several conversations on the specifics of this investigation, and to an anonymous referee, whose suggestions have added substantial clarity to this paper.

References

[1]

Bienvenu,

A.R.

Day and

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

[2]

S.B.

Cooper, Jump equivalence of the

Δ_{2}^{0}

hyperhyperimmune sets, The Journal of Symbolic Logic 37(3) (1972), 598–600.

[3]

R.G.

Downey and

D.R.

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

[4]

R.G.

Downey,

D.R.

Hirschfeldt and

Khoussainov, Uniformity in computable structure theory, Algebra and Logic 42(5) (2003), 318–332.

[5]

R.G.

Downey,

C.G.

JockuschJr.,

T.H.

McNicholl and

P.E.

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

[6]

R.G.

Downey,

C.G.

JockuschJr. and

P.E.

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

[7]

Gurevich, Average case completeness, Journal of Computer and System Sciences 42(3) (1991), 346–398.

[8]

J.D.

Hamkins and

Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame Journal of Formal Logic 47(4) (2006), 515–524.

[9]

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

10.

[10]

G.C.

JockuschJr. and

P.E.

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

11.

[11]

G.C.

JockuschJr. and

Stephan, A cohesive set which is not high, Mathematical Logic Quarterly 39(1) (1993), 515–530.

12.

[12]

Kapovich,

Myasnikov,

P.E.

Schupp and

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

13.

[13]

V.L.

KleeJr. and

G.J.

Minty, How good is the simplex algorithm?, in: Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., Sept. 1–9, 1969),

Shisha, ed., Academic Press, New York, 1972, pp. 159–175.

14.

[14]

L.A.

Levin, Average case complete problems, SIAM Journal on Computing 15(1) (1986), 285–286.

15.

[15]

J.S.

Miller and

Nies, Randomness and computability: Open questions, The Bulletin of Symbolic Logic 12(3) (2006), 390–410.

16.

[16]

J.R.

MyhillSr., Creative sets, Mathematical Logic Quarterly 1(2) (1955), 97–108.

17.

[17]

Nies, Computability and Randomness, Oxford Logic Guides, Oxford Univ. Press, 2009.

18.

[18]

E.L.

Post, Recursively enumerable sets of positive integers and their decision problems, Bulletin of the American Mathematical Society 50(5) (1944), 284–316.

19.

[19]

H.G.

Rice, Classes of recursively enumerable sets and their decision problems, Transactions of the American Mathematical Society 74(2) (1953), 358–366.

20.

[20]

Rybalov, Note: On the strongly generic undecidability of the halting problem, Theoretical Computer Science 377(1–3) (2007), 268–270.

21.

[21]

R.I.

Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer-Verlag, 1987.

22.

[22]

D.A.

Spielman and

S.-H.

Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM 51(3) (2004), 385–463.

23.

[23]

van Lambalgen, The axiomatization of randomness, The Journal of Symbolic Logic 55(3) (1990), 1143–1167.

24.

[24]

von Mises, On the foundations of probability and statistics, Annals of Mathematical Statistics 12(2) (1941), 191–205.