Complements in the symmetric group

Almost 20 years ago I was asked a question by 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” for which the answer to the analogous question is ”yes.”

This post is a very short summary of part of a paper I wrote (still unpublished) which can be downloaded here. This post explains the ”no” part of the answer. For the more technical ”yes” part of the answer, see the more complete pdf version.

Notation: If X is any finite set then

  • |X| denotes the number of elements in X.
  • S_X denotes the symmetric group on X.
  • S_n denotes the symmetric group on \{1,2,...,n\}.
  • A_n denotes its alternating subgroup of even permutations.
  • C_n denotes the cyclic subgroup of S_n generated by the n-cycle (1,2,...,n).
  • M_{10} denotes ”the Mathieu group of degree $10$” and order $720=10!/7!$, which we define as the subgroup of S_{10} generated by (2,6,10,7)(3,9,4,5) and (1,5)(3,8)(4,10)(7,9).
  • M_{11} denotes the Mathieu group of degree 11 and order 7920=11!/7! generated by (1,2,3,4,5,6,7,8,9,10,11) and (3,7,11,8)(4,10,5,6).
  • M_{12} denotes the Mathieu group of degree 12 and order 95040=12!/7! generated by (2,3,5,9,8,10,6,11,4,7,12) and (1,12)(2,11)(3,10)(4,9)(5,8)(6,7).
  • For any prime power q, {\Bbb F}_q denotes the finite field with q elements.
  • AGL_n({{\Bbb F}}_q) denotes the affine group of transformations on {\Bbb F}_q^n of the form \vec{v}\longmapsto A\vec{v}+\vec{a}, where A\in GL_n({{\Bbb F}}_q) and \vec{a} \in {\Bbb F}_q^n.

If G is a finite group and G_1,G_2 are subgroups then we say G_2 is the complement of G_1 when

  • G_1\cap G_2=\{1\}, the identity of G,
    and
  • G=G_1\cdot G_2=\{g_1g_2\ |\ g_1\in G_1,\ g_2\in G_2\}.

Let X denote a finite set. If G is a subgroup of S_X and x\in X then we let G_x denote the stabilizer of x in G:
G_x=\{ g\in G\ |\ g(x)=x\}.

Let G be a permutation group acting on a finite set X (so G is a subgroup of the symmetric
group of X, S_X). Let k\geq 1 be an integer and let
X^{(k)}=\{{\rm distinct\ }k{\rm -tuples\ in\ }X\} =\{(x_1,x_2,...,x_k)\ |\ x_i\not= x_j,\ 1\leq i \textless j\leq k\}.
We say G acts k-transitively on X if G acts transitively on X^{(k)} via the ”diagonal” action
g:(x_1,x_2,...,x_k)\longmapsto (g(x_1),g(x_2),...,g(x_k)).

If G acts transitively on X and G_x=1 for some (hence all) x\in X then we say G acts regularly on X. If G acts k-transitively on X and acts regularly on X^{(k)} then we say G acts sharply k-transitively on X.

The classification of k-transitive groups, for k\geq 4, is to Jordan: A sharply k-transitive group, k\geq 4, must be one of the following.

  • k \geq  6: S_k , S_{k+1} and A_{k+2} only.
  • k = 5: S_5 , S_6 , A_7 and the Mathieu group M_{12}.
  • k = 4: S_4 , S_5 , A_6 and the Mathieu group M_{11}.

We give a table which indicates, for small values of n, which S_m have a complement in S_n.

n m complement of S_m in S_n
4 2 A_4
4 3 C_4
5 2 A_5
5 3 \langle (1,2,3,4,5),(2,3,5,4)\rangle   \cong AGL_1({{\Bbb F}}_5)
size 20
5 4 C_5
6 2 A_6
6 3 \langle (2,3,4,5,6),(3,4,6,5)\rangle   \cong PGL_2({{\Bbb F}}_5)
size 120
6 5 C_6
7 2 A_7
7 5 \langle (1,2,6,5,3,7),(1,4,3,2,5,6)\rangle   \cong AGL_1({{\Bbb F}}_7)
size 42
7 6 C_7
8 2 A_8
8 5 \langle (1,5,8,6,7,4),(1,5,8,7)(2,3,4,6)\rangle   \cong PGL_2({{\Bbb F}}_7)
size 336
8 6 AGL_1({{\Bbb F}}_8)
size 56
8 7 C_8
9 2 A_9
9 6 PGL_2({{\Bbb F}}_8)
size 504
9 7 AGL_1({{\Bbb F}}_9)
size 72
9 8 C_9
10 2 A_{10}
10 7 M_{10}
size 720
(PGL_2({{\Bbb F}}_9) is another)
10 9 C_{10}
11 2 A_{11}
11 7 M_{11}
size 7920
11 9 AGL_1({{\Bbb F}}_{11})
size 110
11 10 C_{11}
12 2 A_{12}
12 7 M_{12}
size 95040
12 9 PGL_2({{\Bbb F}}_{11})
=\langle (1,2,3,4,5,6,7,8,9,10,11),  (1,2,4,8,5,10,9,7,3,6),
(1,10)(2,5)(3,7)(4,8)(6,9)(11,12)\rangle
size 1320
12 11 C_{12}

