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 48.5 to 48.8).
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 (47.11-1) already does what you want (see 47.12).
Most of the functions creating presentations and all functions performing Tietze transformations on them sort the relators by increasing lengths. The function PresentationFpGroup (48.1-1) is an exception because it is intended to reflect the relators that were used to define the involved f. p. group. You may use the command TzSort (48.1-2) to sort the presentation.
‣ PresentationFpGroup( G[, printlevel] ) | ( function ) |
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.
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>
‣ TzSort( P ) | ( function ) |
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 ) | ( function ) |
returns a list of free generators that is a shallow copy (see ShallowCopy (12.7-1)) of the current generators of the presentation P.
‣ FpGroupPresentation( P[, nam] ) | ( function ) |
constructs an f. p. group as defined by the given Tietze presentation P.
gap> h := FpGroupPresentation( p ); <fp group on the generators [ a, b ]> gap> h = g; false
‣ PresentationViaCosetTable( G[, F, words] ) | ( function ) |
constructs a presentation for a given concrete finite group. It applies the relations finding algorithm which has been described in [Can73] and [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 (47.11-1) in contrast uses a multiple-stage algorithm using a chief 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.
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)^6 #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)^2*f1^-2*f2
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.
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)^3, (a*b^-2)^3, a^11, a^2*b*a^-2*b^-1*(b^-1*a)^2*a*b^-1, (a*(b*a^-1)^2*b^-1)^2, a^2*b*a^2*b^-2*a^-1*b*(a^-1*b^-1)^2, (a*b)^2*a^2*b^-1*a^-1*b^-1*a*c*b*c, a^2*(a^2*b)^2*a^-2*c*a*b*a^-1*c ]
Before it is returned, the resulting presentation is being simplified by appropriate calls of the function SimplifyPresentation (48.6-2) (see 48.6), 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't care for the bijection, you may get a shorter presentation by calling the function SimplifyPresentation (48.6-2), now without this restriction, once more yourself.
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
If you apply the function FpGroupPresentation (48.1-4) to the resulting presentation you will get a finitely presented group isomorphic to G. Note, however, that the function IsomorphismFpGroup (47.11-1) is recommended for this purpose.
‣ SimplifiedFpGroup( G ) | ( function ) |
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 (47.12-1) should be used instead.
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)^2, G3^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 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 48.6).
‣ PresentationSubgroup( G, H[, string] ) | ( function ) |
PresentationSubgroup is a synonym for PresentationSubgroupRrs (48.2-2).
‣ PresentationSubgroupRrs( G, H[, string] ) | ( function ) |
‣ PresentationSubgroupRrs( G, table[, string] ) | ( function ) |
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 string1, string2, \(\ldots\), 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.
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
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.
gap> gens[1] = g1; false gap> g1; 60 gap> g1 := gens[1];; g2 := gens[2];; g3 := gens[3];; gap> g1; g1
The Reduced Reidemeister-Schreier algorithm is a modification of the Reidemeister-Schreier algorithm of George Havas [Hav74]. It was proposed by Joachim Neubüser and first implemented in 1986 by Andrea Lucchini and Volkmar Felsch in the SPAS system [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 48.6) or by the command DecodeTree (48.10-1) 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' 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 PresentationNormalClosureRrs (48.2-5)).
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 (48.2-3) of the resulting presentation.
‣ PrimaryGeneratorWords( P ) | ( attribute ) |
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.
gap> PrimaryGeneratorWords( p ); [ a, b^-1*a*b ]
‣ PresentationSubgroupMtc( G, H[, string][, print, level] ) | ( function ) |
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 string1, string2, \(\ldots\), 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 (48.10-1) will be suppressed.
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>
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 in [BC76]. It has been generalized to cover a broad spectrum of different versions (see the survey [Neu82]).
The Modified Todd-Coxeter method performs an enumeration of coset representatives. It proceeds like an ordinary coset enumeration (see 47.6), 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 (48.2-2) 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 48.10 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 (48.2-2). 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 (48.2-2) described above (see there for details), the function PresentationSubgroupMtc returns a list of the primary subgroup generators of H in the attribute PrimaryGeneratorWords (48.2-3) of \(P\). In fact, this list is not very exciting here because it is just a shallow copy of the value of GeneratorsOfPresentation (48.1-3) of 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 48.6).
‣ PresentationNormalClosureRrs( G, H[, string] ) | ( function ) |
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 string1, string2, \(\ldots\), the default string is "_x". You may access the \(i\)-th of these generators by \(P\)!.\(i\).
‣ PresentationNormalClosure( G, H[, string] ) | ( function ) |
PresentationNormalClosure is a synonym for PresentationNormalClosureRrs (48.2-5).
In order to speed up the Tietze transformation routines, each relator in a presentation 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 ) | ( operation ) |
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 (37.6-8).
‣ AbstractWordTietzeWord( word, fgens ) | ( function ) |
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 (37.6-9).
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
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. Note that there is also a function TzPrintOptions (48.11-2). It is described in Section 48.11.
‣ TzPrintGenerators( P[, list] ) | ( function ) |
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.
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
‣ TzPrintRelators( P[, list] ) | ( function ) |
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.
gap> TzPrintRelators( P ); #I 1. f3^2 #I 2. f2^4 #I 3. (f2^-1*f3)^2 #I 4. f1^5 #I 5. f1^2*f2*f1*f2^-1 #I 6. f1^-1*f3*f1*f3*f1^-1*f2^2*f3
‣ TzPrintLengths( P ) | ( function ) |
prints just a list of all relator lengths of the given presentation P.
gap> TzPrintLengths( P ); [ 2, 4, 4, 5, 5, 8 ]
‣ TzPrintStatus( P[, norepeat] ) | ( function ) |
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.
gap> TzPrintStatus( P ); #I there are 3 generators and 6 relators of total length 28
‣ TzPrintPresentation( P ) | ( function ) |
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 (48.4-1), TzPrintRelators (48.4-2), and TzPrintStatus (48.4-4), each with the presentation P as only argument.
‣ TzPrint( P[, list] ) | ( function ) |
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 (48.4-2) and TzPrintPresentation (48.4-5) do). The optional second argument can be used to specify the numbers of the relators to be printed. Default: all relators are printed.
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 ]
‣ TzPrintPairs( P[, n] ) | ( function ) |
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 (18.2-1).
The function TzPrintPairs is useful in the context of Tietze transformations which introduce new generators by substituting words in the current generators (see 48.8). It gives some evidence for an appropriate choice of a word of length 2 to be substituted.
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
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 ) | ( function ) |
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))].
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
‣ TzNewGenerator( P ) | ( function ) |
is an internal function which defines a new abstract generator and adds it to the presentation P. It is called by AddGenerator (48.5-1) 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 (48.5-1), if needed.
‣ AddRelator( P, word ) | ( function ) |
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 ) | ( function ) |
removes the n-th relator from the presentation P, probably changing the group defined by P.
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 [Hav69] and its later revisions (see [HKRR84], [Rob88]).
‣ TzGo( P[, silent] ) | ( function ) |
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 48.11) has a value less than \(2\).
‣ SimplifyPresentation( P ) | ( function ) |
SimplifyPresentation is a synonym for TzGo (48.6-1).
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)^2
Roughly speaking, TzGo (48.6-1) consists of a loop over a procedure which involves two phases: In the search phase it calls TzSearch (48.7-2) and TzSearchEqual (48.7-3) described below which try to reduce the relator lengths by substituting common subwords of relators, in the elimination phase it calls the command TzEliminate (48.7-1) described below (or, more precisely, a subroutine of TzEliminate (48.7-1) in order to save some administrative overhead) which tries to eliminate generators that can be expressed as words in the remaining generators.
If TzGo (48.6-1) 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 (48.7-3) involved has changed the presentation such that another call of TzGo (48.6-1) 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 (48.6-3) instead).
‣ TzGoGo( P ) | ( function ) |
calls the command TzGo (48.6-1) 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 48.11). 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.
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
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 [ 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
‣ TzEliminate( P[, gen] ) | ( function ) |
‣ TzEliminate( P[, n] ) | ( function ) |
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 48.11). The default value of that parameter is infinity (18.2-1), 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 Tietze options 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 ) | ( function ) |
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 \leq 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 48.11 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 ) | ( function ) |
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 \leq 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 (48.7-2). 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 (48.7-2). However, TzSearchEqual does not use the parameter saveLimit: The loop over the relators is executed exactly once.
‣ TzFindCyclicJoins( P ) | ( function ) |
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 (48.8-2).
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 Euclidean algorithm to express \(a\) as a power of \(b\), and then it eliminates \(a\).
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 (48.8-1) and TzSubstituteCyclicJoins (48.8-2) which introduce new generators.
‣ TzSubstitute( P, word ) | ( function ) |
‣ TzSubstitute( P[, n[, eliminate]] ) | ( function ) |
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 \textit{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 "_xi" and adds it to P (see AddGenerator (48.5-1)). 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 (48.7-1). So it may happen that it is the just introduced generator \(x_i\) which now is deleted again so that you don'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
TzSubstitute( P, word );
is more or less equivalent to
AddGenerator( P ); g := GeneratorsOfPresentation(P)[Length(GeneratorsOfPresentation(P))]; AddRelator( P, g^-1 * word );
However, there is a difference: If you are tracing generator images and preimages of P through the Tietze transformations applied to P (see 48.9), then TzSubstitute, as a Tietze transformation of P, will update and save the respective lists, whereas a call of the function AddGenerator (48.5-1) (which does not perform a Tietze transformation) will delete these lists and hence terminate the tracing.
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
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\).
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 );
Here we do not get any more progress without substituting a new generator.
gap> TzSubstitute( P ); #I substituting new generator _x28 defined by _x6*_x23^-1 #I eliminating _x28 = _x6*_x23^-1
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 choose 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.
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
If we save a copy of the current presentation, then later we will be able to restart the computation from the current state.
gap> P1 := ShallowCopy( P ); <presentation with 2 gens and 10 rels of total length 101>
Just for demonstration we 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
This presentation is worse than the one we have saved, so we restart from that presentation again.
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)^3 #I 4. _x31*(_x32*_x31^-1)^2*_x32*_x31*_x32^-2 #I 5. _x31^-1*_x32^2*(_x31*_x32^-1*_x31)^2*_x32^2
‣ TzSubstituteCyclicJoins( P ) | ( function ) |
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.
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 (48.9-1).
‣ TzInitGeneratorImages( P ) | ( function ) |
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 (48.9-3) and TzPreImagesNewGens (48.9-4) 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 (48.10-1) 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 (48.5-1) described in Section 48.5, this new generator cannot be traced in the old generators. Therefore AddGenerator (48.5-1) will terminate the tracing of the generator images and preimages and delete the respective lists whenever it is called.
‣ OldGeneratorsOfPresentation( P ) | ( function ) |
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 ) | ( function ) |
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) GeneratorsOfPresentation (48.1-3) value of P such that the \(i\)-th word \(l[i]\) represents the \(i\)-th old generator of P, i. e., the \(i\)-th entry of the OldGeneratorsOfPresentation (48.9-2) value of P.
‣ TzPreImagesNewGens( P ) | ( function ) |
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 of P (the OldGeneratorsOfPresentation (48.9-2) value of P) such that the \(i\)-th entry of \(l\) represents the \(i\)-th (current) generator of P (the GeneratorsOfPresentation (48.1-3) value of P).
‣ TzPrintGeneratorImages( P ) | ( function ) |
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.
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
‣ DecodeTree( P ) | ( function ) |
assumes that P is a subgroup presentation provided by the Reduced Reidemeister-Schreier or by the Modified Todd-Coxeter method (see PresentationSubgroupRrs (48.2-2), PresentationNormalClosureRrs (48.2-5), PresentationSubgroupMtc (48.2-4)). It eliminates the secondary generators of P (see Section 48.2) by applying the so called "decoding tree" procedure.
DecodeTree is called automatically by the command PresentationSubgroupMtc (48.2-4) where it reduces P to a presentation on the given (primary) 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 48.2. 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.
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 \(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 [AMW82], [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 (48.2-4).
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 (48.2-2) or PresentationNormalClosureRrs (48.2-5)) just returns \(P_0\).
As mentioned in section 48.2, 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 (48.6-1) or TzGoGo (48.6-3). 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 DecodeTree 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 48.11 apply to DecodeTree as well. Hence, in case of inadequate values of these parameters, it may happen that DecodeTree 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 DecodeTree 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 DecodeTree it is convenient to further simplify the resulting presentation by suitable Tietze transformations.
As an example of an explicit call of DecodeTree 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 (48.6-3) 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) ] );;
We use the Reduced Reidemeister Schreier method and default 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
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.
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
This time we end up with a shorter presentation.
As an example of an implicit call of the function DecodeTree via the command PresentationSubgroupMtc (48.2-4) 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 level of InfoFpGroup (47.1-3) temporarily to get some additional output.
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
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 ) | ( attribute ) |
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:
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 (48.7-1) and TzSubstitute (48.8-1) because they explicitly specify the generator to be eliminated. The default value of protected is 0.
eliminationsLimit:Whenever the elimination phase of the TzGo (48.6-1) 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 (48.6-1) command. Note, however, that it is ignored by the TzEliminate (48.7-1) 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 (48.7-1) command or the elimination phase of the TzGo (48.6-1) 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 (48.6-1) command. The default value of expandLimit is 150.
generatorsLimit:Whenever the elimination phase of the TzGo (48.6-1) 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 (48.6-1) 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 (48.6-1) 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 (48.6-1) command. The default value of loopLimit is infinity (18.2-1).
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 (48.7-2) 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 (48.7-2) repeats its procedure instead of returning. Hence you may use the saveLimit parameter as a break criterion for the TzSearch (48.7-2) command and, in particular, for the search phase of the TzGo (48.6-1) command. The default value of saveLimit is 10.
searchSimultaneous:Whenever the TzSearch (48.7-2) or the TzSearchEqual (48.7-3) command is called for a presentation P, then it is allowed to handle up to searchSimultaneous short relators simultaneously (see the description of the TzSearch (48.7-2) command for more details). The choice of this parameter may heavily influence the performance as well as the result of the TzSearch (48.7-2) and the TzSearchEqual (48.7-3) commands and hence also of the search phase of the TzGo (48.6-1) command. The default value of searchSimultaneous is 20.
‣ TzPrintOptions( P ) | ( function ) |
prints the current values of the Tietze options of the presentation P.
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
generated by GAPDoc2HTML