Section21.3The Prime Number Theorem
It turns out \(Li(x)\) is a pretty good approximation indeed.
Theorem21.3.1Prime Number Theorem
If \(\pi(x)\) is the number of primes \(p\leq x\), then \[\lim_{x\to\infty}\frac{\pi(x)}{Li(x)}=1\; .\] In fact, the first bound also has this property: \[\lim_{x\to\infty}\frac{\pi(x)}{x/\log(x)}=1\, .\]This was proved about 100 years after the initial investigations of Gauss by the French and Belgian mathematicians Jacques Hadamard and Charles-Jean de la Vallee-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, though more are including one now; one of several modern versions is in the analytic number theory text by Apostol. As a series of exercises (!) in that book, one can explore a proof due to Selberg and Erdos that is “elementary” in the sense of not using complex integrals; there is a well-known exposition of a very similar proof in Hardy and Wright.
Here are some of the many possible better approximations to \(\pi(x)\) that come out of this sort of thinking. Later, we'll see more of this. Notice how these approximations take the them of the logarithmic integral and subtract various correction factors in the attempt to get closer.
Subsection21.3.1Chebyshev's contributions
Although we cannot explore the theorem itself in depth, we can understand some of the steps one must take on the way there. It is a good place to highlight the number-theoretic 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 to prove a conjecture known (even today!) as Bertrand's Postulate.
Theorem21.3.2Bertrand's Postulate
For any integer \(n\geq 2\), there is a prime between \(n\) and \(2n\).Proof
It is actually quite possible to prove this at the level we have reached, but the proof is long enough to take us a little far afield.
Try it for 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.3Big Oh of Prime Pi
It is true both that:
- \(\pi(x)\) is \(O\left(\frac{x}{\ln(x)}\right)\) and
- \(\frac{x}{\ln(x)}\) is \(O(\pi(x))\).
Interestingly, this is not the same as the Prime Number Theorem; see the exercises.
What we can show here is the gist of a smaller piece of this theorem.
Proposition21.3.4
For big enough \(x\), \(\pi(x)<2\frac{x}{\ln(x)}\; .\)Proof
We can actually sketch out most of the proof of this fact, and do so below. 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\).
Now we'll proceed by induction, in an unusual way. We'll assume it is true for \(n\), and prove it is true for \(2n\)! This needs a little massaging for odd numbers, but is a legitimate induction method.
- So first assume that \(\pi(n)<2\frac{n}{\ln(n)}\). Now what?
- We now look at the product of all the primes between \(n\) and \(2n\), which we write as \[P=\prod_{n<p<2n} p\, .\] Our immediate goal is to get a bound on this number.
- On the one hand, each of these primes \(p\) is greater than \(n\), and there are \(\pi(2n)-\pi(n)\) of them.
- So \[n^{\pi(2n)-\pi(n)}<P\, .\]
- 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\), so...
- Their product divides \[\frac{(2n)\cdot (2n-1)\cdot (2n-2)\cdots (n+1)}{n\cdot (n-1)\cdot (n-2)\cdots 1}\]
- That is to say \[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!}\, .\]
- In particular, \[P\leq \frac{(2n)!}{n!n!}\, .\]
- But this is the number of ways to choose \(n\) things from a collection of \(2n\) things...
- Which 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).
- That leads to the estimate \[n^{\pi(2n)-\pi(n)}<P\leq \frac{(2n)!}{n!n!}<2^{2n}\, ;\]
- Take \(\ln\) of both ends to get \[(\pi(2n)-\pi(n))\ln(n)<2n\ln(2)\]
- Now divide out and isolate to get \[\pi(2n)<\frac{2n\ln(2)}{\ln(n)}+\pi(n)<\frac{2n\ln(2)}{\ln(n)}+2\frac{n}{\ln(n)}=(\ln(2)+1)\frac{2n}{\ln(n)}\, .\]
- Then recall that \(n>1000\) (since we already verified for lower \(n\)):
- Compare \(2\ln(n)\) and \(\ln(2)(\ln(2)+\ln(n))\) for \(n=1000\) - the first one is bigger.
- Further, the derivatives are \(2/n\) and \(\ln(2)/n\), so the derivative of the first one is bigger too.
- So we divide through a bit and get \(\frac{\ln(2)+1}{\ln(n)}<\frac{2}{\ln(2)+\ln(n)}=\frac{2}{\ln(2n)}\).
- Now we can put it all together to see that \[\pi(2n)<(\ln(2)+1)\frac{2n}{\ln(n)}<2\frac{2n}{\ln(2n)}\, ,\] which is exactly what the proposition would predict.
- To rescue this for \(2n+1\), we need another calculus comparison.
- First, from above we have \[\pi(2n+1)\leq \pi(2n)+1<\frac{2n\ln(2)}{\ln(n)}+\pi(n)+1<\frac{2n\ln(2)}{\ln(n)}+2\frac{n}{\ln(n)}+1\; .\]
- Since \(\frac{2n+1}{\ln(2n+1)}>\frac{2n}{\ln(2n+1)}\), it will suffice then to show \[(2+2\ln(2))\frac{n}{\ln(n)}+1<\frac{2n}{\ln(2n+1)}\; .\]
- Since \(n>1000\), \[(2+2\ln(2))\frac{n}{\ln(n)}+1<3.386\frac{n}{\ln(n)}+1<3.394\frac{n}{\ln(n)}\] so it suffices to show \[3.394\frac{n}{\ln(n)}<\frac{2n}{\ln(2n+1)}\; .\]
- This is the same as \[\frac{3.394}{4}<\frac{\ln(n)}{\ln(2n+1)}\]
- The right hand side is bigger than the left hand side at \(n=1000\).
- The derivative of the right is positive.
- So we have the required result that \[\pi(2n+1)<2\frac{2n+1}{\ln(2n+1)}\]
