# Using the incompressibility method for counting prime numbers

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

bits.

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.

## References:

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