A proof of the infinitude of the primes using the incompressibility method

The infinitude of the primes has been known since ancient times thanks to Euclid's reductio ad absurdum proof. Here's what I think might be a new proof of this ancient theorem. It's based around the concept of Kolmogorov-Chaitin algorithmic complexity, specifically as embodied in the so-called "incompressibility method". It may thus be of interest in that it can be added to the growing gallery of proofs that use algorithmic complexity concepts to solve problems whose subject matter is different from the "usual" or "canonical" sort of examples one traditionally comes across in presentations of the theory of algorithmic complexity. Star attractions recently added to this gallery include the proofs by Tao Jiang, Ming Li and Paul Vitanyi concerning a triangle problem of the Heilbronn type (math.CO/9902043) and a lower bound on the average-case complexity of shellsort (cs.CC/9906008). Their proofs are of wholly new results; mine is just a new proof of an old result I'm afraid - but I hope it may still be of some value, in particular for "getting a feel" for the ways the incompressibility method can be applied in varied and diverse problem-solving contexts.

The incompressibility method: a synopsis

Like all the best ideas, the incompressibility method is really quite simple. It comes in various versions: for our purposes here we really only need a cut-down version, as follows. Imagine you already know, by a counting argument or whatever, that there are at least 2 to the power N members of some class. Now suppose that some proposition Prop would imply that these members can all be coded by binary strings of length less than N. By "coded" we mean that there's an algorithm (the encoding algorithm, let's call it) mapping objects of the class to strings of length less than N, such that distinct objects always map to distinct strings. It's quite all right if the encoding algorithm is non-deterministic, so long as it always gives some string as an answer, and distinct objects always map to distinct strings. (In summary: the encoding algorithm, regarded as a multifunction relation from objects to strings, is to be total and nowhere many-to-one.) The coding is then invertible, that is, there is a deterministic, onto (but not necessarily total) decoding algorithm from strings of length less than N to objects of the class, mapping each string which can occur as the output of the encoding algorithm back to the unique object that must have been supplied as input. We will say a string codes for or decodes to an object, with the obvious meaning.

Well then, if Prop implies the possibility of such a coding, then Prop must be false! For there are only (2^N)-1 binary strings of length less than N - the empty string, two strings of length 1, four of length 2, and so on up to 2^(N-1) of length N-1 - and each decodes to at most one object of the class, contradicting that all of the at least 2^N objects of the class have invertible encodings. Thus this version of the incompressibility method is a reductio ad absurdum proof of the negation of Prop.

The name "incompressibility method" comes from thinking of the coding as a compression to compact form of objects whose standard (uncompressed) extant form might be quite large. A fuller version of the method can involve such issues as seeking a limiting compression ratio as the size of an input object tends to infinity; taking into account the length of a purported compression or coding algorithm, considered as a program for some fixed universal Turing machine; and so forth. However, even the cut-down version above can be seen to be about incompressibility - it says you can't losslessly (invertibly) compress all members of some class to binary strings each of length less than the base-2 logarithm of the cardinality of the class.

Suppose there are only finitely many primes...

We take Prop to be the proposition that there are only finitely many primes. I shall show that this would allow a very compact representation of the natural numbers - more compact than writing them in, say, decimal or binary notation. In fact, absurdly compact! So compact as to represent, for some (in fact any) sufficiently large N, the first 2^N natural numbers as binary strings of length less than N, whereupon the incompressibility method delivers the reductio ad absurdum that Prop must be false and there must in fact be infinitely many primes.

The fundamental theorem of arithmetic states that every positive natural number has a unique decomposition as a product of primes, some factors possibly repeated. (The empty product is permitted, and is taken to be 1, the identity for multiplication.) For our purposes, however, we don't need uniqueness - we just need the fact that every positive natural number has a decomposition as a product of primes, which follows immediately from well-foundedness (if the number is composite, split it into proper factors and then care about those factors: this splitting must bottom out, and you've got your decomposition).

Suppose there are only finitely many primes, say K of them. Then we can represent any natural number using the following notation. For zero we use a one-character symbol (we might as well choose 0). For a positive number, we decompose it into a product of primes, and write down for each prime the number of occurrences of that prime in the product - the power which that prime is raised to in the product. Naturally we use, recursively, this notation when writing down each of those powers. For packaging the K powers into a list we can choose any unambiguous notation. For now I'll use square brackets to start and end a list, and commas and whitespace to separate the elements. Taking for example K=5, with the only primes in the world supposedly being 2, 3, 5, 7 and 11, we get these representations of the first few integers:

