Jascha Hoffman

Here's a problem Lewis Carroll enjoyed posing to kids like Alice: how many colors do you need to fill in any map so that neighboring countries are always colored differently?

It sounds simple enough. But when a Victorian law student first posed the question, guessing that it could be done with a mere four colors, logician Augustus De Morgan was stumped. While no one could devise a map that required more, a proof that every map requires only four colors proved remarkably elusive. Mapmakers didn't care, but problem-solvers were obsessed for decades, including the Bishop of London, a Kentucky colonel, and a California traffic cop. The question's very intractability has inspired innovations in computing and network theory, but some say it still has no satisfying solution.

Oxford professor Robin Wilson's Four Colors Suffice: How the Map Problem was Solved (Princeton: 2003) presents the colorful history of this conjecture, with an unassuming lucidity that will appeal to the mathematical novice. It's thrilling to see great mathematicians fall for seductively simple proofs, then stumble on equally simple counter-examples. Or swallow their pride: after telling his class that the problem had been wasted on third-rate minds, the great number-theorist Herman Minkowski took weeks at the blackboard trying to solve it, finally admitting, "Heaven is angered by my arrogance; my proof is also defective."

The first dead-end occurred shortly after the problem was first posed in 1852. De Morgan became obsessed with his initial insight that in any group of four regions, each bordering every other, one region must be completely enclosed by the others, and thus safe from forcing any colors outside the group. Though undeniably true, this was a false start: looking at single groups of four, one at a time, fails to take into account the myriad ways these groups might interact in ways that force the use of more colors.

The next failure, which convinced mathematicians worldwide for over a decade, actually took giant steps in the right direction. Cambridge mathematician Arthur Cayley revived the problem in 1878 and suggested a totally new approach: if you assume there exist some maps that need more than four colors, and of those you take only the ones that have as few regions in them as possible, then you'll have a manageable but complete set of counter-examples on your hands. (Wilson calls these the "minimal criminals.") If you can show that none of these counter-examples can possibly exist, then you've shown that four colors suffice. The only problem is, there are lots of them.

London barrister and amateur mathematician Alfred Bray Kempe ran with this approach, devising an elegant method that claimed to cleanly dispatch with all possible counter-examples. He put one region after another at the center of a counter-example-first a two-sided shape, then a triangle, square and pentagon-then ruled them out by listing all the possible chains of regions that could branch off from them. The proof was widely accepted, and Kempe was elected a Fellow of the Royal Society, and even knighted.

