Chaitin’s proof of the infinitude of primes [1]:

Each integer \(n \in \mathbb{N}\) may be described by its prime factorisation:

\begin{equation} n = \prod_{l=1}^k p_l^{\alpha_l} \end{equation}

so \(\pi(n)=k\) assuming that some exponents \(\alpha_l\) equal zero.

Given that \(p_l \geq 2\),

\begin{equation} \forall l \in [1,k], \alpha_l \leq \log_2 n \end{equation}

and so any exponent may be described using \(\log_2 \log_2 n\) bits.

Now, assuming that the value of \(\log_2 \log_2 n\) is known the integer \(n\) may be described using:

\begin{equation} k \cdot \log_2 \log_2 n \end{equation}


However, given that most integers are incompressible [3] there are integers of binary length \(l = \log_2 n\) which can’t be described in fewer than \(l\) bits. So we may deduce that:

\begin{equation} \pi(n) \cdot \log_2 \log_2 n \geq \log_2 n \end{equation}

for almost all positive integers \(n \in \mathbb{N}\).

This allows us to deduce a useful lower bound on the prime counting function for almost all \(n\):

\begin{equation} \pi(n) \geq \frac{\log_2 n}{\log_2 \log_2 n} \end{equation}

which implies that there are infinitely many prime numbers.


  1. Gregory Chaitin. META MATH! The Quest for Omega. Arxiv. 2004.
  2. Lance Fortnow. Kolmogorov Complexity. 2000.
  3. Aidan Rocke. Almost all integers are incompressible. Kepler Lounge. 2021.