45.3 Subgroup Presentations

is a synonym for PresentationSubgroupRrs(G,H[,string]).

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, ... , 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 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 the Reidemeister-Schreier algorithm of George Havas, it needs only the presentation of G and a coset table of H in G to construct a presentation of H.

Whenever you call the command PresentationSubgroupRrs, it first obtains a coset table of H in G if not given. Next, a set of generators of H is determined by reconstructing the coset table and introducing in that process as many Schreier generators of H in G as are needed to do a Felsch strategy coset enumeration without any coincidences. (In general, though containing redundant generators, this set will be much smaller than the set of all Schreier generators. That is why we call the method the Reduced Reidemeister-Schreier.)

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

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

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

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

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 ]

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, ... , the default string is "_x". You may access the i-th of these generators by P!.i.

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

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 Coset Tables and Coset Enumeration), but as the product of a coset representative by a group generator or its inverse need not be a coset representative itself, the Modified Todd-Coxeter has to store a kind of correction element for each coset table entry. Hence it builds up a so called augmented coset table of H in G consisting of the ordinary coset table and a second table in parallel which contains the associated subgroup elements.

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

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

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

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

To overcome this problem without extending the presentation by all secondary generators, the PresentationSubgroupMtc command applies the so called decoding tree algorithm which provides a more economical approach. The reader is strongly recommended to carefully read section DecodeTree where this algorithm is described in more detail. Here we will only mention that this procedure may add a lot of intermediate generators and relators (and even change the isomorphism type) in a process which in fact eliminates all secondary generators from the presentation and hence finally provides a presentation of H on the primary, i.e., the originally given, generators of H. This is a remarkable advantage of the command PresentationSubgroupMtc compared to the command PresentationSubgroupRrs. But note that, for some particular subgroup H, the Reduced Reidemeister-Schreier method might quite well produce a more concise presentation.

The resulting presentation is returned in the form of a presentation, P say.

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

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

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, ... , the default string is "_x". You may access the i-th of these generators by P!.i.

is a synonym for PresentationNormalClosureRrs(G,H[,string]).

[Top] [Previous] [Up] [Next] [Index]