Prime Number Theorem

Austin TX

I was thinking about prime numbers this past summer. In Prime Parking, I mentioned the prime number theorem. It deserves a little more than the brief nod I gave it.

Many great mathematicians worked on creating and proving a conjecture about how many primes can be found smaller than any given number. For example, there are 4 primes less than 10 (2, 3, 5, and 7) and 8 primes are smaller than 20 ( 2, 3, 5, 7, 11, 13, 17, and  19). The prime-counting function π(x) is the exact number of primes less than x.  The “π” is not referencing the number. This is not “π times x.” The “π” is referencing the Greek letter for “p,” as in prime. I recommend you read “π(x)” as, “the number of primes less than x.” With that said π(10) = 4 and π(20) = 8.

In the late 1700’s Legendre worked on creating a formula for π(x). Over the next 100 years, Gauss, Dirichlet, Chebyshev, and Riemann all took giant leaps in the search. It was in 1896 that Hadamard and De la Vallée Poussin published independent proofs of the PNT.^* (The prime number theorem: so important it gets an acronym).

I got curious about 1896. The first x-ray photograph was taken in 1896. Utah took its place (45th) amongst the United States. The first modern Olympic games were held in Athens, Greece. William McKinley won the U.S. presidential election. That was 1896.

Rewind 31 years to 1865, and Hadamard was born in Versailles, France. Fast forward to the 1940s, and we find Hadamard escaping from Vichy France, arriving in the U.S., and working at Columbia University. Hadamard passed away in Paris in 1963 at the age of 97.

Charles-Jean Étienne Gustave Nicolas de la Vallée Poussin was born in 1866. He passed away 95 years later in 1962. He was a Belgian mathematician.  In 1914, he left Belgium as the WWI forces of the German army were arriving. Vallée Poussin spent four years at Harvard before returning to Europe in 1918.

Much more can be said about the century these two men lived. Industrial revolution, airplanes, world wars, and automobiles changed how we live. Vallée Poussin was made a baron by the King of Belgium. Hadamard’s wife was related to Dreyfus of the Dreyfus affair. This is a meager sampling of information. There is much more to both of their lives.^† We will, however, return to the maths.

What is the PNT?

Clearly, that “~” is not an equals sign. This is not a rule for finding the exact number of primes less than x. The tilde (~) means something like, “as x heads to ∞, the relative error heads to zero.” We, math folk, call this sort of business an asymptotic form.

To work with the rule, you may want to know ln(x) is the natural logarithm of x. Analogous to division undoing multiplication, a logarithm undoes exponentiation. Since 2³ = 8, the log₂ 8 = 3. A logarithm returns the exponent. Rather than using 2 as the base, the ln(x) is log_e x and an answer to the question, “To what power would I raise e to get x?” e is a number and is about 2.71828. It is named after Euler. (Remember him?) Don’t worry, your scientific calculator has an “ln” button. (If you have a semi-intelligent phone or access to the internet, you have a scientific calculator.) You should be able to confirm that 10/ln(10) is about 4.3429. Not bad, seeing as how π(10) = 4.

To be clear, it is not that the difference between π(x) and x/ln(x) is heading to zero. It isn’t. The difference is actually growing. But, it is important to consider how the difference is growing relative to the growing value of x.

You can think of it this way. If you loan your friend $5, it may be weird if he only gives you $3 back. If you loan him $10,000 and he only pays you back $9,996, you may not sweat the $4 difference; he is your friend, after all. Your experience of the error is relative to the loan amount. Their error doubled,  but the relative error shrunk.

There is a Wikipedia page with a good table to see this. (Click that link and take a look.) The third column of the table is the difference between the actual number of primes less than x and PNT’s approximation. You will see those numbers are growing. BUT, in the next column, you can see what happens when you divide π(x) by x/ln(x). The numbers in that column are heading to one. What do we know if the ratio of two values is close to one? Numbers like 99 and 100? Yes, if the ratio of two number is close to one, the two numbers are pretty close to one another.

Now, don’t miss the values in the second column of that table. Those are the actual numbers of primes less than each value of x. You can see, for example, there are 455,052,511 prime numbers less than 10¹⁰ = 10,000,000,000.

Yes, π(10¹⁰) = 455,052,511.

       

---

*↑ The first proofs of the prime number theorem used the Riemann zeta function. This function was studied by Euler in the late 1700’s and then published in a paper by Riemann in 1859.

†↑ The Wikipedia Prime Number Theorem article has a lot of good details about the historical background. As do the pages about Hadamard and Vallée-Poussin on Wikipedia.