• [41]

(a) Show that d({x : l(x) = n, K(x) < n − K(n) − r}) ≤

2n−r−K(r|n∗)+O(1).

(b) Show that there is a constant c such that if string x of length n ends in at least r + K(r|n∗) + c zeros then K(x) < n + K(n) − r.

(c) Show d({x : l(x) = n, K(x) < n−K(n)−r}) ≥ 2n−r−K(r|n∗)−O(1).

Comments. As usual, n∗ denotes the shortest program for n, and if there is more than one then the first one in standard enumeration.

This improves the counting of the distribution of description lengths in Theorem 3.2.1, Item (ii), to a tight bound, up to a multiplicative constant. Hint: for Item

(c) use Item (b). The right-hand side of Item

(c) equals zero for a negative exponent. Source: [J.S. Miller and L. Yu, Advances Math., 226:6(2011), 4816–4840, 2007 (with as prequel Trans.

Amer. Math. Soc., 360:6(2008), 3193–3210)].