Contents

Let

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 weighti, we assume that a codeword of weightiexists. By considering the intersection patterns of a few selected lines with theipoints 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 weightiand .

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.

Contents