Motivation:
While going through a couple interesting papers on the Physics of the Riemann Hypothesis [1] and the Minimum Description Length Principle [2], a derivation(not a proof) of the Prime Number Theorem occurred to me. I thought I would share it here as I wonder whether other mathematicians have pursued this direction. It appears to have interesting implications although the arguments are elementary.
An information-theoretic derivation of the prime number theorem:
If we know nothing about the primes in the worst case we may assume that each prime number less than or equal to $N$ is drawn uniformly from $[1,N]$. So our source of primes is:
\begin{equation} X \sim U([1,N]) \tag{1} \end{equation}
where $H(X) = \ln(N)$ is the Shannon entropy of the uniform distribution.
Now, given a strictly increasing integer sequence of length $N$, $U_N = \{u_i\}_{i=1}^N,$ where $u_i = i$ we may define the prime encoding of $U_N$ as the binary sequence $X_N = \{x_i\}_{i=1}^N$ where $x_i =1$ if $u_i$ is prime and $x_i=0$ otherwise. With no prior knowledge, given that each integer is either prime or not prime, we have $2^N$ possible prime encodings(i.e. arrangements of the primes) in $[1,N] \subset \mathbb{N}$.
If there are $\pi(N)$ primes less than or equal to $N$ then the average number of bits per arrangement gives us the average amount of information gained from correctly identifying each prime number in $U_N$ as:
\begin{equation} S_c = \frac{\log_2 (2^N)}{\pi(N)}= \frac{N}{\pi(N)} \tag{2} \end{equation}
Furthermore, if we assume a maximum entropy distribution over the primes then we would expect that each prime is drawn from a uniform distribution as in (1) so we would have:
\begin{equation} S_c = \frac{N}{\pi(N)} \sim \ln(N) \tag{3} \end{equation}
As for why the natural logarithm appears in (3), we may first note that the base of the logarithm in the Shannon Entropy may be freely chosen without changing its properties. Moreover, given the assumptions if we define $(k,k+1] \subset [1,N]$ the average distance between consecutive primes is given by the sum of weighted distances $l$:
\begin{equation} \sum_{k=1}^{N-1} \frac{1}{k} \lvert (k,k+1] \rvert = \sum_{k=1}^{N-1} \frac{1}{k} \approx \sum_{l=1}^\lambda l \cdot P_l \approx \ln(N) \tag{4} \end{equation}
where $P_l = \frac{1}{l} \cdot \sum_{k= \frac{l \cdot (l-1)}{2}}^{\frac{l\cdot (l-1)}{2}+l-1} \frac{1}{k+1}$ and $\lambda = \frac{\sqrt{1+8(N+1)}-1}{2}$.
This is consistent with the maximum entropy assumption in (1) as there are $k$ distinct ways to sample uniformly from $[1,k]$ and a frequency of $\frac{1}{k}$ associated with the event that a prime lies in $(k-1,k]$. The computation (4) is also consistent with Boltzmann's notion of entropy as a measure of possible arrangements.
There is another useful interpretation of (4). If we break $\sum_{k=1}^{N} \frac{1}{k}$ into $\pi(N)$ disjoint blocks of size $[p_k,p_{k+1}]$ where $p_k,p_{k+1} \in \mathbb{P}$:
\begin{equation} \sum_{k=1}^{N} \frac{1}{k} \approx \sum_{k=1}^{\pi(N)} \sum_{n=p_k}^{p_{k+1}} \frac{1}{n} = \sum_{k=1}^{\pi(N)} (p_{k+1}-p_k)\cdot P(p_k) \approx \ln(N) \tag{5} \end{equation}
where $P(p_k)= \frac{1}{(p_{k+1}-p_k)} \sum_{b=p_k}^{p_{k+1}} \frac{1}{b}$. So we see that (4) also approximates the expected number of observations per prime where $P(p_k)$ may be interpreted as the probability of a successful observation in a frequentist sense. This is consistent with John Wheeler's it from bit interpretation of entropy [5], where the entropy measures the average number of bits(i.e. yes/no questions) per prime number.
Now, we note that given (3), (4) and (5) we have:
\begin{equation} \pi(N) \sim \frac{N}{\ln(N)} \tag{6} \end{equation}
which happens to be equivalent to the prime number theorem.
Discussion:
This investigation has several consequences which may demystify the original assumptions. There are stronger motivations for maximum entropy distributions besides complete ignorance.
By the Shannon source coding theorem, we may infer that $\pi(N)$ primes can't be compressed into fewer than $\pi(N) \cdot \ln(N)$ bits so this result tells us something about the incompressibility of the primes. Why might they be incompressible? By definition, all integers have non-trivial prime factorisations except for the prime numbers.
In fact, there is a strong connection between maximum entropy distributions and incompressible signals. This connection may be clarified by the following insight:
\begin{equation} \mathbb{E}[K(X_N)] \sim \pi(N) \cdot \ln(N) \sim N \tag{7} \end{equation}
where the implicit assumption here is that for any recursive probability distribution, the expected value of the Kolmogorov Complexity equals the Shannon entropy. The distribution of the prime numbers is such a distribution as it is computable.
Testable predictions:
This model implies that independently of the amount of data and computational resources at their disposal, if the best machine learning model predicts the next $N$ primes to be at $\{a_i\}_{i=1}^N \in \mathbb{N}$ then for large $N$ their model's statistical performance will converge to an accuracy that is no better than:
\begin{equation} \frac{1}{N}\sum_{i=1}^N \frac{1}{a_i} \tag{8} \end{equation}
Moreover, it is not possible to prove that a particular object is incompressible within algorithmic information theory so the best we can do is perform rigorous experimental analysis using machine learning methods. There are in fact, two experimentally verifiable propositions:
Prime encodings are algorithmically random and so they would pass the next-bit test [6].
The true positive rate for any computable primality test with bounded algorithmic information content(i.e. bounded memory) converges to zero.
So far I have empirically explored both hypotheses for all prime numbers under a million(i.e. $\pi(N = 10^6$)) and I have defined a specific machine learning challenge which may be used to assess both hypotheses using state-of-the-art machine learning methods.
Question:
Has this line of reasoning already been developed?
Note: I wrote a few more thoughts on the subject on my blog.
References:
Dániel Schumayer and David A. W. Hutchinson. Physics of the Riemann Hypothesis. Arxiv. 2011.
Peter D. Grünwald. The Minimum Description Length Principle . MIT Press. 2007.
Olivier Rioul. This is IT: A Primer on Shannon’s Entropy and Information. Séminaire Poincaré. 2018.
Don Zagier. Newman’s short proof of the Prime Number Theorem. The American Mathematical Monthly, Vol. 104, No. 8 (Oct., 1997), pp. 705-708
John A. Wheeler, 1990, "Information, physics, quantum: The search for links" in W. Zurek (ed.) Complexity, Entropy, and the Physics of Information. Redwood City, CA: Addison-Wesley.
Andrew Chi-Chih Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.
