Cramér’s random model as a Poisson Process

In this article we demonstrate that Cramér’s model is well-approximated by a Poisson Process, and that Cramér’s conjecture may be deduced from an entropy bound on prime gaps.

Cramér’s random model:

Given the asymptotic density of the prime numbers:

\[\begin{equation} \frac{N}{\pi(N)} \sim \frac{1}{\ln N} \tag{1} \end{equation}\]

Harald Cramér developed a probabilistic model for the distribution of primes whereby the prime numbers are modelled by independent random variables \(X(n)\) for \(n \geq 3\) where:

\[\begin{equation} P(X(n)=1) \sim \frac{1}{\ln n} \tag{2} \end{equation}\]

\[\begin{equation} P(X(n)=0) \sim 1- \frac{1}{\ln n} \tag{3} \end{equation}\]

Using this model, Cramér demonstrated that the upper-bound on prime gaps is almost surely:

\[\begin{equation} p_{n+1}-p_n = \mathcal{O}((\ln p_n)^2) \tag{4} \end{equation}\]

In this article we shall demonstrate that Cramér’s model is well-approximated by a Poisson Process, and that Cramér’s conjecture (4) may be deduced from an entropy bound on prime numbers of unknown magnitude sampled from the interval \([1,N] \subset \mathbb{N}\).

Cramér’s random model as a Poisson Process:

Using Cramér’s random model, we may determine that for large \(N \in \mathbb{N}\):

