A Strange Application of Kolmogorov Complexity

This paper deals with two similar inequalities: where K denotes simple Kolmogorov entropy (i.e., the very first version of Kolmogorov complexity having been introduced by Kolmogorov himself) and KP denotes prefix entropy (self-delimiting complexity by the terminology of Li and Vitanyi 1]). It turns out that from (1) the following well-known geometric fact can be inferred: where V is a set in three-dimensional space, S _xy , S _yz , S _xz are its three two-dimensional projections, and |W| is the volume (or the area) of W . Inequality (2), in its turn, is a corollary of the well-known Cauchy—Schwarz inequality. So the connection between geometry and Kolmogorov complexity works in both directions. Received April 20, 1993, and in final form December 6, 1993.