Distribution of Primes

The prime number theorem describes the asymptotic distribution of prime numbers. It gives us a general view of how primes are distributed amongst positive integers and also states that the primes become less common as they become larger. Informally, the theorem states that if any random positive integer is selected in the range of zero to a large number $N$, the probability that the selected integer is a prime is about $\frac{1}{\ln N},$ where $\ln N$ is the natural logarithm of $N$.

One application of the theorem is that it gives a sense of how long it will take to find a prime of a certain size by a random search. Many cryptosystems (e.g. RSA) require primes $p \approx 2^{512}$; the theorem says that the probability that a randomly chosen number of that size is prime is roughly

$$\frac{1}{\ln\big(2^{512}\big)} \approx \frac1{355},$$

or $\frac1{177}$ if the search is restricted to odd numbers. So the expectation is that roughly $177$ numbers will have to be tested for primality, which can be computationally expensive.

To understand the precise statement of the theorem, define $π(x)$ to be the prime-counting function that gives the number of primes less than or equal to $x$, for any real number $x$. For example, $π(10) = 4$ because there are four prime numbers (2, 3, 5, and 7) less than or equal to 10. It is a well-known result that $\lim_{x\to\infty} \pi(x) = \infty$. The next natural question to ask is, "How fast does $\pi(x)$ go to infinity?" The prime number theorem provides the answer: at the same rate as $\frac{x}{\ln(x)},$ i.e.

$$\lim_{x\to\infty}\frac{\pi(x)}{\hspace{2mm} \frac{x}{\ln(x)}\hspace{2mm} }=1,$$

or written with the asymptotic notation,

$$\pi(x)\sim\frac{x}{\ln x}.$$

Note that this notation (and the theorem) does not say anything about the limit of the difference of the two functions as $x \to \infty$. Indeed, this difference tends to infinity as $x$ increases. The theorem does say that this difference tends to infinity more slowly than $\frac{x}{\ln x}$ does.

The function $\text{Li}(x) = \int_2^x\frac{dt}{\ln(t)}$ is actually a closer approximation to $\pi(x)$. It is an easy calculus exercise that $\text{Li}(x) \sim \frac{x}{\ln(x)}$, so $\text{Li}(x) \sim \pi(x)$ as well. Many more precise statements about the size of $\pi(x)$ use $\text{Li}(x)$. Here is a table comparing values of these functions, where the relative error is computed as $\frac{\left\lfloor \text{Li}(x) \right\rfloor -\pi(x)}{\pi(x)}:$

The prime number theorem is equivalent to the statement that the $n^\text{th}$ prime number $p_n$ satisfies

$$p_n \sim n\ln(n),$$

the asymptotic notation meaning again that the relative error of this approximation approaches $0$ as $n$ approaches infinity.

The Riemann zeta function has a deep connection with the distribution of primes. The famous Riemann hypothesis, about the zeroes of the zeta function, is equivalent to many statements involving prime numbers. In particular, it is equivalent to a much tighter bound than can currently be proven on the error in the estimate for $\pi(x)$:

$$\pi(x) = \operatorname{Li}(x) + O\big(\sqrt{x} \log{x}\big)$$

(see big O notation for an explanation of the latter term). More explicitly, the Riemann hypothesis implies

$$\big|\pi(x) - \operatorname{li}(x)\big| < \frac{1}{8\pi} \sqrt{x} \, \log(x) \quad \text{for all } x \ge 2657,$$

where $\operatorname{li}(x) = \int_0^x \frac{dt}{\ln(t)} = \operatorname{Li}(x) + \operatorname{li}(2)$.

Let $c > 1$ be a real number. Show that for sufficiently large $x$, there is always a prime between $x$ and $cx$.

---

We have

$$\pi(cx) \sim \frac{cx}{\ln(cx)} \sim \frac{cx}{\ln(x)} \sim c\pi(x).$$

So $\lim_{x\to\infty} \frac{\pi(cx)}{\pi(x)} = c,$ and therefore $\frac{\pi(cx)}{\pi(x)} > 1$ for sufficiently large $x$. $_\square$

For $c=2,$ this statement is known as Bertrand's postulate; using more precise estimates for $\pi(x)$, one can show that there is always a prime between $x$ and $2x$ for $x > 3$.

From the classical proof of Dirichlet's theorem on primes in arithmetic progressions, it is known that for any positive integer $n$, the prime numbers are approximately evenly distributed among the reduced residue classes modulo $n$ (i.e., the residue classes that are relatively prime to $n$). For example, the reduced residue classes modulo $10$ are 1, 3, 5, and 7, so one would expect that $\frac{1}{4}$ of all prime numbers end in 1, $\frac{1}{4}$ end in 3, and so on.

Surprisingly, in 2016, mathematicians Robert Lemke Oliver and Kannan Soundarajan discovered that this equidistribution does not persist, at least for relatively small $x,$ when one considers the distribution of pairs of consecutive primes, modulo $n$. Consider, for example, the distribution of prime pairs modulo $3$. Let

$$\pi\big(x; (i,j)\big) := \# \text{ of pairs of consecutive primes } (p, q) \text{ such that } p \equiv i \bmod{3} \text{ and } q \equiv j \bmod{3}.$$

If the primes were truly random, one might expect the limiting proportions

$$\lim_{x\to\infty} \frac{\pi\big(x; (1,1)\big)}{\pi(x)} = \lim_{x\to\infty} \frac{\pi\big(x; (1,2)\big)}{\pi(x)} = \lim_{x\to\infty} \frac{\pi\big(x; (2,1)\big)}{\pi(x)} = \lim_{x\to\infty} \frac{\pi\big(x; (2,2)\big)}{\pi(x)} = \frac{1}{4}.$$

But the numerical evidence suggests otherwise, at least when considering relatively small $x$! Among the first million primes (excluding 2), one sees the erratic distribution

$$\begin{aligned} \pi \big(10^6; (1,1)\big) &= 215873\\ \pi \big(10^6; (1,2)\big) &=283957\\ \pi \big(10^6; (2,1)\big) &= 283957\\ \pi \big(10^6; (2,2)\big) &= 216213. \end{aligned}$$

These numbers differ substantially from the expected value $250000$ for each one.

Lemke Oliver and Soundarajan have also observed that this discrepancy holds in other bases, such as base 10. They have conjectured an explanation for the biases, but the conjecture has not yet been proven.