Proposition: S_m has a complement in S_n if and only if there is an subgroup H of S_n such that

  1. H acts (n-m)-transitively on $\{1,2,…,n\}$,
  2. |H|=n(n-1)...(m+1)=n!/m!.

Example: S_{10} has not one but two non-isomorphic subgroups, M_{10} and PGL_2({{\Bbb F}}_9), of order 720=10!/7!, each of which acts 3-transitively on \{1,2,...,10\}. Thus S_7 has two non-isomorphic complements in S_{10}.

The statement below is the main result.

Theorem: The following statements hold.

  1. If n>2 is not a prime power or a prime power plus 1 then the only 1<m<n for which S_m has a complement in S_n are m=2 and m=n-1.
  2. If n>12 is a prime power and not a prime power plus 1 then the only 1<m<n for which S_m has a complement in S_n are m=2, m=n-2 and m=n-1.
  3. If n>12 is a prime power plus 1 but not a prime power then the only 1<m<n for which S_m has a complement in S_n are m=2, m=n-3 and m=n-1.
  4. If n>12 is both a prime power plus 1 and a prime power then the only 1<m<n for which S_m has a complement in S_n are m=2, m=n-3, m=n-2 and m=n-1.
  5. If $n\leq 12$, see the above table.

Grobner bases and permutation puzzles, according to Martin Kreuzer

This post is about some research Prof. Martin Kreuzer, at the Univ. of Passau, does which combines Grobner bases and solving permutation puzzles, such as the Rubik’s cube.

Prof. Martin Kreuzer giving a talk in Annapolis, 2013-12-04

Non-commutative Grobner Bases and Twisty Puzzles was the title of his talk (the link takes you to his slides, which he kindly allowed me to post).

Grobner bases were introduced in the mid-1960s (by Bruno Buchberger and, independently, Heisuke Hironaka), but in hindsight it is amazing they weren’t invented earlier. Indeed, Grobner bases arise when one tried to generalize long division of polynomials in one variable to polynomials of several variables. Non-commutative Grobner bases arise when one does not allow the variables to commute with each other. The main setting is where
G = \langle x_1,...,x_n\ |\ l_1=r_1,...,l_s=r_s\rangle is a finitely presented monoid,
K \langle X \rangle= \oplus_{g\in G} Kg = K/I is a monoid ring, and where
I = \langle l_1-r_1,...,l_s-r_s\rangle is a two-sided ideal generated by binomials.

First, Prof. Kreuzer introduces the non-commutative analogs of term ordering, leading term, and Grobner basis with respect to that ordering.

The non-commutative analog of the Buchberger procedure.


After developing enough theory, it turns out that the word problem in group theory can be re-expressed in terms of the membership problem for K \langle X \rangle.

Prof Kreuzer discussing aspects of computational group theory.

Martin Kreuzer defines a twisty puzzle as a special form of a permutation puzzle. Its pieces (usually called cubies) can be permuted by twisting certain faces of the puzzle. The cubies carry stickers defining their location in the solved puzzle. For example, with the Rubik’s Cube, the 54 stickers of a 3×3×3 cube can be permuted by 90 degree turns of the faces. The possible permutations form a group called the Rubik’s cube group. Then he gives the following definition and remarkable Theorem.

Definition: Let G be a twisty puzzle group given via a set X of generating twists.
(a) The graph whose vertices are the elements of G and whose edges are pairs of positions which differ by just one twist is called the Cayley graph of G.
(b) The diameter δ(G) of the Cayley graph of G is called God’s number for the twisty puzzle.
(c) An algorithm which produces for every scrambled position p an element of X∗ whose length is the distance (in the Cayley graph) from p to the solved position is called a God’s algorithm for the twisty puzzle.

Theorem (God’s Algorithm via Grobner Bases)
Let X be a set of twists (and their inverses) which generate the group of a twisty puzzle. Given a scrambled position p of the puzzle, perform the following steps:
(1) Compute a Grobner basis G of the defining ideal of the twisty puzzle group ring w.r.t. a length compatible word ordering.
(2) Find any word w ∈ X∗ representing a sequence of twists that result in the position p.
(3) Compute NRG(w) ∈ X∗ and return this word.

