% This file was created automatically from pres.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  pres.msk                   GAP documentation             Volkmar Felsch
%A                                                           Alexander Hulpke
%%
%A  @(#)$Id: pres.msk,v 1.24 2003/10/28 04:55:03 gap Exp $
%%
%Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Presentations and Tietze Transformations}

A finite presentation describes a group, but usually there is a multitude of
presentations that describe isomorphic groups. Therefore a presentation in
{\GAP} is different from a finitely presented group though there are ways to
translate between both.

An important feature of presentations is that they can be modified (see
sections "Changing Presentations" to "Tietze Transformations that introduce
new Generators").

%%  The code for presentations was designed and implemented by Volkmar Felsch.

If you only want to get new presentations for subgroups of a finitely
presented group (and do not want to manipulate presentations yourself),
chances are that the operation `IsomorphismFpGroup' already does what you
want (see~"New Presentations and Presentations for Subgroups").

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Creating Presentations}

\>PresentationFpGroup( <G> [, <printlevel>] ) F

creates a presentation, i.e. a  Tietze object, for the given finitely
presented group <G>. This presentation will be exactly as the
presentation of <G> and *no* initial Tietze transformations are applied
to it.

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.  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.



\beginexample
gap> f := FreeGroup( "a", "b" );
<free group on the generators [ a, b ]>
gap> g := f / [ f.1^3, f.2^2, (f.1*f.2)^3 ];
<fp group on the generators [ a, b ]>
gap> p := PresentationFpGroup( g );
<presentation with 2 gens and 3 rels of total length 11>
\endexample

Most of the functions creating presentations and all functions performing
Tietze transformations on them sort the relators by increasing lengths. The
function `PresentationFpGroup' is an exception because it is intended to
reflect the relators that were used to define the involved FpGroup. You may
use the following command to sort the presentation.

\>TzSort( <P> ) F

sorts the relators of the given presentation <P> by increasing lengths.
There is no particular ordering defined for the relators of equal
length. Note that `TzSort' does not return a new object. It changes the
given presentation.



\>GeneratorsOfPresentation( <P> ) O

returns a list of free generators that is a `ShallowCopy' of the current
generators of the presentation <P>.


\>FpGroupPresentation( <P> [, <nam>] ) F

constructs an `FpGroup' group as defined by the  given Tietze
presentation <P>.



\beginexample
gap> h := FpGroupPresentation( p );
<fp group on the generators [ a, b ]>
gap> h = g;
false
\endexample

\>PresentationViaCosetTable( <G> ) F
\>PresentationViaCosetTable( <G>, <F>, <words> ) F

constructs a presentation for a given concrete finite group. It applies
the relations finding algorithm which has been described in \cite{Can73}
and \cite{Neu82}. It automatically applies Tietze transformations to the
presentation found.

If only a group <G> has been specified, the single stage algorithm is
applied.

The operation `IsomorphismFpGroup' in contrast uses a multiple-stage
algorithm using a composition series and stabilizer chains. It usually
should be used rather than `PresentationViaCosetTable'. (It does not
apply Tietze transformations automatically.)

If the two stage algorithm is to be used, `PresentationViaCosetTable'
expects a subgroup <H> of <G> to be provided in form of two additional
arguments <F> and <words>, where <F> is a free group with the same number
of generators as <G>, and <words> is a list of words in the generators of
<F> which supply a list of generators of <H> if they are evaluated as
words in the corresponding generators of <G>.



\beginexample
gap> G := GeneralLinearGroup( 2, 7 );
GL(2,7)
gap> GeneratorsOfGroup( G );
[ [ [ Z(7), 0*Z(7) ], [ 0*Z(7), Z(7)^0 ] ], 
  [ [ Z(7)^3, Z(7)^0 ], [ Z(7)^3, 0*Z(7) ] ] ]
gap> Size( G );
2016
gap> P := PresentationViaCosetTable( G );
<presentation with 2 gens and 5 rels of total length 46>
gap> TzPrintRelators( P );
#I  1. f2^3
#I  2. f1^6
#I  3. f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1*f1^-1*f2^-1
#I  4. f1*f2*f1^-1*f2^-1*f1*f2^-1*f1^-1*f2*f1*f2^-1*f1^-1*f2^-1
#I  5. f1^-3*f2*f1*f2*f1^-1*f2^-1*f1^-1*f2^-1*f1^-2*f2
\endexample

The two stage algorithm saves an essential amount of space by
constructing two coset tables of lengths $|H|$ and $|G|/|H|$ instead of
just one coset table of length $|G|$. The next example shows an application
of this option in the case of a subgroup of size 7920 and index 12 in a
permutation group of size 95040.

\beginexample
gap> M12 := Group( [ (1,2,3,4,5,6,7,8,9,10,11), (3,7,11,8)(4,10,5,6),
> (1,12)(2,11)(3,6)(4,8)(5,9)(7,10) ], () );;
gap> F := FreeGroup( "a", "b", "c" );
<free group on the generators [ a, b, c ]>
gap> words := [ F.1, F.2 ];
[ a, b ]
gap> P := PresentationViaCosetTable( M12, F, words );
<presentation with 3 gens and 10 rels of total length 97>
gap> G := FpGroupPresentation( P );
<fp group on the generators [ a, b, c ]>
gap> RelatorsOfFpGroup( G );
[ c^2, b^4, a*c*a*c*a*c, a*b^-2*a*b^-2*a*b^-2, a^11, 
  a^2*b*a^-2*b^-2*a*b^-1*a^2*b^-1, a*b*a^-1*b*a^-1*b^-1*a*b*a^-1*b*a^-1*b^-1, 
  a^2*b*a^2*b^-2*a^-1*b*a^-1*b^-1*a^-1*b^-1, 
  a*b*a*b*a^2*b^-1*a^-1*b^-1*a*c*b*c, a^4*b*a^2*b*a^-2*c*a*b*a^-1*c ]
\endexample

Before it is returned, the resulting presentation is being simplified by
appropriate calls of the function `SimplifyPresentation' (see "Tietze
Transformations"), but without allowing any eliminations of generators.
This restriction guarantees that we get a bijection between the list of
generators of <G> and the list of generators in the presentation. Hence,
if the generators of <G> are redundant and if you don{\pif}t care for the
bijection, you may get a shorter presentation by calling the function
`SimplifyPresentation', now without this restriction, once more yourself.

\beginexample
gap> H := Group(
> [ (2,5,3), (2,7,5), (1,8,4), (1,8,6), (4,8,6), (3,5,7) ], () );;
gap> P := PresentationViaCosetTable( H );
<presentation with 6 gens and 12 rels of total length 42>
gap> SimplifyPresentation( P );
#I  there are 4 generators and 10 relators of total length 36
\endexample

If you apply the function `FpGroupPresentation' to the resulting
presentation you will get a finitely presented group isomorphic to <G>.
Note, however, that the function `IsomorphismFpGroup' (see
"IsomorphismFpGroup") is recommended for this purpose.

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

