MAT 338 Day 37

First, X enlightens us on the Prime Number Theorem!

As X has pointed out, the Holy Grail of 19th century number theory was conjectured by Gauss and Legendre just before 1800. Let \log(n) be the natural logarithm function.  Then we have:

Prime Number Theorem: If \pi(x) is the number of primes p\leq x, then

As you might recall from last time and X's talk, this is equivalent to saying that

as well.  Here is a similar graph to the one from last time, along with another one showing the relative differences - both out to x=1000.

Remember that this was proved about 100 years later by Hadamard and de la Vallee-Poussin. What methods might one use to prove such a bizarre statement?  The rest of today we will try to get a sense of this - the beginnings of true analytic number theory.

First off, if X didn't mention it, first look back in your handout, the bottom of page 6 to the middle of page 7.  This gives us a good sense of just how crazy such questions are to pretend we have the capacity to answer them.

Next, let's look at a couple of contributions of the great Russian mathematician Chebyshev (Чебышёв), who made fundamental contributions to this type of number theory as well as to statistics!  

The above cell "verifies" Bertrand's Postulate/Chebyshev's Theorem, which Y mentioned in her talk on Erdos, than between n and 2n there is always a prime. Another great theorem of his is the following, which is somewhat weaker than the PNT but more accessible:

Theorem: It is true both that \pi(x) is O(\frac{x}{\ln(x)}) and that \frac{x}{\ln(x)} is O(\pi(x)).

It would take far too long to verify this properly, but we can at least show the gist of a small piece of this:

Proposition: The prime counting function \pi(x)<2\frac{x}{\ln(x)}.

Proof Sketch:

(We'll skip this if it's looking like time is running low for today, and do it next time instead.)

It's not hard to verify this for x<100:

Okay, what next?  The idea is to proceed by induction, in an unusual way - namely, 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 we assume that \pi(n)<2\frac{n}{\ln(n)}.  Now what?  

Our next step is very interesting.  We want to look at the product of all the primes between n and 2n, which we can write as

 One the one hand, since each of these primes p is greater than n (p>n), and there are \pi(2n)-\pi(n) of them (think about this!), we can say  On the other hand, since each of these primes is greater than n but they are all in the list of numbers from n to 2n, we can legitimately say that each of them (and 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 which means that in particular  But this last 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 take \ln of both ends to get and then divide out and isolate to get  Now we just need some little trick based on n>100 (since we already verified for lower n) and a little calculus to get that \frac{\ln(2)+1}{\ln(n)}<\frac{2}{\ln(2)+\ln(n)}=\frac{2}{\ln(2n)}, which yields that which is exactly what the proposition would predict.

It turns out that more advanced statements are not so easy to prove without a lot of work - and our main goal is to get back to general functions stuff the last two weeks of the course.  Still, I want to end today with a substantial piece of a real proof in this direction; it is dense, but just like the last few proofs, requires nothing beyond calculus and a willingness to allow a lot of algebraic and integral manipulation for the purposes of estimation.

Functions: First, we'll review the main function. Think of the prime counting function \pi as a so-called `step' function, where every time you hit a new prime you add 1.

Instead of adding 1 each time, let's add \log(p) each time we hit a prime p. Of course, this will get bigger as p gets bigger.

We call this Chebyshev's theta function, and we write

It turns out the PNT implies the following limit (in fact, they're equivalent): Here is a plot of both limits, along with the constant function 1.

An Integral Formula: In order to prove this, we will first need a formula telling us about \Theta(x). It turns out that integrals will help! Let m=[x], the greatest integer less than x. Let a(n) be the function such that a(p)=1 if p is prime and a(n)=0 otherwise; another way to say this is a(n)=\pi(n)-\pi(n-1). Then it should be clear that

By rearranging the sum in different ways (and using \log(1)=0), we see that

which can be combined with just two left over terms, the second of which is 0: Now, \log(n+1)-\log(n)=\int_{n}^{n+1}\frac{dt}{t}; using this and a few other sleights of hand of integrals, rearrangement, and that \pi(x)=\pi(m) is constant on [m,x], we get

The Final Step: Now we have a formula for \Theta which will allow us to prove something. To recap, we have:

so, given that the Prime Number Theorem says that \lim_{x\to\infty} of the fraction with \pi(x) in it is 1, proving that \lim_{x\to\infty} of \frac{\Theta(x)}{x} is also 1 is equivalent to proving But since the PNT essentially says that in the limit \frac{\pi(t)}{t}\sim \frac{1}{\log(t)}, we can write that Now look at the following graph. An upper sum for the integral of 1/\log(t) between 2 and 9 is the area of the two rectangles shown, one with area \frac{1}{\log(2)}(\sqrt{9}-2) and the other with area \frac{1}{\log(\sqrt{9})}(9-\sqrt{9}), where of course \sqrt{9}=3.

Then in general replace 9 with x (one can do that by redoing the above graph with x=16 or x=25 or whatever); we use logarithmic identities to see that

which clearly goes to zero as x\to\infty. But that means that

This is naturally a tour de force, and only a small part of what one can do with all this.