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
xn + yn =
zn 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
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:
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 221,701 -1. There is a prime between n and 2n for every integer n > 1. Is there a prime between n 2 and (n + 1)2 for every n > 0? No one knows. Are there an infinity of primes of the form n 2 + 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 [A3n ] 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.
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 loge 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
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 +
where z(z) designates the celebrated Riemann
zeta function :
z(z) = 1 + 1/2z + 1/3z
+ 1/4z + ....
The accompanying table shows what a remarkably good approximation
R(n) is to p(n) :
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
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 1/2 of coming up heads, two coins have probability 1/2 x 1/2 = 1/4 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)2. In other words, there
would be about n/(log n)2 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
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)2 to (1.32032..)n/(log n)2.
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.
|100,000,000 - 100,150,000||584||601|
|1,000,000,000 - 1,000,150,000||461||466|
|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|