\>SimplifiedFpGroup( <G> ) F

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 a group  isomorphic to the given one  with a
presentation which has been tried to simplify via Tietze
transformations.


If the connection to the original group is important, then the operation
`IsomorphismSimplifiedFpGroup' (see~"IsomorphismSimplifiedFpGroup") should
be used instead.
\beginexample
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 );
<fp group on the generators [ G1, G3 ]>
gap> RelatorsOfFpGroup( H );
[ G1^2, G1*G3^-1*G1*G3^-1, G3^4 ]
\endexample

In fact, the command

\begintt
H := SimplifiedFpGroup( G );
\endtt

is an abbreviation of the command sequence

\begintt
P := PresentationFpGroup( G, 0 );;
SimplifyPresentation( P );
H := FpGroupPresentation( P );
\endtt

which applies a rather simple-minded strategy of Tietze transformations
to the intermediate presentation <P>.
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{Subgroup Presentations}

\atindex{Schreier}{@Schreier}

\>PresentationSubgroup( <G>, <H>[, <string>] ) F

is a synonym for `PresentationSubgroupRrs(<G>,<H>[,<string>])'.


\>PresentationSubgroupRrs( <G>, <H> [, <string>] ) F
\>PresentationSubgroupRrs( <G>, <table> [, <string>] ) F

uses the  Reduced Reidemeister-Schreier method to compute a presentation
<P>, say, for a subgroup <H> of a finitely presented group <G>. The
generators in the resulting presentation will be named <string>1,
<string>2, ... , the default string is `\"_x\"'.
You may access the <i>-th of these generators by <P>!.<i>.

Alternatively to the subgroup <H>, its coset table <table> in <G> may be
given as second argument.



\beginexample
gap> f := FreeGroup( "a", "b" );;
gap> g := f / [ f.1^2, f.2^3, (f.1*f.2)^5 ];
<fp group on the generators [ a, b ]>
gap> g1 := Size( g );
60
gap> u := Subgroup( g, [ g.1, g.1^g.2 ] );
Group([ a, b^-1*a*b ])
gap> p := PresentationSubgroup( g, u, "g" );
<presentation with 3 gens and 4 rels of total length 12>
gap> gens := GeneratorsOfPresentation( p );
[ g1, g2, g3 ]
gap> TzPrintRelators( p );
#I  1. g1^2
#I  2. g2^2
#I  3. g3*g2*g1
#I  4. g3^5
\endexample

Note 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 will have to introduce the respective
variables and to assign the generators to them.

\beginexample
gap> gens[1] = g1;
false
gap> g1;
60
gap> g1 := gens[1];; g2 := gens[2];; g3 := gens[3];;
gap> g1;
g1
\endexample

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
the Reidemeister-Schreier algorithm of George Havas, 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 command `PresentationSubgroupRrs', it first obtains
a coset table of <H> in <G> if not given. 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 is 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.

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 command
`DecodeTree' (see "DecodeTree") before you can use it. Therefore it is
returned in the form of a presentation, <P> say.

Compared with the Modified Todd-Coxeter method described below, the
Reduced Reidemeister-Schreier method (as well as Havas{\pif} 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).

For certain applications you may be interested in getting not only just a
presentation for <H>, but also a relation between the involved generators of
<H> and the generators of <G>. The subgroup generators in the presentation
are sorted such that the primary generators precede the secondary ones.
Moreover, for each secondary subgroup generator there is a relator in the
presentation which expresses this generator as a word in preceding ones.
Hence, all we need in addition is a list of words in the generators of <G>
which express the primary subgroup generators. In fact, such a list is
provided in the attribute `PrimaryGeneratorWords' of the resulting
presentation.

\>PrimaryGeneratorWords( <P> ) A

is an attribute of the presentation <P> which holds a list of words in
the associated group generators (of the underlying free group) which
express the primary subgroup generators of <P>.


\beginexample
gap> PrimaryGeneratorWords( p );
[ a, b^-1*a*b ]
\endexample

\>PresentationSubgroupMtc( <G>, <H> [, <string>] [, <print level>] ) F

uses the Modified Todd-Coxeter coset representative enumeration method
to compute a presentation <P>, say, for a subgroup <H> of a finitely
presented group <G>. The presentation returned is in generators
corresponding to the generators of <H>. The generators in the resulting
presentation will be named <string>1, <string>2, ... , the default string
is `\"_x\"'. You may access the <i>-th of these generators by <P>!.<i>.

The default print level is 1. If the print level is set to 0, then the
printout of the implicitly called function `DecodeTree' will be
suppressed.



\beginexample
gap> p := PresentationSubgroupMtc( g, u );
#I  there are 3 generators and 4 relators of total length 12
#I  there are 2 generators and 3 relators of total length 14
<presentation with 2 gens and 3 rels of total length 14>
\endexample

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{\pif}s method was proved in \cite{BC76}. It has been generalized to
cover a broad spectrum of different versions (see the survey \cite{Neu82}).

The `Modified Todd-Coxeter' method performs an enumeration of coset
representatives. It proceeds like an ordinary coset enumeration (see
"Coset Tables and Coset Enumeration"), 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.

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.

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 `PresentationSubgroupRrs' 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 `PresentationSubgroupMtc' command applies the
so called *decoding tree* 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 may add a lot of intermediate
generators and relators (and even change the isomorphism type)
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 command
`PresentationSubgroupMtc' compared to the command `PresentationSubgroupRrs'.
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,
<P> say.

As the function `PresentationSubgroupRrs' described above (see there for
details), the function `PresentationSubgroupMtc' returns a list of the
primary subgroup generators of <H> in the attribute
`PrimaryGeneratorWords' of <P>. In fact, this list is not very exciting here
because it is just a shallow copy of the attribute value
`GeneratorsOfPresentation(H)', however it is
needed to guarantee a certain consistency between the results of the
different functions for computing subgroup presentations.

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

\>PresentationNormalClosureRrs( <G>, <H> [, <string>] ) F

uses the Reduced Reidemeister-Schreier method to compute a presentation
<P>, say, for the normal closure of a subgroup <H> of a finitely
presented group <G>. The generators in the resulting presentation will
be named <string>1, <string>2, ... , the default string is `\"_x\"'.
You may access the <i>-th of these generators by <P>!.<i>. 


\>PresentationNormalClosure( <G>, <H>[, <string>] ) F

is a synonym for `PresentationNormalClosureRrs(<G>,<H>[,<string>])'.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Relators in a Presentation}

In order to speed up the Tietze transformation routines,
each relator in a presentation <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. Note that the numbering of the generators in Tietze words is
always relative to a generator list and bears no relation to the internal
numbering of generators in a family of associative words.

\>TietzeWordAbstractWord( <word>, <fgens> ) F

assumes  <fgens>  to be a  list  of  free group
generators  and  <word>  to be an abstract word  in these generators.  It
converts <word> into a Tietze word, i. e., a list of positive or negative
generator numbers.

This function simply calls `LetterRepAssocWord'.


\>AbstractWordTietzeWord( <word>, <fgens> ) F

assumes  <fgens>  to be  a list  of  free group
generators and  <word> to be a Tietze word in these generators,  i. e., a
list of positive or negative generator numbers.  It converts <word> to an
abstract word.

This function simply calls `AssocWordByLetterRep'.



\beginexample
gap> F := FreeGroup( "a", "b", "c" ,"d");
<free group on the generators [ a, b, c, d ]>
gap> tzword := TietzeWordAbstractWord(
> Comm(F.4,F.2) * (F.3^2 * F.2)^-1, GeneratorsOfGroup( F ){[2,3,4]} );
[ -3, -1, 3, -2, -2 ]
gap> AbstractWordTietzeWord( tzword, GeneratorsOfGroup( F ){[2,3,4]} );
d^-1*b^-1*d*c^-2
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Printing Presentations}

Whenever you create a presentation <P>, say, or assign it to a variable,
{\GAP} will respond by printing <P>. However, as <P> may contain a lot of
generators and many relators of large length, it would be annoying if the
standard print facilities displayed all this information in detail.
So they restrict the printout to just one line of text containing the number
of generators, the number of relators, and the total length of all relators
of <P>. As compensation, {\GAP} offers some special print commands which
display various details of a presentation.

\>TzPrintGenerators( <P> [, <list>] ) F

prints the generators of the given Tietze presentation <P> together with
the number of their occurrences in the relators. The optional second
argument can be used to specify the numbers of the generators to be
printed. Default: all generators are printed.



\beginexample
gap> G := Group( [ (1,2,3,4,5), (2,3,5,4), (1,6)(3,4) ], () );
Group([ (1,2,3,4,5), (2,3,5,4), (1,6)(3,4) ])
gap> P := PresentationViaCosetTable( G );
<presentation with 3 gens and 6 rels of total length 28>
gap> TzPrintGenerators( P );
#I  1.  f1   11 occurrences
#I  2.  f2   10 occurrences
#I  3.  f3   7 occurrences   involution
\endexample

\>TzPrintRelators( <P>[, <list>] ) F

prints the relators of the given  Tietze presentation <P>.  The optional
second argument <list> can be used to specify the  numbers of the
relators to be printed.  Default: all relators are printed.



\beginexample
gap> TzPrintRelators( P );
#I  1. f3^2
#I  2. f2^4
#I  3. f2^-1*f3*f2^-1*f3
#I  4. f1^5
#I  5. f1^2*f2*f1*f2^-1
#I  6. f1^-1*f3*f1*f3*f1^-1*f2^2*f3
\endexample

\>TzPrintLengths( <P> ) F

prints just a list of all relator lengths of the given presentation <P>.



\beginexample
gap> TzPrintLengths( P );
[ 2, 4, 4, 5, 5, 8 ]
\endexample

\>TzPrintStatus( <P> [, <norepeat> ] ) F

is an internal function which is used by the Tietze transformation
routines to print the number of generators, the number of relators,
and the total length of all relators in the given Tietze presentation
<P>. If <norepeat> is specified as `true', the printing is suppressed
if none of the three values has changed since the last call.



\beginexample
gap> TzPrintStatus( P );
#I  there are 3 generators and 6 relators of total length 28
\endexample

\>TzPrintPresentation( <P> ) F

prints the generators and the relators of a Tietze presentation.
In fact, it is an abbreviation for the successive call of the three
commands `TzPrintGenerators(<P>)', `TzPrintRelators(<P>)', and
`TzPrintStatus(<P>)'.


\>TzPrint( <P> [, <list>] ) F

prints the current generators of the given presentation <P>, and prints
the relators of <P> as Tietze words (without converting them back to
abstract words as the functions `TzPrintRelators' and
`TzPrintPresentation' do). The optional second argument can be used to
specify the numbers of the relators to be printed. Default: all relators
are printed.



\beginexample
gap> TzPrint( P );
#I  generators: [ f1, f2, f3 ]
#I  relators:
#I  1.  2  [ 3, 3 ]
#I  2.  4  [ 2, 2, 2, 2 ]
#I  3.  4  [ -2, 3, -2, 3 ]
#I  4.  5  [ 1, 1, 1, 1, 1 ]
#I  5.  5  [ 1, 1, 2, 1, -2 ]
#I  6.  8  [ -1, 3, 1, 3, -1, 2, 2, 3 ]
\endexample

\>TzPrintPairs( <P> [, <n>] ) F

prints the <n> most often occurring relator subwords of the form
$a b$, where $a$ and $b$ are different generators or inverses of
generators, together with the number of their occurrences. The default
value of <n> is 10. A value <n> = 0 is interpreted as `infinity'.

The function `TzPrintPairs' is useful in the context of Tietze
transformations which introduce new generators by substituting words in
the current generators (see "Tietze Transformations that introduce new
Generators"). It gives some evidence for an appropriate choice of
a word of length 2 to be substituted.



\beginexample
gap> TzPrintPairs( P, 3 );
#I  1.  3  occurrences of  f2 * f3
#I  2.  2  occurrences of  f2^-1 * f3
#I  3.  2  occurrences of  f1 * f3
\endexample

Finally, there is a function `TzPrintOptions'. It is described in section
"Tietze Options".

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

The functions described in this section may be used to change a presentation.
Note, however, that in general they do not perform Tietze transformations
because they change or may change the isomorphism type of the group defined
by the presentation.

\>AddGenerator( <P> ) F

extends the presentation <P> by a new generator.

Let <i> be the smallest positive integer which has not yet been used as
a generator number in the given presentation. `AddGenerator' defines a
new abstract generator $x_i$ with the name `"_x<i>"' and adds it to the
list of generators of <P>.

You may access the generator $x_i$ by typing <P>!.<i>. However, this
is only practicable if you are running an interactive job because you
have to know the value of <i>. Hence the proper way to access the new
generator is to write
`GeneratorsOfPresentation(P)[Length(GeneratorsOfPresentation(P))]'.



\beginexample
gap> G := PerfectGroup( 120 );;
gap> H := Subgroup( G, [ G.1^G.2, G.3 ] );;
gap> P := PresentationSubgroup( G, H );
<presentation with 4 gens and 7 rels of total length 21>
gap> AddGenerator( P );
#I  now the presentation has 5 generators, the new generator is _x7
gap> gens := GeneratorsOfPresentation( P );
[ _x1, _x2, _x4, _x5, _x7 ]
gap> gen := gens[Length( gens )];
_x7
gap> gen = P!.7;
true
\endexample

\>TzNewGenerator( <P> ) F

is an internal function which defines a new abstract generator and
adds it to the presentation <P>. It is called by `AddGenerator' and
by several Tietze transformation commands. As it does not know which
global lists have to be kept consistent, you should not call it.
Instead, you should call the function `AddGenerator', if needed.


\>AddRelator( <P>, <word> ) F

adds the relator <word> to the presentation <P>, probably changing the
group defined by <P>. <word> must be an abstract word in the generators
of <P>.


\>RemoveRelator( <P>, <n> ) F

removes the <n>-th relator from the presentation <P>, probably changing
the group defined by <P>.



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

The commands in this section can be used to modify a presentation 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.

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 \cite{Hav69} and its
later revisions (see \cite{HKRR84}, \cite{Rob88}).

\>TzGo( <P> [, <silent>] ) F

automatically performs suitable Tietze transformations of the given
presentation <P>. It is perhaps the most convenient one among 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.

If <silent> is specified as `true', the printing of the status line
by `TzGo' is suppressed if the Tietze option `printLevel' (see "Tietze
Options") has a value less than 2.


\>SimplifyPresentation( <P> ) F

