This lemma completes the proof of the theorem.

Note that the above result implies that Miller’s degree of e ective Hausdor dimension 12 cannot compute two C-independent sources of positive e ective Hausdor dimension. This fact likely has interesting consequences for the computational power of such degrees.

Zimand [424] examined the extent to which the hypotheses on X and Y can be weakened. He stated that similar techniques can be used to show that for any δ > 0, there is a c such that, given sequences X and Y that are C-independent and such that C(X n) > c log n and C(Y n) > c log n for every n, a Z can be produced from X and Y with C(Z n) > (1 − δ)n for infinitely many n.

In a more recent paper, Zimand [422] showed that even for pairs of sets of limited dependence (as defined in that paper), it is still possible to extract a Z of high initial segment complexity. The methods are similar to those described here, but more delicate. Also, using similar and equally delicate methods, Zimand [423] showed that from two partially random but independent strings (as defined in that paper), it is possible to construct polynomially many pairwise independent random strings, and if the two original strings are themselves random, then this construction can be done in polynomial time. See [53, 424, 422, 423] for more on this fascinating topic.

13.11 Other notions of dimension

Hausdor ’s extension of Carath´eodory’s s-dimensional measure is certainly not the only generalization of the notion of dimension to non-integer values in geometric measure theory and fractal geometry, and it is also not the only one to have been e ectivized. In this section, we will briefly look at a couple of further dimension concepts and their e ectivizations. Further details about the classical notions may be found in Federer [142].

13.11.1 Box counting dimension

For C 2ω, let C n = {σ 2n : α C (σ α)} and define the upper and lower box counting dimensions of C as

respectively. If dimB and dimB coincide, then this value is called the box counting dimension, or Minkowski dimension, of C. The name “box counting” comes from the fact that, for each level n, one simply counts the number of boxes of size 2−n needed to cover C. The following is clear.

636 13. Algorithmic Dimension

Lemma 13.11.1. For any C 2ω, we have dimH(C) dimB(C) dimB(C).

(Lower) box counting dimension gives an easy upper bound on Hausdor dimension, although this estimate may not be very precise. For instance, let C be the class of all sequences that are 0 from some point on. Then we have dimH(C) = 0 but dimB(C) = 1. (In fact, dimB(D) = 1 for any dense D 2ω.) This observation shows that, in general, box counting dimension is not a stable concept of dimension, since a countable union of classes of box counting dimension 0 such as C can have box counting dimension 1. Staiger [377, 378] has investigated some conditions under which Hausdor and box counting dimension coincide. Probably the most famous example of such a set is the Mandelbrot set.

One can modify box counting dimension to obtain a countably stable notion, yielding the concept of modified box counting dimension, defined as follows. The lower modified box counting dimension of C 2ω is

If these values coincide, then they define the modified box counting dimension dimMB(C) of C. (That is, we split up a set into countably many parts and look at the dimension of the “most complicated” part. Then we optimize this value by looking for the partition with the lowest such dimension.)

The modified box counting dimensions behave more stably than their original counterparts; in particular, all countable classes have modified box counting dimension 0. However, these dimensions are usually hard to calculate, due to the extra inf / sup process involved in their definitions.

13.11.2 E ective box counting dimension

The e ectivization of box counting dimension is due to Reimann [324]. An equivalent formulation of e ective upper box counting dimension was also given by Athreya, Hitchcock, Lutz, and Mayordomo [15]. This concept turns out to coincide with e ective packing dimension, which we discuss below.

We will be concerned only with the dimension of individual sets, and hence will not look at the modified versions of box counting dimension needed for countable stability. It is of course possible to e ectivize the definition of, for example, dimMB X as we do for box counting dimension below.

Definition 13.11.2 (Reimann [324]). A c.e. set C 2<ω is an e ective box cover of B 2ω if B n C for almost all n.

