[GAP Forum] Problems with SetReducedMultiplication

Alexander Hulpke hulpke at math.colostate.edu
Wed Mar 4 21:40:28 GMT 2009



Dear Josef Lauri,

> I am defining a not too complicated finitely presented group as  
> follows:
>
> f:=FreeGroup(3);
> rels:=[f.1^5,f.2^3,f.3^31,
>      f.2*f.1*(f.1*f.2*f.3)^-1,
>      f.3*f.1*(f.1*f.3^2)^-1,
>      f.3*f.2*(f.2*f.3^25)^-1];
> g:=f/rels;
>
> I then want to express some products of the generators in reduced  
> form.

What is happening is the following: The code for reduced  
multiplication calls a Knuth-Bendix rewriting process in the hope of  
finding a confluent rewriting system for reduction. In this particular  
example, this rewriting does not terminate in any reasonable time, I  
suspect the 25-th power is the cause. There are three possible remedies:

1) Under Unix, you could load the kbmag package and set
KB_REW:=KBMAG_REW;
to use that packages Knuth-Bendix algorithm, which is vastly superior  
to the naive version in GAP.

2) If you don't care about the particular representation as words in  
the given generators, you could convert f to a permutation group or  
(the group is solvable) a Pc group with
IsomorphismPermGroup(f);
or
IsomorphismPcGroup(f);
and work in the image. (This gives you the best performance. You also  
could use the homomorphism to translate results back in the presented  
group.)

3) I have changed the code for the next bugfix to have GAP check  
whether the group is small (and then use a permutation representation  
to find a normal form) before attempting a Knuth-Bendix enumeration.  
With this change the code behaves after
SetReducedMultiplication(g);
as you expected it to do. If you want I can send you the corresponding  
fix now. (It is slightly longish, as it affects a couple of functions.)

Apologies for the problem,

    Alexander Hulpke

-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke





More information about the Forum mailing list