Dodecahedral Faces of M12

 

Dodecahedral Faces of M12

 

by Ann Luers Casey

 

This post constitutes part of the math honors thesis written in spring 1997 at the USNA, advised by David Joyner. It is in the public domain.

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 M12. This post explores two different ways of creating M12 and then looks at twelve different ways M12 appears in mathematics, hence the pun the “dodecahedral faces” in the title. Specifically, this post relates M12 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 M24 of a dodecad.

Definitions:

Homomorphism: Let G1, G2 be groups with *1 denoting the group operation for G1 and *2 the group operation for G2. A function f : G1–>G2 is a homomorphism if and only if for all a,b, in Gwe have

f(a *1 b) = f(a) *2 f(b).

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:

  • Let Fq denote the finite field with q elements, q is a power of a prime.
  • Z = the invertible scalar 2×2 matrices with entries in Fqx.
  • Let PGL2(Fq) = GL2(Fq)/Z = {A*Z | A is in GL2(Fq)}, with multiplication given by
    (A*Z)(B*Z) = (A*B)Z. This is the projective linear group over Fq.
  • LF(Fq) is the group of linear fractional transformations x–>(ax+b)/(cx+d).

Claim: There is a group theoretic isomorphism between PGL2(Fq) and LF(Fq). (See [11], Theorem 9.47 for a proof.)

Claim: LF(Fq) acts 3-transitively on the set P1(Fq) (q>3). I.e., one can send any triple to any other triple in P1(Fq) by using a suitable linear fractional transformation. (See [11], Theorem 9.48 for a proof.)

Theorem

PSL2(Fq) = < x–>x+1, x–>kx, x–>-1/x>, where k is any element in Fqthat generates the multiplicative group of squares.

For a proof, see [12], ch 10, section 1.

One way to construct the Mathieu group M12 is the following, accredited to Conway.

M12 = < PSL2(F11), (2 10)(3 4)(5 9)(6 7) >.More explicitly, let

  • f1 be a cyclic permutation = x–> x+1 = (0,1,2,…,10)(inf).
  • f2 = x–>kx = (0)(1 3 9 5 4)(2 6 7 10 8)(inf) when k=3.
  • f3 = x–>-1/x = (0 inf)(1 10)(2 5)(3 7)(4 8)(6 9).
  • f4 = (2 10)(3 4)(5 9)(6 7).

Then M12 = < f1, f2, f3, f4 >. Therefore, M12 is a subgroup of the symmetric group on 12
symbols, namely inf, 0, 1, …, 10.

Another way to construct M12 is given later under 5-transitivity.

