Contents
Next: The Beginning of
Up:The Search for a
Previous: Prologue
A finite projective plane of ordern, with n > 0, is a
collection of lines and points such that
- every line contains n+1 points,
- every point is on n+1 lines,
- any two distinct lines intersect at exactly one point, and
- any two distinct points lie on exactly one line.
Figure 1: The finite projective plane of order two
There are several different definitions for a finite projective plane and
this set of axioms is chosen to highlight the striking duality of lines
and points. One can interchange the words ``line'' and ``point'' in the
definition and obtain essentially the same axioms! The attractiveness
of these objects is in their simplicity and their reliance on the language
of geometry. One is tempted to start drawing lines on paper and may soon
discover some simple examples.
[an error occurred while processing this directive]
The smallest example of a finite projective plane is a triangle,
the plane of order one.
The smallest non-trivial example is of order 2, as shown in
Fig. 1. There are seven points labelled from 1 to 7. There are
also seven lines labelled L1 to L7. Six of them are straight lines but
L6 is represented by the circle through the points 2, 6, and 7. The
reader is invited to verify that the axioms of a finite projective plane
are satisfied.
[an error occurred while processing this directive]
An early reference to a finite projective plane is in the paper by Veblen
[32], which studied the axioms for geometry and used the plane
of order 2 as an example. Veblen also proved that this plane of order 2 cannot
be drawn using only straight lines. In a series of papers
[32,33,34], Veblen, Bussey and Wedderburn
established the existence of most of the planes of small orders, as well
as all four non-isomorphic planes of order 9. One of the orders missing is
n = 6.
Figure 2: Two orthogonal latin squares of order four
Figure 3: A Graeco-Latin square of Order 4
In 1938, Bose [4] explained why there is no projective plane of
order 6. He related the existence of a finite projective plane of order
n to the existence of a hyper-Graeco-Latin square. The term
``Graeco-Latin square'' originated with Euler in 1782. In our modern
terminology, they are called orthogonal Latin squares. Let us define
them.
Figure 4: A Latin square orthogonal to those in Fig. 2
A Latin square of order n is an matrix satisfying the
following properties:
- all the entries are integers between 1 and n,
- in every row, no entry is repeated, and
- in every column, no entry is repeated.
Let and denote two Latin
squares of order n. They are said to be orthogonal provided that
the 2-samples for
are distinct. A simple way to visualize the definition is to put the
second square, slightly shifted, on top of the first square. The resulting
n by n array of 2-samples has no repeated entries, and is often
referred to as a Graeco-Latin square or an Euler square.
[an error occurred while processing this directive]
Figure 2 contains two examples of Latin squares of order 4.
They are orthogonal and the resulting Graeco-Latin square is shown in
Fig. 3. Is there a third Latin square orthogonal to both
the squares in Fig. 2? Yes, there is one, as shown in
Fig. 4. Can one find a fourth? The answer is no. One can
easily prove the following theorem [26, p. 80,].
If equality holds in (1), then the orthogonal set
is said to be complete. Finally, we are ready to state Bose's result
[26, p. 92,].
Why does Bose's result explain the non-existence of a projective plane of
order 6? It states that such a plane exists if and only if there exists a
complete set of 5 mutually orthogonal Latin squares of order 6. The
possible existence of even a pair of orthogonal Latin squares of order 6
was a much older problem.
In a 1782 paper [12], Euler started by stating the
problem of the 36 officers. This problem asks for an arrangement of 36
officers of 6 ranks and from 6 regiments in a square formation of size 6
by 6. Each vertical and each horizontal line of this formation is to
contain one and only one officer of each rank and one and only one officer
from each regiment. Euler denoted the 6 regiments by the Latin letters
a,b,c,d,e,f and the 6 ranks by the Greek letters . He further remarked that the characteristic of
an officer was determined by the two letters, one Latin and the other
Greek, and that the problem consists of arranging the 36 combinations of
two letters in a square in such manner that every row and every column
contains the six Latin as well as the six Greek letters. This was the
origin of the term ``Graeco-Latin square''. Euler observed that the first
step was to arrange the Latin letters in a square so that no letter was
missing either from any row or from any column. He called this square a
Latin square. If he had chosen to arrange the Greek letters instead, then
we would probably have Graeco squares rather than Latin squares. In any
case, if we label both the ranks and the regiments from 1 through 6, then
Euler's problem reduces to the construction of a pair of orthogonal Latin
squares of order 6.
[an error occurred while processing this directive]
Euler found no solution to this particular problem.
He then conjectured that no solution exists if
the order of the square is of the form . This is
the famous Euler's conjecture. The first case n = 2 is trivially
impossible. Tarry around 1900 [27] verified by a systematic
enumeration that Euler's conjecture holds for n = 6. Since there does
not exist even a pair of orthogonal Latin squares, Bose's result implies
the non-existence of a projective plane of order 6.
[an error occurred while processing this directive]
Yet, there is something unpleasant about a systematic hand enumeration: it
is messy and it is error prone. Mathematicians did find a better
explanation in the celebrated Bruck-Ryser theorem [7], which
was published in 1949.
Since and it is not a sum of two integer
squares, the Bruck-Ryser theorem implies the non-existence of a projective
plane of order 6. How did they prove the theorem? We will not repeat it
here, but one of the crucial steps involved the use of an incidence
matrix.
Figure 5: An incidence matrix for the plane of order two
The incidence matrix of a projective plane of order
n is an by matrix where the columns represent the
points and the rows represent the lines. The entry is 1 if point
j is on line i; otherwise, it is 0. For example,
Fig. 5 gives the incidence matrix for the projective
plane of order 2. In terms of an incidence matrix, the properties of being
a projective plane are translated into:
- A has constant row sum n+1,
- A has constant column sum n+1,
- the inner product of any two distinct rows of A is 1, and
- the inner product of any two distinct columns of A is 1.
The conditions on row sums and row inner products
can be encapsuled in the following matrix equation:
where denotes the transpose of the matrix A, I denotes the
identity matrix, and J the matrix of all 1's. Every diagonal entry on
the right hand side of Eq. (2) is n+1, which implies that
the inner product of any row of A with itself is n+1 or, equivalently,
its row sum is n+1. Every off-diagonal entry is 1, which is the same
as requiring the inner product of any two distinct rows of A to be 1.
Ryser also proved that A is a normal matrix [25]; in other
words,
Hence, Eq. (2) also implies the conditions regarding column
sums and column inner products. The Bruck-Ryser theorem starts from this
equation and proves that it implies n is a sum of two integer squares
when .
[an error occurred while processing this directive]
It is surprising that the Bruck-Ryser theorem has a partial converse
[13].
Of course, if the matrix A is actually the incidence matrix of a
projective plane, then it must have entries which are either 0 or 1.
Although this theorem guarantees only a matrix with rational entries, it
suggests that the necessary part of the Bruck-Ryser theorem is very close
to being also sufficient.
Projective planes are special cases of a class of combinatorial objects
called symmetric block designs. We are not going to discuss
block designs, except to mention that Chowla and Ryser have generalized
the Bruck-Ryser theorem to symmetric block designs [10], which
it is now known as the Bruck-Ryser-Chowla theorem. Here again, a partial
converse exists, providing more credence to the hope that the conditions
in the Bruck-Ryser-Chowla theorem are both necessary and sufficient. This
hope is now shattered by the non-existence of the finite projective plane
of order 10.
[an error occurred while processing this directive]
Let us return to the history of projective planes. Now that we have a good
explanation of the non-existence of a plane of order 6, what is the next
unknown case? It is n = 10. Since , a plane of order 10
would exist if the necessary condition of the Bruck-Ryser theorem is also
sufficient. On the other hand, , and so, if one
believes Euler's conjecture, then it does not exist.
First, Euler's conjecture was shown to be false. In 1959, Bose and
Shrikhande [5] constructed a pair of orthogonal Latin squares of
order 22. Then Parker [23,24] constructed a pair of
orthogonal Latin squares of order 10. Together they showed that Euler's
conjecture is false for all orders greater than six [6]. This
raised the hope for the existence of a plane of order 10.
History indicated that significant advances were made when one branch of
mathematics was shown to be related to a different branch of mathematics.
It is not surprising that the beginning of the end of the plane of order
10 occurred when people started studying the binary error-correcting code
associated with it.
Contents
Next: The Beginning of
Up:The Search for a
Previous: Prologue