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

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

$$n = \prod_{l=1}^k p_l^{\alpha_l}$$

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

Given that $$p_l \geq 2$$,

$$\forall l \in [1,k], \alpha_l \leq \log_2 n$$

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:

$$k \cdot \log_2 \log_2 n$$

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:

$$\pi(n) \cdot \log_2 \log_2 n \geq \log_2 n$$

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$$:

$$\pi(n) \geq \frac{\log_2 n}{\log_2 \log_2 n}$$

which implies that there are infinitely many prime numbers.

## References:

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.