> < ^ Date: Wed, 31 Jan 1996 10:55:00 -0500
> < ^ From: David Joyner <wdj@usna.edu >
> < ^ Subject: Re: AbStab.g

----------
X-Sun-Data-Type: text
X-Sun-Data-Description: text
X-Sun-Data-Name: text
X-Sun-Charset: us-ascii
X-Sun-Content-Lines: 53

Dear Forum and Heiko Thei{\ss}en and Martin Sch\"onert:

Thanks for your response.

You said:

I have used the `AbStab.g' library quite a bit for Rubik's Cube. I
never encountered a problem at all. Could it be that the problems you
have with ``solutions'' not working in Maple arise because the model
you use in Maple is slightly different from the one used in GAP (e.g.,
different order of generators)? Note that the ``solutions'' found by

I don't believe so. I carefully determined all the generators used by abstab.g
in terms of my generators.

`AbStab.g' are still not optimal. In the case of Rubik's Cube, they
are usually about an order of magnitude too long.

I'll explain why I think abstab.g has an error. I used GAP and abstab.g
for the group of the masterball, which has size ~4.3x10^26. I usually
can eventually get the masterball into one of two ``nearly solved''
positions: one requiring a 2-cycle and the other requiring a 3-cycle.
Shrink in abstab.g gives a ~90 move long solution to the 3-cycle position
which works. I checked this on my maple implementation and by hand.
Shrink gives a slightly longer solution for the 2-cycle. It does
not work by my maple computer implementation nor by hand. Moreover,
the ``word'' returned by Shrink is *not* equal to the ``word'' returned
by FactorPermGroupElement. This makes me suspicious.

By the way: While trying to play with `AbStab.g' I have noticed that
the function `MakeAbStabChain' runs into an error in GAP V3R4P3, but
succeeds in GAP V3R4P2. The reason is that third update included a
modification of the function `List'. In GAP V3R4P2 the first argument
could have holes (even though the manual forbids this), so e.g.

List( [, 1 ], x -> x ^ 2 )  returned  [ 1 ]

while in GAP V3R4P3 this now results in an error. I suppose that your
experiments with `AbStab.g' were done in GAP V3R4P2 (or earlier). Is
this right?

I used gap3r4p2 at work and I used gap3r4p3 with the 3r4p2 library
at home with no errors of this kind.

Attached by a sun mailtool attachment is a history of a gap session
which produces the above described problem. Also included is a .g
file containing the group-theoretical data for the masterball group,
for anyone interested. I'm enclosing this because, based on this session,
I conjecture that Shrink in abstab.g has a bug. However, I would be
happy to hear of some other explanation for the problem.

                                            - David Joyner
----------
X-Sun-Data-Type: default
X-Sun-Data-Description: default
X-Sun-Data-Name: bug.txt
X-Sun-Charset: us-ascii
X-Sun-Content-Lines: 86


51 math65:/home/math6/wdj> gap
     ########            Lehrstuhl D fuer Mathematik
   ###    ####           RWTH Aachen
  ##         ##
 ##          #             #######            #########
##                        #      ##          ## #     ##
##           #           #       ##             #      ##
####        ##           ##       #             #      ##
 #####     ###           ##      ##             ##    ##
   ######### #            #########             #######
             #                                  #
            ##           Version 3              #
           ###           Release 2              #
          ## #           10 Feb 93              #
         ##  #
        ##   #  Alice Niemeyer, Werner Nickel,  Martin Schoenert
       ##    #  Johannes Meier, Alex Wegner,    Thomas Bischops
      ##     #  Frank Celler,   Juergen Mnich,  Udo Polis
      ###   ##  Thomas Breuer,  Goetz Pfeiffer, Hans U. Besche
       ######   Volkmar Felsch, Heiko Theissen, Alexander Hulpke
                Ansgar Kaup,    Akos Seress
                            For help enter: ?<return>
gap> LogTo("/home/math6/wdj/gap/games/bug.log");
gap> Read("/home/math6/wdj/gap/games/grpdata.g");
gap> Read("/home/math6/wdj/gap/new/AbStab.g");
The record 'descriptions' contains brief descriptions of the functions
in this file.
Functions of importance: MakeAbStabChain, FactorPermGroupElement, Shrink
gap> gen:=Set([f1,f2,f3,f4,r1,r2,r3,r4]);
[ (25,26,27,28,29,30,31,32), (17,18,19,20,21,22,23,24),
  ( 9,10,11,12,13,14,15,16), ( 4,31)( 5,30)( 6,29)( 7,28)(12,23)(13,22)(14,21)
    (15,20), ( 3,30)( 4,29)( 5,28)( 6,27)(11,22)(12,21)(13,20)(14,19),
  ( 2,29)( 3,28)( 4,27)( 5,26)(10,21)(11,22)(12,23)(13,24), (1,2,3,4,5,6,7,8),
  ( 1,28)( 2,27)( 3,26)( 4,25)( 9,20)(10,19)(11,18)(12,17) ]
