March 5: more about the outer automorphism of S_6,
and Aut(S_n) in general  (cf. Chapter 6 of the textbook)

Last time we constructed a total by starting from two disjoint
synthemes, finding the four disjoint from both of them, and
showing that one is a dead end while the other three are pairwise
disjoint and thus complete the total.  Does that ring a bell?
We have 15 synthemes, each disjoint from 8 others; form the
relevant regular graph with n=15 and k=8, and then in effect
we're looking to extend an edge to form a maximal clique of 5,
succeeding provided we avoid a wrong turn at the beginning.
That's just what happened with cliques of maximal size m-1
on the triangular graphs T(m) for m>4; here m=6, and indeed
15 and 8 are the correct parameters.  Check: the syntheme graph
is indeed strongly regular with the same parameters (15,8,4,4).
In fact it's isomorphic with T(6), and we can use this isomorphism
to explain or construct an outer automorphism of S_6 if we identify
pairs (the vertices of T(6)) with simple transpositions and
synthemes (the vertices of the syntheme graph) with triple transpositions.
Indeed it's somewhat surprising that our text doesn't make this connection
(see Chapter 6 for its development of Aut(S_n) and the hyperoval picture).
We give this approach today -- it's basically a standard approach
but "T(m)" and "cliques" provide a convenient link with something
we've thought about already.


What lets us connect these graphs with the structure of G is that
the 15 simple transpositions constitute a conjugacy class in S_6,
and the triple transpositions constitute another one.  Recall:
Elements x and y of a group G are said to be _conjugate_ 
iff there exists g in G such that  y = g^{-1} x g;  this is an
equivalence relation (why?), and the equivalence classes are called
_conjugacy classes_.  Any automorphism of a group must permute
the conjugacy classes -- and if a class is finite (as it must be
in a finite group) then its image must be a conjugacy class of
the same size.

Now in a symmetric group S_n we have

  conjugacy class <==> cycle structure <==> partition of n.

For example, 6 has 11 partitions; here they are, each together with
the parity and size of its conjugacy class:

*   1   111111
   15   21111
*  45   2211
   15   222
*  40   3111
  120   321
*  40   33
   90   411
*  90   42
* 144   51
  120   6

Stars mark even classes.  For example, the number of 6-cycles g is 5!:
they are in bijection with permutations ( g(1), g^2(1), ..., g^5(1) )
of {2,3,4,5,6}.  We'll soon explain how to get such counts for S_n
in general; for now we check our arithmetic by verifying that
the counts add up to #(S_6) = 6! = 720, with the even and odd classes
each adding up to half the total, e.g. 15+15+120+90+120 = (30+90)+120+120
= 360 as it should be.  Last time we saw that our outer automorphism takes
cycle structure 3111 to 33; it is comforting that these classes have the
same size, 40.  We note three further such coincidences: we've already seen
the count 15 for both 21111 and 222, and there's also 120 for both 321 and 6
and 90 for both 411 and 42.  These all look like candidates for switching:
they have not just the same size but also the same exponent, respectively
2, 6, and 4.  We next show that the outer automorphism switches
21111 <==> 222 and 321 <==> 6 but leaves 411 and 42 alone.

The first of these we already expect: our isomorphism Pi ==> Pi*
extending a bijection O ==> O* takes secants (<==> pairs in O, also
lines outside O*) to syntheme points (points outside O).  To prove it,
note that for any 3-cycle c there's a simple transposition commuting with it
(switch any two of the three fixed points); so an outer automorphism takes
a simple transposition to an involution that commutes with a double 3-cycle,
which a simple transposition can't do (check this).  So it must go to a
triple transposition as claimed.  (Can you find a double 3-cycle that
commutes with a triple transposition?)

Similarly c commutes with a 321 permutation g (namely the product of c with
the simple transposition from the previous paragraph) but a double 3-cycle
c' cannot (e.g. if p is the unique fixed point of g then c' moves p, so
the conjugate of g by c' doesn't fix the same p).  So the conjugacy class
[g] must go to the 6-cycles as claimed.