E ective box counting dimension measures how e ciently the initial segments of a set can be “enwrapped” in a c.e. set of strings. For D 2<ω, let D[n] = D ∩ 2n.

Definition 13.11.3 (Reimann [324]). Let B 2ω. The e ective lower box counting dimension of B is

E ective upper box counting dimension is the same as a concept analyzed by Athreya, Hitchcock, Lutz, and Mayordomo [15] and Hitchcock [180], building on work of Staiger [377].

Definition 13.11.4 (Staiger [377], Athreya, Hitchcock, Lutz, and Mayordomo [15]). For A 2<ω, the entropy rate of A is

HA = lim sup log |A[n]|.

n n

For A 2<ω, let Ai.o. = {β 2ω : ∞n (β n A)} and Aa.e. = {β 2ω :∞n (β n A)}. For C 2ω, let

H1(C) = inf{HA : C Ai.o. A Σ01}

and

H1str(C) = inf{HA : C Aa.e. A Σ01}.

For B 2ω, let H1(B) = H1({B}) and H1str(B) = H1str({B}).

It is not hard to see that for any B 2ω, we have dim1B(B) = H1str(B) and dim(B) = H1(B).

It is a trivial observation that, as in the classical case, e ective box counting dimension always bounds e ective Hausdor dimension from above; in particular, dim(B) dim1B(B) for any B 2ω.

There is clearly a connection between e ective box counting and Kolmogorov complexity, as indicated by the following observation of Kolmogorov [211], which we met in Theorem 3.2.2 (ii).

Proposition 13.11.5 (Kolmogorov [211]). Let A N×2<ω be computably enumerable and such that Am = {x : (m, x) A} is finite for all m. Then C(x | m) log |Am| + O(1) for all m and x Am.

638 13. Algorithmic Dimension

Indeed, it is possible to give an elegant characterization of e ective upper box counting dimension in terms of Kolmogorov complexity.

Theorem 13.11.6 (Reimann [324], Athreya, Hitchcock, Lutz, and Mayordomo [15]). For any B 2ω,

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

13.11.3 Packing dimension

Packing dimension is another classically important fractional dimension. The e ectivization of this notion was first considered by Athreya, Hitchcock, Lutz, and Mayordomo [15], but we will follow the treatment of Reimann [324], who noted the connections with the e ective box counting dimension of the previous section.

Packing dimension can be seen as a dual to Hausdor dimension. Hausdor dimension is defined in terms of economical coverings, that is, enclosing a class from the outside; packing measures approximate from the inside, by packing a class economically with disjoint sets of small size.

A prefix-free set P 2<ω is a packing in C 2ω if every σ P has an extension in C. If |σ| n for all σ P , then we call P an n-packing in C.

One can try to find a packing that is as “dense” as possible. Given s 0

exists. However, this definition leads to the same problems we encountered with box counting dimension. Taking for instance the class C of all sequences that are 0 from some point on, we can find denser and denser packings in C, so that for every 0 s < 1, we have P∞s (C) = ∞. Hence P∞s lacks countable additivity, and in particular is not a measure. This

The measure Ps is called the s-dimensional packing measure on 2ω. Packing measures were introduced by Tricot [391] and Sullivan [384]. They can be seen as dual concepts to Hausdor measures, and behave in many ways similarly to them. In particular, one may define packing dimension in the same way as Hausdor dimension.

Definition 13.11.7. The packing dimension of C 2ω is

dimP(C) = inf{s : Ps(C) = 0} = sup{s : Ps(C) = ∞}.

Packing dimension has stability properties similar to Hausdor dimension, such as countable stability. With some e ort, one can show that it coincides with dimMB (see Chapter 3 of Falconer [141]). Generally, the following relations between the di erent dimension concepts hold: dimH(C) dimMB(C) dimMB(C) = dimP(C) dimB(C).

