13.10 C-independence and Zimand’s Theorem

By Miller’s Theorem 13.8.1, we cannot always extract a sequence of arbitrarily high e ective Hausdor dimension from one of nonzero e ective Hausdor dimension. In this section we prove Zimand’s theorem that such extraction is possible from two su ciently independent sources of positive e ective Hausdor dimension.

We begin by briefly discussing the notion of independence of sources. This notion dates back at least to Chaitin [62], who suggested that objects x and y should be independent in terms of their information if I(x)−I(x | y) and I(y) − I(y | x) are small, where I is some kind of information content measure in the wide sense, such as C or K. For 1-random sets A and B, we could regard A and B as being independent iff they are mutually 1-random.

But what about nonrandom sets? For example, suppose that A and B have positive e ective Hausdor dimension but are not 1-random. What would it mean to say that A and B are independent? The theory here is largely undeveloped, but the following notions of independence are useful for our purposes. In this section, we will regard log factors as being small. We will say a little more about this convention below.10

Definition 13.10.1 (Zimand [424], Calude and Zimand [53]).

(i) X and Y are C-independent 11 if

C((X m) (Y n)) C(X m) + C(Y n) − O(log m + log n).

(ii) X and Y are globally independent if

CX (Y n) C(Y n) − O(log n)

and

CY (X n) C(X n) − O(log n).

Since C and K are within an O(log) factor of each other, both definitions remain the same if we replace C by K. Note also that C((X m) (Y n)) and C((Y n) (X m)) are the same up to an O(log m + log n) factor, so the first definition does not depend on the order of X and Y .

As pointed out by Calude and Zimand [53], other notions of smallness are possible. For example, in (i) we could have O(C(m) + C(n)) in place of O(log m + log n), in which case the definition might be di erent for C and

10In general, working up to O(log n) instead of O(1) smooths out many issues, eliding the di erence between various versions of Kolmogorov complexity, for example. The price one pays is losing the many important phenomena hiding in those log factors, such as K-triviality, the unrelativized complexity characterizations of 2-randomness, and so on.

11Calude and Zimand [53] called this notion finitarily independent. We choose what we feel is a more descriptive name.

628 13. Algorithmic Dimension

for K. These modified concepts remain to be explored. We will stick to log factors, as they give enough independence for the results of this section.

Clearly, if X and Y are mutually 1-random, then they are globally independent, so global independence can be seen as an extension of the notion of mutual randomness. If X is K-trivial, then X and Y are globally independent for all Y , since K(X n) O(log n) and X is low for K, so KX (Y n) = K(Y n) ± O(1). Using Lemma 13.10.2 (ii) below, this observation can be extended to show that if C(X m) O(log m), as is the case for an n-c.e. set, for instance, then X and Y are globally independent for all Y .

The following result is an easy application of symmetry of information (see Section 3.3).

Lemma 13.10.2 (Zimand [424], Calude and Zimand [53]). The following are equivalent.

(i)X and Y are C-independent.

(ii)C(X m | Y n) C(X m) − O(log m + log n).

(iii)C((X n) (Y n)) C(X n) + C(Y n) − O(log n).

(iv)C(X n | Y n) C(X n) − O(log n).

The same holds for K in place of C.

Theorem 13.10.3 (Calude and Zimand [53]). If X and Y are globally independent, then X and Y are C-independent.

Proof. If we have Y as an oracle, we can describe X n by giving n and

n) C (X n) − O(log n) C(X n) − O(log n), and hence item (iv) of Lemma 13.10.2 holds

Stephan (see [53]) showed that the converse fails: there are C- independent X and Y that are not globally independent. He also showed the following.

Proof. Without loss of generality, there are infinitely many n such that, for the least s for which Ys n = Y n, we also have Xs n = X n. For all such n, we have C(X n | Y n) = O(1). But then, since dim(X) > 0, item (iv) of Lemma 13.10.2 cannot hold.

Theorem 13.10.5 (Calude and Zimand [53]). If Y is 1-random relative to X, then X and Y are C-independent.

