[GAP Forum] reidemeister-schreier algorithm

Alexander Hulpke hulpke at me.com
Wed Mar 17 01:13:30 GMT 2010


Dear Dave McCune, Dear Forum,

> I have a group G and a map from G onto H, and I want GAP to use Reidemeister-Schreier to get a presentation for the kernel of the map.  I couldn't figure out from the manual how to do this.  Could somebody please help?  Thanks.

If you just want a way to present the subgroup, `IsomorphismFpGroup' will do what you want -- it does Reidemeister-Schreier, as well as some Tietze-Transformations to get the presentation smaller. The homomorphism allows for easy translation between the subgroup of the original group, and the group with the rewritten presentation. For example:

Create some fp group and a map
gap> f:=FreeGroup("a","b");
<free group on the generators [ a, b ]>
gap> g:=f/ParseRelators(f,"a^2,b^3,[a,b]^5");
<fp group on the generators [ a, b ]>
gap> RelatorsOfFpGroup(g);
[ a^2, b^3, a^-1*b^-1*a*b*a^-1*b^-1*a*b*a^-1*b^-1*a*b*a^-1*b^-1*a*b*a^-1*b^
    -1*a*b ]
gap> A5:=Group((1,2,3,4,5),(1,2,3));
Group([ (1,2,3,4,5), (1,2,3) ])
gap> map:=GroupHomomorphismByImages(g,A5,GeneratorsOfGroup(g),
> [(2,4)(3,5),(1,2,3)]);
[ a, b ] -> [ (2,4)(3,5), (1,2,3) ]

Now calculate the kernel, and determine an isomorphism onto a new fp group with the rewritten presentation:
gap> k:=Kernel(map);
Group(<fp, no generators known>)
gap> iso:=IsomorphismFpGroup(k);
[ <[ [ 1, 1 ] ]|b*a*b*a*b*a^-1*b*a^-1*b*a^-1>, 
  <[ [ 2, 1 ] ]|b^-1*a*b^-1*a*b^-1*a^-1*b^-1*a^-1*b^-1*a^-1>, 
  <[ [ 3, 1 ] ]|b*a*b^-1*a*b^-1*a*b^-1*a^-1*b^-1*a^-1*b>, 
  <[ [ 4, 1 ] ]|a*b*a*b^-1*a*b^-1*a*b^-1*a^-1*b^-1*a^-1*b*a^-1>, 
  <[ [ 5, 1 ] ]|b*a*b*a*b^-1*a*b*a*b*a^-1*b*a^-1*b^-1*a^-1*b*a^-1>, 
  <[ [ 6, 1 ] ]|b^-1*a*b*a*b^-1*a*b^-1*a*b^-1*a^-1*b^-1*a^-1*b*a^-1*b> ] -> 
[ F1, F2, F3, F4, F5, F6 ]
gap> h:=Range(iso);
<fp group of size infinity on the generators [ F1, F2, F3, F4, F5, F6 ]>

If we want the actual presentation:
gap> RelatorsOfFpGroup(h);
[ F4*F1^-1*F3*F6*F5*F6*F2*F1^-1*F5*F4^-1*F2^-1*F3^-1 ]

If you want to go down to the bare metal and have a ``purer'' RRS, there is PresentationSubgroupRrs, which returns a ``presentation'' object.

Greetings from Colorado,

  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