The Prime Number Theorem explained

People have asked me to explain how Gauss’ Prime Number Theorem actually works. I mentioned it in my “How to Find Prime Numbers” post, but never explained it, so here is a short and (relatively) simple guide.

To begin with, let’s take a look at the trends in the density of primes up to a certain integer. We can find the density of primes by calculating p / x, where x is the number of integers and p is the number of primes from 1 to x. If we make a table of the density to each power of 10, it will look like this:

x p Density
10 4 40%
100 25 25%
1,000 168 16.8%
10,000 1,229 12.29%
100,000 9,592 9.592%
1,000,000 78,498 7.8498%
10,000,000 664,579 6.64579%
100,000,000 5,761,455 5.761455%

You can see that the density is always decreasing, but the rate is also decreasing. This is very similar to a logarithmic pattern. In fact, if we plot the graph of y = ln(x), mirror it along the horizontal axis so that it becomes y = 1 / ln(x), and compare it to the graph of the density of prime numbers, there is a striking similarity.

Green:  y = 1 / ln(x) Blue: Density of primes

Green: y = 1 / ln(x)
Blue: Density of primes

You’ll find that as the value of x increases, the correlation between the two graphs becomes stronger and stronger. The density of primes follows an almost instinctive natural curve.

This link makes it possible for us to predict the density of primes up to any value of x with the formula 1 / ln(x). The higher the value of x, the higher the accuracy of the prediction. To find the expected number of primes, you only need to find the area under the graph of the density, which can be found using integration. Gauss refined this a little to create the logarithmic integral Li(x), which gives a slightly more accurate estimate for the lower values of x. I ought to give Adrien-Marie Legendre some credit here as well, because he and Gauss both independently conjectured Li(x) at around the same time. Gauss is generally more associated with this, however, mainly because of his legacy.

l talk about how this links into the Riemann hypothesis (and more) in my previous post, which you can read here.

Thank you for reading.

-Ollie James

Advertisements