• [41] Let k be a positive integer, X a multiset with d(X) =

n ≥ 2, and maxx∈X{C(X|x, d(X) )} = k. Theorem 8.5.1 on page 699

(respectively its corollary) give an upper bound on ID(X) defined in Definition 8.5.1 on page 698 using plain Kolmogorov complexity. Here we are interested in a lower bound. Show that there are infinitely many k such that ID(X) ≥ k + log n − O(1).

Comments. Since the bound in Theorem 8.5.1 (respectively its corollary) and the one given here differ only by an additive constant they are tight. That is, the theorem can not be improved. Source: [P.M.B.

Vit´anyi, IEEE Trans. Inform. Theory, 63:8(2017), 4725-4728]. In [C.

Long, X. Zhu, M. Li, and B. Ma, Proc. 17th ACM Conf. Inform. Knowledge Management, 2008, 1213–1220] the notion of information distance for multisets was originally proposed using prefix Kolmogorov complexity. It purported wrongly to prove a claim similar to Theorem 8.5.1 on page 699. Hint: use [H.S.M. Coxeter, Projective Geometry, 2nd Ed., Springer-Verlag, New York, 1987]. The number of strings of length less than or equal k is f(k)=2k+1 − 1. Let integer q be a prime power, n = q + 2, and k satisfies 2k < t(q + 1) ≤ 2k+1 for some positive integer t. Let (P, L) be the projective plane over GF(q) with P the set of points and L the set of lines. (Then d(P) = d(L) = q2 + q + 1, each point is on q + 1 lines and every line contains q + 1 points. Every pair of lines intersect in a point.) Add td(L) dummy points. For every line l ∈ L make t copies of l and add to each of the resulting lines a different dummy point such that all sets of points on a line become different. Let F be the resulting collection of sets of cardinality n. Then every set in F is different and every two sets in F intersect (the two corresponding lines intersect at a point). Every point is on t(q+ 1) sets in F. Show that each set in F has low Kolmogorov complexity and that d(F) labels are required to label the edges incident on a member of F in G defined as in the proof of Theorem 8.5.1.