# A mathematical card trick

If you search hard enough on the internet you’ll discover a pamphlet from the 1898 by Si Stebbins entitled “Card tricks and the way they are performed” (which I’ll denote by [S98] for simplicity). In it you’ll find the “Si Stebbins system” which he claims is entirely his own invention. I’m no magician, by from what I can dig up on Magicpedia, Si Stebbins’ real name is William Henry Coffrin (May 4 1867 — October 12 1950), born in Claremont New Hampshire. The system presented below was taught to Si by a Syrian magician named Selim Cid that Si sometimes worked with. However, this system below seems to have been known by Italian card magicians in the late 1500’s. In any case, this blog post is devoted to discussing parts of the pamphlet [S98] from the mathematical perspective.

In stacking the cards (face down) put the 6 of Hearts $6 \heartsuit$ first, the 9 of Spades $9 \spadesuit$ next (so it is below the $6 \heartsuit$ in the deck), and so on to the end, reading across left to right as indicted in the table below (BTW, the pamphlet [S98] uses the reversed ordering.) My guess is that with this ordering of the deck — spacing the cards 3 apart — it still looks random at first glance.

Next, I’ll present a more mathematical version of this system to illustrate it’s connections with group theory.

We follow the ordering suggested by the mnemonic CHaSeD, we identify the suits with numbers as follows: Clubs is 0, Hearts is 1, Spades is 2 and Diamonds is 3. Therefore, the suits may be identified with the additive group of integers (mod 4), namely: ${\bf{Z}}/4{\bf{Z}} = \{ 0,1,2,3 \}$.

For the ranks, identify King with 0, Ace with 1, 2 with 2, $\dots$, 10 with 10, Jack with 11, Queen with 12. Therefore, the ranks may be identified with the additive group of integers (mod 13), namely: ${\bf{Z}}/13{\bf{Z}}=\{ 0,1,2,\dots 12\}$.

Rearranging the columns slightly, we have the following table, equivalent to the one above.

In this way, we identify the card deck with the abelian group

$G = {\bf{Z}}/4{\bf{Z}} \times {\bf{Z}}/13{\bf{Z}}$.

For example, if you spot the $2 \clubsuit$ then you know that 13 cards later (and If you reach the end of the deck, continue counting with the top card) is the $2 \heartsuit$, 13 cards after that is the $2 \spadesuit$, and 13 cards after that is the $2 \diamondsuit$.

Here are some rules this system satisfies:

Rule 1 “Shuffling”: Never riff shuffle or mix the cards. Instead, split the deck in two, the “bottom half” as the left stack and the “top half” as the right stack. Take the left stack and place it on the right one. This has the effect of rotating the deck but preserving the ordering. Do this as many times as you like. Mathematically, each such cut adds an element of the group $G$ to each element of the deck. Some people call this a “false shuffle” of “false cut.”

Rule 2 “Rank position”: The corresponding ranks of successive cards in the deck differs by 3.

Rule 3 “Suit position”: Every card of the same denomination is 13 cards apart and runs in the same order of suits as in the CHaSeD mnemonic, namely, Clubs $\clubsuit$, Hearts $\heartsuit$, Spades $\spadesuit$, Diamonds $\diamondsuit$.

At least, we can give a few simple card tricks based on this system.

Trick 1: A player picks a card from the deck, keeps it hidden from you. You name that card.

This trick can be set up in more than one way. For example, you can either

(a) spread the cards out behind the back in such a manner that when the card is drawn you can separate the deck at that point bringing the two parts in front of you, say a “top” and a “bottom” stack, or

(b) give the deck to the player, let them pick a card at random, which separates the deck into two stacks, say a “top” and a “bottom” stack, and have the player return the stacks separately.

You know that the card the player has drawn is the card following the bottom card of the top stack. If the card on the bottom of the top stack is denoted $(a,\alpha) \in G$ and the card drawn is $(b,\beta)$ then

$b \equiv a+3 \pmod{13}, \ \ \ \ \ \ \beta \equiv \alpha +1 \pmod{4}.$

For example, a player draws a card and you find that the bottom card is the $9 \diamondsuit$. What is the card the player picked?

solution: Use the first congruence listed: add 3 to 9, which is 12 or the Queen. Use the second congruence listed: add one to Diamond $\diamondsuit$ (which is 3) to get $0 \pmod 4$ (which is Clubs $\clubsuit$). The card drawn is the $Q \clubsuit$.

Trick 2: Run through the deck of cards (face down) one at a time until the player tells you to stop. Name the card you were asked to stop on.

Place cards behind the back first taking notice what the bottom card is. To get the top card, add 3 to the rank of the bottom card, add 1 to the suit of the bottom card. As you run through the deck you silently say the name of the next card (adding 3 to the rank and 1 to the suit each time). Therefore, you know the card you are asked to stop on, as you are naming them to yourself as you go along.

# A footnote to Robert H. Mountjoy

In an earlier post titled Mathematical romantic? I mentioned some papers I inherited of one of my mathematical hero’s Andre Weil with his signature. In fact, I was fortunate enough to go to dinner with him once in Princeton in the mid-to-late 1980s – a very gentle, charming person with a deep love of mathematics. I remember he said he missed his wife, Eveline, who passed away in 1986. (They were married in 1937.)

All this is simply to motivate the question, why did I get these papers? First, as mentioned in the post, I was given Larry Goldstein‘s old office and he either was kind enough to gift me his old preprints or left them to be thrown away by the next inhabitant of his office. BTW, if you haven’t heard of him, Larry was a student of Shimura, when became a Gibbs Fellow at Yale, then went to the University of Maryland at COllege Park in 1969. He wrote lots of papers (and books) on number theory, eventually becoming a full professor, but eventually settled into computers and data science work. He left the University of Maryland about the time I arrived in the early 1980s to create some computer companies that he ran.

This motivates the question: How did Larry get these papers of Weil? I think Larry inherited them from Mountjoy (who died before Larry arrived at UMCP, but more on him later). This motivates the question, who is Mountjoy and how did he get them?

I’ve done some digging around the internet and here’s what I discovered.

The earliest mention I could find is when he was listed as a recipient of an NSF Fellowship in “Annual Report of the National Science Foundation: 1950-1953” under Chicago, Illinois, Mathematics, 1953. So he was a grad student at the University of Chicago in 1953. Andre Weil was there at the time. (He left sometime in 1958.) Mountjoy could have gotten the notes of Andre Weil then. Just before Weil left Chicago, Walter Lewis Baily arrived (in 1957, to be exact). This is important because in May 1965 the Notices of the AMS reported that reported:

Mountjoy, Robert Harbison
Abelian varieties attached to representations of discontinuous groups (S. Mac Lane and W. L. Baily)

(His thesis was published posthumously in American Journal of Mathematics Vol. 89 (1967)149-224.) This thesis is in a field studied by Weil and Baily but not Saunders.

But we’re getting ahead of ourselves. The 1962 issue of Maryland Magazine had this:

Mathematics Grant
A team of University of Maryland mathematics researchers have received a grant of $53,000 from the National Science Foundation to continue some technical investigations they started two years ago. The mathematical study they are directing is entitled “Problems in Geometric Function Theory.” The project is under the direction of Dr. James Hummel. Dr. Mischael Zedek. and Prof. Robert H. Mountjoy, all of the Mathematics Department. They are assisted by four graduate-student researchists. The$53,000 grant is a renewal of an original grant which was made two years ago.

We know he was working at UMCP in 1962.

