Incompressibility method

DRAFT OF AN ARTICLE. UNDER CONSTRUCTION. The incompressibility method is a proof method such as th probabilistic method, the counting method, or the pigeon-hole method. The method proceeds as follows: If we want to prove that an object of a certain type in expectation satisfies a certain property, then we select an object of that type which is incompressible but for a few bits and show that if it satisfies the property than it can be compressed. Since almost all objects of that type are incompressible the argument shows that almost all objects have the property involved. To select an incompressible object is not effective, it cannot be done by a computer program. But a simple counting argument shows that almost all objects of a given type can only be compressed by a few bits. Therefore the property is satisfied by almost all objects of the given type.

History

Although the incompressibity method is presumably older, its application depended on an objective and fixed notion of incompressibility. Such a notion was provided by Kolmogorov complexity due to Andrey Kolmogorov The Kolmogorov complexity of an object (represented by a finite binary string) is the length of a shortest program on a fixed optimal universal Turing machine (optimality here has a technical meaning). Since the machine is fixed and the program concerned is shortest the Kolmogorov complexity is a definite positive integer. The Kolmogorov complexity of an abject is thus the length of a shortest program from which it can be computed. Therefore it is a lower bound on the length of a compressed version (in bits) of that object by any existing or future compression program. The first who used the incompressibility metod with Kolmogorov complexity was apparently Wolfgang Paul He proved that the running time of a 1-tape Turing machine is quadratic for accepting a palindromic language and showed that sorting algorithms require at least $n\log n$ time for sorting $n$ items.The initally most influentail paper using the incompressibility method was Hereaftr the method was applied in many fields and codified and named in the text

Fields of Application

Number Theory

A beatiful proof of Euclid shows that there are infinitely many prime numbers. Eventually Riemann showed that the number of primes less than a given number is connected with the 0s of the Riemann zeta function Hadamard and de la Vallee Poussin proved in the 19th century (1896) that thi number of primes is asymptotic to $n/\log n$. Using the incompressibilty method G.J. Chaitin (attributed) argued as follows. For each $n$ we can describe it by giving its prime factorization $n=p_{1}^{n_{1}}*\cdots *p_{k}^{n_{k}}$ (which is unique) with $p_{1},\ldots ,p_{k}$ the first $k$ primes at most $n$ and the exponents possibly 0. Each exponent is at most $\log n$ and can be described by $\log \log n$ bits. Therefore the description of $n$ can be given in $l\log n$ bita provided we know the value of $\log \log n$ enabling us to parse the consequetive blocks of exponents. Using the incompressiblity of most positive integers in that for each $l>0$ there is a positive integer $n$ of binary length $l\approx \log n$ that cannot be described in less than $l$ bits shows that the number of primes $\pi (n)$ less than $n$ satisfies $\pi (n)\geq ((\log n)/(\log \log n))-o(1)$.