%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  fpgrp.tex                   GAP documentation            Martin Schoenert
%%
%A  @(#)$Id: fpgrp.tex,v 3.16.1.1 1994/08/04 09:49:30 vfelsch Rel $
%%
%Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
%%
%%  This file describes finitely presented groups and  their  implementation.
%%
%H  $Log: fpgrp.tex,v $
%H  Revision 3.16.1.1  1994/08/04  09:49:30  vfelsch
%H  updated AbelianInvariantsSubgroupFpGroup and PresentationSubgroup
%H
%H  Revision 3.16  1994/06/10  03:17:19  vfelsch
%H  updated examples
%H
%H  Revision 3.15  1994/06/08  15:16:14  vfelsch
%H  updated output of examples for Tietze transformations
%H
%H  Revision 3.14  1994/06/03  08:57:20  mschoene
%H  changed a few things to avoid LaTeX warnings
%H
%H  Revision 3.13  1994/05/30  14:51:40  vfelsch
%H  index entries rearranged
%H
%H  Revision 3.12  1994/05/18  13:32:36  vfelsch
%H  some doublequotes corrected
%H
%H  Revision 3.11  1994/04/06  12:53:27  fceller
%H  added 'IsIdenticalPresentationFpGroup'
%H
%H  Revision 3.10  1993/07/27  11:12:44  martin
%H  changed examples to '<free-group> / <relators>'
%H
%H  Revision 3.9  1993/07/23  08:47:49  felsch
%H  some minor improvements
%H
%H  Revision 3.8  1993/07/23  06:57:27  felsch
%H  added abelianized RRS and abelianized MTC
%H
%H  Revision 3.7  1993/05/05  15:15:54  fceller
%H  added 'CosetTableFpGroupDefaultMaxLimit'
%H
%H  Revision 3.6  1993/02/19  10:48:42  gap
%H  adjustments in line length and spelling
%H
%H  Revision 3.5  1993/02/12  11:59:20  felsch
%H  examples adjusted to line length 72
%H
%H  Revision 3.4  1993/02/11  17:46:09  martin
%H  changed '@' to '&'
%H
%H  Revision 3.3  1993/02/02  14:59:29  felsch
%H  examples fixed
%H
%H  Revision 3.2  1993/01/22  19:31:45  felsch
%H  added RRS, MTC, and Tietze
%H
%H  Revision 3.1  1992/04/06  17:06:14  martin
%H  initial revision under RCS
%H
%%
\Chapter{Finitely Presented Groups}

A *finitely presented  group* is a group generated by a set  of *abstract
generators*  subject  to  a  set  of  *relations* that  these  generators
satisfy.  Each group can be represented as finitely presented group.

A finitely  presented group is  constructed as follows.   First create an
appropriate   free group (see  "FreeGroup").    Then create the  finitely
presented group as a factor of this free group by the relators.

|    gap> F2 := FreeGroup( "a", "b" );
    Group( a, b )
    gap> A5 := F2 / [ F2.1^2, F2.2^3, (F2.1*F2.2)^5 ];
    Group( a, b )
    gap> Size( A5 );
    60
    gap> a := A5.1;;  b := A5.2;;
    gap> Index( A5, Subgroup( A5, [ a*b ] ) );
    12 |

Note  that,  even though  the  generators print  with  the names given to
'FreeGroup', no variables of that name are  defined.  That means that the
generators  must   be      entered    as  '<free-group>.<number>'     and
'<fp-group>.<number>'.

Note  that the  generators  of  the free   group  are different from  the
generators of the finitely presented  group (even though they print  with
the same name).    That means that  words  in the generators  of the free
group are not elements of the finitely presented group.

Note that the relations are entered as *relators*, i.e.,  as words in the
generators of  the free group.   To  enter an  equation  use the quotient
operator, i.e.,  for   the  relation  $a^b   = ab$  you have   to   enter
'a\^b/(a\*b)'.

You must *not* change the relators of a finitely presented group at all.

The  elements of  a  finitely presented  group are  words.  There  is one
fundamental  problem  with  this.  Different words  can correspond to the
same element in  a finitely presented  group.   For example in  the group
'A5'  defined  above,  'a'  and 'a\^3'  are  actually  the  same element.
However,  'a' is not equal to  'a\^3' (in the  sense  that 'a  = a\^3' is
'false').   This  leads  to the  following  anomaly{\:}  'a\^3 in  A5' is
'true',  but 'a\^3 in Elements(A5)' is  'false'.   *Some  set  and  group
functions  will not work correctly because of  this problem*.  You should
therefore only use the functions mentioned in "Set Functions for Finitely
Presented Groups" and "Group Functions for Finitely Presented Groups".

The first section in this chapter describes the function 'FreeGroup' that
creates a free group (see "FreeGroup").  The next sections describe which
set theoretic and group functions are implemented specially  for finitely
presented  groups  and  how they  work  (see "Set  Functions for Finitely
Presented Groups"  and  "Group Functions for Finitely Presented Groups").
The next section describes the basic function 'CosetTableFpGroup' that is
used  by  most   other  functions  for  finitely  presented  groups  (see
"CosetTableFpGroup").  The next section describes how  you can compute  a
permutation  group that is  a  homomorphic image of a finitely  presented
group (see  "OperationCosetsFpGroup").  The final section  describes  the
function that finds all subgroups of  a finitely presented group of small
index (see "LowIndexSubgroupsFpGroup").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{FreeGroup}

'FreeGroup( <n> )' \\
'FreeGroup( <n>, <string> )' \\
'FreeGroup( <name1>, <name2>.. )'

'FreeGroup' returns the free group on <n> generators.  The generators are
displayed   as   '<string>.1',  '<string>.2',  ...,  '<string>.<n>'.   If
<string> is missing it defaults to '\"f\"'.  If <string> is  the name  of
the variable that you use to refer to  the group  returned by 'FreeGroup'
you can also enter the generators as '<string>.<i>'.

|    gap> F2 := FreeGroup( 2, "A5" );;
    gap> A5 := F2 / [ F2.1^2, F2.2^3, (F2.1*F2.2)^5 ];
    Group( A5.1, A5.2 )
    gap> Size( A5 );
    60
    gap> F2 := FreeGroup( "a", "b" );;
    gap> D8 := F2 / [ F2.1^4, F2.2^2, F2.1^F2.2 / F2.1 ];
    Group( a, b )
    gap> a := D8.1;;  b := D8.2;;
    gap> Index( D8, Subgroup( D8, [ a ] ) );
    2 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Set Functions for Finitely Presented Groups}

Finitely  presented  groups  are  domains,  thus  in  principle  all  set
theoretic  functions  are applicable to  them  (see  chapter  "Domains").
However because words that are not equal may denote the same element of a
finitely presented group  many  of them will  not work  correctly.   This
sections  describes  which   set  theoretic  functions   are  implemented
specially for finitely presented  groups and  how they work.   You should
*not*  use the  set  theoretic functions  that are not mentioned  in this
section.

The  general  information that  enables {\GAP} to  work  with a  finitely
presented  group  <G>  is  a  *coset  table*  (see  "CosetTableFpGroup").
Basically 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 functions below use
the regular representation of <G>, i.e., the coset table  of <G> over the
trivial subgroup.  Such  a coset  table is computed  by a  method  called
*coset enumeration*.

\vspace{5mm}
'Size( <G> )'%
\index{Size!for finitely presented groups}

The size is simply the degree of the regular representation of <G>.

\vspace{5mm}
'<w> in <G>'%
\index{in!for finitely presented groups}

A word <w> lies  in a parent  group <G> if  all its letters are among the
generators of <G>.

\vspace{5mm}
'<w> in <H>'

To test whether a word <w> lies in a subgroup <H> of a finitely presented
group <G>, {\GAP}  computes the  coset table of <G> over  <H>.   Then  it
tests whether the permutation one gets by replacing each generator of <G>
in <w> with the corresponding permutation is trivial.

\vspace{5mm}
'Elements( <G> )'%
\index{Elements!for finitely presented groups}

The elements of a finitely presented  group are computed by computing the
regular representation of <G>.  Then for  each  point <p> {\GAP} adds the
smallest word <w> that, when viewed  as a permutation, takes  1 to <p> to
the set of elements.  Note that this implies  that each word in  the  set
returned is the smallest word that denotes an element of <G>.

\vspace{5mm}
'Elements( <H> )'

The elements  of  a  subgroup <H> of a  finitely presented group  <G> are
computed by computing the elements of <G> and returning those that lie in
<H>.

\vspace{5mm}
'Intersection( <H1>, <H2> )'%
\index{Intersection!for finitely presented groups}

The intersection of two subgroups <H1> and  <H2>  of a finitely presented
group <G> is computed as follows.  First {\GAP} computes the coset tables
of <G> over <H1> and <H2>.  Then it computes the tensor product  of those
two permutation representations.  The coset table of the  intersection is
the   transitive   constituent   of   1  in   this  tensored  permutation
representation.  Finally {\GAP} computes a set of Schreier generators for
the  intersection  by  performing  another coset  enumeration  using  the
already complete  coset  table.   The intersection  is  returned  as  the
subgroup generated by those Schreier generators.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Group Functions for Finitely Presented Groups}

Finitely presented groups  are after  all groups, thus  in  principle all
group functions are  applicable  to them (see chapter "Groups").  However
because  words  that are  not  equal  may denote  the same element  of  a
finitely presented group many of  them  will  not  work correctly.   This
sections describes which group  functions are implemented  specially  for
finitely  presented groups and how they  work.  You should *not* use  the
group functions that are not mentioned in this section.

The  general  information that  enables {\GAP} to  work  with a  finitely
presented  group  <G>  is  a  *coset  table*  (see  "CosetTableFpGroup").
Basically 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 functions below use
the regular representation of <G>, i.e., the coset table  of <G> over the
trivial subgroup.  Such  a coset  table is computed  by a  method  called
*coset enumeration*.

\vspace{5mm}
'Order( <G>, <g> )'%
\index{Order!for finitely presented groups}

The  order of an  element <g> is computed by translating the element into
the  regular  permutation representation and computing the order of  this
permutation (which is the length of the cycle of 1).

\vspace{5mm}
'Index( <G>, <H> )'%
\index{Index!for finitely presented groups}

The index of  a subgroup <H> in a  finitely presented group <G> is simply
the  degree of  the  permutation  representation of the group  <G> on the
cosets of <H>.

\vspace{5mm}
'Normalizer( <G>, <H> )'%
\index{Normalizer!for finitely presented groups}

The normalizer of a subgroup <H> of a finitely presented group <G> is the
union of those cosets of <H> in <G> that are fixed by all  the generators
of <H> when  viewed as permutations in  the permutation representation of
<G> on the  cosets  of <H>.   The normalizer is returned as the  subgroup
generated by the generators of <H> and representatives of such cosets.

\vspace{5mm}
'CommutatorFactorGroup( <G> )'%
\index{CommutatorFactorGroup!for finitely presented groups}

The commutator factor group of a finitely presented group <G> is returned
as a  new finitely presented group.  The relations of this group are  the
relations  of <G> plus  the  commutator of all the pairs of generators of
<G>.

\vspace{5mm}
'AbelianInvariants( <G> )'%
\index{AbelianInvariants!for finitely presented groups}