There are many occurrences of M12 in mathematics, but here I will list and explain twelve of them:

  1. Mongean Shuffle
  2. Steiner Hexad
  3. Golay Code
  4. Hadamard Matrices
  5. 5- Transitivity
  6. Presentations
  7. Crossing the Rubicon
  8. M12 and the Minimog
  9. Kitten
  10. Mathematical Blackjack or Mathieu’s 21
  11. Sporadic Groups
  12. Stabilizer in M24 of a dodecad

    1. Mongean Shuffle

     

    The Mongean shuffle concerns a deck of twelve cards, labeled 0 through 11. The permutation

    r(t) = 11-t

    reverses the cards around. The permutation

    s(t) = min(2t,23-2t)

    is called the Mongean Shuffle. The permutation group M12 is generated by r and s: M12 = < r,s >, as a subgroup of S12. (See [12], Chap. 11, Sec. 17 or [18])

    2. Steiner Hexad

     

    Jacob Steiner (1796-1863) was a Swiss mathematician specializing in projective goemetry. (It is said that he did 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 = {S1, … ,Sr} of subsets of T such that

    • |Si| = m,
    • For any subset R in T with |R| = k there is a unique i, 1<=i<=n such that R is contained in Si. |S(k,m,n)| = (n choose k)/(m choose k).

    If any set H has cardinality 6 (respectively 8, 12) then H is called a hexad, (respectively octad, dodecad.)

    Let’s look at the Steiner System S(5,6,12) and M12. We want to construct the Steiner system S(5,6,12) using the projective line P1(F11). To define the hexads in the Steiner system, denote

    • the projective line over F11 by P1(F11)={inf,0,1,…,10}.
    • Q = {0,1,3,4,5,9}=the quadratic residues union 0
    • G = PSL2(F11)
    • S = set of all images of Q under G. (Each element g in G will send Q to a subset of P1(F11). )

    There are always six elements in such a hexad. There are 132 such hexads. If I know five of the elements in a hexad of S, then the sixth element is uniquely determined. Therefore S is a Steiner system of type (5,6,12).

    Theorem:
    M12 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 M12.

    (For a proof, see [11], Theorem 9.78.)

    The hexads of S form a Steiner system of type (5,6,12), so

    M12 = < g in S12 | g(s) belongs to S, for all s in S > .

    In other words, M12 is the subgroup stabilizing S. The hexads support the weight six words of the Golay code, defined next. (For a proof, see  [6].)

    3. Golay Code

     

    ” 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 GC24 in 1949 and GC12 in 1954.

    A code C is a vector subspace of (Fq)for some n >=1 and some prime power q =pk.
    An automorphism of C is a vector space isomorphism, f:C–>C.

    If w is a code word in Fqn, 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 (c0,c1,…,cn-1) is a code word then so is (cn-1,c0,…,cn-2).
    If c=(c0,c1,…,cn-1) is a code word in a cyclic code C then we can associate to it a polynomial g_c(x)=c0 + c1x + … + cn-1xn-1. It turns out that there is a unique monic polynomial with coefficients in Fq

    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-alphak1)… (x-alphakr), where {k1,…,kr} are in {0,…,n-1} [17]. The numbers alphaki, 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 Fp is the cyclic code whose generator polynomial has zeros
    {alphak | k is a square mod n} [17]. The ternary Golary code GC11 is the quadratic
    residue code of length 11 over F3.

    The ternary Golay code GC12 is the quadratic residue code of length 12 over F3 obtained by appending onto GC11 a zero-sum check digit [12].

    Theorem:
    There is a normal subgroup N of Aut(GC12) of order 2 such that Aut(GC12)/N is isomorphic to M12. M12 is a quotient of Aut(GC12) by a subgroup or order 2. In other words, M12 fits into the following short exact sequence:

    1–>N–>Aut(GC12)–>M12–>1

    Where i is the embedding and N in Aut(GC12) is a subgroup of order 2. See [6].

    4. Hadamard Matrices

     

    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).

    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 nn/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 12×12 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 P1, P2 such that A = P1 *B *P2.

    All 12×12 Hadamard matrices are equivalent ([13][16] pg. 24). The group of automorphisms of any 12×12 Hadamard matrix is isomorphic to the Mathieu group M12 ([14] pg 99).

     

    5. 5-Transitivity

     

    Emile Mathieu (1835-1890) was a mathematical physicist known for his solution to the vibrations of an elliptical membrane.

    The fact that M12 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 Sn (n>=5), An (n>=7), M12 and M24. (For a proof, see [11])

    Let G act on a set X via phi : G–>SX. G is k-transitive if for each pair of ordered k-tuples (x1, x2,…,xk), (y1,y2,…,yk), all xi and yi elements belonging to X, there exists a g in G such that yi = phi(g)(xi) for each i in {1,2,…,k}.

    M12 can also be constructed as in Rotman [11], using transitive extensions, as follows (this construction appears to be due originally to Witt). Let fa,b,c,d(x)=(ax+b)/(cx+d), let

    M10 = < fa,b,c,d, fa’,b’,c’,d’ |ad-bc is in Fqx, a’d’-b’c’ is not in Fqx >,

    q = 9.

    pi = generator of F9x, so that F9x = < pi> = C8.

    Using Thm. 9.51 from Rotman, we can create a transitive extension of M10. Let omega be a new symbol and define

    M11 = < M10, h| h = (inf, omega)(pi, pi2)(pi3,pi7) (pi5,pi6)>.

    Let P1(F9) = {inf, 0, 1, pi, pi2, … , pi7}. Then M11 is four transitive on Y0 = P1(F9) union {omega}, by Thm 9.51.

    Again using Thm. 9.51, we can create a transitive extension of M11. Let sigma be a new symbol and define

    M12 = < M11, k>, where k = (omega, sig)(pi,pi3) (pi2,pi6)(pi5,pi7). M12 is 5-transitive on Y1 = Y0 union {sig}, by Th. 9.51.

    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 S12 isomorphic to the Mathieu group M12. 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 –> M12 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 M12, i in Y1. Using some h in M12, any i1,…,i5

    in Y1 can be sent to any j1,…,j5 in Y1. That is, there exists an h in M12 such that h(ik) = jk, k= 1,…,5 since M12 is 5-transitive. Therefore, Sig-1(h)(ik) = jk = g(ik). This action is 5-transitive. QED

    In fact, the following uniqueness result holds.

    Theorem: If G and G’ are subgroups of S12 isomorphic to M12 then they are conjugate in S12.

    (This may be found in [7], pg 211.)

    6. Presentations

     

    The presentation of M12 will be shown later, but first I will define a presentation.

    Let G = < x1,…,xn | R1(x1,…xn) = 1, …, Rm(x1,…,xn) = 1> be the smallest group generated by x1,…,xn satisfying the relations R1,…Rm. Then we say G has presentation with generators x1,…,xn and relations R1(x1,…xn) = 1, …, Rm(x1,…,xn) = 1.

    Example: Let a = (1,2,…,n), so a is an n-cycle. Let Cn be the cyclic group, Cn = < a > =
    {1,a,…,an-1}. Then Cn has presentation < x | xn=1 > = all words in x, where x satisfies xn.=1 In fact, < x | xn = 1 > is isomorphic to < a >. Indeed, the isomorphism
    < x | xn = 1 > –> < a > is denoted by xk –> ak, 0 <= k <= n-1. Two things are needed for a presentation:

    • generators, in this case x, and
    • relations, in this case xn = 1.

    Example: Let G be a group generated by a,b with the following relations; a2 = 1, b2 = 1, (ab)2 = 1:

    G = < a,b | a2 = 1, b2 = 1, (ab)2 = 1 > = {1,a,b,ab}.

    This is a non-cyclic group of order 4.

    Two presentations of M12 are as follows:

    M12 = < A,B,C,D | A11 = B5 = C2 = D2 = (BC)2 = (BD)2 = (AC)= (AD)3 = (DCB)2 = 1, AB =A3 >

    = < A,C,D | A11 = C2 = D2 = (AC)3 = (AD)3 = (CD)10 = 1, A2(CD)2A = (CD)2 >.

    In the first presentation above, AB = B-1AB. These are found in [6] and Chap. 10 Sec. 1.6 [12].

    7. Crossing the Rubicon

     

    The Rubicon is the nick-name for the Rubik icosahedron, made by slicing the icosahedron in half for each pair of antipodal vertices. Each vertex can be rotated by 2*pi/5 radians, affecting the vertices in that half of the Rubicon, creating a shape with 12 vertices, and six slices. The Rubicon and M12 are closely related by specific moves on the Rubicon.

    Let f1, f2, …,f12 denote the basic moves of the Rubicon, or a 2*pi/5 radians turn of the sub-pentagon about each vertex. Then according to Conway,

    M12 = < x*y-1 | x,y are elements of {f1, f2, …,f12 } >.

    Actually, if a twist-untwist move, x*y-1, as above, is called a cross of the Rubicon, then M12 is generated by the crosses of the Rubicon! ([1], Chap. 11 Sec. 19 of [12])

    8. M12 and the Minimog

     

    Using the Minimog and C4 (defined below), I want to construct the Golay code GC12.

    The tetracode C4 consists of 9 words over F3:

      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 C4 defines a linear function f : F3 –> F3, 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 4×3 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 GC12 if and only if

    • sum of each column = -(sum row0)
    • row+ – row is one of the tetracode words.

    This may be found in [4].

    Example:

    |+|+ + +|      col sums: ----      row+ - row-: --+0
    |0|0 + -|      row0 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. S12 sends the 3×4 minimog array to another 3×4 array. The group M12 is a subgroup of S12 which sends the Minimog array to another array also yielding S(5,6,12) in Conway-Curtis notation.

    9. Kitten

     

    The kitten is also an interesting facet of the Minimog. Created by R.T. Curtis,
    kittens come from the construction of the Miracle Octal Generator, or MOG, also created by R.T. Curtis. (A description of the MOG would be too far afield for this post, but further information on the MOG can be gotten from [3] or [6].)

    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' kitten               
    

    where 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' kitten
    

    The 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-picture
    

    A 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:

    • A union of parallel lines in any picture,
    • {0, 1, inf} union any line,
    • {Two points at infinity} union {square in a picture corresponding to omitted point at infinity},
    • {One point at infinity} union {cross in the corresponding picture at infinity}.

    (See [2])

    M12 is isomorphic to the group of automorphisms of the Steiner system S(5,6,12) in the Conway-Curtis notation.

    10. Mathematical Blackjack or Mathieu’s 21

    Mathematical Blackjack is a card game where six cards from the group {0,1,…,11} are laid out face up on a table. The rules are:

    • each player must swap a card with a card from the remaining six, that is lower than the card on the table;
    • the first player to make the sum of all six cards less than 21 loses.

    According to Conway and Ryba [8, section V, part (d)], the winning strategy of this game is to choose a move which leaves a Steiner hexad from S(5,6,12) in the shuffle
    notation, whose sum is greater than or equal to 21, on the table.

    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-picture
    

    Riddle: 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 M12 group generated by r, s (see section 1) to shuffle the cards. Since the M12 group preserves hexads, player A still has a winning game. (He and Joe split the money.)

    11. Sporadic Groups

     

    A simple group is a group with no normal subgroups except itself and {1}. Most simple groups are from a family such as PSL2(Fp), p>3 or An, n >= 5. However there exist some simple groups outside of such well known families. These are called sporadic simple groups. M12 is a sporadic simple group of order 95,040. The only smaller sporadic group is M11 of order 7,920. (See [10] pg. 211)

    12. Stabilizer in M24 of a dodecad.

     

    M24 is a sporadic simple group of order 244,823,040 containing M12 as a subgroup. The Steiner system S(5,8,24) is a collection of 8 element subsets, called octads, from a 24 element set X, with the property that any five elements in X determine a unique octad in the system. There are (24 choose 5)/(8 choose 5) = 759 of these octads. M24 is the subgroup of SX which sends the set of octads to itself. Two octads, O1, O2, intersect in a subset of X of order 0,2,4,6 or 8 [14]. If |O1 intersect O2| = 2 then O1 + O2 is order 12. Such a subset of X is called a dodecad. M12 is isomorphic to

    {g in M24 | g(O1 + O2) = (O1 + O2)} = the stablizer of the dodecad O1 + O2.
    (See [6] for details)

    Much more information can be received from the references below or from the hexad/blackjack page.

    References

     

    1. W. D. Joyner, Mathematics of the Rubik’s Cube (USNA Course notes), 1997.
    2. R. T. Curtis, “The Steiner System S(5,6,12), the Mathieu Group M12 and the ‘Kitten’ ,” Computational Group Theory, Academic Press, London, 1984.
    3. J. H. Conway, “hexacode and Tetracode- MOG and MINIMOG,” Computational Group Theory (ed. Atkinson), Academic Press, London, 1984.
    4. Vera Pless, “Decoding the Golay Code,” Transactions of Information Theory, IEEE, 1986, (pgs 561-567).
    5. R. T. Curtis, “A new Combinatorial approach to M24“, Mathematical Proceeding of the Cambridge Philosophical Society, Vol. 79, 1974.
    6. J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker, R. A. Wilson, “M12,”,
      Atlas of Finite Groups, Clarendon Press, Oxford, 1985.
    7. Robinson, A Course in the Theory of Groups, Springer, 1996.
    8. J. H. Conway, N. Sloane, “Lexicographic Codes: Error-Correcting Codes
      from Game Theory,” Transactions on Information Theory, IEEE, 1986.
    9. A .Adler, “The modular Curve X(11) and the Mathieu group M11“,
      Proc. London Math Society 74(1997)1-28.
      See also the paper X(11) and M11.
    10. T. Thompson, From Error-Correcting Codes Through Sphere
      Packings to Simple Groups
      , The Mathematical Association of
      America, 1983.
    11. Rotman, J, Introduction to the Theory of Groups, 4th ed.
      Springer-Verlag, 1995.
    12. J. Conway, N. Sloane, Sphere Packings, Lattices, and Groups,
      Springer-Verlag, 3rd ed., 1999.
    13. B. Kostant, “The Graph of the truncated icosahedron and the
      last letter of Galois.” Notices of the A.M.S. 42(1995)959-
      968.
    14. E. Assmus, “On the Automorphism Groups of Paley-Hadamard
      Matrices.” Combinatorial Mathematics and its Applications.
      University of North Carolina Press, 1969, (pgs 98-103).
    15. P. Greenberg, Mathieu Groups, Courant Institute of Math and
      Science, New York University, 1973.
    16. P. Cameron, J. Van Lint, Designs, Graphs, Codes, and Their
      Links
      , London Mathematical Society, Cambridge University
      Press, 1991.
    17. F. MacWilliams, N. Sloane, The Theory of Error Correcting
      Codes
      , North Holland Publishing Company, 1978.
    18. R. Graham, P. Diaconis, W. Kantor, “The Mathematics of
      Perfect Shuffles”, Advanced Applied Math, Vol. 4, 1985, (pgs
      175-196).

    Typed into html by wdj, 4-18-97.
    Corrections 4-27-2001.
    Last updated 2018-06-10.

     

