6103 words - 24 pages

MAY 2003 NOTICES OF THE AMS 545

PRIMES Is in P: A Breakthrough for

"Everyman" Folkmar Bornemann

"New Method Said to Solve Key Problem in Math" was the headline of a story in the New York Times on August 8, 2002, meaning the proof of the state- ment primes ∈ P, hitherto a big open problem in algorithmic number theory and theoretical com- puter science. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena of the Indian Institute of Tech- nology accomplished the proof through a surpris- ingly elegant and brilliantly simple algorithm. Convinced of its validity after only a few days, the experts raved about it: "This algorithm is beauti- ful" (Carl Pomerance); "It's the best result I've heard in over ten years" (Shafi Goldwasser).

Four days before the headline in the New York Times, on a Sunday, the three authors had sent a nine-page preprint titled "PRIMES is in P" to fifteen experts. The same evening Jaikumar Radhakrish- nan and Vikraman Arvind sent congratulations. Early on Monday one of the deans of the subject, Carl Pomerance, verified the result, and in his en- thusiasm he organized an impromptu seminar for that afternoon and informed Sara Robinson of the New York Times. On Tuesday the preprint became freely available on the Internet. On Thursday a further authority, Hendrik Lenstra Jr., put an end to some brief carping in the NMBRTHRY email list with the pronouncement:

The remarks … are unfounded and/or inconsequential. … The proofs in the paper do NOT have too many additional problems to mention. The only true mistake is …, but that is quite easy to fix. Other mistakes … are too minor to mention. The paper is in substance completely correct.

And already on Friday, Dan Bernstein posted on the Web an improved proof of the main result, short- ened to one page.

This unusually brief-for mathematics-period of checking reflects both the brevity and elegance of the argument and its technical simplicity, "suited for undergraduates". Two of the authors, Kayal and Saxena, had themselves just earned their bachelor's degrees in computer science in the spring. Is it then an exception for a breakthrough to be accessible to "Everyman"?

In his speech at the 1998 Berlin International Congress of Mathematicians, Hans-Magnus Enzensberger took the position that mathematics is both "a cultural anathema" and at the same time in the midst of a golden age due to successes of a quality that he saw neither in theater nor in sports. To be sure, some of those successes have many mathematicians themselves pondering the gulf between the priesthood and the laity within math- ematics. A nonspecialist-cross your heart: how many of us are not such "Everymen"?-can neither truly comprehend nor fully appreciate the proof of Fermat's Last Theorem by Andrew Wiles, although popularization efforts like the book of Simon Singh help one get an inkling of the connections. Probably no author could be found to help "Everyman"

Folkmar Bornemann is a professor...

Get inspired and start your paper now!