gap> G:=MinGenSet(gen);
Group( (25,26,27,28,29,30,31,32), (17,18,19,20,21,22,23,24), ( 9,10,11,12,13,
 14,15,16), ( 4,31)( 5,30)( 6,29)( 7,28)(12,23)(13,22)(14,21)(15,20), ( 3,30)
( 4,29)( 5,28)( 6,27)(11,22)(12,21)(13,20)(14,19), ( 2,29)( 3,28)( 4,27)
( 5,26)(10,21)(11,22)(12,23)(13,24), (1,2,3,4,5,6,7,8) )
gap> 2_cycle:=(1,2);
(1,2)
gap> cycle2a:=FactorPermGroupElement(G,2_cycle);
g1^2*g5*g7*g5^-1*g1*g5*g7^-1*g5^-1*g1^-1*g5*g7*g5^-1*g1^-2*g5*g7^-1*g5^-1*g1^-\
1*g5*g7*g5^-1*g1^3*g5*g7^-1*g5^-1*g1*g5*g7*g5^-1*g1^-1*g5*g7^-1*g5^-1*g1^-3*g5\
*g7*g5^-1*g1^2*g5*g7^-1*g5^-1*g1^-2*g5*g7^-1*g5^-1*g1*g5*g7^3*g5^-1*g1*g5*g7^-\
3*g5^-1*g1^-1*g5*g7*g5^-1*g1^-2*g5*g7*g5^-1*g1^3*g5*g7^-1*g5^-1*g1^-2*g5*g7^-1\
*g5^-1*g1*g5*g7^3*g5^-1*g1*g5*g7^-3*g5^-1*g1^-1*g5*g7*g5^-1*g1^-1*g5*g7*g5^-1*\
g1^2*g5*g7^-1*g5^-1*g1*g5*g7*g5^-1*g1^-1*g5*g7^-1*g5^-1*g1^-3*g5*g7*g5^-1*g1^2\
*g5*g7^-1*g5^-1*g1^-2*g5*g7^-1*g5^-1*g1*g5*g7^3*g5^-1*g1*g5*g7^-3*g5^-1*g1^-1*\
g5*g7*g5^-1*g1^-1*g5*g7*g5^-1*g1^2*g5*g7^-1*g5^-1*g1^-2*g5*g7^-1*g5^-1*g1*g5*g\
7^3*g5^-1*g1*g5*g7^-3*g5^-1*g1^-1*g5*g7*g5^-1*g1^-2*g5*g7*g5^-1*g1^3*g5*g7^-1*\
g5^-1*g1^-2*g5*g7^-1*g5^-1*g1*g5*g7^3*g5^-1*g1*g5*g7^-3*g5^-1*g1^-1*g5*g7*g5^-\
1*g1^-1*g5*g7*g5^-1*g1^2*g5*g7^-1*g5^-1*g1*g5*g7*g5^-1*g1^-1*g5*g7^-1*g5^-1*g1\
^-3*g5*g7*g5^-1*g1^2*g5*g7^-1*g5^-1*g1^-2*g5*g7^-1*g5^-1*g1*g5*g7^3*g5^-1*g1*g\
5*g7^-3*g5^-1*g1^-1*g5*g7*g5^-1*g1^-1*g5*g7*g5^-1*g1^2*g5*g7^-1*g5^-1*g1^-2*g5\
*g7^-1*g5^-1*g1*g5*g7^3*g5^-1*g1*g5*g7^-3*g5^-1*g1^-1*g5*g7*g5^-1*g1^-2*g5*g7*\
g5^-1*g1^3*g5*g7^-1*g5^-1*g1^-2*g5*g7^-1*g5^-1*g1*g5*g7^3*g5^-1*g1*g5*g7^-3*g5\
^-1*g1^-1*g5*g7*g5^-1*g1^-1*g5*g7*g5^-1*g1^2*g5*g7^-1*g5^-1*g1*g5*g7*g5^-1*g1^\
-1*g5*g7^-1*g5^-1*g1^-3*g5*g7*g5^-1*g1^2*g5*g7^-1*g5^-1*g1^-2*g5*g7^-1*g5^-1*g\
1*g5*g7^3*g5^-1*g1*g5*g7^-3*g5^-1*g1^-1*g5*g7*g5^-1*g1^2*g5*g7*g5^-1*g1*g5*g7^\
-1*g5^-1*g1^-1*g5*g7*g5^-1*g1^-3*g5*g7^-1*g5^-1*g1*g5*g7*g5^-1*g1^2*g5*g7^-1*g\
5^-1*g1*g5*g7*g5^-1*g1^-1*g5*g7^-1*g5^-1*g1^-2
gap> cycle2b:=Shrink(G,cycle2a);
g1^-2*g5^-1*g1*g4^-1*g1*g4^-1*g1^-1*g7^2*g5^-1*g1^-1*g5^-1*g7^-3*g5^-1*g1^-1*g\
5^-1*g7*g5^-1*g1^2*g5^-1*g7*g5^-1*g1^-1*g5^-1*g7^-1*g5^-1*g1^2*g5^-1*g7*g5^-1*\
g1^-1*g5^-1*g7^-1*g5^-1*g1^-4*g5^-1*g7*g5^-1*g1*g5^-1*g7^-1*g5^-1*g1*g5^-1*g7^\
-2*g5^-1*g1^-1*g5^-1*g7*g5^-1*g1^-1*g5^-1*g7^-1*g5^-1*g1^2*g5^-1*g7^4*g5^-1*g1\
*g5^-1*g7^-3*g5^-1*g1^-1*g5^-1*g7*g5^-1*g1^2*g5^-1*g7^-1*g5^-1*g1*g5^-1*g7^3*g\
5^-1*g1*g5^-1*g7^-3*g5^-1*g1^-1*g5^-1*g7^2*g5^-1*g1^-1*g5^-1*g7^-1*g5^-1
gap> cycle2a=cycle2b;
false
gap> cycle2c:=Shrink(G,2_cycle);
g1^-2*g5^-1*g1*g4^-1*g1*g4^-1*g1^-1*g7^2*g5^-1*g1^-1*g5^-1*g7^-3*g5^-1*g1^-1*g\
5^-1*g7*g5^-1*g1^2*g5^-1*g7*g5^-1*g1^-1*g5^-1*g7^-1*g5^-1*g1^2*g5^-1*g7*g5^-1*\
g1^-1*g5^-1*g7^-1*g5^-1*g1^-4*g5^-1*g7*g5^-1*g1*g5^-1*g7^-1*g5^-1*g1*g5^-1*g7^\
-2*g5^-1*g1^-1*g5^-1*g7*g5^-1*g1^-1*g5^-1*g7^-1*g5^-1*g1^2*g5^-1*g7^4*g5^-1*g1\
*g5^-1*g7^-3*g5^-1*g1^-1*g5^-1*g7*g5^-1*g1^2*g5^-1*g7^-1*g5^-1*g1*g5^-1*g7^3*g\
5^-1*g1*g5^-1*g7^-3*g5^-1*g1^-1*g5^-1*g7^2*g5^-1*g1^-1*g5^-1*g7^-1*g5^-1
gap> cycle2b=cycle2c;
true
gap> quit;
258.33u 75.28s 33:19.81 16.6%
52 math65:/home/math6/wdj>
----------
X-Sun-Data-Type: default
X-Sun-Data-Description: default
X-Sun-Data-Name: grpdata.g
X-Sun-Charset: us-ascii
X-Sun-Content-Lines: 14