The abelian invariants  of  a  abelian finitely presented group  (e.g., a
commutator  factor group of an arbitrary  finitely presented  group)  are
computed by  building the relation matrix of  <G> and  transforming  this
matrix    to    diagonal   form    with   'ElementaryDivisorsMat'    (see
"ElementaryDivisorsMat").

\vspace{5mm}
'AbelianInvariantsSubgroupFpGroup( <G>, <H> )'%
\index{AbelianInvariantsSubgroupFpGroup} \\
'AbelianInvariantsSubgroupFpGroup( <G>, <cosettable> )'

This  function  is  equivalent  to  'AbelianInvariantsSubgroupFpGroupRrs'
below,    but   note  that      there is     an    alternative  function,
'AbelianInvariantsSubgroupFpGroupMtc'.

\vspace{5mm}
'AbelianInvariantsSubgroupFpGroupRrs( <G>, <H> )'%
\index{AbelianInvariantsSubgroupFpGroupRrs} \\
'AbelianInvariantsSubgroupFpGroupRrs( <G>, <cosettable> )'

'AbelianInvariantsSubgroupFpGroupRrs'  returns   the  invariants  of  the
commutator factor group <H/H\'> of a subgroup <H> of a finitely presented
group <G>.   They are computed by  first  applying an abelianized Reduced
Reidemeister-Schreier    procedure  (see   "Subgroup   Presentations") to
construct a relation matrix of <H/H\'> and  then transforming this matrix
to     diagonal        form    with       'ElementaryDivisorsMat'    (see
"ElementaryDivisorsMat").

As second argument, you may provide either the subgroup <H> itself or its
coset table in <G>.

\vspace{5mm}
'AbelianInvariantsSubgroupFpGroupMtc( <G>, <H> )'%
\index{AbelianInvariantsSubgroupFpGroupMtc}

'AbelianInvariantsSubgroupFpGroupMtc'  returns   the  invariants  of  the
commutator factor group <H/H\'> of a subgroup <H> of a finitely presented
group  <G>.   They are  computed    by applying  an  abelianized Modified
Todd-Coxeter procedure  (see   "Subgroup Presentations") to  construct  a
relation matrix of <H/H\'> and then  transforming this matrix to diagonal
form with 'ElementaryDivisorsMat' (see "ElementaryDivisorsMat").

\vspace{5mm}
'AbelianInvariantsNormalClosureFpGroup( <G>, <H> )'%
\index{AbelianInvariantsNormalClosureFpGroup}

This function is equivalent to 'AbelianInvariantsNormalClosureFpGroupRrs'
below.

\vspace{5mm}
'AbelianInvariantsNormalClosureFpGroupRrs( <G>, <H> )'%
\index{AbelianInvariantsNormalClosureFpGroupRrs}

'AbelianInvariantsNormalClosureFpGroupRrs' returns  the invariants of the
commutator factor group <N/N\'> of the normal closure  <N> a subgroup <H>
of a finitely  presented group <G>.  They are  computed by first applying
an  abelianized  Reduced Reidemeister-Schreier  procedure  (see "Subgroup
Presentations")  to  construct a  relation  matrix  of  <N/N\'>  and then
transforming  this matrix  to  diagonal form with 'ElementaryDivisorsMat'
(see "ElementaryDivisorsMat").

|    gap> & Define the Coxeter group E1.
    gap> F5 := FreeGroup( "x1", "x2", "x3", "x4", "x5" );;
    gap> E1 := F5 / [ F5.1^2, F5.2^2, F5.3^2, F5.4^2, F5.5^2,
    >  ( F5.1 * F5.3 )^2, ( F5.2 * F5.4 )^2, ( F5.1 * F5.2 )^3,
    >  ( F5.2 * F5.3 )^3, ( F5.3 * F5.4 )^3, ( F5.4 * F5.1 )^3,
    >  ( F5.1 * F5.5 )^3, ( F5.2 * F5.5 )^2, ( F5.3 * F5.5 )^3,
    >  ( F5.4 * F5.5 )^2,
    >  ( F5.1 * F5.2 * F5.3 * F5.4 * F5.3 * F5.2 )^2 ];;
    gap> x1:=E1.1;;  x2:=E1.2;;  x3:=E1.3;;  x4:=E1.4;;  x5:=E1.5;;
    gap> & Get normal subgroup generators for B1.
    gap> H := Subgroup( E1, [ x5 * x2^-1, x5 * x4^-1 ] );;
    gap> & Compute the abelian invariants of B1/B1'.
    gap> A := AbelianInvariantsNormalClosureFpGroup( E1, H );
    [ 2, 2, 2, 2, 2, 2, 2, 2 ]
    gap> & Compute a presentation for B1.
    gap> P := PresentationNormalClosure( E1, H );
    << presentation with 18 gens and 46 rels of total length 132 >>
    gap> SimplifyPresentation( P );
    &I  there are 8 generators and 30 relators of total length 148
    gap> B1 := FpGroupPresentation( P );
    Group( _x1, _x2, _x3, _x4, _x6, _x7, _x8, _x11 )
    gap> & Compute normal subgroup generators for B1'.
    gap> gens := B1.generators;;
    gap> numgens := Length( gens );;
    gap> comms := [ ];;
    gap> for i in [ 1 .. numgens - 1 ] do
    >        for j in [i+1 .. numgens ] do
    >            Add( comms, Comm( gens[i], gens[j] ) );
    >        od;
    >    od;
    gap> & Compute the abelian invariants of B1'/B1".
    gap> K := Subgroup( B1, comms );;
    gap> A := AbelianInvariantsNormalClosureFpGroup( B1, K );
    [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0 ] |

The prededing calculation for $B_1$ and a similar one for $B_0$ have been
used  to prove that $B_1^\prime /  B_1^{\prime \prime} \cong Z_2^9 \times
Z^3$ and $B_0^\prime / B_0^{\prime  \prime} \cong Z_2^{91} \times Z^{27}$
as stated in Proposition 5 in \cite{FJNT93}.

The following  functions  are  not  implemented  specially  for  finitely
presented groups,  but  they work  nevertheless.   However,  you probably
should not use them for larger finitely presented groups.

'Core( <G>, <U> )' \\
'SylowSubgroup( <G>, <p> )' \\
'FittingSubgroup( <G> )'

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{CosetTableFpGroup}

'CosetTableFpGroup( <G>, <H> )'

'CosetTableFpGroup' returns the  coset  table of the  finitely  presented
group <G> on the cosets of the subgroup <H>.

Basically 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 <G>, i.e.,  the  coset
table of <G> over the trivial subgroup.

The coset table is  returned as a list of  lists.   For each generator of
<G> and  its inverse the table  contains  a generator list.   A generator
list is simply a list of integers.  If <l> is the  generator list for the
generator <g> and '<l>[<i>] = <j>' then generator <g> takes the coset <i>
to the coset <j> by multiplication from the  right.  Thus the permutation
representation of  <G>  on  the  cosets of <H>  is  obtained by  applying
'PermList' to each  generator list (see "PermList").   The coset table is
standardized,  i.e., the cosets are  sorted with  respect to the smallest
word that lies in each coset.

|    gap> F2 := FreeGroup( "a", "b" );
    Group( a, b )
    gap> A5 := F2 / [ F2.1^2, F2.2^3, (F2.1*F2.2)^5 ];
    Group( a, b )
    gap> CosetTableFpGroup( A5,
    >            Subgroup( A5, [ A5.1, A5.2*A5.1*A5.2*A5.1*A5.2^-1 ] ) );
    [ [ 1, 3, 2, 5, 4 ],
      [ 1, 3, 2, 5, 4 ],    # inverse of above, 'A5.1' is an involution
      [ 2, 4, 3, 1, 5 ],
      [ 4, 1, 3, 2, 5 ] ]   # inverse of above
    gap> List( last, PermList );
    [ (2,3)(4,5), (2,3)(4,5), (1,2,4), (1,4,2) ] |

The coset  table is  computed by a method called *coset enumeration*.   A
*Felsch strategy* is used to decide how to define new cosets.

The  variable  'CosetTableFpGroupDefaultLimit'  determines  for  how many
cosets   the  table  has   initially   room.   'CosetTableFpGroup'   will
automatically  extend this table if need arises, but this is an expensive
operation.  Thus  you  should  set 'CosetTableFpGroupDefaultLimit' to the
number of cosets that  you expect will be  needed at most.   However  you
should not set it too  high, otherwise too much space will be used by the
coset table.

The  variable  'CosetTableFpGroupDefaultMaxLimit' determines the  maximal
size of  the coset  table.  If a coset enumeration reaches  this limit it
signals an error  and enters the breakloop.  You  can  either continue or
quit  the computation  from  there.   Setting  the  limit to  '0'  allows
arbitrary large coset tables.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{OperationCosetsFpGroup}

'OperationCosetsFpGroup( <G>, <H> )'

'OperationCosetsFpGroup'  returns the  permutation  representation of the
finitely  presented group <G>  on  the  cosets of  the subgroup  <H> as a
permutation group.  Note that this permutation representation is faithful
if and only if <H> has a trivial core in <G>.

|    gap> F2 := FreeGroup( "a", "b" );
    Group( a, b )
    gap> A5 := F2 / [ F2.1^2, F2.2^3, (F2.1*F2.2)^5 ];
    Group( a, b )
    gap> OperationCosetsFpGroup( A5,
    >            Subgroup( A5, [ A5.1, A5.2*A5.1*A5.2*A5.1*A5.2^-1 ] ) );
    Group( (2,3)(4,5), (1,2,4) )
    gap> Size( last );
    60 |

'OperationCosetsFpGroup'   simply  calls   'CosetTableFpGroup',   applies
'PermList' to each  row  of the table, and returns the group generated by
those permutations (see "CosetTableFpGroup", "PermList").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{IsIdenticalPresentationFpGroup}

'IsIdenticalPresentationFpGroup( <G>, <H> )'

'IsIdenticalPresentationFpGroup'  returns 'true'  if the presentations of 
the parent groups <G> and <H> are identical and 'false' otherwise.

Two presentations are considered identical if the have the same number of
generators,  i.e.,  <G> is generated by <g1> ... <gn> and <H> by <h1> ...
<hn>, and if the set of relators of <G> stored in '<G>.relators' is equal
to the set of relators of <H> stored in '<H>.relators' *after*  replacing
<hi> by <gi> in these words.

|    gap> F2 := FreeGroup(2);
    Group( f.1, f.2 )
    gap> g := F2 / [ F2.1^2 / F2.2 ];   
    Group( f.1, f.2 )
    gap> h := F2 / [ F2.1^2 / F2.2 ];
    Group( f.1, f.2 )
    gap> g = h;
    false
    gap> IsIdenticalPresentationFpGroup( g, h );
    true |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{LowIndexSubgroupsFpGroup}

'LowIndexSubgroupsFpGroup( <G>, <H>, <index> )'

'LowIndexSubgroupsFpGroup'  returns a  list  of  representatives  of  the
conjugacy classes of  subgroups of the finitely presented  group <G> that
contain the subgroup <H> of <H> and that have index less than or equal to
<index>.

|    gap> F2 := FreeGroup( "a", "b" );
    Group( a, b )
    gap> A5 := F2 / [ F2.1^2, F2.2^3, (F2.1*F2.2)^5 ];
    Group( a, b )
    gap> A5.name := "A5";;
    gap> S := LowIndexSubgroupsFpGroup( A5, TrivialSubgroup( A5 ), 12 );
    [ A5, Subgroup( A5, [ a, b*a*b^-1 ] ), 
      Subgroup( A5, [ a, b*a*b*a^-1*b^-1 ] ), 
      Subgroup( A5, [ a, b*a*b*a*b^-1*a^-1*b^-1 ] ),
      Subgroup( A5, [ b*a^-1 ] ) ]
    gap> List( S, H -> Index( A5, H ) );
    [ 1, 6, 5, 10, 12 ]    # the indices of the subgroups
    gap> List( S, H -> Index( A5, Normalizer( A5, H ) ) );
    [ 1, 6, 5, 10, 6 ]    # the lengths of the conjugacy classes |

'LowIndexSubgroupsFpGroup'  systematically  constructs  all   permutation
representations of <G>.  How large you  can choose <index> depends on the
presentation  of  <G>,  but  you  should  be  careful.   Usually the time
required grows exponentially with <index>.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Presentation Records}%

