Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 7 / 4

First determine when a group automorphism can carry a transposition to another type of involution. An involution in $S_n$ is a product of $k$ disjoint transpositions, and its conjugacy class has sizeAn automorphism preserves element orders and conjugacy-class sizes. Equality with the transposition-class size $n(n-1)/2$ requiresFor $k=2$ this says $(n-2)(n-3)=4$, which has no integral solution $n\ge 4$. For $k=3$, the minimum value of the left side, at $n=6$, is $4!=24=2^2\cdot 3!$; it increases strictly for larger $n$. For $k\ge 4$, even its minimum $(2k-2)!$ exceeds $2^{k-1}k!$: at $k=4$ this is $720>192$, and the ratio of these two quantities increases at the next step by $(2k)(2k-1)/(2(k+1))>1$. Thus only in degree six can the transposition class be exchanged with a different involution class, namely the triple transpositions.

We next prove that any automorphism preserving transpositions is an inner automorphism. Regard a transposition as an edge of the complete graph on the $n$ letters. Two distinct transpositions fail to commute exactly when their edges meet. Any family of pairwise intersecting edges is contained in a vertex star or a triangle: after choosing $\{a,b\}$ and $\{a,c\}$, an edge not containing $a$ must be $\{b,c\}$, which precludes any fourth edge. For $n\ge 5$, the stars are therefore distinguished as the maximal such families of size $n-1\ge 4$. An automorphism permutes stars, inducing a permutation $\pi$ of the letters; their pairwise intersections show that $(ij)$ is sent to $(\pi (i)\pi (j))$. Since transpositions generate $S_n$, this is conjugation by a permutation.

For $n=4$, stars and triangles both have three edges, but a star generates $S_4$ while a triangle generates a subgroup $S_3$. An automorphism preserves the order of the generated subgroup and hence still distinguishes stars. For $n=3$, every permutation of the three transpositions is induced by conjugation in $S_3$, since its conjugation action on them is faithful and has order six. The groups $S_1,S_2$ have trivial automorphism groups. This completes the small cases.

It follows that all automorphisms for $n\ne 6$ are inner. In degree six, an automorphism permutes the two involution classes of size 15; the kernel of this action consists precisely of the inner automorphisms. Therefore the automorphisms of the symmetric group satisfy

A duad is an unordered pair of letters, a syntheme is a partition of the six letters into three duads, and a total of synthemes is a set of five synthemes partitioning the 15 duads. There are $6!/(2^3\cdot 3!)=15$ synthemes. Fix one, $M$. Each of its three duads lies in three synthemes, and two distinct duads of $M$ can occur together only in $M$ itself. Thus precisely $1+3\cdot 2=7$ synthemes meet $M$ in a duad, leaving eight disjoint from it.

For any syntheme $M^{\prime }$ disjoint from $M$, their union as edges in $K_6$ is a six-cycle: the two perfect matchings alternate, and no two-cycle is possible in a simple graph. Its complement is a triangular prism, namely two triangles joined by three corresponding edges. The prism has four perfect matchings. One consists of all three joining edges; each of the other three consists of one joining edge and the remaining edge in each triangle. To partition the prism into three perfect matchings, one cannot use the all-joining matching, since what remains is two odd triangles. The other three do partition it. Hence two disjoint synthemes extend to a unique synthematic total.

There are eight choices for $M^{\prime }$ and four choices of $M^{\prime }$ within each synthematic total containing $M$. Thus $M$ lies in exactly two synthematic totals. Counting incidences of synthemes and synthematic totals now gives the counting synthematic totals formulaTwo distinct synthematic totals share at most one syntheme, since sharing two would force them to be the unique synthematic total extending that pair. Each syntheme gives a pair of synthematic totals containing it, and the 15 synthemes account for all $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ pairs. Therefore every pair of synthematic totals shares exactly one syntheme.

This also explains why the action on the six synthematic totals defines an automorphism of $S_6$. A permutation fixing all synthematic totals fixes their pairwise intersections, hence every syntheme. Each duad is the intersection of two distinct synthemes containing it, so every duad is then fixed. Intersecting two duads through a point shows that every point is fixed. The action is faithful and, by equality of orders, maps $S_6$ onto the full symmetric group of the synthematic totals. Part iii shows that a transposition acts as a triple transposition, establishing that this is an outer automorphism.

Relabel each duad of each synthematic total by the chosen transposition and compare the resulting synthematic total with the six labelled synthematic totals. For example, $(12)$ interchanges $T_1,T_2$, interchanges $T_3,T_4$, and interchanges $T_5,T_6$. Applying the same calculation to the other adjacent transpositions givesThese formulae use the PDF's numbering of the synthematic totals, which is essential for the particular fixed elements below. Compose permutations from left to right, consistently with the right action on synthematic totals. Multiplying the second and fourth images gives $(23)(45)$, while multiplying the third and fifth gives $(34)(56)$. Hence the two involutionsare fixed by the outer automorphism $\alpha$. Since $\alpha$ is a group automorphism, their product is fixed as well. Applying $u$ and then $v$ yieldsUnder right-to-left composition the product is the inverse cycle, which is also fixed; the displayed convention removes that ambiguity.

