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

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.

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

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