The M(13)-groupoid (2)

By lieven

Mathieu-games

Conway’s puzzle M(13) involves the 13 points and 13 lines of $\mathbb{P}^2(\mathbb{F}_3)$ . On all but one point numbered counters are placed holding the numbers 1,…,12 and a move involves interchanging one counter and the ‘hole’ (the unique point having no counter) and interchanging the counters on the two other points of the line determined by the first two points. In the picture on the left, the lines are respresented by dashes around the circle in between two counters and the points lying on this line are those that connect to the dash either via a direct line or directly via the circle. In the first part we saw that the group of all reachable positions in Conway’s M(13) puzzle having the hole at the top positions contains the sporadic simple Mathieu group $M_{12}$ as a subgroup. To see the reverse inclusion we have to recall the definition of the ternary Golay code named in honour of the Swiss engineer Marcel Golay who discovered in 1949 the binary Golay code that we will encounter later on.

The ternary Golay code $\mathcal{C}_{12}$ is a six-dimenional subspace in $\mathbb{F}_3^{\oplus 12}$ and is spanned by its codewords of weight six (the Hamming distance of $\mathcal{C}_{12}$ whence it is a two-error correcting code). There are $264 = 2 \times 132$ weight six codewords and they can be obtained from the 132 hexads, we encountered before as the winning positions of Mathieu’s blackjack, by replacing the stars by signs + or - using the following rules. By a tet (from tetracodeword) we mean a 3×4 array having 4 +-signs indicating the row-positions of a tetracodeword. For example

$~\begin{array}{|c|ccc|} \hline & + & & \\ + & & + & \\ & & & + \\ \hline + & 0 & + & - \end{array}$ is the tet corresponding to the bottom-tetracodeword. $\begin{array}{|c|ccc|} \hline & + & & \\ & + & & \\ & + & & \\ \hline & & & \end{array}$ A col is an array having +-signs along one of the four columns. The signed hexads will now be the hexads that can be written as $\mathbb{F}_3$ vectors as (depending on the column-distributions of the stars in the hexad indicated between brackets)

$col-col~(3^20^2)\qquad \pm(col+tet)~(31^3) \qquad tet-tet~(2^30) \qquad \pm(col+col-tet)~(2^21^2)$

For example, the hexad on the right has column-distribution 2^30 so its signed versions are of the form tet-tet. The two tetracodewords must have the same digit (-) at place four (so that they cancel and leave an empty column). It is then easy to determine these two tetracodewords giving the signed hexad (together with its negative, obtained by replacing the order of the two codewords)

$\begin{array}{|c|ccc|} \hline \ast & \ast & & \\ \ast & & \ast & \\ & \ast & \ast & \\ \hline - & + & 0 & - \end{array}$ signed as $\begin{array}{|c|ccc|} \hline + & & & \\ & & & \\ & + & + & + \\ \hline 0 & - & - & - \end{array} - \begin{array}{|c|ccc|} \hline & + & & \\ + & & + & \\ & & & + \\ \hline + & 0 & + & - \end{array} = \begin{array}{|c|ccc|} \hline + & - & & \\ - & & - & \\ & + & + & \\ \hline - & + & 0 & - \end{array}$

and similarly for the other cases. As Conway&Sloane remark ‘This is one of many cases when the process is easier performed than described’.

We have an order two operation mapping a signed hexad to its negative and as these codewords span the Golay code, this determines an order two automorphism of $\mathcal{C}_{12}$ . Further, forgetting about signs, we get the Steiner-system S(5,6,12) of hexads for which the automorphism group is $M_{12}$ hence the automorphism group op the ternary Golay code is $2.M_{12}$ , the unique nonsplit central extension of $M_{12}$ .

Right, but what is the connection between the Golay code and Conway’s M(13)-puzzle which is played with points and lines in the projective plane $\mathbb{P}^2(\mathbb{F}_3)$ ? There are 13 points $\mathcal{P}$ so let us consider a 13-dimensional vectorspace $X=\mathbb{F}_3^{\oplus 13}$ with basis $x_p~:~p \in \mathcal{P}$ . That is a vector in X is of the form $\vec{v}=\sum_p v_px_p$ and consider the ‘usual’ scalar product $\vec{v}.\vec{w} = \sum_p v_pw_p$ on X. Next, we bring in the lines in $\mathbb{P}^2(\mathbb{F}_3)$ .

For each of the 13 lines l consider the vector $\vec{l} = \sum_{p \in l} x_p$ with support the four points lying on l and let $\mathcal{C}$ be the subspace (code) of X spanned by the thirteen vectors $\vec{l}$ . Vectors $\vec{c},\vec{d} \in \mathcal{C}$ satisfy the remarkable identity $\vec{c}.\vec{d} = (\sum_p c_p)(\sum_p d_p)$ . Indeed, both sides are bilinear in $\vec{c},\vec{d}$ so it suffices to check teh identity for two line-vectors $\vec{l},\vec{m}$ . The right hand side is then 4.4=16=1 mod 3 which equals the left hand side as two lines either intersect in one point or are equal (and hence have 4 points in common). The identity applied to $\vec{c}=\vec{d}$ gives us (note that the squares in $\mathbb{F}_3$ are {0,1}) information about the weight (that is, the number of non-zero digits) of codewords in $\mathcal{C}$

$wt(\vec{c})~mod(3) = \sum_p c_p^2 = (\sum_p c_p)^2 \in \\{ 0,1 \\}$

Let $\mathcal{C}'$ be the collection of $\vec{c} \in \mathcal{C}$ of weight zero (modulo 3) then one can verify that $\mathcal{C}'$ is the orthogonal complement of $\mathcal{C}$ with respect to the scalar product and that the dimension of $\mathcal{C}$ is seven whereas that of $\mathcal{C}'$ is six. Now, let for a point p be $\mathcal{G}_p$ the restriction of

$\mathcal{C}_p = \\{ c \in \mathcal{C}~|~c_p = - \sum_{q \in \mathcal{P}} c_q \\}$

to the coordinates of $\mathcal{P} - \\{ p \\}$ , then $\mathcal{G}_p$ is clearly a six dimensional code in a 12-dimensional space. A bit more work shows that $\mathcal{G}_p$ is a self-dual code with minimal weight greater or equal to six, whence it must be the ternary Golay code! Now we are nearly done. Next time we will introduce a reversi-version of M(13) and use the above facts to deduce that the basic group of the Mathieu-groupoid indeed is the sporadic simple group $M_{12}$ .

References

Robert L. Griess, “ Twelve sporadic groups” chp. 7 ‘The ternary Golay code and $2.M_{12}$ ‘

John H. Conway and N. J.A. Sloane, “ Sphere packings, lattices and groups” chp 11 ‘The Golay codes and the Mathieu groups’

John H. Conway, Noam D. Elkies and Jeremy L. Martin, ‘The Mathieu group $M_{12}$ and its pseudogroup extension $M_{13}$ ‘ arXiv:math.GR/0508630

Previous in series

Artin, arxiv, blackjack, Conway, Elkies, groups, Mathieu, puzzle

No comments
Posted in games, groups
Written on Mon, 30 July 2007 at 9:09 pm
Tags: Artin, arxiv, blackjack, Conway, Elkies, groups, Mathieu, puzzle
If you liked this post, then consider subscribing to our full RSS feed.

The M(13)-groupoid (2)

Mathieu-games

Leave a Reply

Recent Posts

Recent Comments