Monday, September 19, 2005

When is pi(x) > li(x)?

This question probably won't seem especially urgent to most folks, even mathematicians. But since it's related to the most famous unsolved problem in math, namely the Riemann Hypothesis, it seems worth noting a little bit of recent progress.

G. F. B. Riemann stated his hypothesis as merely an incidental remark in his work on the prime number theorem. This theorem, which Riemann worked on, but didn't himself prove, concerns the distribution of prime numbers. More specifically, it concerns the function π(x), which is defined as the number of prime numbers less than or equal to x, for any postive real number x > 0. One form of this theorem states that π(x) is asymptotically equal to x/log(x), where log(x) refers to the natural logarithm. In other words π(x)/(x/log(x)) approaches 1 as x becomes arbitrarily large.

There is a sharper form of this result, which can be written as
π(x) = li(x) + O((x/log(x))e-√log(x)/15)
Here the notation O(f(x)) means a quantity that is never more than Cf(x) for some constant C, and li(x) is defined as:
li(x) = ∫2≤t≤xlog(t)-1 dt
In this form, the prime number theorem was proved independently by J. Hadamard and C. de la Vallée Poussin in 1896.

The exact formulas aren't that important here. The key thing is that π(x) is "pretty close to" li(x) for large x. When people computed π(x) by hand -- an arduous task -- to determine precisely how close, they always found that π(x)<li(x), and so it was conjectured that this was true for any value of x, no matter how large.

However, in 1914 J. E. Littlewood proved that this conjecture was wrong, and in fact the quantity li(x)-π(x) changes sign infinitely often. So there must be some x such that π(x)>li(x), and we can ask what the least such x is. Apparently it is very large. The first good result on how large was obtained by S. Skewes in 1955, who showed that
x < 1010101000

Fortunately, that wasn't the end of the story. The exponent has been reduced considerably. Until this year, the best estimate was by H. te Riele in 1987, who showed that
x < 6.69 × 10370
But there has just been a "substantial" improvement. Kuok Fai Chao and Roger Plymen have shown that
x < 1.3984775 × 10316
See A new bound for the smallest $x$ with $\pi(x) > \li(x)$ for full details (if you're really curious).

How does this relate to the Riemann hypothesis? That hypothesis concerns the values of a complex function ζ(s) of a complex variable s. It says that the only "nontrivial" values s such that ζ(s)=0 all have the imaginary part of s equal to 1/2. (The "trivial" values are negative integers.)

It turns out that this statement is equivalent to one about π(x) and li(x), namely that
π(x) = li(x) + O(log(x)√x)
It is known that this is the best possible result that can hold. So the Riemann hypothesis, if true, says that the "best possible" approximation is correct, even though so far we have been able to prove only a somewhat lesser degree of approximation.

Labels: