(iii)The s-dimensional outer Hausdor measure of R is Hs(R) = limn Hns (R).

This notion has been widely studied. The fundamental result is the following.

Theorem 13.1.2. For each R 2ω there is an s [0, 1] such that

(i)Ht(R) = 0 for all t > s and

(ii)Hu(R) = ∞ for all 0 u < s.

So if Hs(R) = 0 then Hns+r(R) = 0, while if Hns+r(R) = ∞ then Hs(R) =

(ii)(monotonicity) If X Y then dimH(X) dimH (Y ).

(iii)(countable stability) If P is a countable collection of subsets of 2ω,

then dimH( X P X) = supX P dimH(X). In particular, dimH(X Y ) is max{dimH(X), dimH(Y )}.

Proof sketch. This proposition is well known, but its proof is worth sketching. We begin with a lemma.

by all its extensions of length n to obtain an n-cover V of X such that

2−σ = 2−σ, so H1(X) = μ(X) for all n.

σ V σ U n

Part (i) of Proposition 13.1.4 follows immediately from the lemma. To see that part (ii) holds, take any s > dimH(Y ). Then since any n-cover of Y is an n-cover of X, we have Hns (X) Hns (Y ) for all n, so Hs(X) = 0. Part (iii) is proved by a similar manipulation of covers.

594 13. Algorithmic Dimension

13.2 Hausdor dimension via gales

The first person to e ectivize Hausdor dimension explicitly was Lutz [252, 253, 254]. To do so, he used a generalization of the notion of (super)martingale. This idea was, however, in a sense implicit in the work of Schnorr [348, 349], who used orders to calibrate the rates of success of martingales, as we have seen in Chapter 7, in much the same way that the s factor calibrates the growth rate of the measure of covers. Recall that, for a (super)martingale d and an order h, the h-success set of d is

Sh[d] = {A : lim supn d(A n) = ∞}. As we will see, the theory of Hausdor

h(n)

dimension can be developed in terms of orders on martingales, but Lutz [252, 254] originally used the following notions.

Definition 13.2.1 (Lutz [252, 254]). An s-gale is a function d : 2<ω → R 0 such that d(σ) = 2−s(d(σ0) + d(σ1)) for all σ.

An s-supergale is a function d : 2<ω → R 0 such that d(σ) 2−s(d(σ0)+ d(σ1)) for all σ.

We define the success set S[d] of an s-(super)gale in the same way as for martingales.

A 1-(super)gale is the same as a (super)martingale. For s < 1, we can think of an s-gale as capturing the idea of betting in an inflationary environment, in which not betting costs us money. In the case of martingales, if we are not prepared to favor one side or the other in our bet following σ, we just make d(σi) = d(σ) for i = 0, 1, and are assured of retaining our current capital. In the case of an s-gale with s < 1, we are no longer able to do so. If we want to have d(σ0) = d(σ1), then we will have d(σi) < d(σ) for i = 0, 1, and hence will necessarily lose money.

It is quite easy to go between s-gales and rates of success of martingales.

Lemma 13.2.2. For each (super)martingale d there is an s-(super)gale d such that S[d] = S2(1−s)n [d]. Conversely, for each s-(super)gale d there is a (super)martingale d such that S[d] = S2(1−s)n [d].

Proof. For a (super)martingale d, let d be defined by d(σ) = 2(s−1)|σ|d(σ).

Note that, in the above proof, if s is rational then we can pass e ectively from d to d or vice versa, so, for instance, d is c.e. iff d is c.e.

Lutz’ key insight was that Hausdor dimension can be quite naturally characterized using either s-gales or growth rates of martingales.

Theorem 13.2.3 (Lutz [252, 254]). For a class X 2ω the following are equivalent.

We will be particularly interested in the case C = Σ01. The Σ01 Hausdor dimension of R is sometimes called the constructive (Hausdor ) dimension of R, but we will refer to is as the e ective Hausdor dimension, or simply the e ective dimension, of R, and denote it by dim(R).

In Lutz’ original paper [252], he defined C dimension using gales, but in the journal version [254], he used supergales. The issue here is one of multiplicative optimality versus universality. Let us consider the Σ01 case. By Theorem 6.3.5, there is a universal c.e. martingale, but while there is an optimal c.e. supermartingale (Theorem 6.3.7), there is no optimal c.e. martingale (Corollary 6.3.12). As noted by Hitchcock, Lutz, and others, it is not known whether there is always a c.e. r-gale that is universal for the class of all c.e. r-supergales. However, we have the following result, which shows that if r < t then there is a t-gale that is optimal for the class of all r-supergales. Thus gales su ce for defining e ective dimension, and Lutz’ original formulation of e ective dimension in terms of gales is equivalent to the one in terms of supergales.

