Prime Theorem of the Century

"Prime numbers have always fascinated mathematicians," Underwood Dudley of DePauw University in Indiana wrote in a 1978 textbook. "They appear among the integers seemingly at random, and yet not quite: There seems to be some order or pattern, just a little below the surface, just a little out of reach."

A prime is a whole number (other than 1) that is divisible only by itself and 1. That simple definition leads to the following sequence of numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, and so on.

As the numbers of the sequence increase, the intervals between primes, on the average, get longer, though in a somewhat haphazard way. In other words, primes gradually become more scarce as numbers get larger, and one can imagine that, at some point, they might run out.

More than 2,000 years ago, however, the Greek mathematician Euclid proved that the sequence of primes continues forever. Suppose there is a finite number of primes, he argued. That means there's also a largest prime. Multiply all the primes together, then add 1. The new number is certainly bigger than the largest prime.

If the initial assumption is correct, the new number can't be a prime. Otherwise, it would be the largest. Hence, it must be a composite number and divisible by a smaller number. However, because of the way the number was constructed, all known primes, when divided into the new number, leave a remainder of 1. Therefore, the initial assumption can't be correct, and there can be no largest prime.

Proofs of the existence of infinitely many primes, however, give no indication of how these numbers are distributed or where to find a particular member of the sequence of prime numbers. Counting has to take the place of calculation to determine, for instance, precisely how many primes are less than some given number.

There are 4 primes among the first 10 integers; 25 among the first 100; 168 among the first 1,000; 1,229 among the first 10,000, and 9,592 among the first 100,000.

Such number patterns intrigued the great mathematician Carl Friedrich Gauss (1777-1855). When he was about 15 years old, Gauss obtained a list of all prime numbers less than 102,000, and he spent hours counting the number of primes in blocks of 100, 1,000, and 10,000 consecutive integers.

What he found was that, as numbers get larger, the proportion of primes decreases in a particular way. Among the first 10 integers, 1 in 2.5 is prime; among the first 100, 1 in 4; among the first 1,000, 1 in 6; among the first 10,000, 1 in 8.1; and among the first 100,000, 1 in 10.4. Apparently, for numbers up to 10^n, roughly 1 in 2.3n is prime.

Gauss conjectured that the number of primes smaller than a given integer x is approximately x/log x, where log stands for the natural logarithm. (The natural logarithm of a number x is 2.302585. . . times the base 10 logarithm of x.) A table of logarithms that Gauss used as a lad has a complete statement of the conjecture, written in his hand as a note in the margin.

A few years later, the prominent French mathematician Adrien Marie Legendre (1752-1833) came up with an equivalent conjecture concerning the average distribution of primes.

Gauss himself never published his conjecture, though he mentioned it in 1849 when he wrote to the astronomer Johann Franz Encke. By that time, with access to new, longer tables of primes, he could count the number of primes up to 3,000,000. His letter to Encke includes data that show the striking agreement between the actual number of primes and the number predicted by his formula.

No. of Primes Number	No. of Primes By Counting	Percent By Formula	Error
500,000	41,556	41,604.4	0.12
1,000,000	78,501	78,627.5	0.16
1,500,000	114,112	114,263.1	0.13
2,000,000	148,883	149,054.8	0.11
2,500,000	183,016	183,245.0	0.12
3,000,000	216,745	216,970.6	0.10

Note: The figures Gauss quoted for the number of primes weren't always correct.
For example, there are actually 78,498 primes among integers up to 1,000,000.

In the decades that followed, several celebrated mathematicians, including Peter Gustav Lejeune Dirichlet (1805-1859), Pafnuty Lvovich Chebyshev (1821-1894), and Georg Friedrich Bernhard Riemann (1826-1866), tackled various aspects of the distribution of primes. It wasn't until 1896, however, that two young mathematicians finally proved the conjecture of Gauss and Legendre. The achievement belonged to French mathematician Jacques Hadamard (1865-1963) and Belgian mathematician Charles-Jean de la Vallee Poussin (1866-1962), who independently arrived at the result nearly simultaneously.

The result is now known as the prime number theorem. In effect, it states that the average gap between two consecutive primes near the number x is close to the natural logarithm of x. Thus, when x is close to 100, the natural logarithm of x is approximately 4.6, which means that in this range, roughly every fifth number should be a prime.

"This is one of the most astonishing results in all of mathematics," comments Tom M. Apostol of the California Institute of Technology. "It describes a simple relation between the primes and the natural logarithm function -- which, at first glance, has nothing to do with prime numbers."

At the same time, the prime number theorem doesn't eliminate the element of surprise from the realm of primes. It doesn't specify exactly where a particular prime falls. There is still no simple formula for finding primes.

The proof of the Prime Number Theorem a century ago stands as one of the great achievements of mathematics. "The prime number theorem is important,"Apostol says, "not only because it makes a fundamental, elegant statement about primes and has many applications beyond mathematics, but also because much new mathematics was created in the attempts to find a proof."

The mining of prime terrain is far from finished. Here's Apostol's list of a few of the great unsolved problems in prime territory:

Is there an even number greater than 2 that cannot be written as the sum of two primes? (Goldbach's conjecture.)
Is there an even number greater than 2 that cannot be written as the difference of two primes?
Are there infinitely many twin primes, p and p + 2?
Are there infinitely many primes of the form 2^p - 1, where p is prime?
Are there infinitely many primes of the form 2^2^n + 1?
Are there infinitely many primes of the form x^2 + 1, where x is an integer?
Is there always a prime between n^2 and (n + 1)^2 for every positive integer n?
Is there always a prime between n^2 and n^2 + n for every integer n greater than 1?

"Solve any of the above, and your name, too, shall live forever in the mathematical hall of fame!" Apostol declares.

References:

Apostol, Tom M. 1996. A centennial history of the prime number theorem. Engineering & Science 59(Number 4):18-28.

Conway, John H., and Richard K. Guy. 1996. The Book of Numbers. New York: Copernicus.

Guiasu, Silviu. 1995. Is there any regularity in the distribution of prime numbers at the beginning of the sequence of positive integers? Mathematics Magazine 68(April):110-121.

Hawkins, David. 1958. Mathematical sieves. Scientific American 199(December):105-112.

Kramer, Edna E. 1970. The Nature and Growth of Modern Mathematics. New York: Hawthorn Books.

Peterson, Ivars. 1988. The Mathematical Tourist: Snapshots of Modern Mathematics. New York: W.H. Freeman.

Ribenboim, Paulo. 1995. Selling primes. Mathematics Magazine 68(June):175-182.

______. 1989. The Book of Prime Number Records. New York: Springer-Verlag.

Comments are welcome. Please send messages to Ivars Peterson at ipeterson@maa.org.