Is there any good software that solves equations of permutation group elements?

Question

I need to solve equations of permutation group elements (elements of $S_n$) that may not may not have solutions. The number of equations generally exceeds the number of variables. Is there any good software that can do this? If not, is there any method for me to do that on paper in an efficient way? Thank you very much!

One of the problems is: $p_{ij}\in S_3$ for $0\leq i<j\leq 3$. $p_{ij}$ has to satisfy the following conditions:

(1) $p_{12}p_{01}p_{23}=id$

(2) $p_{12}p_{23}p_{01}=id$

(3) $p_{01}p_{02}p_{12}p_{23}=(12)$

(4) $p_{01}p_{02}p_{23}p_{13}p_{12}=(132)$

(5) $p_{01}p_{23}p_{03}p_{13}p_{02}p_{12}=(13)$

(6) $p_{01}p_{23}p_{03}p_{02}p_{13}p_{12}=(13)$

(7) $p_{23}p_{13}p_{12}p_{01}=(23)$

(8) $p_{23}p_{13}p_{01}p_{02}p_{12}=(123)$

(9) $p_{23}p_{01}p_{03}p_{13}p_{02}p_{12}=(13)$

(10) $p_{23}p_{01}p_{03}p_{02}p_{13}p_{12}=(13)$

(11) $p_{01}$ and $p_{23}$ commutes.

(12) $p_{02}$ and $p_{13}$ commutes.

This particular problem can be simplified by reducing all sequences on the left that differ only by permuting adjacent commuting elements. So (2),(6),(9) and (10) can be removed.

Answer 1

There are just $6^6$ possible assignments of permutations to variables to check, so a brute-force solution is probably the simplest in this case.

In general, you want to enumerate the possible solutions, using the equations as early as possible to cut down on the branching. The more equations the better! Thus in this case you might have pseudocode something like

for each p01 in S3
  for each p23 that commutes with p01
     p12 = p23^(-1) p01^(-1)  # from equation (1)
     p02 = p01^(-1) (12) p23^(-1) p12^(-1) # from equation (3)
     p13 = p23^(-1) p12^(-1) p01^(-1) (123) p12^(-1) # from equation (4)
     if p13 commutes with p02
        p03 = p23^(-1) p01^(-1) (13) p12^(-1) p02^(-1) p13^(-1)
        if (all the other conditions hold)
           print solution (p01 p02 p03 p12 p13 p23)

---

Update by Alexander K.: just to illustrate how this pseudocode may be straightforwardly rewritten in GAP :

S3:=SymmetricGroup(3);
for p01 in S3 do
  for p23 in Centraliser(S3,p01) do
    p12 := p23^(-1)*p01^(-1); # from equation (1)
    p02 := p01^(-1)*(1,2)*p23^(-1)*p12^(-1); # from equation (3)
    p13 := p23^(-1)*p12^(-1)*p01^(-1)*(1,2,3)*p12^(-1); # from equation (4)
    if p13*p02 = p02*p13 then
      p03 := p23^(-1)*p01^(-1)*(1,3)*p12^(-1)*p02^(-1)*p13^(-1);
      if true then # replace by checking that all the other conditions hold
        Print([p01,p02,p03,p12,p13,p23],"\n");
      fi;
    fi;
  od;
od;      

Pasting it in GAP produces five solutions - if you will extend it by adding further checks, there may be less.

Answer 2

I am actually going to back up the answer (in slightly more generality) given by Robert Israel, and address the comments you made there.

I would guess that the number of equations is not a big problem, the difficulty will be more focused on the number of variables (involved in each equation) and the size of the group. The reason why it is not a big deal if there are say 200 equations is that only a very small collection of elements are going to satisfy more than a small number of the equations; as soon as one is failed, you can stop. Moreover, you can use a collection of equation involving only a small subset of the variables as an intermediate step.

That being said, you can use your equations to shrink down the number of variables to consider by a large margin. In your example, you can deduce that $p_{01}$ and $p_{23}$ commute, so $p_{23}$ is in the centralizer of $p_{12}$. Then using the other equations you can show that $$\begin{array}{ll} p_{02} & = p_{01}^{-1}(1 \ 2)p_{01}\\ p_{12} & = p_{01}^{-1}p_{23}^{-1}\\ p_{13} & = (1 \ 2 \ 3)p_{01}^{-1}p_{23}^{-1}\\ p_{03} & = p_{01}^{-1}p_{23}^{-1}(1 \ 3)p_{23}(1 \ 2)p_{01}(1 \ 2 \ 3)p_{01}^{-1}p_{23}^{-1} \end{array}$$ By making $6$ choices of $p_{01}$ and then choosing $p_{23}$ from the centralizer, there are only $11$ total possibilities instead of $6^6$.

Starting with $10$ variables in $S_{5}$ gives $120^{10}$ possible selections, which is a lot to "brute force" through, but if you bring it down to really choosing maybe $7$ variables (or possibly less), and each chosen from some restricted subset of $S_{5}$, it is realistic to loop through no matter how many equations.

Answer 3

You could do this with a constraint solver, such as Savile Row ( http://savilerow.cs.st-andrews.ac.uk/ ). While this tool does not support permutations, and permutation multiplication, directly, you can map the problem to integers fairly easily.

This wouldn't use any group theory techniques at all, just tackle the problem as permutations with search, but the performance would (I expect) be very good. If you want, I could write an example of how to transform your problem into the input of Savile Row.