Contents
Next: Backtrack Search using
Up:The Search for a
Previous: The History of
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.
[an error occurred while processing this directive]
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 .
[an error occurred while processing this directive]
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.
[an error occurred while processing this directive]
Contents
Next: Backtrack Search using
Up:The Search for a
Previous: The History of