The newspaper Democrat and Chronicle, from Rochester, New York, on Wednesday, May 25, 1965 (Page 40) published the news that Robert H. Mountjoy “Died suddenly at Purcellville, VA, May 23, 1965”. I couldn’t read the rest (it’s behind a paywall but I could see that much). The next day, they published more: “Robert H. Mountjoy, son-in-law of Mr and Mrs Allen P Mills of Brighton, was killed in a traffic crash in Virgina. Mountjoy, about 30, a mathematics instructors at the University of Maryland, leaves a widow Sarah Mills Mountjoy and a 5-month old son Alexander, and his parents Mr and Mrs Lucius Mountjoy of Chicago.”

It’s so sad. The saying goes “May his memory be a blessing.” I never met him, but from what I’ve learned of Mountjoy, his memory is indeed a blessing.

# 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
3. Golay Code
5. 5- Transitivity
6. Presentations
7. Crossing the Rubicon
8. M12 and the Minimog
9. Kitten
10. Mathematical Blackjack or Mathieu’s 21
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])

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

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

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)

## 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.
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
, 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.

# MINIMOGs and Mathematical blackjack

This is an exposition of some ideas of Conway, Curtis, and Ryba on $S(5,6,12)$ and a card game called mathematical blackjack (which has almost no relation with the usual Blackjack).

Many thanks to Alex Ryba and Andrew Buchanan for helpful discussions on this post.

### Definitions

An m-(sub)set is a (sub)set with m elements. For integers $k, a Steiner system S(k,m,n) is an n-set X and a set S of m-subsets having the property that any k-subset of X is contained in exactly one m-set in S. For example, if $X = \{1,2,\dots,12\}$, a Steiner system S(5,6,12) is a set of 6-sets, called hexads, with the property that any set of 5 elements of X is contained in (“can be completed to”) exactly one hexad.

Rob Beezer has a nice Sagemath description of S(5,6,12).

If S is a Steiner system of type (5,6,12) in a 12-set X then any element the symmetric group $\sigma\in Symm_X\cong S_{12}$ of X sends S to another Steiner system $\sigma(S)$ of X. It is known that if S and S’ are any two Steiner systems of type (5,6,12) in X then there is a $\sigma\in Symm_X$ such that $S'=\sigma(S)$. In other words, a Steiner system of this type is unique up to relabelings. (This also implies that if one defines $M_{12}$ to be the stabilizer of a fixed Steiner system of type (5,6,12) in X then any two such stabilizer groups, for different Steiner systems in X, must be conjugate in $Symm_X$. In particular, such a definition is well-defined up to isomorphism.)

### Curtis’ kitten

NICOLE SHENTING – Cats Playing Poker Cards

J. Conway and R. Curtis [Cu1] found a relatively simple and elegant way to construct hexads in a particular Steiner system $S(5,6,12)$ using the arithmetical geometry of the projective line over the finite field with 11 elements. This section describes this.

Let $\mathbf{P}^1(\mathbf{F}_{11}) =\{\infty,0,1,2,...,9,10\}$ denote the projective line over the finite field $\mathbf{F}_{11}$ with 11 elements. Let $Q=\{0,1,3,4,5,9\}$ denote the quadratic residues with 0, and let $L=\cong PSL(2,\mathbf{F}_{11}),$ where $\alpha(y)=y+1$ and $\beta(y)=-1/y$. Let $S=\{\lambda(Q)\ \vert\ \lambda\in L\}.$

Lemma 1: $S$ is a Steiner system of type $(5,6,12)$.

The elements of S are known as hexads (in the “modulo 11 labeling”).

 	 	 	 	 	$\infty$

6

2	 	10

5	 	7	 	3

6	 	9	 	4	 	6

2	 	10	 	8	 	2	 	10

0	 	 	 	 	 	 	 	 	 	1



Curtis’ Kitten.

In any case, the “views” from each of the three “points at infinity” is given in the following tables.

6	10	3
2	7	4
5	9	8
picture at $\infty$

5	7	3
6	9	4
2	10	8
picture at $0$

5	7	3
9	4	6
8	2	10
picture at $1$


Each of these $3\times 3$ arrays may be regarded as the plane $\mathbf{F}_3^2$. The lines of this plane are described by one of the following patterns.

$\bullet$	$\bullet$	$\bullet$
$\times$	$\times$	$\times$
$\circ$	$\circ$	$\circ$
slope 0

$\bullet$	$\times$	$\circ$
$\bullet$	$\times$	$\circ$
$\bullet$	$\times$	$\circ$
slope infinity

$\bullet$	$\times$	$\circ$
$\circ$	$\bullet$	$\times$
$\times$	$\circ$	$\bullet$
slope -1

$\times$	$\circ$	$\bullet$
$\circ$	$\bullet$	$\times$
$\bullet$	$\times$	$\circ$
slope 1


The union of any two perpendicular lines is called a cross. There are 18 crosses. The complement of a cross in $\mathbf{F}_3^2$ is called a square. Of course there are also 18 squares. The hexads are

1. $\{0,1,\infty\}\cup \{{\rm any\ line}\}$,
2. the union of any two (distinct) parallel lines in the same picture,
3. one “point at infinity” union a cross in the corresponding picture,
4. two “points at infinity” union a square in the picture corresponding to the omitted point at infinity.

Lemma 2 (Curtis [Cu1]) There are 132 such hexads (12 of type 1, 12 of type 2, 54 of type 3, and 54 of type 4). They form a Steiner system of type $(5,6,12)$.

### The MINIMOG description

Following Curtis’ description [Cu2] of a Steiner system $S(5,8,24)$ using a $4\times 6$ array, called the MOG, Conway [Co1] found and analogous description of $S(5,6,12)$ using a $3\times 4$ array, called the MINIMOG. This section is devoted to the MINIMOG. The tetracode words are

0	0	0	0		0	+	+	+		0	-	-	-
+	0	+	-		+	+	-	0		+	-	0	+
-	0	-	+		-	+	0	-		-	-	+	0



With ￼”0″=0, “+”=1, “-“=2, these vectors form a linear code over GF(3)￼. (This notation is Conway’s. One must remember here that “+”+”+”=”-“!) They may also be described as the set of all 4-tuples in of the form
$(0,a,a,a),(1,a,b,c),(2,c,b,a),$
where abc is any cyclic permutation of 012￼. The MINIMOG in the shuffle numbering is the array
$\begin{array}{cccc} 6 & 3 & 0 & 9\\ 5 & 2 & 7 & 10 \\ 4 & 1 & 8 & 11 \end{array}$
We label the rows of the MINIMOG array as follows:

1. the first row has label 0,
2. the second row has label +,
3. the third row has label –

A col (or column) is a placement of three + signs in a column of the MINIMOG array. A tet (or tetrad) is a placement of 4 + signs having entries corresponding (as explained below) to a tetracode.

+	+	+	+

0	0	0	0

+
+	+	+

0	+	+	+

+

+	+	+

0	-	-	-


 	+
+	 	+
+

+	0	+	-

 	 	 	+
+	+
+

+	+	-	0

 	 	+
+	 	 	+
+

+	-	0	+

 	+
+
+	 	+

-	0	-	+


 	 	+
+
+	 	 	+

-	+	0	-


 	 	 	+
+
+	+

-	-	+	0



Each line in $\mathbf{F}_3^2$ with finite slope occurs once in the $3\times 3$ part of some tet. The odd man out for a column is the label of the row corresponding to the non-zero digit in that column; if the column has no non-zero digit then the odd man out is a “?”. Thus the tetracode words associated in this way to these patterns are the odd men out for the tets. The signed hexads are the combinations $6$-sets obtained from the MINIMOG from patterns of the form