\[\begin{equation} \frac{1}{N} \cdot \#\{n \leq N: \pi(n + \lambda \cdot \ln n)-\pi(n)=k\} \sim P(k | N = \lfloor \lambda \cdot \ln n \rfloor) \tag{5} \end{equation}\]

\[\begin{equation} P(k|N = \lfloor \lambda \cdot \ln n \rfloor) \sim \frac{N!}{k!(N-k)!} \big(\frac{\lambda}{N}\big)^k \cdot \big(1-\frac{\lambda}{N}\big)^{N-k} \tag{6} \end{equation}\]

Given the RHS of (6), we find that:

\[\begin{equation} \frac{N!}{(N-k)!} \sim N^k \tag{7} \end{equation}\]

since for \(k \ll N\), Stirling’s approximation applied to the denominator of (6) yields:

\[\begin{equation} \big(\frac{N-k}{e}\big)^{N-k} = \big(\frac{N}{e}\big)^{N-k} \cdot \big(1-\frac{k}{N}\big)^{N-k} \sim \big(\frac{N}{e}\big)^{N-k} \cdot e^{-k} \sim \big(\frac{N}{e}\big)^N \cdot N^{-k} \tag{8} \end{equation}\]

as \(\big(1-\frac{k}{N}\big)^{-k} \rightarrow 1\) as \(N \to \infty\).

Given (8), (6) simplifies to:

\[\begin{equation} P(k|N = \lfloor \lambda \cdot \ln n \rfloor) \sim \frac{\lambda^k}{k!} \big(1-\frac{k}{N}\big)^{N-k} \tag{9} \end{equation}\]

and \(\big(1-\frac{\lambda}{N}\big)^{-k} \rightarrow 1\) as \(N \to \infty\), so (9) further simplifies to:

\[\begin{equation} P(k|N = \lfloor \lambda \cdot \ln n \rfloor) \sim \frac{\lambda^k}{k!} \big(1-\frac{k}{N}\big)^N \tag{10} \end{equation}\]

Finally, using the fact that \(\ln \big(1+\frac{1}{N}\big) \sim \frac{1}{N}\),

\[\begin{equation} \exp\big(\ln \big(1-\frac{\lambda}{N}\big)^N\big) \sim \exp \big(-N \cdot \frac{\lambda}{N}\big) = \exp(-\lambda) \tag{11} \end{equation}\]

so we may conclude that:

\[\begin{equation} \lim_{N \to \infty} \frac{1}{N} \cdot \#\{n \leq N: \pi(n + \lambda \cdot \ln n)-\pi(n)=k\} \sim \frac{\lambda^k}{k!}\cdot e^{-\lambda} \tag{12} \end{equation}\]

The expected number of primes in the interval \([N, N + \lambda \cdot \ln N]\)

We may verify that Cramér’s random model predicts that the expected number of primes in the interval \([N, N + \lambda \cdot \ln N]\) is on the order of \(\sim \lambda\) where \(0< \lambda \lesssim \ln N\). Moreover, this prediction is in complete agreement with that predicted by the Prime Number Theorem.

Given the Prime Number Theorem, for large \(N \in \mathbb{N}\):

\[\begin{equation} \forall \lambda \in (0,\ln N] \forall X \sim U([1,N]), \mathbb{E}[\pi(X + \lambda \cdot \ln X)-\pi(X)] \sim \pi(N+\lambda \cdot \ln N)-\pi(N) \tag{13} \end{equation}\]

which simplifies to:

\[\begin{equation} \pi(N+\lambda \cdot \ln N)-\pi(N) \sim \frac{N +\lambda \cdot \ln N}{\ln N}-\frac{N}{\ln N} = \lambda \tag{14} \end{equation}\]

As one might anticipate, this is in complete agreement with the expected number of primes calculated using Cramér’s random model:

\[\begin{equation} \sum_{k=0}^\infty k \cdot \frac{\lambda^k e^{-k}}{k!} = \sum_{k=1}^\infty k \cdot \frac{\lambda^k \cdot e^{-k}}{k!} = \lambda \cdot e^{-\lambda} \sum_{k=1}^\infty \frac{\lambda^{k-1}}{(k-1)!} = \lambda \cdot e^{-\lambda} \sum_{k=0}^\infty \frac{\lambda^k}{k!} = \lambda \tag{15} \end{equation}\]

Such a verification is an important sanity check as Cramér’s random model was derived from the Prime Number Theorem. However, it remains to be determined that the bound on \(\lambda\) may be carefully justified.

An information-theoretic upper-bound on prime gaps:

Given that for fixed \(\lambda \in (0, \ln N]\) and large \(N \in \mathbb{N}\), Cramér’s model is well-approximated by the Poisson Process:

\[\begin{equation} \lim_{N \to \infty} \frac{1}{N} \cdot \#\{n \leq N: \pi(n + \lambda \cdot \ln n)-\pi(n)=k\} \sim f(k |\lambda) \tag{16} \end{equation}\]

\[\begin{equation} f(k|\lambda) = \frac{\lambda^k}{k!} \cdot e^{-\lambda} \tag{17} \end{equation}\]

this model may be used to analyse prime gaps:

\[\begin{equation} P(p_{n+1}-p_n \sim \lambda \cdot \ln n) \sim f(k=0|\lambda) = e^{-\lambda} \tag{18} \end{equation}\]

Now, given that Chebyshev’s theorem implies that the average information gained from observing a prime number in the interval \([1,N]\) is on the order of \(\sim \ln N\) [3]:

\[\begin{equation} \sum_{p \leq N} \frac{1}{p} \cdot \ln p \sim \ln N \tag{19} \end{equation}\]

we may define the entropy bound:

\[\begin{equation} -\ln P(p_{n+1}-p_n \sim \lambda \cdot \ln n) \lesssim \ln N \implies \lambda \lesssim \ln N \tag{20} \end{equation}\]

and without loss of generality, if we assert that \(N \in \mathbb{P}\) we find that:

\[\begin{equation} p_{n+1}-p_n = \mathcal{O}((\ln p_n)^2) \tag{21} \end{equation}\]

as predicted by Harald Cramér.

References:

1. Cramér, H. “On the Order of Magnitude of the Difference Between Consecutive Prime Numbers.” Acta Arith. 2, 23-46, 1936.

2. K. Soundararajan. The distribution of prime numbers. Arxiv. 2006.

3. Rocke (2022, Jan. 15). Kepler Lounge: Three master keys for Probabilistic Number Theory. Retrieved from keplerlounge.com