Section21.4A slice of the Prime Number Theorem

We end this chapter with a substantial piece of a real proof in the direction of the Prime Number Theorem, courtesy of a function first introduced by Chebyshev. It is dense, but requires nothing beyond calculus and a willingness to allow a lot of algebraic and integral manipulation for the purposes of estimation.

Subsection21.4.1Functions to know

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.

Now, instead of adding 1 each time, let's add \(\log(p)\) (that is, the natural logarithm, notation we'll use for the rest of this section) 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 \[\Theta(x)=\sum_{p\leq x}\log(p)\, .\]

It turns out the Prime Number Theorem implies the following limit: \[\lim_{x\to\infty}\frac{\Theta(x)}{x}=1\, .\] In fact, this limit is logically equivalent to the PNT.

Here is a plot of both limits, along with the constant function 1.

So we will prove this implication - that if the Prime Number Theorem is true, it is also true that \(\Theta(x)/x\) approaches \(1\).

Subsection21.4.2Getting a Formula

In order to prove this, we will first need a formula telling us about \(\Theta(x)\). So we will first turn \(\Theta(x)\) into a hopelessly complicated sum, then use calculus to trickily get something usable.

  • Let \(m=\lfloor x\rfloor\), 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 \[\pi(x)=\sum_{n=1}^{m}a(n)\text{ and }\Theta(x)=\sum_{n=1}^{m}a(n)\log(n)\, .\]
  • By rearranging the sum in different ways (and using \(\log(1)=0\)), we see that \[\Theta(x)=\sum_{1\leq n\leq x}a(n)\log(n)=\sum_{n=1}^{m}a(n)\log(n)=\] \[\sum_{n=2}^{m}[\pi(n)-\pi(n-1)]\log(n)=\sum_{n=2}^{m}\pi(n)\log(n)-\sum_{n=1}^{m-1}\pi(n)\log(n+1)\]
  • This difference of sums can be combined into a single sum, with just two left over terms, the second of which is 0. \[\Theta(x)=\sum_{n=2}^{m-1}\pi(n)[\log(n)-\log(n+1)]+\pi(m)\log(m)-\pi(1)\log(1)\, .\]

Subsection21.4.3More reduction and sleights of hand

Now, \(\log(n+1)-\log(n)=\int_{n}^{n+1}\frac{dt}{t}\). We use this and a few other sleights of hand of integrals, rearrangement, and that \(\pi(x)=\pi(m)\) is constant on \([m,x]\) in the following rethinking of the above sum. \[-\sum_{n=2}^{m-1}\Big[\pi(n)\int_{n}^{n+1}\frac{dt}{t}\Big]+\pi(m)\log(m)\] \[=-\sum_{n=2}^{m-1}\Big[\pi(n)\int_{n}^{n+1}\frac{dt}{t}\Big]+\pi(m)\log(m)-\pi(x)\log(x)+\pi(x)\log(x)\] \[=-\int_{2}^{m}\frac{\pi(t)dt}{t}+\pi(x)\log(x)-\int_{m}^{x}\frac{\pi(t)dt}{t} =\pi(x)\log(x)-\int_{2}^{x}\frac{\pi(t)dt}{t}\, .\]

Now we have a formula for \(\Theta\) which will allow us to prove something.

  • Dividing the previous formula by \(x\), we get: \[\frac{\Theta(x)}{x}=\frac{\pi(x)\log(x)}{x}-\frac{\int_{2}^{x}\frac{\pi(t)}{t}dt}{x}\, ,\]
  • 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 \[\lim_{x\to\infty}\frac{1}{x}\int_{2}^{x}\frac{\pi(t)}{t}dt=0\, .\]
  • Now, the PNT essentially says that in the limit \(\frac{\pi(t)}{t}\sim \frac{1}{\log(t)}\), we can write that \[\frac{1}{x}\int_{2}^{x}\frac{\pi(t)}{t}dt\sim \frac{1}{x}\int_{2}^{x}\frac{dt}{\log(t)}\, .\] So we have reduced our proof to showing that the average value of \(1/log(t)\) tends to zero.

Subsection21.4.4Finish the proof

We now use the following graph of the integral limit to finish the proof.

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

So in general, the overestimate of \(\int_2^x dt/\ln(t)\) will be \[\frac{1}{\log(2)}(\sqrt{x}-2)+\frac{1}{\log(\sqrt{x})}(x-\sqrt{x})\] and we want the limit as \(x\to\infty\) of \(\frac{1}{x}\) times that quantity.

This limit can be simplified a lot with logarithmic identities: \[\frac{1}{x}\left(\frac{1}{\log(2)}(\sqrt{x}-2)+\frac{1}{\log(\sqrt{x})}(x-\sqrt{x})\right)=\frac{1}{\log(2)x^{1/2}}-\frac{2}{x\log(2)}+\frac{1}{\log(\sqrt{x})}-\frac{1}{\log(\sqrt{x})x^{1/2}}\] \[=\frac{1}{\log(2)x^{1/2}}-\frac{2}{x\log(2)}+\frac{2}{\log(x)}-\frac{2}{\log(x)x^{1/2}}\] This pretty clearly goes to zero as \(x\to \infty\).

We can look at the following graphic as well. Black is the overestimate to the integral, red is \(1/x\) times the integral.

The picture confirms our analytic proof that the limit of \(\frac{\theta(x)}{x}\) is the same as that of \(\frac{\pi(x)}{x/\ln(x)}\), which is what we desired!