is a synonym for `TzGo(<P>)'.



\beginexample
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> PrimaryGeneratorWords( P );
[ b, a*b*a ]
gap> TzOptions( P ).protected := 2;
2
gap> TzOptions( P ).printLevel := 2;
2
gap> SimplifyPresentation( P );
#I  eliminating _x7 = _x5^-1
#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 _x3 = _x2*_x1^-1
#I  there are 2 generators and 4 relators of total length 14
#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. _x1^2
#I  2. _x2^3
#I  3. _x2*_x1*_x2*_x1
\endexample

Roughly speaking, `TzGo' 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 `TzGo' succeeds in reducing the number of generators,
the number of relators, or the total length of all relators, 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 command
`TzSearchEqual' involved has changed the presentation such that another
call of `TzGo' 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 the command `TzGoGo' instead).

\>TzGoGo( <P> ) F

calls the command `TzGo' again and again until it does not reduce the
presentation any more.



The result of the Tietze transformations can be affected substantially by
the options parameters (see "Tietze Options"). 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 command `TzGoGo' for different
values of the parameter `eliminationsLimit'
(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 command `TzGoGo' again, i.e., they are
the best results which we can get without substituting new generators.

\beginexample
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> for i in [ 61, 62, 63, 90, 97 ] do
> Pi := PresentationSubgroup( G, H );
> TzOptions( Pi ).eliminationsLimit := i;
> Print("#I eliminationsLimit set to ",i,"\n");
> TzOptions( Pi ).printLevel := 0;
> TzGoGo( Pi );
> TzPrintStatus( Pi );
> od;
#I eliminationsLimit set to 61
#I  there are 2 generators and 104 relators of total length 7012
#I eliminationsLimit set to 62
#I  there are 2 generators and 7 relators of total length 56
#I eliminationsLimit set to 63
#I  there are 3 generators and 97 relators of total length 5998
#I eliminationsLimit set to 90
#I  there are 3 generators and 11 relators of total length 68
#I eliminationsLimit set to 97
#I  there are 4 generators and 109 relators of total length 3813
\endexample

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.

\beginexample
gap> for i in [ 7 .. 11 ] do
> Pi := PresentationSubgroup( G, H );
> TzOptions( Pi ).saveLimit := i;
> Print( "#I saveLimit set to ", i, "\n" );
> TzOptions( Pi ).printLevel := 0;
> TzGoGo( Pi );
> TzPrintStatus( Pi );
> od;
#I saveLimit set to 7
#I  there are 3 generators and 99 relators of total length 2713
#I saveLimit set to 8
#I  there are 2 generators and 103 relators of total length 11982
#I saveLimit set to 9
#I  there are 2 generators and 6 relators of total length 41
#I saveLimit set to 10
#I  there are 3 generators and 118 relators of total length 13713
#I saveLimit set to 11
#I  there are 3 generators and 11 relators of total length 58
\endexample

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

\>TzEliminate( <P> ) F
\>TzEliminate( <P>, <gen> ) F
\>TzEliminate( <P>, <n> ) F

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
`spaceLimit' (see "Tietze Options"). The default value of that parameter
is `infinity', but you may alter it appropriately.

If a generator <gen> has been specified, `TzEliminate' eliminates it if
possible, i. e. if there is a relator in which <gen> occurs just once.
If no second argument has been specified, `TzEliminate' eliminates some
appropriate generator if possible and if the resulting total length of
the relators will not exceed the parameter `lengthLimit'.

If an integer <n> has been specified, `TzEliminate' tries to eliminate
up to <n> generators. Note that the calls `TzEliminate(<P>)' and
`TzEliminate(<P>,1)' are equivalent.


\>TzSearch( <P> ) F

searches for relator subwords which, in some relator, have a complement
of shorter length and which occur in other relators, too, and uses them
to reduce these other relators.

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 in section "Tietze
Options" may strongly influence the performance and the results of the
command `TzSearch'. These are the parameters `saveLimit' and
`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 `saveLimit' per cent.

The default value of `saveLimit' is 10 per cent.

To understand the effect of the option `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
`searchSimultaneous' to prescribe an upper bound for the number of
short relators to be handled simultaneously.

The default value of `searchSimultaneous' is 20.

\>TzSearchEqual( <P> ) F

searches for Tietze relator subwords which, in some relator, have a
complement of equal length and which occur in other relators, too, and
uses them to modify these other relators.

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 `searchSimultaneous' is used by `TzSearchEqual'
in the same way as described for `TzSearch'. However, `TzSearchEqual' does
not use the parameter `saveLimit': The loop over the relators is executed
exactly once.

\>TzFindCyclicJoins( <P> ) F

searches for  power and commutator relators in order
to find  pairs of generators  which  generate a  common  cyclic subgroup.
It uses these pairs to introduce new relators,  but it does not introduce
any new generators as is done by `TzSubstituteCyclicJoins' (see
"TzSubstituteCyclicJoins").

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$.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Tietze Transformations that introduce new Generators}

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 there will be the need to substitute
certain words as new generators in order to improve a presentation.
Therefore {\GAP} offers the two commands `TzSubstitute' and
`TzSubstituteCyclicJoins' which introduce new generators.

\>TzSubstitute( <P>, <word> ) F
\>TzSubstitute( <P> [, <n> [, <eliminate> ] ] ) F

In the first form `TzSubstitute' expects <P> to be a presentation and
<word> to be either an abstract word or a Tietze word in the generators
of <P>. It substitutes the given word as a new generator of <P>. This is
done as follows: First, `TzSubstitute' creates a new abstract generator,
$g$ say, and adds it to the presentation, then it adds a new relator
$g^{-1}\cdot<word>$.

