# The Algorithmic Probability of a Prime Number

The Algorithmic Probability of a Prime Number, defined using Levin’s Coding Theorem.

Aidan Rocke https://github.com/AidanRocke
01-07-2022

From a frequentist perspective, the typical probability that we observe a prime $$p \in \mathbb{P}$$ may be defined as follows:

$\begin{equation} \lim_{N \to \infty} \forall X \sim U([1,N]), P(X \bmod p = 0) = \lim_{N \to \infty} \frac{1}{N} \cdot \lfloor \frac{N}{p} \rfloor = \frac{1}{p} \tag{1} \end{equation}$

In order to define the entropy associated with this discrete probability distribution we may introduce the random variable $$x_p \in \{0,1\}$$ defined as follows:

$\begin{equation} \lim_{N \to \infty} \forall X \sim U([1,N]), X \bmod p = 0 \implies x_p = 1 \tag{2} \end{equation}$

and $$x_p = 0$$ otherwise.

In light of Levin’s Coding theorem,

$\begin{equation} -\log_2 m(x) = K_U(x) + \mathcal{O}(1) \tag{3} \end{equation}$

we may define the algorithmic information gained from observing a prime $$p \in \mathbb{P}$$:

$\begin{equation} K_U(x_p) \sim -\log_2 \frac{1}{p} = \log_2 p \tag{4} \end{equation}$

so the prime numbers are algorithmically random. Moreover, Levin’s Coding theorem implies:

$\begin{equation} -\log_2 m(x)^{m(x)} \sim m(x) \cdot K_U(x) \tag{5} \end{equation}$

Thus, from an information-theoretic perspective, Chebyshev’s theorem(1852):

$\begin{equation} H(x_{p_1},....,x_{p_{\pi(N)}}) = \sum_{p \leq N} H(x_p) \sim \sum_{p \leq N} \frac{1}{p} \cdot \log_2 p \sim \log_2 N \tag{6} \end{equation}$

may be understood as the Expected Algorithmic Information gained from observing a prime number of unknown magnitude in the interval $$[1,N] \subset \mathbb{N}$$.

As a direct consequence of the formula for the joint entropy (6), we may deduce that:

$\begin{equation} P(x_p \land x_q) = P(x_p) \cdot P(x_q) \sim 2^{-K_U(x_p)} \cdot 2^{-K_U(x_q)} \sim \frac{1}{p} \cdot \frac{1}{q} \tag{7} \end{equation}$

as the algorithmic randomness of prime numbers (4), guarantees that $$x_p$$ and $$x_q$$ are independent events.

1. Kolmogorov A.N. Three approaches to the quantitative definition of information. Problems Inform. Transmission, 1(1):1–7, 1965.
2. Peter Grünwald and Paul Vitányi. Shannon Information and Kolmogorov Complexity. 2010.
3. MacKay, David J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. ISBN 0-521-64298-1.