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 ab = 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).
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
23.2 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 GAP3 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.
The size is simply the degree of the regular representation of G.
A word w lies in a parent group G if all its letters are among the generators of G.
w in H
To test whether a word w lies in a subgroup H of a finitely presented group G, GAP3 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.
The elements of a finitely presented group are computed by computing the regular representation of G. Then for each point p GAP3 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.
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.
The intersection of two subgroups H1 and H2 of a finitely presented group G is computed as follows. First GAP3 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 GAP3 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.
23.3 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 GAP3 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.
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).
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.
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.
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.
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).
AbelianInvariantsSubgroupFpGroup( G, H )
AbelianInvariantsSubgroupFpGroup( G, cosettable )
This function is equivalent to AbelianInvariantsSubgroupFpGroupRrs
below, but note that there is an alternative function,
AbelianInvariantsSubgroupFpGroupMtc.
AbelianInvariantsSubgroupFpGroupRrs( G, H )
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.
AbelianInvariantsSubgroupFpGroupMtc( G, H )
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).
AbelianInvariantsNormalClosureFpGroup( G, H )
This function is equivalent to AbelianInvariantsNormalClosureFpGroupRrs
below.
AbelianInvariantsNormalClosureFpGroupRrs( G, H )
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 );
[ 0, 0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2 ]
The prededing calculation for B1 and a similar one for B0 have been used to prove that B1' / B1′ ′ ≅ Z29 × Z3 and B0' / B0′ ′ ≅ Z291 × Z27 as stated in Proposition 5 in FJNT95.
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 )
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.
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).
23.6 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
LowIndexSubgroupsFpGroup( G, H, index )
LowIndexSubgroupsFpGroup( G, H, index, excluded )
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.
The function provides some intermediate output if InfoFpGroup2 has been
set to Print (its default value is Ignore).
If the optional argument excluded has been specified, then it is
expected to be a list of words in the generators of G, and
LowIndexSubgroupsFpGroup returns only those subgroups of index at most
index that contain H, but do not contain any conjugate of any of the
group elements defined by these words.
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
As an example for an application of the optional parameter excluded, we compute all conjugacy classes of torsion free subgroups of index at most 24 in the group G = ⟨ x,y,z | x2, y4, z3, (xy)3, (yz)2, (xz)3 ⟩. It is know from theory that each torsion element of this group is conjugate to a power of x, y, z, xy, xz, or yz.
gap> G := FreeGroup( "x", "y", "z" );
Group( x, y, z )
gap> x := G.1;; y := G.2;; z := G.3;;
gap> G.relators := [ x^2, y^4, z^3, (x*y)^3, (y*z)^2, (x*z)^3 ];;
gap> torsion := [ x, y, y^2, z, x*y, x*z, y*z ];;
gap> InfoFpGroup2 := Print;;
gap> lis :=
> LowIndexSubgroupsFpGroup( G, TrivialSubgroup( G ), 24, torsion );;
#I class 1 of index 24 and length 8
#I class 2 of index 24 and length 24
#I class 3 of index 24 and length 24
#I class 4 of index 24 and length 24
#I class 5 of index 24 and length 24
gap> InfoFpGroup2 := Ignore;;
gap> lis;
[ Subgroup( Group( x, y, z ),
[ x*y*z^-1, z*x*z^-1*y^-1, x*z*x*y^-1*z^-1, y*x*z*y^-1*z^-1 ] ),
Subgroup( Group( x, y, z ),
[ x*y*z^-1, z^2*x^-1*y^-1, x*z*y*x^-1*z^-1 ] ),
Subgroup( Group( x, y, z ),
[ x*y*z^-1, x*z^2*x^-1*y^-1, y^2*x*y^-1*z^-1*x^-1 ] ),
Subgroup( Group( x, y, z ), [ x*y*z^-1, y^3*x^-1*z^-1*x^-1,
y^2*z*x^-1*y^-1 ] ),
Subgroup( Group( x, y, z ), [ y*x*z^-1, x*y*z*y^-1*z^-1,
y^2*z*x^-1*z^-1*x^-1 ] ) ]
The function LowIndexSubgroupsFpGroup finds the requested subgroups by
systematically running through a tree of all potential coset tables of
G of length at most index (where it skips all branches of that tree
for which it knows in advance that they cannot provide new classes of
such subgroups). The time required to do this depends, of course, on the
presentation of G, but in general it will grow exponentially with the
value of index. So you should be careful with the choice of index.
In GAP3, finitely presented groups are distinguished from group presentations which are GAP3 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 GAP3 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.
GAP3 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 (abstract) GAP3 words, but by lists of positive or negative generator numbers which we call Tietze words.
The term ``Tietze record'' will sometimes be used as an alias for ``presentation record''. It occurs, in particular, in certain error messages.
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.
PresentationFpGroup( G )
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.
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,
GAP3 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.
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;
TzPrintGenerators( P )
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.
TzPrintRelators( P )
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 as Tietze words 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.
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 );
TzPrint( P )
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 GAP3 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 GAP3
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 four more print commands for presentation records which are convenient in the context of the interactive Tietze transformation commands:
TzPrintGeneratorImages( P )
TzPrintLengths( P )
TzPrintPairs( P )
TzPrintPairs( P, n )
TzPrintOptions( P )
Moreover, there are two functions which allow to convert abstract words to Tietze words or Tietze words to abstract words.
TietzeWordAbstractWord( word, generators )
Let generators be a list of abstract generators and word an abstract
word in these generators. The function TietzeWordAbstractWord returns
the corresponding (reduced) Tietze word.
gap> F := FreeGroup( "a", "b", "c" );
Group( a, b, c )
gap> tzword := TietzeWordAbstractWord(
> Comm(F.1,F.2) * (F.3^2 * F.2)^-1, F.generators );
[ -1, -2, 1, -3, -3 ]
AbstractWordTietzeWord( word, generators )
Let generators be a list of abstract generators and word a Tietze
word in these generators. The function AbstractWordTietzeWord returns
the corresponding abstract word.
gap> AbstractWordTietzeWord( tzword, F.generators );
a^-1*b^-1*a*c^-2
The function Save allows to save a presentation and to recover it in a
later GAP3 session.
Let P be a presentation, and let file and name be strings denoting
a file name and a variable name, respectively. The function Save
generates a new file file and writes P and name to that file in
such a way that a copy of P can be reestablished by just reading the
file with the function Read. This copy of P will be assigned to a
variable called name.
Warning: It is not guaranteed that the functions Save and Read
work properly if the presentation record P contains additional, user
defined components. For instance, components involving abstract words
cannot be read in again as soon as the associated generators are not
available any more.
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 >>
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 Tietze
transformations commands like TzSubstitute (see Tietze
Transformations), they do not perform Tietze transformations
themselves.
AddGenerator( P )
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 _xi 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 _xi, 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 \_xi above.
AddRelator adds the word word to the list of relators. word must
be a word in the generators of the given presentation.
RemoveRelator removes the nth relator and then resorts the list of
relators in the given presentation record P.
In section Presentation Records we have described the funtion
PresentationFpGroup which supplies a presentation record for a finitely
presented group. The following function can be used to compute a
presentation record for a concrete (e.g. permutation or matrix) group.
PresentationViaCosetTable( G )
PresentationViaCosetTable( G, F, words )
PresentationViaCosetTable constructs a presentation record for the
given group G. The method being used is John Cannon's relations
finding algorithm which has been described in Can73 or in
Neu82.
In its first form, if only the group G has been specified, it applies Cannon's single stage algorithm which, by plain element multiplication, computes a coset table of G with respect to its trivial subgroup and then uses coset enumeration methods to find a defining set of relators for G.
gap> G := GeneralLinearGroup( 2, 7 );
GL(2,7)
gap> G.generators;
[ [ [ 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. f.2^3
#I 2. f.1^6
#I 3. f.1*f.2*f.1*f.2*f.1*f.2*f.1*f.2*f.1*f.2*f.1*f.2
#I 4. f.1*f.2*f.1^-1*f.2*f.1*f.2^-1*f.1^-1*f.2*f.1*f.2*f.1^-1*f.2^-1
#I 5. f.1^2*f.2*f.1*f.2*f.1*f.2^-1*f.1^-1*f.2^-1*f.1^3*f.2^-1
The second form allows to call Cannon's two stage algorithm which first applies the single stage algorithm to an appropriate subgroup H of G and then uses the resulting relators of H and a coset table of G with respect to H to find relators of G. In this case the second argument, F, is assumed to be a free group with the same number of generators as G, and words is expected to be a list of words in the generators of F which, when being evaluated in the corresponding generators of G, provide subgroup generators for H.
gap> M12 := MathieuGroup( 12 );;
gap> M12.generators;
[ ( 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" );
Group( 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 );
Group( a, b, c )
gap> G.relators;
[ 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^2*b^-1*a^-1*b^-1*a*c*b*c*a*b*a*b, a^3*b*a^2*b*a^-2*c*a*b*a^-1*c*a
]
Before it is returned, the resulting presentation is being simplified by
appropriate calls of the function SimplifyPresentation (see Tietze
Transformations), but without allowing it to eliminate any
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't care for the bijection, it may be convenient to apply the function
SimplifyPresentation again.
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
PresentationSubgroupRrs( G, H )
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.
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
string1, string2, ..., the default string is "_x".
The Reduced Reidemeister-Schreier algorithm is a modification of the Reidemeister-Schreier algorithm of George Havas Hav74b. It was proposed by Joachim Neubüser and first implemented in 1986 by Andrea Lucchini and Volkmar Felsch in the SPAS system 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, it is 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.
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, P say.
Compared with the Modified Todd-Coxeter method described below, the
Reduced Reidemeister-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).
As you may be interested not only to get the resulting presentation, but
also to know what the involved subgroup generators are, the function
PresentationSubgroupRrs will also return a list of the primary
generators of H as words in the generators of G. It is provided in
form of an additional component P.primaryGeneratorWords of the
resulting presentation record P.
Note however: As stated in the description of the function Save (see
Presentation Records), the function Read cannot properly recover a
component involving abstract generators different from the current
generators when it reads a presentation which has been written to a file
by the function Save. Therefore the function Save will ignore the
component P.primaryGeneratorWords if you call it to write the
presentation P to a file. Hence this component will be lost if you read
the presentation back from that file, and it will be left to your own
responsibility to remember what the primary generators have been.
A few examples are given in section Tietze Transformations.
PresentationSubgroupMtc( G, H )
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.
The generators in the resulting presentation will be named by
string1, string2, ..., 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 BC76). Another proof for a special version was given by D. H. McLain (see McL77). It was generalized to cover a broad spectrum of different versions (see the survey Neu82). Moser's method was implemented by Harvey A. Campbell (see Cam71. Later, a Modified Todd-Coxeter program was implemented in St. Andrews by David G. Arrell, Sanjiv Manrai, and Michael F. Worboys (see AMW82) and further developed by David G. Arrel and Edmund F. Robertson (see AR84) and by Volkmar Felsch in the SPAS system 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.
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 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, P say.
As the function PresentationSubgroupRrs desribed above (see there for
details), the function PresentationSubgroupMtc returns a list of the
primary subgroup generators of H in form of a component
P.primaryGeneratorWords. In fact, this list is not very exciting here
because it is just a copy of the list H.generators, however it is
needed to guarantee a certain consistency between the results of the
different functions for computing subgroup presentations.
Though the tree decoding 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).
An example is given in section DecodeTree.
PresentationSubgroup( G, H )
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 GAP3 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 GAP3 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.
PresentationNormalClosureRrs( G, H )
PresentationNormalClosureRrs( G, H, string )
PresentationNormalClosureRrs returns a presentation record (see
Presentation Records), P say, 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
string1, string2, ..., 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.
As the function PresentationSubgroupRrs desribed above (see there for
details), the function PresentationNormalClosureRrs returns a list of
the primary subgroup generators of N in form of a component
P.primaryGeneratorWords.
PresentationNormalClosure( G, H )
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, GAP3 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.
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).
The GAP3 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.
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 GAP3 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 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 HKRR84, Rob88).
\vspace5mm 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
GAP3 offers the two commands TzSubstitute and
TzSubstituteCyclicJoins which introduce new generators. These commands
will be described next.
Then we continue the section with a description of the commands
TzInitGeneratorImages and TzPrintGeneratorImages which can be used to
determine and to display the images or preimages of the involved
generators under the isomorphism which is defined by the sequence of
Tietze transformations which are applied to a presentation.
Subsequently we describe some further print commands, TzPrintLengths,
TzPrintPairs, and TzPrintOptions, which are useful if you run the
Tietze transformations interactively.
At the end of the 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.
SimplifyPresentation( P )
TzGo( P )
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.primaryGeneratorWords;
[ b, a*b*a ]
gap> P.protected := 2;;
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 _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
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 GAP3 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.
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.
TzEliminate( P )
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.
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 r1 and r2 of length l1 and l2, respectively, such that l1 ≤ l2 and r1 and r2 coincide (possibly after inverting or conjugating one of them) in some maximal subword w, say, of length greater than l1/2, and then to substitute each copy of w in r2 by the inverse complement of w in r1.
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 r1, and a subroutine is called which loops over the succeeding relators, treating them as long relators r2 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 GAP3 kernel. For the given relator r1 of length l1, say, it first determines the minimal match length l which is l1/2+1, if l1 is even, or (l1+1)/2, otherwise. Then it builds up a hash list for all subwords of length l occurring in the conjugates of r1 or r1-1, and finally it loops over all long relators r2 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 r2, 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.
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 r1 and r2 of length l1 and
l2, respectively, such that l1 is even, l1 ≤ l2, and r1
and r2 coincide (possibly after inverting or conjugating one of them)
in some maximal subword w, say, of length at least l1/2. Let l be
the length of w. Then, if l > l1/2, the pair is handled as in
TzSearch. Otherwise, if l = l1/2, then TzSearchEqual substitutes
each copy of w in r2 by the inverse complement of w in r1.
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.
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
an, and a product of the form as bt 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.
TzSubstitute( P, word )
TzSubstitute( P, word, string )
There are two forms of the command TzSubstitute. This is the first one.
It 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 P, then it adds a new relator g-1 \! .
\! word to P. If a string string has been specified as third
argument, the new generator g will be named by string, otherwise it
will get a default name _xi as described with the function
AddGenerator (see Changing Presentations).
More precisely: If, for instance, word is an abstract word, a call
TzSubstitute( P, word );
is more or less equivalent to
AddGenerator( P );
g := P.generators[Length( P.generators )];
AddRelator( P, g^-1 * word );
whereas a call
TzSubstitute( P, word, string );
is more or less equivalent to
g := AbstractGenerator( string );
AddGenerator( P, g );
AddRelator( P, g^-1 * word );
The essential difference is, that TzSubstitute, as a Tietze
transformation of P, saves and updates the lists of generator images
and preimages if they are being traced under the Tietze transformations
applied to P (see the function TzInitGeneratorImages below), whereas
a call of the function AddGenerator (which does not perform Tietze
transformations) will delete these lists and hence terminate the tracing.
Example.
gap> G := PerfectGroup( 960, 1 );
PerfectGroup(960,1)
gap> P := PresentationFpGroup( G );
<< presentation with 6 gens and 21 rels of total length 84 >>
gap> P.generators;
[ 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 := P.generators[1];;
gap> b := P.generators[2];;
gap> TzSubstitute( P, a*b, "ab" );
#I substituting new generator ab 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. ab 28 occurrences
TzSubstitute( P )
TzSubstitute( P, n )
TzSubstitute( P, n, eliminate )
This is the second form of the command TzSubstitute.
It performs Tietze transformations on the 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 nth 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-1ab, 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 J1.
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
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 GAP3 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.
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 am and bn
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.
Any sequence of Tietze transformations applied to a presentation record
P, starting from an ``old'' presentation P1 and ending up with a
``new'' presentation P2, defines an isomorphism, φ say,
between the groups defined by P1 and P2, respectively. Sometimes
it is desirable to know the images of the old generators or the preimages
of the new generators under φ. The GAP3 Tietze transformations
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 initializes three components of P:
P.oldGenerators:P.generators.
P.imagesOldGens:[i].
P.preImagesNewGens:[i].
This means, that P1 is defined to be the current presentation and
φ to be the identity on P1. From now on, the existence of the
component P.imagesOldGens will cause the Tietze transformations
functions to update the lists of images and preimages whenever they are
called.
You can reinitialize the tracing of the generator images at any later
state by just calling the function TzInitGeneratorImages again. For, if
the above components do already exist when TzInitGeneratorImages is
being called, they will first be deleted and then initialized again.
There are a few restrictions concerning the tracing of generator images:
In general, the functions AddGenerator, AddRelator, and
RemoveRelator described in section Changing Presentations do not
perform Tietze transformations as they may change the isomorphism type of
the presentation. Therefore, if any of them is called for a presentation
in which generator images and preimages are being traced, it will delete
these lists.
If the function DecodeTree is called for a presentation in which
generator images and preimages are being traced, it will not continue to
trace them. Instead, it will delete the corresponding lists, then decode
the tree, and finally reinitialize the tracing for the resulting
presentation.
As stated in the description of the function Save (see Presentation
Records), the function Read cannot properly recover a component
involving abstract generators different from the current generators when
it reads a presentation which has been written to a file by the function
Save. Therefore the function Save will ignore the component
P.oldGenerators if you call it to write the presentation P to a
file. Hence this component will be lost if you read the presentation back
from that file, and it will be left to your own responsibility to
remember what the old generators have been.
If P is a presentation in which generator images and preimages are
being traced through all Tietze transformations applied to P,
TzPrintGeneratorImages prints 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.
gap> G := PerfectGroup( 960, 1 );
PerfectGroup(960,1)
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> # Print the old generators as words in the new generators.
gap> gens := P.generators;
[ a, b, t ]
gap> oldgens := P.oldGenerators;
[ a, b, s, t, u, v ]
gap> for i in [ 1 .. Length( oldgens ) ] do
> Print( oldgens[i], " = ",
> AbstractWordTietzeWord( P.imagesOldGens[i], gens ), "\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
TzPrintLengths prints the list of the lengths of all relators of the
given presentation P.
TzPrintPairs( P )
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.
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.
TzPrintOptions prints the Tietze option components of the specified
presentation P.
The Tietze options have the following meaning.
protected:P.protected generators in a presentation P are
protected from being eliminated by the Tietze transformations
functions. There are only two exceptions: The option
P.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: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: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: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:P.lengthLimit. The default value of
lengthLimit is infinity.
loopLimit: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: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: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: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.
\vspace5mm 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
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.
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 P0, 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.
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.
Now we have to distinguish two cases. If P0 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 P0 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 P0 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. Worboys (see AMW82, AR84). It proceeds as follows.
Starting from P = P0, 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 = P1,
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 P0 has been constructed by the
Reduced Reidemeister-Schreier algorithm, then P0 itself is a
presentation of H, and the corresponding subgroup presentation command
(PresentationSubgroupRrs or PresentationNormalClosureRrs) just
returns P0.
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 P0 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, GAP3 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, GAP3 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 GAP3
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> 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> InfoFpGroup1 := Print;;
gap> P := PresentationSubgroupMtc( G, H );;
#I index = 240 total = 4737 max = 4507
#I MTC defined 2 primary and 4446 secondary subgroup generators
#I there are 246 generators and 617 relators of total length 2893
#I calling DecodeTree
#I there are 115 generators and 382 relators of total length 1837
#I there are 69 generators and 298 relators of total length 1785
#I there are 44 generators and 238 relators of total length 1767
#I there are 35 generators and 201 relators of total length 2030
#I there are 26 generators and 177 relators of total length 2084
#I there are 23 generators and 167 relators of total length 2665
#I there are 20 generators and 158 relators of total length 2848
#I there are 20 generators and 148 relators of total length 3609
#I there are 21 generators and 148 relators of total length 5170
#I there are 24 generators and 148 relators of total length 7545
#I there are 27 generators and 146 relators of total length 11477
#I there are 32 generators and 146 relators of total length 18567
#I there are 36 generators and 146 relators of total length 25440
#I there are 39 generators and 146 relators of total length 38070
#I there are 43 generators and 146 relators of total length 54000
#I there are 41 generators and 143 relators of total length 64970
#I there are 8 generators and 129 relators of total length 20031
#I there are 7 generators and 125 relators of total length 27614
#I there are 4 generators and 113 relators of total length 36647
#I there are 3 generators and 108 relators of total length 44128
#I there are 2 generators and 103 relators of total length 35394
#I there are 2 generators and 102 relators of total length 34380
gap> TzGoGo( P );
#I there are 2 generators and 101 relators of total length 19076
#I there are 2 generators and 84 relators of total length 6552
#I there are 2 generators and 38 relators of total length 1344
#I there are 2 generators and 9 relators of total length 94
#I there are 2 generators and 8 relators of total length 86
gap> TzPrintGenerators( P );
#I 1. _x1 43 occurrences
#I 2. _x2 43 occurrences
gap3-jm