|Figure 2.1 The sieve of Eratosthenes catches 25 primes among whole numbers less than 100.|
Although some shortcuts simplify the sieving, it remains a tedious,
time-consuming procedure, especially when the targets are dozens or hundreds
of digits long. Sieving is a serious business for number theorists, and because
they have no reliable formulas that automatically generate only prime numbers
of any desired size, they use the sieve of Eratosthenes to fill in the gap.
The claims of some mathematicians, both amateur and professional, to have
found a magic formula for primes have invariably turned out to be false.
In many cases, the formulas are merely cleverly disguised versions of the
ancient sieve of Eratosthenes.
Because so many important ideas in number theory seem resistant to definitive
analysis, experiment plays an important role in this field of mathematics
research. Although their work differs from the experimental research associated
with, say, test tubes and noxious chemicals, number theorists, like chemists
and other researchers, often collect piles of data before they can begin
to extract the principles that neatly account for their observations. Strict
reliance on deduction-the hops, steps, and jumps from one theorem or logical
truth to another that we usually associate with mathematics - isn't sufficient
in number theory.
Few people outside of mathematics are aware of the field's empirical aspect.
Much of the mathematics encountered by high-school and college students seems
carved in stone, passed on unchanged from one generation to another. Yet
even the fundamental principles of arithmetic and plane geometry were once
the subjects of debate and speculation. It took centuries of constant
questioning. brilliant guesses, and steady refinements to build the edifice
now known as mathematics, and the structure continues to evolve. The
study of prime numbers is one of the few areas still left in mathematics
in which the concepts, questions and experiments are still simple enough
to intrigue both amateur and professional mathematicians. In fields such
as algebraic topology and differential geometry, usually only the professionals
and advanced graduate students experience the thrill of the quest.
The search for patterns and trends plays an important role in the study of
the distribution of prime numbers. Clearly, although Euclid proved that the
list of primes goes on forever, the stretches between primes, on the average,
get longer and longer (see Figure 2.2). The elimination of multiples of every
new prime encountered by the sieve of Eratosthenes nicely demonstrates the
increasing scarcity of primes among the larger integers.
At the same time, prime numbers appear to be scattered haphazardly throughout
the whole numbers. In 1896, French mathematician Jacques Radamard and Belgian
Charles de la vallee-Poussin used this idea to find an expression that precisely
describes the statistical distribution of primes. The theorem that they
independently proved is now known as the prime number
theorem. It proposes that the average distance between two consecutive
primes near the number n is close to the natural logarithm of
n. When n is close to 100, for instance. the natural logarithm
of n is approximately 4.6. In that range, every fifth number or so
should he a prime.
|Figure 2.2 A computer-generated grid showing primes (white dots) as a spiral of integers from 1 to about 65,000.|
But the prime number theorem doesn't eliminate the element of surprise. It
doesn't specify exactly where a particular prime falls. That's left to the
innumerable tests and experiments that make up the gathering-of-data phase
of mathematics research. This data-collection operation now increasingly
involves computers, which have extended the list of known primes well beyond
the range of hand calculation.
Sometimes, tantalizing pattern fragments show up. The sequence 31, 331,
3331, 33331, 333331, 3333331, 33333331 looks promising: all the numbers
in that sequence are primes. Alas, it fails in the next step. The number
333333331 is a composite with factors 17 and 19607843. Such accidental patterns
Some simple equations can generate a surprising number of primes. The formula
x2 + x + 41, for example, produces an unbroken sequence
of 40 primes, starting with x=0 (see Figure 2.3). For values of
x up to 10,000, the formula produces primes almost half the time.
However, beyond 10,000, the proportion of primes inevitably decreases. Another
simple "prime-rich" formula", x2 + x + 17, also
discovered by the eighteenth-century Swiss mathematician
Leonhard Euler, generates primes for all values of
x from 0 through 15. However, mathematicians have proved that no
polynomial formula has only prime values, so a search for general formulas
similar to the ones illustrated is fruitless.
Primes often appear as pairs of consecutive odd integers: 3 and 5; 11 and
13; 41 and 43; 179 and 181; 209,267 and 209,269; and so on. These twins are
spread throughout the list of known prime numbers. Statistical evidence suggests
that there are infinitely many twin primes, and mathematicians have estimated
that in the range close to the number n, the average distance between
one pair of twin primes and the next is close to the square of the natural
logarithm of n. But no one has yet proved that there is an infinite
number of twin primes; it remains one of the major unsolved problems in number
theory. Over the last century, numerous mathematicians have attacked the
problem in a variety of ways, but all have failed. The optimists believe
that it may take another century of determined assaults before anyone succeeds.
At the same time, it's relatively easy to prove that consecutive primes can
be as far apart as anyone would want. The sequence of numbers n! +
2, n! +3, n! ..... . n! + n shows this conjecture
must be true. The expression n! (read as n factorial) is less a statement
of mathematical excitement than a shorthand way of writing the product of
all whole numbers from 1 to n. The number n!, where n = 5,
for example, has a value of 1 x 2 x 3 x 4 x 5, or 120. In the general case,
n! + 2 is evenly divisible by 2, n! + 3 is evenly divisible
by 3, and so on. Finally, n! + n is evenly divisible by n.
Therefore, all the numbers in the sequence are composite. The sequence can
be made arbitrarily long by picking a sufficiently large number n.
|Figure 2.3 The primes between 41 and 439 plotted on a square spiral beginning with 41 in the center.Values along the diagonal satisfy the formula x2 + x + 41|
All their suggestive properties indicate that primes are not randomly scattered
among the integers, yet prime numbers, in their maddening perversity, defy
all attempts aimed at putting them precisely in their places. To try to prove
many conjectures about prime numbers, mathematicians therefore often must
devise sneaky strategems to get at their prey indirectly. They fence in the
unruly conjecture, first staking out a wide swath of territory before gradually
closing in on it. The pursuers then draw the net tighter, taking in corners
and cutting down boundaries while scrupulously checking for loop- holes.
Finally, if all goes well, the conjecture is trapped.
One such attempt is the continuing work on the Goldbach conjecture, which
views prime numbers as the building blocks of other numbers. The Prussian
mathematician Christian Goldbach suggested the idea
in a letter to Euler in 1742. His claim, expressed in modern terms, is that
every even number greater than 4 is the sum of two odd primes (that is, primes
other than 2). The number 32, for instance, is the sum of 13 and 19. This
proposition is now known as the "strong"
Goldbach conjecture. The "weak" Goldbach
conjecture holds that every odd number greater than 7 can be expressed as
the sum of three odd primes. In both cases, the same prime number may be
used more than once in a single sum.
Neither conjecture has yet been proved, but over the years, there have been
several near misses. In 1937, the Russian mathematician Ivan M. Vinogradov,
a leading number theorist, showed that all "sufficiently large" odd numbers
can be expressed as the sum of three primes. Although Vinogradov couldn't
state explicitly what "large enough" meant, in 1956, his student K. V. Borodzin
found that 3315 works as an upper bound. That number
has more than 6 million digits. If all odd numbers smaller than
3315 are the sum of three primes, then the weak Goldbach
conjecture is proved.
Computer searches have verified both the strong and weak conjectures up to
at least a million. Mathematicians have also proved that if the weak conjecture
is false, then there are only a finite number of exceptions. Thus the trap
is closing in on the weak conjecture, and many mathematicians now regard
it as "essentially" proved. The strong version is somewhat more elusive,
but in 1966, Chinese mathematician Chen Jing-run showed that all large enough
numbers can be expressed as the sum of a prime number and a number that is
either prime or the product of two primes. The net tightens.
Despite such successes, some number theorists believe that certain central
questions about prime numbers may have no solutions. In 1931, a startled
mathematical world had to confront and learn to live with such a possibility,
not just in number theory but everywhere in mathematics. Austrian mathematician
and logician Kurt Gödel
proved that any collection of axioms, such as those underlying euclidean
geometry or the theory of infinite sets, leads to a mathematical system
containing statements that can be neither proved nor disproved on the basis
of those axioms. A theorem, then, can be undecidable: adding more axioms
wouldn't help because some theorems would still slip through. Furthermore,
Gödel's work implies that in some cases, mathematicians wouldn't even
be able to decide whether a theorem can or cannot be proved. Uncertainty
strikes in mathematics!
Various guesses about prime numbers, perhaps even the strong Goldbach
conjecture, may truly turn out to be undecidable. Few mathematical fields
other than number theory have so high a proportion of widely believed but
unproved propositions. This doesn't mean that the conjectures are all likely
to be false, but it implies that for some conjectures, an airtight case might
not exist, despite the steady accumulation of persuasive evidence in its
favour. Mathematical proofs require more than
just overwhelming evidence.
Even so, the quest isn't hopeless. Near misses and proofs that confirm special
cases or parts of conjectures hint that eventually techniques may be developed
to handle the problems-although it could take centuries. That is far different
from saying that a conjecture can never be proved, for a single breakthrough
could put such suppositions as the number of twin primes suddenly within
reach. Meanwhile, with the use of computers, specific knowledge about prime
numbers is growing steadily, although considering the centuries of effort
put in by numerous mathematicians, the theory of prime numbers still seems