col-col, col+tet, tet-tet, col+col-tet.

Lemma 3 (Conway, [CS1], chapter 11, page 321) If we ignore signs, then from these signed hexads we get the 132 hexads of a Steiner system $S(5,6,12)$. These are all possible $6$-sets in the shuffle labeling for which the odd men out form a part (in the sense that an odd man out “?” is ignored, or regarded as a “wild-card”) of a tetracode word and the column distribution is not $0,1,2,3$ in any order.

Furthermore, it is known [Co1] that the Steiner system $S(5,6,12)$ in the shuffle labeling has the following properties.

1. There are $11$ hexads with total $21$ and none with lower total.
2. The complement of any of these $11$ hexads in $\{0,1,...,11\}$ is another hexad.
3. There are $11$ hexads with total $45$ and none with higher total.

### Mathematical blackjack

Mathematical blackjack is a 2-person combinatorial game whose rules will be described below. What is remarkable about it is that a winning strategy, discovered by Conway and Ryba [CS2] and [KR], depends on knowing how to determine hexads in the Steiner system $S(5,6,12)$ using the shuffle labeling.

Mathematical blackjack is played with 12 cards, labeled $0,\dots ,11$ (for example: king, ace, $2$, $3$, …, $10$, jack, where the king is $0$ and the jack is $11$). Divide the 12 cards into two piles of $6$ (to be fair, this should be done randomly). Each of the $6$ cards of one of these piles are to be placed face up on the table. The remaining cards are in a stack which is shared and visible to both players. If the sum of the cards face up on the table is less than 21 then no legal move is possible so you must shuffle the cards and deal a new game. (Conway [Co2] calls such a game *={0|0}, where 0={|}; in this game the first player automatically wins.)

1. Players alternate moves.
2. A move consists of exchanging a card on the table with a lower card from the other pile.
3. The player whose move makes the sum of the cards on the table under 21 loses.

The winning strategy (given below) for this game is due to Conway and Ryba [CS2], [KR]. There is a Steiner system $S(5,6,12)$ of hexads in the set $\{0,1,...,11\}$. This Steiner system is associated to the MINIMOG of in the “shuffle numbering” rather than the “modulo $11$ labeling”.

The following result is due to Ryba.

Proposition 6: For this Steiner system, the winning strategy is to choose a move which is a hexad from this system.

This result is proven in a wonderful paper J. Kahane and A. Ryba, [KR]. If you are unfortunate enough to be the first player starting with a hexad from $S(5,6,12)$ then, according to this strategy and properties of Steiner systems, there is no winning move! In a randomly dealt game there is a probability of 1/7 that the first player will be dealt such a hexad, hence a losing position. In other words, we have the following result.

Corollary 7: The probability that the first player has a win in mathematical blackjack (with a random initial deal) is 6/7.

An example game is given in this expository hexads_sage (pdf).

### Bibliography

[Cu1] R. Curtis, “The Steiner system $S(5,6,12)$, the Mathieu group $M_{12}$, and the kitten,” in Computational group theory, ed. M. Atkinson, Academic Press, 1984.
[Cu2] —, “A new combinatorial approach to $M_{24}$,” Math Proc Camb Phil Soc 79(1976)25-42
[Co1] J. Conway, “Hexacode and tetracode – MINIMOG and MOG,” in Computational group theory, ed. M. Atkinson, Academic Press, 1984.
[Co2] —, On numbers and games (ONAG), Academic Press, 1976.
[CS1] J. Conway and N. Sloane, Sphere packings, Lattices and groups, 3rd ed., Springer-Verlag, 1999.
[CS2] —, “Lexicographic codes: error-correcting codes from game theory,” IEEE Trans. Infor. Theory32(1986)337-348.
[KR] J. Kahane and A. Ryba, “The hexad game,” Electronic Journal of Combinatorics, 8 (2001)

# How do I construct … in GAP?

This page is devoted to answering some basic questions along the line “How do I construct … in GAP?” You may view the html source code for the GAP commands without the output or GAP prompt.

Questions

 How do I construct a … group? permutation dihedral  cyclicconjugacy classes of a finitely presented How do I … a polynomial? factor find roots of evaluate Groebner basis of ideal of Brauer characters How do I find the … of a group representation? How do I compute an mod m, where A is …? Given a group G, how do I compute … ?

• permutation:
To construct a permutation group, write down generators in disjoint cycle notation, put them in a list (i.e., surround them by square brackets), and the permutation group G generated by the cycles (1,2)(3,4) and (1,2,3):
gap> G:=Group((1,2)(3,4),(1,2,3));

Group([ (1,2)(3,4), (1,2,3) ])


This is of course a subgroup of the symmetric group S4 on 4 letters. Indeed, this G is in fact the alternating group on four letters, A4.

By virtue of the fact that the permutations generating G employ integers less than or equal to 4, this group G is a subgroup of the symmetric group S4 on 4 letters. Some permutation groups have special constructions:

gap> S4:=SymmetricGroup(4);
Sym( [ 1 .. 4 ] )
gap> A4:=AlternatingGroup(4);
Alt( [ 1 .. 4 ] )
gap> IsSubgroup(S4,G);
true
gap> IsSubgroup(A4,G);
true
gap> S3:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> IsSubgroup(S3,G);
false



• dihedral
To construct a dihedral group, use the special “DihedralGroup” command:
gap> G:=DihedralGroup(6);
gap> Size(G);
6
gap> f:=GeneratorsOfGroup( G );
[ f1, f2 ]
gap> f[1]^2; f[2]^3;
identity of ...
identity of ...
gap> f[1]^2= f[2]^3;
true



• cyclic group
To construct a cyclic group, you may construct integers mod n:

gap> R:=ZmodnZ( 12);
(Integers mod 12)
gap> a:=Random(R);
ZmodnZObj( 11, 12 )
gap> 4*a;
ZmodnZObj( 8, 12 )
gap> b:=Random(R);
ZmodnZObj( 9, 12 )
gap> a+b;
ZmodnZObj( 8, 12 )


or use the special “CyclicGroup” command

gap> G:=CyclicGroup(12);
pc group of size 12 with 3 generators
gap> a:=Random(G);
f3^2
gap> f:=GeneratorsOfGroup( G );
[ f1, f2, f3 ]
gap> f[1]^4;
f3
gap> f[1]^12;
identity of ...



• conjugacy:
The conjugacy classes of a group G are computed using the “ConjugacyClasses” command. This is a list of classes {x^-1*g*x | x in G}.

gap> G:=SL(2,7);
SL(2,7)
gap> CG:=ConjugacyClasses(G);
[ [ [ Z(7)^0, 0*Z(7) ], [ 0*Z(7), Z(7)^0 ] ]^G,
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^5 ] ]^G,
[ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^5 ] ]^G,
[ [ Z(7)^3, 0*Z(7) ], [ 0*Z(7), Z(7)^3 ] ]^G,
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^2 ] ]^G,
[ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^2 ] ]^G,
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, 0*Z(7) ] ]^G,
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^4 ] ]^G,
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7) ] ]^G,
[ [ Z(7)^4, 0*Z(7) ], [ 0*Z(7), Z(7)^2 ] ]^G,
[ [ Z(7)^5, 0*Z(7) ], [ 0*Z(7), Z(7) ] ]^G ]
gap> g:=Representative(CG[3]); Order(g);
[ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^5 ] ]
14
gap> g:=Representative(CG[4]); Order(g);
[ [ Z(7)^3, 0*Z(7) ], [ 0*Z(7), Z(7)^3 ] ]
2
gap> g:=Representative(CG[5]); Order(g);
[ [ 0*Z(7), Z(7)^3 ], [ Z(7)^0, Z(7)^2 ] ]
7
gap> g:=Representative(CG[6]); Order(g);
[ [ 0*Z(7), Z(7)^4 ], [ Z(7)^5, Z(7)^2 ] ]
7
gap>


