642 13. Algorithmic Dimension

13.12Packing dimension and complexity extraction

Many of the questions we have investigated for Hausdor dimension can also be examined for packing dimension. Some of the results for e ective Hausdor dimension immediately imply the same results for e ective packing dimension, such as Greenberg and Miller’s construction in [170] of a minimal Turing degree of e ective Hausdor dimension 1 (Theorem 13.9.17), which implies the theorem of Downey and Greenberg [106] that there is a minimal degree of e ective packing dimension 1 (Theorem 13.13.1). In other ways, however, the two notions of e ective dimension are quite di erent. For instance, we will see in Section 13.14 that there is no correspondence principle for e ective packing dimension analogous to Theorem 13.6.1. Another example is Miller’s Theorem 13.8.1 that there is a Turing degree of e ective Hausdor dimension 12 , which has no analog for packing dimension.

Theorem 13.12.1 (Fortnow, Hitchcock, Pavan, Vinochandran, and Wang [150]). Let ε > 0. If Dim(A) > 0 then there is a B ≡wtt A such that

Dim(B) > 1 − ε.

Thus we conclude that there is a 0-1 law for packing dimension for weak truth table, and hence Turing, degrees. Too recently for a proof to be included in this book, Conidis [74] has shown that there is a set of positive e ective packing dimension that does not compute any sets of e ective packing dimension 1, and hence there is a Turing degree of e ective packing dimension 1 with no element of e ective packing dimension 1.

We give a new proof of Theorem 13.12.1 due to Laurent Bienvenu. It is rather simple and relies on the relationship between complexities at endpoints of intervals and their oscillations within these intervals. It is fair to say that it is along the same lines as the original, but it does not rely on the di cult result on extractors due to Barak, Impagliazzo, and Wigderson [16]13 used in the original proof.

Proof of Theorem 13.12.1. Let A be such that Dim(A) > 0. Let t > 0 be a rational such that C(A n) tn for infinitely many n. Let m be a fixed large integer.

13The original proof in [150] gave the stronger result that the set B has the same polynomial time Turing degree as A, and hence that there are 0-1 laws for low level complexity classes. However, the extractor result used in that proof (as a black box) is very complex and does not allow for a reasonable presentation in this book (its proof being over 30 pages long). The version we give here su ces for our purposes, as we do not need the result for complexity classes. Like the proof we present, the original proof is nonuniform, but in a di erent way, using a kind of binary search that identifies chunks of intervals of high complexity infinitely often. The closest we have in this book to this procedure is found in Section 13.10.

We claim that there exists a rational t > 0 such that C(A mk) t mk for infinitely many k. To see this, choose any n such that C(A n) tn. Let k be such that n [mk−1, mk). Then

C(α mk) C(α n) − O(log n) tn − O(log n)

tmk−1 − O(log n) mt mk − O(log mk).

Thus, for any t < mt , we have C(α mk) t mk for infinitely many k.

know that s > 0. Let s1 and s2 be rationals such that 0 < s1 < s < s2. By the definition of s, we have C(σk) s2|σk | for almost all k (for simplicity, we may restrict our attention to large enough k and hence assume that this condition is true for all k) and for any d, we have C(σk ) s1|σk | + d for infinitely many k.

Let V be our universal machine. Given A as an oracle, we can compute σ0, σ1, . . . and, for each k, e ectively find a τk such that V(τk) = σk and |τk| s2|σk|. Let D be the sequence given by τ0τ1τ2 . . . . It is easy to see that D wtt A. If we replace a sparse set of bits of D by the bits of A (for instance, replacing each D(2n) by A(n)) to get B, we clearly have B ≡wtt A and Dim(B) = Dim(D).

So let us evaluate Dim(D). For all k, we have C(τk ) C(σk ) − O(1), as σk can be computed from τk . Thus, for infinitely many k, we have C(τk )

proved.

