DecodeTree( P )
DecodeTree eliminates the secondary generators from a presentation P
constructed by the Modified Todd-Coxeter (see PresentationSubgroupMtc)
or the Reduced Reidemeister-Schreier procedure (see
PresentationSubgroupRrs, PresentationNormalClosureRrs). It is called
automatically by the PresentationSubgroupMtc command where it reduces
P to a presentation on the given subgroup generators.
In order to explain the effect of this command we need to insert a few remarks on the subgroup presentation commands described in section Subgroup Presentations. All these commands have the common property that in the process of constructing a presentation for a given subgroup H of a finitely presented group G they first build up a highly redundant list of generators of H which consists of an (in general small) list of ``primary'' generators, followed by an (in general large) list of ``secondary'' generators, and then construct a presentation 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 Rei-de-mei-ster-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.
Also in the case of the Modified Todd-Coxeter method, we could easily extend P_0 to a presentation of H by adding to it all the secondary generators which are not yet contained in it and all the definitions from the generators tree as additional generators and relators. Then we could recursively eliminate all secondary generators by Tietze transformations using the new relators. However, this procedure turns out to be too inefficient to be of interest.
Instead, we use the so called tree decoding procedure which has been developed in St.~Andrews by David G.~Arrell, Sanjiv Manrai, Edmund F.~Robertson, and Michael F.~Wor-boys (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 finishes. Otherwise it checks whether there is a relator in the current presentation which can be used to substitute g by a Tietze transformation. If so, this is done. Otherwise, and only then, the tree definition of g is added to P as a new relator, and the generators involved are added as new generators if they have not yet been contained in P. Subsequently, g is eliminated.
Note that the extension of P by one or two new generators is not a
Tietze transformation. In general, it will change the isomorphism type
of the group defined by P. However, it is a remarkable property of
this procedure, that at the end, i.e., as soon as all secondary
generators have been eliminated, it provides a presentation P = P_1,
say, which defines a group isomorphic to H. In fact, it is this
presentation which is returned by the DecodeTree command and hence by
the PresentationSubgroupMtc command.
If, in the other case, the presentation 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 or PresentationNormalClosureRrs) just
returns P_0.
As mentioned in section Subgroup Presentations, we recommend further
simplifying this presentation before using it. The standard way to do
this is to start from P_0 and to apply suitable Tietze transformations,
e.g., by calling the TzGo or TzGoGo commands. This is probably the
most efficient approach, but you will end up with a presentation on some
unpredictable set of generators. As an alternative, 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 record P.
Note, however, that the tree decoding routines will not work correctly
any more on a presentation from which generators have already been
eliminated by Tietze transformations. Therefore, to prevent you from
getting wrong results by calling the DecodeTree command in such a
situation, GAP will automatically remove the subgroup generators tree
from a presentation record as soon as one of the generators is
substituted by a Tietze transformation.
Nevertheless, a certain misuse of the command is still possible, and we
want to explicitly warn you from this. The reason is that the Tietze
option parameters described in section Tietze Transformations apply to
the DecodeTree command as well. Hence, in case of inadequate values of
these parameters, it may happen that the DecodeTree routine stops
before all the secondary generators have vanished. In this case GAP
will display an appropriate warning. Then you should change the
respective parameters and continue the process by calling the
DecodeTree command again. Otherwise, if you would apply Tietze
transformations, it might happen because of the convention described
above that the tree is removed and that you end up with a wrong
presentation.
After a successful run of the DecodeTree command it is convenient to
further simplify the resulting presentation by suitable Tietze
transformations.
As an example of an explicit call of the DecodeTree command we compute
two presentations of a subgroup of order 384 in a group of order
6912. In both cases we use the Reduced Reidemeister-Schreier
algorithm, but in the first run we just apply the Tietze transformations
offered by the TzGoGo command with its default parameters, whereas in
the second run we call the DecodeTree command before.
gap> F2 := FreeGroup( "a", "b" );;
gap> G := F2 / [ F2.1*F2.2^2*F2.1^-1*F2.2^-1*F2.1^3*F2.2^-1,
> F2.2*F2.1^2*F2.2^-1*F2.1^-1*F2.2^3*F2.1^-1 ];;
gap> a := G.1;; b := G.2;;
gap> H := Subgroup( G, [ Comm(a^-1,b^-1), Comm(a^-1,b), Comm(a,b) ] );;
gap> #
gap> # We use the Reduced Reidemeister Schreier method and default
gap> # Tietze transformations to get a presentation for H.
gap> P := PresentationSubgroupRrs( G, H );
<< presentation with 18 gens and 35 rels of total length 169 >>
gap> TzGoGo( P );
#I there are 3 generators and 20 relators of total length 488
#I there are 3 generators and 20 relators of total length 466
gap> # We end up with 20 relators of total length 466.
gap> #
gap> # Now we repeat the procedure, but we call the tree decoding
gap> # algorithm before doing the Tietze transformations.
gap> P := PresentationSubgroupRrs( G, H );
<< presentation with 18 gens and 35 rels of total length 169 >>
gap> DecodeTree( P );
#I there are 9 generators and 26 relators of total length 185
#I there are 6 generators and 23 relators of total length 213
#I there are 3 generators and 20 relators of total length 252
#I there are 3 generators and 20 relators of total length 244
gap> TzGoGo( P );
#I there are 3 generators and 19 relators of total length 168
#I there are 3 generators and 17 relators of total length 138
#I there are 3 generators and 15 relators of total length 114
#I there are 3 generators and 13 relators of total length 96
#I there are 3 generators and 12 relators of total length 84
gap> # This time we end up with a shorter presentation.
As an example of an implicit call of the command via the
PresentationSubgroupMtc command we handle a subgroup of index 240 in a
group of order 40320 given by a presentation due to B.~H.~Neumann.
gap> F3 := FreeGroup( "a", "b", "c" );;
gap> a := F3.1;; b := F3.2;; c := F3.3;;
gap> G := F3 / [ a^3, b^3, c^3, (a*b)^5, (a^-1*b)^5, (a*c)^4,
> (a*c^-1)^4, a*b^-1*a*b*c^-1*a*c*a*c^-1, (b*c)^3, (b^-1*c)^4 ];;
gap> a := G.1;; b := G.2;; c := G.3;;
gap> H := Subgroup( G, [ a, c ] );;
gap> InfoFpGroup1 := Print;;
gap> P := PresentationSubgroupMtc( G, H );;
#I index = 240 total = 4737 max = 4507
#I MTC defined 2 primary and 4446 secondary subgroup generators
#I there are 246 generators and 617 relators of total length 2893
#I calling DecodeTree
#I there are 115 generators and 382 relators of total length 1837
#I there are 69 generators and 298 relators of total length 1785
#I there are 44 generators and 238 relators of total length 1767
#I there are 35 generators and 201 relators of total length 2030
#I there are 26 generators and 177 relators of total length 2084
#I there are 23 generators and 167 relators of total length 2665
#I there are 20 generators and 158 relators of total length 2848
#I there are 20 generators and 148 relators of total length 3609
#I there are 21 generators and 148 relators of total length 5170
#I there are 24 generators and 148 relators of total length 7545
#I there are 27 generators and 146 relators of total length 11477
#I there are 32 generators and 146 relators of total length 18567
#I there are 36 generators and 146 relators of total length 25440
#I there are 39 generators and 146 relators of total length 38070
#I there are 43 generators and 146 relators of total length 54000
#I there are 41 generators and 143 relators of total length 64970
#I there are 8 generators and 129 relators of total length 20031
#I there are 7 generators and 125 relators of total length 27614
#I there are 4 generators and 113 relators of total length 36647
#I there are 3 generators and 108 relators of total length 44128
#I there are 2 generators and 103 relators of total length 35394
#I there are 2 generators and 102 relators of total length 34380
gap> TzGoGo( P );
#I there are 2 generators and 101 relators of total length 19076
#I there are 2 generators and 84 relators of total length 6552
#I there are 2 generators and 38 relators of total length 1344
#I there are 2 generators and 9 relators of total length 94
#I there are 2 generators and 8 relators of total length 86
gap> TzPrintGenerators( P );
#I 1. _x1 43 occurrences
#I 2. _x2 43 occurrences
GAP 3.4.4