Contents Next: Backtrack Search using Up:The Search for a Previous: The History of

The Beginning of the End

Let A be the incidence matrix of a finite projective plane of order 10. Let V be the vector space generated by the rows of A over

the finite field with two elements {0,1}. A vector in V is called a codeword. The weight of a codeword is the number of 1's in the codeword. Let

be the number of codewords of weight i. We define the weight enumerator of V to be

In 1970, Assmus gave a talk at Oberwolfach entitled ``The projective plane of order ten?'' which discussed the properties of V. After the talk, there was a lot of anticipation about this new approach. Maybe one could derive a contradiction such as showing that one of the weights is non-integral or negative. Unfortunately, no such simple contradictions were found.

However, there were several important advances. Assmus and Mattson showed [2] that the weight enumerator is uniquely determined by , , and . Since their report is not readily available in most libraries, we shall refer to the paper of MacWilliams, Sloane, and Thompson [22], which proved many of the same results. One of the many innocuous but extremely useful results was:

For example, every line must intersect a codeword of even weight in an even number of points. This gives us an extra condition beyond what is available from the definition of a projective plane. Roughly speaking, this condition reduces the number of possibilities for each line by half. The cumulative effect of this condition is tremendous and it is the main reason that makes an exhaustive search possible.

Furthermore, MacWilliams et al. showed that after using about 3 hours of computer time on a General Electric 635. Bruen and Fisher later showed in [8], that also followed from an earlier computer result by Denniston [11]. However, the method of MacWilliams et al. illustrated how to continue attacking the problem. This can be summarised as follows:

Given any weight i, we assume that a codeword of weight i exists. By considering the intersection patterns of a few selected lines with the i points of this codeword, we arrive at a small number of starting configurations, each corresponding to a submatrix of the incidence matrix. Then, we try to complete the rest of the incidence matrix. If we succeed, then it is time to celebrate because we have constructed a plane. If none of the starting configurations can be so completed, then the plane of order 10 does not contain any codeword of weight i and .

This method requires first the generation of all the possible starting configurations. A good reference is the 1980 paper [14] by Marshall Hall, Jr., which analyzed in detail the starting configurations for codewords of small weight . Given a starting configuration, the attempt to complete it is basically a backtracking process. The term ``backtrack'' was coined by D. H. Lehmer in the 1950's, but backtrack techniques have been used to solve puzzles for a long time. It is a tedious and lengthy task, one that is best suited for a computer.

Backtrack Search using a Computer

Contents Next: Backtrack Search using Up:The Search for a Previous: The History of