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^{ 13 }

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 [E.2.2], and another in [E.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.

Subsection21.3.2Chebyshev’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.

(Чебышёв) 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.

Theorem21.3.4.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^{ 15 }

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.

Fact21.3.5.

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^{ 16 }

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!

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.

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

Proposition21.3.7.

For all positive \(x\text{,}\)\(\pi(x)<2\frac{x}{\log(x)}\text{.}\)

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.

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

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

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

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.