• presented
To construct a finitely presented group in GAP, use the “FreeGroup” and “FpGroupPresentation” commands. Here is one example.

gap> M12 := MathieuGroup( 12 );
Group([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6), (1,12)(2,11)(3,6)(4,8)(5,9)(7,10) ])
gap> F := FreeGroup( "a", "b", "c" );
free group on the generators [ a, b, c ]
gap> words := [ F.1, F.2 ];
[ a, b ]
gap> P := PresentationViaCosetTable( M12, F, words );
presentation with 3 gens and 10 rels of total length 97
gap> TzPrintRelators( P );
#I  1. c^2
#I  2. b^4
#I  3. a*c*a*c*a*c
#I  4. a*b^2*a*b^-2*a*b^-2
#I  5. a^11
#I  6. a^2*b*a^-2*b^2*a*b^-1*a^2*b^-1
#I  7. a*b*a^-1*b*a^-1*b^-1*a*b*a^-1*b*a^-1*b^-1
#I  8. a^2*b*a^2*b^2*a^-1*b*a^-1*b^-1*a^-1*b^-1
#I  9. a*b*a*b*a^2*b^-1*a^-1*b^-1*a*c*b*c
#I  10. a^4*b*a^2*b*a^-2*c*a*b*a^-1*c
gap> G := FpGroupPresentation( P );
fp group on the generators [ a, b, c ]
gap> RelatorsOfFpGroup( G );
[ c^2, b^4, a*c*a*c*a*c, a*b^-2*a*b^-2*a*b^-2, a^11, a^2*b*a^-2*b^-2*a*b^-1*a^2*b^-1, a*b*a^-1*b*a^-1*b^-1*a*b*a^-1*b*a^-1*b^-1,
a^2*b*a^2*b^-2*a^-1*b*a^-1*b^-1*a^-1*b^-1, a*b*a*b*a^2*b^-1*a^-1*b^-1*a*c*b*c, a^4*b*a^2*b*a^-2*c*a*b*a^-1*c ]
gap> Size(M12);
95040
gap> Size(G);
95040
gap> IsomorphismGroups(G,M12);
????????


The last command is computationally intensive and requires more than the default memory allocation of 256M of RAM.

Here is another example.

gap> F := FreeGroup( "a", "b");
free group on the generators [ a, b ]
gap> G:=F/[F.1^2,F.2^3,F.1*F.2*F.1^(-1)*F.2^(-1)];
fp group on the generators [ a, b ]
gap> Size(G);
6



• rref
The key command for row reduction is “TriangulizeMat”. The following example illustrates the syntax.

gap> M:=[[1,2,3,4,5],[1,2,1,2,1],[1,1,0,0,0]];
[ [ 1, 2, 3, 4, 5 ], [ 1, 2, 1, 2, 1 ], [ 1, 1, 0, 0, 0 ] ]
gap> TriangulizeMat(M);
gap> M;
[ [ 1, 0, 0, -1, 1 ], [ 0, 1, 0, 1, -1 ], [ 0, 0, 1, 1, 2 ] ]
gap> Display(M);
[ [   1,   0,   0,  -1,   1 ],
[   0,   1,   0,   1,  -1 ],
[   0,   0,   1,   1,   2 ] ]
gap> M:=Z(3)^0*[[1,2,3,4,5],[1,2,1,2,1],[1,1,0,0,0]];
[ [ Z(3)^0, Z(3), 0*Z(3), Z(3)^0, Z(3) ],
[ Z(3)^0, Z(3), Z(3)^0, Z(3), Z(3)^0 ],
[ Z(3)^0, Z(3)^0, 0*Z(3), 0*Z(3), 0*Z(3) ] ]
gap> TriangulizeMat(M);
gap> Display(M);
1 . . 2 1
. 1 . 1 2
. . 1 1 2
gap>


• kernel:
There are different methods for matrices over the integers and matrices over a field. For integer entries, related commands include “NullspaceIntMat” and “SolutionNullspaceIntMat” in section 25.1 “Linear equations over the integers and Integral Matrices” of the reference manual.

gap> M:=[[1,2,3],[4,5,6],[7,8,9]];
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
gap> NullspaceIntMat(M);
[ [ 1, -2, 1 ] ]
gap> SolutionNullspaceIntMat(M,[0,0,1]);
[ fail, [ [ 1, -2, 1 ] ] ]
gap> SolutionNullspaceIntMat(M,[0,0,0]);
[ [ 0, 0, 0 ], [ [ 1, -2, 1 ] ] ]
gap> SolutionNullspaceIntMat(M,[1,2,3]);
[ [ 1, 0, 0 ], [ [ 1, -2, 1 ] ] ]



Here (0,0,1) is not in the image of M
(under v-> v*M) but (0,0,0) and (1,2,3) are.

For field entries, related commands include “NullspaceMat” and “TriangulizedNullspaceMat” in section 24.6 “Matrices Representing Linear Equations and the Gaussian Algorithm”
of the reference manual.

gap> M:=[[1,2,3],[4,5,6],[7,8,9]];
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
gap> NullspaceMat(M);
[ [ 1, -2, 1 ] ]
gap> TriangulizedNullspaceMat(M);
[ [ 1, -2, 1 ] ]
gap> M:=[[1,2,3,1,1],[4,5,6,1,1],[7,8,9,1,1],[1,2,3,1,1]];
[ [ 1, 2, 3, 1, 1 ], [ 4, 5, 6, 1, 1 ], [ 7, 8, 9, 1, 1 ],
[ 1, 2, 3, 1, 1 ] ]
gap> NullspaceMat(M);
[ [ 1, -2, 1, 0 ], [ -1, 0, 0, 1 ] ]
gap> TriangulizedNullspaceMat(M);
[ [ 1, 0, 0, -1 ], [ 0, 1, -1/2, -1/2 ] ]



• characteristic polynomial:
Please see section 24.12.1 of the GAP reference manual for examples of characteristic polynomial of a square matrix (“CharacteristicPolynomial”) and section 56.3 for examples of the “characteristic polynomial” (called a “TracePolynomial”) of an element of a field extension.

• character:
GAP contains very extensive character theoretic functions and data libraries (including an interface the character table in the Atlas). Here is just one simple example.

gap> G:=Group((1,2)(3,4),(1,2,3));
Group([ (1,2)(3,4), (1,2,3) ])
gap> T:=CharacterTable(G);
CharacterTable( Alt( [ 1 .. 4 ] ) )
gap> Display(T);
CT1

2  2  2  .  .
3  1  .  1  1

1a 2a 3a 3b
2P 1a 1a 3b 3a
3P 1a 2a 1a 1a

X.1     1  1  1  1
X.2     1  1  A /A
X.3     1  1 /A  A
X.4     3 -1  .  .