r1 := (1, 2, 3, 4, 5, 6, 7, 8);
r2 := (9, 10, 11, 12, 13, 14, 15, 16);
r3 := (17, 18, 19, 20, 21, 22, 23, 24);
r4 := (25, 26, 27, 28, 29, 30, 31, 32);
f1 := (1, 28)(2, 27)(3, 26)(4, 25)(9, 20)(10, 19)(11, 18)(12, 17);
f2 := (2, 29)(3, 28)(4, 27)(5, 26)(10, 21)(11, 22)(12, 23)(13, 24);
f3 := (3, 30)(4, 29)(5, 28)(6, 27)(11, 22)(12, 21)(13, 20)(14, 19);
f4 := (4, 31)(5, 30)(6, 29)(7, 28)(12, 23)(13, 22)(14, 21)(15, 20);
f5 := (5, 32)(6, 31)(7, 30)(8, 29)(13, 24)(14, 23)(15, 22)(16, 21);
f6 := (6, 25)(7, 32)(8, 31)(1, 30)(14, 17)(15, 24)(16, 23)(9, 22);
f7 := (7, 26)(8, 25)(1, 32)(2, 31)(15, 18)(16, 17)(9, 24)(10, 23);
f8 := (8, 27)(1, 26)(2, 25)(3, 32)(16, 19)(9, 18)(10, 17)(11, 24);
order_of_group := 437763136697395052544000000;
geners := Set([r1,r2,r3,r4,f1,f2,f3,f4,f5,f6,f7,f8]);

> < [top]