This is an algorithm which computes a word representing a shortest possible sequence of twists that produces p from the solved position.

This has even been implemented on a computer in Cocoa, for a permutation puzzle with a very small group.

Prof Kreuzer at his laptop running a “toy” implementation of God’s algorithm.

Another example of a Prohibition era cipher message

The following message, with Elizebeth Friedman‘s decryption, is a message from “Consolidated Exporters” (a Vancouver Canada company illegally importing liquor into the US) to one of its fleet of about 50 “black ships”, the SS Noble. (They are called “black ships” because they “rum run” without lights at night to avoid detection.)

ESF-B4-F15-p24_ss-noble-message

Many thanks to the George C. Marshall Foundation, Lexington, Virginia, for providing this reproduction!

If you were a math textbook …

If I were a Springer-Verlag Graduate Text in Mathematics, I would be David Eisenbud’s Commutative Algebra with a view towards Algebraic Geometry.

I am an attempt to write on commutative algebra in a way that includes the geometric ideas that played a great role in its formation; with a view, in short, towards Algebraic Geometry. I cover the material that graduate students studying Algebraic Geometry – and in particular those studying the book Algebraic Geometry by Robin Hartshorne – should know. The reader should have had one year of basic graduate algebra.

Which Springer GTM would you be? The Springer GTM Test

A 1932 memorandum on rum-runner’s cryptosystems

During the prohibition era, organized crime made phenomenal amounts of money through illegal smuggling. Eventually, their messages were enciphered. By the late 1920s and early 1930s, these cryptosystems became rather sophisticated. Here is a memorandum form Elizebeth Friedman to CMDR Gorman in January or 1932 which gives an indication of this sophistication.
EF-to-CMDR-Gorman_1932-01-28_p1
EF-to-CMDR-Gorman_1932-01-28_p2

Many thanks to the George C. Marshall Foundation, Lexington, Virginia, for providing this reproduction!

A 1926 message from “I Am Alone”

The I Am Alone, flying a Canadian flag, was a rumrunner sunk by Coast Guard patrol boats in the Gulf of Mexico in March, 1929. The USCG knew that the ship was not a Canadian owned-and-controlled vessel but the proof went down to the bottom of the ocean when it was sunk. The Canadian Government sued the United States for $365,000 and the ensuing legal battle brought world-wide attention. Elizebeth Friedman decoded the messages transmitted by the I Am Alone, and those messages proved that the boat was, in fact, not a Canadian owned-and-controlled vessel. The case actually went to a Commission, whose final report was issued in 1935. They found, thanks in part to Elizebeth Friedman, that the owners and controllers of the vessel were not Canadian and used the boat primarily for illegal purposes.

The image below is a scan of an intercepted message, dated 1926-02-15, from the I Am Alone.
ESF-B4-F14-p25_iam-alone-message
The writing is that of EF and you can make out her (mostly) deciphered message.

For more information, see, for example,
All Necessary Force”: The Coast Guard And The Sinking of the Rum Runner “I’m Alone” by Joseph Anthony Ricci, 2011, or
Listening to the rumrunners” by David Mowry, 2001.

The above image is courtesy of the Elizebeth S. Friedman Collection at the George C. Marshall Foundation, Lexington, Virginia. (If you make use of the image, please acknowledge the Marshall Foundation.)

Lester Hill’s “The checking of the accuracy …”, part 10

Construction of finite fields for use in checking

Let F_\Gamma denote a finite algebraic field with \Gamma elements. It is well-known that, for a given \Gamma, all fields F_\Gamma are “simply isomorphic”, and therewith, for our purposes, identical. We shall consequently refer, without restraint, to ”the field F_\Gamma.”

If p is a prime positive integer greater than 1, F_p is called, according to the terminology of Section 8, Example 2, a ”primary” field. Explicit addition tables, as was noted in section 8, are hardly required in deal ing with primary fields. The most useful of these fields, in telegraphic checking, are probably F_{23}, F_{29}, F_{31}, and F_{101}. The field $F_{101}$ will be considered in detail in what follows.

The number of elements in a non-primary finite algebraic field
is a power of a prime. If we have

q=p^k
where p and k are positive integers greater than 1, and p is prime, the non-primary field F_q may be constructed very easily by algebraic extension of the field F_p. Explicit addition table is needed when working with a non-primary field. Otherwise, checking operations are exactly the same as in primary fields.

Example: The field F_3 with the elements (marks) 0,1,2, has the tables

