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

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

## 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$$ :

$\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.

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