Jesse Douglas – yet another Beautiful Mind?

Nobel prize winner John Nash struggled with mental illness for most of his life. His struggles were described Sylvia Nasar’s well-known biography, A Beautiful Mind, as well as a film of the same name starring Russell Crowe. Now, John Nash is practically a household name, honored for his contributions to the mathematics of game theory and economics.

While Jesse Douglas isn’t nearly as well-known as Nash, and didn’t win a Nobel Prize, he was (with Lars Ahlfors in 1936) the first recipient of the Fields Medal. According to one source, he too struggled with mental illness. However, before talking about the life of Jesse Douglas, let’s talk about his mathematical research.

Jesse-Douglas-1940-1941_250x250

Jesse Douglas in his 40s.

His Mathematics

Jesse Douglas solved a geometrical problem formulated in the 1700’s now called Plateau’s problem.  Plateau’s problem (also known as the soap bubble problem) is to show the existence of a minimal surface with a given boundary. Plateau was a a Belgian physicist who lived in the 1800s, known for his experiments with soap films. A minimal surface is a surface that locally minimizes its area. For example, the catenoid (see below) obviously doesn’t have minimum area for its (disconnected) boundary, but any piece of it bounded by a (connected) closed curve does have minimum area.

 

 

 

His research was not universally recognized at first. According to Reid [R76]:

