Section21.2Some history

Somewhat remarkably, the first people we know of compiling substantial data about this are Gauss and Legendre.

To properly understand what they did, we need another concept, somewhat related to Landau notation.

Definition21.2.1
We say that two functions \(f(x)\) and \(g(x)\) are asymptotic to each other when \[\lim_{x\to\infty}\frac{f(x)}{g(x)}=1\] Essentially, in the long run these functions get as close to each other as you like, on a percentage basis.

Legendre tried to estimate \(\pi(x)\). He said that \(\pi(x)\approx \frac{x}{\ln(x)-A}\), where he fudges the constant \(A\approx 1.08366\). More precisely, he claimed that \(\pi(x)\) is asymptotic to this function.

Another way to think of this is that the average chance of a number of size \(x\) being prime is about \(\frac{1}{\ln(x)-A}\). This was based on a lot of data he had collected, and the constant \(A\) seemed to give the best match to the data.

Not long after this, Gauss came up with a solution that was both more elegant and correct. And he didn't tell anyone for over fifty years! Gauss' conjecture was that \[\lim_{x\to\infty}\frac{\pi(x)}{x/\ln(x)}=1\] Or, using our new term, \(\pi(x)\) is asymptotic to \(\frac{x}{\ln(x)}\). So, roughly \(1/\ln(x)\) integers near \(x\) would be prime.

Subsection21.2.1The first really accurate estimate and errors

In fact, Gauss makes this more precise. Here is the general idea.

  • Reinterpret the proportion as suggesting that \(1/\ln(x)\) integers near \(x\) are prime. The we can think of this as a probability density function. What do we do with such functions? We integrate the function to get the cumulative amount!
  • That is, we should expect that \(\pi(x)\approx \int_0^x\frac{dt}{\ln(t)}\).
  • Or, equivalently, we should expect that \[\lim_{x\to\infty}\frac{\pi(x)}{\int_0^x\frac{dt}{\ln(t)}}=1\; .\]

This should sound 100% crazy! But Gauss and Legendre were no fools, and the accuracy is astounding.

Definition21.2.2
We give the name logarithmic integral to the (convergent) integral \(Li(x)=\int_0^x \frac{dt}{\ln(t)}\).

Notice how much closer \(Li(x)\) is to the actual value of \(\pi(x)\) than the \(x/\ln(x)\) estimate. It's usually closer by several orders of magnitude.

Subsection21.2.2Exploring \(Li\)

Can we try for some more analysis? Since we saw that \(x/\ln(x)\) didn't seem to be as good an approximation, we'll leave it out for now. This graphic follows one along a roughly 1000-wide stretch at a time.

It seems pretty clear that \(Li(x)\), even if it's a good approximation, will not ever be less than the actual count of primes. And yet, the English mathematician Littlewood proved the following result.

As remarkable as this seems, his student Skewes proved the following even more amazing fact.

This bound originally had a \(34\) in the last spot, but with a special assumption (the so-called Riemann Hypothesis, to which we shall return). In fact, today we know that the first time this “switch” happens is no higher than \(1.4\times 10^{316}\). There is still no explicit number known for which this is true, however, and we haven't even gotten remotely near those bounds with computers.

This sounds terrible, but actually is good news. After all, if \(\pi\) beats \(Li\) once in a while, then \(Li\) must be a great approximation indeed! So, just how great is it?