Theorem 13.3.2 (Hitchcock [179]). Let 0 r < t be rationals. There is a c.e. t-gale d such that for all c.e. r-supergales d, we have S[d] S[d ].

Proof. Let d be a multiplicatively optimal c.e. r-supergale with d(λ) < 1 (constructed as in the proof of Theorem 6.3.7). It is enough to build d so

Then it is easy to check that each dn is a t-gale and dn(σ) = 1 for all

σ A[n].

Now let s (r, t) be rational and let

Let X S[d]. Then X (n − 1) A for infinitely many A. For such n, d (X (n − 1)) 2(s−r)ndn(X (n − 1)) = 2(s−r)n.

Hence X S[d ].

Of course, this result translates into the language of martingales. Say

d(A n)

that a (super)martingale d s-succeeds on A if lim supn 2(1−s)n = ∞. We can build a c.e. martingale that (s + ε)-succeeds on every set A for which there is a c.e. supermartingale that s-succeeds on A. However, we do not know

598 13. Algorithmic Dimension

whether for each such A there necessarily is a martingale that s-succeeds on A.

In any case, dim(R) is equal to inf{s Q : R S2(1−s)n [d]}, where d is an optimal c.e. supermartingale. It follows immediately that dim(R) = sup{dim(A) : A R} and, more generally, the e ective dimension of an arbitrary union of classes is the supremum of the e ective dimensions of the individual classes. (Notice that for classical Hausdor dimension, the corresponding fact is true only for countable unions.)

We can also e ectivize Definition 13.1.1 directly. For Σ01 dimension, we have the following.

s

(iii)The e ective s-dimensional outer Hausdor measure of R is H (R) =

s limn Hn(R).

(iv) The e ective Hausdor dimension of R is the unique s [0, 1] such

It is straightforward to e ectivize our earlier work and show that the e ective analog of Theorem 13.2.3 holds. That is, the above definition agrees with our earlier definition of e ective Hausdor dimension. A similar comment holds for other suitable complexity classes.

There is another fundamental characterization of e ective Hausdor dimension, in terms of initial segment complexity.

Theorem 13.3.4 (Mayordomo [262]). For A 2ω, we have

Proof. The second equation is immediate, since C and K agree up to a log factor. We prove the first equation.

First suppose that dim(A) < s. Let d be a universal c.e. supermartingale.

2Staiger [378] showed that Theorem 13.3.4 can be obtained from results of Levin in [425]. There were also a number of earlier results indicating the deep relationship between e ective Hausdor dimension and Kolmogorov complexity, such as those of Cai and Hartmanis [45], Ryabko [338, 339, 340], and Staiger [376, 377]. These results are discussed in Lutz [254] (Section 6, in particular) and Staiger [378].

so is d. There are infinitely many n such that A n D. For any such n, we have d(A n) 2(s−r)n, so d succeeds on A, and hence dim(A) s.3

One consequence of this characterization is that if A has positive e ective Hausdor dimension, then A is complex, since if dim(A) > r > 0, then C(A n) > rn for almost all n.

The Kolmogorov complexity characterization of e ective dimension also allows us to easily produce sets with fractional e ective dimension. Let A

Recall the following definition. Given an infinite and coinfinite set X, let x0 < x1 < · · · be the elements of X, let y0 < y1 < · · · be the elements of

X, and define C X D to be {xn : n C} {yn : n D}. For a computable

real r [0, 1], we can find a computable X such that limn |X∩[0,n)| = r.

n

Then it is easy to check that A X 0ω has e ective dimension r. Thus we have the following result.

Theorem 13.3.5 (Lutz [252, 254]). For every computable real s, there is a set of e ective Hausdor dimension s.

Clearly, every 1-random set has e ective dimension 1, but if we take r = 1 in the above construction, then we have an example of a set of e ective dimension 1 that is not 1-random.

