> < ^ Date: Mon, 05 Feb 1996 12:02:08 -0500
> < ^ From: David Joyner <wdj@usna.edu >
> ^ Subject: Shrink/ AbStab.g (reply)

Dear Forum and Martin Schoenert:

I want to thank everyone for their kind responses regarding my GRAPE/
Cayley graph question and my AbSTab.g/Shrink question.
I hope I am not beating this poor AbStab.g horse/thread to death but I
still am having problems with the Shrink command which I cannot
resolve. I hope I am not wasting bandwidth but I would like to
respond in the hopes of clarifying the actual result which, to me,
suggests that Shrink might be the cause of the problem. (Though quite
possibly I'm wrong.)

From GAP-Forum-Sender@Math.RWTH-Aachen.DE Fri Feb 2 09:14 EST 1996
Sender: GAP-Forum-Sender@Math.RWTH-Aachen.DE
Reply-To: GAP Forum <GAP-Forum-Reply@Math.RWTH-Aachen.DE>
X-Miles: GAP Forum article 818 accepted at 02 Feb 96 13:51 +0100
Date: Fri, 02 Feb 96 12:46:00 +0100 (MET)
From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de>
To: Multiple recipients of list <GAP-Forum@Math.RWTH-Aachen.DE>
Subject: Re: Re: AbStab.g
Content-Type: text
Content-Length: 3732

W. David Joyner wrote in his e-mail message of 1996/01/31

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,

I ran the calculation again. For the 2-cycle, I got back a (long) word using
FactorPermGroupElement and two different shorter words using Shrink twice.
Then I converted them all into MAPLE notation and plugged them each into
my MAPLE implementation for the masterball. The long work (using FactorPermGroupElement)
worked as expected, while *neither* of the shorter words (using Shrink) worked. This
makes me think that there is something wrong with Shrink. I did the same
thing with a 3-cycle and all of the words worked. The only problem, which
I have duplicated 3 or 4 times now, is with 2-cycles. It is possible that
I am causing the mistake in converting to MAPLE notation, of course, but I don't see
how since I am using the same procedure for all the words and it is only
the words obtained from Shrink applied to a 2-cycle which I have a problem

the ``word'' returned by Shrink is *not* equal to the ``word'' returned
by FactorPermGroupElement. This makes me suspicious.

Well there are many words representing a particular element of your
group. 'FactorPermGroupElement' simply finds one such word. 'Shrink'
takes such a word, and then tries to find a shorter word representing the
same element. Thus there is no reason that 'FactorPermGroupElement' and
'Shrink' should return the same word. In fact one would usually hope
that 'Shrink' returns a different word.

Good point. I misunderstood the meaning of GAP's boolean = function.

Maybe you are confused by the reording of the generators? Since you said

Possibly, but as I said above I am using the same procedure to convert between
the generators and so far, except for the case of a word obtained by Shrink
on a 2-cycle, the conversion seems to be correct.

'gen:=Set([f1,f2,f3,f4,r1,r2,r3,r4]);', GAP reorders the generators, so
'g1' corresponds to 'r4', 'g2' corresponds to 'r3', 'g3' corresponds to 'r2',
'g4' corresponds to 'f4', 'g5' corresponds to 'f3', 'g6' corresponds to 'f2',
and 'g7' corresponds to 'r1'. I must confess that I don't understand
why you apply 'Set' to the generators list, why not simply take it as it is?

A better idea. I thought MinGenSet required a set but I'll just use Group

By the way. The banner in the log says you are still running GAP 3.2.
The latest release is GAP 3.4.3.


You also say:

gap> map( G, cycle2a );
( 1, 2)
gap> map( G, cycle2b );
( 1, 2)

which implies that the long ('FactorPermGroupElement') word equals the short
('Shrink') word obtained from the 2-cycle. Good point. So, on one hand Shrink is
correct but on the other it seems to produce an incorrect result (in MAPLE). I don't
understand the problem. Note that a 2-cycle is not possible in the Rubik's cube
group (though 3-cycles are), so that my experience does not appear to be inconsistent
with other people's use of Shrink for the Rubik's cube.

-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]