In  {\GAP}, *finitely presented  groups*  are  distinguished  from *group
presentations* which are {\GAP} objects of their own and which are stored
in *presentation  records*.  The reason  is that very often presentations
have to be changed (e.g. simplified) by Tietze transformations, but since
in  these new  generators  and relators are introduced, all  words in the
generators of a finitely presented group would also have to be changed if
such  a  Tietze  transformation  were  applied to  the presentation of  a
finitely presented group.  Therefore, in {\GAP} the presentation defining
a finitely presented group is never changed; changes are only allowed for
group presentations  which  are  not  considered  to  define a particular
group.

{\GAP}  offers a bundle of commands to perform  Tietze transformations on
finite   group    presentations    (see    "SimplifiedFpGroup",   "Tietze
Transformations").  In  order  to speed  up the respective routines,  the
relators in such a presentation record are  not represented  by  ordinary
{\GAP} words, but by lists of positive or negative generator numbers.

The term ``*Tietze  record*\'\'\  will  sometimes be used as an alias for
``*presentation record*\'\'.  It occurs, in particular, in certain  error
messages.  \index{Tietze record}

The following  two  commands can be used to create a presentation  record
from a  finitely presented group  or, vice  versa, to  create a  finitely
presented group from a presentation.

\vspace{5mm}
'PresentationFpGroup( <G> )'%
\index{PresentationFpGroup} \\
'PresentationFpGroup( <G>, <printlevel> )'

'PresentationFpGroup' returns a presentation record containing a copy  of
the  presentation of the given finitely presented group  <G> on the  same
set of generators.

The  optional <printlevel> parameter can be used to restrict or to extend
the amount  of  output provided by  Tietze  transformation  commands when
being applied to the created presentation record.  The default value 1 is
designed  for  interactive  use  and  implies  explicit  messages  to  be
displayed  by most of  these  commands.   A <printlevel> value of  0 will
suppress these messages, whereas a <printlevel>  value of 2  will enforce
some additional output.

\vspace{5mm}
'FpGroupPresentation( <P> )'%
\index{FpGroupPresentation}

'FpGroupPresentation' returns a  finitely presented group defined  by the
presentation in the given presentation record <P>.

If some presentation record <P>, say, contains a large presentation, then
it  would  be nasty  to  wait for  the end of an  unintentionally started
printout of all of its components (or, more precisely, of  its  component
'<P>.tietze' which contains  the essential lists).   Therefore,  whenever
you use the standard print  facilities  to display a presentation record,
{\GAP}  will  provide just  one line of text  containing  the  number  of
generators, the number of relators, and the total length of all relators.
Of course, you may use the 'RecFields' and 'PrintRec' commands to display
all components of <P>.

In  addition, you may  use  the  following commands to extract and  print
different amounts of information from a presentation record.

\vspace{5mm}
'TzPrintStatus( <P> )'%
\index{TzPrintStatus}

'TzPrintStatus'  prints the current  state of a presentation record  <P>,
i.e., the number of generators,  the  number of relators, and  the  total
length of all relators.

If  you are working  interactively,  you can get the same  information by
just typing '<P>;'

\vspace{5mm}
'TzPrintGenerators( <P> )'%
\index{TzPrintGenerators} \\
'TzPrintGenerators( <P>, <list> )'

'TzPrintGenerators'   prints  the  current  list  of   generators  of   a
presentation record <P>, providing for each generator its name, the total
number of its  occurrences in the relators,  and,  if  that generator  is
known to be an involution, an appropriate message.

If a  list  <list> has  been  specified as  second argument,  then  it is
expected to be  a list of the position  numbers  of  the generators to be
printed.  <list> need not be sorted and  may  contain duplicate elements.
The generators are printed in  the order in which and  as often as  their
numbers occur in <list>.  Position  numbers out of range (with respect to
the list of generators) will be ignored.

\vspace{5mm}
'TzPrintRelators( <P> )'%
\index{TzPrintRelators} \\
'TzPrintRelators( <P>, <list> )'

'TzPrintRelators' prints the current list of relators  of  a presentation
record <P>.

If  a  list  <list>  has been specified  as  second argument, then it  is
expected  to  be a list  of the position numbers  of the  relators  to be
printed.  <list> need  not be sorted  and may contain duplicate elements.
The relators are printed in  the order  in  which  and as often  as their
numbers occur in <list>.  Position numbers out of range  (with respect to
the list of relators) will be ignored.

\vspace{5mm}
'TzPrintPresentation( <P> )'%
\index{TzPrintPresentation}

'TzPrintPresentation' prints the current lists of generators and relators
and the current state of a presentation record <P>.  In fact, the command

|    TzPrintPresentation( P ) |

is an abbreviation of the command sequence

|    Print( "generators:\n" ); TzPrintGenerators( P );
    Print( "relators:\n" ); TzPrintRelators( P );
    TzPrintStatus( P ); |

\vspace{5mm}
'TzPrint( <P> )'%
\index{TzPrint} \\
'TzPrint( <P>, <list> )'

'TzPrint' provides a  kind of  *fast print out* for a presentation record
<P>.

Remember that  in order to  speed up  the Tietze transformation routines,
each relator in a presentation record  <P> is internally represented by a
list of positive or negative generator  numbers, i.e., each factor of the
proper  {\GAP}  word  is  represented  by  the  position  number  of  the
corresponding  generator with respect to the current list of  generators,
or by the respective negative  number, if  the factor is the inverse of a
generator which  is not known to be an involution.   In  contrast  to the
commands  'TzPrintRelators'  and  'TzPrintPresentation'  described above,
'TzPrint' does not  convert these lists back to the corresponding  {\GAP}
words.

'TzPrint' prints the  current  list  of  generators,  and  then  for each
relator its length and its internal representation as a list  of positive
or negative generator numbers.

If  a  list  <list> has been specified  as  second  argument, then it  is
expected to  be a list of  the position  numbers of the  relators  to  be
printed.  <list> need not be sorted  and may contain  duplicate elements.
The relators are printed  in the order  in which and  as  often  as their
numbers occur in <list>.  Position numbers out  of range (with respect to
the list of relators) will be ignored.

There are  three more  print commands for presentation records  which are
convenient  in  the  context  of  the interactive  Tietze  transformation
commands\:

\vspace{5mm}
'TzPrintLengths( <P> )'

See "Tietze Transformations".

\vspace{5mm}
'TzPrintPairs( <P> )' \\
'TzPrintPairs( <P>, <n> )'

See "Tietze Transformations".

\vspace{5mm}
'TzPrintOptions( <P> )'

See "Tietze Transformations".

\vspace{5mm}
'Save( <file>, <P>, <name> )'%
\index{Save!for presentation records}

'Save' writes the  presentation  record  <P> to the file <file> in such a
way that the file can be read by {\GAP}.  This allows you, in particular,
to restart a computation with  the current  presentation not only in  the
present, but also  in a later  {\GAP} session.  Then, when you  read  the
file, a copy of <P> will be  assigned to  the variable  specified by  the
argument <name> in the current call of the 'Save' command.

Example.

|    gap> F2 := FreeGroup( "a", "b" );;
    gap> G := F2 / [ F2.1^2, F2.2^7, Comm(F2.1,F2.1^F2.2),
    >                Comm(F2.1,F2.1^(F2.2^2))*(F2.1^F2.2)^-1 ];
    Group( a, b )
    gap> a := G.1;; b := G.2;;
    gap> P := PresentationFpGroup( G );
    << presentation with 2 gens and 4 rels of total length 30 >>
    gap> TzPrintGenerators( P );
    &I  1.  a   11 occurrences   involution
    &I  2.  b   19 occurrences
    gap> TzPrintRelators( P );
    &I  1. a^2
    &I  2. b^7
    &I  3. a*b^-1*a*b*a*b^-1*a*b
    &I  4. a*b^-2*a*b^2*a*b^-2*a*b*a*b
    gap> TzPrint( P );
    &I  generators: [ a, b ]
    &I  relators:
    &I  1.  2  [ 1, 1 ]
    &I  2.  7  [ 2, 2, 2, 2, 2, 2, 2 ]
    &I  3.  8  [ 1, -2, 1, 2, 1, -2, 1, 2 ]
    &I  4.  13  [ 1, -2, -2, 1, 2, 2, 1, -2, -2, 1, 2, 1, 2 ]
    gap> TzPrintStatus( P );
    &I  there are 2 generators and 4 relators of total length 30
    gap> Save( "checkpoint", P, "P0" );
    gap> Read( "checkpoint" );
    &I  presentation record P0 read from file
    gap> P0;
    << presentation with 2 gens and 4 rels of total length 30 >> |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Changing Presentations}%

The  commands  described  in  this section  can be  used  to  change  the
presentation in a presentation record.   Note that, in general, they will
change the  isomorphism  type  of the  group defined by the presentation.
Hence,  though they  sometimes  are  called  as  subroutines  by Tiet\-ze
transformation     commands    like    'TzSubstitute'    (see     "Tietze
Transformations"),   they   do  *not*   perform   Tietze  transformations
themselves.

\vspace{5mm}
'AddGenerator( <P> )'%
\index{AddGenerator} \\
'AddGenerator( <P>, <generator> )'

'AddGenerator' adds a new generator to the list of generators.

If you don\'t specify a second argument, then  'AddGenerator' will define
a  new  abstract  generator  '\_x<i>'  and save  it  in a  new  component
'<P>.<i>' of  the  given  presentation  record  where  <i>  is the  least
positive  integer which  has  not  yet  been used as a  generator number.
Though this  new generator will be printed as '\_x<i>',  you will have to
use the external variable '<P>.<i>' if you want to access it.

If you  specify a second  argument, then <generator> must be  an abstract
generator which does  not yet occur in the presentation.   'AddGenerator'
will add it to the presentation and save  it in a new component '<P>.<i>'
in the same way as described for \_x<i> above.

\vspace{5mm}
'AddRelator( <P>, <word> )'%
\index{AddRelator}

'AddRelator' adds  the word <word> to the list of  relators.  <word> must
be a word in the generators of the given presentation.

\vspace{5mm}
'RemoveRelator( <P>, <n> )'%
\index{RemoveRelator}

'RemoveRelator'  removes the <n>th relator and  then resorts the  list of
relators in the given presentation record <P>.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Subgroup Presentations}

'PresentationSubgroupRrs( <G>, <H> )'%
\index{PresentationSubgroupRrs} \\
'PresentationSubgroupRrs( <G>, <H>, <string> )' \\
'PresentationSubgroupRrs( <G>, <cosettable> )' \\
'PresentationSubgroupRrs( <G>, <cosettable>, <string> )'

