14
$\begingroup$

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:

  1. Prime encodings are algorithmically random and so they would pass the next-bit test [6].

  2. 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:

  1. Dániel Schumayer and David A. W. Hutchinson. Physics of the Riemann Hypothesis. Arxiv. 2011.

  2. Peter D. Grünwald. The Minimum Description Length Principle . MIT Press. 2007.

  3. Olivier Rioul. This is IT: A Primer on Shannon’s Entropy and Information. Séminaire Poincaré. 2018.

  4. Don Zagier. Newman’s short proof of the Prime Number Theorem. The American Mathematical Monthly, Vol. 104, No. 8 (Oct., 1997), pp. 705-708

  5. 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.

  6. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, 1982.

$\endgroup$
5
  • 18
    $\begingroup$ I think most mathematicians use the word "derivation" as a synonym for "proof". I suggest to add the adjective "heuristic" to "derivation". As in "heuristic argument". $\endgroup$ – GH from MO Feb 16 at 3:03
  • 15
    $\begingroup$ This seems to suggest that the log in the prime number theorem should be to base $2$, rather than base $e$, as it is. $\endgroup$ – Will Sawin Feb 16 at 4:31
  • 5
    $\begingroup$ This seems quite related: mathoverflow.net/questions/337875/…. $\endgroup$ – Emil Jeřábek Feb 16 at 10:40
  • 10
    $\begingroup$ I don't see where you used any property of primes. I'm also not sure what's meant by $|\{x_k\}|$. $\endgroup$ – Gerry Myerson Feb 16 at 11:18
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ – Steve Huntsman Feb 16 at 13:47
11
$\begingroup$

You may be interested in this arxiv paper [1], "Some information-theoretic computations related to the distribution of prime numbers", Ioannis Kontoyiannis, 2007.

It discusses Chebyshev's 1852 result,

$$ \sum_{p \leq n} \frac{\log p}{p} \sim \log n , $$

which is related to the prime number theorem and used in proofs of it. The paper begins by sketching Billingsley's 1973 heuristic information-theoretic argument, then makes it rigorous. The heuristic is similar to yours: Suppose we uniquely represent a number $N = \prod_{p \leq N} p^{X_p}$. Then we pick $N$ uniformly at random in $\{1,\dots,n\}$, with an entropy of $\log(n)$. The information contained in the $\{X_p\}$ variables in the same; so that collection has the same entropy. Then there is an argument that the $\{X_p\}$ are approximately geometrically distributed. This winds up giving the left side. (Note we could take all the logs to any base without changing the claim, since the change cancels out on both sides.)

[1] https://arxiv.org/abs/0710.4076

$\endgroup$
9
$\begingroup$

The following argument seems related in spirit (though it shows far less), but may be of independent interest. Let $X$, $N$, etc, be as you defined. Then $X = p_1^{E_1}\cdots p_k^{E_k}$ where the $p_i$ are the primes and the $E_i$ are (quite correlated) random variables, and $k = \pi(N)$. We then have $H(X) = H(E_1,\cdots,E_k) \leq \sum_i H(E_i)$, since neglecting correlations increases entropy. Now, $E_i\leq\log_2N$, so its entropy is at most $\log_2\log_2N$. This means $\pi(N)\geq\log_2N/\log_2\log_2N$. This provides an information-theoretic proof of the infinitude of primes, but the estimate falls far, far short of the PNT.

References: I had found a version of this back in grad school but never wrote it up. But others have thought about this too. You'll find this argument and a bit more here: https://www.dpmms.cam.ac.uk/~ik355/PAPERS/itw-talk.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.