March 10: the (5,6,12) Steiner system via Aut(S_6)
(cf. Chapter 6 of the textbook; also p.27, Exercise 13)


Recall that we found in Pi_4 an oval O and a dual oval O*
permuted by S_6 in different ways, and showed that the resulting
outer automorphism of S_6 is essentially unique (i.e. unique up to
inner automorphism).  Such 6-element sets O and O* with non-conjugate
actions of S_6 are said to be "dual".  This duality gives:

@ a bijection between 15 pairs in O and 15 synthemes in O*
@ a bijection between 15 synthemes in O and 15 pairs in O*
@ a bijection between 10 even splits of O and 10 even splits of O*

The last of these is constructed as follows.  There are Bin(6,3)/2 = 10
ways to partition O into two triples.  Fix one of these, and let c and c'
be 3-cycles permuting them.  Then c and c' commute and generate a subgroup
A =~= (Z/3)^2 over S_6 (it's a 3-Sylow because 3^2 || 6!).  We saw already
that each of c and c' maps to a double 3-cycle of O*.  Since these commute
but are neither equal nor inverses of each other, those double 3-cycles
must come from the same even split of O*, say c --> c* c'*  and
c' --> c* (c'*)^(-1).  So we get a well-defined bijection as claimed.
Moreover cc' maps to c*^(-1) and c^(-1)c' maps to c'*, so if we use
the same rule starting from even splits of O* we get the same bijection
(and A goes to a subgroup conjugate to A, as it must by Sylow's theorem).

What's more, these bijections are related as follows:

@ if a pair p in O is contained in a syntheme s, then the dual syntheme p*
contains the dual pair s*.  Proof: p and s commute as elements of order 2
of S_6, and that's the only way two elements in their conjugacy classes
to commute.  [NB The three pairs in a given syntheme constitute a maximal
_co_clique in the triangular graph T(6); on the syntheme graph the
corresponding coclique is the three synthemes containing a given pair.]

@ an even split {c,c'} splits each pair in a syntheme s* iff its dual
{c*,c'*} does _not_ split the pair dual to s.  Proof: that's the only way
a triple or simple transposition can commute with a nontrivial element of
the 3-Sylow group A.


We can use this to obtain:

Theorem (6.7, page 87-88, extended)

There exists a unique 5-(12,6,1) design up to isomorphism.
The automorphism group M_12 is "simply 5-transitive":
for every pairwise distinct x_i (i=1,...,5) and pairwise distinct
y_i (i=1,2,3,4,5) there exists a unique automorphism taking each
x_i to y_i.  In particular |M_12| = 12*11*10*9*8 = 95040.

Proof: Let D be such a design.  It has  Bin(12,5)/Bin(6,5) = 132
blocks, and the intersection triangle for the six points of a block is

                  132
                66    66
             30    36    30
          12    18    18    12
        4     8    10     8     4
     1     3     5     5     3     1
  1     0     3     2     3     0     1

(this is page 87, Table 6.1 but with a typo corrected: the text has
2,3,2 instead of 3,2,3 in the bottom row).  In particular the complement
of a block is again a block.  This suggests the following construction.
Fix a block B with complement B@.  Choose an isomorphism between the
symmetric groups of B and B@ that realizes the outer automorphism
(i.e. choose a bijection between B@ and the totals of B).  The design
then consists of the following blocks B', ordered according to the
size of their intersection with B:

(6) B' = B itself.

(4) For any four-element subset S of B, the union of S and any of the
 3 pairs in the syntheme of B@ associated to the complement of S

(3) For any three-element subset S of B, the union of S with either of
 the two parts of the even split of B@ corresponding the even split of B
 that contains S

(2) For any two-element subset S of B, the union of S with the
 complement in B@ of one of the three pairs of the associated syntheme

(0) B' = B@.

This gives 1 + 3*15 + 2*20 + 3*15 + 1 = 132 blocks B' as needed (and
of course consistent with the bottom row of the intersection triangle).
The fact that this is actually a (5,6,12) Steiner system -- that is,
that any 5-element set P is contained in a unique block B' -- can be
recovered from our above description of the duality of pairs, synthemes,
and "even splits"; the only tricky case is when the intersection of P
with B has size 2 or 3, and we can cut down on the case analysis
a bit by proving that every P is contained in at least one B', and then
double-count pairs (P,B'): the count is at least #P = Bin(12,5),
but also equal to Bin(6,5) * #B' = 132*Bin(6,5), but that equals
Bin(12,5), so each P must be in a unique B'.  (Likewise it is enough
to prove each P is contained in _at most_ one B'.)

Now suppose we have any (5,6,12) Steiner system D1.  Fix a block B1
of the design and a bijection of that design with B.  This can be done
in 132*6! = 12*11*10*9*8 ways.  We claim that this extends to a unique
isomorphism of Steiner systems.  We shall repeatedly use the following
fact: any 4-element subset T of the points of a (5,6,12) Steiner system
is contained in four blocks, each the union of T with a pair, and
these pairs partition the 12-4=8 points in the complement of T.
(Because for each point outside T, that point together with T
makes 5, which are contained in a unique block.)

First let T be one of the 15 four-element subsets of B1, i.e. the
complement of a pair P.  The blocks containing T are B1 itself and
three others which partition B1@.  This gives a map

  f: pairs in B1 --> synthemes in B1@

which takes P to the syntheme determined by the complement of P in B1.

Taking complements, it follows that for each pair P the three blocks
that intersect S1 in P are obtained from the union of P with B1@
by removing one of the pairs in f(P).

If pairs P,P' overlap in a point then f(P) and f(P') are disjoint:
if f(P) and f(P') share a pair then its complement in B1@, together with
the three points of B not in P or P', are five points contained in
two blocks.

Next let T consist of three points in B1 and one in B1@.  The resulting
partition must pair each of the remaining points of B1 with a point in B1@:
if two points in B1 were paired then they together with T would be a block
that meets B1 in exactly 5 points.

Now the intersection triangle tells us that for any 3-element subset
S1 of B1 there are exactly 2 blocks that intersect B1 in S1.  I claim
that they do not intersect in B1@.  Indeed if they did then they would
meet in one point, and letting T be that one point union S1 we get
a contradiction.  So, S1 determines an even split of B1@.  Take the
complements of those two blocks (which are also blocks of the design)
we see that the complement of S1 in B1 determines the same even split.
So we get a well-defined bijection

  g: even splits in B1 <--> even splits in B1@ .

Moreover, E is the even split containing S1, and S1 contains pair P,
then each pair in the syntheme f(P) is split by g(E).  Proof: else
two of the pairs in f(P) contain one of the parts E' of the even split
g(E), and their union with P is a block that meets the block {E union E'}
in exactly five points.

We deduce that f is a bijection.  Say that an even split E is "neighbor" of
a pair iff the pair contained in one of the parts of E, and is a "neighbor"
of a syntheme iff it corresponds to *none* of the syntheme's component pairs.
Then E is a neighbor of pairs and 4 synthemes.  Exercise: these 15+15 = 30
neighborhoods constitute a (3,4,10) Steiner system.  In particular (and this
is much easier, and all we'll need): different pairs have different
neighborhoods.  But we saw in effect that g maps the neighborhood of P
to a neighborhood of f(P).  Since g is a bijection, it follows that
f is a bijection as well.  (Whew.)

Thus f is an isomorphism from the triangular graph T(6) of pairs in B1
to the syntheme group of B1@.  We saw alreay that such an isomorphism
is tantamount to an identification of B1@ with the totals of B1.
(A point p in B1 goes to the total consisting of all synthemes f(P)
for P containing the point.)  That identification identifies B1@ with
B@, the complement of B in the (5,6,12) Steiner system we designed previously.
Using the properties of f and g that we've developed we now quickly confirm
that this bijection from B1@ to B@, together with the given bijection from
B1 to B, yield an isomorphism from D1 to our known D and that this
isomorphism is unique.

As noted alreay, this means there are 132*6! isomorphisms.  Moreover,
any bijection from a 5-point set F1 in D1 to 5-point set F in D
extends uniquely to a bijection from the unique block containing F1
to the unique block containing F, and thus to a unique isomorphism from
D1 to D.  In particular, taking D1=D we see that Aut(D) is simply
5-transitive, QED.

It also follows that, given D and B, we can recover Aut(S_6) as
the index-66 subgroup of Aut(D) as the group of automorphisms that fix
the decomposition of the 12 points into B and B@.  This may seem
circular, but there are other constructions of D (e.g. from the
affine plane over the 3-element field, or a Hadamard matrix of order 12,
or the projective line over the 11-element field), and each of those
can give us an alternative route to Aut(S_6).