Arriving in the year 192901930 at the end of a European tour as a National Research Fellow, he proposed to talk about his not-yet-published work on Plateau’s Problem at the weekly meeting of the mathematische Gesellschaft [at Gottingen University]. The problem had been around for a long time. Many outstanding mathematicians, including Riemann himself, had worked on it. The members of the Gesellschaft simply did not believe that an American had solved it. … When he had finished his presentation, some of the members of the Gesellschaft took him severely to task on almost every detail of the proof. Let left Gottingen deeply offended …

Douglas solved this geometrical problem in his paper “Solution of the problem of Plateau,” Trans. Amer. Math. Soc. 33 (1931)263–321. Gray and Micallef [GM07] do an excellent job of describing Jesse’s mathematical approach to the problem. Jesse continued working on generalizing and refining aspects of his research on this problem for the next 10 years or so. Some of his papers in this field include

  • A method of numerical solution of the problem of Plateau, Annals of Mathematics 29(1927 – 1928)180-188
  • Solution of the problem of Plateau, Trans. Amer. Math. Soc. 33 (1931) 263–321.
  • Systems of K-dimensional manifolds in an N-dimensional space, Mathematische Annalen 105 (1931) 707-733.
  • The Problem of Plateau for Two Contours, Studies in Applied Mathematics 10(1931)315-359.
  • One-sided minimal surfaces with a given boundary, Trans. Am Math Soc 34(1932)731–756.
  • A Jordan space curve no arc of which can form part of a contour which bounds a finite area, Annals of Mathematics 35(1934) 100-103.
  • Green’s function and the problem of Plateau, American Journal of Mathematics. 61 (1939) 545–589.
  • The most general form of the problem of Plateau, American Journal of Mathematics. 61 (1939)590–608.
  • Solution of the inverse problem of the calculus of variations, Proceedings of the National Academy of Sciences. 25(1939) 631–637.
  • The analytic prolongation of a minimal surface across a straight line, Proc Natl Acad Sci USA. 25(1939)375-377.
  • The higher topological form of Plateau’s problem, Annali della Scuola Normale Superiore di Pisa , 8 (1939)195-218.
  • Minimal surfaces of higher topological structure, Annals of Mathematics 40(1939) 205-298 .
  • Theorems in the inverse problem of the calculus of variations, Proc Natl Acad Sci USA, 26(1940) 215–221.

