23.13 Tietze Transformations

The GAP commands being described in this section can be used to modify a group presentation in a presentation record 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 designed by George Havas Hav69 which has been available from Canberra since 1977 in a stand-alone version implemented by Peter Kenne and James Richardson and later on revised by Edmund F.~Robertson (see HKRR84, Rob88).

SimplifyPresentation, TzGo, and TzGoGo (the first two of these commands are identical).

Then we describe the lower-level commands TzEliminate, TzSearch, TzSearchEqual, and TzFindCyclicJoins. They are the bricks of which the preceding higher-level commands have been composed. You may use them to try alternative strategies, but if you are satisfied by the performance of TzGo and TzGoGo, then you don't need them.

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 you will need to substitute certain words as new generators in order to improve your presentation. Therefore GAP offers the two commands TzSubstitute and TzSubstituteCyclicJoins which introduce new generators. These commands will be described next.

Then we continue the section with a description of the commands TzInitGeneratorImages and TzPrintGeneratorImages which can be used to determine and to display the images or preimages of the involved generators under the isomorphism which is defined by the sequence of Tietze transformations which are applied to a presentation.

Subsequently we describe some further print commands, TzPrintLengths, TzPrintPairs, and TzPrintOptions, which are useful if you run the Tietze transformations interactively.

At the end of the section we list the Tietze options and give their default values. These are parameters which essentially influence the performance of the commands mentioned above. However, they are not specified as arguments of function calls. Instead, they are associated to the presentation records: Each presentation record keeps its own set of Tietze option values in the form of ordinary record components.

SimplifyPresentation( P ) TzGo( P )

SimplifyPresentation performs Tietze transformations on a presentation P. It is perhaps the most convenient of 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.

Roughly speaking, SimplifyPresentation consists of a loop over a procedure which involves two phases: In the search phase it calls TzSearch and TzSearchEqual described below which try to reduce the relator lengths by substituting common subwords of relators, in the elimination phase it calls the command TzEliminate described below (or, more precisely, a subroutine of TzEliminate in order to save some administrative overhead) which tries to eliminate generators that can be expressed as words in the remaining generators.

If SimplifyPresentation succeeds in reducing the number of generators, the number of relators, or the total length of all relators, then 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 TzSearchEqual command involved has changed the presentation such that another call of SimplifyPresentation 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 instead the TzGoGo command which we will describe next).

As an example we compute a presentation of a subgroup of index 408 in PSL(2,17).

    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> P.primaryGeneratorWords;
    [ b, a*b*a ]
    gap> P.protected := 2;;
    gap> P.printLevel := 2;;
    gap> SimplifyPresentation( P );
    #I  eliminating _x7 = _x5
    #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*_x2*_x1 

Note that the number of loops over the two phases as well as the number of subword searches or generator eliminations in each phase are determined by a set of option parameters which may heavily influence the resulting presentation and the computing time (see Tietze options below).

TzGo is just another name for the SimplifyPresentation command. It has been introduced for the convenience of those GAP users who are used to that name from the go option of the ANU Tietze transformation stand-alone program or from the go command in SPAS.

TzGoGo( P )

TzGoGo performs Tietze transformations on a presentation P. It repeatedly calls the TzGo command until neither the number of generators nor the number of relators nor the total length of all relators have changed during five consecutive calls of TzGo.

This may remarkably save you time and effort if you handle small presentations, however it may lead to annoyingly long and fruitless waiting times in case of large presentations.

TzEliminate( P ) TzEliminate( P, gen )
TzEliminate( P, n )

TzEliminate 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 P.spaceLimit. The default value of P.spaceLimit is infinity, but you may alter it appropriately (see Tietze options below).

If you specify a generator gen as second argument, then TzEliminate only tries to eliminate that generator.

If you specify an integer n as second argument, then TzEliminate tries to eliminate up to n generators. Note that the calls TzEliminate( P ) and TzEliminate( P, 1 ) are equivalent.

TzSearch( P )

TzSearch performs Tietze transformations on a presentation P. It tries to reduce the relator lengths by substituting common subwords of relators by shorter words.

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 le 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 at the end of this section may strongly influence the performance and the results of the TzSearch command. These are the parameters P.saveLimit and P.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 P.saveLimit per cent.

