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