Search yields math proof no one can check.

Search yields math proof no one can check

"Don't touch this problem. It's too difficult. You may not get anywhere, and you may never graduate." That was the advice Clement Lam received nearly 20 years ago when he was a graduate student. Lam heeded his adviser's warning but eventually came back to the problem -- one of the most famous unanswered questions in an area of mathematics known as combinatorics. Earlier this month, Lam and a team of computer scientists at Concordia University in Montreal completed an eleborate, extensive computer search that finally settled the question.

Like many notoriously difficult mathematical problems, this one is relatively easy to state. Imagine a square table consisting of 111 columns and 111 rows. The aim is to fill 11 of the spaces in each row so that all columns also have exactly 11 spaces filled. In addition, for any pair of rows selected, both rows must each have only one filled space that falls in the same column. It's the second condition that makes the problem particularly difficult.

Such a completed table, in which filled spaces can be represented by ones and empty spaces by zeros, is one way of expressing what is known as a "finite projective plane." This particular example, if it exists, would have the designation "order 10." Lam's exhaustive computer search established that no "finite projective planes of order 10" exist. In other words, no combination of ones and zeros satisfies the rules for such a plane.

The search for finite projectivbe planes of a particular order spans a long history. Mathematicians know that such planes, or equivalent tables, are simple to construct when the order is a prime number, such as 2, 3, 5 and so on, or a power of a prime, such as 4, 9 or 27. Although mathematicians have conjectured that these are the only possibilities, no one is certain they are. Consequently, mathematicians have been interested in orders such as 10 and 12 to see if they can find any exceptions. However, Lam's result for order 10 fits the postulated pattern.

Lam's computer search depended on a combination of careful analysis and a clever computer program. With more than 470 trillion ways of filling in just one of the 111 rows, trying every possible combinatin was out of the question. In 1970, F.J. MacWilliams and Neil J.A. Sloane at AT&T Bell Laboratories in Murray Hill, N.J., and John G. Thompson of Cambridge University in England, applied various mathematical techniques to narrow the search to a smaller number of special cases. Lam, working with John McKay, Larry Thiel and Stanley Swiercz, used those ideas as the basis for the latest attempt to solve the problem.

Lam and McKay began the first leg of the computations in 1979, using a VAX minicomputer to run through the simpler cases. Those efforts required almost a year of computer time. Realizing the final case would take more than 100 years on their own computer, Lam and his collaborators looked for help. Computer scientists at the Institute for Defense Analyses, in Princeton, N.J., came to the rescue. They agreed to run Lam's program on a Cray supercomputer whenever the computer happened to be idle.

In the end, the search consumed several thousand hours of computer time spread over a little more than two years. "Had we to pay for [the computer time] at anything like commercial rates, we couldn't have done the work," McKay says. The bill would have come to millions of dollars.

Whether mathematicians now regard the order-10 question as settled depends on how comfortable they are with the notion of such a large, complex computer-based proof. "It isn't a proof than anyone can check easily," says Bell Labs mathematician Ronald L. Graham.

Even trying to verify the proof on another computer seems impractical. Several people had a hand in writing the original computer programs. The computations were done in bits and pieces over a number of years and rquired large amounts of computer time. Moreover, computers aren't infallible. Cosmic rays or a flaw in a computer's operating system can easily change a calculation.

"There is always the possibility of error," Lam says. "But I'm happy and satisfied with the result. The way I look at it is that when I am using the computer in this way, I am not really doing a mathematical proof. You can say the whole [computer] program is the proof, but I would look at it more like an experimental result."

Last month, Lam and a student finished their search for all possible projective planes of order 9 -- a simpler case. Mathematicians had already found four different patterns satisfying the rules for order 9. Lam's search found the four patterns and established there are no others. That kind of outcome helps build confidence in the result for order 10.

The computer techniques and algorithms that Lam and his team developed for solving the order-10 problem are likely to be useful in a wide variety of problems in combinatorics. Such problems come up frequently in the design of switches for fiber-optic networks, in which lines must be connected in just the right ways. "We're sharpening the tools now," Lam says.