The Mathematical Experience

by Philip J Davis & Reuben Hersh

5.The Prime Number Theorem (p209)

THE THEORY of numbers is simultaneously one of the most elementary branches of mathematics in that it deals, essentially, with the arithmetic properties of the integers 1, 2, 3,. . . and one of the most difficult branches insofar as it is laden with difficult problems and difficult technique.
Among the advanced topics in theory of numbers, three may be selected as particularly noteworthy: the theory of partitions, Fermat's "Last Theorem," and the prime number theorem. The theory of partitions concerns itself with the number of ways in which a number may be broken up into smaller numbers. Thus, including the "null" partition, two may be broken up as 2 or 1 + 1. Three may be broken up as 3, 2 + 1, 1 + 1 + 1, four may be broken up as 4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1. The number of ways that a given number may be broken up is far from a simple matter, and has been the object of study since the mid-seventeen hundreds. The reader might like to experiment and see whether he can systematize the process and verify that the number 10 can be broken up in 42 different ways.

Pierre de Fermat 1601 - 1665

Fermat's "Last Theorem" asserts that if n > 2, the equation  xⁿ + yⁿ =  zⁿ cannot be solved in integers x, y, z, with xyz ¹ 0. This theorem has been proved (1979) for all n < 30,000, but the general theorem is remarkably elusive. Due to the peculiar history of this problem, it has attracted more than its share of mathematical crackpottery and most mathematicians ardently wish that the problem would be settled. The prime number theorem, which is the subject of this section, has great attractions and mystery and is related to some of the central objects of mathematical analysis. It is also related to what is probably the most famous of the unsolved mathematical problems-the so-called Riemann Hypothesis. It is one of the finest examples of the extraction of order from chaos in the whole of mathematics.
Soon after a child learns to multiply and divide, he notices that some numbers are special. When a number is factored, it is decomposed into its basic constituents-its prime factors. Thus, 6 = 2 x 3, 28 = 2 x 2 x 7, 270 = 2 x 3 x 3 x 3 x 5 and these decompositions cannot be carried further. The numbers 2, 3, 5, 7,. . . are the prime numbers, numbers that cannot themselves be split into further multiplications. Among the integers, the prime numbers play a role that is analogous to the elements of chemistry.

Table of primes (Click to Expand)

Let us make a list of the first few prime numbers: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109113 ......
This list never ends. Euclid already had proved that there are an infinite number of primes. Euclid's proof is easy and elegant and we will give it. Suppose we have a complete list of all the prime numbers up to a certain prime Pm. Consider the integer N =  (2 ^. 3 ^. 5 ^{. . .} Pm) + 1, formed by adding 1 to the product of all the primes up to Pm. Now N is larger than Pm (for it is certainly more than twice its size). When N is divided by 2 it goes 3 ^. 5 ^{. . .} Pm times and leaves a remainder 1. When it is divided by 3, it goes 2 ^. 5 ^{. . .} Pm and leaves a remainder 1. Similarly, it leaves a remainder of 1 when divided by any of the primes 2, 3,5,. ...Pm.
Now N is either a prime number or it isn't. If it is a prime number, it is a prime number greater than Pm. If it isn't a prime number, it may be factored into prime numbers. But none of its prime factors can be 2, 3, 5,. ...., Pm as we just saw. Therefore there is a prime number greater than Pm. The logical argument (actually, the dilemma, which forces one to the same conclusion whichever path one is compelled to take) tells us that the list of primes never ends.
The second feature of the list of primes that strikes one is the absence of any noticeable pattern or regularity. Of course all the prime numbers except 2 are odd, so the gap between any two successive primes has to be an even number. But there seems to be no rhyme or reason as to which even number it happens to be. There are nine prime numbers between 9,999,900 and 10,000,000:

9,999,901	9,999,907	9,999,929	9,999,931
9,999,937	9,999,943	9,999,971	9,999,973
9,999,991.

But among the next hundred integers, from 10,000,000 to 10,000,100, there are only two: 10,000,019 and 10,000,079.
"Upon looking at these numbers, one has the feeling of being in the presence of one of the inexplicable secrets of creation," writes Don Zagier in an outburst of modern number mysticism. What is known about primes and what is not known or conjectural would fill a large book. Here are some samples. The largest known prime in 1979 was 2^21,701 -1. There is a prime between n and 2n for every integer n > 1. Is there a prime between n ² and (n + 1)² for every n > 0? No one knows. Are there an infinity of primes of the form n ² + 1 where n is an integer? No one knows. There are runs of integers of arbitrary length which are free of primes. No polynomial with integer coefficients can take on only prime values at the integers. There is an irrational number A such that [_A3ⁿ ] takes on only prime values as n = 0, 1, 2 (Here the notation [x] means the greatest integer £ x.) Is every even number the sum of two odd primes? No one knows; this is the notorious Goldbach conjecture. Are there an infinite number of prime pairs, such as 1; 3 or 17;19 or 10,006,427;10,006,429 which differ by 2? This is the problem of the twin primes, and no one knows the answer though most mathematicians are convinced that the statement is very likely to be true. Some order begins to emerge from this chaos when the primes are considered not in their individuality but in the aggregate; one considers the social statistics of the primes and not the eccentricities of the individuals. One first makes a large tabulation of primes. This is difficult and tedious with pencil and paper, but with a modern computer it is easy. Then one counts them to see how many there are up to a given point. The function p(n) is defined as the number of primes less than or equal to the number n. The function p(n) measures the distribution of the prime numbers. Having obtained it, it is only natural to compute the ratio n/p(n) which tells us what fraction of the numbers up to a given point are primes. (Actually, it is the reciprocal of this fraction.) Here is the result of a recent computation.

