The Algorithmic Probability of a Prime Number

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

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.

References:

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.