A = E(3)^2
= (-1-ER(-3))/2 = -1-b3
gap> irr:=Irr(G);
[ Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, 1, 1 ] ),
Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3)^2, E(3) ] ),
Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3), E(3)^2 ] ),
Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 3, -1, 0, 0 ] ) ]
gap> Display(irr);
[ [       1,       1,       1,       1 ],
[       1,       1,  E(3)^2,    E(3) ],
[       1,       1,    E(3),  E(3)^2 ],
[       3,      -1,       0,       0 ] ]
gap> chi:=irr[2]; gamma:=CG[3]; g:=Representative(gamma); g^chi;
Character( CharacterTable( Alt( [ 1 .. 4 ] ) ), [ 1, 1, E(3)^2, E(3) ] )
(1,2,3)^G
(1,2,3)
E(3)^2



For further details and examples, see chapters 6972 of the GAP reference manual.

• brauer:
Just a simple example of what GAP can do here. To construct a Brauer character table:

gap> G:=Group((1,2)(3,4),(1,2,3));
Group([ (1,2)(3,4), (1,2,3) ])
gap> irr:=IrreducibleRepresentations(G,GF(7));
[ [ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^0 ] ] ],

[ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^4 ] ] ],

[ (1,2)(3,4), (1,2,3) ] -> [ [ [ Z(7)^0 ] ], [ [ Z(7)^2 ] ] ],

[ (1,2)(3,4), (1,2,3) ] -> [

[ [ 0*Z(7), Z(7)^3, Z(7)^0 ], [ 0*Z(7), Z(7)^3, 0*Z(7) ],
[ Z(7)^0, Z(7)^3, 0*Z(7) ] ],
[ [ 0*Z(7), Z(7)^0, 0*Z(7) ],
[ 0*Z(7), 0*Z(7), Z(7)^0 ], [ Z(7)^0, 0*Z(7), 0*Z(7) ] ]

] ]
gap> brvals := List(irr,chi-> List(ConjugacyClasses(G),c->
BrauerCharacterValue(Image(chi, Representative(c)))));
[ [ 1, 1, 1, 1 ], [ 1, 1, E(3)^2, E(3) ], [ 1, 1, E(3), E(3)^2 ],
[ 3, -1, 0, 0 ] ]
gap> Display(brvals);
[ [       1,       1,       1,       1 ],

[       1,       1,  E(3)^2,    E(3) ],

[       1,       1,    E(3),  E(3)^2 ],

[       3,      -1,       0,       0 ] ]
gap>


List(ConjugacyClasses(G),c->BrauerCharacterValue(Image(chi, Representative(c)))));
#Display(brvals);
T:=CharacterTable(G);
Display(T);
–>

• polynomial
There are various ways to construct a polynomial in GAP.

gap> Pts:=Z(7)^0*[1,2,3];
[ Z(7)^0, Z(7)^2, Z(7) ]
gap> Vals:=Z(7)^0*[1,2,6];
[ Z(7)^0, Z(7)^2, Z(7)^3 ]
gap> g:=InterpolatedPolynomial(GF(7),Pts,Vals);
Z(7)^5*x_1^2+Z(7)


Or:

gap> p:=3;; F:=GF(p);;
gap> R:=PolynomialRing(F,["x1","x2"]);
PolynomialRing(..., [ x1, x2 ])
gap> vars:=IndeterminatesOfPolynomialRing(R);;
gap> x1:=vars[1]; x2:=vars[2];
x1
x2
gap> p:=x1^5-x2^5;
x1^5-x2^5
gap> DivisorsMultivariatePolynomial(p,R);
[ x1^4+x1^3*x2+x1^2*x2^2+x1*x2^3+x2^4, x1-x2 ]


Or:

gap> x:=X(Rationals);
x_1
gap> f:=x+x^2+1;
x_1^2+x_1+1
gap> Value(f,[x],[1]);
3


• factor
To factor a polynomial in GAP, there is one command for univariate polynomials (“Factors”) and another command for multivariate polynomials (“DivisorsMultivariatePolynomial”). For a factoring a univariate polynomial, GAP provides only methods over finite fields and over subfields of cyclotomic fields. Please see the examples given in section 64.10 “Polynomial Factorization” for more details. For multivariate polynomials, a very slow algorithm has been implemented in GAP and an interface to a very fast algorithm in Singular has been implemented for those who have both Singular and the GAP Singular package installed. The former of these was illustrated above in “polynomial” above. (Again, the ground field must be a finite field or a subfields of cyclotomic fields.) For the latter, please see the example in the (GAP-)Singular manual FactorsUsingSingularNC.

• roots
There are some situations where GAP can find the roots of a polynomial but GAP does not do this generally. (The roots must generate either a finite field or a subfield of a cyclotomic field.) However, there is a package called RadiRoot which must be installed which does help to do this for polynomials with rational coefficients (radiroot itself requires other packages to be installed; please see the webpage for more details). The “Factors” command actually has an option which allows you to increase the groundfield so that a factorization actually returns the roots. Please see the examples given in section 64.10 “Polynomial Factorization” for more details. Here is a second approach.

gap> p:=3; n:=4; F:=GF(p^n); c:=Random(F); r:=2;
3
4
GF(3^4)
Z(3^4)^79
2
gap>  x:=X(F,1); f:=x^r-c*x+c-1;
x_1
x_1^2+Z(3^4)^39*x_1+Z(3^4)^36
gap>  F_f:=FieldExtension( F, f );
AsField( GF(3^4), GF(3^8) )
gap>  alpha:=RootOfDefiningPolynomial(F_f);
Z(3^4)^36
gap> Value(f,[x],[alpha]);
0*Z(3)



Here is a third. First, enter the following program

RootOfPolynomial:=function(f,R)
local F0,Ff,a;
F0:=CoefficientsRing(R);
Ff:=FieldExtension(F0,f);
a:=RootOfDefiningPolynomial(Ff);
return a;
end;


Here’s how this can be used to find a root:

gap> F:=Rationals;
Rationals
gap> x:=X(F,1); f:=x^2+x+1;
x_1
x_1^2+x_1+1
gap> R:=PolynomialRing( F, [ x ]);
PolynomialRing(..., [ x_1 ])
gap> a:=RootOfPolynomial(f,R);
E(3)
gap> # check:
gap> Value(f,[x],[a]);
0


1. In the GAP Forum: Hensel lifting discussion.
2. In the manual, Galois groups.

• evaluate:
The relevant command is “Value”. There are several examples already on this page. For others, please see the examples given in section 64.7 Multivariate polynomials of the manual. For sparse uivariate polynomials, there is also the command “ValuePol” in section 23.6 of the manual.

• integer power
This is easy and intuitive:

gap> a:=1000; n:=100000; m:=123;
1000
100000
123
gap> a^n mod m;
1



• matrix power:
This too is easy and intuitive:

gap> A:=[[1,2],[3,4]]; n:=100000; m:=123;
[ [ 1, 2 ], [ 3, 4 ] ]
100000
123
gap> A^n mod m;
[ [ 1, 41 ], [ 0, 1 ] ]


• polynomial power
GAP allows you to do arithmetic over the polynomial ring R[x], where R = Z/nZ (where n is a positive integer). Here’s an example.