Proof. By the same argument as in the proof of Theorem 13.10.3, KX (Y n) K(Y n | X n) + 2 log n + O(1). If X and Y are not C-independent then there are infinitely many n with K(Y n | X n) < K(Y n) −

5 log n < n − 3 log n. For such n, we have KX (Y n) n − log n + O(1), contradicting the fact that Y is 1-random relative to X.

We now turn to the task of amplifying the complexity of two C-independent sources.

Theorem 13.10.6 (Zimand [424]). For any rational q > 0, there is a truth table reduction Ψ such that if X and Y are C-independent and have e ective Hausdor dimension greater than q, then dim(ΨX Y ) = 1. Moreover, an index for Ψ can be determined computably from q.

The idea of the proof will be to chop X and Y into suitable bits and reassemble them. A technical combinatorial lemma (Lemma 13.10.14) will be at the heart of the proof. It will use a well-known tool from probability theory, Cherno bounds, which can be found in any standard probability textbook, such as Feller [144].

We give a brief introduction to the main ideas of the proof, following Zimand [424]. Suppose that we have two independent strings σ and τ of length n with C(σ) and C(τ ) both equal to qn for a positive rational q. (The independence here means that C(στ ) is approximately C(σ)+C(τ ) = 2qn.) Suppose further that we can construct a function E : 2n ×2n → 2m for some suitable m, such that E is regular, in the sense that for each su ciently

We claim that if ρ = E(σ, τ ) then the C-complexity of ρ must be large. Assume for a contradiction that C(ρ) < (1 − ε)m for a fairly large ε. We have the following facts.

(i)The set B = {σ 2n : C(σ) = qn} has size approximately 2qn.

(ii)The set A = {τ 2m : C(τ ) < (1 − ε)m} has size less than 2(1−ε)m.

(iii)(σ, τ ) E−1(A) ∩ B × B.

qn 2

Thus |E−1(A)∩B ×B| (22εm) , approximately. If we e ectively enumerate E−1(A) ∩ B × B, then each pair of strings in that set can be described by its position in that enumeration, so C(σ, τ ) 2qn − εm, approximately, which violates the independence hypothesis on σ and τ .

Now the above argument is not quite true, as a function E with the necessary properties may not exist, but in Lemma 13.10.14 we will construct a function that makes the above argument “true enough” to prove the theorem.

630 13. Algorithmic Dimension

Proof of Theorem 13.10.6. Note that, by hypothesis, C(X n) > qn and C(Y n) > qn for all su ciently large n.

Lemma 13.10.7. Let r be a rational such that 0 < r < q. For any su ciently large n0, we can compute an n1 > n0 such that

C(X (n0, n1) | X n0) > r(n1 − n0).

Proof. Let 0 < r < q − r and let n1 = 1r−r n0. Suppose that C(X (n0, n1) | X n0) r(n1 − n0). The string X n1 can be described by

giving a description of X n0 and a description of X (n0, n1) given X n0. Thus, for su ciently large n0, we have

C(X n1) n0 + O(log n0) + r(n1 − n0)

rn1 + (1 − r)n0 + O(log n0) rn1 + r n1 + O(log n0) < qn1.

We use Lemma 13.10.7 to split up X and Y into blocks X1X2 . . .

and Y1Y2 . . . , respectively. Each Xi is chosen based on the conditional complexity given the previous blocks, and similarly for the Yi.

Let a be a number such that Lemma 13.10.7 holds for all n0 a. Let b be the constant 1r−r in the proof of Lemma 13.10.7. Let t0 = 0, let ti = a, and let ti+1 = b(t0 + ··· + ti) for i > 0. For i 1, let Xi = X [ti−1, ti)

ti = ab(1 + b)i−2 for i 2 and |Xi| = |Yi| = ab2(1 + b)i−3 for i 3.

The following lemma follows immediately from the definitions and Lemma 13.10.7.

Lemma 13.10.8. The following hold for all i.

| | |

(i) C(Xi Xi−1) > r Xi .

| | | |

(ii) log Xi i and log Xi i.

The same holds for the Yi.

The following inequalities follow easily by symmetry of information.

Lemma 13.10.9. For all σ and τ ,

