March 22: The 4-(23,7,1) Steiner system D_{23}, and a bit about
the automorphism groups of D_{22} and D_{23}

Back to building the 5-(24,8,1) design via it's repeatedly derived
designs with parameters 4-(23,7,1), 3-(22,6,1), 4-(21,5,1).
The last of these is a Pi_4, which we already know is unique.
Last time we've narrowed down the 3-(22,6,1) to one choice,
but didn't yet show that it works (except indirectly since
we've already constructed a 3-(22,6,1) in a homework exercise
via the 2-(11,5,2) Paley biplane).

To that end (and because we won't have the indirect method available
for the 23- and 24-point designs), we argue as follows.  Fix any
three points.  We claim they're in a unique block.  If one of the three
is \infty_1, the other two lie on a unique line and we're done.
If not, but they're collinear, we're still done (they can't be on a
hyperoval because no hyperoval meets a line is as many as three points).
Finally, if three non-collinear points, put them at the three unit
vectors, and then exactly one of the three hyperovals through them works.
Indeed if O is any oval then diag(1,1,a) and diag(1,1,b) takes O to
some O', O" in the other two equivalence classes, so exactly one of
O, O', O" is in the class we chose.  So there exists a 3-(22,6,1) design
D_{22}, as desired.  Moreover it is unique up to isomorphism, and indeed
for any 3-(22,6,1) design D' and any point of D' we may choose
an isomorphism D' --> D_{22} taking that point to \infty_1.
We shall see next time that by taking D' = D_{22} we can conclude
that Aut(D_{22}) is 3-transitive on points (and thus transitive
on blocks).


The next step is 4-(23,7,1).  We extend the intersection triangle from
the 3-(22,6,1) to get

              253
            176  77 
          120  56  21
        80   40  16   5
      52   28  12   4   1
    32   20   8   4   0   1
  16   16   4   4   0   0   1
 0   16   0   4   0   0   0   1