gap> Z4:=ZmodnZ(4);
(Integers mod 4)
gap> R:=UnivariatePolynomialRing(Z4,1);
PolynomialRing(..., [ x ])
gap> x:=IndeterminatesOfPolynomialRing(R)[1];
x
gap> I:=TwoSidedIdealByGenerators( R,[x^8-x^0]);
two-sided ideal in PolynomialRing(..., [ x ]), (1 generators)
gap> gen:=x^8-x^0;
x8-ZmodnZObj(1,4)
gap> QuotientRemainder(R,x^8,gen);
[ ZmodnZObj(1,4), ZmodnZObj(1,4) ]
gap> QuotientRemainder(R,x^15,gen);
[ x^7, x^7 ]
gap> QuotientRemainder(R,x^15+x^8,gen);
[ x^7+ZmodnZObj(1,4), x^7+ZmodnZObj(1,4) ]
gap> PowerMod( R, x+x^0, 15, gen );
ZmodnZObj(0,4)
gap> PowerMod( R, x, 15, gen );
x^7



• Groebner basis
GAP’s Groebner bases algorithms are relatively slow and are included mostly for simple examples and for teaching purposes. However, a GAP interface to a very fast algorithm in Singular has been implemented for those who have both Singular and the GAP Singular package installed. The former of these is illustrated in section 64.17 Groebner bases of the GAP manual. For the latter, please see the example in the (GAP-)Singular manual GroebnerBasis.

• normal subgroup:
Here is an example:

gap> G := AlternatingGroup( 5 );
Group( (1,2,5), (2,3,5), (3,4,5) )
gap> normal := NormalSubgroups( G );
[ Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ),
Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (1,2)(3,4), (1,3)(4,5), (1,4)(2,3) ] ) ]


1. Please see Volkmar Felsch’s GAP Forum response to a related question.
2. The xgap package (or, on a mac, Gap.app) displays subgroup lattices graphically.

• abelian subgroup
One idea to compute all the abelian subgroups is to compute all the subgroups then “filter” out the abelian ones. Here is an illustration, taked from a GAP Forum response Volkmar Felsch.

gap> G := AlternatingGroup( 5 );
Group( (1,2,5), (2,3,5), (3,4,5) )
gap> classes := ConjugacyClassesSubgroups( G );
[ ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ) ),
ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5),
(2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (3,4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5),
(2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5), (2,4)(3,5) ] ) ), ConjugacyClassSubgroups( Group(
(1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5),
(3,4,5) ), [ (1,2,3,4,5) ] ) ), ConjugacyClassSubgroups( Group(
(1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5),
(3,4,5) ), [ (3,4,5), (1,2)(4,5) ] ) ),
ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (1,2,3,4,5), (2,5)(3,4) ] ) ), ConjugacyClassSubgroups( Group(
(1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5),
(3,4,5) ), [ (2,3)(4,5), (2,4)(3,5), (3,4,5) ] ) ),
ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5), (3,4,5) ), Group(
(1,2,5), (2,3,5), (3,4,5) ) ) ]
gap> cl := classes[4];
ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5), (2,4)(3,5) ] ) )
gap> length := Size( cl );
5
gap> rep := Representative( cl );
Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5), (2,4)(3,5) ] )
gap> order := Size( rep );
4
gap> IsAbelian( rep );
true
gap> abel := Filtered( classes, cl -> IsAbelian( Representative( cl ) ) );
[ ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ), [  ] ) ),
ConjugacyClassSubgroups( Group( (1,2,5), (2,3,5),
(3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5),
(2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (3,4,5) ] ) ), ConjugacyClassSubgroups( Group( (1,2,5),
(2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5), (3,4,5) ),
[ (2,3)(4,5), (2,4)(3,5) ] ) ), ConjugacyClassSubgroups( Group(
(1,2,5), (2,3,5), (3,4,5) ), Subgroup( Group( (1,2,5), (2,3,5),
(3,4,5) ), [ (1,2,3,4,5) ] ) ) ]


• homology
This depends on how the group is given. For example, suppose that G is a permutation group with generators genG and H is a permutation group with generators genH. To find a homomorphism from G to H, one may use the “GroupHomomorphismByImages” or “GroupHomomorphismByImagesNC” commands. For examples of the syntax, please see section 38.1 Creating Group Homomorphisms. Here’s an illustration of how to convert a finitely presented group into a permutation group.

gap> p:=7;
7
gap> G:=PSL(2,p);
Group([ (3,7,5)(4,8,6), (1,2,6)(3,4,8) ])
gap> H:=SchurCover(G);
fp group of size 336 on the generators [ f1, f2, f3 ]
gap> iso:=IsomorphismPermGroup(H);
[ f1, f2, f3 ] -> [ (1,2,4,3)(5,9,7,10)(6,11,8,12)(13,14,15,16),
(2,5,6)(3,7,8)(11,13,14)(12,15,16), (1,4)(2,3)(5,7)(6,8)(9,10)(11,12)(13,
15)(14,16) ]
gap> H0:=Image(iso);                       # 2-cover of PSL2
Group([ (1,2,4,3)(5,9,7,10)(6,11,8,12)(13,14,15,16),
(2,5,6)(3,7,8)(11,13,14)(12,15,16), (1,4)(2,3)(5,7)(6,8)(9,10)(11,12)(13,
15)(14,16) ])
gap> IdGroup(H0);
[ 336, 114 ]
gap> IdGroup(SL(2,7));
[ 336, 114 ]
gap>


• semi-direct product(Contributed by Nilo de Roock):
As you can easily verify, D8 is isomorphic to C2:C4. Or in GAP…

N:=CyclicGroup(IsPermGroup,4);
G:=CyclicGroup(IsPermGroup,2);
AutN:=AutomorphismGroup(N);
f:=GroupHomomorphismByImages(G,AutN,GeneratorsOfGroup(G),[Elements(AutN)[2]]);
NG:=SemidirectProduct(G,f,N);


Verify with

StructureDescription(NG);


• semi-direct products(Contributed by Nilo de Roock):
The following shows how to construct all non-abelian groups of order 12 as semi-direct products. These products are not trivial yet small enough to verify by hand.

#D12 = (C2 x C2) : C3
G1:=CyclicGroup(IsPermGroup,2);
G2:=CyclicGroup(IsPermGroup,2);
G:=DirectProduct(G1,G2);
N:=CyclicGroup(IsPermGroup,3);
AutN:=AutomorphismGroup(N);
f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3],Elements(G)[4]],[Elements(AutN)[1],Elements(AutN)[2],Elements(AutN)[1],Elements(AutN)[2]]);
NG:=SemidirectProduct(G,f,N);
Print(str(NG));
Print("\n");

#T = C4 : C3
G:=CyclicGroup(IsPermGroup,4);
N:=CyclicGroup(IsPermGroup,3);
AutN:=AutomorphismGroup(N);
f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3],Elements(G)[4]],[Elements(AutN)[1],Elements(AutN)[2],Elements(AutN)[1],Elements(AutN)[2]]);
NG:=SemidirectProduct(G,f,N);
Print(str(NG));
Print("\n");

#A4 = C3 : (C2 x C2)
G:=CyclicGroup(IsPermGroup,3);
N1:=CyclicGroup(IsPermGroup,2);
N2:=CyclicGroup(IsPermGroup,2);
N:=DirectProduct(G1,G2);
AutN:=AutomorphismGroup(N);
f:=GroupHomomorphismByImages(G,AutN,[Elements(G)[1],Elements(G)[2],Elements(G)[3]],[Elements(AutN)[1],Elements(AutN)[4],Elements(AutN)[5]]);
NG:=SemidirectProduct(G,f,N);
Print(str(NG));
Print("\n");


• cohomology
GAP will compute the Schur multiplier H2(G,C) using the
“AbelianInvariantsMultiplier” command. Here is an example showing how to find H2(A5,C), where A5 is the alternating group on 5 letters.

