> < ^ From:

< ^ Subject:

John Neil writes in his mail of 21-Apr-92:

I love the extensions to GAP which allow it to perform operations on

finitely generated groups (since I'm a topologist by profession), but

have run into a problem of sorts. I have two presentations of the

same group (I know that they are isomorphic for other reasons) that I

would like to work with in GAP. The problem is, while GAP can

compute the order of the group quite easily for one of the

presentations, for the other it has EXTREME difficulty. The group is

of order 120 and I usually run GAP with 2MB of allocated storage.

However, GAP crashes on the second presentation with this memory

size. The only way I've been able to get it to compute the order was

to run GAP without the memory size restriction on a machine which has

128MB of resident memory....

gap> g := FreeGroup( 2, "g" ); Group( g.1, g.2 ) gap> g.relators := [ g.1^5*g.2^-24, g.2*g.1^2*g.2^-1*g.1^-3 ]; [ g.1^5*g.2^-24, g.2*g.1^2*g.2^-1*g.1^-3 ] gap> Size( g ); 120 gap> time; 2238310

GAP uses the Felsch strategy for the coset enumeration. Basically this

enumerates the words of the free group on two generators systematically

w.r.t. to length-lexicographical ordering. It uses the relators to

decide which words correspond to the same element in the group. Actually

in this case the group defined by < g.1, g.2 | g.2*g.1^2*g.2^-1*g.1^-3 >

is infinite, and GAP can enumerate the elements of this group

systematically (without coincendences). But GAP (and other

implementations of Felsch TC) has to enumerate 700000 words until the

first relator can be used to see that two words are the same element in

the group. This is why the enumeration takes so long. (Note that after

this first coincedence a total collapse happens, i.e., after this

coincedence and its consequences have been handled the coset table is

complete.)

A coset enumeration that uses the HLT strategy to define new cosets has

no problems with this group. This is because it enumerates the words of

the free group in such a way that relators can be used earlier. A hybrid

strategy that uses Felsch for the relators and HLT for the subgroup

generators (e.g., the coset enumerator in SPAS), also has no problems

with this group.

We intend to add the other strategies to GAP in a future release.

However, there is a simple trick that you can use. Note that the problem

with your group is the large length of the first generator. So the trick

is to reduce the length of this relator. To do this one introduces an

additional generator.

gap> g := FreeGroup( 3, "g" ); Group( g.1, g.2, g.3 ) gap> g.relators := [ g.1^5*g.3^-4, g.2*g.1^2*g.2^-1*g.1^-3, g.3/g.2^6 ]; [ g.1^5*g.3^-4, g.2*g.1^2*g.2^-1*g.1^-3, g.3*g.2^-6 ] gap> Size( g ); 120 gap> time; 3000

Martin.

--

Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551

Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, D 51 Aachen, Germany

> < [top]