So in a 4-(23,7,1) design any two blocks meet in an _odd_ number
of points (whereas in the 3-(22,6,1) the intersection was even,
as we'll see happens also for the 5-(24,8,1) ).  Fix two points
\infty_1, \infty_2.  [That's the text's notation on page 22-23;
I've also seen I, II (and III for the 5-(24,8,1)), which is
probably better because we already have "points at infinity" in Pi_4.]
The doubly derived design is Pi_4, and we've already accounted for
each of the singly derived designs last time.  This tells us that
the 253 blocks include

  21: \infty_1 + \infty_2 + line
  56: \infty_1 + hyperoval in one equivalence class
  56: \infty_2 + hyperoval in another equivalence class

That leaves 120, which must be 7-element subsets B of the points of Pi_4
that meet each line, and each of the 56+56 hyperovals already used,
in an odd number of points.

We already outlined Monday (though it wasn't in the notes)
what such B must be.  Fix a point p in B.  Then each of the
5 lines through p meets B in 0, 2, or 4 other points.
4 is not possible: then B is a line plus two other points q,r
and a line through q but not r (or vice versa) meets B in exactly
2 points.  This can be done also using the "variance trick":
n1 + n3 + n5 = 21,  n1 + 3*n3 + 5*n5 = 7*5 = 35,  and
3*2*n3 + 5*4*n5 = 7*6 = 42 yields (n1,n3,n5) = (14,7,0).
Either way case, we find that each p is on three lines 
that go through two other points of B, and any two points of B
determine a unique such line.  That is, B is a 2-(7,3,1) design,
hence a copy of Pi_2 in Pi_4.  This is called a _Baer subplane_
(so the name B for such a Block is doubly apposite).  Conversely,
any Baer subplane satisfies our condition that every line meet it
in one or three points.  If it's at least two then they determine
a line of B, so exactly 3.  To exclude the possibility of 0
we can either count 7+14 lines through B, or argue by linear algebra:
F_4^3 is a 6-dimensional vector space over F_2; an F_4 line ax+by+cz=0
comes from a 4-dimensional subspace over F_2, and B comes from a
3-dimensional subspace -- and 3+4>6, so there's a nontrivial intersection.

Since the finite field F_4 contains F_2, there's an obvious Pi_2 in Pi_4:
the points (x:y:z) with F_2 coordinates (more properly, whose coordinates
can all be made to lie in F_2 after a suitable F_4^* scaling).
I claim that every Baer subplane is equivalent to this one under some
choice of coordinates -- i.e. under the subgroup PGL_3(F_4) of Aut(Pi_4).
Indeed let {p,q,r,s} be one of the hyperovals of B.  We have seen that
for any field k the group PGL_3(k) acts transitively on 4-tuples of
points in general linear positions on P^2, and there's a unique choice of
coordinates that puts the 4-tuple at ( (1:0:0), (0:1:0), (0:0:1), (1:1:1) ).
Then B must also contain the intersections of lines pq and rs, pr and qs,
and ps and qr.  The first two of these are z=0 and x=y, i.e. (1:1:0);
likewise the others are (1:0:1) and (0:1:1), and there's our copy of Pi_2
in Pi_4.

(Digression: we can try this construction over any field k; it works iff
the last three points are collinear, i.e. iff the determinant

  | 0 1 1 |
  | 1 0 1 |
  | 1 1 0 |

vanishes.  But this determinant is 2 -- we don't even need our formula
[Lemma 1.12 on p.4] for det(xI=yJ) here... -- so this always works if 0=2
in k, and always fails otherwise.  This can be interpreted classically
in terms of Ceva's and Menelaus's theorem: the ratio product must be both
1 and -1.  BTW: 1) Ceva's theorem was anticipated several centuries
earlier by "Yusuf Al-Mu'taman ibn Hud, an 11th-century king of Zaragoza"
according to the Wikipage for Ceva's Theorem (if the URL
<http://en.wikipedia.org/wiki/Ceva's_theorem> fails, replace the ' by %27);
2) the wikipage <http://en.wikipedia.org/wiki/Menelaus_theorem> for
Menelaus's theorem is the first time I've heard of this "long-running
joke amongst mathematicians" involving the Ceva and Menelaus theorems.)

So how many Baer subplanes are there?  PGL_3(F_4) acts transitively,
and the stabilizer is PGL_3(F_2), so the count is the ratio of the
two groups' orders, which is (63*60*48/3) / 168 = 360.  [Or if you prefer,
there are 21*20*12*9 choices for p,q,r,s, and each B is obtained from
168 of them -- but that's basically the same argument.]  We need to
use 120 of them, which is exactly 1/3.  It works almost exactly as for
the hyperovals, except a bit more easily.

We just saw that for any two Baer subplanes B, B' there's
g0 in PGL_3(F_4) taking B to B' -- this time we didn't have to go
through the twice-as-large group Aut(Pi_4).  Any other such g is g0 h
with h(B)=B, i.e. h in Aut(Pi_2) = GL_3(F_2).  This last "=" hides
something that we next make explicit.  As with hyperovals,
any combinatorial automorphism of B extends to Aut(Pi_4); here
the extension is not unique, but there are two choices and exactly
one is in PGL_3(F_4).   To see this, consider the maps:

  Stabilizer in Aut(Pi_4) of B --> Aut(Pi_2)
  Stabilizer in PGL_3(F_4) of B --> Aut(Pi_2)

both maps are is surjective.  The kernel of the second is {id}.
by applying the four-points-in-general-position lemma to PGL_3(F_4)
rather than GL_3(F_2).  So the second map is an isomorphism.
The kernel of the first map is either {id} or a 2-element group,
and we see it's the latter because it contains the field involution.

Now I claim that  det(g) = det(g0 h).  That is, I claim that
the restriction of det to

   det: Stabilizer in PGL_3(F_4) of B --> F_4^*

is trivial.  We could show this by proving that the stabilizer,
a 168-element group, is simple.  But it's even, um, simpler to note
that with our choice of coordinates every element of the stabilizer
manifestly has determinant 1 because it has a representative in PGL_3(F_2).

So we can define an equivalence relation:  B ~ B'  <==>  det(g) = 1
and this splits the 360 Baer subplanes into 3 equivalence classes
of 120 each.  Again there is a combinatorial description: B ~ B'
iff  |B intersect B'|  is odd.  (Note that this holds even if B = B',
as for the O equivalence relation.)

