Not all mathematical equations have to be exact to be beautiful or powerful. In today’s post, I will share one famous example that illustrates this principle. But before I begin, I like invite you to watch this video clip:

The video you just watched highlights (in orange) all the prime numbers that can fit into a regular computer screen. Most people (apart than mathematicians) don’t give a hoot about prime numbers. Yet, these numbers role an enormously important role not only in the abstract world of mathematics but also in the real world of business and national security (think encryption).

Prime numbers are “proud” numbers. This is because they are only divisible by one and themselves. For example, 2 is divisible only by 1 and itself. So is 3, 5, 7, 11, 13 and so on. It has been known since the time of Euclid in 300 BC that there are an infinite number of prime numbers. The search for the largest prime numbers continues to this day with new discoveries aided by supercomputers or thousands of desktop computers working in tandem.

Infinity boggles the mind. How about a more down-to-earth question, like how many primes are there less than a finite real number x? Well, this is easy to answer for small x (say 100). Simply count them with a pocket calculator or a spreadsheet. For example, it is easy to see that are nine primes under 25 (they are: 2, 3, 5, 7, 11, 13, 17, 19 and 23). But the problem becomes horribly hard to solve when x is humongous, say a hundred billion. For such cases, it would be cool to have a formula that can supply an answer, even an approximate one (i.e., one that is ‘reasonably close’ to the truth).

Such a formula was derived by the famed German mathematician Carl Friedrich Gauss (1777 – 1855) when he was barely 15!

Gauss’s formula can be written as follows:

where “log” refers to the natural logarithm function. The notation is the approximate number of primes less than x. The formula says that in the limit (as x approaches infinity), the ratio to approaches 1, which is to say that we get more accurate approximations for very large x.

The first thing that strikes me when I came across this formula is how concise and elegant it looks. But does it work? The only way to find out is to verify the formula numerically and plot as a function of x over a wide range of values. I show two plots below. The first graph is for x up to 25 (i.e. x relatively small). The resultant plot looks like a staircase. Now see what happens when x goes to 1,000 (second graph). The “staircase” begins to look more like a smooth curve, This is the first hint that Gauss’s formula gets more accurate as x becomes large.

To honor Gauss, his formula has been given the grand-sounding name Prime Number Theorem. It is not a theorem in the usual sense of being backed by a solid proof. Gauss didn’t have one; he came up with his formula based on an educated guess.

This is what he did: rather than try to predict the precise location of the next prime, Gauss asked whether he could at least predict how many primes there are in the first 100 numbers, the first 1,000 numbers, and so on, hoping to catch a pattern. Using his keen power of observation, he noticed a pattern emerges when x becomes large. He was looking at a table like this:

The first column of the table shows x and the second number records the number of prime numbers less than x. For example, there are 25 primes for x up to 100. Thus, on average, one must count 100/25 or 4 numbers before one arrives at a prime number.

A pattern starts to emerge when x becomes very large x (in this table, around a hundred million). From this point on, Gauss noticed that every time he multiplied x by 10, he only have to add about 2.3 to the previous average (the third column) to deduce the number of primes less than x. This “add 2.3” pattern doesn’t appear until a hundred million. After that, the pattern stabilizes.

Why 2.3 is the interesting question. Just like 1, 2, 3 increases by one at a time when you go from log₁₀ 10 to log₁₀ 100 and log₁₀ 1000 etc, multiplying by 10 is roughly equivalent to taking the log of the resultant number to base e (a number known as the exponential constant). For example, log_e 100 is 4.605 and log_e 1000 = 6.908, giving a difference of about 2.3. From this, Gauss figured out that to get an approximate answer to the number of primes less than x, all one has to do is use his formula which exploits this property of the natural log.

But we still haven’t determine just how good Gauss’s formula is. The next plot will do this job. This plot compares the true number of primes for x up to 500 (top curve) and the estimate based on Gauss’s method (bottom curve). Not bad for an approximation formula!

Since the time of Gauss, mathematicians have continuously improved on Gauss’s original formula. I won’t go into the details here, but if you’re interested, do consult the references listed in note [1]. But I do want to conclude by saying that Gauss’s discovery reveals something else: that even though prime numbers seem to be randomly distributed (as you saw in the video), it is remarkable we can get pretty close to the actual number of primes less than very large x using Gauss’s simple and deterministic formula. Now, that is surprising and beautiful.

Notes

[1] The German mathematician Adrien-Marie Legendre (1752 – 1833) started the ball rolling by replacing Gauss’s approximation with one that divides x by log x – 1.08366. The correction factor shifts Gauss’s curve upwards to close in on the true number of primes up to x. Again, this is a piece of experimental mathematics without the backing of rigorous proof. Also, the constant 1.08366 was based on his limited table for values of pi(x), which only went to x = 400,000. In the long run, 1 is a better choice than Legendre’s 1.08366. Gauss himself came up with an alternate estimate (perhaps first considered in 1791 but published in 1863 in which pi(x) is approximately Li(x), the principal value of integral of 1/log u from u=0 to u=x).

Don Zagier gives a wonderfully lucid explanation for the reasoning behind the function Li in his introductory article “The first 50 million prime numbers” (from The Mathematical Intelligencer 0 (1977) 7-19, based on his inaugural lecture held at Bonn University, May 5, 1975):

“[A] good approximation to , which was first given by Gauss is obtained by taking as starting point the empirical fact that the frequency of prime numbers near a very large number x is almost exactly 1/log x. From this, the number of prime numbers up to x should be approximately given by the logarithmic sum:

Ls(x) = 1/log 2 + 1/log 3 + ^… + 1/log x

or, what is essentially the same, by the logarithmic integral

Notice again that Gauss’ conjecture is equivalent to the prime number theorem.  Let’s compare these estimates:

Finally, in 1896, the French mathematician, Jacques Salomon Hadamard and independently, the Belgian mathematician Charles de la Vallée Poussin  completely proved the prime number theorem using Riemann’s work relating pi(x) to the complex zeta function.  de la Vallée Poussin also proved that Gauss’ Li(x) is a better approximation to pi(x) than x/(log x –a) no matter what value is assigned to the constant a (though a =1 is still the best correction number). 

[2] If you’re not tired (or bored) by the prime number theorem by now, see P. Ribenboim, The Little Book of Big Primes, Springer-Verlag, New York, 1991. Check out this website which has a ton of information on prime numbers: The Prime Pages at https://primes.utm.edu/howmany.html. Finally, check out this excellent website (http://empslocal.ex.ac.uk/people/staff/mrwatkin/zeta/encoding1.htm)  if you’re wondering whether there are even better approximations to pi(x) than what I’ve discussed so far. Short answer: yes. And guessed what? They are still intimately related to Gauss’s log integral function, Li!