He also wrote papers in other fields in mathematics, for example, the theory of finite groups. For example, in 1951 he published a series of short articles On finite groups with two independent generators, all in the Proc. Natl. Acad. Sci. USA. Also, in 1953, he published a series of short articles On the basis theorem for finite abelian groups, again, all in the Proc. Natl. Acad. Sci. USA.

His Life

Jesse’s father, Louis, was a Polish immigrant who moved to Canada sometime in the late 1800s. The family name was changed at Canadian Immigration and I don’t know his original name. At some point, Louis married Sarah Kommel (I don’t know when the move occurred, nor when and where they met) and moved to New York City. I think both Louis and Sarah were Jewish. Jesse was born in NYC on July 3rd, 1897. According to a geneology website, Sarah’s parents were Leazar Louis Kommel (1851-1923) and Chaya Lande, who died in 1906. Jesse’s mother Sarah passed away in 1939, a year before Jesse married (as we will see below).

Jesse was educated at public schools in New York City. According to Steinhardt [St92], Jesse had a photographic memory. After graduation from high school, he entered the City College of New York and won the Belden Medal for excellence in mathematics in his first year at City College of New York, the youngest recipient at the time. He graduated with a B.Sc. cum laude in February 1916 at the age of 18. Then he entered Columbia University to undertake research under the supervision of Edward Kasner. He took part in Kasner’s seminar on differential geometry and it was there that Jesse first heard of Plateau’s Problem. He submitted his doctoral thesis On Certain Two-Point Properties of General Families of Curves in 1920 (some references say 1921). After getting his PhD, he was an instructor at Columbia from 1920 to 1926. (Was this in the statistics department or the mathematics department? I don’t know.)

He won a National Research Fellowship and as a result, traveled widely for four years, visiting Princeton and Harvard in 1927, Chicago in 1928, and Paris from 1928 to 1930, with trips to Gottingen, Hamburg, and Rome. Jesse was offered an Assistant Professor position at MIT in January 1930. He took leave of absence for a term in 1932. After his promotion to Associate Professor at MIT in 1934, he almost at once took leave of absence again to be a Research Worker at the Institute for Advanced Study in Princeton from 1934 to 1935.  After returning to MIT, Jesse was awarded the first Fields Medal, together with Lars Ahlfors, in 1936. Once again, Jesse took leave of absence from MIT in 1936, and on 1 July 1938, he resigned. According to Aronson [A13], Jesse “became ill” at this time and Levinson was eventually hired as his replacement.

This may seem like the romantic life of a world-class mathematician, but it really is very unusual to be “homeless” 18 years after your get your PhD degree. Something is going on. According to Hersh [H10]:

