## The Riemann hypothesis: Counting prime numbers in an interval

Given what he had proven (or thought he had proven) about ζ(s), Riemann went on to give an “explicit” formula for π(x), the number of primes not greater than x. That is, not merely an asymptotic formula, but an exact formula. Before we consider that, let’s review what we’ve already said about π(x).

That is, based on probabalistic ideas as well as extensive calculations, Gauss conjectured that

π(x) ~ x/log(x)

There’s a similar function which gives a slightly better result, both theoretically and computationally. It is the “logarithmic integral”:

Li(x) = ∫2≤t≤x log(t)-1 dt

This was actually a pretty good estimate. When x = 107, the estimate is off by only 339.

One of Gauss’ near contemporaries, A. M. Legendre (1752-1833) reached similar conclusions. His book Theorie des nombres in about 1800 suggested that

π(x) ~ x/(A log(x) + B)

for constants A and B. Somewhat later, P. L. Chebyshev actually proved, around 1850 (about 10 years before Riemann’s paper), that if the limit implied by Legendre’s asymptotic equivalence actually existed, A had to be 1.

Riemann’s 1859 paper gave an “explicit” formula for π(x) that shows

π(x) = Li(x) + other stuff

Riemann’s formula gave the “other stuff” explicitly. Unfortunately he could not estimate it well enough to yield, immediately, the prime number theorem. But let’s take a closer look at it anyhow.

Starting with the Euler product for ζ(s), we’ve already found, for Re(s) > 1,

log ζ(s) = ∑pn (1/n)p-ns

Riemann defined a function F(x), for real x ≥ 0, that is constant except for jumps at integers which are powers of primes. F(0) = 0. At integers which are primes, it jumps by 1. At the squares of primes, it jumps by 1/2. At prime cubes it jumps by 1/3. And so on. That sounds like a rather peculiar function, but it turns out there is a simple formula for it. Riemann realized that

F(x) = ∑1≤n<∞ π(x1/n)/n

Here’s how to see that. First note that for any x ≥ 0 the sum has only a finite number of terms, because π(x) = 0 for 0 ≤ x < 2. Hence π(x1/n) = 0 for x1/n < 2, or equivalently, for log2(x) < n. If p is any prime, then log2(x) = (ln(p)/ln(2))logp(x) = N(x,p). So the sum is actually, for any prime p,

F(x) = ∑1≤n≤N(x,p) π(x1/n)/n

Now, π(x) is a monotonically increasing step function, with steps only for x a prime integer. Hence F(x) is also a monotonically increasing step function, with steps where x is a positive integer power of a prime. If x = pk, then k = logp(x) ≤ N(x,p), and the step, which occurs for n = k, is 1/k.

Riemann then showed that for this peculiar function, the preceding formula is an integral:

log ζ(s) = s ∫0≤x≤∞ F(x)x-s-1 dx

By a procedure known as “Fourier inversion” this can be used to express F(x) in terms of log ζ(s):

F(x) = (2πi)-1 ∫ log ζ(s) (x-s/s) ds

At this point, the other product formula for ζ(s) can be used to give a formula for log ζ(s) which can be substituted into the integral. As we’ve seen, this other formula explicitly involves the zeros of ζ(s). This is the precise point at which the distribution of those zeros becomes important. There is a great deal of hairy calculus involved in working everything out. But the final result is a formula for F(X), which is:

F(x) = Li(x) – ∑ρ Li(xρ) – log 2 + ∫x≤t≤∞ (t(t2 – 1)log t)-1 dt

There were substantial holes in Riemann’s “proof” of this formula. It was rigorously established by H. von Mangoldt only in 1895.

To finish the derivation of a formula for π(x) there is one more “trick”, which involves the number-theoretic function μ(n) defined for integers by μ(n) = 0 if n is divisible by the square of a prime, μ(n) = 1 if n is a product of an even number of distinct primes, and μ(n) = -1 if n is a product of an odd number of distinct primes. μ(n) is called the Möbius function. (The same Möbius who was responsible for the Möbius strip.) Using that, we can “invert” the expression for F(x) in terms of π(x) to obtain

π(x) = ∑1≤n<∞ μ(n)F(x1/n)/n

This is also a finite sum, since for any x and sufficiently large n, F(x1/n) = 0. Finally, substituting the preceding expression for F(x) into this we get

π(x) = Li(x) + ∑2≤n<∞ μ(n)Li(x1/n)/n + other stuff

which, as claimed, is an “explicit” formula for π(x).

Oddly enough, Riemann did not try to use this explicit formula to give an asymptotic formula for π(x). Or perhaps not so oddly, because estimating the size of the “other stuff” is quite difficult. In particular, it entails dealing with with sums like

1≤n<∞ρ Li(xρ/n)

that involve zeros of ζ(s). Theoretically this is quite significant. It shows that π(x) depends explicitly on the zeros of ζ(s). However, in practice, dealing with these terms requires knowing about the location of those zeros. Our knowledge of this is very limited even today, and Riemann knew even less, in spite of his inspired hunch.

The bottom line is that it is necessary to describe the location of the zeros of ζ(s) at least crudely even to prove the prime number theorem. And in order to get the “best possible” estimate of π(x) it’s necessary to prove Riemann’s hypothesis.