# 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…