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.

Authors and Affiliations

1. Technische Universität Berlin, FB Mathematik, Sekr. MA 8-1, Straß e des 17. Juni 135, 10623 Berlin, Germany hammer@math.tu-berlin.de , Germany

   D. Hammer

2. Institute of Problems of Information Transmission, 57th Moscow School, Moscow Mathematics Institute, Moscow, Russia shen@main.mccme.rssi.ru, Russia

   A. Shen

Received April 20, 1993, and in final form December 6, 1993.

Reprints and permissions