In its second form, `TzSubstitute' 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
below.

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
relator subwords of the form $g_1 g_2$, where $g_1$ and $g_2$ are
different generators or their inverses, and sorts them by decreasing
numbers of occurrences.

Let $a b$ be the last word in that list, and let <i> be the smallest
positive integer which has not yet been used as a generator number in
the presentation <P> so far. `TzSubstitute' defines a new abstract
generator $x_i$ named `"_x<i>"' and adds it to <P> (see `AddGenerator').
Then it adds the word $x_i^{-1} a b$ as a new relator to <P> and
replaces all occurrences of $a b$ in the relators by $x_i$. Finally,
it eliminates some suitable generator from <P>.

The choice of the generator to be eliminated depends on the actual
value of the parameter <eliminate>:

If <eliminate> is zero, `TzSubstitute' just calls the function
`TzEliminate'. So it may happen that it is the just introduced generator
$x_i$ which now is deleted again so that you don{\pif}t get any
remarkable progress in simplifying your presentation. On the first
glance this does not look reasonable, but it is a consequence of the
request that a call of `TzSubstitute' with <eliminate> = 0 must not
increase the total length of the relators.

Otherwise, if <eliminate> is 1 or 2, `TzSubstitute' eliminates the
respective factor of the substituted word $a b$, i. e., it eliminates
$a$ if <eliminate> = 1 or $b$ if <eliminate> = 2. In this case, it may
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.



There is still another property of the command `TzSubstitute' which should
be mentioned. If, for instance, `word' is an abstract word, a call

\begintt
TzSubstitute( P, word );
\endtt

is more or less equivalent to

\begintt
AddGenerator( P );
g := GeneratorsOfPresentation(P)[Length(GeneratorsOfPresentation(P))];
AddRelator( P, g^-1 * word );
\endtt

However, there is a difference: If you are tracing generator images and
preimages of <P> through the Tietze transformations applied to <P> (see
"Tracing generator images through Tietze transformations"), then
`TzSubstitute', as a Tietze transformation of <P>, will update and save the
respective lists, whereas a call of the function `AddGenerator' (which does
not perform a Tietze transformation) will delete these lists and hence
terminate the tracing.

\beginexample
gap> G := PerfectGroup( IsSubgroupFpGroup, 960, 1 );
A5 2^4
gap> P := PresentationFpGroup( G );
<presentation with 6 gens and 21 rels of total length 84>
gap> GeneratorsOfPresentation( P );
[ a, b, s, t, u, v ]
gap> TzGoGo( P );
#I  there are 3 generators and 10 relators of total length 81
#I  there are 3 generators and 10 relators of total length 80
gap> TzPrintGenerators( P );
#I  1.  a   31 occurrences   involution
#I  2.  b   26 occurrences
#I  3.  t   23 occurrences   involution
gap> a := GeneratorsOfPresentation( P )[1];;
gap> b := GeneratorsOfPresentation( P )[2];;
gap> TzSubstitute( P, a*b );
#I  now the presentation has 4 generators, the new generator is _x7
#I  substituting new generator _x7 defined by a*b
#I  there are 4 generators and 11 relators of total length 83
gap> TzGo( P );
#I  there are 3 generators and 10 relators of total length 74
gap> TzPrintGenerators( P );
#I  1.  a   23 occurrences   involution
#I  2.  t   23 occurrences   involution
#I  3.  _x7   28 occurrences
\endexample

As an example of an application of the command `TzSubstitute' in its second
form we handle a subgroup of index 266 in the Janko group $J_1$.

\beginexample
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 );
\endexample

Here we do not get any more progress without substituting a new generator.

\beginexample
gap> TzSubstitute( P );
#I  substituting new generator _x28 defined by _x6*_x23^-1
#I  eliminating _x28 = _x6*_x23^-1
\endexample

{\GAP} cannot substitute a new generator without extending the total length,
so we have to explicitly ask for it by using the second form of the command
`TzSubstitute'. Our problem is to chose appropriate values for the arguments
<n> and <eliminate>. For this purpose it may be helpful to print out a list
of the most frequently occurring squarefree relator subwords of length 2.

\beginexample
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
\endexample

If we save a copy of the current presentation, then later we will be able to
restart the computation from the current state.

\beginexample
gap> P1 := ShallowCopy( P );
<presentation with 2 gens and 10 rels of total length 101>
\endexample

Just for demonstration we make an inconvenient choice:

\beginexample
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
\endexample

This presentation is worse than the one we have saved, so we restart from
that presentation again.

\beginexample
gap> P := ShallowCopy( 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
\endexample

\>TzSubstituteCyclicJoins( <P> ) F

tries to find pairs of commuting generators $a$ and $b$, say, such that
the exponent of $a$ (i. e. the least currently known positive integer
$n$ such that $a^n$ is a relator in <P>) is prime to the exponent of
$b$. For each such pair, their product $a b$ is substituted as a new
generator, and $a$ and $b$ are eliminated.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Tracing generator images through Tietze transformations}