\begin{array}{r|*{3}{r}}  \multicolumn{1}{c|}  +&0&1&2\\\hline  {}0&0&1&2\\  {}1&1&2&0\\  {}2&2&0&1\\  \end{array}
\begin{array}{r|*{3}{r}}  \multicolumn{1}{c|}  \cdot &0&1&2\\\hline  {}0&0&0&0\\  {}1&0&1&2\\  {}2&0&2&1\\  \end{array}

By adjoining a root of the equation x^2=2, an equation which is irreducible in F_3, we easily obtain the field F_9 with marks

\alpha j+\beta
where \alpha and \beta denote elements of F_3. The marks of F_9 are thus

0,1,2,j,j+1,j+2,2j,2j+1,2j+2.
These marks (elements) are combined, in the rational field operations of F_9, according to the reduction formula j^2=2. If we label the marks of F_9 as follows

\begin{array}{ccccccccc}  0 & 1 & 2 & j & j+1& j+2& 2j& 2j+1& 2j+2\\  0 & 1 & a & b & c & d & e & f & g\\  \end{array}
the addition and multiplication tables of the field are given as in
Section 8, Example 1.

In a like manner, F_{27} can be obtained from F_3 by adjunction of a root of the equation x^3=x+1, which is irreducible in F_3 and F_9. The marks (elements) of F_{27} are

\alpha j^2+\beta j+\gamma,
where \alpha,\beta,\gamma are elements of F_3. They are combined, in the rational operations of F_{27} according to the reduction formula j^3=j+1.

Example: The field F_2 with the elements (marks) 0,1, has the tables

\begin{array}{r|*{2}{r}}  \multicolumn{1}{c|}  + &0&1\\ \hline  {}0&0&1\\  {}1&1&0\\  \end{array}
\begin{array}{r|*{2}{r}}  \multicolumn{1}{c|}  \cdot &0&1\\ \hline  {}0&0&0\\  {}1&0&1\\  \end{array}

By adjunction of a root of the equation x^5=x^2+1, which is irreducible in the fields F_2, F_4, F_8 and F_{16}, we easily obtain the field F_{32}. The marks of F_{32} are

\alpha j^4+\beta j^3+\gamma j^2+\delta j+\epsilon,
where \alpha,\beta,\gamma, \delta,\epsilon are elements of F_2; and these 32 marks are combined, in the rational operations of F_{32}, according to the reduction formula j^5=j^2+1.

Example: The field F_5 with the elements (marks) 0,1,2,3,4, has the tables

\begin{array}{r|*{5}{r}}  \multicolumn{1}{c|}  +&0&1&2&3&4\\\hline  {}0&0&1&2&3&4\\  {}1&1&2&3&4&0\\  {}2&2&3&4&0&1\\  {}3&3&4&0&1&2\\  {}4&4&0&1&2&3\\  \end{array}
\begin{array}{r|*{5}{r}}  \multicolumn{1}{c|}  \cdot &0&1&2&3&4\\\hline  {}0&0&0&0&0&0\\  {}1&0&1&2&3&4\\  {}2&0&2&4&1&3\\  {}3&0&3&1&4&2\\  {}4&0&4&3&2&1\\  \end{array}

By adjoining a root of the equation x^2=2, which is irreducible in F_{5}, we readily obtain the field F_{25}. The marks of F_{25} are

\alpha j+\beta ,
where \alpha,\beta are elements of F_5; and these 25 marks are combined, in the rational operations of F_{25}, according to the reduction formula j^2=2.

Of the non-primary fields, F_{25}, F_{27}, F_{32} are probably those which are most amenable to practical application in telegraphic checking.

mathematics problem 155

A colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his students, giving a prize of a cookie if they could solve it. Here is one of them.

Mathematics Problem, #155

We can represent a triangle with sides of length a, b, c by the ordered triple (a, b, c). Changing the order of the sides doesn’t change the triangle, so (a, b, c), (b, a, c), (b, c, a), (c, b, a), (c, a, b), and (a, c, b) all represent the same triangle. To avoid confusion, let’s agree to write (a, b, c) with a < b < c. We say that a triangle <I (a, b, c) is integral if a, b, and c are integers. How many integral triangles are there with longest side less than or equal to 100 ?

Mathematics Problem 154

A colleague Bill Wardlaw (March 3, 1936-January 2, 2013) used to create a “Problem of the Week” for his students, giving a prize of a cookie if they could solve it. Here is one of them.

Mathematics Problem, #154

Find the volume of the intersection of three cylinders, each of radius a, which are centered on the x-axis, the y-axis, and the z-axis. That is, find the volume of the three dimensional region