The default value of P.saveLimit is 10.

To understand the effect of the parameter P.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 P.searchSimultaneous to prescribe an upper bound for the number of short relators to be handled simultaneously.

The default value of P.searchSimultaneous is 20.

TzSearchEqual( P )

TzSearchEqual performs Tietze transformations on a presentation P. It tries to alter relators by substituting common subwords of relators by subwords of equal length.

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 le 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. 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 P.searchSimultaneous is used by TzSearchEqual in the same way as described for TzSearch.

However, TzSearchEqual does not use the parameter P.saveLimit: The loop over the relators is executed exactly once.

TzFindCyclicJoins( P )

TzFindCyclicJoins performs Tietze transformations on a presentation P. It searches for pairs of generators which generate the same cyclic subgroup and eliminates one of the two generators of each such pair it finds.

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 Euclidian algorithm to express a as a power of b, and then it eliminates a.

TzSubstitute( P, word ) TzSubstitute( P, word, string )

There are two forms of the command TzSubstitute. This is the first one. It 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 P, then it adds a new relator g^{-1} ! cdot ! word , to P. If a string string has been specified as third argument, the new generator g will be named by string, otherwise it will get a default name _xi as described with the function AddGenerator (see Changing Presentations).

More precisely: If, for instance, word is an abstract word, a call

TzSubstitute( P, word );

is more or less equivalent to

    AddGenerator( P );
    g := P.generators[Length( P.generators )];
    AddRelator( P, g^-1 * word );

whereas a call

TzSubstitute( P, word, string );

is more or less equivalent to

    g := AbstractGenerator( string );
    AddGenerator( P, g );
    AddRelator( P, g^-1 * word );

The essential difference is, that TzSubstitute, as a Tietze transformation of P, saves and updates the lists of generator images and preimages if they are being traced under the Tietze transformations applied to P (see the function TzInitGeneratorImages below), whereas a call of the function AddGenerator (which does not perform Tietze transformations) will delete these lists and hence terminate the tracing.

