Category: featured

Mathieu’s blackjack (1)

Published July 16, 2007 by lieven

Mathieu’s blackjack is a two-person combinatorial game played with 12 cards of values 0,1,2,…,11. For example take from any deck the numbered cards together with the jack (value 11) and the queen (value 0) (btw. if you find this PI by all means replace the queen by a zero-valued king). Shuffle the cards and divide them into two piles of 6 cards (all of them face up on the table) : the main-pile and the other-pile. The rules of the game are

players alternate moves
a move consists of exchanging a card of the main-pile with a lower-valued card from the other-pile
the player whose move makes the sum of all cards in the main-pile under 21 looses the game

For example, the starting main-pile might consist of the six cards

This pile has total value 3+4+7+8+9+11=42. A move replaces one of these cards with a lowever vlued one not in the pile. So for example, replacing 8 with 5 or 1 or 2 or the queen are all valid moves. A winning move from this situation is for example replacing 8 by the queen (value 0) decreasing the value from 42 to 34

But there are otthers, such as replacing 11 by 5, 9 by 1 or 4 by 2. To win this game you need to know the secrets of the tetracode and the MINIMOG.

The tetracode is a one-error correcting code consisting of the following nine words of length four over $\mathbb{F}_3 = { 0,+,- } $

$~\begin{matrix} 0~0 0 0 & 0~+ + + & 0~- – – \\ +~0 + – & +~+ – 0 & +~- 0 + \\ -~0 – + & -~+ 0 – & -~- + 0 \end{matrix} $

The first element (which is slightly offset from the rest) is the slope s of the words, and the other three digits cyclically increase by s (in the field $\mathbb{F}_3 $). Because the Hamming-distance is 3 (the minimal number of different digits between two codewords), the tetracode can correct one error, meaning that if at most one of the four digits gets distorted by the channel one can detect and correct this. For example, if you would receive the word $+~++- $ (which is not a codeword) and if you would know that at most one digits went wrong, you can deduce that the word $+~0+- $ was sent. Thus, one can solve the 4-problem for the tetracode : correctt a tetracodeword given all 4 of its digits, one of which may be mistaken.

Another easy puzzle is the 2-problem for the tertracode : complete a tetracodeword from any 2 of its digits. For example, given the incomplete word $?~?0+ $ you can decide that the slope should be + and hence that the complete word must be $+~-0+ $.

We will use the MINIMOG here as a way to record the blackjack-position. It is a $4 \times 3 $ array where the 12 boxes correspond to the card-values by the following scheme

$\begin{array}{|c|ccc|} \hline 6 & 3 & 0 & 9 \\ 5 & 2 & 7 & 10 \\ 4 & 1 & 8 & 11 \\ \hline \end{array} $

and given a blackjack-position we place a star in the corresponding box, so the above start-position (resp. after the first move) corresponds to

$~\begin{array}{|c|ccc|} \hline & \ast & & \ast \\ & & \ast & \\ \ast & & \ast & \ast \\ \hline – & 0 & 0 & + \end{array}~ $ respectively $\begin{array}{|c|ccc|} \hline & \ast & \ast & \ast \\ & & \ast & \\ \ast & & & \ast \\ \hline – & 0 & – & + \end{array} $

