23.11 Subgroup Presentations

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 Neubaccent127user 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 Rei-de-mei-ster-Schreier method (as well as Havas' original Reidemeister-Schreier program) has the advantage that it does not require generators of H to be given if a coset table of H in G is known. This provides a possibility to compute a presentation of the normal closure of a given subgroup (see the PresentationNormalClosureRrs command below).

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 Tietze Transformations).

An example is given in section DecodeTree.

PresentationSubgroup( G, H ) PresentationSubgroup( G, H, string )
PresentationSubgroup( G, cosettable )
PresentationSubgroup( G, cosettable, string )

Presentation Records) containing a presentation for the subgroup H of the finitely presented group G.

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

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

A few examples are given in section Tietze Transformations.

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, GAP offers different methods for the construction of normal closure presentations, then PresentationNormalClosure will call one of these procedures as a kind of default method. At present, however, the Reduced Reidemeister-Schreier algorithm is the only one implemented so far. Therefore, at present the PresentationNormalClosure command is identical with the PresentationNormalClosureRrs command described above.

Previous Up Top Next
Index

GAP 3.4.4
April 1997