NTIC The Prime Number Theorem

🔗

Section 21.3 The Prime Number Theorem

🔗

It turns out

$Li(x)$ is a pretty good approximation indeed.

🔗

Subsection 21.3.1 Stating the theorem

🔗

Theorem 21.3.1. Prime Number Theorem.

If $\pi(x)$ is the number of primes $p\leq x\text{,}$ then

$\begin{equation*} \lim_{x\to\infty}\frac{\pi(x)}{Li(x)}=1\text{.} \end{equation*}$

In fact, the first bound also has this property (see Exercise 21.5.6):

$\begin{equation*} \lim_{x\to\infty}\frac{\pi(x)}{x/\log(x)}=1\text{.} \end{equation*}$

🔗

This result, conjectured by Riemann, was proved about 100 years after the initial investigations of Gauss by the French and Belgian mathematicians Jacques Hadamard and Charles-Jean de la Vallée-Poussin. They made good use of the analytic methods we are slowly approaching.

🔗

Any proof is this is well beyond the bounds of this text. One of several modern versions is in the analytic number theory text [C.4.6] by Apostol; see also [C.2.9]. Additionally, as a series of exercises (!) in that book, one can also explore a proof⁴There is an interesting controversy behind this proof which is worth looking up. Selberg was an early Fields medalist, and Erdős was one of the most prolific mathematicians of all time. due to Selberg and Erdős that is “elementary”, in the sense of not using complex-valued integrals. There is a well-known exposition of a very similar proof in [C.2.2], and another in [C.4.4].

🔗

Later, we'll see that many better approximations to

$\pi(x)$ exist which come out of this sort of thinking. Notice how the approximations in the next interactive cell take the logarithmic integral and subtract various correction factors in the attempt to get closer.

xxxxxxxxxx
 
@interact
def _(n=100):
   P = plot(prime_pi,3,n, color='black',legend_label=r'$\pi(x)$')
   P += plot(Li,3,n, color='green',legend_label='$Li(x)$')
   P += plot(lambda x: Li(x) - sqrt(prime_pi(x)),3,n, color='orange', legend_label=r'$Li(x)-\sqrt{\pi(x)}$')
   P += plot(lambda x: Li(x) - .5*Li(sqrt(x)),3,n, color='red', legend_label=r'$Li(x)-\frac{1}{2}Li(\sqrt{x})$')
   P += plot(lambda x: Li(x) - sqrt(x)/log(x),3,n, color='purple', legend_label=r'$Li(x)-\sqrt{x}/\log(x)$')
   show(P, xmin=max(n-1000,0), ymin=prime_pi(max(n-1000,0)))

🔗

Subsection 21.3.2 Chebyshev's contributions

🔗

Although we cannot explore the theorem itself in depth, we can try to understand some of the intermediate steps. This is a good place to highlight the contributions of the great Russian mathematician Chebyshev (Чебышёв), who made fundamental advances in this type of number theory as well as in statistics.

🔗

He was the first person to prove a conjecture known (even today!) as Bertrand's Postulate, after the French mathematician who first proposed it.

🔗

Theorem 21.3.2. Bertrand's Postulate.

For any integer $n\geq 2\text{,}$ there is a prime between $n$ and $2n\text{.}$

🔗

Proof.

It is actually quite possible to prove this at the level we have reached, but any proof is long enough to take us a little far afield.

🔗

Try testing it yourself below!

xxxxxxxxxx
 
@interact
def _(n=25):
    pretty_print(html("$%s$ is a prime between $%s$ and $%s$"%(next_prime(n),n,2*n)))

🔗

On a related note, although this proves you can't have too long of stretches without prime numbers, you can certainly have arbitrary stretches of composite numbers. See Exercise 21.5.7 for an easy example. Paul Nahin, in [C.7.13], describes the following more clever example, a cute result of Louis A. Graham.

🔗

Fact 21.3.3.

Multiply all the primes $p$ from $2$ to $n+1$ to get $N=\prod_{2\leq p \leq n+1}p\text{.}$ Then we have $n$ consecutive composite integers from $N-(n+1)$ to $N-2\text{.}$

🔗

Proof.

We know that $N$ is a multiple of a prime factor⁵In fact, all such factors. of each number $x$ from $2$ to $n+1\text{.}$ For each such $x$ and prime factor $p_x\text{,}$ Proposition 1.2.8 guarantees that $N-x$ is also a multiple of $p_x\text{.}$

🔗

Try testing it yourself below!

xxxxxxxxxx
 
@interact
def _(n=5):
    N = prod(prime_range(n+2))
    pretty_print(html("The numbers between $%s$ and $%s$ are all composite"%(N-(n+1),N-2)))
    L = [N-(n+1)..N-2]
    print([N-(n+1)..N-2])
    pretty_print(html("have factors"))
    print([l.divisors()[1] for l in L])
    pretty_print(html("and there are $%s$ of them"%(len(L))))

🔗

More immediately germane to our task of looking at

$\pi(x)$ and its value, Chebyshev proved the first substantial result on the way to the Prime Number Theorem, validating Legendre's intuition.

🔗

Theorem 21.3.4. Big Oh of Prime Pi.

It is true both that:

$\pi(x)$ is $O\left(\frac{x}{\log(x)}\right)$ and
$\frac{x}{\log(x)}$ is $O(\pi(x))\text{.}$

🔗

Interestingly, this is not the same as the Prime Number Theorem; see Exercise 21.5.8.

