Tag: blackjack

sporadic simple games

Published July 13, 2008 by lieven

About a year ago I did a series of posts on games associated to the Mathieu sporadic group $M_{12} $, starting with a post on Conway’s puzzle M(13), and, continuing with a discussion of mathematical blackjack. The idea at the time was to write a book for a general audience, as discussed at the start of the M(13)-post, ending with a series of new challenging mathematical games. I asked : “What kind of puzzles should we promote for mathematical thinking to have a fighting chance to survive in the near future?”

Now, Scientific American has (no doubt independently) taken up this lead. Their July 2008 issue features the article Rubik’s Cube Inspired Puzzles Demonstrate Math’s “Simple Groups” written by Igor Kriz and Paul Siegel.

By far the nicest thing about this article is that it comes with three online games based on the sporadic simple groups, the Mathieu groups $M_{12} $, $M_{24} $ and the Conway group $.0 $.

the M(12) game

Scrambles to an arbitrary permutation in $M_{12} $ and need to use the two generators $INVERT=(1,12)(2,11)(3,10)(4,9)(5,8)(6,7) $ and $MERGE=(2,12,7,4,11,6,10,8,9,5,3) $ to return to starting position.

Here is the help-screen :

They promise the solution by july 27th, but a few-line GAP-program cracks the puzzle instantly.

the M(24) game

Similar in nature, again using two generators of $M_{24} $. GAP-solution as before.

This time, they offer this help-screen :

the .0 game

Their most original game is based on Conway’s $.0 $ (dotto) group. Unfortunately, they offer only a Windows-executable version, so I had to install Bootcamp and struggle a bit with taking screenshots on a MacBook to show you the game’s starting position :

Dotto:

Dotto, our final puzzle, represents the Conway group Co0, published in 1968 by mathematician John H. Conway of Princeton University. Co0 contains the sporadic simple group Co1 and has exactly twice as many members as Co1. Conway is too modest to name Co0 after himself, so he denotes the group “.0” (hence the pronunciation “dotto”).

In Dotto, there are four moves. This puzzle includes the M24 puzzle. Look at the yellow/blue row in the bottom. This is, in fact, M24, but the numbers are arranged in a row instead of a circle. The R move is the “circle rotation to the right”: the column above the number 0 stays put, but the column above the number 1 moves to the column over the number 2 etc. up to the column over the number 23, which moves to the column over the number 1. You may also click on a column number and then on another column number in the bottom row, and the “circle rotation” moving the first column to the second occurs. The M move is the switch, in each group of 4 columns separated by vertical lines (called tetrads) the “yellow” columns switch and the “blue” columns switch. The sign change move (S) changes signs of the first 8 columns (first two tetrads). The tetrad move (T) is the most complicated: Subtract in each row from each tetrad 1/2 times the sum of the numbers in that tetrad. Then in addition to that, reverse the signs of the columns in the first tetrad.

Strategy hints: Notice that the sum of squares of the numbers in each row doesn’t change. (This sum of squares is 64 in the first row, 32 in every other row.) If you manage to get an “8”in the first row, you have almost reduced the game to M24 except those signs. To have the original position, signs of all numbers on the diagonal must be +. Hint on signs: if the only thing wrong are signs on the diagonal, and only 8 signs are wrong, those 8 columns can be moved to the first 8 columns by using only the M24 moves (M,R).

the King’s problem on MUBs

Published February 28, 2008 by lieven

MUBs (for Mutually Unbiased Bases) are quite popular at the moment. Kea is running a mini-series Mutual Unbias as is Carl Brannen. Further, the Perimeter Institute has a good website for its seminars where they offer streaming video (I like their MacromediaFlash format giving video and slides/blackboard shots simultaneously, in distinct windows) including a talk on MUBs (as well as an old talk by Wootters).

So what are MUBs to mathematicians? Recall that a d-state quantum system is just the vectorspace $\mathbb{C}^d $ equipped with the usual Hermitian inproduct $\vec{v}.\vec{w} = \sum \overline{v_i} w_i $. An observable $E $ is a choice of orthonormal basis ${ \vec{e_i} } $ consisting of eigenvectors of the self-adjoint matrix $E $. $E $ together with another observable $F $ (with orthonormal basis ${ \vec{f_j} } $) are said to be mutally unbiased if the norms of all inproducts $\vec{f_j}.\vec{e_i} $ are equal to $1/\sqrt{d} $. This definition extends to a collection of pairwise mutually unbiased observables. In a d-state quantum system there can be at most d+1 mutually unbiased bases and such a collection of observables is then called a MUB of the system. Using properties of finite fields one has shown that MUBs exists whenever d is a prime-power. On the other hand, existence of a MUB for d=6 still seems to be open…

The King’s Problem (( actually a misnomer, it’s more the poor physicists’ problem… )) is the following : A physicist is trapped on an island ruled by a mean
king who promises to set her free if she can give him the answer to the following puzzle. The
physicist is asked to prepare a d−state quantum system in any state of her choosing and give it
to the king, who measures one of several mutually unbiased observables on it. Following this, the physicist is allowed to make a control measurement
on the system, as well as any other systems it may have been coupled to in the preparation
phase. The king then reveals which observable he measured and the physicist is required
to predict correctly all the eigenvalues he found.

The Solution to the King’s problem in prime power dimension by P. K. Aravind, say for $d=p^k $, consists in taking a system of k object qupits (when $p=2l+1 $ one qupit is a spin l particle) which she will give to the King together with k ancilla qupits that she retains in her possession. These 2k qupits are diligently entangled and prepared is a well chosen state. The final step in finding a suitable state is the solution to a pure combinatorial problem :

She must use the numbers 1 to d to form $d^2 $ ordered sets of d+1 numbers each, with repetitions of numbers within a set allowed, such that any two sets have exactly one identical number in the same place in both. Here’s an example of 16 such strings for d=4 :

11432, 12341, 13214, 14123, 21324, 22413, 23142, 24231, 31243, 32134, 33421, 34312, 41111, 42222, 43333, 44444

Here again, finite fields are used in the solution. When $d=p^k $, identify the elements of $\mathbb{F}_{p^k} $ with the numbers from 1 to d in some fixed way. Then, the $d^2 $ of number-strings are found as follows : let $k_0,k_1 \in \mathbb{F}_{p^k} $ and take as the first 2 numbers the ones corresponding to these field-elements. The remaning d-2 numbers in the string are those corresponding to the field element $k_m $ (with $2 \leq m \leq d $) determined from $k_0,k_1 $ by the equation

$k_m = l_{m} * k_0+k_1 $

where $l_i $ is the field-element corresponding to the integer i ($l_1 $ corresponds to the zero element). It is easy to see that these $d^2 $ strings satisfy the conditions of the combinatorial problem. Indeed, any two of its digits determine $k_0,k_1 $ (and hence the whole string) as it follows from
$k_m = l_m k_0 + k_1 $ and $k_r = l_r k_0 + k_1 $ that $k_0 = \frac{k_m-k_r}{l_m-l_r} $.

In the special case when d=3 (that is, one spin 1 particle is given to the King), we recover the tetracode : the nine codewords

0000, 0+++, 0—, +0+-, ++-0, +-0+, -0-+, -+0-, –+0

encode the strings (with +=1,-=2,0=3)

3333, 3111, 3222, 1312, 1123, 1231, 2321, 2132, 2213

The M(13)-groupoid (2)

Published July 30, 2007 by lieven

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