n	p(n)	n/p(n)
10	4	2.5
100	25	4.0
1000	168	6.0
10,000	1,229	8.1
100,000	9,592	10.4
1,000,000	78,498	12.7
10,000,000	664,579	15.0
100,000,000	5,761,455	17.4
1,000,000,000	50,847,534	19.7
10,000,000,000	455,052,512	22.0

Notice that as one moves from one power of 10 to the next, the ratio n/p(n) increases by roughly 2.3. (For example, 22.0 - 19.7 = 2.3.) At this point, any mathematician worth his salt thinks of log_e 10 (=2.30258...) and on the basis of this evidence, it is easy to formulate the conjecture that p(n) is approximately equal to n/log n.
The more formal statement that

lim_n®¥ p(n)/(n/log n) = 1

Carl Friedrich Gauss 1777 - 1855

Jacques Hadamard 1865 - 1963

is the famous prime number theorem. The discovery of the theorem can be traced as far back as Gauss, at age fifteen (around 1792), but the rigorous mathematical proof dates from 1896 and the independent work of C. de la Vallee Poussin and Jacques Hadamard. Here is order extracted from confusion, providing a moral lesson on how individual eccentricities can exist side by side with law and order.

While the expression n/log n is a fairly simple approximation for p(n) , it is not terribly close, and mathematicians have been interested in improving it. Of course, one does this at the price of complicating the approximant. One of the most satisfactory approximants to p(n) is the function

R(n) = 1 + å^¥_k=1  1/_kz(k+1) (log n)^k /_k!

where z(z) designates the celebrated Riemann zeta function :

z(z) = 1 + 1/2^z + 1/3^z + 1/4^z + ....

The accompanying table shows what a remarkably good approximation R(n) is to p(n) :

	p(n)	R(n)
100,000,000	5,761,455	5,761,552
200,000,000	11,078,937	11,079,090
300,000,000	16,252,325	16,252,355
400,000,000	21,336,326	21,336,185
500,000,000	26,355,867	26,355,517
600,000,000	31,324,703	31,324,622
700,000,000	36,252,931	36,252,719
800,000,000	41,146,179	41,146,248
900,000,000	46,009,215	46,009,949
1,000,000,000	50,847,534	50,847,455

Let us turn, finally, to the question of twin prime pairs. It is thought that there are an infinite number of such pairs, though this is still an open question.
Why do we believe it is true, even though there is no proof? First of all, there is numerical evidence; we find more prime pairs whenever we look for them; there does not seem to be a region of the natural number system so remote that it lies beyond the largest prime pair. But more than that, we have an idea how many prime pairs there are. We can get this idea by noticing that the occurrence of prime pairs in a table of prime numbers seem to be unpredictable or random. This suggests the conjecture that the chance of two numbers n and n + 2, both being prime, acts like the chance of getting a head on two successive tosses of a coin. If two successive random experiments are independent, the chance of success on both is the product of the chances of success on either; for example, if one coin has probability ¹/₂ of coming up heads, two coins have probability ¹/₂ x ¹/₂ =  ¹/₄ of coming up a pair of heads.
Now the prime number theorem, which has been proved, says that if n is a large number, and we choose a number x at random between 0 and n, the chance that x is 1 prime will be "about"  1/log n. The bigger n is, the better is the approximation given by  1/log n to the proportion of primes in the numbers up to n.

If we trust our feeling that the occurrence of twin primes is like two coins coming up heads, then the chance 1 that both x and x + 2 are prime would be about 1/(log n)². In other words, there would be about n/(log n)² prime pairs to be found between 0 and n. This fraction approaches infinity as n goes to infinity, so this would provide a quantitative version of the prime pair conjecture.
For reasons involving the dependence of x + 2 being prime on the supposition that x is already prime, one should modify the estimate n/(log n)² to (1.32032..)n/(log n)².
Appended is a comparison between what has been found and what is predicted by this simple formula. The agreement is remarkably good, but the final Q.E.D. is yet to be written.

Interval	Prime twins Expected	Prime twins Found
100,000,000 - 100,150,000	584	601
1,000,000,000 - 1,000,150,000	461	466
10,000,000,000 -10,000,150,000	374	389
100,000,000,000 - 100,000,150,000	309	276
1,000,000,000,000 - 1,000,000,150,000	259	276
10,000,000,000,000 - 10,000,000,150,000	221	208
100,000,000,000,000 - 100,000,000,150,000	191	186
1,000,000,000,000,000 - 1,000,000,000,150,000	166	161

Further Readings. See Bibliography E. Grosswald; D. N. Lehmer; D. Zagier.