Finally, how do hyperovals and subplanes interact, i.e. intersect?
We want to use one B class and two O classes such that each B and O
have odd intersection.  So, we have to extend ~ to an equivalence
relation that can mix hyperovals and subplanes in such a way that
each B class corresponds to a unique O class which consists of
the hyperovals that meet B in an even number of points.  Our
standard O containing (1:0:0), (0:1:0), (0:0:1), (1:1:1) meets
our standard B in those four points and no others; its images under 
diag(1,1,a) and diag(1,1,b) meet that B in only three points
(the unit vectors but not (1:1:1)).  So we declare that
g (standard O) ~ g' (standard B)  iff det(g) = det(g').
This does not depend on the choice of g and g', and you'll check
that it does what we want: |B intersect O| is even iff B ~ O.

This completes our census of blocks of a 4-(23,7,1) design:

  21: \infty_1 + \infty_2 + line
  56: \infty_1 + hyperoval in one equivalence class
  56: \infty_2 + hyperoval in another equivalence class
 120: Baer subplane in the third equivalence class

There are six choices; each is stable under PSL_3(F_4), and
they're permuted transitively by PGL_3(F_4) and switching
\infty_1 <--> \infty_2, so all are equivlent.

It remains to check that this works.  This time we don't have
the shortcut of having constructed a 4-(23,7,1) [or 5-(24,8,1)]
design some other way.  But it's not hard.  Given four points:

@ If two of them are \infty_1 and \infty_2, we must use a line,
which is the unique line through the other 2.

@ If one of them is (say) \infty_2 and the other isn't, use
the above argument for verifying the 3-(22,6,1) design.

@ If all four are in \Pi_4, and are collinear, use that line plus
\infty_1 and \infty_2.  There is no other choice because neither
a hyperoval nor a subplane can meet a line in four points.

@ If no three are on a line, they are equivalent to our four
standard points.  Those are contained in a unique subplane B
and a unique hyperoval O with B~O.  Hence exactly one of B and O
is available.

@ Finally, if three are on a line l but the fourth isn't,
we must use a subplane (lines can't work and a hyperoval meets l
in at most two points).  We must show that (i) there are three subplanes
B containing our four points, (ii) one in each equivalence class.
This will give us what we need.  For (i), say our points are p,q,r,x
with r not on l.  Let l' be the x-r line.  B must contain a unique one of
the three points on l' other than r and x.  Each of those points, call it s,
together with p,q,r gives four points in general position and we already
know that these are contained in a unique B.  For (ii), any two of the
three B choices meet in at least four points, and they cannot meet in more
lest they coincide (any five points include a (unique) hyperoval, from which
we can reconstruct the subplane as above).  So they meet in exactly 4
and are thus inequivalent.  [For (ii), alternatively -- and more honestly,
since this had to be done in the course of proving the properties of our
equivalence relation -- we may choose coordinates so that p,q,r,x
are at (1:0:0), (0:1:0), (0:0:1), (1:1:0).  Then one of the three B's
is our standard one, and the others are its images under diag(1,1,a)
and diag(1,1,b), which are inequivalent.  Yes, this gives you part of
Exercise 2 of the current problem set.  It also proves that the
construction actually yields a 4-(23,7,1) design using only the
determinant definition of the equivalent classes, without having
to verify that it is equivlent to the combinatorial one using
the parity of intersections.]

In conclusion: we have proved (again modulo Exercise 2) that
our construction gives a 4-(23,7,1) design D_{23}, and any 4-(23,7,1)
design D' is isomorphic with it -- and indeed we may choose the
isomorphism to take any ordered pair of distinct points of D' to
(\infty_1, \infty_2).  We shall see next time that by taking
D' = D_{23} we can conclude that Aut(D_{23}) is 4-transitive on points
(and thus transitive on blocks).