Built on Facts

You all know what the natural log function looks like. Take the number 1, divide it by the natural log, and then find the antiderivative of that function. You’ll get the logarithmic integral function. It looks like this:

Sometimes the lower limit of the integral is changed to 2 instead of 0, in order to get rid of that singularity at the origin. But we’re only interested in the behavior at large x so it doesn’t matter either way.

It turns out that if you count all the prime numbers up to one million, the answer will be approximately li(1000000). This is helpful because it’s a lot easier to calculate the logarithmic integral for huge numbers than it is to actually count up all the primes below that number. The formal statement of this fact is called the Prime Number Theorem, and it’s one of the most important facts in mathematics. Here it is:

Pi(x) is not the number pi times x, here pi(x) is actually the prime counting function, which is the number of primes less than x. As x gets larger and larger, pi(x) and the logarithmic integral become closer and closer approximations of each other in terms of their percentage difference.

But that’s in terms of their percent difference. Their absolute difference does grow without bound, it just does so more slowly than x. Now, prove the following statement and you’ll get a million dollars from the Clay Mathematics Institute, the Fields Medal, and a cushy job touring the mathematics lecture circuit. For some particular finite unchanging positive constant c:

That is, the error of the approximation grows more slowly than c times sqrt(x)*ln(x). You don’t even have to figure out the particular value of c, just prove that there is one. And furthermore, it doesn’t even have to be true for all x; just for all x greater than some particular finite positive constant. And you don’t even have to calculate the exact value of that constant either, just prove that there is one.

That statement is a consequence of the Riemann hypothesis, and the truth or falsehood of that statement has been proven to be the same as the truth or falsehood of the Riemann hypothesis. Unfortunately no one has yet been able to prove either statement in either direction despite its being the most important unsolved problem in mathematics.

Hey, it’s the weekend and you’ve probably got some free time. Your million dollars await!

Comments

#1 Dylan
August 17, 2008

Done!
#2 Miko
August 17, 2008

And furthermore, it doesn’t even have to be true for all x; just for all x greater than some particular finite positive constant.

But since we have an arbitrary constant c involved already, this second one isn’t saying anything new: suppose it’s true for x>k. Note the interval [1, k] is compact and it isn’t too difficult to show pi(x)-li(x) is bounded on it, and thus by adjusting c we could make it work for all x>0 just as easily.
#3 Matt Springer
August 17, 2008

True, and true without qualification if you use the definition of li(x) which starts the integral at 2 rather than 0. But pi(x)-li(x) isn’t bounded if you include 0, so for the benefit of those readers not familiar with Big O notation I decided to be more specific than technically required. Thanks for the clarification!
#4 Luke O'Dell
August 17, 2008

Really interesting post. Is there an application of this, or is it just cool mathematics?
#5 Uncle Al
August 17, 2008

The Feds confiscate 35% and California 10.3% more (income in excess of a magabuck). Are you definably self-employed doing mathematics? Subtract 15.3% for FICA and Medicare. A megabuck gross is about $394K net. You keep a third (sales tax if you buy something, of course). Now my advice for those who die, declare the pennies on your eyes. Cause I’m the tax man, yeah I’m the tax man. And you’re working for no one but me.
#6 Matt Springer
August 17, 2008

Is there an application of this, or is it just cool mathematics?

It’s mostly very important in pure math, but there are some possible applications. Since it’s intimately connected with prime numbers, it could conceivably have real-world cryptographic implications but there’s no way of knowing for sure yet. Less dramatically, it currently has applications in theoretical physics via the appearance of the zeta function in quantum field theory and a few other places.

More intriguingly, a conjecture of Hilbert and Polya might indicate a relationship between the Riemann hypothesis and both quantum and statistical mechanics.
#7 Paul Murray
August 18, 2008

I have discovered a remarkable proof of this, but unfortunately this comment box is too small to contain it.

(Sorry. Someone had to say it.)
#8 Johan
August 19, 2008

Unchanging constant? Is there any other kind?
#9 aatish
August 21, 2008

sure. most the ‘constants’ of nature (charge of the electron, etc.) change depending on the energy scale of your experiment.