# Science: The computer search for a projective plane of order 10

FOR SEVERAL decades, mathematicians have tried to answer a question

at the foundations of geometry: Is there a projective plane of order 10?

A projective plane is defined as being made up of ‘points’. Certain sets

of these points are known as ‘lines’. Mathematicians say that the plane

has order n if it contains a total of n^{2} + n + 1 points, with as many lines,

and the following four axioms hold:

1. Every line contains n + 1 points.

2. Every point lies on n + 1 lines.

3. Any two lines intersect at exactly one point.

##### Advertisement

4. Any two points lie on exactly one line.

The simplest projective plane is a ‘triangle’, of order 1. It turns

out that a projective plane of order n always exists if n is the power of

a prime number – for example, n equals 7 or 8 (which is 2^{3}). This is true

where n is less than 9, with the exception of n equals 6, and mathematicians

proved in 1938 that there is no projective plane of order 6.

With the question of the existence of a projective plane settled for

n less than 9 mathematicians have been focusing their attention on one where

n equals 10. But the question has resisted their attacks.

Now, however, three computer scientists report a negative answer to

the question (Canadian Journal of Mathematics, December 1989). C. W. H.

Lam, L. Thiel and S. Swiercz of Concordia University in Montreal had initially

announced the result a year ago. At the time, The New York Times published

an article entitled ‘Is a math proof a proof if no one can check it?’.

Lam and his colleagues in Montreal started to work on the problem in

1980. They searched for the projective plane using the CRAY-1A supercomputer

at the American Institute for Defense Analyses.

Mathematicians can represent such a plane as a square array of 0s and

1s. They call this its ‘incidence matrix’. In such an array, each row represents

a line in the plane. If the jth point lies on the ith line, then there is

a 1 in position j of row i. The search for a projective plane is, therefore,

reduced to the search for its incidence matrix.

In the case of order 10, the incidence matrix has 111 rows each of 111

digits. A mathematician, given any 111-by-111 array of 0s and 1s, can tell

simply by inspecting it whether the array is an incidence matrix. But it

is out of the question to check systematically all possible arrays, even

with the help of a supercomputer.

To achieve their proof, Lam and his colleagues borrowed some ideas from

the algebraic theory of codes. Using theoretical arguments, they reduced

the problem so that they needed only to examine 45 cases. They were able

to do this on a computer.

For each of the 45 cases, the computer started with a partial array

and attempted to complete it to form an incidence matrix. The algorithm

was called ‘backtrack search’.

Lam and his colleagues knew that if the algorithm succeeded in at least

one case, they would have found a projective plane of order 10. If it did

not, then they would know that no such plane existed.

Their CRAY-1A supercomputer took almost 3000 hours, spread over two

years. When the computer found no incidence matrix, the three researchers

concluded that there could be no projective plane of order 10.

Lam and his colleagues are quick to concede that their computer proof

is not a mathematical ‘proof’ in the traditional sense. ‘I want to emphasise

that this is only an experimental result,’ says Lam. ‘It desperately needs

an independent verification or, better still, a theoretical explanation’.