> < ^ From:

< ^ Subject:

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

> < [top]