replacement - How to transform abstract finite group to permutation group?

It seems that Mathematica only has group functionality for permutation groups? Then there is a step to transform the abstract finite one to a permutation one.

As an example, consider the following problem

Suppose $G=$, try to compute $ab^2ab^2a$.

It can proceed by viewing the elements of group just as a string, and the rule of group can be view as a rule of string replace. Any way, I would like to use NonCommutativeMultiply instead:

Firstly, let us define the rule, basically, we only need to define the rule for $ab$ and $ba$, since whenever we know how to commute these two generators, then we can use the fact $a^2=1=b^3$ to simplify our expression. It is not hard to compute $ab=b^2a$, $ba=ab^2$:

rel = {c___ ** a ** a ** d___ :> c ** i ** d, 

  c___ ** b ** b ** b ** d___ :> c ** i ** d, 
  c___ ** a ** b ** d___ :> c ** b ** b ** a ** d, 
  c___ ** b ** a ** d___ :> c ** a ** b ** b ** d , a___ ** i :> a, 
  i ** a___ :> a}

Now, let us define the set of group elements. Since $a$ is a order 2 element and $b$ is order $3$, we know that $G$ must be a subgroup of order $6=o(a)\times o(b)$, thus the elements can be expressed by

set = {i, a, b, b ** b, a ** b, b ** a}

Lastly, we can compute what's the results of $a$ multiply from left:

a ** # & /@ set/.rel

The problem: It seems my rule has not do the function of simplify the expression, as you can see the results is

{a, NonCommutativeMultiply[i], b ** b ** a, b ** b ** a ** b, i ** b, 
   b ** b ** a ** a}

the element b**b**a**a should be b**b, so please help me to correct the rule?

The correct result should be

aset = {a, i, a ** b, b ** a, b, b ** b}

form which we can find the permutation by

FindPermutation[set, aset]

which gives

Cycles[{{1, 2}, {3, 5}, {4, 6}}]

Answer

For simplicity, let's set

ncm[a__] := NonCommutativeMultiply[a]

My recommendation for this problem is to choose a "normal order" for the group elements. That is, I would choose to represent the group elements in such a way that all the a's are to the left of the b's. To do this, we define our set of replacements in such a way that b's always move to the right:

rel = {ncm[c___, a, a, d___] :> ncm[c, i, d]

  , ncm[c___, b, b, b, d___] :> ncm[c,i, d]
  , ncm[c___, b, b, a, d___] :> ncm[c, a, b, d]
  , ncm[c___, b, a, d___] :> ncm[c, a, b, b, d]
  , ncm[a__, i] :> ncm[a]
  , ncm[i, a__] :> ncm[a]
  , ncm[a_] :> a
 }

This guarantees that when we apply the rules repeatedly (which we have to do), the process will eventually terminate.

Then, we get the group elements into normal order by using ReplaceRepeated with the replacement rules rel:

set = {i, a, b, b ** b, a ** b, b ** a} //. rel
(* {i, a, b, b ** b, a ** b, a ** b ** b} *)

So, instead of using b ** a as one of the elements, we use the slightly more complicated (but it turns out easier to use) a ** b ** b.

Finally, then, multiplication on the left by a results in

aset = a ** # & /@ set //. rel
(* {a, i, a ** b, a ** b ** b, b, b ** b} *)

and

FindPermutation[set, aset]

(* Cycles[{{1, 2}, {3, 5}, {4, 6}}] *)

---

Brief explanation

To answer your questions:

• 
  

  NonCommutativeMultiply has very little rules associated with it. In particular, ncm[a] doesn't evaluate, i.e. it just evaluates to ncm[a]. So we have to add the rule that if we have ncm[i], for instance, this will evaluate to i.

  
  


• 
  
  

  _ is Blank. It is a pattern that will match any single expression. __ is BlankSequence. It is a pattern will match any sequence of one or more expressions. ___ is BlankNullSequence. It will match any sequence of expressions, including the Null Sequence. Meditate on the results of these three evaluations:

  
  

  {f[], f[a], f[a, b]} /. f[_] :> f[1]

  
  

  {f[], f[a], f[a, b]} /. f[__] :> f[1]

  
  

  {f[], f[a], f[a, b]} /. f[___] :> f[1]