The Prime Number Theorem

We’ve just seen experimental evidence that $n/\ln(n)$ approximates $\pi(n)$ fairly well. Although the error itself grows as $n \rightarrow \infty$, the proportional error gets ever smaller.

Let’s write that out.

$$ \lim_{n \rightarrow \infty} \frac{\pi(n) - n/\ln(n)}{\pi(n)} = 0 $$

Rearranging this gives us the following.

$$ \lim_{n \rightarrow \infty} \frac{\pi(n)}{n/\ln(n)} = 1 $$

This says the ratio of $\pi(n)$ and the approximation $n/ ln(n)$ tends to 1 as $n \rightarrow \infty$. And this is precisely what the prime number theorem says.

$$ \pi(n) \sim n/ \ln(n) $$

The symbol $\sim$ says that both sides are asymptotically equivalent. For example, $f(n) \sim g(n)$ means $f(n)/g(n) = 1$ as $n \rightarrow \infty$.

Video: [youtube]

Slides: [pdf]

Asymptotic Equivalence

Some examples of asymptotic equivalence will help clarify its meaning.

If $f(x)=x^2 + x$ and $g(x)=x^2$, then $f \sim g$. Both $f$ and $g$ have the same dominant term $x^2$.

$$ \lim_{x\rightarrow\infty} \frac{x^2+x}{x^2} = \lim_{x\rightarrow\infty}1+\frac{1}{x}=1 $$

Swapping $f$ and $g$ doesn't break asymptotic equivalence, $g \sim f$.

$$ \lim_{x\rightarrow\infty} \frac{x^2}{x^2+x}=\lim_{x\rightarrow\infty}\frac{1}{1+\frac{1}{x}}=1 $$

However, if $f(x)=x^{3}$ and $g(x)=x^{2}$, then $f$ and $g$ are not asymptotically equivalent because the ratio $f/g$ tends to $x$, not 1. 

If we know that $f \sim g$ and $g \sim h$, then we can also say $f \sim h$. This property, called transitivity, is familiar from normal equality.

What About li(n)?

Gauss' second approximation $\text{li}(n)$ appeared to be a better approximation for $\pi(n)$. You'll find the prime number theorem is sometimes expressed using the logarithmic integral.

$$ \pi(n) \sim \text{li}(n) $$

Surely the prime number theorem must be about one of the approximations, not both? The only solution is for both approximations to be asymptotically equivalent. Let's see that this is indeed the case.

Let's set $f(n)=\frac{{n}}{\ln(n)}$ and $g(n)=\int_{0}^{n}\frac{1}{\ln(x)}dx$. 

To show $f \sim g$ we need to find the limit of $f(n)/g(n)$ as $n\rightarrow\infty$ and confirm it is 1. Sadly, both $f(n)$ and $g(n)$ become infinitely large as $n\rightarrow\infty$, so the ratio is undefined. 

When this happens, we usually try l'Hopital's rule as an alternative way to find the limit.

$$ \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=\lim_{n\rightarrow\infty}\frac{f'(n)}{g'(n)} $$

It's fairly easy to work out $f'(n)=\frac{\ln(n)-1}{\ln^{2}(n)}$, and $g'(n)=\frac{1}{\ln(n)}$ pops out of the definition of $\text{li}(n)$. 

$$ \begin{align} \lim_{n\rightarrow\infty}\frac{f'(n)}{g'(n)} &= \lim_{n\rightarrow\infty}\frac{(\ln(n)-1)\ln(n)}{\ln^{2}(n)} \\ &= \lim_{n\rightarrow\infty}1-\frac{1}{\ln(n)} \\ &= 1 \end{align} $$

So the prime number theorem can refer to either of the two approximations, $n/ln(n)$ and $\text{li}(n)$, because they are asymptotically equivalent.

What Does The Prime Number Theorem Really Say?

The prime number theorem says that $\pi(n)$ grows in a way that is asymptotically equivalent to functions like $n/\ln(n)$ and $\text{li}(n)$. 

It doesn't say that these are the only or best functions for approximating $\pi(n)$, which leaves open the intriguing possibility of other functions that are even better than $\text{li}(n)$.

Bertrand's Postulate

The prime number theorem, even if it looks imprecise, is rather useful. Let's look at a particularly simple example.

In 1845 Bertrand proposed that there is at least one prime between a counting number and its double, $n<p<2n$.

Let's compare the number of primes up to $2x$, with the number of primes up to $x$.

$$ \frac{\pi(2x)}{\pi(x)} \sim \frac{2x}{\ln(2x)} \cdot \frac{\ln(x)}{x} \sim 2 $$

This shows that for sufficiently large $x$, between $x$ and $2x$, there are $x/\ln(x)$ primes. This is a stronger statement than Bertrand's postulate which merely suggests there is at least one prime.

There are proofs that don't require $x$ to be sufficiently large, but they're nowhere near as simple as this deduction from the prime number theorem.