\( \newcommand\al{\alpha} \newcommand\be{\beta} \newcommand\de{\delta} \newcommand\De{\Delta} \newcommand\eps{\epsilon} \newcommand\ga{\gamma} \newcommand\Ga{\Gamma} \newcommand\ka{\kappa} \newcommand\la{\lambda} \newcommand\La{\Lambda} \newcommand\om{\omega} \newcommand\Om{\Omega} \newcommand\sg{\sigma} \newcommand\Sg{\Sigma} \renewcommand\th{\theta} %--- Latex uses \th for a Norse character \newcommand\Th{\Theta} \newcommand\vphi{\varphi} % % some calligraphy % \newcommand\cA{{\mathcal A}} \newcommand\cB{{\mathcal B}} \newcommand\cC{{\mathcal C}} \newcommand\cD{{\mathcal D}} \newcommand\cE{{\mathcal E}} \newcommand\cF{{\mathcal F}} \newcommand\cG{{\mathcal G}} \newcommand\cH{{\mathcal H}} \newcommand\cI{{\mathcal I}} \newcommand\cJ{{\mathcal J}} \newcommand\cK{{\mathcal K}} \newcommand\cL{{\mathcal L}} \newcommand\cM{{\mathcal M}} \newcommand\cN{{\mathcal N}} \newcommand\cO{{\mathcal O}} \newcommand\cP{{\mathcal P}} \newcommand\cQ{{\mathcal Q}} \newcommand\cR{{\mathcal R}} \newcommand\cS{{\mathcal S}} \newcommand\cT{{\mathcal T}} \newcommand\cU{{\mathcal U}} \newcommand\cV{{\mathcal V}} % % fields and rings (and a semigroup) % \newcommand\cx{{\mathbb C}}% complexes \newcommand\fld{{\mathbb F}} \newcommand\flde{{\mathbb E}} \newcommand\ints{{\mathbb Z}} \newcommand\nn{{\mathbb N}}%non-negative integers \newcommand\re{{\mathbb R}}%reals \newcommand\rats{{\mathbb Q}} % % the really useful stuff % \newcommand\comp[1]{{\mkern2mu\overline{\mkern-2mu#1}}} \newcommand\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus \newcommand\res{\mathbin{\mkern-2.0mu\restriction\mkern-2.0mu}} \newcommand\sbs{\subseteq} \newcommand\sps{\supseteq} \newcommand\seq[3]{#1_{#2},\ldots,#1_{#3}} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\im}{im} \DeclareMathOperator{\row}{row} \newcommand\pmat[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand\cprod{\mathbin{\square}} \newcommand\gbin[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} % % matrix theory % \newcommand\ip[2]{\langle#1,#2\rangle} \newcommand\one{{\bf1}} \DeclareMathOperator{\rk}{rk} \DeclareMathOperator{\tr}{tr} \DeclareMathOperator{\col}{col} \newcommand\mat[3]{\mathrm{Mat}_{#1\times #2}(#3)} \newcommand\sm[3]{\sum_{#1=#2}^{#3}} % % some group theory % \newcommand\aut[1]{{\rm Aut}(#1)} \newcommand\fx[1]{{\rm fix}(#1)}% ch2 \newcommand\grp[1]{\langle #1\rangle} \newcommand\nrml{\vartriangleleft} \newcommand\nrmleq{\trianglelefteq} \DeclareMathOperator{\Sym}{Sym} \newcommand\sym[1]{\Sym(#1)} \DeclareMathOperator{\Alt}{Alt} \newcommand\alt[1]{\Alt(#1)} \)

Section6.3The Steiner System \(S(5,\,6,\,12)\)

The Steiner system, \(S(5,\,6,\,12)\) is a collection of \(132\) \(6\)-sets (“blocks”), chosen from a \(12\)-set (the “points”), such that every set of \(5\) points chosen from the \(12\)-set is contained in exactly one of the blocks. In other words, a \(S(5,\,6,\,12)\) Steiner system is a \(5\)-\((12,6,1)\) design.

We first need some of the objects we computed in Chapter 5, so evaluate the next cell to get started.

The \(12\) points for our construction will be the \(6\) vertices of \(K_6\) and the \(6\) factorizations of \(K_6\). The construction of designs in Sage is not as robust as those of graphs and permutation groups, and require our points to be integers, starting at zero. We are in good shape with our vertices, and by necessity, we will use a dictionary to map factorizations to the integers \(6\) through \(11\).

The first two blocks of the construction will be the set of all six vertices and the set of all six factorizations. We will create the blocks as sorted lists. The sorting is only for the sake of appearance.

The next \(90\) blocks come from considering each of the \(15\) pairs of distinct factorizations. We know that each such pair has a single factor in common. This factor has three edges, each edge providing two vertices as endpoints. For each of the \(15\cdot 3=45\) factorization-pair/vertex-pair combinations we build two blocks. Start the first block with the six vertices, remove the two vertices of the pair, and add in the two factorizations of the pair. Similarly, start the second block with the six factorizations, remove the two factorizations of the pair, and add in the two vertices of the pair.

The final \(40\) blocks require more care. Each of the \({6\choose 3}=20\) sets of triples can be used to create a permutation of the vertices that is a \(3\)-cycle. While there are two possible ways to create this permutation, either choice leads to the same result in the following procedure. As we did in Section 5.3, this permutation of the vertices can be used to induce a permutation of the six factorizations. (so be sure to evalaute the cell below that defines this function.) It is not obvious (details are in van Lint and Wilson), but the induced permutation is a product of two \(3\)-cycles. We use these two \(3\)-cycles merely to group the six factorizations into two sets of three. (This decrease in structure partially explains the flexibility in the choice of the initial \(3\)-cycle.) For each of the two sets of three factorizations so determined, append the three vertices chosen initially, so as to create the final \(20\cdot 2=40\) blocks.

There are now \(132\) blocks, which we can examine if we wish.

We can, of course, verify analytically that this construction creates a Steiner system, but we let Sage do the work instead and see that the parameters returned are as expected.

Note that the enabling arithmetic for this example is: \(12 = 6 + 6\) and \(132=2 + 15\cdot 3\cdot 2 + {6\choose 3}\cdot 2\).

The automorphism group of a design (Steiner system) is a permutation of the points which carries blocks to blocks, and non-blocks to non-blocks. The Steiner system \(S(5,\,6,\,12)\) is remarkable, in part because its automorphism group is the Mathieu group, \(M_{12}\). This permutation group is highly transitive and is one of the first five sporadic simple groups discovered. In particular, \(M_{12}\) is \(5\)-transitive, a fact you can verify in Sage by creating the group and examining a succession of orbits and stabilizers.

Exercise 6.3.1

Verify that the Mathieu group, as implemented directly in Sage, is a \(5\)-transitive permutation group.

Sage claims to be able to build the automorphism group of this design, but the routine is broken and would likely produce permutations on \(144\) symbols (all vertices of the point-block incidence graph of the design).

Exercise 6.3.2

Analyze all \(12!=479\,001\,600\) permutations of the \(12\) points of the \(S(5,\,6,\,12)\) Steiner system and identify the \(95\,040\) permutations which preserve the blocks. This may take a long time (perhaps an unreasonable amount of time). To be more efficient, perhaps use the Sage combinatorics routines to build the permutations quickly (rather than the permutation group code), and try to move on to testing the next permutation just as soon as the current one fails to preserve some block.

Exercise 6.3.3

Build the point-block incidence graph of the \(S(5,\,6,\,12)\) Steiner system and construct the group of graph automorphisms. For these permuations, isolate the permutations of the points of the design which are automorphisms of the design. Use the experience to debug and fix Sage's automorphism group routine for designs.