Any sequence of Tietze transformations applied to a presentation, starting
from some presentation $P_1$ and ending up with some presentation $P_2$,
defines an  isomorphism, $\varphi$ say, between the groups defined by $P_1$
and $P_2$, respectively. Sometimes it is desirable to know the images of the
(old) generators of $P_1$ or the preimages of the (new) generators of $P_2$
under $\varphi$. The {\GAP} Tietze transformation functions are able to trace
these images. This is not automatically done because the involved words may
grow to tremendous length, but it will be done if you  explicitly  request
for it by calling the function `TzInitGeneratorImages'.

\>TzInitGeneratorImages( <P> ) F

expects <P> to be a presentation. It defines the current generators to
be the ``old generators'' of <P> and initializes the (pre)image tracing.
See `TzImagesOldGens' and `TzPreImagesNewGens' for details.

You can reinitialize the tracing of the generator images at any later
state by just calling the function `TzInitGeneratorImages' again.

Note: A subsequent call of the function `DecodeTree' will imply that the
images and preimages are deleted and reinitialized after decoding the
tree.

Moreover, if you introduce a new generator by calling the function
`AddGenerator' described in section "Changing Presentations", this
new generator cannot be traced in the old generators. Therefore
`AddGenerator' will terminate the tracing of the generator images and
preimages and delete the respective lists whenever it is called.


\>OldGeneratorsOfPresentation( <P> ) F

assumes that <P> is a presentation for which the generator images
and preimages are being traced under Tietze transformations. It
returns the list of old generators of <P>.


\>TzImagesOldGens( <P> ) F

assumes that <P> is a presentation for which the generator images
and preimages are being traced under Tietze transformations. It
returns a list <l> of words in the (current) generators
`GeneratorsOfPresentation(<P>)' of <P> such that the <i>-th word
`<l>[<i>]' represents the <i>-th old generator
`OldGeneratorsOfPresentation(<P>)[<i>]' of <P>.


\>TzPreImagesNewGens( <P> ) F

assumes that <P> is a presentation for which the generator images
and preimages are being traced under Tietze transformations. It
returns a list <l> of words in the old generators
`OldGeneratorsOfPresentation(<P>)' of <P> such that the <i>-th word
`<l>[<i>]' represents the <i>-th (current) generator
`GeneratorsOfPresentation(<P>)[<i>]' of <P>.



\>TzPrintGeneratorImages( <P> ) F

assumes that <P> is a presentation for which the generator images
and preimages are being traced under Tietze transformations. It
displays the preimages of the current generators as Tietze words in
the old generators, and the images of the old generators as Tietze
words in the current generators.



\beginexample
gap> G := PerfectGroup( IsSubgroupFpGroup, 960, 1 );
A5 2^4
gap> P := PresentationFpGroup( G );
<presentation with 6 gens and 21 rels of total length 84>
gap> TzInitGeneratorImages( P );
gap> TzGo( P );
#I  there are 3 generators and 11 relators of total length 96
#I  there are 3 generators and 10 relators of total length 81
gap> TzPrintGeneratorImages( P );
#I  preimages of current generators as Tietze words in the old ones:
#I  1. [ 1 ]
#I  2. [ 2 ]
#I  3. [ 4 ]
#I  images of old generators as Tietze words in the current ones:
#I  1. [ 1 ]
#I  2. [ 2 ]
#I  3. [ 1, -2, 1, 3, 1, 2, 1 ]
#I  4. [ 3 ]
#I  5. [ -2, 1, 3, 1, 2 ]
#I  6. [ 1, 3, 1 ]
gap> gens := GeneratorsOfPresentation( P );
[ a, b, t ]
gap> oldgens := OldGeneratorsOfPresentation( P );
[ a, b, s, t, u, v ]
gap> TzImagesOldGens( P );
[ a, b, a*b^-1*a*t*a*b*a, t, b^-1*a*t*a*b, a*t*a ]
gap> for i in [ 1 .. Length( oldgens ) ] do
> Print( oldgens[i], " = ", TzImagesOldGens( P )[i], "\n" );
> od;
a = a
b = b
s = a*b^-1*a*t*a*b*a
t = t
u = b^-1*a*t*a*b
v = a*t*a
\endexample

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

\>DecodeTree( <P> ) F

assumes that <P> is a subgroup presentation provided by the Reduced
Reidemeister-Schreier or by the Modified Todd-Coxeter method (see
`PresentationSubgroupRrs', `PresentationNormalClosureRrs',
`PresentationSubgroupMtc' in section "Subgroup Presentations").
It eliminates the secondary generators of <P> (see "Subgroup
Presentations") by applying the so called ``decoding tree'' procedure.

`DecodeTree' is called automatically by the command
`PresentationSubgroupMtc' (see "PresentationSubgroupMtc") where it
reduces <P> to a presentation on the given (primary) 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 Reidemeister-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.

In fact, we could easily receive a presentation of <H> also in this case
if we extended $P_0$ 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 *decoding tree* procedure (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 terminates. 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 command `DecodeTree' and hence by
the command `PresentationSubgroupMtc'.

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 to further
simplify this presentation before you use it. The standard way to do
this is to start from $P_0$ and to apply suitable Tietze transformations,
e.g., by calling the commands `TzGo' or `TzGoGo'. 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 <P>.

Note, however, that the decoding tree 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 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.

\beginexample
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) ] );;
\endexample

We use the Reduced Reidemeister Schreier method and default Tietze
transformations to get a presentation for <H>.

\beginexample
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
\endexample

We end up with 20 relators of total length 466. Now we repeat the
procedure, but we call the decoding tree algorithm before doing the Tietze
transformations.

\beginexample
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
\endexample

This time we end up with a shorter presentation.

As an example of an implicit call of the function `DecodeTree' via the
command `PresentationSubgroupMtc' we handle a subgroup of index 240 in a
group of order 40320 given by a presentation due to B.~H.~Neumann. Note
that we increase the FpGroup info level to get some additional output.

