NTIC A Slice of the Prime Number Theorem

Section 21.4 A 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 also first introduced by Chebyshev. The argument is dense, but requires nothing beyond calculus and a willingness to allow a lot of algebraic and integral manipulation for the purposes of estimation. (See a good calculus text to review integral concepts.)

🔗

Subsection 21.4.1 Functions to know

🔗

First, we'll review the main function. Think of the prime counting function

π

as a so-called step function, where every time you hit a new prime you add 1. The picture reminds you of this attribute.

🔗
Figure 21.4.1. Plot of prime pi function

🔗

Let's define a new function in that spirit. Instead of adding 1 each time

x

hits a prime, we will add

\log (p)

(recall that this is the natural logarithm) each time we hit a prime

p .

Of course, this value we add will get bigger as

p

gets bigger.

🔗
Figure 21.4.2. Plot of Chebyshev theta function

🔗

Definition 21.4.3.

We call the function given by this formula Chebyshev's theta function:

Θ (x) = \sum_{p \leq x} \log (p) .

🔗

Sage note 21.4.4. Python can do math too.

We include an interactive version so you can see the code.

xxxxxxxxxx
 
def theta(x): return sum(math.log(p) for p in prime_range(1,floor(x)+1))
@interact
def _(n=100):
    show(plot(theta,1,n))

The syntax math.log is referring to Python's builtin calculation of the natural logarithm, accessible in the math module. This is sometimes faster and easier to use than Sage's more powerful capabilities, because if you put an integer in Sage's logarithm, it will normally not approximate it. All we want here is an easy approximation, so this should be faster.

🔗

Earlier in this chapter we noted that the Prime Number Theorem is logically equivalent to the limit

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

There are actually many such logical equivalences. One of them involves

Θ :

lim_{x \to \infty} \frac{Θ (x)}{x} = 1

🔗

This is certainly numerically plausible. Here is a plot of both limits, along with the constant function

1 .

🔗
Figure 21.4.5. Plot of Chebyshev theta function limits

🔗

In the interact below, there is an option for an

L i

versus

x / l o g (x)

version of the theorem. Note how much better the prime number theorem limit looks with the

L i

version.

xxxxxxxxxx
 
def theta(x): return sum(math.log(p) for p in prime_range(1,floor(x)+1))
def pnt(n): return prime_pi(n)*log(n)/n
def pntli(n): return prime_pi(n)/Li(n)
def thox(n): return theta(n)/n
@interact
def _(end=100000,PNT=['log','Li']):
    P = plot(1,(1,end),color='black')
    P += plot(thox,(1,end),legend_label='Chebyshev Theta')
    if PNT == "log":
        P += plot(pnt,(1,end),color='red',legend_label='Prime Number Theorem')
    if PNT == "Li":
        P += plot(pntli,(1,end),color='red',legend_label='Prime Number Theorem')
    show(P)

🔗

As usual, proving such things completely is beyond the level of this course, but we can prove the following partial implication.

🔗

Proposition 21.4.6.

If the Prime Number Theorem is true, then it is also true that $Θ (x) / x$ approaches $1 .$

🔗

Proof.

The rest of this section is the proof.

🔗

Subsection 21.4.2 Getting a formula with sleights of hand

🔗

In order to prove this implication, we will first need a formula telling us more about

Θ (x) .

Our strategy⁸ will be to first turn

Θ (x)

into an even more hopelessly complicated sum, but then use calculus trickily to get something usable by summing up integrals.

This is an expansion of the terse approach taken in [E.4.6, Theorems 4.3 and 4.4].

🔗

In order to do this, we need two subsidiary functions. First, recall the notation

⌊ x ⌋

for the greatest integer less than

x .

Secondly:

🔗

Definition 21.4.7.

We let $a (n)$ be the prime number indicator function defined by