gap> A5:=AlternatingGroup(5);
Alt( [ 1 .. 5 ] )
gap> AbelianInvariantsMultiplier(A5);
[ 2 ]


So, H2(A5,C) is Z/2Z.

1. See section 37.23 and section 37.24 of the GAP manual.
2. See D. Holt’s GAP package cohomolo.

# Real world applications of representation theory

### (Subtitle: Representation theorists will rule the world one day just you wait)

This post describes some applications of representation theory of non-abelian groups to various fields and gives some references.

• Engineering.
• Tensegrity – the design of “strut-and-cable” constructions.Want to build a building with cables and struts but don’t know representation theory? Check out these references:
• R. Connelly and A. Back, “Mathematics and tensegrity”, Amer Scientist, April-May 1998, pages 142-151
• symmetric tensegrities
• Telephone network designs.This is the information age with more and more telephone lines needed every day. Want to reach out and touch someone? You need representation theory.
• F. Bien, “Construction of telephone networks by group representations”, Notices A. M. S. 36(1989)5-22
• Nonlinear network problems.This is cheating a little since the works in the reference below really use the theory of Lie groups instead of representation theory itself. Still, there is a tangential relation at least between representation theory of Lie groups and the solution to certain nonlinear network problems.
• C. Desoer, R. Brockett, J. Wood, R. Hirshorn,
A. Willsky, G. Blankenship, Applications of Lie group theory to nonlinear network problems, (Supplement to IEEE Symposium on Circuit Theory, 1974), Western Periodicals Co., N. Hollywood, CA, 1974
• Control theory.
• R. W. Brockett, “Lie theory and control systems defined on spheres”, SIAM J on Applied Math 25(1973) 213-225
• Robotics.The future is not in plastics (see the movie “The Graduate“) but in robotics.
How do you figure out their movements before building them? You guessed it, using representation theory.

• G. Chirikjian, “Determination and synthesis of discretely actuated manipulator workspaces using harmonic analysis”, in Advances in Robotic Kinematics, 5, 1996, Springer-Verlag
• G. Chirikjian and I. Ebert-Uphoff, “Discretely actuated manipulator workspace generation by closed-form convolution”, in ASME Design Engineering Technical Conference, August 18-22 1996
• Radar design.W. Schempp, Harmonic analysis on the Heisenberg nilpotent Lie group, with
applications to signal theory
, Longman Scientific & Technical, New York (Copublished in the U.S. with Wiley), 1986.
• Antenna design.B. Hassibi, B. Hochwald, A. Shokrollahi, W. Sweldens, “Representation theory for high-rate multiple antenna code design,” 2000 preprint (see A. Shokrollahi’s site for similar works).
• Design of stereo systems.We’re talkin’ quadrophonic state-of-the-art.
• K. Hannabus, “Sound and symmetry”, Math. Intelligencer, 19, Fall 1997, pages 16-20
• Coding theory. Interesting progress in coding theory has been made using group theory and representation theory. Here are a few selected references.
• F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes,
North-Holland/Elsevier, 1993 (8th printing)
• I. Blake and R. Mullin, Mathematical Theory of Coding, Academic Press, 1975
49(1995)215-223
• J.-P. Tillich and G. Zemor,
“Optimal cycle codes constructed from Ramanujan graphs,” SIAM J on Disc. Math. 10(1997)447-459
• H. Ward and J. Wood, “Characters and the equivalence of codes,” J. Combin. Theory A 73348-352
• J. Lafferty and D. Rockmore, “Spectral Techniques for Expander Codes” , (Extended Abstract) 1997 Symposium on Theory of Computation (available
at  Dan Rockmore’s web page)
• Mathematical physics.
Any complete list of books and papers in this field which use representation theory would be much too long for the limited goal we have here (which is simply
to list some real-world applications). A small selection is given below.

• Differential equations (such as the heat equation, Schrodinger wave equation, etc).M. Craddock, “The symmetry groups of linear partial differential equations
and representation theory, I” J. Diff. Equations 116(1995)202-247
• Mechanics.
• D.H. Sattinger, O.L. Weaver, Lie Groups and Algebras With Applications to Physics, Geometry, and Mechanics (Applied Mathematical Sciences, Vol 61) , Springer Verlag, 1986
• Johan Belinfante, “Lie algebras and inhomogeneous simple materials”,
SIAM J on Applied Math 25(1973)260-268
• Models for elementary particles.
• Quantum mechanics.
• Eugene Wigner, “Reduction of direct products and restriction of representations to subgroups: the everyday tasks of the quantum theorists”, SIAM J on Applied Math 25(1973) 169-185
• V. Vladimirov, I. Volovich, and E. Zelenov, “Spectral theory in p-adic quantum mechanics and representation theory,” Soviet Math. Doklady 41(1990)40-44
• Y. Manin, “Reflections on arithmetical physics,” in Conformal invariance and string theory, Academic Press, 1989, pages 293-303
• V. Vladimirov, I. Volovich, and E. Zelenov, p-adic analysis and mathematical physics, World Scientific, 1994
• V. Vladimirov, “On the Freund-Witten adelic formula for Veneziano amplitudes,” Letters in Math. Physics 27(1993)123-131
• Mathematical chemistry.
• Spectroscopy.B. Judd, “Lie groups in Atomic and molecular spectroscopy”, SIAM J on Applied Math 25(1973) 186-192
• Crystallography.
• G. Ramachandran and R. Srinivasan, Fourier methods in crystallography,
New York, Wiley-Interscience, 1970.
• T. Janssen, Crystallographic groups, North-Holland Pub., London, 1973.
• J. Zak, A. Casher, M. Gluck, Y. Gur, The irreducible representations of space groups, W. A. Benjamin, Inc., New York, 1969.
• Molecular strucure of the Buckyball.
• F. Chung and S. Sternberg, “Mathematics and the buckyball”, American Scientist 83(1993)56-71
• F. Chung, B. Kostant, and S. Sternberg, “Groups and the buckyball”, in Lie theory and geometry, (ed. J.-L. Brylinski et al), Birkhauser, 1994
• G. James, “The representation theory for the Buckminsterfullerene,” J. Alg. 167(1994)803-820
• Knot theory (which, in turn, has applications to modeling DNA) uses representation theory. F. Constantinescu and F. Toppan, “On the linearized Artin braid representation,” J. Knot Theory and its Ramifications, 2(1993)
• The Riemann hypothesis.
Think you’re going to solve the Riemann hypothesis without using
representation theory? Check this paper out: A. Connes, “Formule de traces en geometrie non-commutative et hypothese de Riemann”, C. R. Acad. Sci. Paris 323 (1996)1231-1236. (For those who argue that this is not a real-world application, we refer to Barry Cipra’s article, “Prime Formula Weds Number Theory and Quantum Physics,” Science, 1996 December 20, 274, no. 5295, page 2014, in Research News.)
• Circuit design, statistics, signal processing, …
See the survey paper
D. Rockmore, “Some applications of generalized FFTs” in Proceedings of the DIMACS
Workshop on Groups and Computation, June 7-10, 1995 eds. L. Finkelstein and W. Kantor, (1997) 329–369. (available at  Dan Rockmore’s web page)
• Vision – See the survey papers by Jacek Turski:Geometric Fourier Analysis of the Conformal Camera for Active Vision, SIAM Review, Volume 46 Issue 2 pages 230-255, 2004 Society for Industrial and Applied Mathematics, and, Geometric Fourier Analysis for Computational Vision, JFAA 11, 1-23, 2005.