Although the traditional definition of packing dimension is rather complicated, due to the additional decomposition / optimization step, there is a simple martingale characterization of this notion. This characterization was discovered by Athreya, Hitchcock, Lutz, and Mayordomo [15], and demonstrates the dual nature of Hausdor dimension and packing dimension much more clearly. It came as a surprise to workers in the area, who had thought packing dimension was too complex to have such a simple characterization.

Definition 13.11.8. For 0 < s 1, a martingale d s-succeeds strongly on

d(A n)

A if lim infn 2(1−s)n = ∞.

d(α n)

Obviously, this condition is equivalent to limn 2(1−s)n = ∞. From a gambling perspective, succeeding strongly means not only accumulating arbitrary high levels of capital, but also being able to guarantee that the capital stays above arbitrarily high levels from a certain time on.

Theorem 13.11.9 (Athreya, Hitchcock, Lutz, and Mayordomo [15]). For any C 2ω,

dimP(C) = inf{s : some martingale s-succeeds strongly on all A C}.

Proof. We actually prove this result for dimMB(C) in place of dimP(C), and rely on the fact mentioned above that dimP(C) = dimMB(C).

12This need no longer be the case if the dimension function h(x) = xs is replaced by more irregular functions not satisfying even weak continuity requirements.

640 13. Algorithmic Dimension

( ) Let d be a martingale that s-succeeds strongly on all A C. We show that dimMB(C) s. Without loss of generality, assume that d(λ) 1. Let

Dn = {σ 2n : d(σ) > 2(1−s)n}.

dimMB(C) < s < t < u < 1. By the definition of modified box counting

t-succeeds strongly on elements of Xi, since we can then use the additivity of martingales to combine these into a single martingale that u-succeeds strongly on all elements of C.

So we assume that X 2ω is such that dimB(X) < s < s < t and show that there exists a martingale d that t-succeeds strongly on all A X.

Let Xn = X n, and for σ 2 n, let Xnσ = {τ Xn : σ τ }. There

As t > s, we see that d t-succeeds strongly on all A X.

13.11.4 E ective packing dimension

The somewhat involved definition of packing measures renders a direct Martin-L¨of-style e ectivization in terms of computably enumerable covers di cult. This obstacle can be overcome by using the martingale characterization provided by Theorem 13.11.9.

Definition 13.11.10 (Athreya, Hitchcock, Lutz, and Mayordomo [15]).

The e ective packing dimension of C 2ω is

Dim(C) = inf{s : there is a c.e. martingale that

s-succeeds strongly on all A C}.

In Section 13.11.3 we stated the fact that packing dimension equals upper modified box counting dimension. For individual sets, the modifications to box counting dimension leading to countable stability can be disregarded. A careful e ectivization of the proof of Theorem 13.11.9 yields the following.

Theorem 13.11.11 (Reimann [324]). For every A 2ω, we have

Dim(A) = dim1B(A).

Combining this result with Theorem 13.11.6 allows us to characterize e ective packing dimension in terms of initial segment complexity.

Corollary 13.11.12 (Athreya, Hitchcock, Lutz, and Mayordomo [15]).

A direct proof of this statement can be obtained by a simple modification of the proof of Theorem 13.3.4 (changing liminf’s to limsup’s, “there are infinitely many” to “for almost all”, etc.).

Notice that this characterization makes it clear that a su ciently generic set (say a 2-generic set) has high e ective packing dimension, since the set of strings of high Kolmogorov complexity is dense. Thus packing dimension is a common ground between category and measure.

This characterization also makes it easy to build sets of specified e ective packing dimension, as we saw for e ective Hausdor dimension. Indeed, it is not hard to use it to build, say, a set A such that dim(A) = p and Dim(A) = q for any rationals p and q such that 0 p q 1. In particular, we have the following.

Corollary 13.11.13 (Athreya, Hitchcock, Lutz, and Mayordomo [15]).

There is a set of e ective packing dimension 1 and e ective Hausdor dimension 0.