A Steiner system $S(5,6,12)$ consists of 12 points and a collection of six-element blocks such that every five-element subset lies in exactly one block. The blocks are often called hexads. Necessarily their number is $\left(\genfrac{}{}{0ex}{}{12}{5}\right)/\left(\genfrac{}{}{0ex}{}{6}{5}\right)=132$. We give the synthematic construction of the small Witt design explicitly and prove this defining property.

Write $X=\{1,\dots ,6\}$ and $Y=\{T_1,\dots ,T_6\}$. For an unordered pair $P=\{T_i,T_j\}\subset Y$, let $S(P)$ denote the unique syntheme shared by its two synthematic totals. A duad $D\subset X$ belongs to three synthemes. The corresponding three pairs $P$ partition $Y$: every synthematic total contains $D$ in exactly one of its synthemes, and each syntheme lies in exactly two synthematic totals. Thus the incidence $D\in S(P)$ gives a perfect matching of the six synthematic totals for each duad.

To describe the blocks with three points in each half, take an unordered partition $X=A\bigsqcup A^c$ into triples. A syntheme is cross if each of its three duads joins $A$ to $A^c$. Form a graph on $Y$ by declaring $P$ an edge exactly when $S(P)$ is cross. This graph is the union of two disjoint triangles. Indeed a synthematic total partitions the nine cross duads; every syntheme has either one or three cross duads, so if $k$ of its five synthemes are cross, then $3k+(5-k)=9$, giving $k=2$. Each vertex therefore has degree two. The stronger assertion about its components follows directly for $A=\{1,2,3\}$, when the two triangles areany other triple partition is obtained by relabelling $X$, which also permutes the synthematic totals. Denote the two components by $B,B^c$.

The complete block collection is given by the following three rules:

There are $2+15\cdot 3\cdot 2+10\cdot 4=132$ distinct blocks. The first two rules have different intersection sizes with $X$ from the third; within the third, a block determines its triple $A$ and its component. We next verify the Steiner system property, rather than relying solely on this count.

We need one further consequence of the triangle construction. The three synthemes attached to the three pairs within $B$ are pairwise disjoint, since any two belong to their common synthematic total, and together they are all nine cross duads of the complete bipartite graph between $A$ and $A^c$. Thus $B$ determines the unordered partition $A\bigsqcup A^c$ uniquely: it is the bipartition of this connected graph. There are 10 such partitions, each giving two different components, hence 20 different triples in $Y$. Since $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$, each triple in $Y$ corresponds to exactly one triple partition of $X$. The same reasoning applies to $B^c$.

Let $F$ be any five-point set and put $r=|F\cap X|$. If $r=5$, only $X$ can contain it; if $r=0$, only $Y$ can contain it, because no other block has five points in either half.

If $r=4$, set $D=X\setminus F$ and write $F\cap Y=\{T\}$. The three pairs attached to $D$ partition $Y$, so exactly one contains $T$; its block $(X\setminus D)\cup P$ is the unique block through $F$. If $r=1$, put $P=Y\setminus F$ and write $F\cap X=\{x\}$. The three duads of $S(P)$ partition $X$, so exactly one contains $x$; this gives the unique block $D\cup (Y\setminus P)$.

If $r=3$, write $A=F\cap X$ and $P=F\cap Y$. A syntheme has either one or three duads crossing $A\bigsqcup A^c$. In the one-cross case, $S(P)$ has exactly one duad $D$ internal to $A^c$, and the unique block is $(X\setminus D)\cup P$. No block with three points in each half is possible, since $P$ is then not an edge of either triangle. In the three-cross case, $P$ is an edge of exactly one triangle $B$, giving the unique block $A\cup B$; no duad of $S(P)$ is internal to $A^c$, so a block with four points in $X$ is impossible.

Finally let $r=2$, write $D=F\cap X$ and $B=F\cap Y$, and use the uniquely associated partition $X=A\bigsqcup A^c$ just proved. If $D$ crosses this partition, the three synthemes belonging to the pairs inside $B$ contain each cross duad exactly once. Thus the matching of $Y$ attached to $D$ has exactly one pair internal to $B$. It has exactly one pair $P$ internal to $B^c$ as well, since a matching must leave equal numbers of vertices in the two halves for cross pairs. The unique block containing $F$ is then $D\cup (Y\setminus P)$; $D$ is not contained in either $A$ or $A^c$, so no block of the third rule applies. If $D$ is internal to $A$ or $A^c$, none of its attached pairs lies inside $B$ or $B^c$, since the synthemes attached to these internal pairs are cross. Thus the second rule gives no block. The third rule gives exactly one, namely $A\cup B$ or $A^c\cup B$, according to which part contains $D$.

All possibilities have now been exhausted, provingThis is the small Witt design; the construction uses only duads, synthemes, their synthematic totals, and the induced action on those synthematic totals.