\beginexample
gap> F3 := FreeGroup( "a", "b", "c" );;
gap> a := F3.1;;  b := F3.2;;  c := F3.3;;
gap> G := F3 / [ a^3, b^3, c^3, (a*b)^5, (a^-1*b)^5, (a*c)^4,
>     (a*c^-1)^4, a*b^-1*a*b*c^-1*a*c*a*c^-1, (b*c)^3, (b^-1*c)^4 ];;
gap> a := G.1;;  b := G.2;;  c := G.3;;
gap> H := Subgroup( G, [ a, c ] );;
gap> SetInfoLevel( InfoFpGroup, 1 );
gap> P := PresentationSubgroupMtc( G, H );;
#I  index = 240  total = 4737  max = 4507
#I  MTC defined 2 primary and 4444 secondary subgroup generators
#I  there are 246 generators and 617 relators of total length 2893
#I  calling DecodeTree
#I  there are 114 generators and 385 relators of total length 1860
#I  there are 69 generators and 294 relators of total length 1855
#I  there are 43 generators and 235 relators of total length 2031
#I  there are 35 generators and 207 relators of total length 2348
#I  there are 25 generators and 181 relators of total length 3055
#I  there are 19 generators and 165 relators of total length 3290
#I  there are 20 generators and 160 relators of total length 5151
#I  there are 23 generators and 159 relators of total length 8177
#I  there are 25 generators and 159 relators of total length 12241
#I  there are 29 generators and 159 relators of total length 18242
#I  there are 34 generators and 159 relators of total length 27364
#I  there are 38 generators and 159 relators of total length 41480
#I  there are 41 generators and 159 relators of total length 62732
#I  there are 45 generators and 159 relators of total length 88872
#I  there are 46 generators and 159 relators of total length 111092
#I  there are 44 generators and 155 relators of total length 158181
#I  there are 32 generators and 155 relators of total length 180478
#I  there are 7 generators and 133 relators of total length 29897
#I  there are 4 generators and 119 relators of total length 28805
#I  there are 3 generators and 116 relators of total length 35209
#I  there are 2 generators and 111 relators of total length 25658
#I  there are 2 generators and 111 relators of total length 22634
gap> TzGoGo( P );
#I  there are 2 generators and 108 relators of total length 11760
#I  there are 2 generators and 95 relators of total length 6482
#I  there are 2 generators and 38 relators of total length 1464
#I  there are 2 generators and 8 relators of total length 116
#I  there are 2 generators and 7 relators of total length 76
#I  there are 2 generators and 6 relators of total length 66
#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
gap> TzPrint( P );
#I  generators: [ _x1, _x2 ]
#I  relators:
#I  1.  3  [ 1, 1, 1 ]
#I  2.  3  [ 2, 2, 2 ]
#I  3.  8  [ 2, -1, 2, -1, 2, -1, 2, -1 ]
#I  4.  8  [ 2, 1, 2, 1, 2, 1, 2, 1 ]
#I  5.  14  [ -1, -2, 1, 2, 1, -2, -1, 2, 1, -2, -1, -2, 1, 2 ]
#I  6.  16  [ 1, 2, 1, -2, 1, 2, 1, -2, 1, 2, 1, -2, 1, 2, 1, -2 ]
gap> K :=  FpGroupPresentation( P );
<fp group on the generators [ _x1, _x2 ]>
gap> SetInfoLevel( InfoFpGroup, 0 );
gap> Size( K );
168
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Tietze Options}

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: Each presentation
keeps its own set of Tietze option parameters as an attribute.

\>TzOptions( <P> ) AM

is a record whose components direct the heuristics applied by the Tietze
transformation functions.

You may alter the value of any of these Tietze options by just assigning
a new value to the respective record component.



The following Tietze options are recognized by {\GAP}:

\beginitems
`protected':&
  The first `protected' generators in a presentation <P> are
  protected from being eliminated by the Tietze transformations
  functions.  There are only  two exceptions:  The option
  `protected'   is   ignored   by   the   functions
  `TzEliminate(<P>,<gen>)' and `TzSubstitute(<P>,<n>,<eliminate>)'
  because they explicitly specify the generator to be eliminated.
  The default value of `protected' is 0.

`eliminationsLimit':&
  Whenever the elimination phase of the `TzGo' command is entered
  for a presentation <P>,  then it  will eliminate at most
  `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 `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 - $`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 maximal {\GAP} list length of $2^{31}-1$ or the value
  of the option `lengthLimit'. The default value of `lengthLimit'
  is $2^{31}-1$.

`loopLimit':&
  Whenever the `TzGo' command is called for a presentation <P>,
  then it will loop over at most `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 `printLevel' $= 0$, they will not
  provide any output except for error messages. If `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 `printLevel' $= 2$, you
  will get a much more generous amount of output. Finally, if
  `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 `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
  `searchSimultaneous' 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.
\enditems

\>TzPrintOptions( <P> ) F

prints the current values of the Tietze options of the presentation <P>.



\beginexample
gap> TzPrintOptions( P );
#I  protected          = 0
#I  eliminationsLimit  = 100
#I  expandLimit        = 150
#I  generatorsLimit    = 0
#I  lengthLimit        = 2147483647
#I  loopLimit          = infinity
#I  printLevel         = 1
#I  saveLimit          = 10
#I  searchSimultaneous = 20
\endexample