a (n) = {\begin{cases} 1 & if n is prime \\ 0 & otherwise \end{cases} .

Another way to say this is

a (n) = π (n) - π (n - 1) .

Prime pi versus indicator function — 🔗
Figure 21.4.8. Prime $π$ versus $a$ indicator function

🔗

One can get the indicator function just by writing prime_pi(x)-prime_pi(x-1).

🔗

For convenience we write

m = ⌊ x ⌋ .

Then we can rewrite these step functions as weighted sums of

a (n) :

π (x) = \sum_{n = 1}^{m} a (n) and Θ (x) = \sum_{n = 1}^{m} a (n) \log (n) .

🔗

Our goal is to rearrange

Θ

to be a sum of terms involving

π .

First we turn

Θ

into a difference of sums by rearranging (and using

\log (1) = 0

Θ (x) = \sum_{1 \leq n \leq x} a (n) \log (n) = \sum_{n = 1}^{m} a (n) \log (n) =

\sum_{n = 2}^{m} [π (n) - π (n - 1)] \log (n) = \sum_{n = 2}^{m} π (n) \log (n) - \sum_{n = 1}^{m - 1} π (n) \log (n + 1)

🔗

This difference of sums can be combined into a single sum, with just two left over terms⁹.

Θ (x) = \sum_{n = 2}^{m - 1} π (n) [\log (n) - \log (n + 1)] + π (m) \log (m) - π (1) \log (2) .

Students a little more familiar with calculus may want to compare this process to integration by parts, but in a discrete context, sometimes called Abel summation.

🔗

To continue, we will rewrite almost all of this as single integral. We use a few key facts:

The difference which appears in the the sum in the immediately preceding $Θ$ formula can be considered as an integral, $- (\log (n + 1) - \log (n)) = - \int_{n}^{n + 1} \frac{d t}{t} .$
We have that $π (x)$ is constant on the interval $[⌊ x ⌋, x],$ and in particular on any given interval $[n, n + 1),$ so it may be factored out of any integral from $n$ to $n + 1 .$
We can rearrange and add sums and integrals as usual.
Note that $π (1) = 0,$ so the second extra term is zero.

🔗

This yields the following rewrite.

Θ (x) = - \sum_{n = 2}^{m - 1} [π (n) \int_{n}^{n + 1} \frac{d t}{t}] + π (m) \log (m)

= - \sum_{n = 2}^{m - 1} [π (n) \int_{n}^{n + 1} \frac{d t}{t}] + π (m) \log (m) - π (x) \log (x) + π (x) \log (x)

= - \int_{2}^{m} \frac{π (t) d t}{t} + π (x) \log (x) - \int_{m}^{x} \frac{π (t) d t}{t} = π (x) \log (x) - \int_{2}^{x} \frac{π (t) d t}{t} .

🔗

Now we have a formula for

Θ

which will allow us to prove something.

🔗

Subsection 21.4.3 Finish the proof

🔗

We can divide the formula

Θ (x) = π (x) \log (x) - \int_{2}^{x} \frac{π (t) d t}{t}

x :

\frac{Θ (x)}{x} = \frac{π (x) \log (x)}{x} - \frac{\int_{2}^{x} \frac{π (t)}{t} d t}{x} .

🔗

Given that the Prime Number Theorem says that

lim_{x \to \infty}

of the fraction with

π (x)

in it is 1, proving that

lim_{x \to \infty} \frac{Θ (x)}{x}

is also 1 is equivalent to proving

lim_{x \to \infty} \frac{1}{x} \int_{2}^{x} \frac{π (t)}{t} d t = 0 .

🔗

Now, the Prime Number Theorem also implies that

\frac{π (t)}{t}

and

\frac{1}{\log (t)}

are asymptotic (recall Definition 21.2.1), so that their averaging integrals

\frac{1}{x} \int_{2}^{x} \frac{π (t)}{t} d t and \frac{1}{x} \int_{2}^{x} \frac{d t}{\log (t)}

🔗

clearly are also asymptotic.

🔗

This reduces our proof to showing that the average value of

1 / \log (t)

tends to zero. Since integrals have a graphical interpretation, we now use the following graph of the integral limit to finish the proof!

🔗

Consider that one possible upper sum for the integral of

1 / \log (t)

between 2 and 9 is the area of the two rectangles shown below, one with area

\frac{1}{\log (2)} (\sqrt{9} - 2)

and the other with area

\frac{1}{\log (\sqrt{9})} (9 - \sqrt{9}) .

(Of course

\sqrt{9} = 3

but this form is more useful here.)

🔗
Figure 21.4.9. Estimating integrals for proof

🔗

In general, the same argument should hold, so a possible overestimate of

\int_{2}^{x} d t / \log (t)

\frac{1}{\log (2)} (\sqrt{x} - 2) + \frac{1}{\log (\sqrt{x})} (x - \sqrt{x})

🔗

and we want the limit as

x \to \infty

\frac{1}{x}

times that quantity.

🔗

Now is the time to recklessly use logarithmic identities:

\frac{1}{x} (\frac{1}{\log (2)} (\sqrt{x} - 2) + \frac{1}{\log (\sqrt{x})} (x - \sqrt{x}))

= \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 last expression has positive powers of

x

and their logs in the denominators, so it pretty clearly goes to zero as

x \to \infty .

🔗

If the algebra doesn't convince you, perhaps an interactive graph will. Below, black is the overestimate to the integral and red is

1 / x

times the integral.

xxxxxxxxxx
 
@interact
def _(top=(16,[n^2 for n in [2..10]])):
    f(x)=1/log(x)
    P=plot(f,1,top+1)
    P += line([(2,0),(2,f(2)),(math.sqrt(top),f(2)), (math.sqrt(top),0)], rgbcolor='black')
    P += line([(math.sqrt(top),f(math.sqrt(top))), (top,f(math.sqrt(top))),(top,0)], rgbcolor='black')
    P += line([(2,0),(2,f(2)),(2+(math.sqrt(top)-2)/top,f(2)), (2+(math.sqrt(top)-2)/top,0)], rgbcolor='red')
    P += line([(math.sqrt(top),f(math.sqrt(top))), (math.sqrt(top)+(top-math.sqrt(top))/top, f(math.sqrt(top))), (math.sqrt(top) + (top-math.sqrt(top))/top,0)], rgbcolor='red')
    P.show(ymax=2)

🔗

The picture confirms our analytic proof that the limit of

\frac{θ (x)}{x}

is the same as that of

\frac{π (x)}{x / \log (x)},

which is what we desired!