In the final row we have added elements of $\mathbb{F}_3 $ indicating wher ethe stars are placed in that column (if there is just one star, we write the row-number of the star (ordered 0,+,- from top to bottom), if there are two stars we record the row-number of the empty spot. If we would have three or no stars in a column we would record a wild-card character : ?

Observe that the final row of the start position is $-~00+ $ which is NOT a tetracodeword, whereas that of the winning position $-~0-+ $ IS a tetracodeword! This is the essence of the _Conway-Ryba winning strategy_ for Mathieu’s blackjack. There are precisely 132 winning positions forming the Steiner-system S(5,6,12). By an S(5,6,12) we mean a collection of 6-element subsets (our card-piles) from a 12-element set (the deck minus the king) having the amazing property that for EVERY 5-tuple from the 12-set there is a UNIQUE 6-element set containing this 5-tuple. Hence, there are exactly $\begin{pmatrix} 12 \\\ 5 \end{pmatrix}/6 = 132 $ elements in a Steiner S(5,6,12) system. The winning positions are exactly those MINOMOGs having 6 stars such that the final row is a tetracodeword (or can be extended to a tetracodeword replacing the wildcards ? by suitable digits) and such that the distribution of the stars over the columns is NOT (3,2,1,0) in any order.

Provided the given blackjack-position is not in this Steiner-system (and there is only a 1/7 chance that it is), the strategy is clear : remove one of the stars to get a 5-tuple and determine the unique 6-set of the Steiner-system containing this 5-tuple. If the required extra star corresponds to a value less than the removed star you have a legal and winning move (if not, repeat this for another star). Finding these winning positions means solving 2- and 4-problems for the tetracode. _Another time_ we will say more about this Steiner system and indicate the relation with the Mathieu group $M_{12} $.

References

J.H. Conway and N.J.A. Sloane, ‘The Golay codes and the Mathieu groups’, chp. 10 of “Sphere Packings, Lattices and Groups“

David Joyner and Ann Casey-Luers, ‘Kittens, S(5,6,12) and Mathematical blackjack in SAGE‘

Hexagonal Moonshine (3)

Published July 13, 2007 by lieven

Hexagons keep on popping up in the representation theory of the modular group and its close associates. We have seen before that singularities in 2-dimensional representation varieties of the three string braid group $B_3 $ are ‘clanned together’ in hexagons and last time Ive mentioned (in passing) that the representation theory of the modular group is controlled by the double quiver of the extended Dynkin diagram $\tilde{A_5} $, which is an hexagon…

Today we’re off to find representations of the extended modular group $\tilde{\Gamma} = PGL_2(\mathbb{Z}) $, which is obtained by adding to the modular group (see this post for a proof of generation)

$\Gamma = \langle U=\begin{bmatrix} 0 & -1 \\\ 1 & 0 \end{bmatrix},V=\begin{bmatrix} 0 & 1 \\\ -1 & 1 \end{bmatrix} \rangle $ the matrix $R=\begin{bmatrix} 0 & 1 \\\ 1 & 0 \end{bmatrix} $

In terms of generators and relations, one easily verfifies that

$\tilde{\Gamma} = \langle~U,V,R~|~U^2=R^2=V^3=(RU)^2=(RV)^2=1~\rangle $

and therefore $\tilde{\Gamma} $ is the amalgamated free product of the dihedral groups $D_2 $ and $D_3 $ over their common subgroup $C_2 = \langle~R~\rangle $, that is

$\tilde{\Gamma} = \langle U,R | U^2=R^2=(RU)^2=1 \rangle \ast_{\langle R | R^2=1 \rangle} \langle V,R | V^3=R^2=(RV)^2=1 \rangle = D_2 \ast_{C_2} D_3 $

From this description it is easy to find all n-dimensional $\tilde{\Gamma} $-representations $V $ and relate them to quiver-representations. $D_2 = C_2 \times C_2 $ and hence has 4 1-dimensonal simples $S_1,S_2,S_3,S_4 $. Restricting $V\downarrow_{D_2} $ to the subgroup $D_2 $ it decomposes as

$V \downarrow_{D_2} \simeq S_1^{\oplus a_1} \oplus S_2^{\oplus a_2} \oplus S_3^{\oplus a_3} \oplus S_4^{\oplus a_4} $ with $a_1+a_2+a_3+a_4=n $

Similarly, because $D_3=S_3 $ has two one-dimensional representations $T,S $ (the trivial and the sign representation) and one simple 2-dimensional representation $W $, restricting $V $ to this subgroup gives a decomposition

$V \downarrow_{D_3} \simeq T^{b_1} \oplus S^{\oplus b_2} \oplus W^{\oplus b_3} $, this time with $b_1+b_2+2b_3=n $

Restricting both decompositions further down to the common subgroup $C_2 $ one obtains a $C_2 $-isomorphism $V \downarrow_{D_2} \rightarrow^{\phi} V \downarrow_{D_3} $ which implies also that the above numbers must be chosen such that $a_1+a_3=b_1+b_3 $ and $a_2+a_4=b_2+b_3 $. We can summarize all this info about $V $ in a representation of the quiver

Here, the vertex spaces on the left are the iso-typical factors of $V \downarrow_{D_2} $ and those on the right those of $V \downarrow_{D_3} $ and the arrows give the block-components of the $C_2 $-isomorphism $\phi $. The nice things is that one can also reverse this process to get all $\tilde{\Gamma} $-representations from $\theta $-semistable representations of this quiver (having the additional condition that the square matrix made of the arrows is invertible) and isomorphisms of group-representation correspond to those of quiver-representations!

This proves that for all n the varieties of n-dimensional representations $\mathbf{rep}_n~\tilde{\Gamma} $ are smooth (but have several components corresponding to the different dimension vectors $~(a_1,a_2,a_3,a_4;b_1,b_2,b_3) $ such that $\sum a_i = n = b_1+b_2+2b_3 $.

The basic principle of _M-geometry_ is that a lot of the representation theory follows from the ‘clan’ (see this post) determined by the simples of smallest dimensions. In the case of the extended modular group $\tilde{\Gamma} $ it follows that there are exactly 4 one-dimensional simples and exactly 4 2-dimensional simples, corresponding to the dimension vectors

$\begin{cases} a=(0,0,0,1;0,1,0) \\\ b=(0,1,0,0;0,1,0) \\\ c=(1,0,0,0;1,0,0) \\\ d=(0,0,1,0;1,0,0) \end{cases} $ resp. $\begin{cases} e=(0,1,1,0;0,0,1) \\\ f=(1,0,0,1;0,0,1) \\\ g=(0,0,1,1;0,0,1) \\\ h=(1,1,0,0;0,0,1) \end{cases} $

If one calculates the ‘clan’ of these 8 simples one obtains the double quiver of the graph on the left. Note that a and b appear twice, so one should glue the left and right hand sides together as a Moebius-strip. That is, the clan determining the representation theory of the extended modular group is a Moebius strip made of two hexagons!

However, one should not focuss too much on the hexagons (that is, the extended Dynkin diagram $\tilde{A_5} $) here. The two ‘backbones’ (e–f and g–h) have their vertices corresponding to 2-dimensional simples whereas the topand bottom vertices correspond to one-dimensional simples. Hence, the correct way to look at this clan is as two copies of the double quiver of the extended Dynkin diagram $\tilde{D_5} $ glued over their leaf vertices to form a Moebius strip. Remark that the components of the sotropic root of $\tilde{D_5} $ give the dimensions of the corresponding $\tilde{\Gamma} $ simples.

The remarkable ubiquity of (extended) Dynkins never ceases to amaze!

Generators of modular subgroups

Published July 12, 2007 by lieven

In older NeverEndingBooks-posts (and here) proofs were given that the modular group $\Gamma = PSL_2(\mathbb{Z}) $ is the group free product $C_2 \ast C_3 $, so let’s just skim over details here. First one observes that $\Gamma $ is generated by (the images of) the invertible 2×2 matrices

$U= \begin{bmatrix} 0 & -1 \\\ 1 & 0 \end{bmatrix} $ and $V= \begin{bmatrix} 0 & 1 \\\ -1 & 1 \end{bmatrix} $

A way to see this is to consider X=U.V and Y=V.U and notice that multiplying with powers of X adds multiples of the second row to the first (multiply on the left) or multiples of the first column to the second (multiply on the right) and the other cases are handled by taking multiples with powers of Y. Use this together with the fact that matrices in $GL_2(\mathbb{Z}) $ have their rows and columns made of coprime numbers to get any such matrix by multiplication on the left or right by powers of X and Y into the form

$\begin{bmatrix} \pm 1 & 0 \\\ 0 & \pm 1 \end{bmatrix} $ and because $U^2=V^3=\begin{bmatrix} -1 & 0 \\\ 0 & -1 \end{bmatrix} $

we see that $\Gamma $ is an epimorphic image of $C_2 \ast C_3 $. To prove isomorphism one can use the elegant argument due to Roger Alperin considering the action of the Moebius transformations $u(z) = -\frac{1}{z} $ and $v(z) = \frac{1}{1-z} $ (with $v^{-1}(z) = 1-\frac{1}{z} $) induced by the generators U and V on the sets $\mathcal{P} $ and $\mathcal{N} $ of all positive (resp. negative) irrational real numbers. Observe that

$u(\mathcal{P}) \subset \mathcal{N} $ and $v^{\pm}(\mathcal{N}) \subset \mathcal{P} $

Hence, if $w $ is a word in $u $ and $v^{\pm} $ of off length we either have $w(\mathcal{P}) \subset \mathcal{N} $ or $w(\mathcal{N}) \subset \mathcal{P} $ so $w $ can never be the identity. If the length is even we can conjugate $w $ such that it starts with $v^{\pm} $. If it starts with $v $ then $w(\mathcal{P}) \subset v(\mathcal{N}) $ is a subset of positive rationals less than 1 whereas if it starts with $v^{-1} $ then $w(\mathcal{P}) \subset v^{-1}(\mathcal{N}) $ is a subset of positive rationals greater than 1, so again it cannot be the identity. Done!

By a result of Aleksandr Kurosh it follows that every modular subgroup is the group free product op copies of $C_2, C_3 $ or $C_{\infty} $ and we would like to determine the free generators explicitly for a cofinite subgroup starting from its associated Farey code associated to a special polygon corresponding to the subgroup.

To every even interval [tex]\xymatrix{x_i = \frac{a_i}{b_i} \ar@{-}[r]_{\circ} & x_{i+1}= \frac{a_{i+1}}{b_{i+1}}}[/tex] in the Farey code one associates the generator of a $C_2 $ component

$A_i = \begin{bmatrix} a_{i+1}b_{i+1}+ a_ib_i & -a_i^2-a_{i+1}^2 \\\ b_i^2+b_{i+1}^2 & -a_{i+1}b_{i+1}-a_ib_i \end{bmatrix} $

to every odd interval [tex]\xymatrix{x_i = \frac{a_i}{b_i} \ar@{-}[r]_{\bullet} & x_{i+1} = \frac{a_{i+1}}{b_{i+1}}}[/tex] in the Farey code we associate the generator of a $C_3 $ component

$B_i = \begin{bmatrix} a_{i+1}b_{i+1}+a_ib_{i+1}+a_ib_i & -a_i^2-a_ia_{i+1}-a_{i+1}^2 \\\ b_i^2+b_ib_{i+1} + b_{i+1}^2 & -a_{i+1}b_{i+1} – a_{i+1}b_i – a_i b_i \end{bmatrix} $

and finally, to every pair of free intervals [tex]\xymatrix{x_k \ar@{-}[r]_{a} & x_{k+1}} \ldots \xymatrix{x_l \ar@{-}[r]_{a} & x_{l+1}}[/tex] we associate the generator of a $C_{\infty} $ component

$C_{k,l} = \begin{bmatrix} a_l & -a_{l+1} \\\ b_l & – b_{l+1} \end{bmatrix} \begin{bmatrix} a_{k+1} & a_k \\\ b_{k+1} & b_k \end{bmatrix}^{-1} $

Kulkarni’s result states that these matrices are free generators of the cofiniite modular subgroup determined by the Farey code. For example, for the M(12) special polygon on the left (bounded by the thick black geodesics), the Farey-code for this Mathieu polygon is

[tex]\xymatrix{\infty \ar@{-}[r]_{1} & 0 \ar@{-}[r]_{\bullet} & \frac{1}{3} \ar@{-}[r]_{\bullet} & \frac{1}{2} \ar@{-}[r]_{\bullet} & 1 \ar@{-}[r]_{1} & \infty}[/tex]

Therefore, the structure of the subgroup must be $C_{\infty} \ast C_3 \ast C_3 \ast C_3 $ with the generator of the infinite factor being

$\begin{bmatrix} -1 & 1 \\\ -1 & 0 \end{bmatrix} $ and those of the cyclic factors of order three

$\begin{bmatrix} 3 & -1 \\\ 13 & -4 \end{bmatrix}, \begin{bmatrix} 7 & -3 \\\ 19 & 8 \end{bmatrix} $ and $\begin{bmatrix} 4 & -3 \\\ 7 & -5 \end{bmatrix} $

This approach also gives another proof of the fact that $\Gamma = C_2 \ast C_3 $ because the Farey code to the subgroup of index 1 is [tex]\xymatrix{\infty \ar@{-}[r]_{\circ} & 0 \ar@{-}[r]_{\bullet} & \infty}[/tex] corresponding to the fundamental domain on the left. This finishes (for now) this thread on Kulkarni’s paper (or rather, part of it). On the Lost? page I will try to list threads in a logical ordering when they materialize.

Reference

Ravi S. Kulkarni, “An arithmetic-geometric method in the study of the subgroups of the modular group”, Amer. J. Math 113 (1991) 1053-1133