I have worked on some functions that, given a permutation group G, and an
element r of G, the functions produce an abstract word such that
I have worked on some functions that work with the word problem for
permutation groups. The functions are elaborations on things written by Peter
Webb. The idea of my functions is this:
Let G be a permutation group generated by [p1..pn].
Define G.abstractGenerators to be a list [a1..an] of abstract generators
Create something like the stabilizer chain, that is actually a chain of
stabilizer subgroups. To make sure that the generators do not grow
exponentially in length, make preferences in the choice of generators to those
of shortest lengths.
Given an element r of G, produce a word r1 in [p1..pn], using the
stabilizer chain in much the same way that "in" works, but keeping track of
what left transversals are multiplied together.
As a sample run, I show an example from Rubik's cube:
gap> Read("abgens2");
gap> Read("cube");
The group 'cube' represents the operations of the Rubik's cube:
+----------+
| 1 2 3 |
| 4 R 5 |
| 6 7 8 |
+----------+----------+----------+----------+
| 9 10 11 | 17 18 19 | 25 26 27 | 33 34 35 |
| 12 W 13 | 20 Y 21 | 28 B 29 | 36 G 37 |
| 14 15 16 | 22 23 24 | 30 31 32 | 38 39 40 |
+----------+----------+----------+----------+
| 41 42 43 |
| 44 O 45 |
| 46 47 48 |
+----------+
To draw the cube at any time, type 'drawcube()'.
To draw a particular permutation g, type 'DrawCube(g)'.
The cube is generated by the clockwise rotations of the sides,
R, W, Y, B, G, O for Red, White, Yellow, Blue, Green, and Orange.
They may also be referred to respectively as
top, left, front, right, rear, bottom
gap> l := [18,20,17,4,21,19,5,23,22,15,24,31,36,34,33,37,35,39,38,40];
[ 18, 20, 17, 4, 21, 19, 5, 23, 22, 15, 24, 31, 36, 34, 33, 37, 35, 39, 38,
40 ]
gap> qube := ShallowCopy(cube);
cube
gap> qube.name := "qube";
"qube"
gap> s := Runtime();MakeAbStabChain(cube);e := Runtime();e-s;MakeAbStabChain(qube,l); Runtime()-e;
5100
53733
48633
43333
gap> ### 48.633 seconds to make the stabilizer chain for cube
gap> ### 43.333 seconds to make the stabilizer chain for qube
gap> r := Random(cube);
( 1,22,38, 9,41,48,35,16,32)( 2, 5,28,18,42,44,12,47,10,45,34,26,21, 7,23,15,
37,39, 4,31)( 3,40,24,11,33,14,30, 6,27,46,43,17)( 8,25,19)(13,20)
gap> s := Runtime();rc := FactorPermGroupElement(cube,r);;e := Runtime();e-s;
97166
97166
0
gap> s := Runtime();rq := FactorPermGroupElement(qube,r);;e := Runtime();e-s;
97216
97216
0
gap> LengthWord(rc);
1219
gap> LengthWord(rq);
781
gap> s := Runtime();rc1 := Shrink(cube,rc);e := Runtime();e-s;
97350
G^-1*W*G^-1*O*R*O*B*G*R^-1*G^-1*O^-2*G*R*G^-1*B^-1*O^2*W*O*W^-1*R^-1*Y^-1*B*Y*\
B^-1*Y*O^-1*Y^-1*B*Y^-1*B^-1*Y*O*Y*O^-1*Y^-1*O*R*W*R^-1*Y^-1*R*W*R^-1*Y^-1*B*Y\
*B^-1*O^-1*G*R*Y*R^-1*G^-1*Y*B*G*R^-1*G^-1*Y^-1*R*W*R^-1*B*G*R*G^-1*Y^-1*W*G*W\
^-1*R*W^-1*R^-1*G^-2*O^-1*R^-1*G*R*Y*R^-1*G^-1*Y^-1*R*W^-1*R^-1*B*G*R^-1*G^-1*\
B*Y*B^-1*O^-1*B^-1*R*W*R^-1*W*G^-1*W^-1*G^-2*O^-1*Y*R^-1*Y*R*G^-1*B^-1*G*R*G^-\
1*B^-1*R*W^-1*R^-1*B^-1*G*R^-2*G^-1*W*G*W^-1*R*W^-1*R^-1*G*Y^-1*O^-2*W^-1
130833
33483
gap> ### 33.483 seconds to "Shrink" rc using cube
gap> LengthWord(rc1);
135
gap> s := Runtime();rq1 := Shrink(qube,rq);e:=Runtime();e-s;LengthWord(rq1);
130950
G^-2*O*G^-1*O^-1*B*O^-1*B^-1*O*G^-1*O^-1*B*O*B^-1*O*G*O^-2*B*O*B^-1*O*G*O^-1*B\
*O^-1*B^-1*G*B*O*B^-1*O^-1*G^-2*O*G*O^-1*G*O*G^-1*O^-1*G*B*O^-1*B^-1*G*B*O*B^-\
1*O^-1*G^-2*B*O*B^-1*O^-1*G*O*G^-1*O^-1*G*O^2*B*G^-1*B^-1*O*B*G*B^-1*O*B*O*B^-\
1*G^-1*O*B*G^-1*B^-1*O^-1*G^-1*B*O^-1*B*G^-1*O^-2*W^-1*G*W*O*W^-1*G^-2*W*B*O*W\
*O^-1*G*B*O^-1*Y*B^-1*Y^-1*O^-1*W^-1
151366
20416
107
gap> ### 20.416 seconds to "Shrink" rq using qube
You may email me for the files.
-Philip Osterlund