654 13. Algorithmic Dimension

13.15Computable dimension and Schnorr dimension

13.15.1 Basics

It is natural to consider notions of dimension obtained by replacing c.e. gales by computable ones. Recall that a martingale d s-succeeds on A if

d(A n)

lim supn 2(1−s)n = ∞ and s-succeeds strongly on A if limn 2(1−s)n = ∞. As discussed in Section 13.3, the following definitions were in a sense implicit

in the work of Schnorr [349].

Definition 13.15.1 (Lutz [252, 254], Athreya, Hitchcock, Lutz, and Mayordomo [15]). The computable Hausdor dimension of C 2ω is

dimcomp(C) = inf{s : there is a computable martingale that s-succeeds on all A C}.

The computable packing dimension of C 2ω is

Dimcomp(C) = inf{s : there is a computable martingale that s-succeeds strongly on all A C}.

For A 2ω, we write dimcomp(A) for dimcomp({A}) and refer to it as the computable Hausdor dimension of A, and similarly for packing dimension.

A di erent approach to passing from Σ01 objects to computable ones in the definition of algorithmic dimension is to consider test sets that are computable in the sense of Schnorr.

Definition 13.15.2. Let s 0 be rational.

A Schnorr s-test is a uniformly c.e. sequence {Sn}n ω of sets of strings

are actually uniformly computable, since to determine whether σ Sn it

in fact 2−n). If σ has not been enumerated so far, it cannot be in Sn. But of course the converse does not hold: there are computable sets of strings generating open sets with noncomputable measures. Indeed, we have mentioned before that every Σ01 class can be generated by a computable set of strings.

We can adapt Definition 13.5.6 to get an s-analog of the concept of total

Solovay test introduced in Definition 7.1.9. A Solovay s-test D is total if

σ D 2 is computable.

As we saw in Section 13.5, the correspondence between tests for s-Martin- L¨of randomness and Solovay s-tests is close but not quite exact. In the Schnorr case, however, we do get an exact correspondence.

Theorem 13.15.3 (Downey, Merkle, and Reimann [125]). For any rational s 0, a class C 2ω is Schnorr s-null if and only if there is a total Solovay s-test that covers every element of C.

Sn form a Schnorr s-test whose intersection contains all sets covered by

S.

We have the following e ective version of Theorem 13.1.2.

Proposition 13.15.4 (Downey, Merkle, and Reimann [125]). For any rationals t s 0, if C is Schnorr s-null then it is also Schnorr t-null.

Proof. It su ces to show that if s t, then every Schnorr s-test is also a Schnorr t-test. Obviously, the only issue is checking the computability of the relevant sum.

Let {Sn}n ω be a Schnorr s-test. Given any rational r 0 and any n and k, let

Now, mn(s) is computable, and 2(s−t)k goes to zero as k gets larger. Therefore, we can e ectively approximate mn(t) to any desired degree of precision.

656 13. Algorithmic Dimension

Thus the following definition makes sense.

Definition 13.15.5 (Downey, Merkle, and Reimann [125]). The Schnorr Hausdor dimension of C 2ω is

dimS(C) = inf{s 0 : C is Schnorr s-null}.

For A 2ω, we write dimS(A) for dimS({A}) and refer to it as the Schnorr Hausdor dimension of A.

Note that the Schnorr Hausdor dimension of any class is at most 1, since for any ε > 0 we can choose a computable sequence k0, k1, . . . such that the sets 2kn form a Schnorr 1 + ε test covering all of 2ω.

We saw in Section 8.11.2 that the concepts of computable randomness and Schnorr randomness do not coincide. That is, there are Schnorr random sets on which some computable martingale succeeds. However, the di erences vanish when it comes to Hausdor dimension.

Theorem 13.15.6 (Downey, Merkle, and Reimann [125]). For any B 2ω, we have dimS(B) = dimcomp(B).

Proof. ( ) Suppose that a computable martingale d s-succeeds on B. By Theorem 7.1.2, we may assume that d is rational-valued. We may also assume that s < 1, since the case s = 1 is trivial. It su ces to show that for any t (s, 1), we can find a Schnorr t-test that covers B. Fix such a t.

Let

Uk = {σ : 2−(1−t)|σ|d(σ) 2k}.

It is easy to see that the {Uk}k ω are uniformly computable (since d is rational-valued and computable) and cover B, so we are left with showing

d(τ ) 2(1−t)n2k 2r+kd(λ). So by Kolmogorov’s Inequality (Theorem 6.3.3), μ(Uk) − μ(V ) 2−(r+k).

( ) Suppose dimS(B) < s < 1. (Again the case s = 1 is trivial.) We show that there is a computable martingale d that s-succeeds on B.

We verify that dk is a martingale. Given σ, if there is a τ Vk such that τ σ, then clearly dk(σ0) + dk(σ1) = 2dk(σ). Otherwise,

dk(σ0) + dk(σ1)

= 2−|τ |+(1−s)(|σ|+|τ |+1) + 2−|τ |+(1−s)(|σ|+|τ |+1)

is a Schnorr s-test to show that the dk are uniformly computable, and hence d is computable.

Finally, note that, for σ Vk, we have d(σ) dk(σ) = 2(1−s)|σ|, so if B k Vk , then d(B n) 2(1−s)n infinitely often, which means that d s-succeeds on B.

Thus, in contrast to randomness, the approaches to dimension via Schnorr tests and via computable martingales yield the same concept. Because of the potential confusion between the terms “e ective dimension” (which we have used to mean our primary notion of Σ01 dimension) and “computable dimension”, we will use the term “Schnorr Hausdor dimension” and the notation dimS. For uniformity, we will also refer to computable packing dimension as Schnorr packing dimension and use the notation DimS in place of Dimcomp.

It follows from the definitions that dimS(A) DimS(A) for any A. We call sets for which Schnorr Hausdor and Schnorr packing dimension coincide Schnorr regular , following [391] and [15]. It is easy to construct a nonSchnorr regular sequence; in Section 13.15.4, we will see that such sequences occur even among the c.e. sets.

13.15.2 Examples of Schnorr dimension

The easiest way to construct examples of sequences of non-integral Schnorr Hausdor dimension is by inserting zeroes into a sequence of Schnorr Hausdor dimension 1. Note that it easily follows from the definitions that every Schnorr random set has Schnorr Hausdor dimension 1. On the other hand, it is not hard to show that not every set of Schnorr Hausdor dimension 1 is Schnorr random.

A second class of examples is based on the fact that Schnorr random sets satisfy the law of large numbers, not only with respect to the uniform measure, but also with respect to other computable Bernoulli distributions. For a sequence p = (p0, p1, . . . ) of elements of (0, 1), the Bernoulli measure μp