  
  [1X47 [33X[0;0YFinitely Presented Groups[133X[101X
  
  [33X[0;0YA  [13Xfinitely  presented  group[113X  (in short: FpGroup) is a group generated by a
  finite  set of [13Xabstract generators[113X subject to a finite set of [13Xrelations[113X that
  these  generators  satisfy.  Every  finite  group  can  be  represented as a
  finitely  presented  group, though in almost all cases it is computationally
  much  more  efficient  to  work  in another representation (even the regular
  permutation representation).[133X
  
  [33X[0;0YFinitely presented groups are obtained by factoring a free group by a set of
  relators.   Their   elements   know  about  this  presentation  and  compare
  accordingly.[133X
  
  [33X[0;0YSo  to  create  a finitely presented group you first have to generate a free
  group  (see [2XFreeGroup[102X ([14X37.2-1[114X) for details). There are two ways to specify a
  quotient of the free group: either by giving a list of relators or by giving
  a  list  of equations. Relators are just words in the generators of the free
  group.  Equations are represented as pairs of words in the generators of the
  free  group. In either case the generators of the quotient are [13Xthe images[113X of
  the  free  generators  under  the canonical homomorphism from the free group
  onto the quotient. So for example to create the group[133X
  
  
  [24X[33X[0;6Y⟨ a, b ∣ a^2, b^3, (a b)^5 ⟩[133X[124X
  
  [33X[0;0Yyou can use the following commands:[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf := FreeGroup( "a", "b" );;[127X[104X
    [4X[25Xgap>[125X [27Xg := f / [ f.1^2, f.2^3, (f.1*f.2)^5 ];[127X[104X
    [4X[28X<fp group on the generators [ a, b ]>[128X[104X
    [4X[25Xgap>[125X [27Xh := f / [ [f.1^2, f.1^0], [f.2^3, f.1^0], [(f.1*f.2)^4, f.2^-1*f.1^-1] ];[127X[104X
    [4X[28X<fp group on the generators [ a, b ]>[128X[104X
  [4X[32X[104X
  
  [33X[0;0YNote that you cannot call the generators by their names. These names are not
  variables,  but  just  display  figures.  So,  if  you  want  to  access the
  generators  by  their  names,  you  first  have  to introduce the respective
  variables and to assign the generators to them.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XUnbind(a);[127X[104X
    [4X[25Xgap>[125X [27XGeneratorsOfGroup( g );[127X[104X
    [4X[28X[ a, b ][128X[104X
    [4X[25Xgap>[125X [27Xa;[127X[104X
    [4X[28XError, Variable: 'a' must have a value[128X[104X
    [4X[25Xgap>[125X [27Xa := g.1;; b := g.2;; # assign variables[127X[104X
    [4X[25Xgap>[125X [27XGeneratorsOfGroup( g );[127X[104X
    [4X[28X[ a, b ][128X[104X
    [4X[25Xgap>[125X [27Xa in f;[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27Xa in g;[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [33X[0;0YTo  relieve  you of the tedium of typing the above assignments, [13Xwhen working
  interactively[113X, there is the function [2XAssignGeneratorVariables[102X ([14X37.2-3[114X).[133X
  
  [33X[0;0YNote that the generators of the free group are different from the generators
  of  the  FpGroup  (even  though  they are displayed by the same names). That
  means that words in the generators of the free group are not elements of the
  finitely presented group. Vice versa elements of the FpGroup are not words.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xa*b = b*a;[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27X(b^2*a*b)^2 = a^0;[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [33X[0;0YSuch  calculations  comparing  elements of an FpGroup may run into problems:
  There  exist  finitely presented groups for which no algorithm exists (it is
  known  that  no  such  algorithm can exist) that will tell for two arbitrary
  words  in  the  generators whether the corresponding elements in the FpGroup
  are equal.[133X
  
  [33X[0;0YTherefore  the  methods  used by [5XGAP[105X to compute in finitely presented groups
  may  run  into  warning  errors,  run  out  of memory or run forever. If the
  FpGroup  is  (by theory) known to be finite the algorithms are guaranteed to
  terminate (if there is sufficient memory available), but the time needed for
  the calculation cannot be bounded a priori. See [14X47.6[114X and [14X47.16[114X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27X(b^2*a*b)^2;[127X[104X
    [4X[28X(b^2*a*b)^2[128X[104X
    [4X[25Xgap>[125X [27Xa^0;[127X[104X
    [4X[28X<identity ...>[128X[104X
  [4X[32X[104X
  
  [33X[0;0YA  consequence  of  our  convention  is  that elements of finitely presented
  groups  are  not  printed in a unique way. See also [2XSetReducedMultiplication[102X
  ([14X47.3-4[114X).  For  many  [21Xhigher  level[121X computations for a finite group, such as
  conjugacy  classes or character table, it is advisable not to use an FpGroup
  but  an  isomorphic  group in a better internal representation, such as a pc
  group   (see  [2XIsomorphismPcGroup[102X  ([14X46.5-2[114X))  or  a  permutation  group  (see
  [2XIsomorphismPermGroup[102X   ([14X43.3-1[114X)).  In  fact,  calling  a  function  such  as
  [2XConjugacyClasses[102X  ([14X39.10-2[114X)  with  an  FpGroup for which [10XHasIsFinite[110X returns
  [9Xfalse[109X  may result in an error message, because the developers of the FpGroup
  code  do  not  want  an  [13Xautomatic[113X  [2XIsFinite[102X  ([14X30.4-2[114X)  test  (which may not
  terminate)  in the function. (Once the [2XIsFinite[102X ([14X30.4-2[114X) value is known, the
  computation  in  question  can  be  done  with  the FpGroup, but still it is
  advisable to use a better internal representation.)[133X
  
  
  [1X47.1 [33X[0;0YIsSubgroupFpGroup and IsFpGroup[133X[101X
  
  [1X47.1-1 IsSubgroupFpGroup[101X
  
  [33X[1;0Y[29X[2XIsSubgroupFpGroup[102X( [3XH[103X ) [32X Category[133X
  
  [33X[0;0Yis  the  category  for  finitely presented groups or subgroups of a finitely
  presented group.[133X
  
  [1X47.1-2 IsFpGroup[101X
  
  [33X[1;0Y[29X[2XIsFpGroup[102X( [3XG[103X ) [32X filter[133X
  
  [33X[0;0Yis a synonym for [10XIsSubgroupFpGroup([3XG[103X[10X) and IsGroupOfFamily([3XG[103X[10X)[110X.[133X
  
  [33X[0;0YFree groups are a special case of finitely presented groups, namely finitely
  presented groups with no relators.[133X
  
  [33X[0;0YNote  that  [10XFreeGroup(infinity)[110X (which exists e.g. for purposes of rewriting
  presentations  with  further  generators)  satisfies  this filter, though of
  course  it  is  not  finitely  generated  (and thus not finitely presented).
  [10XIsFpGroup[110X  thus  is not a proper property test and slightly misnamed for the
  sake of its most prominent uses.[133X
  
  [33X[0;0YAnother  special case are groups given by polycyclic presentations. [5XGAP[105X uses
  a  special  representation  for these groups which is created in a different
  way. See chapter [14X46[114X for details.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xg:=FreeGroup(2);[127X[104X
    [4X[28X<free group on the generators [ f1, f2 ]>[128X[104X
    [4X[25Xgap>[125X [27XIsFpGroup(g);[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27Xh:=CyclicGroup(2);[127X[104X
    [4X[28X<pc group of size 2 with 1 generator>[128X[104X
    [4X[25Xgap>[125X [27XIsFpGroup(h);[127X[104X
    [4X[28Xfalse[128X[104X
  [4X[32X[104X
  
  [1X47.1-3 InfoFpGroup[101X
  
  [33X[1;0Y[29X[2XInfoFpGroup[102X [32X info class[133X
  
  [33X[0;0YThe  info  class  for  functions  dealing  with finitely presented groups is
  [2XInfoFpGroup[102X.[133X
  
  
  [1X47.2 [33X[0;0YCreating Finitely Presented Groups[133X[101X
  
  [1X47.2-1 \/[101X
  
  [33X[1;0Y[29X[2X\/[102X( [3XF[103X, [3Xrels[103X ) [32X method[133X
  [33X[1;0Y[29X[2X\/[102X( [3XF[103X, [3Xeqns[103X ) [32X method[133X
  
  [33X[0;0Ycreates a finitely presented group given by the presentation [22X⟨ gens ∣ [3Xrels[103X ⟩[122X
  or  [22X⟨  gens ∣ [3Xeqns[103X ⟩[122X, respectively where [22Xgens[122X are the free generators of the
  free  group [3XF[103X. Relations can be entered either as words or as pairs of words
  in  the  generators  of [3XF[103X. In the former case we refer to the words given as
  [13Xrelators[113X, in the latter we refer to the pairs of words as [13Xequations[113X. The two
  methods can currently not be mixed.[133X
  
  [33X[0;0YThe same result is obtained with the infix operator [10X/[110X, i.e., as [3XF[103X [10X/[110X [3Xrels[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf := FreeGroup( 3 );;[127X[104X
    [4X[25Xgap>[125X [27Xf / [ f.1^4, f.2^3, f.3^5, f.1*f.2*f.3 ];[127X[104X
    [4X[28X<fp group on the generators [ f1, f2, f3 ]>[128X[104X
    [4X[25Xgap>[125X [27Xf / [ [ f.1^4, f.1^0 ], [ f.2^3, f.1^0 ], [ f.1, f.2^-1*f.3^-1 ] ];[127X[104X
    [4X[28X<fp group on the generators [ f1, f2, f3 ]>[128X[104X
  [4X[32X[104X
  
  [1X47.2-2 FactorGroupFpGroupByRels[101X
  
  [33X[1;0Y[29X[2XFactorGroupFpGroupByRels[102X( [3XG[103X, [3Xelts[103X ) [32X function[133X
  
  [33X[0;0Yreturns the factor group [3XG[103X/[22XN[122X of [3XG[103X by the normal closure [22XN[122X of [3Xelts[103X where [3Xelts[103X
  is expected to be a list of elements of [3XG[103X.[133X
  
  [1X47.2-3 ParseRelators[101X
  
  [33X[1;0Y[29X[2XParseRelators[102X( [3Xgens[103X, [3Xrels[103X ) [32X function[133X
  
  [33X[0;0YWill  translate  a  list of relations as given in print, e.g. [22Xx y^2 = (x y^3
  x)^2  xy  =  yzx[122X  into relators. [3Xgens[103X must be a list of generators of a free
  group,  each being displayed by a single letter. [3Xrels[103X is a string that lists
  a sequence of equalities. These must be written in the letters which are the
  names  of  the generators in [3Xgens[103X. Change of upper/lower case is interpreted
  to indicate inverses.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf:=FreeGroup("x","y","z");;[127X[104X
    [4X[25Xgap>[125X [27XAssignGeneratorVariables(f);[127X[104X
    [4X[28X#I  Assigned the global variables [ x, y, z ][128X[104X
    [4X[25Xgap>[125X [27Xr:=ParseRelators([x,y,z],[127X[104X
    [4X[25X>[125X [27X"x^2 = y^5 = z^3 = (xyxyxy^4)^2 = (xz)^2 = (y^2z)^2 = 1");[127X[104X
    [4X[28X[ x^2, y^5, z^3, (x*z)^2, (y^2*z)^2, ((x*y)^3*y^3)^2 ][128X[104X
    [4X[25Xgap>[125X [27Xg:=f/r;[127X[104X
    [4X[28X<fp group on the generators [ x, y, z ]>[128X[104X
  [4X[32X[104X
  
  [1X47.2-4 StringFactorizationWord[101X
  
  [33X[1;0Y[29X[2XStringFactorizationWord[102X( [3Xw[103X ) [32X function[133X
  
  [33X[0;0Yreturns  a string that expresses a given word [3Xw[103X in compact form written as a
  string.  Inverses  are  expressed  by  changing  the upper/lower case of the
  generators, recurring expressions are written as products.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XStringFactorizationWord(z^-1*x*y*y*y*x*x*y*y*y*x*y^-1*x);[127X[104X
    [4X[28X"Z(xy3x)2Yx"[128X[104X
  [4X[32X[104X
  
  
  [1X47.3 [33X[0;0YComparison of Elements of Finitely Presented Groups[133X[101X
  
  [1X47.3-1 \=[101X
  
  [33X[1;0Y[29X[2X\=[102X( [3Xa[103X, [3Xb[103X ) [32X method[133X
  
  [33X[0;0YTwo  elements  of  a finitely presented group are equal if they are equal in
  this  group.  Nevertheless they may be represented as different words in the
  generators.   Because   of   the   fundamental  problems  mentioned  in  the
  introduction  to  this  chapter such a test may take very long and cannot be
  guaranteed to finish.[133X
  
  [33X[0;0YThe  method  employed  by  [5XGAP[105X  for such an equality test use the underlying
  finitely  presented group. First (unless this group is known to be infinite)
  [5XGAP[105X  tries  to  find  a  faithful  permutation  representation  by a bounded
  Todd-Coxeter.  If this fails, a Knuth-Bendix (see [14X52.5[114X) is attempted and the
  words are compared via their normal form.[133X
  
  [33X[0;0YIf  only elements in a subgroup are to be tested for equality it thus can be
  useful  to  translate  the  problem  in  a  new  finitely presented group by
  rewriting (see [2XIsomorphismFpGroup[102X ([14X47.11-1[114X));[133X
  
  [33X[0;0YThe equality test of elements underlies many [21Xbasic[121X calculations, such as the
  order  of an element, and the same type of problems can arise there. In some
  cases,  working  with rewriting systems can still help to solve the problem.
  The  [5Xkbmag[105X  package  provides such functionality, see the package manual for
  further details.[133X
  
  [1X47.3-2 \<[101X
  
  [33X[1;0Y[29X[2X\<[102X( [3Xa[103X, [3Xb[103X ) [32X method[133X
  
  [33X[0;0YCompared  with  equality  testing,  problems  get  even worse when trying to
  compute  a  total ordering on the elements of a finitely presented group. As
  any  ordering that is guaranteed to be reproducible in different runs of [5XGAP[105X
  or  even  with  different  groups given by syntactically equal presentations
  would  be  prohibitively expensive to implement, the ordering of elements is
  depending on a method chosen by [5XGAP[105X and not guaranteed to stay the same when
  repeating the construction of an FpGroup. The only guarantee given for the [10X<[110X
  ordering  for  such  elements  is  that it will stay the same for one family
  during its lifetime. The attribute [2XFpElmComparisonMethod[102X ([14X47.3-3[114X) is used to
  obtain a comparison function for a family of FpGroup elements.[133X
  
  [1X47.3-3 FpElmComparisonMethod[101X
  
  [33X[1;0Y[29X[2XFpElmComparisonMethod[102X( [3Xfam[103X ) [32X attribute[133X
  
  [33X[0;0YIf  [3Xfam[103X  is the elements family of a finitely presented group this attribute
  returns  a  function  [10Xsmaller([3Xleft[103X[10X,  [3Xright[103X[10X)[110X  that  will  be  used to compare
  elements in [3Xfam[103X.[133X
  
  [1X47.3-4 SetReducedMultiplication[101X
  
  [33X[1;0Y[29X[2XSetReducedMultiplication[102X( [3Xobj[103X ) [32X function[133X
  
  [33X[0;0YFor  an FpGroup [3Xobj[103X, an element [3Xobj[103X of it or the family [3Xobj[103X of its elements,
  this function will force immediate reduction when multiplying, keeping words
  short at extra cost per multiplication.[133X
  
  
  [1X47.4 [33X[0;0YPreimages in the Free Group[133X[101X
  
  [1X47.4-1 FreeGroupOfFpGroup[101X
  
  [33X[1;0Y[29X[2XFreeGroupOfFpGroup[102X( [3XG[103X ) [32X attribute[133X
  
  [33X[0;0Yreturns  the  underlying free group for the finitely presented group [3XG[103X. This
  is   the   group   generated   by   the  free  generators  provided  by  the
  [2XFreeGeneratorsOfFpGroup[102X ([14X47.4-2[114X) value of [3XG[103X.[133X
  
  [1X47.4-2 FreeGeneratorsOfFpGroup[101X
  
  [33X[1;0Y[29X[2XFreeGeneratorsOfFpGroup[102X( [3XG[103X ) [32X attribute[133X
  [33X[1;0Y[29X[2XFreeGeneratorsOfWholeGroup[102X( [3XU[103X ) [32X operation[133X
  
  [33X[0;0Y[2XFreeGeneratorsOfFpGroup[102X returns the underlying free generators corresponding
  to  the  generators  of  the finitely presented group [3XG[103X which must be a full
  FpGroup.[133X
  
  [33X[0;0Y[2XFreeGeneratorsOfWholeGroup[102X  also  works  for  subgroups  of  an  FpGroup and
  returns the free generators of the full group that defines the family.[133X
  
  [1X47.4-3 RelatorsOfFpGroup[101X
  
  [33X[1;0Y[29X[2XRelatorsOfFpGroup[102X( [3XG[103X ) [32X attribute[133X
  
  [33X[0;0Yreturns  the relators of the finitely presented group [3XG[103X as words in the free
  generators provided by the [2XFreeGeneratorsOfFpGroup[102X ([14X47.4-2[114X) value of [3XG[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf := FreeGroup( "a", "b" );;[127X[104X
    [4X[25Xgap>[125X [27Xg := f / [ f.1^5, f.2^2, f.1^f.2*f.1 ];[127X[104X
    [4X[28X<fp group on the generators [ a, b ]>[128X[104X
    [4X[25Xgap>[125X [27XSize( g );[127X[104X
    [4X[28X10[128X[104X
    [4X[25Xgap>[125X [27XFreeGroupOfFpGroup( g ) = f;[127X[104X
    [4X[28Xtrue[128X[104X
    [4X[25Xgap>[125X [27XFreeGeneratorsOfFpGroup( g );[127X[104X
    [4X[28X[ a, b ][128X[104X
    [4X[25Xgap>[125X [27XRelatorsOfFpGroup( g );[127X[104X
    [4X[28X[ a^5, b^2, b^-1*a*b*a ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YNote  that  these  attributes  are  only  available  for  the  [13Xfull[113X finitely
  presented  group. It is possible (for example by using [2XSubgroup[102X ([14X39.3-1[114X)) to
  construct  a  subgroup of index [22X1[122X which is not identical to the whole group.
  The latter one can be obtained in this situation via [2XParent[102X ([14X31.7-1[114X).[133X
  
  [33X[0;0YElements  of  a  finitely presented group are not words, but are represented
  using  a  word  from  the  free  group  as representative. The following two
  commands  obtain  this representative, respectively create an element in the
  finitely presented group.[133X
  
  [1X47.4-4 UnderlyingElement[101X
  
  [33X[1;0Y[29X[2XUnderlyingElement[102X( [3Xelm[103X ) [32X operation[133X
  
  [33X[0;0YLet  [3Xelm[103X  be  an  element of a group whose elements are represented as words
  with  further  properties.  Then [2XUnderlyingElement[102X returns the word from the
  free group that is used as a representative for [3Xelm[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xw := g.1*g.2;[127X[104X
    [4X[28Xa*b[128X[104X
    [4X[25Xgap>[125X [27XIsWord( w );[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27Xue := UnderlyingElement( w );[127X[104X
    [4X[28Xa*b[128X[104X
    [4X[25Xgap>[125X [27XIsWord( ue );[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [1X47.4-5 ElementOfFpGroup[101X
  
  [33X[1;0Y[29X[2XElementOfFpGroup[102X( [3Xfam[103X, [3Xword[103X ) [32X operation[133X
  
  [33X[0;0YIf  [3Xfam[103X  is  the elements family of a finitely presented group and [3Xword[103X is a
  word  in  the free generators underlying this finitely presented group, this
  operation  creates  the  element  with  the  representative [3Xword[103X in the free
  group.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xge := ElementOfFpGroup( FamilyObj( g.1 ), f.1*f.2 );[127X[104X
    [4X[28Xa*b[128X[104X
    [4X[25Xgap>[125X [27Xge in f;[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27Xge in g;[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  
  [1X47.5 [33X[0;0YOperations for Finitely Presented Groups[133X[101X
  
  [33X[0;0YFinitely presented groups are groups and so all operations for groups should
  be  applicable  to  them  (though  not  necessarily  efficient  methods  are
  available).  However,  one may run into errors if the FpGroup does not store
  that  it  is  finite; see the introduction to this chapter. Most methods for
  finitely presented groups rely on coset enumeration. See [14X47.6[114X for details.[133X
  
  [33X[0;0YThe  command  [2XIsomorphismPermGroup[102X ([14X43.3-1[114X) can be used to obtain a faithful
  permutation representation, if such a representation of small degree exists.
  (Otherwise it might run very long or fail.)[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf := FreeGroup( "a", "b" );[127X[104X
    [4X[28X<free group on the generators [ a, b ]>[128X[104X
    [4X[25Xgap>[125X [27Xg := f / [ f.1^2, f.2^3, (f.1*f.2)^5 ];[127X[104X
    [4X[28X<fp group on the generators [ a, b ]>[128X[104X
    [4X[25Xgap>[125X [27Xh := IsomorphismPermGroup( g );[127X[104X
    [4X[28X[ a, b ] -> [ (2,4)(5,6), (1,2,3)(4,5,6) ][128X[104X
    [4X[25Xgap>[125X [27Xu:=Subgroup(g,[g.1*g.2]);;rt:=RightTransversal(g,u);[127X[104X
    [4X[28XRightTransversal(<fp group of size 60 on the generators[128X[104X
    [4X[28X[ a, b ]>,Group([ a*b ]))[128X[104X
    [4X[25Xgap>[125X [27XImage(ActionHomomorphism(g,rt,OnRight));[127X[104X
    [4X[28XGroup([ (1,2)(3,4)(5,7)(6,8)(9,10)(11,12),[128X[104X
    [4X[28X  (1,3,2)(4,5,6)(7,8,9)(10,11,12) ])[128X[104X
  [4X[32X[104X
  
  [1X47.5-1 PseudoRandom[101X
  
  [33X[1;0Y[29X[2XPseudoRandom[102X( [3XF:[103X [3Xradius[103X [3X:=[103X [3Xl[103X ) [32X method[133X
  
  [33X[0;0YThe  default  algorithm  for  [2XPseudoRandom[102X  ([14X30.7-2[114X)  makes little sense for
  finitely  presented  or free groups, as it produces words that are extremely
  long.[133X
  
  [33X[0;0YBy  specifying the option [10Xradius[110X, instead elements are taken as words in the
  generators  of [3XF[103X in the ball of radius [3Xl[103X with equal distribution in the free
  group.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XPseudoRandom(g:radius:=20);[127X[104X
    [4X[28Xa^3*b^2*a^-2*b^-1*a*b^-4*a*b^-1*a*b^-4[128X[104X
  [4X[32X[104X
  
  
  [1X47.6 [33X[0;0YCoset Tables and Coset Enumeration[133X[101X
  
  [33X[0;0YCoset enumeration (see [Neu82] for an explanation) is one of the fundamental
  tools  for  the  examination  of  finitely  presented  groups.  This section
  describes [5XGAP[105X functions that can be used to invoke a coset enumeration.[133X
  
  [33X[0;0YNote  that  in  addition  to  the built-in coset enumerator there is the [5XGAP[105X
  package  [5XACE[105X.  Moreover, [5XGAP[105X provides an interactive Todd-Coxeter in the [5XGAP[105X
  package [5XITC[105X which is based on the [5XXGAP[105X package.[133X
  
  [1X47.6-1 CosetTable[101X
  
  [33X[1;0Y[29X[2XCosetTable[102X( [3XG[103X, [3XH[103X ) [32X operation[133X
  
  [33X[0;0Yreturns  the  coset table of the finitely presented group [3XG[103X on the cosets of
  the subgroup [3XH[103X.[133X
  
  [33X[0;0YBasically  a  coset  table is the permutation representation of the finitely
  presented  group  on the cosets of a subgroup (which need not be faithful if
  the  subgroup  has  a  nontrivial core). Most of the set theoretic and group
  functions  use  the  regular representation of [3XG[103X, i.e., the coset table of [3XG[103X
  over the trivial subgroup.[133X
  
  [33X[0;0YThe  coset table is returned as a list of lists. For each generator of [3XG[103X and
  its  inverse the table contains a generator list. A generator list is simply
  a  list  of  integers. If [22Xl[122X is the generator list for the generator [22Xg[122X and if
  [22Xl[i] = j[122X then generator [22Xg[122X takes the coset [22Xi[122X to the coset [22Xj[122X by multiplication
  from  the right. Thus the permutation representation of [3XG[103X on the cosets of [3XH[103X
  is obtained by applying [2XPermList[102X ([14X42.5-2[114X) to each generator list.[133X
  
  [33X[0;0YThe coset table is standard (see below).[133X
  
  [33X[0;0YFor  finitely  presented groups, a coset table is computed by a Todd-Coxeter
  coset  enumeration.  Note  that  you  may  influence the performance of that
  enumeration    by    changing   the   values   of   the   global   variables
  [2XCosetTableDefaultLimit[102X   ([14X47.6-7[114X)   and  [2XCosetTableDefaultMaxLimit[102X  ([14X47.6-6[114X)
  described     below     and     that    the    options    described    under
  [2XCosetTableFromGensAndRels[102X ([14X47.6-5[114X) are recognized.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xtab := CosetTable(g, Subgroup(g, [ g.1, g.2*g.1*g.2*g.1*g.2^-1 ]));[127X[104X
    [4X[28X[ [ 1, 4, 5, 2, 3 ], [ 1, 4, 5, 2, 3 ], [ 2, 3, 1, 4, 5 ],[128X[104X
    [4X[28X  [ 3, 1, 2, 4, 5 ] ][128X[104X
    [4X[25Xgap>[125X [27XList( last, PermList );[127X[104X
    [4X[28X[ (2,4)(3,5), (2,4)(3,5), (1,2,3), (1,3,2) ][128X[104X
    [4X[25Xgap>[125X [27XPrintArray( TransposedMat( tab ) );[127X[104X
    [4X[28X[ [  1,  1,  2,  3 ],[128X[104X
    [4X[28X  [  4,  4,  3,  1 ],[128X[104X
    [4X[28X  [  5,  5,  1,  2 ],[128X[104X
    [4X[28X  [  2,  2,  4,  4 ],[128X[104X
    [4X[28X  [  3,  3,  5,  5 ] ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YThe  last  printout in the preceding example provides the coset table in the
  form  in  which it is usually used in hand calculations: The rows correspond
  to  the  cosets, the columns correspond to the generators and their inverses
  in  the  ordering  [22Xg_1,  g_1^{-1},  g_2,  g_2^{-1}[122X.  (See section [14X47.7[114X for a
  description on the way the numbers are assigned.)[133X
  
  [1X47.6-2 TracedCosetFpGroup[101X
  
  [33X[1;0Y[29X[2XTracedCosetFpGroup[102X( [3Xtab[103X, [3Xword[103X, [3Xpt[103X ) [32X function[133X
  
  [33X[0;0YTraces  the coset number [3Xpt[103X under the word [3Xword[103X through the coset table [3Xtab[103X.
  (Note:  [3Xword[103X must be in the free group, use [2XUnderlyingElement[102X ([14X47.4-4[114X) if in
  doubt.)[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XTracedCosetFpGroup(tab,UnderlyingElement(g.1),2);[127X[104X
    [4X[28X4[128X[104X
  [4X[32X[104X
  
  [1X47.6-3 FactorCosetAction[101X
  
  [33X[1;0Y[29X[2XFactorCosetAction[102X( [3XG[103X, [3XH[103X ) [32X operation[133X
  
  [33X[0;0Yreturns the action of [3XG[103X on the cosets of its subgroup [3XH[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xu := Subgroup( g, [ g.1, g.1^g.2 ] );[127X[104X
    [4X[28XGroup([ a, b^-1*a*b ])[128X[104X
    [4X[25Xgap>[125X [27XFactorCosetAction( g, u );[127X[104X
    [4X[28X[ a, b ] -> [ (2,4)(5,6), (1,2,3)(4,5,6) ][128X[104X
  [4X[32X[104X
  
  [1X47.6-4 CosetTableBySubgroup[101X
  
  [33X[1;0Y[29X[2XCosetTableBySubgroup[102X( [3XG[103X, [3XH[103X ) [32X operation[133X
  
  [33X[0;0Yreturns a coset table for the action of [3XG[103X on the cosets of [3XH[103X. The columns of
  the table correspond to the [2XGeneratorsOfGroup[102X ([14X39.2-4[114X) value of [3XG[103X.[133X
  
  [1X47.6-5 CosetTableFromGensAndRels[101X
  
  [33X[1;0Y[29X[2XCosetTableFromGensAndRels[102X( [3Xfgens[103X, [3Xgrels[103X, [3Xfsgens[103X ) [32X function[133X
  
  [33X[0;0Yis  an  internal  function  which  is  called  by  the  functions [2XCosetTable[102X
  ([14X47.6-1[114X),  [2XCosetTableInWholeGroup[102X  ([14X47.8-1[114X)  and others. It is, in fact, the
  workhorse  that  performs  a Todd-Coxeter coset enumeration. [3Xfgens[103X must be a
  set  of  free  generators  and  [3Xgrels[103X a set of relators in these generators.
  [3Xfsgens[103X  are  subgroup generators expressed as words in these generators. The
  function returns a coset table with respect to [3Xfgens[103X.[133X
  
  [33X[0;0Y[2XCosetTableFromGensAndRels[102X  will  call [10XTCENUM.CosetTableFromGensAndRels[110X. This
  makes  it possible to replace the built-in coset enumerator with another one
  by assigning [10XTCENUM[110X to another record.[133X
  
  [33X[0;0YThe  library  version  which  is  used by default performs a standard Felsch
  strategy  coset  enumeration.  You  can  call  this  function  explicitly as
  [10XGAPTCENUM.CosetTableFromGensAndRels[110X  even  if  other  coset  enumerators are
  installed.[133X
  
  [33X[0;0YThe expected parameters are[133X
  
  [8X[3Xfgens[103X[8X[108X
        [33X[0;6Ygenerators of the free group [3XF[103X[133X
  
  [8X[3Xgrels[103X[8X[108X
        [33X[0;6Yrelators as words in [3XF[103X[133X
  
  [8X[3Xfsgens[103X[8X[108X
        [33X[0;6Ysubgroup generators as words in [3XF[103X.[133X
  
  [33X[0;0Y[2XCosetTableFromGensAndRels[102X processes two options (see chapter [14X8[114X):[133X
  
  [8X[10Xmax[110X[8X[108X
        [33X[0;6YThe  limit  of  the number of cosets to be defined. If the enumeration
        does not finish with this number of cosets, an error is raised and the
        user  is asked whether she wants to continue. The default value is the
        value  given  in  the  variable [10XCosetTableDefaultMaxLimit[110X. (Due to the
        algorithm  the  actual  limit used can be a bit higher than the number
        given.)[133X
  
  [8X[10Xsilent[110X[8X[108X
        [33X[0;6YIf  set to [9Xtrue[109X the algorithm will not raise the error mentioned under
        option  [10Xmax[110X  but  silently  return  [9Xfail[109X.  This  can  be  useful if an
        enumeration is only wanted unless it becomes too big.[133X
  
  [1X47.6-6 CosetTableDefaultMaxLimit[101X
  
  [33X[1;0Y[29X[2XCosetTableDefaultMaxLimit[102X [32X global variable[133X
  
  [33X[0;0Yis  the  default  limit  for  the  number  of  cosets  allowed  in  a  coset
  enumeration.[133X
  
  [33X[0;0YA  coset  enumeration  will  not finish if the subgroup does not have finite
  index, and even if it has it may take many more intermediate cosets than the
  actual  index  of the subgroup is. To avoid a coset enumeration [21Xrunning away[121X
  therefore  [5XGAP[105X  has a [21Xsafety stop[121X built in. This is controlled by the global
  variable [2XCosetTableDefaultMaxLimit[102X.[133X
  
  [33X[0;0YIf  this  number  of  cosets is reached, [5XGAP[105X will issue an error message and
  prompt  the  user  to  either  continue  the  calculation or to stop it. The
  default value is [22X4096000[122X.[133X
  
  [33X[0;0YSee  also  the  description  of  the  options  to  [2XCosetTableFromGensAndRels[102X
  ([14X47.6-5[114X).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf := FreeGroup( "a", "b" );;[127X[104X
    [4X[25Xgap>[125X [27Xu := Subgroup( f, [ f.2 ] );[127X[104X
    [4X[28XGroup([ b ])[128X[104X
    [4X[25Xgap>[125X [27XIndex( f, u );[127X[104X
    [4X[28XError, the coset enumeration has defined more than 4096000 cosets[128X[104X
    [4X[28XStack trace:[128X[104X
    [4X[28X*[1] Error( "the coset enumeration has defined more ", "than ", limit, " cosets\n" );[128X[104X
    [4X[28X   @ GAPROOT/lib/grpfp.gi:1230[128X[104X
    [4X[28X [2] TCENUM.CosetTableFromGensAndRels( fgens, grels, fsgens )[128X[104X
    [4X[28X   @ GAPROOT/lib/grpfp.gi:1068[128X[104X
    [4X[28X [3] CosetTableFromGensAndRels( fgens, grels, fsgens )[128X[104X
    [4X[28X   @ GAPROOT/lib/grpfp.gi:1346[128X[104X
    [4X[28X [4] TryCosetTableInWholeGroup( H )[128X[104X
    [4X[28X   @ GAPROOT/lib/grpfp.gi:1359[128X[104X
    [4X[28X [5] CosetTableInWholeGroup( H )[128X[104X
    [4X[28X   @ GAPROOT/lib/grpfp.gi:1733[128X[104X
    [4X[28X...  at *stdin*:3[128X[104X
    [4X[28Xtype 'return;' if you want to continue with a new limit of 8192000 cosets,[128X[104X
    [4X[28Xtype 'quit;' if you want to quit the coset enumeration,[128X[104X
    [4X[28Xtype 'maxlimit := 0; return;' in order to continue without a limit[128X[104X
    [4X[26Xbrk>[126X [27Xquit;[127X[104X
  [4X[32X[104X
  
  [33X[0;0YAt  this  point,  a  [9Xbreak[109X-loop (see Section [14X6.4[114X) has been entered. The line
  beginning  [10XError[110X  tells you why this occurred. The next seven lines occur if
  [2XOnBreak[102X  ([14X6.4-3[114X)  has its default value [2XWhere[102X ([14X6.4-5[114X). They explain, in this
  case,  how  [5XGAP[105X  came  to be doing a coset enumeration. Then you are given a
  number  of  options of how to escape the [9Xbreak[109X-loop: you can either continue
  the  calculation  with  a  larger  number  of  permitted  cosets,  stop  the
  calculation  if  you  don't  expect  the  enumeration to finish (like in the
  example  above),  or  continue  without  a  limit  on  the number of cosets.
  (Choosing  the  first option will, of course, land you back in a [9Xbreak[109X-loop.
  Try it!)[133X
  
  [33X[0;0YSetting [2XCosetTableDefaultMaxLimit[102X (or the [10Xmax[110X option value, for any function
  that  invokes a coset enumeration) to [2Xinfinity[102X ([14X18.2-1[114X) (or to [22X0[122X) will force
  all coset enumerations to continue until they either get a result or exhaust
  the whole available space. For example, each of the following two inputs[133X
  
  [4X[32X[104X
    [4Xgap> CosetTableDefaultMaxLimit := 0;;[104X
    [4Xgap> Index( f, u );[104X
  [4X[32X[104X
  
  [33X[0;0Yor[133X
  
  [4X[32X[104X
    [4Xgap> Index( f, u : max := 0 );[104X
  [4X[32X[104X
  
  [33X[0;0Yhave  essentially  the  same  effect  as  choosing the third option (typing:
  [10Xmaxlimit := 0; return;[110X) at the [10Xbrk>[110X prompt above (instead of [10Xquit;[110X).[133X
  
  [1X47.6-7 CosetTableDefaultLimit[101X
  
  [33X[1;0Y[29X[2XCosetTableDefaultLimit[102X [32X global variable[133X
  
  [33X[0;0Yis  the  default  number of cosets with which any coset table is initialized
  before doing a coset enumeration.[133X
  
  [33X[0;0YThe function performing this coset enumeration will automatically extend the
  table  whenever  necessary  (as long as the number of cosets does not exceed
  the  value  of [2XCosetTableDefaultMaxLimit[102X ([14X47.6-6[114X)), but this is an expensive
  operation.  Thus,  if  you  change  the value of [2XCosetTableDefaultLimit[102X, you
  should  set  it  to  a number of cosets that you expect to be sufficient for
  your  subsequent  coset  enumerations. On the other hand, if you make it too
  large, your job will unnecessarily waste a lot of space.[133X
  
  [33X[0;0YThe default value of [2XCosetTableDefaultLimit[102X is [22X1000[122X.[133X
  
  [1X47.6-8 MostFrequentGeneratorFpGroup[101X
  
  [33X[1;0Y[29X[2XMostFrequentGeneratorFpGroup[102X( [3XG[103X ) [32X function[133X
  
  [33X[0;0Yis  an  internal  function which is used in some applications of coset table
  methods.  It  returns  the  first  of those generators of the given finitely
  presented group [3XG[103X which occur most frequently in the relators.[133X
  
  [1X47.6-9 IndicesInvolutaryGenerators[101X
  
  [33X[1;0Y[29X[2XIndicesInvolutaryGenerators[102X( [3XG[103X ) [32X attribute[133X
  
  [33X[0;0Yreturns  the  indices  of those generators of the finitely presented group [3XG[103X
  which  are  known  to  be  involutions.  This  knowledge is used by internal
  functions to improve the performance of coset enumerations.[133X
  
  
  [1X47.7 [33X[0;0YStandardization of coset tables[133X[101X
  
  [33X[0;0YFor  any two coset numbers [22Xi[122X and [22Xj[122X with [22Xi < j[122X the first occurrence of [22Xi[122X in a
  coset  table  precedes  the  first occurrence of [22Xj[122X with respect to the usual
  row-wise  ordering  of  the table entries. Following the notation of Charles
  Sims'  book  on  computation  with finitely presented groups [Sim94] we call
  such a table a [13Xstandard coset table[113X.[133X
  
  [33X[0;0YThe table entries which contain the first occurrences of the coset numbers [22Xi
  >  1[122X  recursively  provide  for each [22Xi[122X a representative of the corresponding
  coset  in form of a unique word [22Xw_i[122X in the generators and inverse generators
  of  [22XG[122X.  The  first coset (which is [22XH[122X itself) can be represented by the empty
  word  [22Xw_1[122X.  A coset table is standard if and only if the words [22Xw_1, w_2, ...[122X
  are  length-plus-lexicographic  ordered  (as defined in [Sim94]), for short:
  [13Xlenlex[113X.[133X
  
  [33X[0;0YThis  standardization  of  coset  tables  is different from that used in [5XGAP[105X
  versions  4.2  and  earlier.  Before  that,  we  ignored  the  columns  that
  correspond  to  inverse  generators  and  hence only considered words in the
  generators  of  [22XG[122X. We call this older ordering the [13Xsemilenlex[113X standard as it
  also  applies  to the case of semigroups where no inverses of the generators
  are known.[133X
  
  [33X[0;0YWe  changed  our default from the semilenlex standard to the lenlex standard
  to  be  consistent  with  [Sim94].  However,  the semilenlex standardisation
  remains  available and the convention used for all implicit standardisations
  can   be   selected   by   setting   the   value   of  the  global  variable
  [2XCosetTableStandard[102X  ([14X47.7-1[114X) to either [10X"lenlex"[110X or [10X"semilenlex"[110X. Independent
  of  the current value of [2XCosetTableStandard[102X ([14X47.7-1[114X) you can standardize (or
  restandardize) a coset table at any time using [2XStandardizeTable[102X ([14X47.7-2[114X).[133X
  
  [1X47.7-1 CosetTableStandard[101X
  
  [33X[1;0Y[29X[2XCosetTableStandard[102X [32X global variable[133X
  
  [33X[0;0Yspecifies  the  definition  of  a  [13Xstandard coset table[113X. It is used whenever
  coset  tables  or  augmented  coset  tables  are  created.  Its value may be
  [10X"lenlex"[110X   or   [10X"semilenlex"[110X.  If  it  is  [10X"lenlex"[110X  coset  tables  will  be
  standardized  using all their columns as defined in Charles Sims' book (this
  is  the  new  default  standard  of [5XGAP[105X). If it is [10X"semilenlex"[110X they will be
  standardized  using  only their generator columns (this was the original [5XGAP[105X
  standard). The default value of [2XCosetTableStandard[102X is [10X"lenlex"[110X.[133X
  
  [1X47.7-2 StandardizeTable[101X
  
  [33X[1;0Y[29X[2XStandardizeTable[102X( [3Xtable[103X, [3Xstandard[103X ) [32X function[133X
  
  [33X[0;0Ystandardizes  the  given coset table [3Xtable[103X. The second argument is optional.
  It  defines  the  standard  to  be  used,  its  values  may  be  [10X"lenlex"[110X or
  [10X"semilenlex"[110X  specifying  the new or the old convention, respectively. If no
  value  for  the  parameter  [3Xstandard[103X  is  provided the function will use the
  global  variable [2XCosetTableStandard[102X ([14X47.7-1[114X) instead. Note that the function
  alters the given table, it does not create a copy.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XStandardizeTable( tab, "semilenlex" );[127X[104X
    [4X[25Xgap>[125X [27XPrintArray( TransposedMat( tab ) );[127X[104X
    [4X[28X[ [  1,  1,  2,  4 ],[128X[104X
    [4X[28X  [  3,  3,  4,  1 ],[128X[104X
    [4X[28X  [  2,  2,  3,  3 ],[128X[104X
    [4X[28X  [  5,  5,  1,  2 ],[128X[104X
    [4X[28X  [  4,  4,  5,  5 ] ][128X[104X
  [4X[32X[104X
  
  
  [1X47.8 [33X[0;0YCoset tables for subgroups in the whole group[133X[101X
  
  [1X47.8-1 CosetTableInWholeGroup[101X
  
  [33X[1;0Y[29X[2XCosetTableInWholeGroup[102X( [3XH[103X ) [32X attribute[133X
  [33X[1;0Y[29X[2XTryCosetTableInWholeGroup[102X( [3XH[103X ) [32X operation[133X
  
  [33X[0;0Yis  equivalent to [10XCosetTable([3XG[103X[10X,[3XH[103X[10X)[110X where [3XG[103X is the (unique) finitely presented
  group  such  that  [3XH[103X  is  a  subgroup  of  [3XG[103X.  It  overrides a [10Xsilent[110X option
  (see [2XCosetTableFromGensAndRels[102X ([14X47.6-5[114X)) with [9Xfalse[109X.[133X
  
  [33X[0;0YThe  variant  [2XTryCosetTableInWholeGroup[102X  does not override the [10Xsilent[110X option
  with  [9Xfalse[109X  in  case  a coset table is only wanted if not too expensive. It
  will    store    a    result   that   is   not   [9Xfail[109X   in   the   attribute
  [2XCosetTableInWholeGroup[102X.[133X
  
  [1X47.8-2 SubgroupOfWholeGroupByCosetTable[101X
  
  [33X[1;0Y[29X[2XSubgroupOfWholeGroupByCosetTable[102X( [3Xfpfam[103X, [3Xtab[103X ) [32X function[133X
  
  [33X[0;0Ytakes  a  family  [3Xfpfam[103X of an FpGroup and a standardized coset table [3Xtab[103X and
  returns  the  subgroup of [3Xfpfam[103X[10X!.wholeGroup[110X defined by this coset table. The
  function  will  not  check  whether  the  coset  table  is standardized. See
  also [2XCosetTableBySubgroup[102X ([14X47.6-4[114X).[133X
  
  
  [1X47.9 [33X[0;0YAugmented Coset Tables and Rewriting[133X[101X
  
  [1X47.9-1 AugmentedCosetTableInWholeGroup[101X
  
  [33X[1;0Y[29X[2XAugmentedCosetTableInWholeGroup[102X( [3XH[103X[, [3Xgens[103X] ) [32X function[133X
  
  [33X[0;0YFor  a  subgroup  [3XH[103X  of a finitely presented group, this function returns an
  augmented  coset  table.  If a generator set [3Xgens[103X is given, it is guaranteed
  that  [3Xgens[103X will be a subset of the primary and secondary subgroup generators
  of this coset table.[133X
  
  [33X[0;0YIt  is  mutable so we are permitted to add further entries. However existing
  entries  may  not be changed. Any entries added however should correspond to
  the subgroup only and not to a homomorphism.[133X
  
  [1X47.9-2 AugmentedCosetTableMtc[101X
  
  [33X[1;0Y[29X[2XAugmentedCosetTableMtc[102X( [3XG[103X, [3XH[103X, [3Xtype[103X, [3Xstring[103X ) [32X function[133X
  
  [33X[0;0Yis  an  internal  function  used  by  the  subgroup  presentation  functions
  described  in  [14X48.2[114X. It applies a Modified Todd-Coxeter coset representative
  enumeration  to  construct an augmented coset table (see [14X48.2[114X) for the given
  subgroup  [3XH[103X  of  [3XG[103X.  The subgroup generators will be named [3Xstring[103X[10X1[110X, [3Xstring[103X[10X2[110X,
  [22X...[122X.[133X
  
  [33X[0;0YThe  function  accepts  the  options  [10Xmax[110X  and  [10Xsilent[110X  as described for the
  function [2XCosetTableFromGensAndRels[102X ([14X47.6-5[114X).[133X
  
  [1X47.9-3 AugmentedCosetTableRrs[101X
  
  [33X[1;0Y[29X[2XAugmentedCosetTableRrs[102X( [3XG[103X, [3Xtable[103X, [3Xtype[103X, [3Xstring[103X ) [32X function[133X
  
  [33X[0;0Yis  an  internal  function  used  by  the  subgroup  presentation  functions
  described  in  [14X48.2[114X.  It applies the Reduced Reidemeister-Schreier method to
  construct an augmented coset table for the subgroup of [3XG[103X which is defined by
  the  given  coset  table  [3Xtable[103X.  The  new subgroup generators will be named
  [3Xstring[103X[10X1[110X, [3Xstring[103X[10X2[110X, [22X...[122X.[133X
  
  [1X47.9-4 RewriteWord[101X
  
  [33X[1;0Y[29X[2XRewriteWord[102X( [3Xaug[103X, [3Xword[103X ) [32X function[133X
  
  [33X[0;0Y[2XRewriteWord[102X rewrites [3Xword[103X (which must be a word in the underlying free group
  with  respect  to  which  the  augmented  coset  table  [3Xaug[103X is given) in the
  subgroup  generators  given  by  the augmented coset table [3Xaug[103X. It returns a
  Tietze-type  word  (i.e. a  list  of integers), referring to the primary and
  secondary generators of [3Xaug[103X.[133X
  
  [33X[0;0YIf [3Xword[103X is not contained in the subgroup, [9Xfail[109X is returned.[133X
  
  
  [1X47.10 [33X[0;0YLow Index Subgroups[133X[101X
  
  [1X47.10-1 LowIndexSubgroupsFpGroupIterator[101X
  
  [33X[1;0Y[29X[2XLowIndexSubgroupsFpGroupIterator[102X( [3XG[103X[, [3XH[103X], [3Xindex[103X[, [3Xexcluded[103X] ) [32X operation[133X
  [33X[1;0Y[29X[2XLowIndexSubgroupsFpGroup[102X( [3XG[103X[, [3XH[103X], [3Xindex[103X[, [3Xexcluded[103X] ) [32X operation[133X
  
  [33X[0;0YThese   functions  compute  representatives  of  the  conjugacy  classes  of
  subgroups of the finitely presented group [3XG[103X that contain the subgroup [3XH[103X of [3XG[103X
  and that have index less than or equal to [3Xindex[103X.[133X
  
  [33X[0;0Y[2XLowIndexSubgroupsFpGroupIterator[102X  returns an iterator (see [14X30.8[114X) that can be
  used  to  run over these subgroups, and [2XLowIndexSubgroupsFpGroup[102X returns the
  list of these subgroups. If one is interested only in one or a few subgroups
  up to a given index then preferably the iterator should be used.[133X
  
  [33X[0;0YIf the optional argument [3Xexcluded[103X has been specified, then it is expected to
  be a list of words in the free generators of the underlying free group of [3XG[103X,
  and  [2XLowIndexSubgroupsFpGroup[102X  returns only those subgroups of index at most
  [3Xindex[103X  that  contain [3XH[103X, but do not contain any conjugate of any of the group
  elements defined by these words.[133X
  
  [33X[0;0YIf not given, [3XH[103X defaults to the trivial subgroup.[133X
  
  [33X[0;0YThe  algorithm  used finds the requested subgroups by systematically running
  through  a  tree  of all potential coset tables of [3XG[103X of length at most [3Xindex[103X
  (where it skips all branches of that tree for which it knows in advance that
  they  cannot provide new classes of such subgroups). The time required to do
  this  depends,  of  course, on the presentation of [3XG[103X, but in general it will
  grow  exponentially  with  the value of [3Xindex[103X. So you should be careful with
  the choice of [3Xindex[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xli:=LowIndexSubgroupsFpGroup( g, TrivialSubgroup( g ), 10 );[127X[104X
    [4X[28X[ Group(<fp, no generators known>), Group(<fp, no generators known>),[128X[104X
    [4X[28X  Group(<fp, no generators known>), Group(<fp, no generators known>) ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YBy  default,  the  algorithm  computes no generating sets for the subgroups.
  This can be enforced with [2XGeneratorsOfGroup[102X ([14X39.2-4[114X):[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XGeneratorsOfGroup(li[2]);[127X[104X
    [4X[28X[ a, b*a*b^-1 ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YIf  we  are interested just in one (proper) subgroup of index at most [22X10[122X, we
  can  use  the function that returns an iterator. The first subgroup found is
  the  group  itself,  except  if  a list of excluded elements is entered (see
  below), so we look at the second subgroup.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xiter:= LowIndexSubgroupsFpGroupIterator( g, 10 );;[127X[104X
    [4X[25Xgap>[125X [27Xs1:= NextIterator( iter );;  Index( g, s1 );[127X[104X
    [4X[28X1[128X[104X
    [4X[25Xgap>[125X [27XIsDoneIterator( iter );[127X[104X
    [4X[28Xfalse[128X[104X
    [4X[25Xgap>[125X [27Xs2:= NextIterator( iter );;  s2 = li[2];[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [33X[0;0YAs  an  example  for  an  application of the optional parameter [3Xexcluded[103X, we
  compute  all conjugacy classes of torsion free subgroups of index at most [22X24[122X
  in  the  group  [22XG = ⟨ x,y,z ∣ x^2, y^4, z^3, (xy)^3, (yz)^2, (xz)^3 ⟩[122X. It is
  know  from  theory that each torsion element of this group is conjugate to a
  power  of  [22Xx[122X,  [22Xy[122X,  [22Xz[122X,  [22Xxy[122X, [22Xxz[122X, or [22Xyz[122X. (Note that this includes conjugates of
  [22Xy^2[122X.)[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XF := FreeGroup( "x", "y", "z" );;[127X[104X
    [4X[25Xgap>[125X [27Xx := F.1;; y := F.2;; z := F.3;;[127X[104X
    [4X[25Xgap>[125X [27XG := F / [ x^2, y^4, z^3, (x*y)^3, (y*z)^2, (x*z)^3 ];;[127X[104X
    [4X[25Xgap>[125X [27Xtorsion := [ x, y, y^2, z, x*y, x*z, y*z ];;[127X[104X
    [4X[25Xgap>[125X [27XSetInfoLevel( InfoFpGroup, 2 );[127X[104X
    [4X[25Xgap>[125X [27Xlis := LowIndexSubgroupsFpGroup(G, TrivialSubgroup(G), 24, torsion);;[127X[104X
    [4X[28X#I  LowIndexSubgroupsFpGroup called[128X[104X
    [4X[28X#I   class 1 of index 24 and length 8[128X[104X
    [4X[28X#I   class 2 of index 24 and length 24[128X[104X
    [4X[28X#I   class 3 of index 24 and length 24[128X[104X
    [4X[28X#I   class 4 of index 24 and length 24[128X[104X
    [4X[28X#I   class 5 of index 24 and length 24[128X[104X
    [4X[28X#I  LowIndexSubgroupsFpGroup done. Found 5 classes[128X[104X
    [4X[25Xgap>[125X [27XSetInfoLevel( InfoFpGroup, 0 );[127X[104X
  [4X[32X[104X
  
  [33X[0;0YIf  a  particular  image group is desired, the operation [2XGQuotients[102X ([14X40.9-4[114X)
  (see [14X47.14[114X) can be useful as well.[133X
  
  
  [1X47.11 [33X[0;0YConverting Groups to Finitely Presented Groups[133X[101X
  
  [1X47.11-1 IsomorphismFpGroup[101X
  
  [33X[1;0Y[29X[2XIsomorphismFpGroup[102X( [3XG[103X ) [32X attribute[133X
  
  [33X[0;0Yreturns an isomorphism from the given finite group [3XG[103X to a finitely presented
  group  isomorphic  to [3XG[103X. The function first [13Xchooses a set of generators of [3XG[103X[113X
  and then computes a presentation in terms of these generators.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xg := Group( (2,3,4,5), (1,2,5) );;[127X[104X
    [4X[25Xgap>[125X [27Xiso := IsomorphismFpGroup( g );[127X[104X
    [4X[28X[ (1,2), (2,3), (3,4), (4,5) ] -> [ F1, F2, F3, F4 ][128X[104X
    [4X[25Xgap>[125X [27Xfp := Image( iso );[127X[104X
    [4X[28X<fp group of size 120 on the generators [ F1, F2, F3, F4 ]>[128X[104X
    [4X[25Xgap>[125X [27XRelatorsOfFpGroup( fp );[127X[104X
    [4X[28X[ F1^2, F2^2, F3^2, F4^2, (F1*F2)^3, (F1*F3)^2, (F1*F4)^2, (F2*F3)^3,[128X[104X
    [4X[28X  (F2*F4)^2, (F3*F4)^3 ][128X[104X
  [4X[32X[104X
  
  [1X47.11-2 IsomorphismFpGroupByGenerators[101X
  
  [33X[1;0Y[29X[2XIsomorphismFpGroupByGenerators[102X( [3XG[103X, [3Xgens[103X[, [3Xstring[103X] ) [32X function[133X
  [33X[1;0Y[29X[2XIsomorphismFpGroupByGeneratorsNC[102X( [3XG[103X, [3Xgens[103X, [3Xstring[103X ) [32X operation[133X
  
  [33X[0;0Yreturns an isomorphism from a finite group [3XG[103X to a finitely presented group [3XF[103X
  isomorphic to [3XG[103X. The generators of [3XF[103X correspond to the [13Xgenerators of [3XG[103X given
  in  the  list  [3Xgens[103X[113X. If [3Xstring[103X is given it is used to name the generators of
  the finitely presented group.[133X
  
  [33X[0;0YThe [10XNC[110X version will avoid testing whether the elements in [3Xgens[103X generate [3XG[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XSetInfoLevel( InfoFpGroup, 1 );[127X[104X
    [4X[25Xgap>[125X [27Xiso := IsomorphismFpGroupByGenerators( g, [ (1,2), (1,2,3,4,5) ] );[127X[104X
    [4X[28X#I  the image group has 2 gens and 5 rels of total length 39[128X[104X
    [4X[28X[ (1,2), (1,2,3,4,5) ] -> [ F1, F2 ][128X[104X
    [4X[25Xgap>[125X [27Xfp := Image( iso );[127X[104X
    [4X[28X<fp group of size 120 on the generators [ F1, F2 ]>[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThe  main  task  of the function [2XIsomorphismFpGroupByGenerators[102X is to find a
  presentation  of  [3XG[103X  in  the  provided  generators  [3Xgens[103X.  In  the case of a
  permutation group [3XG[103X it does this by first constructing a stabilizer chain of
  [3XG[103X  and  then  it  works  through  that  chain  from  the  bottom to the top,
  recursively  computing  a presentation for each of the involved stabilizers.
  The   method   used  is  essentially  an  implementation  of  John  Cannon's
  multi-stage  relations-finding  algorithm  as described in [Neu82] (see also
  [Can73]  for a more graph theoretical description). Moreover, it makes heavy
  use  of  Tietze  transformations  in each stage to avoid an explosion of the
  total length of the relators.[133X
  
  [33X[0;0YNote  that because of the random methods involved in the construction of the
  stabilizer  chain  the  resulting  presentations  of  [3XG[103X  will  in general be
  different for repeated calls with the same arguments.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XM12 := MathieuGroup( 12 );[127X[104X
    [4X[28XGroup([ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6),[128X[104X
    [4X[28X  (1,12)(2,11)(3,6)(4,8)(5,9)(7,10) ])[128X[104X
    [4X[25Xgap>[125X [27Xgens := GeneratorsOfGroup( M12 );;[127X[104X
    [4X[25Xgap>[125X [27Xiso := IsomorphismFpGroupByGenerators( M12, gens );;[127X[104X
    [4X[28X#I  the image group has 3 gens and 24 rels of total length 669[128X[104X
    [4X[25Xgap>[125X [27Xiso := IsomorphismFpGroupByGenerators( M12, gens );;[127X[104X
    [4X[28X#I  the image group has 3 gens and 20 rels of total length 414[128X[104X
  [4X[32X[104X
  
  [33X[0;0YAlso    in   the   case   of   a   permutation   group   [3XG[103X,   the   function
  [2XIsomorphismFpGroupByGenerators[102X  supports  the option [10Xmethod[110X that can be used
  to modify the strategy. The option [10Xmethod[110X may take the following values.[133X
  
  [8X[10Xmethod := "regular"[110X[8X[108X
        [33X[0;6YThis  may  be  specified  for groups of small size, up to [22X10^5[122X say. It
        implies  that the function first constructs a regular representation [3XR[103X
        of  [3XG[103X and then a presentation of [3XR[103X. In general, this presentation will
        be  much  more concise than the default one, but the price is the time
        needed for the construction of [3XR[103X.[133X
  
  [8X[10Xmethod := [ "regular", bound ][110X[8X[108X
        [33X[0;6YThis  is a refinement of the previous possibility. In this case, [10Xbound[110X
        should  be  an  integer,  and  if so the method [10X"regular"[110X as described
        above  is applied to the largest stabilizer in the stabilizer chain of
        [3XG[103X  whose size does not exceed the given bound and then the multi-stage
        algorithm  is used to work through the chain from that subgroup to the
        top.[133X
  
  [8X[10Xmethod := "fast"[110X[8X[108X
        [33X[0;6YThis  chooses  an  alternative  method  which essentially is a kind of
        multi-stage  algorithm  for  a stabilizer chain of [3XG[103X but does not make
        any attempt do reduce the number of relators as it is done in Cannon's
        algorithm  or  to  reduce  their  total length. Hence it is often much
        faster  than the default method, but the total length of the resulting
        presentation may be huge.[133X
  
  [8X[10Xmethod := "default"[110X[8X[108X
        [33X[0;6YThis  simply means that the default method shall be used, which is the
        case if the option [10Xmethod[110X is not given a value.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xiso := IsomorphismFpGroupByGenerators( M12, gens :[127X[104X
    [4X[25X>[125X [27X                                          method := "regular" );;[127X[104X
    [4X[28X#I  the image group has 3 gens and 11 rels of total length 92[128X[104X
    [4X[25Xgap>[125X [27Xiso := IsomorphismFpGroupByGenerators( M12, gens :[127X[104X
    [4X[25X>[125X [27X                                          method := "fast" );;[127X[104X
    [4X[28X#I  the image group has 3 gens and 136 rels of total length 3170[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThough  the  option  [10Xmethod  :=  "regular"[110X  is only checked in the case of a
  permutation  group  it  also  affects the performance and the results of the
  function  [2XIsomorphismFpGroupByGenerators[102X  for other groups, e. g. for matrix
  groups. This happens because, for these groups, the function first calls the
  function  [2XNiceMonomorphism[102X  ([14X40.5-2[114X)  to get a bijective action homomorphism
  from  [3XG[103X to a suitable permutation group, [22XP[122X say, and then, recursively, calls
  itself for the group [22XP[122X so that now the option becomes relevant.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XG := ImfMatrixGroup( 5, 1, 3 );[127X[104X
    [4X[28XImfMatrixGroup(5,1,3)[128X[104X
    [4X[25Xgap>[125X [27Xgens := GeneratorsOfGroup( G );[127X[104X
    [4X[28X[ [ [ -1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 0, 1, 0 ],[128X[104X
    [4X[28X      [ -1, -1, -1, -1, 2 ], [ -1, 0, 0, 0, 1 ] ],[128X[104X
    [4X[28X  [ [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ],[128X[104X
    [4X[28X      [ 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1 ] ] ][128X[104X
    [4X[25Xgap>[125X [27Xiso := IsomorphismFpGroupByGenerators( G, gens );;[127X[104X
    [4X[28X#I  the image group has 2 gens and 11 rels of total length 120[128X[104X
    [4X[25Xgap>[125X [27Xiso := IsomorphismFpGroupByGenerators( G, gens :[127X[104X
    [4X[25X>[125X [27X                                          method := "regular");;[127X[104X
    [4X[28X#I  the image group has 2 gens and 6 rels of total length 56[128X[104X
    [4X[25Xgap>[125X [27XSetInfoLevel( InfoFpGroup, 0 );[127X[104X
    [4X[25Xgap>[125X [27Xiso;[127X[104X
    [4X[28X<composed isomorphism:[ [ [ -1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, \[128X[104X
    [4X[28X0, 0, 1, 0 ], [ -1, -1, -1, -1, 2 ], [ -1, 0, 0, 0, 1 ] ], [ [ 0, 1, 0\[128X[104X
    [4X[28X, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ], [ 1, 0, 0, 0, 0 ], [ 0\[128X[104X
    [4X[28X, 0, 0, 0, 1 ] ] ]->[ F1, F2 ]>[128X[104X
    [4X[25Xgap>[125X [27XConstituentsCompositionMapping(iso);[127X[104X
    [4X[28X[ <action isomorphism>,[128X[104X
    [4X[28X  [ (2,3,4)(5,6)(8,9,10), (1,2,3,5)(6,7,8,9) ] -> [ F1, F2 ] ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YSince  [5XGAP[105X  cannot decompose elements of a matrix group into generators, the
  resulting isomorphism is stored as a composition of a (faithful) permutation
  action  on  vectors  and  a  homomorphism  from the permutation image to the
  finitely  presented  group. In such a situation the constituent mappings can
  be  obtained  via  [2XConstituentsCompositionMapping[102X  ([14X32.2-8[114X)  as separate [5XGAP[105X
  objects.[133X
  
  
  [1X47.12 [33X[0;0YNew Presentations and Presentations for Subgroups[133X[101X
  
  [33X[0;0Y[2XIsomorphismFpGroup[102X  ([14X47.11-1[114X)  is  also  used  to  compute  a  new  finitely
  presented  group  that  is  isomorphic  to  the given subgroup of a finitely
  presented  group.  (This  is  typically  the  only  method  to  compute with
  subgroups of a finitely presented group.)[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf:=FreeGroup(2);;[127X[104X
    [4X[25Xgap>[125X [27Xg:=f/[f.1^2,f.2^3,(f.1*f.2)^5];[127X[104X
    [4X[28X<fp group on the generators [ f1, f2 ]>[128X[104X
    [4X[25Xgap>[125X [27Xu:=Subgroup(g,[g.1*g.2]);[127X[104X
    [4X[28XGroup([ f1*f2 ])[128X[104X
    [4X[25Xgap>[125X [27Xhom:=IsomorphismFpGroup(u);[127X[104X
    [4X[28X[ <[ [ 1, 1 ] ]|f2^-1*f1^-1> ] -> [ F1 ][128X[104X
    [4X[25Xgap>[125X [27Xnew:=Range(hom);[127X[104X
    [4X[28X<fp group on the generators [ F1 ]>[128X[104X
    [4X[25Xgap>[125X [27XList(GeneratorsOfGroup(new),i->PreImagesRepresentative(hom,i));[127X[104X
    [4X[28X[ <[ [ 1, 1 ] ]|f2^-1*f1^-1> ][128X[104X
  [4X[32X[104X
  
  [33X[0;0YWhen  working  with such homomorphisms, some subgroup elements are expressed
  as  extremely  long  words in the group generators. Therefore the underlying
  words  of  subgroup  generators  stored  in  the isomorphism (as obtained by
  [2XMappingGeneratorsImages[102X  ([14X40.10-2[114X)  and  displayed  when [2XView[102X ([14X6.3-3[114X)ing the
  homomorphism)  as well as preimages under the homomorphism are stored in the
  form  of  straight  line program elements (see [14X37.9[114X). These will behave like
  ordinary words and no extra treatment should be necessary.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xr:=Range(hom).1^10;[127X[104X
    [4X[28XF1^10[128X[104X
    [4X[25Xgap>[125X [27Xp:=PreImagesRepresentative(hom,r);[127X[104X
    [4X[28X<[ [ 1, 10 ] ]|(f2^-1*f1^-1)^10>[128X[104X
  [4X[32X[104X
  
  [33X[0;0YIf  desired,  it  also  is  possible to convert these underlying words using
  [2XEvalStraightLineProgElm[102X ([14X37.9-4[114X):[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xr:=EvalStraightLineProgElm(UnderlyingElement(p));[127X[104X
    [4X[28X(f2^-1*f1^-1)^10[128X[104X
    [4X[25Xgap>[125X [27Xp:=ElementOfFpGroup(FamilyObj(p),r);[127X[104X
    [4X[28X(f2^-1*f1^-1)^10[128X[104X
  [4X[32X[104X
  
  [33X[0;0Y(If  you are only interested in a finitely presented group isomorphic to the
  given  subgroup  but  not in the isomorphism, you may also use the functions
  [2XPresentationViaCosetTable[102X  ([14X48.1-5[114X)  and  [2XFpGroupPresentation[102X  ([14X48.1-4[114X) (see
  [14X48.1[114X).)[133X
  
  [33X[0;0YHomomorphisms  can  also  be used to obtain an isomorphic finitely presented
  group with a (hopefully) simpler presentation.[133X
  
  [1X47.12-1 IsomorphismSimplifiedFpGroup[101X
  
  [33X[1;0Y[29X[2XIsomorphismSimplifiedFpGroup[102X( [3XG[103X ) [32X attribute[133X
  
  [33X[0;0Yapplies  Tietze  transformations  to a copy of the presentation of the given
  finitely  presented group [3XG[103X in order to reduce it with respect to the number
  of generators, the number of relators, and the relator lengths.[133X
  
  [33X[0;0YThe  operation  returns  an  isomorphism  with  source  [3XG[103X,  range  a group [3XH[103X
  isomorphic  to  [3XG[103X,  so  that the presentation of [3XH[103X has been simplified using
  Tietze transformations.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf:=FreeGroup(3);;[127X[104X
    [4X[25Xgap>[125X [27Xg:=f/[f.1^2,f.2^3,(f.1*f.2)^5,f.1/f.3];[127X[104X
    [4X[28X<fp group on the generators [ f1, f2, f3 ]>[128X[104X
    [4X[25Xgap>[125X [27Xhom:=IsomorphismSimplifiedFpGroup(g);[127X[104X
    [4X[28X[ f1, f2, f3 ] -> [ f1, f2, f1 ][128X[104X
    [4X[25Xgap>[125X [27XRange(hom);[127X[104X
    [4X[28X<fp group on the generators [ f1, f2 ]>[128X[104X
    [4X[25Xgap>[125X [27XRelatorsOfFpGroup(Range(hom));[127X[104X
    [4X[28X[ f1^2, f2^3, (f1*f2)^5 ][128X[104X
    [4X[25Xgap>[125X [27XRelatorsOfFpGroup(g);[127X[104X
    [4X[28X[ f1^2, f2^3, (f1*f2)^5, f1*f3^-1 ][128X[104X
  [4X[32X[104X
  
  [33X[0;0Y[2XIsomorphismSimplifiedFpGroup[102X  uses  Tietze  transformations  to simplify the
  presentation, see [14X48.1-6[114X.[133X
  
  
  [1X47.13 [33X[0;0YPreimages under Homomorphisms from an FpGroup[133X[101X
  
  [33X[0;0YFor  some  subgroups  of  a  finitely presented group the number of subgroup
  generators  increases  with  the  index of the subgroup. However often these
  generators  are  not  needed  at  all  for further calculations, but what is
  needed  is the action of the cosets of the subgroup. This gives the image of
  the  subgroup  in  a finite quotient and this finite quotient can be used to
  calculate normalizers, closures, intersections and so forth [Hul01].[133X
  
  [33X[0;0YThe  same  applies  for  subgroups  that  are  obtained  as  preimages under
  homomorphisms.[133X
  
  [1X47.13-1 SubgroupOfWholeGroupByQuotientSubgroup[101X
  
  [33X[1;0Y[29X[2XSubgroupOfWholeGroupByQuotientSubgroup[102X( [3Xfpfam[103X, [3XQ[103X, [3XU[103X ) [32X function[133X
  
  [33X[0;0Ytakes  a FpGroup family [3Xfpfam[103X, a finitely generated group [3XQ[103X such that the fp
  generators   of  [3Xfpfam[103X  can  be  mapped  by  an  epimorphism  [22Xphi[122X  onto  the
  [2XGeneratorsOfGroup[102X ([14X39.2-4[114X) value of [3XQ[103X, and a subgroup [3XU[103X of [3XQ[103X. It returns the
  subgroup of [3Xfpfam[103X[10X!.wholeGroup[110X which is the full preimage of [3XU[103X under [22Xphi[122X.[133X
  
  [1X47.13-2 IsSubgroupOfWholeGroupByQuotientRep[101X
  
  [33X[1;0Y[29X[2XIsSubgroupOfWholeGroupByQuotientRep[102X( [3XG[103X ) [32X Representation[133X
  
  [33X[0;0Yis  the  representation  for  subgroups  of  an FpGroup, given by a quotient
  subgroup.  The  components  [3XG[103X[10X!.quot[110X  and  [3XG[103X[10X!.sub[110X hold quotient, respectively
  subgroup.[133X
  
  [1X47.13-3 AsSubgroupOfWholeGroupByQuotient[101X
  
  [33X[1;0Y[29X[2XAsSubgroupOfWholeGroupByQuotient[102X( [3XU[103X ) [32X attribute[133X
  
  [33X[0;0Yreturns      the      same      subgroup      in      the     representation
  [2XAsSubgroupOfWholeGroupByQuotient[102X.[133X
  
  [33X[0;0YSee  also [2XSubgroupOfWholeGroupByCosetTable[102X ([14X47.8-2[114X) and [2XCosetTableBySubgroup[102X
  ([14X47.6-4[114X).[133X
  
  [33X[0;0YThis technique is used by [5XGAP[105X for example to represent the derived subgroup,
  which is obtained from the quotient [22XG/G'[122X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf:=FreeGroup(2);;g:=f/[f.1^6,f.2^6,(f.1*f.2)^6];;[127X[104X
    [4X[25Xgap>[125X [27Xd:=DerivedSubgroup(g);[127X[104X
    [4X[28XGroup(<fp, no generators known>)[128X[104X
    [4X[25Xgap>[125X [27XIndex(g,d);[127X[104X
    [4X[28X36[128X[104X
  [4X[32X[104X
  
  [1X47.13-4 DefiningQuotientHomomorphism[101X
  
  [33X[1;0Y[29X[2XDefiningQuotientHomomorphism[102X( [3XU[103X ) [32X function[133X
  
  [33X[0;0Yif      [3XU[103X      is      a     subgroup     in     quotient     representation
  ([2XIsSubgroupOfWholeGroupByQuotientRep[102X  ([14X47.13-2[114X)),  this function returns the
  defining homomorphism from the whole group to [3XU[103X[10X!.quot[110X.[133X
  
  
  [1X47.14 [33X[0;0YQuotient Methods[133X[101X
  
  [33X[0;0YAn  important  class  of  algorithms  for  finitely presented groups are the
  [13Xquotient  algorithms[113X  which  compute  quotient  groups  of  a given finitely
  presented  group. There are algorithms for epimorphisms onto abelian groups,
  [22Xp[122X-groups     and    solvable    groups.    (The    [21Xlow    index[121X    algorithm
  –[2XLowIndexSubgroupsFpGroup[102X  ([14X47.10-1[114X)–  can  be  considered  as  well  as  an
  algorithm that produces permutation group quotients.)[133X
  
  [33X[0;0Y[2XMaximalAbelianQuotient[102X ([14X39.18-4[114X), as defined for general groups, returns the
  largest abelian quotient of the given group.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf:=FreeGroup(2);;fp:=f/[f.1^6,f.2^6,(f.1*f.2)^12];[127X[104X
    [4X[28X<fp group on the generators [ f1, f2 ]>[128X[104X
    [4X[25Xgap>[125X [27Xhom:=MaximalAbelianQuotient(fp);[127X[104X
    [4X[28X[ f1, f2 ] -> [ f1, f3 ][128X[104X
    [4X[25Xgap>[125X [27XSize(Image(hom));[127X[104X
    [4X[28X36[128X[104X
  [4X[32X[104X
  
  [1X47.14-1 PQuotient[101X
  
  [33X[1;0Y[29X[2XPQuotient[102X( [3XF[103X, [3Xp[103X[, [3Xc[103X][, [3Xlogord[103X][, [3Xctype[103X] ) [32X function[133X
  
  [33X[0;0Ycomputes  a  factor  [3Xp[103X-group  of  a  finitely presented group [3XF[103X in form of a
  quotient  system.  The  quotient system can be converted into an epimorphism
  from  [3XF[103X  onto the [3Xp[103X-group computed by the function [2XEpimorphismQuotientSystem[102X
  ([14X47.14-2[114X).[133X
  
  [33X[0;0YFor  a  group [22XG[122X define the exponent-[22Xp[122X central series of [22XG[122X inductively by [22Xcal
  P_1(G)  =  G[122X and [22Xcal P_{i+1}(G) = [cal P_i(G),G]cal P_{i+1}(G)^p[122X. The factor
  groups modulo the terms of the lower exponent-[22Xp[122X central series are [22Xp[122X-groups.
  The group [22XG[122X has [22Xp[122X-class [22Xc[122X if [22Xcal P_c(G) ≠ cal P_{c+1}(G) = 1[122X.[133X
  
  [33X[0;0YThe  algorithm  computes  successive  quotients  modulo  the  terms  of  the
  exponent-[22Xp[122X  central  series  of  [3XF[103X.  If the parameter [3Xc[103X is present, then the
  factor  group modulo the [22X(c+1)[122X-th term of the exponent-[22Xp[122X central series of [3XF[103X
  is returned. If [3Xc[103X is not present, then the algorithm attempts to compute the
  largest  factor  [3Xp[103X-group  of  [3XF[103X.  In  case  [3XF[103X does not have a largest factor
  [3Xp[103X-group, the algorithm will not terminate.[133X
  
  [33X[0;0YBy  default  the algorithm computes only with factor groups of order at most
  [22Xp^256[122X.  If  the  parameter  [3Xlogord[103X  is  present, it will compute with factor
  groups  of  order at most [22Xp^[3Xlogord[103X[122X. If this parameter is specified, then the
  parameter [3Xc[103X must also be given. The present implementation produces an error
  message   if   the   order  of  a  [22Xp[122X-quotient  exceeds  [22Xp^256[122X  or  [22Xp^[3Xlogord[103X[122X,
  respectively.  Note  that  the  order of intermediate [22Xp[122X-groups may be larger
  than the final order of a [22Xp[122X-quotient.[133X
  
  [33X[0;0YThe  parameter  [3Xctype[103X  determines  the  type  of  collector that is used for
  computations  within  the  factor  [3Xp[103X-group. [3Xctype[103X must either be [10X"single"[110X in
  which  case  a  simple collector from the left is used or [10X"combinatorial"[110X in
  which case a combinatorial collector from the left is used.[133X
  
  [1X47.14-2 EpimorphismQuotientSystem[101X
  
  [33X[1;0Y[29X[2XEpimorphismQuotientSystem[102X( [3Xquotsys[103X ) [32X operation[133X
  
  [33X[0;0YFor   a  quotient  system  [3Xquotsys[103X  obtained  from  the  function  [2XPQuotient[102X
  ([14X47.14-1[114X),  this  operation  returns  an  epimorphism  [22X[3XF[103X  → [3XP[103X[122X where [22X[3XF[103X[122X is the
  finitely presented group of which [3Xquotsys[103X is a quotient system and [22X[3XP[103X[122X is a pc
  group isomorphic to the quotient of [3XF[103X determined by [3Xquotsys[103X.[133X
  
  [33X[0;0YDifferent  calls to this operation will create different groups [3XP[103X, each with
  its own family.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XPQuotient( FreeGroup(2), 5, 10, 1024, "combinatorial" );[127X[104X
    [4X[28X<5-quotient system of 5-class 10 with 520 generators>[128X[104X
    [4X[25Xgap>[125X [27Xphi := EpimorphismQuotientSystem( last );[127X[104X
    [4X[28X[ f1, f2 ] -> [ a1, a2 ][128X[104X
    [4X[25Xgap>[125X [27XCollected( Factors( Size( Image( phi ) ) ) );[127X[104X
    [4X[28X[ [ 5, 520 ] ][128X[104X
  [4X[32X[104X
  
  [1X47.14-3 EpimorphismPGroup[101X
  
  [33X[1;0Y[29X[2XEpimorphismPGroup[102X( [3Xfpgrp[103X, [3Xp[103X[, [3Xcl[103X] ) [32X operation[133X
  
  [33X[0;0Ycomputes  an  epimorphism  from  the  finitely  presented group [3Xfpgrp[103X to the
  largest  [22Xp[122X-group  of  [22Xp[122X-class  [3Xcl[103X  which  is  a  quotient of [3Xfpgrp[103X. If [3Xcl[103X is
  omitted,  the  largest  finite  [22Xp[122X-group  quotient (of [22Xp[122X-class up to [22X1000[122X) is
  determined.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xhom:=EpimorphismPGroup(fp,2);[127X[104X
    [4X[28X[ f1, f2 ] -> [ a1, a2 ][128X[104X
    [4X[25Xgap>[125X [27XSize(Image(hom));[127X[104X
    [4X[28X8[128X[104X
    [4X[25Xgap>[125X [27Xhom:=EpimorphismPGroup(fp,3,7);[127X[104X
    [4X[28X[ f1, f2 ] -> [ a1, a2 ][128X[104X
    [4X[25Xgap>[125X [27XSize(Image(hom));[127X[104X
    [4X[28X6561[128X[104X
  [4X[32X[104X
  
  [1X47.14-4 EpimorphismNilpotentQuotient[101X
  
  [33X[1;0Y[29X[2XEpimorphismNilpotentQuotient[102X( [3Xfpgrp[103X[, [3Xn[103X] ) [32X function[133X
  
  [33X[0;0Yreturns  an  epimorphism  on  the  class  [3Xn[103X finite nilpotent quotient of the
  finitely  presented  group  [3Xfpgrp[103X.  If  [3Xn[103X  is  omitted,  the  largest finite
  nilpotent quotient (of [22Xp[122X-class up to [22X1000[122X) is taken.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xhom:=EpimorphismNilpotentQuotient(fp,7);[127X[104X
    [4X[28X[ f1, f2 ] -> [ f1*f4, f2*f5 ][128X[104X
    [4X[25Xgap>[125X [27XSize(Image(hom));[127X[104X
    [4X[28X52488[128X[104X
  [4X[32X[104X
  
  [33X[0;0YA related operation which is also applicable to finitely presented groups is
  [2XGQuotients[102X  ([14X40.9-4[114X),  which  computes  all  epimorphisms  from  a (finitely
  presented) group [3XF[103X onto a given (finite) group [3XG[103X.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27XGQuotients(fp,Group((1,2,3),(1,2)));[127X[104X
    [4X[28X[ [ f1, f2 ] -> [ (1,2), (2,3) ], [ f1, f2 ] -> [ (2,3), (1,2,3) ],[128X[104X
    [4X[28X  [ f1, f2 ] -> [ (1,2,3), (2,3) ] ][128X[104X
  [4X[32X[104X
  
  [1X47.14-5 SolvableQuotient[101X
  
  [33X[1;0Y[29X[2XSolvableQuotient[102X( [3XF[103X, [3Xsize[103X ) [32X function[133X
  [33X[1;0Y[29X[2XSolvableQuotient[102X( [3XF[103X, [3Xprimes[103X ) [32X function[133X
  [33X[1;0Y[29X[2XSolvableQuotient[102X( [3XF[103X, [3Xtuples[103X ) [32X function[133X
  [33X[1;0Y[29X[2XSQ[102X( [3XF[103X, [3X...[103X ) [32X function[133X
  
  [33X[0;0YThis  routine calls the solvable quotient algorithm for a finitely presented
  group  [3XF[103X.  The  quotient to be found can be specified in the following ways:
  Specifying  an  integer  [3Xsize[103X  finds  a quotient of size up to [3Xsize[103X (if such
  large  quotients  exist).  Specifying  a  list of primes in [3Xprimes[103X finds the
  largest  quotient  involving the given primes. Finally [3Xtuples[103X can be used to
  prescribe a chief series.[133X
  
  [33X[0;0Y[2XSQ[102X can be used as a synonym for [2XSolvableQuotient[102X.[133X
  
  [1X47.14-6 EpimorphismSolvableQuotient[101X
  
  [33X[1;0Y[29X[2XEpimorphismSolvableQuotient[102X( [3XF[103X, [3Xparam[103X ) [32X function[133X
  
  [33X[0;0Ycomputes  an  epimorphism  from  the  finitely  presented group [3Xfpgrp[103X to the
  largest  solvable  quotient given by [3Xparam[103X (specified as in [2XSolvableQuotient[102X
  ([14X47.14-5[114X)).[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf := FreeGroup( "a", "b", "c", "d" );;[127X[104X
    [4X[25Xgap>[125X [27Xfp := f / [ f.1^2, f.2^2, f.3^2, f.4^2, f.1*f.2*f.1*f.2*f.1*f.2,[127X[104X
    [4X[25X>[125X [27X f.2*f.3*f.2*f.3*f.2*f.3*f.2*f.3, f.3*f.4*f.3*f.4*f.3*f.4,[127X[104X
    [4X[25X>[125X [27Xf.1^-1*f.3^-1*f.1*f.3, f.1^-1*f.4^-1*f.1*f.4,[127X[104X
    [4X[25X>[125X [27Xf.2^-1*f.4^-1*f.2*f.4 ];;[127X[104X
    [4X[25Xgap>[125X [27Xhom:=EpimorphismSolvableQuotient(fp,300);Size(Image(hom));[127X[104X
    [4X[28X[ a, b, c, d ] -> [ f1*f2, f1*f2, f2*f3, f2 ][128X[104X
    [4X[28X12[128X[104X
    [4X[25Xgap>[125X [27Xhom:=EpimorphismSolvableQuotient(fp,[2,3]);Size(Image(hom));[127X[104X
    [4X[28X[ a, b, c, d ] -> [ f1*f2*f4, f1*f2*f6*f8, f2*f3, f2 ][128X[104X
    [4X[28X1152[128X[104X
  [4X[32X[104X
  
  [1X47.14-7 LargerQuotientBySubgroupAbelianization[101X
  
  [33X[1;0Y[29X[2XLargerQuotientBySubgroupAbelianization[102X( [3Xhom[103X, [3XU[103X ) [32X function[133X
  
  [33X[0;0YLet [3Xhom[103X a homomorphism from a finitely presented group [22XG[122X to a finite group [22XH[122X
  and  [22X[3XU[103X  ≤ H[122X. This function will –if it exists– return a subgroup [22XS ≤ [3XG[103X[122X, such
  that  the core of [22XS[122X is properly contained in the kernel of [3Xhom[103X as well as in
  the  derived  subgroup of [22XV[122X, where [22XV[122X is the pre-image of [3XU[103X under [3Xhom[103X. Thus [22XS[122X
  exposes  a  larger  quotient  of  [22XG[122X.  If  no  such  subgroup exists, [9Xfail[109X is
  returned.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xf:=FreeGroup("x","y","z");;[127X[104X
    [4X[25Xgap>[125X [27Xg:=f/ParseRelators(f,"x^3=y^3=z^5=(xyx^2y^2)^2=(xz)^2=(yz^3)^2=1");[127X[104X
    [4X[28X<fp group on the generators [ x, y, z ]>[128X[104X
    [4X[25Xgap>[125X [27Xl:=LowIndexSubgroupsFpGroup(g,6);;[127X[104X
    [4X[25Xgap>[125X [27XList(l,IndexInWholeGroup);[127X[104X
    [4X[28X[ 1, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6 ][128X[104X
    [4X[25Xgap>[125X [27Xq:=DefiningQuotientHomomorphism(l[6]);;p:=Image(q);Size(p);[127X[104X
    [4X[28XGroup([ (4,5,6), (1,2,3)(4,6,5), (2,4,6,3,5) ])[128X[104X
    [4X[28X360[128X[104X
    [4X[25Xgap>[125X [27Xs:=LargerQuotientBySubgroupAbelianization(q,SylowSubgroup(p,3));[127X[104X
    [4X[28XGroup(<fp, no generators known>)[128X[104X
    [4X[25Xgap>[125X [27XSize(Image(DefiningQuotientHomomorphism(s)));[127X[104X
    [4X[28X193273528320[128X[104X
  [4X[32X[104X
  
  
  [1X47.15 [33X[0;0YAbelian Invariants for Subgroups[133X[101X
  
  [33X[0;0YUsing  variations of coset enumeration it is possible to compute the abelian
  invariants  of  a subgroup of a finitely presented group without computing a
  complete  presentation  for  the subgroup in the first place. Typically, the
  operation  [2XAbelianInvariants[102X  ([14X39.16-1[114X)  when  called  for  subgroups should
  automatically  take  care  of  this,  but  in  case you want to have further
  control about the methods used, the following operations might be of use.[133X
  
  [1X47.15-1 AbelianInvariantsSubgroupFpGroup[101X
  
  [33X[1;0Y[29X[2XAbelianInvariantsSubgroupFpGroup[102X( [3XG[103X, [3XH[103X ) [32X function[133X
  
  [33X[0;0Y[2XAbelianInvariantsSubgroupFpGroup[102X        is        a        synonym       for
  [2XAbelianInvariantsSubgroupFpGroupRrs[102X ([14X47.15-3[114X).[133X
  
  [1X47.15-2 AbelianInvariantsSubgroupFpGroupMtc[101X
  
  [33X[1;0Y[29X[2XAbelianInvariantsSubgroupFpGroupMtc[102X( [3XG[103X, [3XH[103X ) [32X function[133X
  
  [33X[0;0Yuses the Modified Todd-Coxeter method to compute the abelian invariants of a
  subgroup [3XH[103X of a finitely presented group [3XG[103X.[133X
  
  
  [1X47.15-3 [33X[0;0YAbelianInvariantsSubgroupFpGroupRrs[133X[101X
  
  [33X[1;0Y[29X[2XAbelianInvariantsSubgroupFpGroupRrs[102X( [3XG[103X, [3XH[103X ) [32X function[133X
  [33X[1;0Y[29X[2XAbelianInvariantsSubgroupFpGroupRrs[102X( [3XG[103X, [3Xtable[103X ) [32X function[133X
  
  [33X[0;0Yuses  the  Reduced  Reidemeister-Schreier  method  to  compute  the  abelian
  invariants of a subgroup [3XH[103X of a finitely presented group [3XG[103X.[133X
  
  [33X[0;0YAlternatively  to the subgroup [3XH[103X, its coset table [3Xtable[103X in [3XG[103X may be given as
  second argument.[133X
  
  [1X47.15-4 AbelianInvariantsNormalClosureFpGroup[101X
  
  [33X[1;0Y[29X[2XAbelianInvariantsNormalClosureFpGroup[102X( [3XG[103X, [3XH[103X ) [32X function[133X
  
  [33X[0;0Y[2XAbelianInvariantsNormalClosureFpGroup[102X       is       a      synonym      for
  [2XAbelianInvariantsNormalClosureFpGroupRrs[102X ([14X47.15-5[114X).[133X
  
  [1X47.15-5 AbelianInvariantsNormalClosureFpGroupRrs[101X
  
  [33X[1;0Y[29X[2XAbelianInvariantsNormalClosureFpGroupRrs[102X( [3XG[103X, [3XH[103X ) [32X function[133X
  
  [33X[0;0Yuses  the  Reduced  Reidemeister-Schreier  method  to  compute  the  abelian
  invariants  of  the  normal  closure of a subgroup [3XH[103X of a finitely presented
  group [3XG[103X. See [14X48.2[114X for details on the different strategies.[133X
  
  [33X[0;0YThe  following  example  shows a calculation for the Coxeter group [22XB_1[122X. This
  calculation  and  a  similar one for [22XB_0[122X have been used to prove that [22XB_1' /
  B_1''  ≅  Z_2^9  ×  Z^3[122X  and  [22XB_0'  /  B_0'' ≅ Z_2^91 × Z^27[122X as stated in in
  [FJNT95, Proposition 5].[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27X# Define the Coxeter group E1.[127X[104X
    [4X[25Xgap>[125X [27XF := FreeGroup( "x1", "x2", "x3", "x4", "x5" );[127X[104X
    [4X[28X<free group on the generators [ x1, x2, x3, x4, x5 ]>[128X[104X
    [4X[25Xgap>[125X [27Xx1 := F.1;; x2 := F.2;; x3 := F.3;; x4 := F.4;; x5 := F.5;;[127X[104X
    [4X[25Xgap>[125X [27Xrels := [ x1^2, x2^2, x3^2, x4^2, x5^2,[127X[104X
    [4X[25X>[125X [27X (x1 * x3)^2, (x2 * x4)^2, (x1 * x2)^3, (x2 * x3)^3, (x3 * x4)^3,[127X[104X
    [4X[25X>[125X [27X (x4 * x1)^3, (x1 * x5)^3, (x2 * x5)^2, (x3 * x5)^3, (x4 * x5)^2,[127X[104X
    [4X[25X>[125X [27X (x1 * x2 * x3 * x4 * x3 * x2)^2 ];;[127X[104X
    [4X[25Xgap>[125X [27XE1 := F / rels;[127X[104X
    [4X[28X<fp group on the generators [ x1, x2, x3, x4, x5 ]>[128X[104X
    [4X[25Xgap>[125X [27Xx1 := E1.1;; x2 := E1.2;; x3 := E1.3;; x4 := E1.4;; x5 := E1.5;;[127X[104X
    [4X[25Xgap>[125X [27X# Get normal subgroup generators for B1.[127X[104X
    [4X[25Xgap>[125X [27XH := Subgroup( E1, [ x5 * x2^-1, x5 * x4^-1 ] );;[127X[104X
    [4X[25Xgap>[125X [27X# Compute the abelian invariants of B1/B1'.[127X[104X
    [4X[25Xgap>[125X [27XA := AbelianInvariantsNormalClosureFpGroup( E1, H );[127X[104X
    [4X[28X[ 2, 2, 2, 2, 2, 2, 2, 2 ][128X[104X
    [4X[25Xgap>[125X [27X# Compute a presentation for B1.[127X[104X
    [4X[25Xgap>[125X [27XP := PresentationNormalClosure( E1, H );[127X[104X
    [4X[28X<presentation with 18 gens and 46 rels of total length 132>[128X[104X
    [4X[25Xgap>[125X [27XSimplifyPresentation( P );[127X[104X
    [4X[28X#I  there are 8 generators and 30 relators of total length 148[128X[104X
    [4X[25Xgap>[125X [27XB1 := FpGroupPresentation( P );[127X[104X
    [4X[28X<fp group on the generators [ _x1, _x2, _x3, _x4, _x6, _x7, _x8, _x11[128X[104X
    [4X[28X ]>[128X[104X
    [4X[25Xgap>[125X [27X# Compute normal subgroup generators for B1'.[127X[104X
    [4X[25Xgap>[125X [27Xgens := GeneratorsOfGroup( B1 );;[127X[104X
    [4X[25Xgap>[125X [27Xnumgens := Length( gens );;[127X[104X
    [4X[25Xgap>[125X [27Xcomms := [ ];;[127X[104X
    [4X[25Xgap>[125X [27Xfor i in [ 1 .. numgens - 1 ] do[127X[104X
    [4X[25X>[125X [27X    for j in [i+1 .. numgens ] do[127X[104X
    [4X[25X>[125X [27X        Add( comms, Comm( gens[i], gens[j] ) );[127X[104X
    [4X[25X>[125X [27X    od;[127X[104X
    [4X[25X>[125X [27Xod;[127X[104X
    [4X[25Xgap>[125X [27X# Compute the abelian invariants of B1'/B1".[127X[104X
    [4X[25Xgap>[125X [27XK := Subgroup( B1, comms );;[127X[104X
    [4X[25Xgap>[125X [27XA := AbelianInvariantsNormalClosureFpGroup( B1, K );[127X[104X
    [4X[28X[ 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2 ][128X[104X
  [4X[32X[104X
  
  
  [1X47.16 [33X[0;0YTesting Finiteness of Finitely Presented Groups[133X[101X
  
  [33X[0;0YAs  a  consequence  of  the  algorithmic  insolvabilities  mentioned  in the
  introduction  to  this  chapter,  there cannot be a general method that will
  test whether a given finitely presented group is actually finite.[133X
  
  [33X[0;0YTherefore  testing  the  finiteness  of  a  finitely  presented group can be
  problematic.  What [5XGAP[105X actually does upon a call of [2XIsFinite[102X ([14X30.4-2[114X) (or if
  it is –probably implicitly– asked for a faithful permutation representation)
  is  to test whether it can find (via coset enumeration) a cyclic subgroup of
  finite  index.  If  it  can,  it rewrites the presentation to this subgroup.
  Since  the  subgroup  is  cyclic,  its  size  can be checked easily from the
  resulting  presentation,  the  size of the whole group is the product of the
  index  and the subgroup size. Since however no bound for the index of such a
  subgroup  (if any exist) is known, such a test might continue unsuccessfully
  until memory is exhausted.[133X
  
  [33X[0;0YOn  the other hand, a couple of methods exist, that might prove that a group
  is infinite. Again, none is guaranteed to work in every case:[133X
  
  [33X[0;0YThe  first  method  is  to  find  (for  example via the low index algorithm,
  see [2XLowIndexSubgroupsFpGroup[102X  ([14X47.10-1[114X))  a  subgroup  [22XU[122X such that [22X[U:U'][122X is
  infinite.    If   [22XU[122X   has   finite   index,   this   can   be   checked   by
  [2XIsInfiniteAbelianizationGroup[102X ([14X47.16-1[114X).[133X
  
  [33X[0;0YNote   that   this   test  has  been  done  traditionally  by  checking  the
  [2XAbelianInvariants[102X      ([14X39.16-1[114X)      (see      section [14X47.15[114X)     of     [22XU[122X,
  [2XIsInfiniteAbelianizationGroup[102X ([14X47.16-1[114X) does a similar calculation but stops
  as  soon  as  it  is  known  whether [22X0[122X is an invariant without computing the
  actual values. This can be notably faster.[133X
  
  [33X[0;0YAnother  method  is  based on [22Xp[122X-group quotients, see [2XNewmanInfinityCriterion[102X
  ([14X47.16-2[114X).[133X
  
  [1X47.16-1 IsInfiniteAbelianizationGroup[101X
  
  [33X[1;0Y[29X[2XIsInfiniteAbelianizationGroup[102X( [3XG[103X ) [32X property[133X
  
  [33X[0;0Yreturns  true if the commutator factor group [22X[3XG[103X/[3XG[103X'[122X is infinite. This might be
  done without computing the full structure of the commutator factor group.[133X
  
  [1X47.16-2 NewmanInfinityCriterion[101X
  
  [33X[1;0Y[29X[2XNewmanInfinityCriterion[102X( [3XG[103X, [3Xp[103X ) [32X function[133X
  
  [33X[0;0YLet  [3XG[103X be a finitely presented group and [3Xp[103X a prime that divides the order of
  the  commutator  factor  group  of  [3XG[103X.  This  function  applies  an infinity
  criterion  due  to M. F. Newman [New90] to [3XG[103X. (See [Joh97, chapter 16] for a
  more  explicit  description.)  It  returns [9Xtrue[109X if the criterion succeeds in
  proving that [3XG[103X is infinite and [9Xfail[109X otherwise.[133X
  
  [33X[0;0YNote  that  the criterion uses the number of generators and relations in the
  presentation  of [3XG[103X. Reduction of the presentation via Tietze transformations
  ([2XIsomorphismSimplifiedFpGroup[102X   ([14X47.12-1[114X))   therefore   might   produce  an
  isomorphic group, for which the criterion will work better.[133X
  
  [4X[32X  Example  [32X[104X
    [4X[25Xgap>[125X [27Xg:=FibonacciGroup(2,9);[127X[104X
    [4X[28X<fp group on the generators [ f1, f2, f3, f4, f5, f6, f7, f8, f9 ]>[128X[104X
    [4X[25Xgap>[125X [27Xhom:=EpimorphismNilpotentQuotient(g,2);;[127X[104X
    [4X[25Xgap>[125X [27Xk:=Kernel(hom);;[127X[104X
    [4X[25Xgap>[125X [27XIndex(g,k);[127X[104X
    [4X[28X152[128X[104X
    [4X[25Xgap>[125X [27XAbelianInvariants(k);[127X[104X
    [4X[28X[ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 ][128X[104X
    [4X[25Xgap>[125X [27XNewmanInfinityCriterion(Kernel(hom),5);[127X[104X
    [4X[28Xtrue[128X[104X
  [4X[32X[104X
  
  [33X[0;0YThis  proves  that  the subgroup [10Xk[110X (and thus the whole group [10Xg[110X) is infinite.
  (This is the original example from [New90].)[133X
  
