Dear Gap Forum,

In his reply to Bill Banks' question concerning the problem of
recognizing which element of a small finitely presented group is
described by a given word in its generators, Richard Rossmanith wrote:

I had the same problem, and probably also other people. What I usually
do (and probably what is more or less the natural thing to do here) is
to convert the group into a isomorphic permutation group with
"OperationCosetsFpGroup", and then define two mutually inverse
isomorphisms phi, psi between my original group g and the permutation
group p.

I would solve your example this way:

gap> f:=FreeGroup("x");
Group( x )
gap> x:=f.1;
x
gap> g:=f/[x^2];
Group( x )
gap> x:=g.1;
x
gap> p:=OperationCosetsFpGroup(g,TrivialSubgroup(g));
Group( (1,2) )
gap> phi:=GroupHomomorphismByImages(g,p,g.generators,p.generators);
GroupHomomorphismByImages( Group( x ), Group( (1,2) ), [ x ], [ (1,2) ] )
gap> psi:=GroupHomomorphismByImages(p,g,p.generators,g.generators);
GroupHomomorphismByImages( Group( (1,2) ), Group( x ), [ (1,2) ], [ x ] )
gap> IsIsomorphism(phi); IsIsomorphism(psi);
true
true
gap> ((x*x*x*x*x*x*x)^phi)^psi;
x^-1

(This is a strange, but at least canonical GAP says "x".)

Note that this approach does unfortunately not always (but almost) work.
Namely it does not work when one of the generators of g becomes trivial
by the relations you gave. Then this element would be mapped onto the
empty permutation under phi, so GAP seems to throw it out of the set of
generators of p. (It obviously is not needed to generate p. But the
generating sets of g and p are not "compatible" anymore, so you have a
harder time defining phi and psi.)

Maybe there's a better way, in this case I would be interested, too.

Indeed, there is a way to avoid the problem with empty permutations among
the generators. It suffices to replace the two lines defining phi and psi
by

phi := OperationHomomorphism( g, p );
psi := InverseMapping( phi );

Example:

gap> F := FreeGroup( "x", "y", "z" );;
gap> x := F.1;; y := F.2;; z := F.3;;
gap> G := F / [ x, y^2, z^3, Comm( y, z ) ];;
gap> x := G.1;; y := G.2;; z := G.3;;
gap> P := OperationCosetsFpGroup( G, TrivialSubgroup( G ) );;
gap> phi := OperationHomomorphism( G, P );;
gap> psi := InverseMapping( phi );;
gap> IsIsomorphism( phi );
true
gap> IsIsomorphism( psi );
Error, arbitrary generating systems not yet allowed for fp groups in
G.operations.GroupHomomorphismByImages( G, H, gens, imgs ) called from
GroupHomomorphismByImages( hom.range, hom.source, hom.genimages,
hom.generators ) called from
struct.operations.InverseMapping( struct ) called from
InverseMapping( hom ) called from
struct.operations.KernelGroupHomomorphism( struct ) called from
...
brk> quit;
gap> ((y^5*z)^phi)^psi;
y^-1*z^-2
gap> ((y*z*y)^phi)^psi;
z^-2
gap> ((z*y*z)^phi)^psi;
y^-1*z^-1

This approach works though the "inverse mapping" psi is not necessarily
a mapping. e. g., if we have two generators in p which are equal, but
which are mapped on different generators of g.

The resulting representative for a given word w in G is the image under
psi of a word in the generators of P for the permutation phi(w). This
product is computed by first constructing a stabilizer chain of P (via
the Schreier-Sims method) and then using the stabilizer coset
representatives.

It may be a disadvantage of the homomorphism functions called in the
above example that they do not give us a feeling for their complexity.

As an alternative, here is a different approach, again using a faithful
permutation representation of G, which is more transparent. It involves
two functions, an initializing function which has to be called just once
for the group, and the proper function itself.

gap> InitElementWord := function( G )
>     local elts, T;
>     T := CosetTableFpGroup( G, TrivialSubgroup( G ) );
>     G.permutations := List( [1 .. Length( G.generators ) ],
>         i ->PermList(  T[ 2*i - 1 ] ) );
>     elts := Elements( G );
> end;;
gap> ElementWord := function( G, word )
>     local perm;
>     perm := MappedWord( word, G.generators, G.permutations );
>     return G.elements[1^perm];
> end;;

We use these functions to handle the same example as above:

gap> F := FreeGroup( "x", "y", "z" );;
gap> x := F.1;; y := F.2;; z := F.3;;
gap> G := F / [ x, y^2, z^3, Comm( y, z ) ];;
gap> x := G.1;; y := G.2;; z := G.3;;
gap> InitElementWord( G );
gap> ElementWord( G, y^5*z );
y*z
gap> ElementWord( G, y*z*y );
z
gap> ElementWord( G, z*y*z );
y*z^2

Now the representative for a given word w in G is determined by the
definition of the associated coset representative in the coset table
T of G by its trivial subgroup. This is consistent with the
representation of w in the list Elements(G).

Volkmar Felsch, Aachen