Schnorr [349] considered exponential orders on martingales, and hence was in a sense implicitly studying dimension. We thank Sebastiaan Terwijn for the following comments on Schnorr’s work. There is no explicit reference in Schnorr’s book to Hausdor dimension. After introducing orders of growth of martingales, he places special emphasis on exponential orders. It is interesting to ask why he did this, and whether he might have been inspired by the theory of dimension, but when asked at a recent meeting, he said he was not so motivated, so it is unclear why he gave such emphasis to exponential orders. Chapter 17 of [349] is titled “Die Zufallsgesetze von exponentieller Ordnung” (“The statistical laws of exponential

3Using the characterization in Definition 13.3.3, we can give a slightly cleaner proof.

600 13. Algorithmic Dimension

order”) and it starts as follows: “Nach unserer Vorstellung entsprechen den wichtigsten Zufallsgesetzen Nullmengen mit schnell wachsenden Ordnungsfunktionen. Die exponentiell wachsenden Ordnungsfunktionen sind hierbei von besonderer Bedeutung.”4

Satz 17.1 then says that for any measure 0 set A the following are equivalent.

1. There are a computable martingale d and an a > 1 such that A is

2. There are a Schnorr test { Un }n ω and a b > 0 such that A is contained in {X : lim supn mU (X n) − bn > 0}, where mU is a “Niveaufunktion” from strings to numbers defined by mU (σ) = min{n : σ Un}.

This result is a test characterization saying something about the speed at which a set is covered, and resembles characterizations of e ective Hausdor dimension.

In this chapter we will focus on the Σ01 notion of e ective dimension, but as with notions of algorithmic randomness, there are many possible variations. For instance, we can vary arithmetic complexity of the gales used in the definition of dimension. In Section 13.15, we will examine the e ect of replacing Σ01 gales by computable ones, to yield a notion of computable dimension. We can also take the test set approach and study variations on that, for instance Schnorr dimension, which turns out to be equivalent to computable dimension, as we will see in Section 13.15. Some known relationships between notions of randomness and dimension are summarized in

No other implications hold than the ones indicated.

4“In our opinion, the important statistical laws correspond to null sets with fast growing orders. Here the exponentially growing orders are of special significance.”

13.4 Shift complex sets

Not every set of high e ective Hausdor dimension is a “watered down” version of a 1-random set.

Definition 13.4.1. Let 0 < d < 1. A set A is d-shift complex if for every m < n, we have K(A [m, n]) d(n − m) − O(1).

If A is d-shift complex then K(A n) dn − O(1), so the e ective Hausdor dimension of A is at least d. On the other hand, a 1-random set cannot be d-shift complex for any d > 0, since it must contain arbitrarily long sequences of 0’s. Thus Theorem 13.4.3 below, which states that d- shift complex sets exist for every d (0, 1), shows that sets of high e ective dimension can be quite di erent from 1-random sets. (Note that any 1-shift complex set would be 1-random, and hence no such sets exist.) We give a proof due to Miller [274], though the original proof in Durand, Levin, and Shen [138] is also not complicated.

We say that a set A avoids a string σ if there are no m < n such that σ = A [m, n]. Theorem 13.4.3 also follows from a stronger result due to Rumyantsev and Ushakov [337], who showed that if c < 1 and for each n, we have a set Fn 2n with |Fn| 2cn, then there is an A such that for all su ciently large n, the set A avoids every element of Fn.

We think of w(σ) as measuring the threat that an extension of σ ends in an element of S. Note in particular that if σ itself ends in some τ S then w(σ) c|λ| = 1, so it is enough to build A so that w(A n) < 1 for all n. We have w(λ) = 0. Now suppose that we have defined A n = σ so that w(σ) < 1. It is easy to check that c(w(σ0) + w(σ1)) = w(σ) + p < 2c, so there is an i < 2 such that w(σi) < 1, and we can let A(n) = i.

Theorem 13.4.3 (Durand, Levin, and Shen [138]). Let 0 < d < 1. There is a d-shift complex set.

Proof. Let b = − log(1 −d) + 1, let c = 2−d, and let S = {τ 2<ω : K(τ ) d|τ | − b}. We have

602 13. Algorithmic Dimension

where the last inequality is easy to show using the fact that d (0, 1). Thus, by the lemma, there is an A that avoids every element of S. This A is clearly d-shift complex.

13.5 Partial randomness

Results such as Theorem 13.3.4 show that e ective dimension can be thought of as a notion of “partial randomness”. Indeed, as we saw above, a set such as A 0 for a 1-random A, which one would intuitively think of as “ 21 -random”, does indeed have e ective dimension 12 . In this section, we look at a di erent, though closely related, approach to defining a notion of s-randomness for s [0, 1].