'PresentationSubgroupRrs'    returns   a    presentation   record    (see
"Presentation Records") containing a presentation for the subgroup <H> of
the    finitely   presented   group   <G>.    It   uses    the    Reduced
Reidemeister-Schreier method to construct this presentation.%
\index{Reduced Reidemeister-Schreier}

As second argument, you may provide either the subgroup <H> itself or its
coset table in <G>.

The   generators  in  the  resulting  presentation  will   be   named  by
'<string>1', '<string>2', ..., the default string is '\"\_x\"'.

The Reduced  Reidemeister-Schreier algorithm is  a  modification  of  the
Reidemeister-Schreier algorithm of George  Havas  \cite{Hav74b}.   It was
proposed by Joachim Neub{\accent127u}ser and first implemented in 1986 by
Andrea Lucchini and Volkmar Felsch in the SPAS system \cite{Spa89}.  Like
George  Havas{\'}  Reidemeister-Schreier  algorithm,  it  needs only  the
presentation of  <G> and a  coset table  of  <H>  in <G>  to construct  a
presentation of <H>.

Whenever you call  the 'PresentationSubgroupRrs' command, it checks first
whether a  coset table  of <H> in <G> has already been computed and saved
in the subgroup  record of <H> by a  preceding call  of some  appropriate
command like 'CosetTableFpGroup'  (see "CosetTableFpGroup"), 'Index' (see
"Index"), or 'LowIndexSubgroupsFpGroup' (see "LowIndexSubgroupsFpGroup").
Only  if the  coset table is not yet available, is  it now constructed by
'PresentationSubgroupRrs'  which   calls  'CosetTableFpGroup'  for   this
purpose.  In  this  case,  of  course, a set  of  generators  of  <H>  is
required, but they will not be used any more in the subsequent steps.

Next,  a  set of generators of <H> is  determined  by  reconstructing the
coset table and introducing in  that process as many  Schreier generators
of <H> in  <G> as are needed  to do a  Felsch  strategy coset enumeration
without  any  coincidences.  (In  general,  though  containing  redundant
generators,  this set will be  much smaller  than the set of all Schreier
generators.   That\'s   why   we   call    the   method   the   *Reduced*
Reidemeister-Schreier.)

After having constructed this set of *primary subgroup generators* , say,
the coset table is extended to an *augmented coset table* which describes
the  action of the  group generators  on  coset representatives, i.e., on
elements  instead of cosets.  For  this purpose,  suitable words  in  the
(primary) subgroup generators have to  be associated  to  the coset table
entries.  In order to keep the lengths of these words short, additional
*secondary  subgroup  generators*  are  introduced  as  abbreviations  of
subwords. Their number may be large.%
\index{primary subgroup generators}%
\index{secondary subgroup generators}%
\index{augmented coset table}

Finally, a  Reidemeister  rewriting  process  is  used  to  get  defining
relators for <H> from the relators of <G>.  As the resulting presentation
of  <H>  is  a  presentation on  primary *and*  secondary generators,  in
general   you  will   have   to   simplify   it   by  appropriate  Tietze
transformations  (see  "Tietze  Transformations") or  by the 'DecodeTree'
command  (see  "DecodeTree") before  you can use  it.   Therefore  it  is
returned in the form of a presentation record.

Compared  with  the  Modified  Todd-Coxeter method described  below,  the
Reduced Rei\-de\-mei\-ster-Schreier method (as well as Havas{\'} original
Reidemeister-Schreier program) has the advantage that it does not require
generators of <H>  to be given if  a coset table of <H> in  <G> is known.
This  provides  a  possibility to compute  a  presentation  of the normal
closure  of a  given  subgroup  (see  the  'PresentationNormalClosureRrs'
command below).

A few examples are given in section "Tietze Transformations".

\vspace{5mm}
'PresentationSubgroupMtc( <G>, <H> )'%
\index{PresentationSubgroupMtc} \\
'PresentationSubgroupMtc( <G>, <H>, <string> )' \\
'PresentationSubgroupMtc( <G>, <H>, <printlevel> )' \\
'PresentationSubgroupMtc( <G>, <H>, <string>, <printlevel> )'

'PresentationSubgroupMtc'    returns    a   presentation   record    (see
"Presentation Records") containing a presentation for the subgroup <H> of
the  finitely  presented  group  <G>.  It  uses a  Modified  Todd-Coxeter
method to construct this presentation.%
\index{Modified Todd-Coxeter}

The  generators  in   the   resulting  presentation  will  be  named   by
'<string>1', '<string>2', ..., the default string is '\"\_x\"'.

The optional <printlevel> parameter can be used to restrict  or to extend
the amount of  output provided by the 'PresentationSubgroupMtc'  command.
In particular, by specifying the <printlevel> parameter to be  0, you can
suppress the output of  the 'DecodeTree' command which is called  by  the
'PresentationSubgroupMtc'  command (see  below).  The  default  value  of
<printlevel> is 1.

The  so  called  Modified  Todd-Coxeter  method was proposed, in slightly
different forms, by Nathan S.~Mendelsohn and William O.~J.~Moser in 1966.
Moser\'s  method  was proved by  Michael J.~Beetham and Colin M.~Campbell
(see \cite{BC76}).  Another  proof  for a  special version  was  given by
D.~H.~McLain (see  \cite{McL77}).  It  was generalized  to cover  a broad
spectrum  of different versions (see the  survey \cite{Neu82}).  Moser\'s
method was implemented by Harvey A.~Campbell (see \cite{Cam71}.  Later, a
Modified Todd-Coxeter program was  implemented in  St.~Andrews  by  David
G.~Arrell, Sanjiv Manrai, and Michael  F.~Worboys (see \cite{AMW82})  and
further  developed   by  David  G.~Arrel  and  Edmund  F.~Robertson  (see
\cite{AR84}) and by Volkmar Felsch in the SPAS system \cite{Spa89}.

The  'Modified Todd-Coxeter'  method  performs  an enumeration  of  coset
representatives.   It  proceeds like an  ordinary  coset enumeration (see
'CosetTableFpGroup' "CosetTableFpGroup"), but as  the product of  a coset
representative by  a group  generator or its inverse need not be a  coset
representative itself, the Modified Todd-Coxeter has to store a  kind  of
correction element for each coset table entry.   Hence it builds  up a so
called *augmented coset table* of <H>  in <G> consisting  of the ordinary
coset table and a second  table in parallel which contains the associated
subgroup elements.%
\index{augmented coset table}

Theoretically, these subgroup elements could be expressed as words in the
given generators of   <H>, but in    general these words tend   to become
unmanageable  because of their   enormous lengths.   Therefore,  a highly
redundant list of subgroup generators is built up starting from the given
(``*primary*\'\')  generators     of    <H>   and     adding   additional
(``*secondary*\'\')  generators which  are  defined as   abbreviations of
suitable words of length  two in the  preceding generators such that each
of the subgroup elements in the augmented coset table can be expressed as
a word of length at most  one in the  resulting (primary *and* secondary)
subgroup generators.%
\index{primary subgroup generators}%
\index{secondary subgroup generators}

Then  a  rewriting  process (which is essentially a kind of  Reidemeister
rewriting process) is used to  get  relators  for  <H>  from the defining
relators of <G>.

The resulting presentation involves  all  the  primary, but not  all  the
secondary generators of <H>.   In fact, it contains only those  secondary
generators which  explicitly occur in the augmented  coset table.  If  we
extended this presentation by those  secondary generators which  are  not
yet contained in it as additional generators,  and by the  definitions of
all  secondary   generators  as  additional  relators,  we  would  get  a
presentation of <H>, but, in general, we would end up with a large number
of generators and relators.

On the other hand, if  we  avoid this extension, the current presentation
will not necessarily define <H> although  we have used the same rewriting
process  which  in  the  case of  the  'SubgroupPresentationRrs'  command
computes a defining set of relators for <H> from an augmented coset table
and defining relators  of <G>.  The different behaviour here is caused by
the fact that coincidences may have occurred in the Modified Todd-Coxeter
coset enumeration.

To  overcome  this problem  without  extending  the presentation  by  all
secondary generators, the  'SubgroupPresentationMtc' command  applies the
so called  *tree decoding*  algorithm  which provides  a  more economical
approach.   The reader is  strongly recommended to carefully read section
"DecodeTree"  where this algorithm is  described in more detail.  Here we
will  only  mention  that  this  procedure  adds  many  fewer  additional
generators  and relators  in a  process  which  in  fact  eliminates  all
secondary generators from  the presentation and hence finally  provides a
presentation  of  <H>  on  the  primary,  i.e.,  the   originally  given,
generators   of  <H>.   This   is   a   remarkable   advantage   of   the
'SubgroupPresentationMtc'       command       compared       to       the
'SubgroupPresentationRrs'  command.   But note that, for  some particular
subgroup <H>, the  Reduced Reidemeister-Schreier method might quite  well
produce a more concise presentation.

The  resulting  presentation  is  returned in  the form of a presentation
record.  Though  the  tree  decoding  routine already involves a  lot  of
Tietze transformations, we recommend that you try to further simplify the
presentation   by   appropriate  Tietze   transformations  (see   "Tietze
Transformations").

An example is given in section "DecodeTree".

\vspace{5mm}
'PresentationSubgroup( <G>, <H> )'%
\index{PresentationSubgroup} \\
'PresentationSubgroup( <G>, <H>, <string> )' \\
'PresentationSubgroup( <G>, <cosettable> )' \\
'PresentationSubgroup( <G>, <cosettable>, <string> )'

'PresentationSubgroup' returns a presentation record  (see  "Presentation
Records") containing a presentation for the subgroup  <H> of the finitely
presented group <G>.

As second argument, you may provide either the subgroup <H> itself or its
coset table in <G>.

In  the case   of providing  the  subgroup  <H>  itself as  argument, the
current   {\GAP}  implementation offers a  choice   between two different
methods for  constructing   subgroup presentations,  namely   the Reduced
Reidemeister-Schreier and  the Modified  Todd-Coxeter procedure.  You can
specify either of  them by calling the commands 'PresentationSubgroupRrs'
or 'PresentationSubgroupMtc', respectively.  Further methods may be added
in a later {\GAP} version.  If, in  some concrete application, you don\'t
care  for   the    method   to    be selected,     you    may use     the
'PresentationSubgroup'  command  as a kind  of default  command.   In the
present installation,   it  will call  the  Reduced Reidemeister-Schreier
method, i.e., it is identical with the 'PresentationSubgroupRrs' command.

A few examples are given in section "Tietze Transformations".

\vspace{5mm}
'PresentationNormalClosureRrs( <G>, <H> )'%
\index{PresentationNormalClosureRrs} \\
'PresentationNormalClosureRrs( <G>, <H>, <string> )'

'PresentationNormalClosureRrs'   returns  a  presentation   record   (see
"Presentation Records") containing a presentation for the normal  closure
of  the  subgroup <H> of the finitely presented group  <G>.  It  uses the
Reduced Reidemeister-Schreier  method  to  construct  this  presentation.
This  provides a possibility  to  compute  a presentation  for  a  normal
subgroup  for  which  only  ``normal  subgroup  generators\'\',  but  not
necessarily a full set of generators are known.

The   generators  in   the  resulting   presentation  will  be  named  by
'<string>1', '<string>2', ..., the default string is '\"\_x\"'.

'PresentationNormalClosureRrs'  first  establishes an  intermediate group
record for the factor group of <G> by the normal closure <N>, say, of <H>
in <G>.  Then it performs a coset enumeration of  the trivial subgroup in
that factor group.  The resulting coset table  can be considered as coset
table  of  <N> in <G>, hence  a presentation for <N> can  be  constructed
using the  Reduced  Reidemeister-Schreier algorithm as  described for the
'PresentationSubgroupRrs' command.

\vspace{5mm}
'PresentationNormalClosure( <G>, <H> )'%
\index{PresentationNormalClosure} \\
'PresentationNormalClosure( <G>, <H>, <string> )'

'PresentationNormalClosure'   returns    a   presentation   record   (see
"Presentation Records") containing a presentation for the  normal closure
of the subgroup <H> of the finitely presented group <G>.  This provides a
possibility  to  compute  a presentation for a normal subgroup for  which
only ``normal  subgroup generators\'\', but not necessarily a full set of
generators are known.

If,  in  a  later  release,  {\GAP}  offers  different  methods  for  the
construction      of     normal     closure      presentations,      then
'PresentationNormalClosure' will call one of these  procedures as a  kind
of    default    method.     At    present,    however,    the    Reduced
Reidemeister-Schreier  algorithm  is  the only  one implemented  so  far.
Therefore,  at   present   the  'PresentationNormalClosure'   command  is
identical  with  the   'PresentationNormalClosureRrs'  command  described
above.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{SimplifiedFpGroup}

'SimplifiedFpGroup( <G> )'

'SimplifiedFpGroup'  applies  Tietze  transformations  to a  copy of  the
presentation of the given finitely presented group <G> in order to reduce
it with respect to  the number of generators, the number of relators, and
the relator lengths.

'SimplifiedFpGroup' returns the resulting finitely presented group (which
is isomorphic to <G>).

|    gap> F6 := FreeGroup( 6, "G" );;
    gap> G := F6 / [ F6.1^2, F6.2^2, F6.4*F6.6^-1, F6.5^2, F6.6^2,
    >         F6.1*F6.2^-1*F6.3, F6.1*F6.5*F6.3^-1, F6.2*F6.4^-1*F6.3,
    >         F6.3*F6.4*F6.5^-1, F6.1*F6.6*F6.3^-2, F6.3^4 ];;
    gap> H := SimplifiedFpGroup( G );
    Group( G.1, G.3 )
    gap> H.relators;
    [ G.1^2, G.1*G.3^-1*G.1*G.3^-1, G.3^4 ] |

In fact, the command

|    H := SimplifiedFpGroup( G ); |

is an abbreviation of the command sequence

|    P := PresentationFpGroup( G, 0 );;
    SimplifyPresentation( P );
    H := FpGroupPresentation( P ); |

which applies  a rather simple-minded strategy of  Tietze transformations
to the intermediate presentation record <P> (see "Presentation Records").
If for  some  concrete group the resulting presentation  is unsatisfying,
then  you  should  try  a  more  sophisticated,  interactive  use of  the
available Tietze transformation commands (see "Tietze Transformations").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Tietze Transformations}%

The {\GAP} commands being described in this section can be used to modify
a group presentation in a presentation record by Tietze transformations.

In general, the aim of such modifications will be to *simplify* the given
presentation, i.e., to reduce the number of generators and the number  of
relators without increasing too much the sum of all relator lengths which
we  will  call the *total length* of the  presentation.  Depending on the
concrete  presentation under  investigation  one may end up  with a nice,
short presentation or with a very huge one.%
\index{total length of a presentation}

Unfortunately there  is  no algorithm which could be  applied to find the
shortest presentation which  can  be  obtained  by Tietze transformations
from a  given one.  Therefore, what  {\GAP}  offers  are some lower-level
Tietze  transformation  commands  and,  in  addition,  some  higher-level
commands which apply the lower-level ones in  a kind of  default strategy
which of course cannot be the optimal choice for all presentations.

The  design  of  these commands  follows closely the  concept of the  ANU
Tietze transformation program designed by George Havas \cite{Hav69} which
has been  available  from Canberra  since  1977 in a  stand-alone version
implemented by Peter  Kenne and  James Richardson and later on revised by
Edmund F.~Robertson (see \cite{HKRR84}, \cite{Rob88}).

\vspace{5mm} In this section, we first describe the higher-level commands
'SimplifyPresentation', 'TzGo',  and  'TzGoGo' (the  first two  of  these
commands are identical).

Then  we  describe  the  lower-level commands  'TzEliminate', 'TzSearch',
'TzSearchEqual', and  'TzFindCyclicJoins'.  They  are the bricks of which
the preceding higher-level commands have been composed.  You may use them
to  try  alternative  strategies,  but  if  you  are  satisfied  by   the
performance of 'TzGo' and 'TzGoGo', then you don\'t need them.

Some  of  the Tietze transformation commands listed so far  may eliminate
generators and hence change the given presentation to a presentation on a
subset  of  the  given set of generators, but they all do *not* introduce
new generators.  However,  sometimes you will need to  substitute certain
words as new generators in order to improve your presentation.  Therefore
{\GAP}     offers     the     two     commands     'TzSubstitute'     and
'TzSubstituteCyclicJoins' which introduce new generators.  These commands
will be described next.

Subsequently we describe  some print  commands,  namely 'TzPrintLengths',
'TzPrintPairs',  and 'TzPrintOptions', which are useful if  you  run  the
Tietze transformations interactively.

At the end of this section  we list  the *Tietze  options* and give their
default  values.  These  are  parameters which essentially influence  the
performance  of  the commands mentioned  above.   However, they  are  not
specified as  arguments of function  calls.  Instead, they are associated
to the  presentation  records{\:} Each presentation record keeps  its own
set of Tietze option values in the form of ordinary record components.

\vspace{5mm}
'SimplifyPresentation( <P> )'%
\index{SimplifyPresentation} \\
'TzGo( <P> )'%
\index{TzGo}

'SimplifyPresentation'  performs Tietze transformations on a presentation
<P>.   It  is perhaps  the  most  convenient  of  the interactive  Tietze
transformation commands.  It offers  a kind of default strategy which, in
general,  saves you from explicitly  calling the lower-level commands  it
involves.

Roughly  speaking,  'SimplifyPresentation'  consists  of  a  loop  over a
procedure which  involves two  phases{\:} In the *search phase* it  calls
'TzSearch' and 'TzSearchEqual'  described  below which  try to reduce the
relator lengths  by  substituting  common  subwords  of relators,  in the
*elimination phase*  it calls the command  'TzEliminate'  described below
(or, more  precisely, a subroutine of 'TzEliminate' in order to save some
administrative overhead) which tries to eliminate generators that can  be
expressed as words in the remaining generators.

If 'SimplifyPresentation' succeeds in reducing the number of  generators,
the  number of  relators,  or the total length of all  relators, then  it
displays the  new  status before returning (provided that you did not set
the print level to zero).  However, it does not provide any output if all
these three  values  have remained unchanged, even if the 'TzSearchEqual'
command involved has changed the presentation such  that  another call of
'SimplifyPresentation' might provide further  progress.  Hence, in such a
case it makes sense  to repeat the call of the command for  several times
(or to call instead the 'TzGoGo' command which we will describe next).

As an example  we  compute  a presentation of a  subgroup of index 408 in
$PSL(2,17)$.

|    gap> F2 := FreeGroup( "a", "b" );;
    gap> G := F2 / [ F2.1^9, F2.2^2, (F2.1*F2.2)^4, (F2.1^2*F2.2)^3 ];;
    gap> a := G.1;;  b := G.2;;
    gap> H := Subgroup( G, [ (a*b)^2, (a^-1*b)^2 ] );;
    gap> Index( G, H );
    408
    gap> P := PresentationSubgroup( G, H );
    << presentation with 8 gens and 36 rels of total length 111 >>
    gap> P.printLevel := 2;;
    gap> SimplifyPresentation( P );
    &I  eliminating _x7 = _x5
    &I  eliminating _x5 = _x4
    &I  eliminating _x18 = _x3
    &I  eliminating _x8 = _x3
    &I  there are 4 generators and 8 relators of total length 21
    &I  there are 4 generators and 7 relators of total length 18
    &I  eliminating _x4 = _x3^-1*_x2^-1
    &I  eliminating _x1 = _x3^-1*_x2
    &I  there are 2 generators and 5 relators of total length 18
    &I  there are 2 generators and 4 relators of total length 13
    &I  there are 2 generators and 3 relators of total length 9
    gap> TzPrintRelators( P );
    &I  1. _x3^2
    &I  2. _x2^3
    &I  3. _x3*_x2*_x3*_x2 |

Note that the number  of loops over the two phases as well  as the number
of  subword   searches  or  generator  eliminations  in  each  phase  are
determined by a set of option parameters which may  heavily influence the
resulting presentation and the computing time (see Tietze options below).

'TzGo' is just another name  for the  'SimplifyPresentation' command.  It
has  been introduced for  the convenience  of those {\GAP} users  who are
used to  that  name from the *go* option of the ANU Tietze transformation
stand-alone program or from the *go* command in SPAS.

\vspace{5mm}
'TzGoGo( <P> )'%
\index{TzGoGo}

'TzGoGo'  performs  Tietze  transformations  on  a presentation  <P>.  It
repeatedly   calls  the  'TzGo'  command  until  neither  the  number  of
generators  nor  the number  of relators  nor  the total  length  of  all
relators have changed during five consecutive calls of 'TzGo'.

This  may  remarkably  save  you  time  and effort  if you  handle  small
presentations, however it may  lead  to  annoyingly  long  and  fruitless
waiting times in case of large presentations.

\vspace{5mm}
'TzEliminate( <P> )'%
\index{TzEliminate} \\
'TzEliminate( <P>, <gen> )' \\
'TzEliminate( <P>, <n> )'

'TzEliminate' tries to eliminate a generator from a  presentation <P> via
Tietze transformations.

Any  relator which  contains  some generator just  once  can be  used  to
substitute that generator by a word in the remaining generators.  If such
generators and relators exist, then 'TzEliminate' chooses a generator for
which  the product of  its number  of occurrences and  the length  of the
substituting word is minimal, and  then it eliminates this generator from
the  presentation, provided  that  the  resulting  total  length  of  the
relators  does   not  exceed  the  associated  Tietze  option   parameter
'<P>.spaceLimit'.   The default value of '<P>.spaceLimit'  is 'infinity',
but you may alter it appropriately (see Tietze options below).

If you specify a generator <gen> as  second argument, then  'TzEliminate'
only tries to eliminate that generator.

If you  specify an  integer  <n>  as second argument,  then 'TzEliminate'
tries  to   eliminate   up  to   <n>  generators.  Note  that  the  calls
'TzEliminate( <P> )' and 'TzEliminate( <P>, 1 )' are equivalent.

\vspace{5mm}
'TzSearch( <P> )'%
\index{TzSearch}

'TzSearch'  performs Tietze transformations  on  a  presentation <P>.  It
tries to reduce the relator lengths by  substituting  common  subwords of
relators by shorter words.

The idea is to find pairs of relators $r_1$ and $r_2$ of length $l_1$ and
$l_2$, respectively, such that $l_1 \le l_2$ and $r_1$ and $r_2$ coincide
(possibly  after inverting or conjugating one of  them)  in some  maximal
subword $w$, say, of length  greater than $l_1/2$, and then to substitute
each copy of $w$ in $r_2$ by the inverse complement of $w$ in $r_1$.

Two of the  Tietze option parameters which  are listed at the end of this
section may  strongly  influence the performance and  the results of  the
'TzSearch'  command.   These  are   the  parameters  '<P>.saveLimit'  and
'<P>.searchSimultaneous'.  The first of them has the following effect.

When TzSearch  has  finished  its main  loop over  all relators, then, in
general, there are  relators which  have  changed  and  hence  should  be
handled  again in  another run  through  the  whole  procedure.  However,
experience shows that it really does  not pay  to continue this way until
no more relators change.  Therefore, 'TzSearch' starts a new loop only if
the loop just finished has reduced the total length of the relators by at
least '<P>.saveLimit' per cent.

The default value of '<P>.saveLimit' is 10.

To understand the  effect of  the parameter '<P>.searchSimultaneous',  we
have to look in more detail at how 'TzSearch' proceeds.

First,  it sorts  the  list of  relators by increasing lengths.   Then it
performs a loop  over this list.  In each step  of this loop, the current
relator  is treated as *short  relator* $r_1$, and a subroutine is called
which  loops  over  the  succeeding  relators,  treating  them  as  *long
relators*   $r_2$   and  performing   the   respective   comparisons  and
substitutions.

As  this  subroutine performs a  very  expensive  process,  it  has  been
implemented  as a C routine in the  {\GAP} kernel.  For the given relator
$r_1$ of  length $l_1$,  say,  it  first  determines  the  *minimal match
length*  $l$  which  is  $l_1/2+1$,  if  $l_1$  is  even, or $(l_1+1)/2$,
otherwise.  Then it builds  up a hash list for all subwords of length $l$
occurring in the conjugates of  $r_1$ or $r_1^{-1}$, and finally it loops
over all long  relators  $r_2$ and  compares the  hash  values  of  their
subwords of length $l$ against this list.  A comparison of subwords which
is much more expensive is only done if a hash match has been found.

To improve  the efficiency  of this  process  we  allow the subroutine to
handle several short relators simultaneously provided that they  have the
same  minimal  match  length.   If,  for example,  it  handles  $n$ short
relators simultaneously,  then you save  $n  -  1$ loops  over  the  long
relators $r_2$,  but  you  pay  for  it by  additional fruitless  subword
comparisons.  In general, you will not get the best performance by always
choosing the maximal  possible number of  short  relators  to  be handled
simultaneously.  In fact, the optimal choice of the number will depend on
the concrete presentation under investigation.  You can use the parameter
'<P>.searchSimultaneous' to prescribe  an upper  bound for the  number of
short relators to be handled simultaneously.

The default value of '<P>.searchSimultaneous' is 20.

\vspace{5mm}
'TzSearchEqual( <P> )'%
\index{TzSearchEqual}

'TzSearchEqual'  performs Tietze transformations on a  presentation  <P>.
It tries to alter relators by substituting common subwords of relators by
subwords of equal length.

The idea is to find pairs of relators $r_1$ and $r_2$ of length $l_1$ and
$l_2$, respectively, such that $l_1$ is  even, $l_1  \le l_2$, and  $r_1$
and $r_2$ coincide (possibly after inverting or conjugating one  of them)
in some maximal subword $w$, say, of length at least $l_1/2$.  Let $l$ be
the  length of  $w$.   Then, if  $l > l_1/2$,  the pair is  handled as in
'TzSearch'.  Otherwise, if $l  = l_1/2$, then 'TzSearchEqual' substitutes
each copy of $w$ in $r_2$ by the inverse complement of $w$ in $r_1$.

The  Tietze  option   parameter   '<P>.searchSimultaneous'  is   used  by
'TzSearchEqual' in the same way as described for 'TzSearch'.

However, 'TzSearchEqual' does  not use the  parameter '<P>.saveLimit'{\:}
The loop over the relators is executed exactly once.

\vspace{5mm}
'TzFindCyclicJoins( <P> )'%
\index{TzFindCyclicJoins}

'TzFindCyclicJoins' performs  Tietze transformations  on  a  presentation
<P>.  It searches  for pairs of generators which generate the same cyclic
subgroup and eliminates  one of  the two generators of each such pair  it
finds.

More precisely{\:}  'TzFindCyclicJoins'  searches for pairs of generators
$a$  and  $b$ such that (possibly  after inverting  or  conjugating  some
relators)  the set of relators  contains the  commutator $[a,b]$, a power
$a^n$, and  a  product  of the form $a^s b^t$ with $s$ prime to $n$.  For
each  such  pair, 'TzFindCyclicJoins'  uses  the  Euclidian algorithm  to
express $a$ as a power of $b$, and then it eliminates $a$.

\vspace{5mm}
'TzSubstitute( <P> )'%
\index{TzSubstitute} \\
'TzSubstitute( <P>, <n> )' \\
'TzSubstitute( <P>, <n>, <eliminate> )'

'TzSubstitute' performs Tietze  transformations  on  a  presentation <P>.
Basically, it  substitutes  a  squarefree  word  of  length  2  as  a new
generator and then eliminates a  generator  from  the extended  generator
list.  We will describe this process in more detail.

The  parameters  <n>  and  <eliminate>  are  optional.   If  you  specify
arguments  for them, then <n>  is expected to be a  positive integer, and
<eliminate> is expected to be 0, 1, or 2.  The default values are $n = 1$
and $eliminate = 0$.

'TzSubstitute'   first  determines  the  <n>  most  frequently  occurring
squarefree  relator subwords  of  length  2 and sorts  them by decreasing
numbers of occurrences.  Let $ab$ be the <n>th word in that list, and let
<i> be the smallest  positive integer  which has not  yet  been used as a
generator number.  Then 'TzSubstitute' defines a new  generator '<P>.<i>'
(see  'AddGenerator' for  details), adds it to  the presentation together
with a new relator $P.i^{-1}ab$, and  replaces all occurrences of $ab$ in
the given relators by '<P>.<i>'.

Finally,  it eliminates some generator  from  the  extended presentation.
The  choice  of that  generator  depends  on  the  actual  value  of  the
<eliminate> parameter\:

If <eliminate> is zero, then the generator to be eliminated is  chosen as
by the  'TzEliminate' command.  This means  that in this case it may well
happen that  it is the generator '<P>.<i>' just introduced which  is  now
deleted  again  so  that  you do  not  get  any  remarkable  progress  in
transforming  your  presentation.   On  the other  hand,  this  procedure
guaranties that the total length of the relators will not be increased by
a call of 'TzSubstitute' with $eliminate = 0$.

Otherwise,  if <eliminate> is 1 or 2, then  'TzSubstitute' eliminates the
respective factor of the  substituted word $ab$, i.e., $a$ for $eliminate
=  1$ or  $b$ for $eliminate = 2$.  In this case, it may well happen that
the  total  length  of  the  relators  increases,  but  sometimes such an
intermediate  extension  is  the  only  way to  finally  reduce  a  given
presentation.

In order to decide which arguments might be appropriate for the next call
of 'TzSubstitute', often it  is helpful to print out a  list of the  most
frequently occurring squarefree  relator subwords of  length 2.  You  may
use the 'TzPrintPairs' command described below to do this.

As an example we handle a subgroup of index 266 in the Janko group $J_1$.

|    gap> F2 := FreeGroup( "a", "b" );;
    gap> J1 := F2 / [ F2.1^2, F2.2^3, (F2.1*F2.2)^7,
    >    Comm(F2.1,F2.2)^10, Comm(F2.1,F2.2^-1*(F2.1*F2.2)^2)^6 ];;
    gap> a := J1.1;;  b := J1.2;;
    gap> H := Subgroup ( J1, [ a, b^(a*b*(a*b^-1)^2) ] );;
    gap> P := PresentationSubgroup( J1, H );
    << presentation with 23 gens and 82 rels of total length 530 >>
    gap> TzGoGo( P );
    &I  there are 3 generators and 47 relators of total length 1368
    &I  there are 2 generators and 46 relators of total length 3773
    &I  there are 2 generators and 46 relators of total length 2570
    gap> TzGoGo( P );
    &I  there are 2 generators and 46 relators of total length 2568
    gap> TzGoGo( P );
    gap> & We do not get any more progress without substituting a new
    gap> & generator
    gap> TzSubstitute( P );
    &I  substituting new generator _x28 defined by _x6*_x23^-1
    &I  eliminating _x28 = _x6*_x23^-1
    gap> & GAP cannot substitute a new generator without extending the
    gap> & total length, so we have to explicitly ask for it
    gap> TzPrintPairs( P );
    &I  1.  504  occurrences of  _x6 * _x23^-1
    &I  2.  504  occurrences of  _x6^-1 * _x23
    &I  3.  448  occurrences of  _x6 * _x23
    &I  4.  448  occurrences of  _x6^-1 * _x23^-1
    gap> TzSubstitute( P, 2, 1 );
    &I  substituting new generator _x29 defined by _x6^-1*_x23
    &I  eliminating _x6 = _x23*_x29^-1
    &I  there are 2 generators and 46 relators of total length 2867
    gap> TzGoGo( P );
    &I  there are 2 generators and 45 relators of total length 2417
    &I  there are 2 generators and 45 relators of total length 2122
    gap> TzSubstitute( P, 1, 2 );
    &I  substituting new generator _x30 defined by _x23*_x29^-1
    &I  eliminating _x29 = _x30^-1*_x23
    &I  there are 2 generators and 45 relators of total length 2192
    gap> TzGoGo( P );
    &I  there are 2 generators and 42 relators of total length 1637
    &I  there are 2 generators and 40 relators of total length 1286
    &I  there are 2 generators and 36 relators of total length 807
    &I  there are 2 generators and 32 relators of total length 625
    &I  there are 2 generators and 22 relators of total length 369
    &I  there are 2 generators and 18 relators of total length 213
    &I  there are 2 generators and 13 relators of total length 141
    &I  there are 2 generators and 12 relators of total length 121
    &I  there are 2 generators and 10 relators of total length 101
    gap> TzPrintPairs( P );
    &I  1.  19  occurrences of  _x23 * _x30^-1
    &I  2.  19  occurrences of  _x23^-1 * _x30
    &I  3.  14  occurrences of  _x23 * _x30
    &I  4.  14  occurrences of  _x23^-1 * _x30^-1
    gap> & If we save a copy of the current presentation, then later we
    gap> & will be able to restart the computation from the current state
    gap> P1 := Copy( P );;
    gap> & Just for demonstration, let's make an inconvenient choice
    gap> TzSubstitute( P, 3, 1 );
    &I  substituting new generator _x31 defined by _x23*_x30
    &I  eliminating _x23 = _x31*_x30^-1
    &I  there are 2 generators and 10 relators of total length 122
    gap> TzGoGo( P );
    &I  there are 2 generators and 9 relators of total length 105
    gap> & The presentation is worse than the one we have saved, so let's
    gap> & restart from that one again
    gap> P := Copy( P1 );
    << presentation with 2 gens and 10 rels of total length 101 >>
    gap> TzSubstitute( P, 2, 1);
    &I  substituting new generator _x31 defined by _x23^-1*_x30
    &I  eliminating _x23 = _x30*_x31^-1
    &I  there are 2 generators and 10 relators of total length 107
    gap> TzGoGo( P );
    &I  there are 2 generators and 9 relators of total length 84
    &I  there are 2 generators and 8 relators of total length 75
    gap> TzSubstitute( P, 2, 1);
    &I  substituting new generator _x32 defined by _x30^-1*_x31
    &I  eliminating _x30 = _x31*_x32^-1
    &I  there are 2 generators and 8 relators of total length 71
    gap> TzGoGo( P );
    &I  there are 2 generators and 7 relators of total length 56
    &I  there are 2 generators and 5 relators of total length 36
    gap> TzPrintRelators( P );
    &I  1. _x32^5
    &I  2. _x31^5
    &I  3. _x31^-1*_x32^-1*_x31^-1*_x32^-1*_x31^-1*_x32^-1
    &I  4. _x31*_x32*_x31^-1*_x32*_x31^-1*_x32*_x31*_x32^-2
    &I  5. _x31^-1*_x32^2*_x31*_x32^-1*_x31^2*_x32^-1*_x31*_x32^2 |

\newpage
As shown in the preceding example, you can use the 'Copy' command to save
a copy of a presentation record and to restart from it  again if you want
to try an alternative strategy.  However, this copy will be lost as  soon
as you finish your current {\GAP} session.  If you use the 'Save' command
(see "Presentation Records") instead,  then you get a permanent copy on a
file which you can read in again in a later session.

\vspace{5mm}
'TzSubstituteCyclicJoins( <P> )'%
\index{TzSubstituteCyclicJoins}

'TzSubstituteCyclicJoins'    performs   Tietze   transformations   on   a
presentation <P>.  It tries to find pairs of generators $a$ and $b$, say,
for which among  the  relators (possibly after  inverting  or conjugating
some of them) there are the commutator $[a,b]$ and powers $a^m$ and $b^n$
with mutually  prime exponents  $m$ and  $n$.   For each  such  pair,  it
substitutes the product $ab$  as  a new generator, and then it eliminates
the generators $a$ and $b$.

\vspace{5mm}
'TzPrintLengths( <P> )'%
\index{TzPrintLengths}

'TzPrintLengths' prints  the list of  the lengths  of all relators of the
given presentation <P>.

\vspace{5mm}
'TzPrintPairs( <P> )'%
\index{TzPrintPairs} \\
'TzPrintPairs( <P>, <n> )'

'TzPrintPairs' determines  in  the  given presentation  <P>  the <n> most
frequently occurring squarefree relator subwords  of length  2 and prints
them together with their numbers of  occurrences.   The  default value of
<n> is 10.  A value $n = 0$ is interpreted as 'infinity'.

This  list is a  useful piece of information  in the context of using the
'TzSubstitute' command described above.

\vspace{5mm}
'TzPrintOptions( <P> )'%
\index{TzPrintOptions}

Several  of  the  Tietze  transformation  commands  described  above  are
controlled by  certain parameters, the *Tietze options*, which often have
a  tremendous  influence on their performance and  results.   However, in
each application of the  commands, an appropriate choice of these  option
parameters  will depend on the concrete presentation under investigation.
Therefore we have implemented the Tietze options in such  a way that they
are associated to the presentation records{\:}  Each  presentation record
keeps its own  set  of  Tietze option parameters in the form of  ordinary
record components.   In  particular, you may alter the  value  of any  of
these  Tietze  options by  just assigning  a  new value to the respective
record component.%
\index{Tietze options}

'TzPrintOptions'  prints the Tietze  option components of  the  specified
presentation <P>.

\vspace{5mm}
The Tietze options have the following meaning.

'eliminationsLimit': \\
        Whenever the elimination  phase of  the 'TzGo' command is entered
        for  a  presentation  <P>,   then  it   will  eliminate  at  most
        '<P>.eliminationsLimit' generators (except for further ones which
        have  turned  out  to   be  trivial).  Hence  you  may  use   the
        'eliminationsLimit' parameter as a break criterion for the 'TzGo'
        command.  Note, however, that it  is ignored by the 'TzEliminate'
        command.  The default value of 'eliminationsLimit' is 100.

'expandLimit': \\
        Whenever the routine for eliminating  more than  1  generators is
        called for a presentation <P> by the 'TzEliminate' command or the
        elimination phase of the 'TzGo' command, then it saves the  given
        total  length of the  relators,  and  subsequently it checks  the
        current total length against  its value before  each elimination.
        If the total length  has increased to more than '<P>.expandLimit'
        per cent of its original value, then the  routine returns instead
        of   eliminating  another  generator.   Hence  you  may  use  the
        'expandLimit' parameter  as a  break  criterion  for  the  'TzGo'
        command.  The default value of 'expandLimit' is 150.

'generatorsLimit': \\
        Whenever the elimination  phase of the  'TzGo' command is entered
        for  a  presentation  <P>  with  $n$  generators,  then  it  will
        eliminate at most $n - $'<P>.generatorsLimit'  generators (except
        for generators which turn out to  be trivial).  Hence you may use
        the  'generatorsLimit'  parameter  as  a break  criterion for the
        'TzGo' command.  The default value of 'generatorsLimit' is 0.

'lengthLimit': \\
        The  Tietze  transformation  commands  will  never  eliminate   a
        generator of a presentation  <P>,  if  they  cannot  exclude  the
        possibility  that  the  resulting total  length  of  the relators
        exceeds  the value of  '<P>.lengthLimit'.  The default  value  of
        'lengthLimit' is 'infinity'.

'loopLimit': \\
        Whenever the 'TzGo'  command  is called  for a  presentation <P>,
        then  it  will  loop  over  at  most '<P>.loopLimit' of its basic
        steps.  Hence you  may  use the  'loopLimit' parameter as a break
        criterion  for   the  'TzGo'   command.  The   default  value  of
        'loopLimit' is 'infinity'.

'printLevel': \\
        Whenever   Tietze  transformation  commands  are  called  for   a
        presentation <P> with  '<P>.printLevel'  $=  0$,  they  will  not
        provide any output except for error messages. If '<P>.printLevel'
        $=  1$, they will display some  reasonable amount of output which
        allows you to watch the progress of the computation and to decide
        about your next commands. In the case '<P>.printLevel' $= 2$, you
        will  get  a much more  generous amount  of output.  Finally,  if
        '<P>.printLevel' $= 3$, various messages on internal details will
        be added.  The default value of 'printLevel' is 1.

'saveLimit': \\
        Whenever the  'TzSearch' command has finished its main loop  over
        all relators of a presentation <P>, then it checks whether during
        this loop the total length of the relators has been reduced by at
        least  '<P>.saveLimit'  per  cent.  If  this is  the  case,  then
        'TzSearch' repeats its procedure instead of returning.  Hence you
        may use the 'saveLimit' parameter  as a  break  criterion for the
        'TzSearch' command  and, in  particular,  for the search phase of
        the 'TzGo' command.  The default value of 'saveLimit' is 10.

'searchSimultaneous': \\
        Whenever the 'TzSearch'  or the 'TzSearchEqual' command is called
        for  a  presentation  <P>,  then it is  allowed  to handle  up to
        '<P>.searchSimultaneously' short relators simultaneously (see for
        the description of the 'TzSearch' command for more details).  The
        choice of this parameter may heavily influence the performance as
        well  as  the result of the  'TzSearch'  and  the 'TzSearchEqual'
        commands and  hence also  of  the  search  phase  of  the  'TzGo'
        command.  The default value of 'searchSimultaneous' is 20.

\vspace{5mm} As soon as  a presentation record has been defined, you  may
alter any of its Tietze option parameters at any time by just assigning a
new value to the respective component.

To demonstrate  the  effect of the 'eliminationsLimit' parameter, we will
give  an example in which we handle a subgroup of index 240 in a group of
order 40320  given by  a presentation  due  to B.~H.  Neumann.   First we
construct a presentation of the subgroup, and  then  we  apply  to it the
'TzGoGo'   command  for  different   values  of  the  'eliminationsLimit'
parameter (including the default value 100).  In  fact, we also alter the
'printLevel' parameter, but this  is only done in order to suppress  most
of  the output.   In all  cases the  resulting  presentations  cannot  be
improved any more by applying the 'TzGoGo'  command again, i.e., they are
the best results which we can get without substituting new generators.

|    gap> F3 := FreeGroup( "a", "b", "c" );;
    gap> G := F3 / [ F3.1^3, F3.2^3, F3.3^3, (F3.1*F3.2)^5,
    >       (F3.1^-1*F3.2)^5, (F3.1*F3.3)^4, (F3.1*F3.3^-1)^4,
    >       F3.1*F3.2^-1*F3.1*F3.2*F3.3^-1*F3.1*F3.3*F3.1*F3.3^-1,
    >       (F3.2*F3.3)^3, (F3.2^-1*F3.3)^4 ];;
    gap> a := G.1;;  b := G.2;;  c := G.3;;
    gap> H := Subgroup( G, [ a, c ] );;
    gap> P := PresentationSubgroup( G, H );
    << presentation with 224 gens and 593 rels of total length 2769 >>
    gap> for i in [ 28, 29, 30, 94, 100 ] do
    >       Pi := Copy( P );
    >       Pi.eliminationsLimit := i;
    >       Print( "&I  eliminationsLimit set to ", i, "\n" );
    >       Pi.printLevel := 0;
    >       TzGoGo( Pi );
    >       TzPrintStatus( Pi );
    >    od;
    &I  eliminationsLimit set to 28
    &I  there are 2 generators and 95 relators of total length 10817
    &I  eliminationsLimit set to 29
    &I  there are 2 generators and 5 relators of total length 35
    &I  eliminationsLimit set to 30
    &I  there are 3 generators and 98 relators of total length 2928
    &I  eliminationsLimit set to 94
    &I  there are 4 generators and 78 relators of total length 1667
    &I  eliminationsLimit set to 100
    &I  there are 3 generators and 90 relators of total length 3289 |

Similarly,  we  demonstrate the influence of the 'saveLimit' parameter by
just continuing the  preceding example  for some  different values of the
'saveLimit' parameter  (including  its  default  value  10),  but without
changing the 'eliminationsLimit'  parameter which keeps its default value
100.

|    gap> for i in [ 9, 10, 11, 12, 15 ] do
    >       Pi := Copy( P );
    >       Pi.saveLimit := i;
    >       Print( "&I  saveLimit set to ", i, "\n" );
    >       Pi.printLevel := 0;
    >       TzGoGo( Pi );
    >       TzPrintStatus( Pi );
    >    od;
    &I  saveLimit set to 9
    &I  there are 3 generators and 97 relators of total length 5545
    &I  saveLimit set to 10
    &I  there are 3 generators and 90 relators of total length 3289
    &I  saveLimit set to 11
    &I  there are 3 generators and 103 relators of total length 3936
    &I  saveLimit set to 12
    &I  there are 2 generators and 4 relators of total length 21
    &I  saveLimit set to 15
    &I  there are 3 generators and 143 relators of total length 18326 |

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{DecodeTree}%

'DecodeTree( <P> )'%
\index{tree decoding}

'DecodeTree' eliminates the secondary generators  from a presentation <P>
constructed by  the Modified Todd-Coxeter (see 'PresentationSubgroupMtc')
or      the      Reduced     Reidemeister-Schreier     procedure     (see
'PresentationSubgroupRrs', 'PresentationNormalClosureRrs').  It is called
automatically by the 'PresentationSubgroupMtc'  command where it  reduces
<P> to a presentation on the given subgroup generators.%
\index{secondary subgroup generators}

In  order to explain  the effect of this command  we need to insert a few
remarks  on   the subgroup presentation  commands    described in section
"Subgroup Presentations".   All these commands  have  the common property
that in  the process of constructing  a presentation for a given subgroup
<H>  of a  finitely presented group   <G> they first   build up a  highly
redundant  list of  generators of <H>  which  consists of  an (in general
small)  list  of ``primary\'\'\ generators,  followed  by  an (in general
large)  list   of ``secondary\'\'\ generators,     and  then construct  a
presentation $P_0$, say, *on a sublist of  these generators* by rewriting
the defining relators of <G>.  This sublist contains all primary, but, at
least in general, by far not all secondary generators.%
\index{primary subgroup generators}

The role of the primary generators depends on  the concrete choice of the
subgroup presentation command.  If  the  Modified  Todd-Coxeter method is
used, they are just the given generators of <H>, whereas  in  the case of
the Reduced Reidemeister-Schreier algorithm they are  constructed  by the
program.

Each of  the secondary generators is defined  by a  word of length two in
the preceding  generators and their inverses.  By historical reasons, the
list  of these  definitions is  called  the  *subgroup  generators  tree*
though in fact it is not a tree but rather a kind of bush.%
\index{subgroup generators tree}

Now we have to distinguish two cases.  If  $P_0$ has been constructed  by
the Reduced Rei\-de\-mei\-ster-Schreier routines, it is a presentation of
<H>.   However, if  the Modified Todd-Coxeter  routines  have  been  used
instead, then  the relators in $P_0$ are valid relators  of <H>, but they
do not necessarily  define <H>.  We handle these cases in turn,  starting
with the latter one.

Also in the  case  of the Modified Todd-Coxeter method,  we could  easily
extend  $P_0$ to a presentation of <H> by adding to it  all the secondary
generators which are not yet contained in it and all the definitions from
the generators tree as additional generators and relators.  Then we could
recursively eliminate all secondary generators by Tietze  transformations
using the  new relators.  However,  this  procedure  turns out to  be too
inefficient to be of interest.

Instead, we  use the  so called *tree decoding* procedure which  has been
developed  in  St.~Andrews by  David  G.~Arrell,  Sanjiv  Manrai,  Edmund
F.~Robertson, and Michael F.~Wor\-boys  (see \cite{AMW82},  \cite{AR84}).
It proceeds as follows.

Starting from  $P = P_0$, it  runs through a  number of steps  in each of
which it  eliminates the current ``last\'\'\  generator  (with respect to
the list of all primary and secondary generators).  If the last generator
<g>, say, is a primary generator, then the procedure finishes.  Otherwise
it checks  whether there is a relator  in the current  presentation which
can be used to substitute <g> by a Tietze transformation.  If so, this is
done.  Otherwise, and only then, the  tree definition of  <g> is added to
<P> as  a  new relator,  and  the generators involved   are added as  new
generators if they have not yet been contained in <P>.  Subsequently, <g>
is eliminated.

Note that the extension of <P> by  one or two new  generators is *not*  a
Tietze  transformation.  In general, it will change the  isomorphism type
of the group  defined by  <P>.  However,  it is a remarkable  property of
this  procedure, that  at  the  end,  i.e.,  as  soon  as  all  secondary
generators have been eliminated, it  provides a  presentation  $P = P_1$,
say, which defines  a  group  isomorphic to <H>.   In  fact,  it is  this
presentation  which is returned by  the 'DecodeTree' command and hence by
the 'PresentationSubgroupMtc' command.

If, in the other case, the presentation $P_0$ has been constructed by the
Reduced   Reidemeister-Schreier   algorithm,  then  $P_0$   itself  is  a
presentation  of <H>, and the corresponding subgroup presentation command
('PresentationSubgroupRrs'   or    'PresentationNormalClosureRrs')   just
returns $P_0$.

As  mentioned in section  "Subgroup Presentations", we  recommend further
simplifying this  presentation  before using it.  The standard  way to do
this is to start from $P_0$ and to apply suitable Tietze transformations,
e.g.,  by calling the 'TzGo' or  'TzGoGo' commands.  This is probably the
most efficient approach, but  you will end up with a presentation on some
unpredictable set of generators.   As an alternative, {\GAP}  offers  you
the  'DecodeTree' command  which you can use to  eliminate all  secondary
generators (provided that there are no space or time problems).  For this
purpose,  the  subgroup presentation  commands  do  not only  return  the
resulting  presentation, but also the tree (together with some associated
lists)  as  a  kind  of  side  result in  a component  '<P>.tree' of  the
resulting presentation record <P>.

Note,  however, that  the tree decoding  routines will not work correctly
any  more  on  a presentation  from which  generators have  already  been
eliminated  by  Tietze transformations.  Therefore, to prevent  you  from
getting wrong  results by calling  the  'DecodeTree'  command in  such  a
situation, {\GAP}  will automatically remove the subgroup generators tree
from  a  presentation  record  as  soon  as  one  of  the  generators  is
substituted by a Tietze transformation.

Nevertheless,  a certain misuse of  the command is still possible, and we
want to explicitly warn you from this.   The reason  is  that the  Tietze
option parameters described in  section "Tietze Transformations" apply to
the 'DecodeTree' command as well.  Hence, in case of inadequate values of
these  parameters,  it may  happen  that the  'DecodeTree' routine  stops
before all  the secondary generators  have vanished.  In this case {\GAP}
will  display  an  appropriate  warning.   Then  you  should  change  the
respective   parameters   and  continue  the  process   by  calling   the
'DecodeTree'  command  again.   Otherwise,  if  you  would  apply  Tietze
transformations,  it  might  happen  because  of the convention described
above that  the  tree  is  removed  and  that you end  up  with  a  wrong
presentation.

After  a successful run of  the 'DecodeTree' command  it is convenient to
further   simplify  the   resulting   presentation  by  suitable   Tietze
transformations.

As an example of an explicit call of the 'DecodeTree' command we  compute
two presentations  of  a  subgroup  of  order  $384$  in a group of order
$6912$.   In  both  cases  we   use   the  Reduced  Reidemeister-Schreier
algorithm, but  in the first run we just apply the Tietze transformations
offered by the 'TzGoGo' command with  its default  parameters, whereas in
the second run we call the 'DecodeTree' command before.

|    gap> F2 := FreeGroup( "a", "b" );;
    gap> G := F2 / [ F2.1*F2.2^2*F2.1^-1*F2.2^-1*F2.1^3*F2.2^-1,
    >                F2.2*F2.1^2*F2.2^-1*F2.1^-1*F2.2^3*F2.1^-1 ];;
    gap> a := G.1;;  b := G.2;;
    gap> H := Subgroup( G, [ Comm(a^-1,b^-1), Comm(a^-1,b), Comm(a,b) ] );;
    gap> &
    gap> & We use the Reduced Reidemeister Schreier method and default
    gap> & Tietze transformations to get a presentation for H.
    gap> P := PresentationSubgroupRrs( G, H );
    << presentation with 18 gens and 35 rels of total length 169 >>
    gap> TzGoGo( P );
    &I  there are 3 generators and 20 relators of total length 488
    &I  there are 3 generators and 20 relators of total length 466
    gap> & We end up with 20 relators of total length 466.
    gap> &
    gap> & Now we repeat the procedure, but we call the tree decoding
    gap> & algorithm before doing the Tietze transformations.
    gap> P := PresentationSubgroupRrs( G, H );
    << presentation with 18 gens and 35 rels of total length 169 >>
    gap> DecodeTree( P );
    &I  there are 9 generators and 26 relators of total length 185
    &I  there are 6 generators and 23 relators of total length 213
    &I  there are 3 generators and 20 relators of total length 252
    &I  there are 3 generators and 20 relators of total length 244
    gap> TzGoGo( P );
    &I  there are 3 generators and 19 relators of total length 168
    &I  there are 3 generators and 17 relators of total length 138
    &I  there are 3 generators and 15 relators of total length 114
    &I  there are 3 generators and 13 relators of total length 96
    &I  there are 3 generators and 12 relators of total length 84
    gap> & This time we end up with a shorter presentation. |

As  an  example  of   an   implicit   call   of   the   command  via  the
'PresentationSubgroupMtc' command  we handle a subgroup of index 240 in a
group of order 40320 given by a presentation due to B.~H.~Neumann.

|    gap> F3 := FreeGroup( "a", "b", "c" );;
    gap> G := F3 / [ F3.1^3, F3.2^3, F3.3^3, (F3.1*F3.2)^5,
    >       (F3.1^-1*F3.2)^5, (F3.1*F3.3)^4, (F3.1*F3.3^-1)^4,
    >       F3.1*F3.2^-1*F3.1*F3.2*F3.3^-1*F3.1*F3.3*F3.1*F3.3^-1,
    >       (F3.2*F3.3)^3, (F3.2^-1*F3.3)^4 ];;
    gap> a := G.1;;  b := G.2;;  c := G.3;;
    gap> H := Subgroup( G, [ a, c ] );;
    gap> InfoFpGroup1 := Print;;
    gap> P := PresentationSubgroupMtc( G, H );;
    &I  index = 240  total = 4737  max = 4507
    &I  MTC defined 2 primary and 4472 secondary subgroup generators
    &I  there are 246 generators and 617 relators of total length 2893
    &I  calling DecodeTree
    &I  there are 114 generators and 380 relators of total length 1829
    &I  there are 72 generators and 293 relators of total length 1849
    &I  there are 47 generators and 252 relators of total length 2062
    &I  there are 36 generators and 214 relators of total length 2341
    &I  there are 25 generators and 188 relators of total length 2957
    &I  there are 20 generators and 170 relators of total length 3313
    &I  there are 20 generators and 158 relators of total length 4155
    &I  there are 21 generators and 155 relators of total length 6088
    &I  there are 24 generators and 155 relators of total length 9014
    &I  there are 27 generators and 155 relators of total length 13812
    &I  there are 31 generators and 155 relators of total length 20654
    &I  there are 36 generators and 155 relators of total length 32444
    &I  there are 39 generators and 155 relators of total length 51121
    &I  there are 42 generators and 155 relators of total length 74713
    &I  there are 40 generators and 153 relators of total length 85251
    &I  there are 12 generators and 140 relators of total length 29401
    &I  there are 7 generators and 131 relators of total length 18067
    &I  there are 4 generators and 122 relators of total length 20325
    &I  there are 2 generators and 115 relators of total length 21588
    &I  there are 2 generators and 114 relators of total length 16370
    gap> TzGoGo( P );
    &I  there are 2 generators and 112 relators of total length 13126
    &I  there are 2 generators and 99 relators of total length 7572
    &I  there are 2 generators and 62 relators of total length 3384
    &I  there are 2 generators and 24 relators of total length 1506
    &I  there are 2 generators and 20 relators of total length 1000
    &I  there are 2 generators and 13 relators of total length 494
    &I  there are 2 generators and 10 relators of total length 314
    &I  there are 2 generators and 9 relators of total length 252
    &I  there are 2 generators and 8 relators of total length 192
    &I  there are 2 generators and 7 relators of total length 92
    &I  there are 2 generators and 6 relators of total length 52
    gap> TzPrintGenerators( P );
    &I  1.  _x1   26 occurrences
    &I  2.  _x2   26 occurrences |