But in 1890, Percy Heawood, an Oxford eccentric known for his immense mustache and flowing cape, produced a map that showed that one of Kempe's chains didn't work. Even as he disgraced Kempe, however, Heawood demonstrated the lasting value of his contribution, giving a full Kempe-style proof that five colors suffice. (As a result of Heawood's later work, we now know that any map drawn on a doughnut requires no more than seven colors, not counting sprinkles. "There are, of course, additional reasons why one seldom encounters a map of the United States on one's doughnut," mused novelist Tom Robbins.)

The modern story picks up in 1948, when German geometer Heinrich Heesch realized that if he could find a master set of patterns that can't appear in a minimal criminal, he would rule out all possible counter-examples and have a proof. But finding these patterns was really hard, and there were thousands of them.

Enter the computer. In 1976, after 2000 machine-hours at the University of Illinois, Kenneth Appel and Wolfgang Haken found every single one, turning out the first famous computer-aided proof. Some claimed this was not a proof, since it cannot be verified in detail by a human being. By admitting computer proofs into the canon, writes Robin Wilson, math was "in danger of becoming an empirical science, as fallible as physics." Far from a feat of pure reasoning, the answer appeared to some as a monstrous coincidence.

There's an unwritten law as old as math itself: proof comes with understanding. But Appel and Hanken's proof, while almost certainly valid, doesn't clear anything up. Math is changing because of proofs like theirs: Computer jocks like Stephen Wolfram insist that math needs to get beyond its infatuation with axioms, while string theorists say their results just can't wait for rigorous proof. And strangely, mathematicians are even starting to teach machines to prove theorems on their own. So maybe some day computers will explain why four colors are enough, in terms we can understand.

BERKELEY, Calif. - A reclusive Russian mathematician appears to have answered a question that has stumped mathematicians for more than a century.

After a decade of isolation in St. Petersburg, over the last year Grigory Perelman posted a few papers to an online archive. Although he has no known plans to publish them, his work has sent shock waves through what is usually a quiet field.

At two conferences held during the last two weeks in California, a range of specialists scrutinized Perelman's work, trying to grasp all the details and look for potential flaws.

If Perelman really has proved the so-called Poincare Conjecture, as many believe he has, he will become known as one of the great mathematicians of the 21st century and will be first in line for a $1 million prize offered by the Clay Mathematics Institute in Cambridge.

Colleagues say Perelman, who did not attend the California conferences and did not respond to a request for comment, couldn't care less about the money, and doesn't want the attention. Known for his single-minded devotion to research, he seldom appears in public; he answers e-mails from mathematicians, but no one else.

"What mathematicians enjoy is the chase of really difficult problems," said Hyam Rubinstein, a mathematician who came from Australia to attend meetings at the Mathematical Sciences Research Institute in Berkeley and the American Institute of Mathematics in Palo Alto, Calif., hoping to better understand Perelman's solution. "This problem is like the Mount Everest of math conjectures, so everyone wants to be the first to climb it."

The Poincare Conjecture, named after the Frenchman who proposed it in 1904, is the question that essentially founded the field of topology, the "rubber-sheet geometry" that looks at the properties of surfaces that don't change no matter how much you stretch or bend them.

To solve it, one would have to prove something that no one seriously doubts: that, just as there is only one way to bend a two-dimensional plane into a shape without holes - the sphere - there is likewise only one way to bend three-dimensional space into a shape that has no holes. Though abstract, the conjecture has powerful practical implications: Solve it and you may be able to describe the shape of the universe.

Dozens of the best mathematicians of the last century tried with all kinds of approaches to solve the conjecture. Some thought they had it for months, even years, but counter-examples and flaws just kept springing up. Simply-stated but elusive to prove - like Fermat's Last Theorem - this conjecture has spurred the development of whole branches of mathematics.

A decade ago, after some work in the United States that colleagues described as "brilliant," Perelman gave up a promising career to work in seclusion in St. Petersburg. Although he appears occasionally, most recently for lectures at the Massachusetts Institute of Technology and several other US schools last spring, he keeps a very low profile.

Even in mathematical circles, surprisingly little is known about him, and those who know him often don't want to speak publicly about his work.

At any rate, he seems to have used his time alone wisely. While working out the Poincare Conjecture, Perelman also seems to have established a much stronger result, one that could change many branches of mathematics. Called the "Geometrization Conjecture," it is a far-reaching claim that joins topology and geometry, by stating that all space-like structures can be divided into parts, each of which can be described by one of three kinds of simple geometric models. Like a similar result for surfaces proved a century ago, this would have profound consequences in almost all areas of mathematics.

As the foundation for his proof, Perelman used a method called Ricci flow, invented in the mid-1980s by Columbia University mathematician Richard Hamilton, which breaks a surface into parts and smooths these parts out, making them easier to understand and classify.

Although some mathematicians find it disturbing that Poincare's simple question could have such a complicated answer, Hamilton is not worried. After so many failed proofs, he said, "no one expected it to be easy."

Hamilton calls Perelman's work original and powerful - and is now running a seminar at Columbia devoted to checking Perelman's proof in all its detail.

If the proof is vetted, the Clay Mathematics Institute may face a difficult choice. Its rules state that any solution must be published two years before being considered for the $1 million prize. Perelman's work remains unpublished and he appears indifferent to the money. Hamilton, on the other hand, did the foundational work on which the proof is based - but that was over a decade ago. And, as with any major finding, many people have contributed in some degree.

Huge financial prizes raise the stakes for assigning credit for major proofs like this one. For the time being, however, researchers are sharing their approaches with a sense of openness. And the mood is one of cautious optimism that Perelman's approach, even if flawed, will eventually be the one that works.

It takes years for a solution to make the leap from being just another claim to actually being considered "true." Perelman's work will be digested by a wide range of mathematicians in the next few years, said University of California at Davis mathematician Joel Hass. Steps that Perelman pushed through by brute force will be replaced with simpler methods, and his work will be integrated into other fields, Hass said.

And while the equivalent of the Poincare conjecture has already been proven for dimensions four and up, no one yet has any idea how to classify all the spaces that appear in higher dimensions. This state of ignorance is what prods mathematicians to keep working.

"It's interesting how a really good problem can sometimes be much better than a really good answer," Rubinstein said with a grin.