45.9 Tietze Transformations that introduce new Generators

In the first form TzSubstitute 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, then it adds a new relator g^-1·word .

In its second form, TzSubstitute 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 below.

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 relator subwords of the form g₁ g₂, where g₁ and g₂ are different generators or their inverses, and sorts them by decreasing numbers of occurrences.

Let a b be the last word in that list, and let i be the smallest positive integer which has not yet been used as a generator number in the presentation P so far. TzSubstitute defines a new abstract generator x_i named "_xi" and adds it to P (see AddGenerator). Then it adds the word x_i^-1 a b as a new relator to P and replaces all occurrences of a b in the relators by x_i. Finally, it eliminates some suitable generator from P.

The choice of the generator to be eliminated depends on the actual value of the parameter eliminate:

If eliminate is zero, TzSubstitute just calls the function TzEliminate. So it may happen that it is the just introduced generator x_i which now is deleted again so that you don't get any remarkable progress in simplifying your presentation. On the first glance this does not look reasonable, but it is a consequence of the request that a call of TzSubstitute with eliminate = 0 must not increase the total length of the relators.

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

There is still another property of the command TzSubstitute which should be mentioned. If, for instance, word is an abstract word, a call

TzSubstitute( P, word );

is more or less equivalent to

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

However, there is a difference: If you are tracing generator images and preimages of P through the Tietze transformations applied to P (see Tracing generator images through Tietze transformations), then TzSubstitute, as a Tietze transformation of P, will update and save the respective lists, whereas a call of the function AddGenerator (which does not perform a Tietze transformation) will delete these lists and hence terminate the tracing.

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

As an example of an application of the command TzSubstitute in its second form we handle a subgroup of index 266 in the Janko group J₁.

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 );

Here we do not get any more progress without substituting a new generator.

gap> TzSubstitute( P );
#I  substituting new generator _x28 defined by _x6*_x23^-1
#I  eliminating _x28 = _x6*_x23^-1

GAP cannot substitute a new generator without extending the total length, so we have to explicitly ask for it by using the second form of the command TzSubstitute. Our problem is to chose appropriate values for the arguments n and eliminate. For this purpose it may be helpful to print out a list of the most frequently occurring squarefree relator subwords of length 2.

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

If we save a copy of the current presentation, then later we will be able to restart the computation from the current state.

gap> P1 := ShallowCopy( P );
<presentation with 2 gens and 10 rels of total length 101>

Just for demonstration we 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

This presentation is worse than the one we have saved, so we restart from that presentation again.

gap> P := ShallowCopy( 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

tries to find pairs of commuting generators a and b, say, such that the exponent of a (i. e. the least currently known positive integer n such that aⁿ is a relator in P) is prime to the exponent of b. For each such pair, their product a b is substituted as a new generator, and a and b are eliminated.

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