Copyright 2002 The New York Times Company
The New York Times
September 3, 2002, Tuesday, Late Edition - Final
SECTION: Section F; Page 3; Column 2; Science Desk
LENGTH: 1434 words
HEADLINE: ESSAY;
From Here to Infinity: Obsessing With the Magic of Primes
BYLINE: By GEORGE JOHNSON
BODY:
There are practical reasons you would not want to smash atoms in your basement,
observing for yourself the peculiar behavior of the fundamental components of matter.
But studying primes, those mathematical quarks from which all numbers are made, is a
game anyone can play. The only hazard is that it is easy to become obsessed, even for a
nonmathematician.
It was early August, just after three computer scientists from India sent rumbles through
the mathematical world with a new discovery about primes Ð numbers like 7, 23 and
1,299,007 that are divisible by only themselves and 1. And there I sat, reading about the
implications on an Internet rumor-mill called Slashdot.org while listening for inspiration
to an eerie John Cage-like musical composition derived from the first 18,000 primes.
Then, out of curiosity, I began plugging one long string of digits after another into a
computer program designed to test for primality. My Social Security number, my
MasterCard number, the numbers on my checking account and driver's license. All, to
my dismay, failed the test. They were mere composites, those boring, commonplace
numbers that can be made from multiplying primes together.
Hoping to sharpen my intuitions, I visited Prime Island, an imaginary world
(yoyo.cc.monash.edu.au/bunyip/primes) generated by feeding primes into a computer
graphics program. The resulting landscape, a kind of cross between the Labrador coast
and the Utah canyon lands, evokes the austere beauty of these unsplittable numbers and
the manner in which they are scattered through the number system -- haphazardly, it
seems, but with possible hints of an underlying order.
Other explorers of these abstract lands have tried translating sequences of primes into
nucleotide chains, perhaps seeking some primal life form. I would have been content
simply to find a good meaty prime in my personal life. My boyhood phone number,
with or without area code, my FedEx account, even my ZIP code. Still, not a single one.
Clearly these are rare birds, as became increasingly apparent as I leafed through the bills
in my wallet hoping to find at least one serial number that was prime. 55,396,545? This,
I was briskly informed by the program, can be broken into 3 and 18,465,515 (which, in
turn, can be reduced to 5 x 223 x 16,561).
Maybe then 56,774,503. Wrong again. It comes from multiplying 109 and 520,867.
O.K., then, what if both the serial numbers are spliced together, one after another:
5,539,654,556,774,503? That, alas, is 11 times 503,604,959,706,773. Not even reversing
the digits helps: 3,054,776,554,569,355 is 5 times 610,955,310,913,871.
With an infinity of primes (Euclid proved this) one would think that the hunt would be
easier. But the further you crawl out on the number line, the sparser the primes become.
Twenty-five percent of the numbers between 1 and 100 are prime, but less than 4
percent of those between 1 and 1 trillion. It is downhill from there. (According to the
prime number theorem, the decline follows a logarithmic relation -- a hint of an
overarching pattern.)
For some larger numbers, the prime-testing program could determine that they were
composites but not what their factors were. That would have taken too much number
crunching. It is curious that, using various mathematical tests, one can tell if a number is
prime without going to the bother of factoring it.
That is where the Indian computer scientists' discovery comes in. For years
mathematicians have been able to take very long numbers -- so long that they could not
be factored in any reasonable time -- and run them through a kind of primality testing
machine: an algorithm that can say, with a very high likelihood, whether the number is
fissionable.
This is good enough for practical purposes. These highly probable "industrial grade"
primes are used on the Internet to generate the keys that encode secret messages. But, for
mostly theoretical reasons, mathematicians had long wondered whether there was an
efficient way to tell with absolute certainty that any number was prime.
The answer, they now know, is yes. In a preprint posted at
www.cse.iitk.ac.in/news/primality.html, Dr. Manindra Agrawal and his students Neeraj
Kayal and Nitin Saxena of the Indian Institute of Technology in Kanpur offer a
foolproof primality-testing algorithm that runs in "polynomial time." As it examines
longer and longer numbers, the computing time increases but not so drastically as to
overwhelm the machine.
When the result was announced, the Internet briefly buzzed with rumors that something
even greater had happened: the factoring process itself had been cracked wide open.
That would have been a truly stunning result.
The fastest known factoring techniques are "superpolynomial"; slightly increasing the
size of the input causes the algorithm to slow to a glacial crawl. Breaking down a number
hundreds of digits long can take billions of years. A fast mathematical shortcut would
revolutionize mathematics, and cause civilization's codes to come undone.
The news from Kanpur stands as a reminder that this still might happen. As one
mathematician put it: "The only proof we have that factoring is hard is that it's been an
open problem for many years. But then so was primality testing."
Meanwhile, some mathematicians (and a few amateurs) continue to scrutinize primes,
searching for a rhythm to the way they are distributed -- a kind of Mendeleyev's periodic
table, a genetic code of the number system . . . a harmonic theory that might explain the
erratic yet somewhat soothing sound of the prime number music, called halo.mid (the
suffix meaning that it is a midi file), that continues to emanate from my loudspeakers.
Accompanying it now, like the libretto of an opera flashing on an electronic screen, is a
little counter I found on the Web that reels off one prime number after another: 22,973,
22,993, 23,003, 23,011, 23,017, 23,021, 23,027 . . .
They appear with no obvious order (like weeds in the number system, a mathematician
once said), but maybe there is a larger pattern that the human brain just cannot discern.
In fact, researchers have found evidence of a linkage between quantum mechanics and
something called the Riemann function, a mathematical relationship deeply connected
to the distribution of primes. Maybe the particles of the number system are somehow
intertwined with the particles of matter and energy.
. . . 98,711, 98,713, 98,717, 98,729, 98,731, 98,737, 98,773 . . . The counter keeps
ticking off primes. Those, like 98,711 and 98,713 or 98,729 and 98,731, which are just
two places apart (the closest two primes can be), are called twin primes. They pop up
with amazing regularity, and mathematicians believe that there is an infinity of them.
The mysteries abound. While killing time during a boring lecture (or so the legend goes),
the 20th-century mathematician Stanislaw Ulam discovered his "Ulam spiral": Build a
grid of numbers starting with 1 at the center, moving over a square for 2 and then coiling
around. The primes inexplicably tend to line up along diagonals. Plot thousands of
numbers this way, representing each with a tiny dot, and the diagonals crisscross like
some tenuous crystalline structure, a scaffolding behind the stars in the numerical skies.
Maybe this is what the autistic twins in Oliver Sacks's "The Man Who Mistook His Wife
for a Hat" saw with their inner eyes. Dr. Sacks wrote of how he observed the brothers
one day at a state mental hospital as they sat in apparent rapture exchanging six-figure
primes that they seemed to pull from their heads.
The next day the doctor returned and offered them an eight-figure prime to play with.
Once they overcame their astonishment, the twins were off, generating 10-digit primes.
Dr. Sacks's list did not go any higher so he was unable to check their work as they went
on to spout seemingly impenetrable numbers as long as 20 digits. If only he had had the
Agrawal-Kayal-Saxena algorithm.
Could the twins have been born with the neurological equivalent? Dr. Sacks speculated
in his book that they were equipped with a "Pythagorean sensibility," a special feeling for
numbers, "a direct cognition -- like angels."
The gift, if that is what it was, turned out to be exceedingly delicate. Ten years later the
two were separated and put in halfway houses. Though they learned important
grooming skills and how to ride buses, Dr. Sacks reported, the ability to commune with
numbers was apparently gone. They had become as clueless as the rest of us.
http://www.nytimes.com
GRAPHIC: Photo: This imaginary landscape, Prime Island, was generated by a
computer program to give viewers an idea of how primes are distributed through the
number system -- haphazardly, but with hints of a subtle order. (Adrian Leatherland)
Chart: "Prime Patterns"
In Ulams Spiral, where numbers coil outward, the prime numbers tend to line up in
diagonals.
Diagram of Ulams Spiral.
LOAD-DATE: September 3, 2002