NTIC The Prime Number Theorem

Section 21.3 The Prime Number Theorem

It turns out

L i (x)

is a pretty good approximation indeed.

🔗

Subsection 21.3.1 Stating the theorem

🔗

Theorem 21.3.1. Prime Number Theorem.

If $π (x)$ is the number of primes $p \leq x,$ then

lim_{x \to \infty} \frac{π (x)}{L i (x)} = 1 .

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

lim_{x \to \infty} \frac{π (x)}{x / \log (x)} = 1 .

🔗

Historical remark 21.3.2. The Prime Number Theorem.

The Prime Number Theorem was conjectured by Bernhard Riemann in his only paper on number theory. It 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 [E.4.6] by Apostol; see also [E.2.9]. Additionally, as a series of exercises (!) in that book, one can also explore a proof⁶ 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 [E.2.2], and another in [E.4.4].

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.

🔗

Later, we'll see that many better approximations to

π (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.

🔗

Historical remark 21.3.3. Pafnuty Chebyshev.

Chebyshev (Чебышёв) was a prominent Russian mathematician of the mid-19th century, but his most important legacy may be bringing the native Russian tradition into international prominence. (Recall that Euler worked in Russia for much of his life, but alongside other Swiss scientists.) In addition to fundamental advances in this type of number theory, he worked on the theory of orthogonal polynomials which is used so much today in applications, and probability theory underlying modern 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.4. Bertrand's Postulate.

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

🔗

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 [E.7.13], describes the following more clever example, a cute result of Louis A. Graham.

🔗

Fact 21.3.5.

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

🔗

Proof.

We know that $N$ is a multiple of a prime factor⁷ 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{.}$

In fact, all such factors.

🔗

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

π (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.6. Big Oh of Prime Pi.

It is true both that:

$π (x)$ is $O (\frac{x}{\log (x)})$ and
$\frac{x}{\log (x)}$ is $O (π (x)) .$

🔗

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

For all positive $x,$ $π (x) < 2 \frac{x}{\log (x)} .$

🔗

Proof.

We follow Stopple's presentation in Section 5.2 of [E.4.5] closely in sketching out most of a proof of this below; see also [E.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.8. 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.9 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)}=\frac{\log(2)+1}{\log(n)}2n\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)< \frac{\log(2)+1}{\log(n)}2n <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{\log(2)+1}{\log(n)}2n +1\text{.} \end{equation*}

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

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

Since $n>1000$ and $\frac{n}{\log(n)}$ is increasing, $\frac{1}{n/\log(n)}\lt 0.007\text{,}$ so

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

To finish it suffices to show that in this range

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

Showing the last (purely calculus) steps is Exercise 21.5.11.

🔗

Lemma 21.3.9.

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

P = \prod_{n < p < 2 n} p

Then we can bound it as

n^{π (2 n) - π (n)} < P \leq \frac{(2 n)!}{n! n!} < 2^{2 n}

🔗

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*}

We are now ready for the conceptual key of the proof, which uses the combinatorial leitmotif of counting things in two different way. Namely, 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.