# Number proofs done by computer might err

January 12, 2007 12:00 AMIf I have $15 and you have $20, and we keep tossing a coin so that you win $1 from me if it turns up heads and I win $1 from you if it lands tails, you have a reasonable chance of eventually bankrupting me and walking away with the whole $35. But your prospects are not so overwhelmingly great that I refuse to play. In fact, your probability of winning it all equals your $20 divided by the sum of our stakes ($35), or just 57 percent.

The "gambler's ruin" problem has entranced mathematicians since the 1800s, and at this week's annual meetings of the American Mathematical Society and the Mathematical Association of America in New Orleans it played another role: "as a case study in the limits of proof and of machine proofs," says mathematician Doron Zeilberger of Rutgers University. Mathematicians, to their dismay, are the first scientists to face the shattering and humbling prospect that the complexities of nature may be beyond the reach of the human mind.

In the coin-toss game, with patience and a calculator, you can figure out not only each gambler's chance of cleaning up but also how long the game will likely take and the probability that it will eventually end. (That probability is 100 percent, no matter how unequal the initial stakes.) Other questions, however, "are beyond the scope of mere humans," says Prof. Zeilberger. How the game will play out if we use a loaded coin, for instance, requires a computer.

No one blinks an eye when computers do tedious calculations like this, especially when speed counts. Imagine having only an abacus, pencil and paper to calculate stock-market prices in real time.

For proofs rather than calculations, however, the growing reliance on a box of electronics to apprehend mathematical truth is freaking out some researchers. After all, Galileo said that God wrote the book of nature in the language of mathematics. "If the goal of mathematics is understanding," Brian Davies of Kings College London recently wrote in the journal Notices of the AMS, then "computer-assisted proofs do not supply it in full measure."

At the math meeting, discovery after discovery showed that there are still secrets to plumb even about plain old natural numbers -- 1, 2, 3 and the rest. Take the fact that there is an infinite number of prime numbers, those greater than 1 that can be divided only by themselves and 1. No matter how high you count, you never reach numbers so large they all have other factors. The primes go on forever.

Yet nonprime numbers are as nimble at avoiding the landmines of primes as the most adroit sapper. For instance, there are infinitely many nonprimes that can absorb any extra digit and still remain nonprime, Michael Filaseta of the University of South Carolina, Columbia, and his student Mark Kozek announced at the math meeting. That is, you can start with something like 121 and insert a 7, making 1271, and it's still not prime. It's obvious that that would work for even numbers and those ending in 5, but it also works for those ending in 1, 3, 7 and 9.

That's surprising when you remember that there are infinitely many primes, lurking in every neighborhood of the number line. You'd think that eventually nature would run out of numbers that can absorb any extra digit and still avoid becoming prime.

But as the South Carolina team proved, there are infinitely many nonprime numbers that are odd and don't end in 5, yet can withstand this abuse. They even found the smallest one: 25,011. No matter which digit you pick, 0 to 9, and no matter where you want to put it -- between the 2 and 5, the 5 and 0, whatever -- you won't get a prime number.

Prof. Filaseta and his student proved this without significant silicon help, which goes to show that humans can still discover and prove mathematical truths. But mathematicians have become increasingly vexed that some statements about numbers cannot be proved by humans. Worse, the proofs that computers do are so long and complicated that no one can say for sure that the statement being proved really is true, says Prof. Davies.

Two recent computer-aided proofs have this problem. One proved that to color any assembly of shapes, such as a map or a tiled floor, so that no adjoining shapes have the same color, you need only four colors. It's called the four-color theorem. Another proved that to pack the most spheres in a big box, arrange them like oranges in a crate with oranges in each upper layer resting on the dimple formed by four oranges beneath them. A third proof, only partially complete, will likely run to 10,000 pages if it is ever written down in full, says Prof. Davies, "and would not be comprehensible to any single individual."

No one has been able to check every line of these three proofs, as your 7th grade geometry teacher did. And the fact that a computer did them robs mathematicians of the joy of understanding how the necessary insight came about; the silicon ain't talking. There will be more and more proofs that no human mind will be able to follow. As mathematicians try to understand the language of Galileo's God, they may never be sure they have read it right.