648 13. Algorithmic Dimension

By recursion, we define an extension (S, ε) of (T, ε) in SpΦ. We start by letting S(λ) = T (λ) and labeling this string by ε on (S, ε). Suppose that we have defined σ = S(ρ ) = T (ρ) where σ is labeled by δ on (T, ε) and by γ on (S, ε). Assume that we have carried out the construction so far so that nγ (σ) nδ(σ). For every τ of length strictly shorter than nγ (σ), we can let S(ρ τ ) = T (ρτ ) = στ (and leave it unlabeled on (S, ε)).

Let τ0, . . . , τ2n−1 be the strings of length n = nγ (σ). Enumerate the pairs of numbers i < j < 2n as (i0, j0), . . . , (im, jm). For each i 2n and k m,

This lemma completes the proof of Theorem 13.13.1.

13.14 Building sets of high packing dimension

One way in which e ective packing dimension di ers from e ective Hausdor dimension is in the absence of a correspondence principle analogous to Theorem 13.6.1. Conidis [75] built a countable Π01 class P of e ective packing dimension 1. (In fact, he built P to have a unique element of rank 1, so that all other elements of P are computable. See Section 2.19.1 for the definition of the rank of an element of a Π01 class.) Since P is countable, its classical packing dimension is 0. Note also that, by Theorem 13.6.1, the e ective Hausdor dimension of P is 0.

Theorem 13.14.1 (Conidis [75]). There is a countable Π01 class of e ective packing dimension 1.

Proof. By Lemma 13.13.2, there is a computable sequence 0 = n0 < n1 <

· · · such that for every σ 2nk , there is a τ 2nk+1 with σ τ and K(τ ) (1 − 2−k)nk+1. We build finite trees Ts 2 ns such that T0

Stage 0. Let σ0 = λ and T0 = {λ}.

Stage s + 1. If there is a least k s such that Ks(σk ) < (1 − 2−k)|σk| then redefine σk to be the leftmost extension τ 2|σk| of σk−1 on Ts such that Ks(τ ) (1 − 2−k)|τ | (which we will argue below must exist). In this case, undefine all σj for j > k.

Let k be largest such that σk is still defined and let τ be the leftmost leaf of Ts that extends σk (so that |τ | = ns). Define Ts+1 as follows. Begin by adding all extensions of τ of length ns+1. For every leaf ρ =τ of Ts, add ρ0ns+1−ns to Ts+1. Finally, close downwards to obtain a subtree of 2 ns+1 . Let σk+1 = τ 0ns+1−ns .

End of Construction.

Every time σk is defined at a stage s to extend some τ 2ns , every extension of τ of the same length as σk is added to Ts+1. Thus, by the choice of the ns, if we ever find that Ks(σk) < (1 − 2−k)|σk | then we can redefine σk as in the construction. Thus the construction never gets stuck, and it follows by induction that every σk has a final value, which we will refer to simply as σk, such that σ0 σ1 · · · and K(σk) (1 − 2−k)|σk |

for all k.

Let P = [ s Ts] and X = k σk . Then X P and Dim(X) = 1, so Dim(P ) = 1. It is easy to see from the construction that if ρ =σk and

|ρ| = |σk|, then every extension of ρ on P is eventually 0. Thus every element of P other than X is eventually 0, and hence P is countable.

Note that, in the above proof, the σk never move to the left, so the unique noncomputable element X of P is a left-c.e. real.

This result suggests that it is easier (from a computability-theoretic perspective) to build sets of high e ective packing dimension than ones of high e ective Hausdor dimension. (Theorem 13.12.1 can also be seen as evidence for this claim.) Downey and Greenberg [106] have extended Theorem 13.14.1 as follows.

Theorem 13.14.2 (Downey and Greenberg [106]). Every set A of array noncomputable degree computes a set B of e ective packing dimension 1. If A is c.e. then B can be taken to be a left-c.e. real that is the unique rank 1 element of a Π01 class.

Before proving this result, we make a few comments. The following result shows that c.e. traceable sets have packing dimension 0.

Theorem 13.14.3 (Essentially Kummer [226], see Downey and Greenberg [106]). If A is c.e. traceable, then for every computable order h, we have

C(A n) log n + h(n) + O(1).

Proof. Let A be c.e. traceable and fix a computable order h. (We may assume that h(0) > 0.) By Proposition 2.23.12, A is c.e. traceable with bound h. Let T0, T1, . . . be a c.e. trace with bound h for the function n → A n. We can describe A n by describing n and the position of A n in the enumeration of Tn, so C(A n) log n + h(n) + O(1).

Since we can choose h to be slow growing, and log n is bounded away from n, we have the following.

Corollary 13.14.4. If A is c.e. traceable then Dim(A) = 0.

650 13. Algorithmic Dimension

Combining this result with Theorem 13.14.2 and the fact that a c.e. degree is array computable iff it is c.e. traceable (Theorem 2.23.13), we have the following.

