Infinitude of primes by incompressibility

Occam’s razor states that entities must not be multiplied beyond necessity. What is necessity?

Definition Kolmogorov complexity of a string x is the length of the shortest possible program p that outputs x, i.e.

K_f (x) = \min\{|p| : f(p) = x\}.

The Kolmogorov complexity measures the information content. The function K_f(x) is (in general) not computable, although the Kolmogorov complexity of an integer is computable.

C_f (x) = \min\{|E| : E\textnormal{ has value }x\},

where E is some prime factorisation. We can use this is prove the infinitude of primes (which of course is a rather simple proof without incompressibility):

Any number m can be represented as m = p_1^{e_1} p_2^{e_2}...p_k^{e_k} . Now assume that there are only k distinct primes. The exponents are then \forall i : e_i \leq \log_2{m}. We can then further represent the exponents by k \log_2 \log_2 m bits, so

\frac{\log_2 m}{\log_2 \log_2 m} > k \iff k \log_2 \log_2 m < \log_2 m.

And this is a contradiction? Why? Because of incompressibility! According to this, we would be able to describe any number m with less than \log_2 m bits! So there must be infinitely many primes…


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s