Douglas’s name is almost forgotten today. He is a rather tragic figure, one of several important mathematicians gravely handicapped by what are now called bipolar, and used to be called manic-depressive, symptoms. He had a junior position at M.I.T., which he lost as a result of inability to perform consistently in the classroom.

According to Steinhardt [St92],

… the volatility of this mix of great gifts and sharp emotions [in which his “over-sized sensitivity surfaced not infrequently in intense feelings articulated vigorously to colleagues”] in Douglas’ makeup worked to the disadvantage of the great American mathematician’s external fortunes.

I don’t know what he did professionally in the 1939-1940 period, but he married Jessie Nayler on June 30th, 1940 (they had one son Lewis Philip Douglas). The husband named Jesse and the wife named Jessie! He often taught summer courses at Columbia University, as well as courses at Yeshiva University. The following year, Jesse was a Guggenheim fellow at Columbia University from 1940 to 1941. He taught at Brooklyn College from 1942 to 1946, as an assistant professor. His teaching during these war years went well according to a letter of commendation (did he teach students from the US Military Academy during this time?), and he received a Distinguished Service Award. In 1945, Jesse wrote an application letter for a teaching position saying [St92]:

This semester I have a teaching load of 19 hours per week at Brooklyn College, including two advances courses: complex variables and calculus of variations.

It is no surprise that he published nothing in the period 1942-1950. According to Micallef [M13],

There is a blank in Douglas’s career from 1946 to 1950, and the later part of Douglas’ life seems to have been troubled. His marriage ended in divorce in 1950.

In 1951, Jesse published a string of papers in a completely different field, finite group theory. Perhaps the end of Jesse’s marriage to Jessie caused him to reinvent himself, mathematically?

According to some sources, Douglas harbored resentment towards his research “competition” Rado (who he strongly beieved should not be credited with solving Plateau’s Problem [St92]) and Courant, as well as J.F. Ritt at Columbia, who may have blocked his appointment to a permanent position at his alma mater. (Sadly, anti-Semitic prejudices common of those times may have played a role in Jesse’s troubles in this regard.) Never-the-less, he is remembered as a helpful, sympathetic, and approachable colleague [St92].

His resentment of Courant was unfortunate because some 10 years earlier, in March 1935, Courant invited Jesse to speak at NYU. According to Reid [R76]:

Courant’s invitation to Douglas to speak at NYU was to a certain extent an olive branch. … Remembering this past history [Jesse’s reception at Gottingen 5 years earlier], Courant did his best to make Douglas’ lecture at NYU an event.

Clearly, Courant appreciated Jesse’s work and tried to treat him with due respect.

Other than Jesse’s mathematical research, this does not appear to have been a happy period in Jesse’s life. According to O’Conner and Robertson [OCR],

His [ex-]wife, Jessie Douglas died in 1955, the year in which Douglas was appointed professor of mathematics at the City College of New York. He remained in that post for the final ten years of his life, living in Butler Hall, 88 Morningside Drive in New York.

Steinhardt [St92] recalls the difficulty that Abraham Schwartz had in having CCNY give tenure at the full professor level to Jesse, when he was 1958. Except for the logician Emil Post, there was no one at CCNY at the time close to Jesse’s stature as a researcher. Ironically, a number of CCNY mathematicians “felt threatened by the appointment”, presumably fearing Jesse would require them to work harder.

There are a number of anecdotes of Jesse Douglas and his interactions with students. They aren’t universally flattering and I hesitate to repeat the negative ones, as I don’t know how typical they are. A number of sources suggest that when he was feeling well, he could be an impressive, charismatic, self-confident expositor and a lucid  teacher. While I don’t know the teaching load at Columbia University the time (where he belonged), I do know that, compared to today’s teaching loads, they were often quite heavy (see for example Parikh’s biography, The Unreal Life of Oscar Zariski). Are these unflattering reports of Jesse’s interactions with students merely due to his oppressive teaching load and inability to handle that volume of students? I don’t know. Perhaps he held others to the same very high standards that he held himself in his own mathematical research.

Unfortunately, not enough is known about this very remarkable mathematician.

References

[A13] D.G. Aronson, Norman Levinson: 1912-1975, Biographical memoirs, Nat. Acad. Sci., 2013.

[GM07] Jeremy Gray, Mario Micallef, The work of Jesse Douglas on minimal surfaces, 2013. (appeared in Bull AMS 2008)  pdf

[H10] R. Hersh, Under-represented then over-represented, College J. Math, 2010.

[M13] M. Micallef, The work of Jesse Douglas on Minimal Surfaces, talk at Universidad de Granada, 2013-02-07.

[OCR] John J. O’Connor and Edmund F. Robertson, Jesse Douglas.

[R76] C. Reid, Courant, Springer-Verlag, 1976.

[St92] F. Steinhardt, “Jesse Douglas as teacher and colleague”, in The Problem of Plateau, ed. T. Rassias, World Scientific, 1992.

Ring theory, via coding theory and cryptography

