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