E = {(x,y,z) | x2 + y2 < a2, y2 + z2 < a2, z2 + x2 < a2}.

Lester Hill’s “The checking of the accuracy …”, part 9

We may inquire into the possibility of undisclosed errors occurring in the transmittal of the sequence:

\begin{array}{ccccccccccccccc}  f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 & f_9  & f_{10} & f_{11} & f_{12} & c_1 & c_2 & c_3 \\  5 & 17 & 13 & 21 & 0 & 8 & 6 & 0 & 11 & 0 & 11 & 11 & 6 & 15 & 2 \\  X & T & Y & P & V & Z & R & V & H & V & H & H & R & I & F \\  \end{array}

Invoking the theorem established in sections 4 and 5, and formulated at the close of section 5, we may assert:

  • (1) If not more than three errors are made in transmitting the fifteen letters of the sequence, and if the errors made affect the f_i only, the c_j being correctly transmitted, then the presence of error is certain to be disclosed.
  • (2) If not more than three errors are made, all told, but at least three of them affect the f_i, then the presence of error will enjoy only a

    1-{\rm in}-22^3\ \ \ \ \ (1-{\rm in}-10648)
    chance of escaping disclosure.

These assertions result at once from the theorem referred to. But a closer study of the reference matrix employed in this example permits us to replace them by the following more satisfactory statements:

  • (1′)
    If errors occur in not more than three of the fifteen elements of the sequence f_1f_2\dots f_{12}c_1 c_2 c_3, and if at least one of the particular elements f_{11}f_{12}c_2 is correctly transmitted, the presence of error will certainly be disclosed. But if exactly three errors are made, affecting presicely the elements f_{11}f_{12}c_2, the presence of error will enjoy a 1-in-22^2 (1-in-484) chance of escaping disclosure.
  • (2′)
    If more than three errors are made, then whatever the distribution of errors among the fifteen elements of the sequence, the presence of error will enjoy only a
    1-in-22^3 (1-in-10648) chance of escaping disclosure.

Assertions of this kind will be carefully established below, when a more important finite field is under consideration. The argument then made will be applicable in the case of any finite field. But it is worthwhile here to look more carefully into the exceptional distribution of errors which is italicized in (1′). This will help us note any weakness that ought to be avoided in the construction of reference matrices.

Suppose that exactly three errors are made, affecting precisely f_{11}f_{12}c_2. If the mutilated message is to check up, and the errors to escape disclosure, we must have (for error notations, see sections 4,5):

11\epsilon_{11}+12\epsilon_{12}=0,\ \ \   11^2\epsilon_{11}+12^2\epsilon_{12}=\delta_2,\ \ \   11^3\epsilon_{11}+12^3\epsilon_{12}=0.
These equations may be written:

11\epsilon_{11}+12\epsilon_{12}=0,\ \ \   6\epsilon_{11}+6\epsilon_{12}=\delta_2,\ \ \   20\epsilon_{11}+3\epsilon_{12}=0.
But 11\epsilon_{11}=-12\epsilon_{12} can be written 11\epsilon_{11}=11\epsilon_{12}, or \epsilon_{11}=\epsilon_{12}.
Etc. In this way, we find that the errors can escape disclosure if and only if

\epsilon_{11}=\epsilon_{12},\ \ \ {\rm and}\ \ \ \delta_{2}=12\epsilon_{11}.
The error \epsilon_{11} can be made quite arbitrarily. But then the values of \epsilon_{12} and \delta_2 are then completely determined. There is evidently a 1-in-484 chance – and no more – that the errors will fall out just right.

The trouble arises from the vanishing, in our reference matrix, of the two-rowed
determinant

\big{|}   \begin{array}{cc}  11 & 12 \\  11^3 & 12^3  \end{array}  \big{|} .
Note that

\big{|}   \begin{array}{cc}  11 & 12 \\  11^3 & 12^3  \end{array}  \big{|}   = 11\cdot 12\cdot  \big{|}   \begin{array}{cc}  1 & 1 \\  11^2 & 12^2  \end{array}  \big{|}   = 17 \big{|}   \begin{array}{cc}  1 & 1 \\  11^2 & 12^2  \end{array}  \big{|} =0,
since 11^2=12^2.

From the fact that \big{|}   \begin{array}{cc}  11 & 12 \\  11^3 & 12^3  \end{array}  \big{|} is the only vanishing determinant of any order in the matrix employed, all other assertions made in (1′) and (2′) are readily justified. This will be made clear in the following sections.

It will be advantageous, as shown more completely in subsequent sections, to employ reference matrices which contain the smallest possible number of vanishing determinants of any orders.