In these notes on ring theory, I tried to cover enough material to get a feeling for basic ring theory, via cyclic codes and ring-based cryptosystems such as NTRU. Here’s a list of the topics.

1 Introduction to rings
1.1 Definition of a ring
1.2 Integral domains and fields
1.3 Ring homomorphisms and ideals
1.4 Quotient rings
1.5 UFDs
1.6 Polynomial rings
1.6.1 Application: Shamir’s Secret Sharing Scheme
1.6.2 Application: NTRU
1.6.3 Application: Modified NTRU
1.6.4 Application to LFSRs

2 Structure of finite fields
2.1 Cyclic multiplicative group
2.2 Extension fields
2.3 Back to the LFSR

3 Error-correcting codes
3.1 The communication model
3.2 Basic definitions
3.3 Binary Hamming codes
3.4 Coset leaders and the covering radius
3.5 Reed-Solomon codes as polynomial codes
3.6 Cyclic codes as polynomial codes
3.6.1 Reed-Solomon codes as cyclic codes
3.6.2 Quadratic residue codes
3.6.3 BCH bound for cyclic codes
3.6.4 Decoding cyclic codes
3.6.5 Cyclic codes and LFSRs

4 Lattices
4.1 Basic definitions
4.2 The shortest vector problem
4.2.1 Application to a congruential PKC
4.3 LLL and a reduced lattice basis
4.4 Hermite normal form
4.5 NTRU as a lattice cryptosystem

Calculus on graphs

In these notes, I tried to cover enough material to get a feeling for “calculus on graphs”, with applications to sports rankings and the Friendship Theorem. Here’s a list of the topics.

1 . Introduction
2. Examples
3. Basic definitions
3.1 Diameter, radius, and all that
3.2 Treks, trails, paths
3.3 Maps between graphs
3.4 Colorings
3.5 Transitivity
4. Adjacency matrix
4.1 Definition
4.2 Basic results
4.3 The spectrum
4.4 Application to the Friendship Theorem
4.5 Eigenvector centrality and the Keener ranking
4.6 Strongly regular graphs
4.7  Orientation on a graph
5. Incidence matrix
5.1 The unsigned incidence matrix
5.2 The oriented case
5.3 Cycle space and cut space
6. Laplacian matrix
6.1 The Laplacian spectrum
7  Hodge decomposition for graphs
7.1 Abstract simplicial complexes
7.2 The Bjorner complex and the Riemann hypothesis
7.3 Homology groups
8. Comparison graphs
8.1 Comparison matrices
8.2 HodgeRank
8.3 HodgeRank example

Gray codes

This is based on work done about 20 years ago with a former student Jim McShea.

Gray codes were introduced by Bell Labs physicist Frank Gray in the 1950s. As introduced, a Gray code is an ordering of the n-tuples in GF(2)^n = \{0,1\}^n such that two successive terms differ in only one position. A Gray code can be regarded as a Hamiltonian path in the cube graph. For example:

[[0, 0, 0], [1, 0, 0], [1, 1, 0], [0, 1, 0], [0, 1, 1], [1, 1, 1], [1, 0, 1], [0, 0, 1]]

These can be generalized to n-tuples of integers (mod m) in the obvious way.

Gray codes have several applications:

  • solving puzzles such as the Tower of Hanoi and the Brain [G],
  • analog-digital-converters (goniometers) [S],
  • Hamiltonian circuits in hypercubes [Gil] and Cayley graphs of Coxeter groups [CSW],
  • capanology (the study of bell-ringing) [W],
  • continuous space-filling curves [Gi],
  • classification of Venn diagrams [R],
  • design of communication codes,
  • and more (see Wikipedia).
brain-puzzle

The Brain puzzle

Here's a SageMath/Python function for computing Gray codes.
def graycode(length,modulus):
    """
    Returns the n-tuple reverse Gray code mod m.


    EXAMPLES:
        sage: graycode(2,4)
        
        [[0, 0],
         [1, 0],
         [2, 0],
         [3, 0],
         [3, 1],
         [2, 1],
         [1, 1],
         [0, 1],
         [0, 2],
         [1, 2],
         [2, 2],
         [3, 2],
         [3, 3],
         [2, 3],
         [1, 3],
         [0, 3]]

    """
    n,m = length,modulus
    F = range(m)
    if n == 1:
        return [[i] for i in F]
    L = graycode(n-1, m)
    M = []
    for j in F:
        M = M+[ll+[j] for ll in L]
    k = len(M)
    Mr = [0]*m
    for i in range(m-1):
        i1 = i*int(k/m)
        i2 = (i+1)*int(k/m)
        Mr[i] = M[i1:i2]
    Mr[m-1] = M[(m-1)*int(k/m):]
    for i in range(m):
        if is_odd(i):
            Mr[i].reverse()
    M0 = []
    for i in range(m):
        M0 = M0+Mr[i]
    return M0


REFERENCES