zero    0                               (our chosen symbol)
one     [0,0,0,0,0]                     (the empty product)
two     [ [0,0,0,0,0], 0, 0, 0, 0 ]     (that's 2 being raised to the power 1)
three   [ 0, [0,0,0,0,0], 0, 0, 0 ]     (that's 3 being raised to the power 1)
four    [ [[0,0,0,0,0], 0, 0, 0, 0],    (that's 2 being raised to the power 2)
                0, 0, 0, 0 ]
five    [ 0, 0, [0,0,0,0,0], 0, 0 ]     (that's 5 being raised to the power 1)
six     [ [0,0,0,0,0], [0,0,0,0,0],     (2 and 3 are each raised to the power 1)
                0, 0, 0 ]
seven   [ 0, 0, 0, [0,0,0,0,0], 0 ]     (that's 7 being raised to the power 1)
eight   [ [0, [0,0,0,0,0], 0, 0, 0],    (that's 2 being raised to the power 3)
                0, 0, 0, 0 ]
.
.
.

The reader will be forgiven for thinking this is not a very compact notation for the natural numbers! Nevertheless, it is in fact absurdly compact as intimated earlier. To perform a length analysis, let's first simplify and standardize the layout. We can obviously drop all the commas and whitespace, which are just a sop to human readability, without compromising the notation. Less obvious, but also true, is that we can drop the closing brackets - all the lists are of length K, so if you've read K list elements, you know you're finished! So we're down to two characters, 0 and [. This is convenient since it means the strings are then already "binary"; with more than two characters we'd get bogged down in tedious accounting of bits-per-character and the like. The stripped representations:

zero    0
one     [00000
two     [[000000000
three   [0[00000000
four    [[[0000000000000
five    [00[0000000
six     [[00000[00000000
seven   [000[000000
eight   [[0[000000000000
.
.
.

These, although confusing to a human reader, are perfectly unambiguous to the decoding algorithm, which (just as you'd expect) goes as follows: if the string is 0, the answer is zero; otherwise skip the [ symbol, then read and decode exactly K substrings, using recursive descent parsing with this algorithm as the decoding algorithm for the substrings, whereupon the answer is the product of the K primes raised to those respective decoded powers.

Now then! We perform an inductive length analysis on facts of the form "the first so-and-so-many natural numbers are all coded by strings of length less than such-and-such".

• Base case: "The first one natural numbers are all coded by strings of length less than two." This is trivial since zero is coded by the string 0, of length 1.

• Inductive case: "If the first N natural numbers are all coded by strings of length less than L, then the first 2^N natural numbers are all coded by strings of length less than KL." (K, remember, is our name for how many primes there are supposed to be.)

  Proof of inductive case: To be among the first 2^N natural numbers is simply to be less than 2^N. Such a number must therefore have fewer than N factors of 2, let alone of any other particular prime, in a decomposition of it into prime factors. Thus all K powers of primes in the decomposition are less than N, and by the inductive hypothesis have codings of length less than L. The coding for our number thus has a length of the sum of those K lengths each less than L, plus one for the [ symbol - that is, a total length less than KL.

By induction, we see that the first 2^(2^...(2^(2^(2^2)))...) (tower of height T of iterated powers of 2) natural numbers are all coded by strings of length less than 2(K^T). That "tower of powers", by the way, is sometimes called "2 tetrated by T", tetration being iterated exponentiation in the same way that exponentiation is iterated multiplication, and multiplication is iterated addition.

Since tetration is far faster-growing than exponentiation, by taking T above large enough we can make the binary logarithm of 2 tetrated by T (which is just 2 tetrated by T-1 in fact!) larger than 2(K^T). The incompressibility method then gives us the reductio ad absurdum we crave: that Prop is false and there are infinitely many primes.

Can this sort of proof be taken further?

Here are some thoughts on where we might go from here in using the incompressibility method in number theory and related fields.

• There's a lot of "slack" in the gap in growth rates between exponentiation and tetration - but we only used the mere existence of the gap in the proof above. Can we put the slack to productive use? We might be able to use the incompressibility method to reach conclusions about the number density of the primes. Basically they mustn't become too sparse, as otherwise the representation of natural numbers used above (or something like it) would become "too efficient" and lead to an absurdity. Can we, say, obtain a new proof of the theorem that for large N, the local number density of the primes tends to 1/ln(N)?
• There are systems other than the natural numbers which have elements analogous to the primes - "atoms" of whatever plays the role of multiplication. Can we prove anything about the distribution of such elements in the system they belong to?

I'd be delighted to hear from anyone who succeeds in taking things further in these or any other ways. Good luck to anyone who tries their hand!

This corner of the web maintained by Iain Stewart <ids@doc.ic.ac.uk>, Department of Computing, Imperial College, London, UK

- add your own comments to this web page or any other for all to see! (Only supported by some browsers, sometimes via an extension or the like.)

(If you're reading this from within IC DoC you can try Crit, an earlier way to annotate the web. )