|
From here to infinity
By George Johnson
Copyright 2002 The New
York Times Company. All Rights Reserved.
Excerpts from article ...
full text available from the New York Times on the newsstand.
http://www.nytimes.com/2002/09/03/science/03ESSA.html
September 3, 2002
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 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.
http://yoyo.cc.monash.edu.au/~bunyip/primes/
...
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
http://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."
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.
|
|