[CSW] J. Conway, N. Sloane, and A. Wilks, “Gray codes and reflection groups”, Graphs and combinatorics 5(1989)315-325

[E] M. C. Er, “On generating the N-ary reflected Gray codes”, IEEE transactions on computers, 33(1984)739-741

[G] M. Gardner, “The binary Gray code”, in Knotted donuts and other mathematical entertainments, F. H. Freeman and Co., NY, 1986

[Gi] W. Gilbert, “A cube-filling Hilbert curve”, Math Intell 6 (1984)78

[Gil] E. Gilbert, “Gray codes and paths on the n-cube”, Bell System Technical Journal 37 (1958)815-826

[R] F. Ruskey, “A Survey of Venn Diagrams“, Elec. J. of Comb.(1997), and updated versions.

[S] Web page of T. Sillke

[W] A. White, “Ringing the cosets”, Amer. Math. Monthly 94(1987)721-746

Simple unsolved math problem, 8

Sylver coinage is a game for 2 players invented by John H. Conway.

The two players take turns naming positive integers that are not the sum of non-negative multiples of any previously named integers. The player who is forced to name 1 loses.

James Joseph Sylvester proved the following fact.

Lemma: If a and b are relatively prime positive integers, then (a – 1)(b – 1) – 1 is the largest number that is not a sum of nonnegative multiples of a and b.

Therefore, if a and b have no common prime factors and are the first two moves, this formula gives an upper bound on the next number that can still be played.

R. L. Hutchings proved the following fact.

Theorem: If the first player selects any prime number p>3 as a first move then he/she has a winning strategy.

Very little is known about the subsequent winning moves. That is, a winning strategy exists but it’s not know what it is!

Unsolved problem:Are there any non-prime winning opening moves in Sylver coinage?

For further info, Sicherman maintains a Sylver coinage game webpage.

Sports ranking methods, 4

This is the fourth of a series of expository posts on matrix-theoretic sports ranking methods. This post discusses the Elo rating.

This system was originally developed by Arpad Elo (Elo (1903-1992) was a physics professor at Marquette University in Milwaukee and a chess master, eight-time winner of the Wisconsin State Chess Championships.) Originally, it was developed for rating chess players in the 1950s and 1960s. Now it is used for table tennis, basketball, and other sports.

We use the following version of his rating system.

As above, assume all the $n$ teams play each other (ties allowed)
and let r_i denote the rating of Team i, i=1,2,\dots,n.

Let A=(A_{ij}) denote an $n\times n$ matrix of score results:

A_{ij}= \left\{ \begin{array}{rr} -1,& {\rm if\ team\ } i {\rm \ lost\ to\ team\ } j,\\ +1,& {\rm if\ team\ } i {\rm\ beat\ team\ } j,\\ 0, & {\rm if}\ i=j. \end{array} \right.

Let S_{ij}=(A_{ij}+1)/2.

As in the previous post, the matrix A associated to the example of the Patriot league is the adjacency matrix of a diagraph.

  1. Initialize all the ratings to be 100: {\bf r}=(r_1,\dots,r_n) = (100,\dots,100).
  2. After Team i plays Team j, update their rating using the formula

    r_i = r_i+K(S_{ij}-mu_{ij}),

    where K=10 and

    \mu_{ij} = (1+e^{-(r_i-r_j)/400})^{-1}.

In the example of the Patriot league, the ratings vector is

{\bf r}=(85.124, 104.79, 104.88, 85.032, 94.876, 124.53).

This gives the ranking

Lafayette < Army < Lehigh < Bucknell < Holy Cross < Navy.

This gives a prediction failure rate of 13.3\%.

Some SageMath code for this:

def elo_rating(A):
    """
    A is a signed adjacency matrix for a directed graph.

    Returns elo ratings of the vertices of Gamma = Graph(A) 
        
    EXAMPLES:
        sage: A = matrix(QQ,[
        [0 , -1 , 1  , -1 , -1 , -1 ],
        [1,   0 ,  -1,  1,  1,   -1  ],
        [-1 , 1 ,  0 ,  1 , 1  , -1  ],
        [1 , -1 , -1,  0 ,  -1 , -1  ],
        [1 , - 1 , - 1 , 1 , 0 , - 1  ],
        [1 ,  1  ,  1  , 1  , 1  , 0 ]
        ])
        sage: elo_rating(A)
        (85.124, 104.79, 104.88, 85.032, 94.876, 124.53)

    """
    n = len(A.rows())
    RR = RealField(prec=20)
    V = RR^n
    K = 10
    r0 = 100 # initial rating
    r = n*[r0]
    for i in range(n):
        for j in range(n):
            if ij and A[i][j]==1:
                S = 1
            elif ij and A[i][j]==-1:
                S = 0
            else:
                S = 1/2
            mu = 1/(1+e^(-(r[i]-r[j])/400))
            r[i] = r[i]+K*(S-mu)
    return V(r)