(i)C(στ ) C(σ) + C(τ ) + O(log C(σ) + log C(τ )),

(ii)C(τ σ) C(σ) + C(τ | σ) − O(log C(σ) + log C(τ )), and

(iii)|C(σ | τ ) − (C(στ ) − C(τ ))| < O(log |σ| + log |τ |).

Now we assemble some facts about the Xi and Yi.

Lemma 13.10.10. For all i and j,

| − |

(i) C(YiXj ) (C(Yi) + C(Xj )) O(i + j),

and the result now follows by combining this inequality with (13.3). The argument for (iv) is analogous.

C(XiYi | Xi−1Yi−1) C(Xi | Xi−1Yi−1) + C(Yi | Xi−1Yi−1) − O(i).

Proof. Since C(Xi) |Xi| + O(1) and similarly for Yi, if we apply Lemma 13.10.9 (ii) in conditional form, we get

C(XiYi | Xi−1Yi−1) C(Xi | Xi−1Yi−1) + C(Yi | XiYi−1) − O(i).

But C(Yi | XiYi−1) C(Yi | Yi−1) − O(i) C(Yi | Xi−1Yi−1) − O(i), by Lemma 13.10.10 (iv).

We now come to the combinatorial heart of the proof. Let ni = |Xi| =

The pair (Ei, mi) will be chosen so that C(Zi | Xi−1Yi−1) > (1 − ε)mi,

|

which will imply that C(Zi Zi−1) is also close to mi. We will then be able to show that if we define Z = Z1Z2 . . . , then C(Z k) is su ciently close to k for all k.

The exact method of choosing Ei and mi comes from the theory of randomness extractors and hashing. The proof below uses what is known as the probabilistic method.

Definition 13.10.12. A function E : 2n × 2n → 2m is r-regular if for every B1, B2 2n with |Bi| rn for i = 1, 2 and every σ 2m,

|E−1(σ) ∩ (B1 × B2)| 2−m+1|B1 × B2|.

The function E is weakly r-regular if it obeys the above definition when we consider only Bi with |B1| = |B2| = rn .

Lemma 13.10.13. If E : 2n × 2n → 2m is weakly r-regular then E is regular.

Proof. Let k = rn and suppose that for all B1, B2 with |Bi| = 2k and all σ 2m, we have |E−1(σ) ∩ (B1 × B2)| 2−m+1|B1 × B2| = 2−m+1+2k.

Let k1, k2 k and let B1 and B2 be such that |Bi| = 2ki . Partition each

Lemma 13.10.14. For each r > 0, if 2m < r2.99n then with positive

e ectively by searching).

Proof. By the previous lemma, it is enough to show that E is weakly r- regular. Let N = 2n and M = 2m (as numbers).

Choose B1, B2 2n with |Bi| = N r (ignoring rounding for simplicity). Let j1 B1 × B2 and j2 2m. We think of 2n × 2n as a table with N rows and N columns, of 2m as colors, and of E as specifying a coloring. Then B1 × B2 is a rectangle in this table, j1 is a cell in this rectangle, and j2 is one of M possible colors for this cell. Clearly Prob(E(j1) = j2) = M1 .

be the number of j2-colored cells in B1 × B2. If there is no rectangle B1 × B2 and j2 such that − M1 > M1 , then E is weakly r-regular, so it is enough to show that this event has positive probability.

Applying the Cherno bounds mentioned above, we have

Straightforward manipulation shows that this task is the same as showing that N3M2r −ln M > 2N r +2N r(1−r) ln N , which holds when M < N .99r.

We are finally ready to build Z. We proceed as follows.

1. Split X = X1X2 . . . and Y = Y1Y2 . . . as above, using the parameters

2.For the parameters ni = |Xi| = |Yi| and mi = i2, find an r2 -regular function Ei. Let Zi = Ei(Xi, Yi).

3.Let Z = Z1Z2 . . . .

Lemma 13.10.15. For all ε > 0 and all su ciently large i, we have

Lemma 13.10.9 (iii) and (iv), if i is su ciently large then tj > rni −O(i) >