🔗

What we will show here is the gist of a smaller piece of this theorem.

🔗

Proposition 21.3.5.

For big enough $x\text{,}$ $\pi(x)<2\frac{x}{\log(x)}\text{.}$

🔗

Proof.

We follow Stopple's presentation in Section 5.2 of [C.4.5] closely in sketching out most of a proof of this below; see also [C.2.11] for a very similar proof. It is a little longer than some of our other proofs. It uses some very basic combinatorial ideas and calculus facts, however, so it is a great example of several parts of mathematics coming together.

First, it's not hard to verify this for $x<1000\text{,}$ as the following figure demonstrates.

Figure 21.3.6. Plot of prime pi function versus $2x/\log(x)$

Now we'll proceed by induction, in an unusual way. We'll assume it is true for $n\text{,}$ and prove it is true for $2n\text{.}$ This needs a little massaging for odd numbers, but is a legitimate induction method.

With this in mind, we first assume that $\pi(n)<2\frac{n}{\log(n)}\text{.}$ Now what?

Below, in Lemma 21.3.7 we look at the product of all the primes (if any) between $n$ and $2n\text{,}$ which we write as

\begin{equation*} P=\prod_{n<p<2n} p\text{.} \end{equation*}

In that result some combinatorial thinking leads to the following estimate:

\begin{equation*} n^{\pi(2n)-\pi(n)}<P\leq \frac{(2n)!}{n!n!}<2^{2n} \end{equation*}

These bounds show that $P$ is between a certain power of $n$ and a certain power of $2\text{.}$

Now we will manipulate this to get the final result. Begin by taking $\log$ of both ends to get

\begin{equation*} (\pi(2n)-\pi(n))\log(n)<2n\log(2) \end{equation*}

Now divide out and isolate to get

\begin{equation*} \pi(2n)<\frac{2n\log(2)}{\log(n)}+\pi(n)<\log(2)\frac{2n}{\log(n)}+2\frac{n}{\log(n)}=(\log(2)+1)\frac{2n}{\log(n)}\text{.} \end{equation*}

In Exercise 21.5.10 you will show that, as long as $n> 1000\text{,}$ we have the inequality

\begin{equation*} \frac{\log(2)+1}{\log(n)}<\frac{2}{\log(2)+\log(n)}=\frac{2}{\log(2n)} \end{equation*}

Now we can put it all together to see that

\begin{equation*} \pi(2n)<(\log(2)+1)\frac{2n}{\log(n)}<2\frac{2n}{\log(2n)}\text{,} \end{equation*}

which is exactly what the proposition would predict.

To rescue this for $2n+1\text{,}$ we need another calculus comparison. First, from above we have

\begin{equation*} \pi(2n+1)\leq \pi(2n)+1<\frac{2n\log(2)}{\log(n)}+\pi(n)+1 \end{equation*}

\begin{equation*} <\frac{2n\log(2)}{\log(n)}+2\frac{n}{\log(n)}+1 \end{equation*}

Since $\frac{2n+1}{\log(2n+1)}>\frac{2n}{\log(2n+1)}\text{,}$ it will suffice then to show

\begin{equation*} (2+2\log(2))\frac{n}{\log(n)}+1<\frac{2n}{\log(2n+1)}\text{.} \end{equation*}

Since $n>1000\text{,}$

\begin{equation*} (2+2\log(2))\frac{n}{\log(n)}+1<3.386\frac{n}{\log(n)}+1<3.394\frac{n}{\log(n)} \end{equation*}

so it suffices to show

\begin{equation*} 3.394\frac{n}{\log(n)}<\frac{2n}{\log(2n+1)}\text{.} \end{equation*}

Showing this is Exercise 21.5.11.

🔗

Lemma 21.3.7.

Let the product of all the primes between $n$ and $2n$ be written

$\begin{equation*} P=\prod_{n<p<2n} p \end{equation*}$

Then we can bound it as

$\begin{equation*} n^{\pi(2n)-\pi(n)}<P\leq \frac{(2n)!}{n!n!}<2^{2n} \end{equation*}$

🔗

Proof.

Think of all the primes in question. On the one hand, each of these primes $p$ is greater than $n\text{,}$ and there are $\pi(2n)-\pi(n)$ of them. So

\begin{equation*} n^{\pi(2n)-\pi(n)}<P\text{.} \end{equation*}

On the other hand, each of these primes is greater than $n$ but they are all in the list of numbers from $n$ to $2n\text{,}$ so their product divides

\begin{equation*} \frac{(2n)\cdot (2n-1)\cdot (2n-2)\cdots (n+1)}{n\cdot (n-1)\cdot (n-2)\cdots 1} \end{equation*}

That is to say $P$ is a factor of a binomial coefficient

\begin{equation*} P \mid \frac{(2n)\cdot (2n-1)\cdot (2n-2)\cdots (n+1)}{n\cdot (n-1)\cdot (n-2)\cdots 1}=\frac{(2n)!}{n!n!} \end{equation*}

and in particular,

\begin{equation*} P\leq \frac{(2n)!}{n!n!} \end{equation*}

Now here is the conceptual key of the proof. We reinterpret this factorial fraction as the number of ways to choose $n$ things from a collection of $2n$ things! And the number of ways to choose $n$ things is certainly less than the number of ways to pick any old collection out of $2n$ things, which is $2^{2n}$ (because you either pick it or you don't).

Since we showed both bounds, this concludes the proof.