On the other hand, packing dimension does have an e ect on the complexity extraction question for Hausdor dimension. The following result implies that if A is a set of positive e ective Hausdor dimension that does not compute any set of higher e ective Hausdor dimension, then A must have e ective packing dimension 1.

Theorem 13.12.2 (Bienvenu, Doty, and Stephan [38]). If Dim(A) > 0 then for each ε > 0 there is a B T A such that dim(B) − ε.

644 13. Algorithmic Dimension

Proof. We may assume that dim(A) > 0. Let s1, s2, s3, and t be rationals

proof is to split A e ectively into blocks ν = σn . . . σn+k such that K(ν) is relatively small and use these to find su ciently incompressible short prefix-free descriptions τi for the σi. We then let B = τ1τ2 . . . .

We will make several uses of the fact that

K(στ ) = K(σ) + K(σ | τ ) ± O(log |σ| + log |τ |),

K(ρ0 . . . ρn) = K(ρj | ρ0 . . . ρj−1) ± O log |ρj | .

j n j n

These facts follow easily from the symmetry of information results proved in Section 3.3. (These results are proved for plain complexity, but as pointed out in Section 3.10, also hold for prefix-free complexity because K and C agree up to a log factor.)

Suppose that we have already defined η = τ1 . . . τn−1 for ρ = σ1 . . . σn−1 so that |η| s3|ρ|. By the choice of s2, there are infinitely many k such that for ν = σn . . . σn+k, we have K(ν | ρ) s2|ν|. Fix such a k. For j k, let νj = σn . . . σn+j .

If k is large enough (so that quantities such as (s3 − s2)|ν| overwhelm the relevant log terms), then, by symmetry of information,