# Complements in the symmetric group

About 20 years ago I was asked a question of Herbert Kociemba, a computer scientist who has one of the best Rubik’s cube solving programs known. Efficient methods of storing permutations in $S_E$ and $S_V$ (the groups of all permutations of the edges $E$ and vertices $V$, respectively, of the Rubik’s cube) are needed, hence leading naturally to the concept of the complement of $S_m$ in $S_n$. Specifically, he asked if $S_8$ has a complement in $S_{12}$ (this terminology is defined below). The answer is,
as we shall see, ”no.” Nonetheless, it turns out to be possible to introduce a slightly more general notion of a “$k$-tuple of complementary subgroups” (defined below) for which the answer to the analogous question is ”yes.”

This post is a very short summary of a paper I wrote (still unpublished) which can be downloaded here.

# Splitting fields of representations of generalized symmetric groups, 8

In this post, we give an example.

Let $G=C_3^8\, >\!\!\lhd \, S_8$ and let

$\pi = \theta_{\mu,\rho}=Ind_{G_\mu}^G(\mu\cdot \tilde{\rho}),$

where $\mu$ is a character of $C_3^8$ and $\rho$ is an irreducible representation of its stabilizer in $S_8$, $(S_8)_\mu$.

The real representations $\pi$ of $G$ are the ones for which

1. $\mu$ is represented by a character of the form

$(1,1,1,1,1,1,\omega,\omega^2) \ {\rm or}\ (1,1,...,1),$

and $\rho$ anything, or

2. $\mu$ is represented by a character of the form

$(1,1,1,1,\omega,\omega,\omega^2,\omega^2), \rho_1=(\pi_1,\pi_2,\pi_2)\in (S_4)^*\times (S_2)^*\times (S_2)^*,$

or

3. $\mu$ is represented by a character of the form

$(\omega,\omega,\omega,\omega,\omega^2,\omega^2,\omega^2,\omega^2), \rho_1=(\pi_2,\pi_2)\in (S_4)^*\times (S_4)^*,$

or

4. $\mu$ is represented by a character of the form

$(1,1,\omega,\omega,\omega,\omega^2,\omega^2,\omega^2), \rho_1=(\pi_1,\pi_2,\pi_2)\in (S_2)^*\times (S_3)^*\times (S_3)^*.$

The complex representations of $G$ are: the representations
whose characters have at least one complex value. Such representations $\pi = \theta_{\mu,\rho}$ are characterized by the fact that $(\mu,\rho)$ is inequivalent to $(\overline{\mu},\rho)$ under the obvious $S_8$-equivalence relation (which can be determined from the equivalence relation for representations in $G^*$).

The complex representations of $G$ are the remaining representations not included in the above list.

There are no quaternionic representations of $G$.

The claims above follow from the fact that a representation
$\theta_{\rho,\mu}$ is complex if and only if $\mu$ is not self-dual.

# Splitting fields of representations of generalized symmetric groups, 7

In this post, we discover which representations of the generalized symmetric group $G = S_n\ wr\ C_\ell = C_\ell^n\, >\!\!\lhd \, S_n$ can be realized over a given abelian extension of ${\mathbb{Q}}$.

Let $\theta_{\mu,\rho}\in G^*$ be the representation defined previously, where $\rho\in ((S_n)_\mu)^*$.

Let $K\subset {\mathbb{Q}}(\zeta_\ell)$ be a subfield, where $\zeta_\ell$ is a primitive $\ell^{th}$ root of unity. Assume $K$ contains the field generated by the values of the character of $\theta_{\mu,\rho}$. Assume $K/{\mathbb{Q}}$ is Galois and let $\Gamma_K=Gal({\mathbb{Q}}(\zeta_\ell)/K)$. Note if we regard $C_\ell$ as a subset of ${\mathbb{Q}}(\zeta_\ell)$ then there is an induced action of $\Gamma_K$ on $C_\ell$,

$\sigma:\mu \longmapsto \mu^\sigma, \ \ \ \ \ \ \ \ \ \mu\in (C_\ell)^*,\ \ \sigma\in \Gamma_K,$

where $\mu^\sigma(z)=\mu(\sigma^{-1}(z))$, $z\in C_\ell$. This action extends to an action on $(C_\ell^n)^*=(C_\ell^*)^n$.

Key Lemma:
In the notation above, $\theta_{\mu,\rho}\cong\theta_{\mu,\rho}^\sigma$ if and only if $\mu$ is equivalent to $\mu^\sigma$ under the action of $S_n$ on $(C_\ell^n)^*$.

Let

$n_\mu(\chi)=|\{i\ |\ 1\leq i\leq n,\ \mu_i=\chi\}|,$

where $\mu=(\mu_1,...,\mu_n)\in (C_\ell^n)^*$ and $\chi\in C_\ell^*$.

Theorem: The character of $\theta_{\mu,\rho}\in G^*$ has values in $K$ if and only if $n_\mu(\chi)=n_\mu(\chi^\sigma)$,
for all $\sigma\in \Gamma_K$ and all $\chi\in C_\ell^*$.

This theorem is proven in this paper.

We now determine the splitting field of any irreducible character of a generalized symmetric group.

Theorem: Let $\chi=tr(\theta_{\rho,\mu})$ be an irreducible character of $G=S_n\ wr\ C_\ell$. We have

$Gal({\mathbb{Q}}(\zeta_\ell)/{\mathbb{Q}}(\chi))= Stab_\Gamma(\chi).$

This theorem is also proven in this paper.

In the next post we shall give an example.

# Splitting fields of representations of generalized symmetric groups, 6

This post shall list some properties of the Schur index $m_F(G)$ in the case where $G = S_n\ wr\ C_\ell$ is a generalized symmetric group and $F$ is either the reals or rationals.

Let $\eta_k(z)=z^k$, for $z\in C_\ell$, $1\leq k\leq \ell$.

Theorem: Let $G = S_n\ wr\ C_\ell$. Let $\mu=(\eta_{e_1},...,\eta_{e_n})\in (C_\ell^n)^*$, for some $e_j\in \{0,...,\ell-1\}$, and let $\rho\in (S_n)_\mu^*$. Let
$\chi$ denotes the character of $\theta_{\mu,\rho}$.

1. Suppose that one of the following conditions holds:
1. $4|\ell$ and $\overline{e_1+...+e_n}$ divides $\overline{\ell/4}$ in ${\mathbb{Z}}/\ell {\mathbb{Z}}$, or
2. $(e_1+...+e_n,\ell)=1$,

Then $m_{\Bbb{Q}}(\chi)=1$.

2. Suppose that one of the following conditions holds:
1. $(n,\ell)=1$, $4|\ell$, and $(e_1+...+e_n)x\equiv \ell /4\ ({\rm mod}\ \ell)$ is not solvable, or
2. $(n,\ell)=1$ and $(e_1+...+e_n,\ell)>1$.

Then $m_{\mathbb{Q}}(\chi\eta_1)=1$.

This theorem is proven in this paper. Benard has shown that $m_{\mathbb{Q}}(\chi)=1$, for all $\chi$ as in the above theorem.

Since the Schur index over ${\mathbb{Q}}$ of any irreducible character $\chi$ of a generalized symmetric group $G$ is equal to $1$, each such character is associated to a representation $\pi$ all of whose matrix coefficients belong to the splitting field ${\mathbb{Q}}(\chi)$.

What is the splitting field ${\mathbb{Q}}(\chi)$, for $\chi\in G^*$?

This will be addressed in the next post.