Example.

    gap> G := PerfectGroup( 960, 1 );
    PerfectGroup(960,1)
    gap> P := PresentationFpGroup( G );
    << presentation with 6 gens and 21 rels of total length 84 >>
    gap> P.generators;
    [ 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 := P.generators[1];;
    gap> b := P.generators[2];;
    gap> TzSubstitute( P, a*b, "ab" );
    #I  substituting new generator ab 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.  ab   28 occurrences 

TzSubstitute( P ) TzSubstitute( P, n )
TzSubstitute( P, n, eliminate )

This is the second form of the command TzSubstitute. It performs Tietze transformations on the presentation P. Basically, it 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.

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 squarefree relator subwords of length 2 and sorts them by decreasing numbers of occurrences. Let ab be the nth word in that list, and let i be the smallest positive integer which has not yet been used as a generator number. Then TzSubstitute defines a new generator P.i (see AddGenerator for details), adds it to the presentation together with a new relator P.i^{-1}ab, and replaces all occurrences of ab in the given relators by P.i.

Finally, it eliminates some generator from the extended presentation. The choice of that generator depends on the actual value of the eliminate parameter:

If eliminate is zero, then the generator to be eliminated is chosen as by the TzEliminate command. This means that in this case it may well happen that it is the generator P.i just introduced which is now deleted again so that you do not get any remarkable progress in transforming your presentation. On the other hand, this procedure guaranties that the total length of the relators will not be increased by a call of TzSubstitute with eliminate = 0.

Otherwise, if eliminate is 1 or 2, then TzSubstitute eliminates the respective factor of the substituted word ab, i.e., a for eliminate = 1 or b for eliminate = 2. In this case, it may well 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.

In order to decide which arguments might be appropriate for the next call of TzSubstitute, often it is helpful to print out a list of the most frequently occurring squarefree relator subwords of length 2. You may use the TzPrintPairs command described below to do this.

As an example 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 );
    gap> # We do not get any more progress without substituting a new
    gap> # generator
    gap> TzSubstitute( P );
    #I  substituting new generator _x28 defined by _x6*_x23^-1
    #I  eliminating _x28 = _x6*_x23^-1
    gap> # GAP cannot substitute a new generator without extending the
    gap> # total length, so we have to explicitly ask for it
    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
    gap> # If we save a copy of the current presentation, then later we
    gap> # will be able to restart the computation from the current state
    gap> P1 := Copy( P );;
    gap> # Just for demonstration, let's 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
    gap> # The presentation is worse than the one we have saved, so let's
    gap> # restart from that one again
    gap> P := Copy( 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*_x31^-1*_x32^-1*_x31^-1*_x32^-1
    #I  4. _x31*_x32*_x31^-1*_x32*_x31^-1*_x32*_x31*_x32^-2
    #I  5. _x31^-1*_x32^2*_x31*_x32^-1*_x31^2*_x32^-1*_x31*_x32^2 

As shown in the preceding example, you can use the Copy command to save a copy of a presentation record and to restart from it again if you want to try an alternative strategy. However, this copy will be lost as soon as you finish your current GAP session. If you use the Save command (see Presentation Records) instead, then you get a permanent copy on a file which you can read in again in a later session.

TzSubstituteCyclicJoins( P )

TzSubstituteCyclicJoins performs Tietze transformations on a presentation P. It tries to find pairs of generators a and b, say, for which among the relators (possibly after inverting or conjugating some of them) there are the commutator [a,b] and powers a^m and b^n with mutually prime exponents m and n. For each such pair, it substitutes the product ab as a new generator, and then it eliminates the generators a and b.

TzInitGeneratorImages( P )

Any sequence of Tietze transformations applied to a presentation record P, starting from an ``old'' presentation P_1 and ending up with a ``new'' 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 or the preimages of the new generators under varphi. The GAP Tietze transformations 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.

TzInitGeneratorImages initializes three components of P:

P.oldGenerators:

This is the list of the old generators. It is initialized by a copy of the current list of generators, P.generators.

P.imagesOldGens:

This will be the list of the images of the old generators as Tietze words in the new generators. For each generator g_i, the i-th entry of the list is initialized by the Tietze word [i].

P.preImagesNewGens:

This will be the list of the preimages of the new generators as Tietze words in the old generators. For each generator g_i, the i-th entry of the list is initialized by the Tietze word [i].

This means, that P_1 is defined to be the current presentation and varphi to be the identity on P_1. From now on, the existence of the component P.imagesOldGens will cause the Tietze transformations functions to update the lists of images and preimages whenever they are called.

You can reinitialize the tracing of the generator images at any later state by just calling the function TzInitGeneratorImages again. For, if the above components do already exist when TzInitGeneratorImages is being called, they will first be deleted and then initialized again.

There are a few restrictions concerning the tracing of generator images:

In general, the functions AddGenerator, AddRelator, and RemoveRelator described in section Changing Presentations do not perform Tietze transformations as they may change the isomorphism type of the presentation. Therefore, if any of them is called for a presentation in which generator images and preimages are being traced, it will delete these lists.

If the function DecodeTree is called for a presentation in which generator images and preimages are being traced, it will not continue to trace them. Instead, it will delete the corresponding lists, then decode the tree, and finally reinitialize the tracing for the resulting presentation.

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.oldGenerators 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 old generators have been.

TzPrintGeneratorImages( P )

If P is a presentation in which generator images and preimages are being traced through all Tietze transformations applied to P,, TzPrintGeneratorImages prints 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( 960, 1 );
    PerfectGroup(960,1)
    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> # Print the old generators as words in the new generators.
    gap> gens := P.generators;
    [ a, b, t ]
    gap> oldgens := P.oldGenerators;
    [ a, b, s, t, u, v ]
    gap> for i in [ 1 .. Length( oldgens ) ] do
    >  Print( oldgens[i], " = ",
    >  AbstractWordTietzeWord( P.imagesOldGens[i], gens ), "\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 

TzPrintLengths( P )

TzPrintLengths prints the list of the lengths of all relators of the given presentation P.

TzPrintPairs( P ) TzPrintPairs( P, n )

TzPrintPairs determines in the given presentation P the n most frequently occurring squarefree relator subwords of length 2 and prints them together with their numbers of occurrences. The default value of n is 10. A value n = 0 is interpreted as infinity.

This list is a useful piece of information in the context of using the TzSubstitute command described above.

TzPrintOptions( P )

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 records: Each presentation record keeps its own set of Tietze option parameters in the form of ordinary record components. In particular, you may alter the value of any of these Tietze options by just assigning a new value to the respective record component.

TzPrintOptions prints the Tietze option components of the specified presentation P.

The Tietze options have the following meaning.

protected:

The first P.protected generators in a presentation P are protected from being eliminated by the Tietze transformations functions. There are only two exceptions: The option P.protected is ignored by the functions TzEliminate(P,gen) and TzSubstitute(P,n,eliminate) because they explicitly specify the generator to be eliminated. The default value of protected is 0.

eliminationsLimit:

Whenever the elimination phase of the TzGo command is entered for a presentation P, then it will eliminate at most P.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 command. Note, however, that it is ignored by the TzEliminate 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 command or the elimination phase of the TzGo 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 P.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 command. The default value of expandLimit is 150.

generatorsLimit:

Whenever the elimination phase of the TzGo command is entered for a presentation P with n generators, then it will eliminate at most n - P.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 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 value of P.lengthLimit. The default value of lengthLimit is infinity.

loopLimit:

Whenever the TzGo command is called for a presentation P, then it will loop over at most P.loopLimit of its basic steps. Hence you may use the loopLimit parameter as a break criterion for the TzGo command. The default value of loopLimit is infinity.

printLevel:

Whenever Tietze transformation commands are called for a presentation P with P.printLevel = 0, they will not provide any output except for error messages. If P.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 P.printLevel = 2, you will get a much more generous amount of output. Finally, if P.printLevel = 3, various messages on internal details will be added. The default value of printLevel is 1.

saveLimit:

Whenever the TzSearch 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 P.saveLimit per cent. If this is the case, then TzSearch repeats its procedure instead of returning. Hence you may use the saveLimit parameter as a break criterion for the TzSearch command and, in particular, for the search phase of the TzGo command. The default value of saveLimit is 10.

searchSimultaneous:

Whenever the TzSearch or the TzSearchEqual command is called for a presentation P, then it is allowed to handle up to P.searchSimultaneously short relators simultaneously (see for the description of the TzSearch command for more details). The choice of this parameter may heavily influence the performance as well as the result of the TzSearch and the TzSearchEqual commands and hence also of the search phase of the TzGo command. The default value of searchSimultaneous is 20.

alter any of its Tietze option parameters at any time by just assigning a new value to the respective component.

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 TzGoGo command for different values of the eliminationsLimit parameter (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 TzGoGo command 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> P := PresentationSubgroup( G, H );
    << presentation with 224 gens and 593 rels of total length 2769 >>
    gap> for i in [ 28, 29, 30, 94, 100 ] do
    >       Pi := Copy( P );
    >       Pi.eliminationsLimit := i;
    >       Print( "#I  eliminationsLimit set to ", i, "\n" );
    >       Pi.printLevel := 0;
    >       TzGoGo( Pi );
    >       TzPrintStatus( Pi );
    >    od;
    #I  eliminationsLimit set to 28
    #I  there are 2 generators and 95 relators of total length 10817
    #I  eliminationsLimit set to 29
    #I  there are 2 generators and 5 relators of total length 35
    #I  eliminationsLimit set to 30
    #I  there are 3 generators and 98 relators of total length 2928
    #I  eliminationsLimit set to 94
    #I  there are 4 generators and 78 relators of total length 1667
    #I  eliminationsLimit set to 100
    #I  there are 3 generators and 90 relators of total length 3289 

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 [ 9, 10, 11, 12, 15 ] do
    >       Pi := Copy( P );
    >       Pi.saveLimit := i;
    >       Print( "#I  saveLimit set to ", i, "\n" );
    >       Pi.printLevel := 0;
    >       TzGoGo( Pi );
    >       TzPrintStatus( Pi );
    >    od;
    #I  saveLimit set to 9
    #I  there are 3 generators and 97 relators of total length 5545
    #I  saveLimit set to 10
    #I  there are 3 generators and 90 relators of total length 3289
    #I  saveLimit set to 11
    #I  there are 3 generators and 103 relators of total length 3936
    #I  saveLimit set to 12
    #I  there are 2 generators and 4 relators of total length 21
    #I  saveLimit set to 15
    #I  there are 3 generators and 143 relators of total length 18326 

Previous Up Top Next
Index

GAP 3.4.4
April 1997