> < ^ Date: Tue, 14 Nov 2000 17:24:05 -0500 (EST)
> < ^ From: Alexander Hulpke <hulpke@math.colostate.edu >
^ Subject: Re: computing with a homomorphism

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

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
> 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]