NTIC Some History

Section 21.2 Some History

Somewhat remarkably, given how long humans have been studying primes, the first people we know of compiling substantial data about them are Gauss and Legendre, around 1800.

🔗

Legendre first tried to estimate

π (x) .

He said that

π (x) \approx \frac{x}{\log (x) - A},

where he fudges the constant

A \approx 1.08366 .

More precisely, he claimed that

π (x)

is asymptotic to this function.

🔗

Definition 21.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.

🔗

Here is another way to think about this. Think of the average chance of a number of size

x

being prime; Legendre guessed this was of the form

\frac{1}{\log (x) - A} .

This general notion was based on a lot of data he had collected, and the constant

A

he finally settled on seemed to give the best match to the data. (See also Figure 21.2.4 below.)

🔗

Not long after this, Gauss came up with a solution that was more elegant – and despite not being ‘fitted’ to the data in the same way, was correct. And he didn't tell anyone for over fifty years! Gauss' conjecture was that

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

🔗

Or, using our new term,

π (x)

is asymptotic to

\frac{x}{\log (x)} .

🔗

Subsection 21.2.1 The first really accurate estimate and errors

🔗

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

🔗

First, reinterpret the proportion as suggesting that

1 / \log (x)

integers near

x

are prime. If we do that, then we can think of

1 / \log (x)

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

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

or equivalently

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

🔗

Definition 21.2.2.

We give the name logarithmic integral³ to the (convergent) integral $L i (x) = \int_{2}^{x} \frac{d t}{\log (t)} .$

There is also a definition for this integral $\int_0^x\frac{dt}{\log(t)}\text{,}$ which has a properly defined value (beyond the level of this course) despite the integrand going to negative infinity. The form used for the prime counting function is traditionally the one with lower bound $2\text{,}$ for reasons clear in the rest of this text. There are no divergence issues at stake.

🔗

That a function as rigid as

π

would be close to an integral function should sound like it has a 100% probability of being crazy! But Gauss was no fool, and the accuracy is astounding.

🔗
Figure 21.2.3. Plot of prime pi function versus log integral

xxxxxxxxxx
 
@interact
def _(n=100):
    show(plot(prime_pi,3,n,color='black', legend_label=r'$\pi(x)$') + plot(x/log(x),3,n,color='red', legend_label=r'$x/\log(x)$') + plot(Li,3,n, color='green', legend_label='$Li(x)$'))

🔗

Notice how much closer

L i (x)

is to the actual value of

π (x)

than the

x / \log (x)

estimate. It's usually closer by several orders of magnitude, as you can try verifying numerically in the following interact.

xxxxxxxxxx
 
@interact
def _(n=[100,1000,1000000,1000000000]):
    P = prime_pi(n)
    pretty_print(html(r"$\pi(%s)=%s$"%(n,prime_pi(n))))
    pretty_print(html(r"The error with $%s/\log(%s)$ is $\approx %s$"%(n,n,P-(n/log(n)).n())))
    pretty_print(html(r"The error with $Li(%s)$ is $\approx %s$"%(n,(P-Li(n)).n())))

Figure 21.2.4. Excerpt from Gauss' letter to Encke on prime numbers

One of the brilliant aspects of the internet is how much easier it is to find source material of such things. Courtesy of the digitization center at the State and University Library of Göttingen (the university where Gauss worked), you can see a scan of the actual letter in question⁴.

Thanks to Martin Liebetruth for helpful correspondence; another helpful article on this, by Yuri Tschinkel, is in the Bulletin of the AMS.

In Figure 21.2.4, Gauss is comparing his calculations of the number of primes with his formula, as well as those of his correspondent and Legendre. Whether or not you can read Gauss' (quite legible) German, you can still note how in the last set of numbers he is essentially doing data science on Legendre's formula, with $A$ as the modeling variable, using more and more detailed training sets!

🔗

Subsection 21.2.2 Exploring $L i$

🔗

Can we try for some more analysis? Since we saw that

x / \log (x)

didn't seem to be as good an approximation, we'll leave it out for now. This graphic show two representative 1000-wide stretches, and the following interact allows you to explore more of them.

🔗
Figure 21.2.5. Compare prime pi and Li over two ranges

xxxxxxxxxx
 
@interact
def _(n=1000):
   P = plot(prime_pi,3,n, color='black',legend_label=r'$\pi(x)$')
   P += plot(Li,3,n, color='green',legend_label='$Li(x)$')
   show(P, xmin=max(n-1000,0), ymin=prime_pi(max(n-1000,0)))

🔗

Based on this evidence, it seems clear that

L i (x),

even if it's a good approximation, should not ever be less than the actual count of primes. And yet, the English mathematician John Littlewood proved the following result.

🔗

Fact 21.2.6.

For any number $x,$ there is an $x^{'} > x$ such that

L i (x^{'}) < π (x^{'}) .

🔗

Historical remark 21.2.7. Skewes' Number.

As remarkable as this seems, Littlewood's student Stanley Skewes proved the following even more amazing fact:

The first time this happens is no higher than

$10^{10^{10^{10^{1000}}}} .$

In Skewes' original paper, this bound had a $34$ instead of $1000$ in the last exponent⁵, but that result relied upon a special assumption (the so-called Riemann Hypothesis, see Chapter 25). Both of these bounds are known as Skewes' number.

Actually, the exact bound was $e^{e^{e^{79}}}\text{.}$

🔗

We have known since the 1960's that there is an actual run of integers where

L i

is smaller starting near

1.53 \times 10^{1165} .

Today we know that the first time this “switch” happens is no higher than

1.4 \times 10^{316}

(see [E.7.23] and a follow-up from 2015 for the state of the art). Of course, we haven't even gotten remotely near those bounds with computers, although computation is necessary to help obtain these bounds.

🔗

This uncertainty sounds terrible, but actually is good news. After all, if

π

beats

L i

once in a while, then

L i

must be a great approximation indeed! So, just how great is it?