[36]

(a) Show that 

x,y,z 2−K(x,y,z) ≤ 1.

(b) Show that 2K(x, y, z) ≤ K(x, y) + K(x, z) + K(y, z) + O(1) for all strings x, y, z with K(x), K(y), K(z) ≤ n

(c) Let X, Y, Z be finite sets. Let f : X × Y → R, g : Y × Z →

R, and h : Z × X → R be functions with nonnegative values. Then



x,y,z∈X,Y,Z f(x, y)g(y, z)h(z, x)

2

≤



x,y∈X,Y f 2(x, y)



·



y,z∈Y,Z g2(y, z)



·



z,x∈Z,X h2(z, x)



.

Comments. Item

(c) is the Loomis-Whitney inequality. This inequality implies the bound on the volume of a three-dimensional body in terms of its two-dimensional projections. Hint for Item (c): Assume for convenience at first that the members of X, Y, Z are strings of length at most n. It is enough to show that if the sums on the right-hand side of the inequality do not exceed 1 then the same is true for the left-hand side.

(Normalize the values of

f, g, h by deviding by a constant so that both sides of the inequality get below 1.) Use Items

(a) and

(b) to obtain a proof for Item (c). A similar result for the plain complexity is Exercise 2.8.5 on page 195. This is further explained by the discussion in the last two paragraphs of Section 6.14. Source: [A.K. Shen,, V.A. Uspensky, and N.K. Vereshchagin, Kolmogorov Complexity and Algorithmic Randomness, American Mathematical Society, 2017]. Item

(c) was the inspiration for the cover design of the Russian original edition.