We begin with the measure-theoretic approach. We will see that there are at least two reasonable ways to define the concept of s-Martin-L¨of randomness. The first is a straightforward generalization of the original

We can also define A to be weakly s-random if K(A n) sn−O(1). The analog of Schnorr’s Theorem that 1-randomness is the same as Martin-L¨of randomness is straightforward.

Theorem 13.5.2 (Tadaki [385]). Let s [0, 1] be a computable real. A set A is weakly s-Martin-L¨of random iff A is weakly s-random.

Proof. This proof directly mimics the one of Theorem 6.2.3. We give it here as an example. For other similar results whose proofs are straightforward modifications of the s = 1 case, we simply mention that fact.

Suppose that A is weakly s-Martin-L¨of random. Let Vk = {σ : K(σ)

5Below, we will define the notion of tests for strong s-Martin-L¨of randomness. Since they will determine a stronger notion of s-randomness, these tests will be weaker than the ones we define here. The terminology adopted here is meant to avoid the confusion of talking about weak tests in connection with strong randomness and strong tests in connection with weak randomness, or the equally confusing possibility of having objects called “weak tests” that are actually stronger than ones called “strong tests”.

Conversely, suppose that A is not weakly s-Martin-L¨of random. Let {Vk}k ω be a test for weak s-Martin-L¨of randomness such that A k Vk . Then it is easy to check that {(s|σ| − k, σ) : σ Vk2 , k > 2} is a KC set, so for each c there is an n such that K(A n) < sn − c.

Of course, weak s-randomness is closely related to e ective dimension.

Proposition 13.5.3. For all A, we have dim(A) = sup{s : A is weakly s- random}.

Whether A is dim(A)-random depends on A, of course. We have seen that there are sets of e ective dimension 1 that are not 1-random, and it is easy to construct similar examples for s < 1. On the other hand, the examples we gave in connection with Theorem 13.3.5 have e ective dimension s and are weakly s-random, so we have the following extension of that result.

Theorem 13.5.4 (Lutz [252, 254]). For every computable real s [0, 1], there is a set of e ective Hausdor dimension s that is weakly s-random.

The discussion above tells us that the concept of s-randomness does give us some information beyond what we can get from e ective dimension alone.

Using Theorem 13.5.2, we can emulate the proof that Ω is 1-random to show the following.

Theorem 13.5.5 (Tadaki [385]). Let s (0, 1] and let Ωs = 2−|σs| .

U(σ)↓

Then Ωs is weakly s-random.

Similarly, we can construct a universal test for weak s-Martin-L¨of randomness and develop other tools of the theory of 1-randomness. For example, it is useful to have an analog of Solovay tests for s-randomness.

Definition 13.5.6. Let s [0, 1]. A Solovay s-test is a c.e. set S 2<ω

such that σ S 2 < ∞. A set A is covered by this test if A σ for infinitely many σ S.

The following result can be proved in much the same way as the s = 1 case. Although one direction is slightly weaker than in the s = 1 case, this result is enough to establish that for all A, we have dim(A) = inf{s : A is covered by some Solovay s-test}.

604 13. Algorithmic Dimension

Theorem 13.5.7 (Reimann [324]). If A is weakly s-random then A is not covered by any Solovay s-test. If A is covered by some Solovay s-test then A is not weakly t-random for any t > s.

The following variant will be useful in the proof of Theorem 13.8.1 below.

Definition 13.5.8. An interval Solovay s-test is a c.e. set T of intervals

in [0, 1] with dyadic rational endpoints such that I T |I|s < ∞ (where |I| is the length of I).

It is easy to transform an interval Solovay s-test T into a Solovay s- test S as follows. For each [q, q + r] T , first let n be largest such that

[q, q + r] [q, q + 2−n]. Note that 2−n < 2r. Let σ0 and σ1 be such that 0.σ0 = q and 0.σ1 = q + 2−n. Let τi = (σi0ω) n. Put τ0 and τ1 into S. It

dimension of a real.

Turning now to the martingale approach to randomness, we run into some trouble. The following definitions are natural.

Definition 13.5.9. Let s [0, 1].

(i)A is martingale s-random if for all c.e. martingales d, we have A /

S2(1−s)n [d].

(ii)A is supermartingale s-random if for all c.e. supermartingales d, we have A / S2(1−s)n [d].

It is currently unknown whether these notions are the same, for the kind of reasons we mentioned when discussing Theorem 13.3.2.

We would like to show that at least one of these notions of martingale s-randomness coincides with weak s-randomness, but one direction of the equivalence does not work. Consider Schnorr’s proof that if a set is Martin- L¨of random then no c.e. (super)martingale can succeed on it. We are given a c.e. (super)martingale d, and when we see d(σ) > 2k, we put σ into a test set Uk. Now imagine we follow the same proof for the s < 1 case. Here our test sets Vk are sets of strings. We might see that ds(σ0) > 2k and put σ0 into Vk. Since d is only c.e., at some later stage t > s we might see that dt(σ) > 2k. We would like to have σ Vk , but of course putting σ into Vk is a waste, since σ0 is already there, and indeed the measure calculation in Schnorr’s proof is unlikely to work if Vk is not prefix-free. If we were to follow Schnorr’s proof, we would simply put σ1 into Vk . Unfortunately, 2(2−s(|σ|+1)) > 2−s|σ|, so the simple measure calculation that allowed Schnorr’s proof to succeed is no longer available.

This problem was overcome by the following definition of Calude, Staiger, and Terwijn [52].

Definition 13.5.10 (Calude, Staiger, and Terwijn [52]). Let s [0, 1].

606 13. Algorithmic Dimension

Definition 13.5.14 (Downey and Reid, see [323]). Let f : 2<ω → 2<ω be a partial computable function computed by a Turing machine M , and let Q rng f . The M -pullback of Q is the unique subset Q of dom f satisfying the following conditions.6

(i)f (Q ) = Q.

(ii)If σ Q and f (τ ) = f (σ), then |τ | |σ|.

(iii)If σ Q and f (τ ) = f (σ) with |τ | = |σ| then σ is enumerated into dom M before τ is. (We assume that elements enter dom M one at a time.)

be a computable real. A set A is strongly s-Martin-L¨of random iff KM (A n) n − O(1) for all s-measurable machines M .

We know of no characterization of strong s-randomness in terms of initial segment prefix-free or plain complexity.

Before we prove Theorem 13.5.15, we need a lemma, which takes the role of the KC Theorem in this setting.

Lemma 13.5.16 (Downey, Reid, and Terwijn, see [323]). Let s (0, 1]. Let {Uk}k ω be a test for strong s-Martin-L¨of randomness. There is an s-measurable machine M such that for each k and σ U2k+2, there is a τ of length |σ| − (k + 1) with M (τ ) = σ.

Proof. If σ U2k+2 then 2−|σ| 2−s|σ| 2−(2k+2), so |σ| 2k + 2, whence |σ|−(k + 1) > 0. So for a single such σ, requiring that there be a τ of length |σ| − (k + 1) with M (τ ) = σ does not cause a problem.

We define M in the most obvious way: Whenever we see σ enter U2k+2, we find the leftmost τ of length |σ| − (k + 1) and let M (τ ) = σ. We must show that there is always such a τ available, that is, that for each n there are at most 2n many strings of length n needed for the definition of M .

As argued above, if σ U2k+2 then |σ| 2k + 2, so if k > n − 1 then |σ| − (k + 1) > n. Thus we need to worry about only those U2k+2 with k n − 1. Note that strings σ U2k+2 that require a domain element τ of length n must have length n + k + 1.

For a set S of strings, let #(S, n) denote the number of strings of length n in S. As the set of all strings in U2k+2 of length n + k + 1 is prefix-free,

{2−s(n+k+1) : σ U2k+2 |σ| = n + k + 1} 2−(2k+2).

6Roughly speaking, this definition is an approximation to the notion of σ for Kolmogorov complexity introduced in Chapter 3.

608 13. Algorithmic Dimension

Hitchcock [180] showed that for such classes, and in fact even for arbitrary countable unions of Π01 classes, the classical Hausdor dimension of a class is equal to its e ective Hausdor dimension, and hence to the supremum of the Hausdor dimensions of its elements. Thus, for such classes, we can think of classical Hausdor dimension, which at a first look seems clearly to be a global property of a class, as a pointwise phenomenon.

Theorem 13.6.1 (Hitchcock [180]). Let P be a countable union of Π01 classes. Then dimH P = dim P .

Proof. It is enough to prove the result for the case in which P is a single Π01 class, since the Hausdor dimension of a countable union of classes is the supremum of the Hausdor dimension of the individual classes, and similarly for e ective dimension.

can recognize when we have found one. Then the Vn form a test for weak s-Martin-L¨of randomness, and P n Vn , so no element of P is weakly s-Martin-L¨of random, and hence dim(A) < s for all A P .

Thus dim P < s. Since s > dimH P is arbitrary, dim P dimH P .

Hitchcock [180] also showed that if P is a Σ02 class (i.e., a union of uniformly Π01 classes), then the Hausdor dimension of P is equal to its computable Hausdor dimension (that is, the dimension defined using computable, rather than c.e., martingales, which is equivalent to the concept of Schnorr Hausdor dimension defined below).

Note that, as observed by Hitchcock [180], Theorem 13.6.1 cannot be extended even to a single Π02 class, since {Ω} is a Π02 class.

13.7Hausdor dimension and complexity extraction

There have been several results about the dimensions of classes of sets defined in computability-theoretic terms. One important theme is the following: given a set of positive e ective dimension, to what extent is it possible to extract a greater level of complexity/randomness from that set? As we will see, there are several ways to formalize this question. (Note that we have already seen in Theorem 8.16.6 that there are sets of reasonably high initial segment complexity that do not compute 1-random sets.)

We begin by pointing out a fundamental di erence between the degrees of 1-random sets and those of sets of high e ective Hausdor dimension.

Lemma 13.7.1 (Folklore). Let A m B. There is a C ≡m B such that A and C have the same e ective Hausdor dimension. The same result holds for any weaker reducibility, such as Turing reducibility.

Proof. Let f be a fast-growing computable function, such as Ackermann’s function (though a much slower-growing function than that will do for this argument). For each n, replace A(f (n)) by B(n). Call the resulting set C. Then C ≡m B, and A and C have the same e ective Hausdor dimension because K(A m) and K(C m) are very close for all m. The same procedure works for any weaker reducibility.

As we saw in Corollary 8.8.6, Kuˇcera [215] proved that the Turing degrees

of 1-random sets are not closed upwards. This fact is true even in the 0

2

degrees, for instance by Theorem 8.8.4. Hence, we have the following.

dimension 1 containing no 1-random sets.

Proof. Choose a < b < 0 such that a is 1-random but b is not. By Lemma 13.7.1, b contains a set of e ective Hausdor dimension 1.

Since Ω tt , the method above also gives the following result.

Corollary 13.7.3 (Reimann [324]). The tt-degree of has e ective Hausdor dimension 1.

The only way we have seen to make a set of e ective Hausdor dimension 1 that is not 1-random is to take a 1-random set and “mess it up” by a process such as inserting 0’s at a sparse set of locations. It is natural to ask whether this is in some sense the only way we can produce such a set. One way to formalize this question is by asking whether it is always possible to extract randomness from a source of e ective Hausdor dimension 1.

Question 13.7.4 (Reimann). Let A have e ective Hausdor dimension 1. Is there necessarily a 1-random B T A?

We will give a negative answer to this question due to Greenberg and Miller [170] in Section 13.9, where we will present their construction of a set of e ective Hausdor dimension 1 and minimal Turing degree. We saw in Corollary 6.9.5 that no minimal degree is 1-random.

Similarly, one of the only methods we have seen for making a set of fractional e ective Hausdor dimension is to take a set of higher e ective Hausdor dimension and “thin it out” (the other method being the construction of shift complex sets in Section 13.4). Again we are led to ask whether, given a set A of fractional e ective Hausdor dimension, it is always possible to find a set B T A of higher e ective Hausdor dimension, or even of e ective Hausdor dimension 1, or even a 1-random B T A. By

610 13. Algorithmic Dimension

Lemma 13.7.1, these questions remain the same if we replace T by ≡T, so we can think of them as questions about the relationship between the e ective Hausdor dimension of A and that of its degree. Thus we can ask the following question.

Question 13.7.5 (Reimann, Terwijn). Is there a Turing degree a of effective Hausdor dimension strictly between 0 and 1? If so, can a be

02?

Question 13.7.5 is known as the broken dimension question. In Section 13.8, we will give a positive answer to it due to Miller [273]. Before doing so, we mention some earlier attempts to solve this question that are interesting and insightful in their own right.

We have seen in Theorem 8.8.1 that 1-random sets can always compute DNC functions. Terwijn [387] proved that this is also the case for sets of nonzero e ective Hausdor dimension. We can easily extract this result from our results on autocomplex sets and DNC functions: As mentioned following Theorem 13.3.4, if A has positive e ective Hausdor dimension, then A is complex, so by Theorem 8.16.4, A computes a DNC function. However, Terwijn’s original proof is instructive and short, so we give it below.

Theorem 13.7.6 (Terwijn [387]). If dim(A) > 0 then A can compute a DNC function.

Proof. By Theorem 2.22.1, it is enough to show that A can compute a fixed-point free function.

Let s be such that dim(A) > s > 0 and 1s N. For each e, let e0 and e1 be indices chosen in some canonical way so that We = We0 We1 . For a string σ, let σ be the string of length |σ| such that σ(n) = 1 − σ(n). Let

test for weak s-Martin-L¨of randomness for each e. We can e ectively find indices g(e) for each such test. (That is, WΦg(e) (n) enumerates Be,n for each e and n.)

The usual construction of a universal test applied to tests for weak s- Martin L¨of randomness produces a universal test for weak s-Martin-L¨of randomness {Un}n ω such that for each index i, for the ith test for weak s-Martin-L¨of randomness {Vn}n ω, we have Vn+i+1 Un for all n. Since

dim(A) > s, there is an n such that A / Un , so A / Be,n+g(e)+1 for all e.

To construct the fixed-point free function h T A, given e, let h(e) be an index so that Wh(e)0 f (n + g(e) + 1) = A f (n + g(e) + 1) and Wh(e)1 f (n + g(e) + 1) = A f (n + g(e) + 1). If Wh(e) = We, then

612 13. Algorithmic Dimension

Theorem 13.8.1 (Miller [273]). Let α (0, 1) be a left-c.e. real. There is

a02 set A of e ective Hausdor dimension α such that if B T A then

the e ective Hausdor dimension of B is at most α.

Proof. To simplify the presentation, we take α = 12 . It should be clear how to modify the proof to work for any rational α, and not too di cult to see how to handle the general case.

We will build A as the intersection of a sequence of nested Π01 classes of positive measure. We will begin with a class all of whose members have e ective dimension at least 12 , thus ensuring that dim(A) 12 . At each stage we will satisfy a requirement of the form ΨAe total k > n (K(ΨAe k) −n)k). To do so, we will want to wait until a large set of oracles that appear to be in our current Π01 class P compute the same string via Ψe, and then compress that string. A key to showing that we can do this will be to use the dimension of the measure of P . Thus we will work with Π01

