> < ^ Date: Tue, 21 Apr 1992 12:34:45 +0200
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
< ^ Subject: Re: Love the finitely generated group stuff, but...
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]