Finally, since a 411 permutation is odd it is the product of an odd number
of simple transpositions (three suffice), so its image under an outer
automorphism is an odd product of triple transpositions.  But that's still
an odd permutation, so it cannot have cycle structure 42, QED.


So now what about S_n in general?  For a partition (or cycle structure) with
a1 1's, a2 2's, a3 3's, etc., the conjugacy class has size

(#)   n! / (a1! * a2! 2^a2 * a3! 3^a3 * ... )

(of course the product is finite because for k>n the k-th factor is
0! k^0 = 1).  This can be proved by generalizing either of our two
arguments last time for the special case that a2 = n/2 (and all other
a's vanish).  Fortunately we don't have to prove that for n>6 there are
no coincidences: it's enough to work with the simple transpositions.
Indeed we know that these generate S_n (any permutation can be obtained --
or if you prefer undone -- by a sequence of pairwise switches), so an
automorphism of S_n is determined by its action on simple transpositions.
For future reference we observe that S_n is even generated by the n-1 simple
transpositions (12), (13), (14), ... (1n): reduce to the previous claim
by writing an arbitrary simple transposition (ij) as (1i)(1j)(1i).

In turn we have a bijection from the simple transpositions to the vertices
of T(n).  I claim that any automorphism that takes this conjugacy class to
itself yields an _automorphism_ of T(n), i.e. it takes edges to edges.
This follows from the observation that two simple transpositions
do *not* commute if and only if they overlap on exactly 1 letter --
that is, iff the corresponding vertices of T(n) are adjacent.

  Digression:

  i) in general the product of two simple transpositions has order
   1 if they coincide, 2 if they commute, and 3 if not; in group-theory lingo
   this is sometimes expressed by saying that the simple transpositions form
   a "conjugacy class of 3-transpositions" -- quite a few of the groups
   in the ATLAS have such a description.

  ii) the syntheme graph has a similar description, because two triple
   transpositions don't commute iff they have *no* pair in common.
   (If there's a common pair we're basically in the 4-element
   normal subgroup of S_4 consisting of the identity and the three
   double transpositions.)  Here too we see that these 15 involutions
   as 3-transpositions -- which is what we expect since this conjugacy
   class is equivalent with the simple transpositions under Aut(S_6).

Back to T(n): an automorphism of T(n) must permute its maximal cliques.
But for n>4 there are exactly n of them, and each vertex is contained
in exactly 2.  This gives us a homomorphism from Aut(T(n)) to S_n
and shows that the kernel is trivial (if we know where each maximal clique
goes then we can identify each vertex by intersecting the two cliques
it is in).  Since the map is clearly surjective, we deduce that
Aut(T(n)) = S_n for n>4.  We already saw that for n=4 there are twice as
many maximal cliques and indeed Aut(T(4)) is twice as large as S_4;
for T(3) it is easy to see Aut(T(3))=S_3, while Aut(T(2)) and Aut(T(1))
are clearly trivial.

So far we have:

Proposition: an automorphism of S_n takes the conjugacy class of
simple transpositions to itself if and only if it is inner.

Proof: given the automorphism f, it is enough to find an inner automorphism
that agrees with f on the simple transpositions.  If n is not 4, use the
image in S_n of the automorphism of T(m).  If n=4, the construction still
works because f cannot induce an automorphism of T(4) that switches the
two kinds of maximal clique: one gives three elements of S_4 that generate
all of S_4, the other generate only a subgroup S_3.  This completes the proof.

In particular for S_6 every automorphism is either inner or our one
outer automorphism followed by an inner one; so Aut(S_6) contains S_6
as a subgroup of index 2.

Theorem: For n other than 6, every automorphism of S_n is inner.

Proof sketch: For n=1 and n=2 the automorphism group is trivial.
For n=3,4,5 there is no other conjugacy class whose size is
the same as that of the simple transpositions.  For n>6
the same is true because the class of simple transpositions
is the smallest non-identity class, as one can check from the
formula (#) for the size of an arbitrary conjugacy class in S_n:
it's almost clear that for large n the size of any other class
grows at least as n^3, which does it for sufficiently large n,
and a bit of routine but unedifying work turns "sufficiently large"
into "at least 7".