> < ^ From:

^ Subject:

Dear GAP-forum,

In two recent mails, Laurent Bartholdi and Derek Holt asked about a way for

expressing elements of a subgroup of a finitely presented group as words in

generators.

The ``proper'' way (in my eyes) to do this in GAP would be to use

`IsomorphismFpGroupByGenerators' as Derek already did. Computing an image

under such an homomorphism will express an element as a word.

Alas, in release 4.2 the functionality for such homomorphisms is lacking.

There is some ad-hoc code that permits to compute the images of

``obvious'' elements (such as the original generators) under such a

homomorphism, but (again, as Derek's mail shows) it fails for most products.

(This is the reason for the strange behaviour observed.)

On the algorithmic level, what has to be done is fairly clear: One has to

compute an augmented (modified TC) coset table and then use this coset table

to rewrite words in the subgroup generators. Unfortunately the format of

augmented coset tables was not documented and no such rewriting function had

been made available.

Since I needed this functionality for my own research, I implemented proper

homomorphism methods this spring. They are in the development version of GAP

and will be part of the next release. With these methods, Derek's example

becomes:

gap> F:=FreeGroup(2); R:=[F.1^2,F.2^3,(F.1*F.2)^3]; G:=F/R; #A4. gap> gap> SG := []; gap> for r in R do for e in List(Elements(G),UnderlyingElement) do > Add(SG,r^e); > od; od; gap> K:=Subgroup(F,SG); gap> phi := IsomorphismFpGroupByGenerators(K,SG);; gap> K.4^phi; y4 gap> (K.1*K.4)^phi; y1^2 gap> (K.1*K.5)^phi; y1*y5 # try some longer word ... gap> r:=PseudoRandom(F);; gap> Length(r); 8628 gap> w:=(K.7^r)^phi;; gap> Length(UnderlyingElement(w)); 9673

I do not realistically expect a 4.3 release (including this functionality)

before next spring, though of course (as everyone else) I would like these

new functions to be available as soon as possible.

(Incidentally, following up on Isabel Araujo's earlier mail, there also will

be a much better implementation of a Knuth-Bendix available in the next

release.)

If you require such decomposition functionality for your research and cannot

wait until then *and if you have enough system experience to replace library

files with newer versions*, I'd be more than happy to send you privately

code which implements ``proper'' homomorphisms for finitely presented

groups.

Best wishes,

Alexander Hulpke

-- The Ohio State University, Department of Mathematics,

231W 18th Avenue, Columbus, OH 43210, USA

email: ahulpke@math.ohio-state.edu, Phone: ++1-614-688-3175

> < [top]