Groups are objects in mathematics that measure symmetry in nature. A group is a set with a binary operation that has an inverse, an identity and is associative. For example, a clock has 12-fold symmetry. A more unusual group is a sporadic, non-abelian simple group. It can be very interesting to look more closely at such a group that arises naturally. One such group is M_{12}. This paper explores two different ways of creating M_{12} and then looks at twelve different ways M_{12} appears in mathematics, hence the pun the "dodecahedral faces" in the title. Specifically, this paper relates M_{12} to the Mongean shuffle, hexads of a Steiner system, Golay codes, the Hadamard matrix of order 12, 5-transitivity, presentations, crossing the Rubicon, the minimog, the kitten, mathematical blackjack, sporadic groups, and the stabilizer in M_{24} of a dodecad.
Definitions:
Homomorphism: Let G_{1}, G_{2} be groups with *_{1} denoting the group operation for G_{1} and *_{2} the group operation for G_{2}. A function f : G_{1}-->G_{2} is a homomorphism if and only if for all a,b, in G_{1} we have
Isomorphism: If a homomorphism is bijective, then it is called an isomorphism.
Automorphism: An isomorphism from a group G to itself is an automorphism.
Notation:
Claim: LF(F_{q}) acts 3-transitively on the set P^{1}(F_{q}) (q>3). I.e., one can send any triple to any other triple in P^{1}(F_{q}) by using a suitable linear fractional transformation. (See [11], Theorem 9.48 for a proof.)
Theorem PSL_{2}(F_{q}) = < x-->x+1, x-->kx, x-->-1/x>, where k is any element in F_{q}^{x} that generates the multiplicative group of squares.
For a proof, see [12], ch 10, section 1.
One way to construct the Mathieu group M_{12} is the following, accredited to Conway.
Another way to construct M_{12} is given later in the paper under 5-transitivity.
There are many occurrences of M_{12} in mathematics, but here I will list and explain twelve of them:
Jacob Steiner (1796-1863) was a Swiss mathematician specializing in projective goemetry. (It is said that hedid not learn to read or write until the age of 14 and only started attending school at the age of 18.) The origins of "Steiner systems" are rooted in problems of plane geometry. |
Let T be a given set with n elements. Then the Steiner system S(k,m,n) is a collection S = {S_{1}, ... ,S_{r}} of subsets of T such that
Let's look at the Steiner System S(5,6,12) and M_{12}. We want to construct the Steiner system S(5,6,12) using the projective line P^{1}(F_{11}). To define the hexads in the Steiner system, denote
Theorem: M_{12} sends a hexad in a Steiner system to another hexad in a Steiner system. In fact, the automorphism group of a Steiner system of type (5,6,12) is isomorphic to M_{12}.
(For a proof, see [11], Theorem 9.78.)
The hexads of S form a Steiner system of type (5,6,12), so
The hexads support the weight six words of the Golay code, defined next. (For a proof, see [6].)
" The Golay code is probably the most important of all codes for both practical and theoretical reasons." ([17], pg. 64)
M. J. E. Golay (1902-1989) was a Swiss physicist known for his work in infrared spectroscopy among other things. He was one of the founding fathers of coding theory, discovering GC_{24} in 1949 and GC_{12} in 1954. |
A code C is a vector subspace of (F_{q})^{n} for some n >=1 and some prime power q =p^{k}. An automorphism of C is a vector space isomorphism, f:C-->C.
If w is a code word in F_{q}^{n}, n>1, then the number of non-zero coordinates of w is called the weight w, denoted by wt(w). A cyclic code is a code which has the property that whenever (c_{0},c_{1},...,c_{n-1}) is a code word then so is (c_{n-1},c_{0},...,c_{n-2}). If c=(c_{0},c_{1},...,c_{n-1}) is a code word in a cyclic code C then we can associate to it a polynomial g_c(x)=c_{0} + c_{1}x + ... + c_{n-1}x^{n-1}. It turns out that there is a unique monic polynomial with coefficients in F_{q} of degree >1 which divides all such polynomials g_c(x). This polynomial is called a generator polynomial for C, denoted g(x).
Let n be a positive integer relatively prime to q and let alpha be a primitive n-th root of unity. Each generator g of a cyclic code C of length n has a factorization of the form g(x) = (x-alpha^{k1})... (x-alpha^{kr}), where {k_{1},...,k_{r}} are in {0,...,n-1} [17]. The numbers alpha^{k}_{i}, 1<= i<= r, are called the zeros of the code C.
If p and n are distinct primes and p is a square mod n, then the quadratic residue code of length n over F_{p} is the cyclic code whose generator polynomial has zeros {alpha^{k} | k is a square mod n} [17]. The ternary Golary code GC_{11} is the quadratic residue code of length 11 over F_{3}.
The ternary Golay code GC_{12} is the quadratic residue code of length 12 over F_{3} obtained by appending onto GC_{11} a zero-sum check digit [12].
Theorem: There is a normal subgroup N of Aut(GC_{12}) of order 2 such that Aut(GC_{12})/N is isomorphic to M_{12}. M_{12} is a quotient of Aut(GC_{12}) by a subgroup or order 2. In other words, M_{12} fits into the following short exact sequence:
Jacques Hadamard (1865-1963) was a French mathematician who did important work in analytic number theory. He also wrote a popular book "The psychology in invention in the mathematical field" (1945) (which is still available from Dover Pub.). |
A Hadamard matrix is any n x n matrix with a +1 or -1 in every entry such that the absolute value of the determinant is equal to n^{n/2}.
An example of a Hadamard matrix is the Paley-Hadamard matrix. Let p be a prime of the form 4N-1, p > 3. A Paley-Hadamard matrix has order p+1 and has only +1's and -1's as entries. The columns and rows are indexed as (inf,0,1,2,...,p-1). The infinity row and the infinity column are all +1's. The zero row is -1 at the 0th column and at the columns that are quadratic non-residues mod p; the zero row is +1 elsewhere. The remaining p-1 rows are cyclic shifts of the finite part of the second row. For further details, see for example [14].
When p = 11 this construction yields a 12x12 Hadamard matrix.
Given two Hadamard Matrices A, B we call them left-equivalent if there is an nxn signed permutation matrix P such that PA = B.
The set {P nxn signed permutation matrix| AP is left equivalent to A} is called the automorphism group of A. In other words, a matrix is an automorphism of the Hadamard matrix, if it is a nxn monomial matrix with entries in {0,+1,-1} and when it is multiplies the Hadamard matrix on the right, only the rows may be permuted, with a sign change in some rows allowed.
Two nxn Hadamard matrices A, B are called equivalent if there are nxn signed permutation matrices P_{1}, P_{2} such that A = P_{1} *B *P_{2}.
All 12x12 Hadamard matrices are equivalent ([13], [16] pg. 24). The group of automorphisms of any 12x12 Hadamard matrix is isomorphic to the Mathieu group M_{12} ([14] pg 99).
Emile Mathieu (1835-1890) was a mathematical physicist known for his solution to the vibrations of an elliptical membrane. |
The fact that M_{12} acts 5-transitively on a set with 12 elements is due to E. Mathieu who proved the result in 1861. (Some history may be found in [15].)
There are only a finite number of types of 5-transitive groups, namely S_{n} (n>=5), A_{n} (n>=7), M_{12} and M_{24}. (For a proof, see [11])
Let G act on a set X via phi : G-->S_{X}. G is k-transitive if for each pair of ordered k-tuples (x_{1}, x_{2},...,x_{k}), (y_{1},y_{2},...,y_{k}), all x_{i} and y_{i} elements belonging to X, there exists a g in G such that
M_{12} can also be constructed as in Rotman [11], using transitive extensions, as follows (this construction appears to be due originally to Witt). Let f_{a,b,c,d}(x)=(ax+b)/(cx+d), let
Using Thm. 9.51 from Rotman, we can create a transitive extension of M_{10}. Let omega be a new symbol and define
Again using Thm. 9.51, we can create a transitive extension of M_{11}. Let sigma be a new symbol and define
Now that we constructed a particular group that is 5-transitive on a particular set with 12 elements, what happens if we have a group that is isomorphic to that group? Is this new group also 5- transitive?
Let G be a subgroup of S_{12} isomorphic to the Mathieu group M_{12}. Such a group was constructed in Section 1.
Lemma: There is an action of G on the set {1,2,...,12} which is 5-transitive.
proof: Let Sig : G --> M_{12} be an isomorphism. Define g(i) = Sig(g)(i), where i = {1,2,...,12}, g is in G. This is an action since Sig is an isomorphism. Sig^{-1}(h)(i) = h(i) for all g in M_{12}, i in Y_{1}. Using some h in M_{12}, any i_{1},...,i_{5} in Y_{1} can be sent to any j_{1},...,j_{5} in Y_{1}. That is, there exists an h in M_{12} such that h(i_{k}) = j_{k}, k= 1,...,5 since M_{12} is 5-transitive. Therefore, Sig^{-1}(h)(i_{k}) = j_{k} = g(i_{k}). This action is 5-transitive. QED
In fact, the following uniqueness result holds.
Theorem: If G and G' are subgroups of S_{12} isomorphic to M_{12} then they are conjugate in S_{12}.
(This may be found in [7], pg 211.)
Let G = < x_{1},...,x_{n} | R_{1}(x_{1},...x_{n}) = 1, ..., R_{m}(x_{1},...,x_{n}) = 1> be the smallest group generated by x_{1},...,x_{n} satisfying the relations R_{1},...R_{m}. Then we say G has presentation with generators x_{1},...,x_{n} and relations R_{1}(x_{1},...x_{n}) = 1, ..., R_{m}(x_{1},...,x_{n}) = 1.
Example: Let a = (1,2,...,n), so a is an n-cycle. Let C_{n} be the cyclic group, C_{n} = < a > = {1,a,...,a^{n-1}}. Then C_{n} has presentation < x | x^{n}=1 > = all words in x, where x satisfies x^{n}. In fact, < x | x^{n} = 1 > is isomorphic to < a >. Indeed, the isomorphism < x | x^{n} = 1 > --> < a > is denoted by x^{k} --> a^{k}, 0 <= k <= n-1. Two things are needed for a presentation:
Two presentations of M_{12} are as follows:
Let f_{1}, f_{2}, ...,f_{12} denotes the basic moves of the Rubicon, or a 2*pi/5 radians turn of the sub-pentagon about each vertex. Then according to Conway,
The tetracode C_{4} consists of 9 words over F_{3}:
0 000, 0 +++, 0 ---, where 0=0, +=1, and -=2 all mod 3. + 0+-, + +-0, + -0+, - 0-+, - +0-, - -+0.Each (a,b,c,d) in C_{4} defines a linear function f : F_{3} --> F_{3}, where f(x) = ax+b, f(0) = b, f(1) = f(+) = c, f(2) = f(-) = d, and a is the "slope" of f. This implies a + b = c (mod 3), b - a = d (mod 3).
Minimog: A 4x3 array whose rows are labeled 0,+,-, that construct the Golay code in such a way that both signed and unsigned hexads are easily recognized.
A col is a word of length 12, weight 3 with a "+" in all entries of any one column and a "0" everywhere else. A tet is a word of length 12, weight 4 who has "+" entries in a pattern such that the row names form a tetracode word, and "0" entires elsewhere. For example,
_________ _________ | |+ | | |+ | | |+ | |+| + | | |+ | | | +| --------- --------- "col" "tet"The above "col" has "+" entries in all entries of column 2, and "0" entries elsewhere. The above "tet" has a "+" entry in each column. The row names of each "+" entry are +, 1, +, - respectively. When put together, + 0+- is one of the nine tetracode words.
Lemma: Each word belongs to the ternary Golay Code GC_{12} if and only if
Example:
|+|+ + +| col sums: ---- row_{+} - row_{-}: --+0 |0|0 + -| row_{0} sum: + = -(sum of each col) |+|+ 0 -|How do I construct a Golay code word using cols and tets? By the Lemma above, there are four such combinations of cols and tets that are Golay code words. These are: col - col, col + tet, tet - tet, col + col - tet.
Example:
col-col col+tet tet-tet col+col-tet | |+ -| | |+ + | |+|0 + +| | |- + +| | |+ -| |+| - | |-| - | |-| 0 +| | |+ -| | | + +| | | -| | | + 0| ? ? ? ? + 0 ? - - ? - + + 0 + -"Odd-Man-Out": The rows are labeled 0,+,-, resp.. If there is only one entry in a column then the label of the corresponding row is the Odd Man Out. (The name of the odd man out is that of the corresponding row.) If there is no entry or more than one entry in the column then the odd man out is denoted by "?".
For example, in the arrays above, the Odd-Men-Out are written below the individual arrays.
For the Steiner system S(5,6,12), the minimog is labeled as such:
______________ |0 3 inf 2 | |5 9 8 10 | |4 1 6 7 | --------------The four combinations of cols and tets above that construct a Golay code word yield all signed hexads. From these signed hexads, if you ignore the sign, there are 132 hexads of the Steiner system S(5,6,12) using the (o, inf, 1) labeling discussed in Section 9 below. There are a total of 265 words of this form, but there are 729 Golay code words total. So, although the above combinations yield all signed hexads, they do not yield all hexads of the Golay code ( [12] pg. 321).
The hexad for the tet-tet according to the S(5,6,12) Minimog above would be (0, inf, 2, 5, 8, 7).
The rules to obtain each hexad in this Steiner system is discussed in Section 9 below.
A Steiner system of type (5,6,12) and the Conway-Curtis notation can be obtained from the Minimog. S_{12} sends the 3x4 minimog array to another 3x4 array. The group M_{12} is a subgroup of S_{12} which sends the Minimog array to another array also yielding S(5,6,12) in Conway-Curtis notation.
Suppose we want to construct a Steiner system from the set T = {0, 1, ..., 10, inf}. The kitten places 0, 1, and inf at the corners of a triangle, and then creates a rotational symmetry of triples inside the triangle according to R(y) = 1/(1-y) (as in [2], section 3.1). A kitten looks like:
infinity 6 2 10 5 7 3 6 9 4 6 2 10 8 2 10 0 1 Curtis' kittenwhere 0, 1, inf are the points at infinity.
Another kitten, used to construct a Steiner system from the set T = {0, 1, ..., 10, 11} is
6 9 10 8 7 2 5 9 4 11 9 10 8 3 10 8 1 0 Conway-Curtis' kittenThe corresponding minimog is
_________________________ | 6 | 3 | 0 | 9 | |-----|-----|-----|-----| | 5 | 2 | 7 | 10 | |-----|-----|-----|-----| | 4 | 1 | 8 | 11 | |_____|_____|_____|_____|(see Conway [3]).
The first kitten shown consists of the three points at 0, inf, 1 with an arrangement of points of the plane corresponding to each of them. This correspondence is:
6 |10 | 3 5 | 7 |3 5 | 7 | 3 2 | 7 | 4 6 | 9 |4 9 | 4 | 6 5 | 9 | 8 2 |10 |8 8 | 2 |10 inf-picture 0-picture 1-pictureA union of two perpendicular lines is called a cross. There are 18 crosses of the kitten:
___________________________________________ |* * * |* * * |* * * |* | * | * | |* | * | * |* * * |* * * |* * * | |* | * | * |* | * | * | ----------------------------------------- _________________________________________ |* | * |* * |* |* * | * | |* | * |* * | * * | * | * | |* * * |* * * | * | * * |* * |* * * | ----------------------------------------- _________________________________________ |* * | * | * * | * | * * |* * | |* * |* * |* |* * | * * | * | | * |* * | * * |* * |* |* * | ------------------------------------------A square is a complement of a cross. The 18 squares of a kitten are:
___________________________________________ | | | | * * |* * |* * | | * * |* * |* * | | | | | * * |* * |* * |* * |* * |* * | ----------------------------------------- _________________________________________ | * * |* * | * | * * | * |* * | | * * |* * | * |* | * * |* * | | | |* * |* | * | | ----------------------------------------- _________________________________________ | * |* * |* |* * |* | * | | * | * | * * | * |* |* * | |* * | * |* | * | * * | * | -----------------------------------------The rules to obtain a hexad in the {0,1,inf} notation are the following:
M_{12} is isomorphic to the group of automorphisms of the Steiner system S(5,6,12) in the Conway-Curtis notation.
The shuffle notation for the hexad, used in the Mathematical Blackjack game, is shown below (see also the description in the hexad/blackjack page):
8 |10 |3 5 |11 |3 5 |11 |3 9 |11 |4 2 | 4 |8 8 | 2 |4 5 | 2 |7 7 | 9 |10 9 |10 |7 0-picture 1-picture 6-pictureRiddle: Assuming the strategy, player A just made a winning hexad move that will force player B to make the sum under 21 on his next turn. Joe Smith walks up to player B and offers to shuffle all 12 cards while player A isn't looking, for a fee. Player B grabs at his chance thinking that a random shuffle will let him back in the game. How is it that player B still loses?
Joe is actually working for Player A. Joe does not shuffle the cards randomly, but instead uses the M_{12} group generated by r, s (see section 1) to shuffle the cards. Since the M_{12} group preserves hexads, player A still has a winning game. (He and Joe split the money.)
Much more information can be received from the references below or from the hexad/blackjack page.
Typed into html by wdj, 4-18-97. Last corrections/modifications 4-19-2008.
http://www.permutationpuzzles.org/rubik/m_12.html