[31] Let x be a binary string of length n, and B1(x,

d) be the set of strings y with E1(x, y) ≤

d. Let the number of elements in B1(x,

d) be denoted by b1(x, d). The set B1

(d, x, n) is defined as B1(x, d)

{0, 1}n and b1

(d, x, n) is the number of elements in B1

(d, x, n).

(a) Show that up to an additive constant, log b1

(d, x) = d − K(d|x) and d − K

(d) < log b1

(d, x, n) < d − K(d|x). The last equation holds only for n ≥ d − K(d); for n

(d) we have log b1

(d, x, n) = n up to an additive constant.

(b) Let x be a binary string. Show that the number b3

(d, x) of binary strings y with E3(x, y) ≤ d satisfies log b3

(d, x) = d − K(d|x) up to an additive logarithmic term.

(c) For the number of strings of length n close to a random string x of length n (that is, K(x) ≥ n) in the distance E3, the picture is different from that for distance E1 in Item (a). In distance E3, ‘tough guys have few neighbors of their own size.’ Show that a random string x of length n has only about 2d/2 strings of length n within E3-distance d (while there are essentially 2d such strings within E1-distance d).

(d) Generalize Item (c): Let binary string x have length n. Show that for every x, the number of y’s of length n such that E3(x, y) ≤ d is 2α, with

α = 1 2 (n + d − K(x)) ± O(log n) for n − K(x) ≤

d. and α = d ± O(log n)

for n − K(x) > d.

(e) Let c be a constant and let S be a set with cardinality d(S)=2d and K(S) = c log

d. Show that almost all pairs of elements x, y ∈ S have distance E1(x, y) ≥

d, up to an additive logarithmic term. Show that a similar statement can be proved for the distance of a string x (possibly outside S) to the majority of elements y in S. If K(x) ≥ n, then for almost all y ∈ S we have E1(x, y) ≥ n + d ± O(log dn).

Comments. We estimate the density of strings in balls centered on a particular string under different distance measures. In a discrete space with a distance function, the rate of growth of the number of elements in balls of size d can be considered as a kind of dimension of the space. Hint for Item (b): the upper bound follows from Item

(a) since E3 ≥ E1; for the lower bound, consider strings y of the form px, where p is a self-delimiting program. Source: [C.H. Bennett, P. G´acs, M. Li, P.M.B. Vit´anyi, and W.H. Zurek, IEEE Trans. Inform. Theory, 44:4(1998), 1407–1423].