K(σn+i | ρνi−1

i k

and for all j k, by symmetry of information,

K(νj | ρ) K(ρνj ) − K(ρ) + O(log |ρ| + log |νj |) t(|ρ| + |νj |) − s1|ρ|,

so that, again by symmetry of information,

K(σn+i | ρνi−i) (t − s1)|ρ| + t|νj |.

i j

Given the existence of such k, we can e ectively find k and τn, . . . , τn+k such that, letting ν and νj be as above, each τn+i is a U-description of

dim(B) Dim(dim(AA)) − ε.

Fix m. Let n, k, etc. be as above so that n m n + k. Let j = m − n. The choice of the τi as appropriate U-descriptions ensures that

K(σ1 . . . σm) K(τ1 . . . τm) + O(1), so K(τ1 . . . τm) s1|σ1, . . . , σm| −

O(1). Furthermore,

|τ1 . . . τm| |η| + |τn . . . τn+j | s3|ρ| + (t − s1)|ρ| + t|νj |

Given l, let m be least such that B l τ1 . . . τm. Then |τ1 . . . τm| − l m, so K(τ1 . . . τm) K(B l) + O(m). Since m is sublinear in |τ1 . . . τm|,

13.13 Clumpy trees and minimal degrees

In this section we introduce the useful notion of clumpy trees, using them to show that there is a minimal degree of e ective packing dimension 1. This result follows from Theorem 13.9.17, of course, but can be proved using an easier method.

Theorem 13.13.1 (Downey and Greenberg [106]). There is a set of minimal Turing degree and e ective packing dimension 1.

Proof. We give a notion of forcing P such that a su ciently generic filter G P yields a set XG 2ω with e ective packing dimension 1 and minimal Turing degree.14 This notion is a modification of the standard notion of forcing with computable perfect trees due to Sacks [345]. We need to restrict the kind of perfect trees we use so that we can always choose strings that are su ciently complicated (i.e., not easily compressed), to be initial segments of the set we build. The problem, of course, is that we cannot determine e ectively which strings are su ciently incompressible, but our conditions, the trees, have to be computable. The solution to this problem relies on the following lemma.

14A notion of forcing is just a partial order P, whose elements are called conditions, and whose ordering is called extension. A filter on P is a subset F of P such that if p, q F then p, q have a common extension in P, and if p F and p extends q, then q F . A subset D of P is dense if for every p P there is a q D extending p. The filter F is generic for a collection of dense sets if it contains an element of each set in the collection. By su ciently generic we mean that F is generic for a countable collection of dense sets D0, D1, . . . that will be specified in the proof below. Such an F necessarily exists, because we can let p0 D0 and let pi+1 Di+1 extend pi, and then define F = {q P : i (pi extends q)}.

646 13. Algorithmic Dimension

let n = m − |σ|.

We denote the n corresponding to σ and ε in the above lemma by nε(σ). A perfect function tree is a map T : 2<ω → 2<ω that preserves extension and incompatibility. We write [T ] for the class of all B for which there is an A with T (A n) B for all n. Let T be a perfect function tree, σ rng T , and ε Q>0. Let ρ = T −1(σ). We say that T contains an ε-clump above σ if στ T (ρτ ) for all τ 2nε(σ). (Note that this condition implies that T (ρτ ) = στ for all τ 2<nε(σ).) The idea is that, by the above lemma, such a clump allows us to find extensions of σ on T that are fairly

incompressible.

Given a perfect function tree T and a positive rational ε, we recursively define a labeling of part of the image of T as follows.

1.Label T (λ) by ε.

2.If σ is labeled by a rational number δ, and T contains a δ-clump above σ, then for all binary strings τ of length nδ(σ), label T (ρτ ) by

2δ , where ρ = T −1(σ).

3. If T does not contain such a clump, stop the labeling process.

The tree T is called ε-clumpy if this labeling process never halts; that is, the δ-clumps required at step 2 are always present.

Let P be the collection of pairs (T, ε) where T is an ε-clumpy, computable tree. Note that P = , since the identity function is an ε-clumpy tree for all ε.

A perfect function tree S extends a perfect function tree T if there is some perfect function tree R such that S = T ◦R (where ◦ denotes composition). If (T, ε), (S, δ) P then we say that (S, δ) extends (T, ε) if S extends T and δ is the label of S(λ) on (T, ε) (in particular, we require that S(λ) be labeled on (T, ε)).

A standard example is that of full subtrees: If T is a perfect function tree and σ rng T , let Extσ(T ) = T ◦ {τ →ρτ }, where ρ = T −1(σ). If

(T, ε) P and σ rng T is labeled by δ, then (Extσ (T ), δ) is in P and extends (T, ε).

For G P, if element.

Lemma 13.13.3. If G P is a su ciently generic filter, then XG is well-defined and Dim(XG) = 1. (In particular, XG is not computable.)

δ2 on (T, ε) and (ExtT (ρτ )(T ), 2δ ) P extends (T, ε). If that condition is in G then στ T (ρτ ) XG. Thus the set of conditions that force there to

K(ν) P

be a ν XG such that | | > q is dense in .

ν

We finish by showing that if G is su ciently generic then XG has minimal Turing degree. Let Φ be a Turing functional. As usual in Sacks forcing, let

DivΦ = {(T, ε) P : x σ rng T (Φσ (x) ↑)}

and

TotΦ = {(T, ε) P : x σ rng T σ rng T (σ σ Φσ (x) ↓)}.

determined an initial segment σ of XG. It is easy to check that the labeled

Thus if we can show that TotΦ CompΦ SpΦ is dense in P, we will have shown that either ΦXG is not total, or ΦXG is computable, or ΦXG computes XG. Since Φ is arbitrary and we have already shown that XG is not computable, we can then conclude that XG has minimal degree.

Since we have already seen that TotΦ DivΦ is dense in P, it is enough to show that SpΦ CompΦ is dense below TotΦ in P. That is, every condition in TotΦ is extended by one in SpΦ CompΦ.

Lemma 13.13.4. SpΦ CompΦ is dense below TotΦ in P.

Proof. Suppose that (T, ε) TotΦ has no extension in CompΦ. Then for all σ rng T , there are σ0, σ1 rng T extending σ such that Φσ0 and Φσ1 are incompatible.