classes such that dim(μ(P )) 12 .

We begin by introducing some concepts that will be needed in the proof.

fractional length, so the cost of compressing a string of length 5 by a factor of 2 is actually 2−2, not 2−2.5). Of course, there is no reason to think that this compression can be realized e ectively. In other words, even if S is c.e., there may not be a prefix-free machine M compressing some initial segment of each set in S by a factor of 2 so that the measure of the domain of M is close to W (S).

Suppose that S is finite and let V be such that S V . It is suboptimal for V to contain any string incomparable with every σ S or to contain a proper extension of some σ S. In other words, it is always possible to

Hence this infimum is achieved, justifying the following definition when S is finite.

Definition 13.8.3. An optimal cover of S 2<ω is a set Soc 2<ω such that S Soc and DW(Soc) = W (S). For the sake of uniqueness, we also require Soc to have the minimum measure among all possible contenders.

It is not hard to see that optimal covers, if they exist, are unique and prefix-free. The analysis above shows that when S is finite, we can compute both the optimal cover of S and W (S).

then the only way for σ to not be in St+1 is for some τ σ to be in St+1. This fact has some nice consequences. First, it implies a nesting property:

the direct weight of any prefix-free subset is bounded by W (S). Here and below, we write τ 2<ω for {τ σ : σ 2<ω}.

Lemma 13.8.4. For any c.e. set S 2<ω, we can e ectively find a c.e. V 2<ω such that V = Soc and if P V is prefix-free, then DW(P )

W (S).

approximation—or in terminology borrowed from set theory, the type of forcing condition—determines the nature of the requirements that we can satisfy during the construction. Our conditions will be pairs (σ, S) with σ 2<ω and S σ2<ω c.e. and such that σ / Soc. A condition describes a restriction on the set A that is being constructed. Specifically,