Corollary 13.14.5 (Downey and Greenberg [106]). The following are equivalent for a c.e. set A.

(i)A computes a set of positive e ective packing dimension.

(ii)A computes a set of e ective packing dimension 1.

(iii)The degree of A is array noncomputable.

Corollary 13.14.4, together with the existence of minimal degrees of packing dimension 1 (Theorem 13.9.17), implies Shore’s unpublished result that there is a minimal degree that is not c.e. traceable. As discussed in Section 2.23, Ishmukhametov [184] showed that if a degree is c.e. traceable then it has a strong minimal cover in the Turing degrees. Yates had earlier asked the still open question of whether every minimal degree has a strong minimal cover. It follows that c.e. traceability is not enough to answer this question.

Downey and Ng [129] have further sorted out the connections between high e ective packing dimension and notions such as array computability.

Theorem 13.14.6 (Downey and Ng [129]). (i) There is a degree that is not c.e. traceable but has e ective packing dimension 0.

(ii)There is a degree that is array computable but has e ective packing dimension 1.

Part (ii) follows by taking a hyperimmune-free 1-random degree and applying Proposition 2.23.10. For a proof of part (i), see [129]. The degrees in the above result can also be 02, and hence there seems to be no way to relate the degrees of packing dimension 1 with any known lowness class.

We now proceed with the proof of Theorem 13.14.2.

Proof of Theorem 13.14.2. We begin with the non-c.e. case. Recall that

fpb C means that f can be computed from oracle C by a reduction procedure with a primitive recursive bound on the use function, and that

fpb iff there is a computable function f (n, s) and a primitive recursive

function p such that lims f (n, s) = f (n) and |{s : f (n, s) =f (n, s + 1)}| p(n). Recall further that a set of strings S is pb-dense if there is a function

is pb-generic if it meets every pb-dense set of strings. Finally, recall that Theorem 2.24.22 states that if a is array noncomputable, then there is a pb-generic set B T a. Thus, it is enough to show that if B is pb-generic then Dim(B) = 1, which we now do.

It is easy to check that the map given by Lemma 13.13.2, which takes

2nε(σ) , is primitive recursive. For k > 0, let Sk = {ν 2 k : > 1 − k1 }.

a fairly simple permitting argument.15 Let A be a c.e. set of a.n.c. degree. We have requirements

for k > 0. It is enough to satisfy infinitely many of these requirements. As noted in the proof of Theorem 13.14.1, there is a computable sequence

0 = n0 < n1 < · · · such that for every σ 2nk , there is a τ 2nk+1 with σ τ and K(τ ) (1 − 2−k)nk+1. Partition N into consecutive intervals I0, I1, . . . such that |Ik| = 2nk . By Theorem 2.23.4, there is a D ≡T A such that for every c.e. set W there are infinitely many m with D ∩Im = W ∩Im.

We define B as the limit of strings σ0 σ1 · · · , which can change value during the construction. We begin with σk = 0nk for all k. We also build a c.e. set W , into which we enumerate requests for D-permission. Let uk = |I0| + |I1| + · · · + |Ik|.

At stage s, say that Rk requires attention if Ds ∩ Ik Ws ∩ Ik =Ik and Ks(σk) < (1 − 2−k)|σk|, and either

1.this is the first stage at which this inequality obtains for the current value of σk or

2.Ds+1 uk =Ds uk.

If there is a least k s such that Rk requires attention then proceed as follows. If 1 holds then put the least n Ik \ W into W . If 2 holds then redefine σk to be the leftmost extension τ 2nk of σk−1 such that Ks(τ ) (1 − 2−k)|τ | and redefine σj for j > k to be σk 0nj −nk .

15There is also a simple proof, due to Miller [personal communication], using material from Chapter 16: In Theorem 16.1.6 we will see that every a.n.c. c.e. degree contains a n. So let A be a c.e. set of

packing dimension 1. Let q < 1 be such that K(B n) qn for all su ciently large n.

We have B − B log n + 2 log log n 1 2 , so if we know B log n + 2 log log n , n log n

then we can determine whether k is in X for all k < n. Thus

C(X n) K(B log n + 2 log log n ) + K(n) + O(1) (1 + q) log n + O(log log(n)),

contradicting our choice of X.

652 13. Algorithmic Dimension

Clearly, each σk has a final value. For these final values, let B =

Since the σk move only to the right, B is a left-c.e. real. Since σk cannot change unless D changes below uk, we also have B wtt D T A.

