45.8 Elementary Tietze Transformations

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 spaceLimit (see Tietze Options). The default value of that parameter is infinity, but you may alter it appropriately.

If a generator gen has been specified, TzEliminate eliminates it if possible, i. e. if there is a relator in which gen occurs just once. If no second argument has been specified, TzEliminate eliminates some appropriate generator if possible and if the resulting total length of the relators will not exceed the parameter lengthLimit.

If an integer n has been specified, TzEliminate tries to eliminate up to n generators. Note that the calls TzEliminate(P) and TzEliminate(P,1) are equivalent.

searches for relator subwords which, in some relator, have a complement of shorter length and which occur in other relators, too, and uses them to reduce these other relators.

The idea is to find pairs of relators r₁ and r₂ of length l₁ and l₂, respectively, such that l₁ £ l₂ and r₁ and r₂ coincide (possibly after inverting or conjugating one of them) in some maximal subword w, say, of length greater than l₁/2, and then to substitute each copy of w in r₂ by the inverse complement of w in r₁.

Two of the Tietze option parameters which are listed in section Tietze Options may strongly influence the performance and the results of the command TzSearch. These are the parameters saveLimit and 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 saveLimit per cent.

The default value of saveLimit is 10 per cent.

To understand the effect of the option 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₁, and a subroutine is called which loops over the succeeding relators, treating them as long relators r₂ 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₁ of length l₁, say, it first determines the minimal match length l which is l₁/2+1, if l₁ is even, or (l₁+1)/2, otherwise. Then it builds up a hash list for all subwords of length l occurring in the conjugates of r₁ or r₁^-1, and finally it loops over all long relators r₂ 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₂, 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 searchSimultaneous to prescribe an upper bound for the number of short relators to be handled simultaneously.

The default value of searchSimultaneous is 20.

searches for Tietze relator subwords which, in some relator, have a complement of equal length and which occur in other relators, too, and uses them to modify these other relators.

The idea is to find pairs of relators r₁ and r₂ of length l₁ and l₂, respectively, such that l₁ is even, l₁ £ l₂, and r₁ and r₂ coincide (possibly after inverting or conjugating one of them) in some maximal subword w, say, of length at least l₁/2. Let l be the length of w. Then, if l > l₁/2, the pair is handled as in TzSearch. Otherwise, if l = l₁/2, then TzSearchEqual substitutes each copy of w in r₂ by the inverse complement of w in r₁.

The Tietze option parameter searchSimultaneous is used by TzSearchEqual in the same way as described for TzSearch. However, TzSearchEqual does not use the parameter saveLimit: The loop over the relators is executed exactly once.

searches for power and commutator relators in order to find pairs of generators which generate a common cyclic subgroup. It uses these pairs to introduce new relators, but it does not introduce any new generators as is done by TzSubstituteCyclicJoins (see TzSubstituteCyclicJoins).

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ⁿ, 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.

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