Now suppose that D ∩ Ik = W ∩ Ik . Let t be the least stage by which all Rj for j < k have stopped requiring attention, which must exist because each Rj can require attention at most twice for each string in 2nj . It can never be the case that Ds ∩ Ik \ Ws ∩ Ik = , since then we would never again put a number into W ∩ Ik, ensuring that D ∩ Ik =W ∩ Ik . Every time we put a number into W ∩ Ik, we move σk. Since |Ik | = 2nk and σk always has length k, we never have Ws ∩ Ik = Ik. Thus, if there is an s t such that Ks(σk) < (1 − 2−k)|σk |, then Rk requires attention at stage s, and so a number enters W ∩ Ik. This number will later enter D, at which point Rk will again require attention, and σk will be redefined. Thus, for the final value of σk , we must have K(σk) (1 − 2−k)|σk |, and hence Rk is satisfied.

Since there are infinitely many k such that D ∩ Ik = W ∩ Ik , infinitely many requirements are satisfied, and hence Dim(B) = 1.

For the full result, we combine this permitting argument with the proof of Theorem 13.14.1. We have the same requirements as above. Let D, nk, and Ik be as above (except that it is convenient to have |Ik | = 2nk+1 now).

We will have strings σk as above, but now their lengths may change during the construction, as in the proof of Theorem 13.14.1. As in that proof, we will build a tree via approximations Ts. While we work above a particular value of σk, we extend all other strings of the same length by 0’s. Thus, when we redefine σk, we must move σk+1 above σk0n for some large n. This redefinition means that we now must associate some large Ij with σk+1, since we may need many permissions to ensure that K(σk+1) < (1 − 2−(k+1))|σk+1| for the final value of σk+1. The main idea of the construction is that, instead of having a fixed use uk for permitting changes to σk, we will now have a varying use uk (so we will no longer have a wtt-reduction from D). When we redefine σk , we also redefine uk to be |I0| + |I1| + · · · + |Ij−1|, where Ij is the interval now associated with Rk+1. When we seek a permission to change σk, we do so by putting numbers into every Im [uk−1, uk). This action will allow us to argue that each Im such that D ∩ Im = W ∩ Im gives us enough permissions to satisfy some requirement, and hence infinitely many requirements are satisfied.

We say that Ik is active at stage s + 1 if Ds ∩ Ik Ws ∩ Ik =Ik.

Construction.

Stage 0. Let σ0 = λ, let T0 = {λ}, and let u0 = 0.

Stage s + 1. Say that Rk requires attention if Ks(σk ) < (1 − 2−k)|σk| and either

1.this is the first stage at which this inequality obtains for the current value of σk or

2. Ds+1 uk =Ds uk.

If there is a least k s such that Rk requires attention then proceed as follows. If 1 holds then for each active Im [uk−1, uk), put the least n Im \W into W . If 2 holds then redefine σk to be the leftmost extension τ 2|σk| of σk−1 on Ts such that Ks(τ ) (1 − 2−k)|τ | (which must exist by the same reasoning as in the proof of Theorem 13.14.1), redefine uk to be |I0| + |I1| + · · · + |Is|, and undefine all σj and uj for j > k.

Now let k be largest such that σk is still defined and let τ be the leftmost leaf of Ts that extends σk (so that |τ | = ns). Define Ts+1 as follows. Begin by adding all extensions of τ of length ns+1. For every leaf ρ =τ of Ts, add

ρ0ns+1−ns to Ts+1. Finally, close downwards to obtain a subtree of 2 ns+1 . Let σk+1 = τ 0ns+1−ns and uk+1 = |I0| + |I1| + · · · + |Is+1|.

End of Construction.

Neither σk nor uk can change unless some number less than uk enters D. Since each uk has a final value, D can compute the final value of each σk, and hence can compute B.

Now suppose that D ∩ Ik = W ∩ Ik . It can never be the case that Ds ∩ Ik \ Ws ∩ Ik = , since then Ik would become inactive, and we would never again put a number into W ∩ Ik, ensuring that D ∩ Ik =W ∩ Ik . Furthermore, each time a number enters W ∩ Ik, it does so because some string σk becomes redefined. It is easy to see from the construction that in that case |σk| nk, and the strings corresponding to di erent numbers entering W ∩ Ik must be di erent. Since |Ik| = 2nk+1, we never put all of Ik into W . Thus Ik is permanently active.

Let j be such that, for the final value of uj−1 and uj , we have Ik [uj−1, uj ), and let s0 be a stage by which these final values are reached. Then all Ri for i < j must eventually stop requiring attention (since each time such a requirement redefines σi, it undefines uj ), say by stage s1 > s0. If at any stage s > s1 we have Ks(σj ) < (1 − 2−j )|σj |, then Rj will require attention. It will then put a number into W ∩ Ik. This number must later enter D, which will cause uj to change. By the choice of s0, this situation cannot happen, so in fact Ks(σj ) (1 − 2−j )|σj | for all s > s1, and hence K(σj ) (1 − 2−j )|σj |, which means that Rj is satisfied.

Since there are infinitely many k such that D ∩ Ik = W ∩ Ik and only finitely many can have Ik [uj−1, uj ) for a given j, infinitely many requirements are satisfied, and hence Dim(B) = 1.