Given a finitely presented group G, the user can attempt to simplify its presentation using substring searching. The choice of simplification strategy can either be left to Magma or selected by the user.

Simplify(G: parameters) : GrpFP -> GrpFP

Given a finitely presented group G attempt to eliminate generators and shorten relators by locating substrings that correspond to the left or right hand side of a relation. A new group K isomorphic to G is created which is (hopefully) defined by a simpler presentation than that for G. The order in which transformations are applied is determined by a set of heuristics.

    Iterations: RngIntElt               Default: Infinity

Perform at most n iterations (default: no limit) of the main elimination loop. Usually, one generator is eliminated for each iteration of the loop.

    SearchLimit: RngIntElt              Default: 1500

Only look for substrings of relators of length less than or equal to the limit specified when looking for Tietze transformations. If this bound is exceeded, then the number of times the limit was enforced will be printed.

Create a Tietze process that takes the presentation for the fp-group G as its starting point. This process may now be manipulated by various procedures that will be described below.

    Ngens: RngIntElt                    Default: 10

    Strategy: RngIntElt                 Default: 0

    Iterations: RngIntElt               Default: Infinity

Use the default strategy to simplify the presentation as much as possible. Eliminate n generators (default: 10) between substring searches. Perform at most i iterations (default: no limit) of the main elimination loop. Usually, one generator is eliminated for each iteration of the loop.

Eliminate generators in the presentation defined by the Tietze process P under the control of the parameters. First any relators of length one are used to eliminate trivial generators. Then, if there are any non-involutory relators of length two, the generator with the higher number is eliminated.

    Relator: RngIntElt                  Default: 0

This procedure performs an elimination using the n-th relator. The generator which is eliminated will be the highest numbered one which occurs exactly once in the relator (if any).

    Generator: RngIntElt                Default: 0

If n > 0, generator n is eliminated using the shortest suitable relator (if any). If n = 0, the first relator in which a generator occurs exactly once will be used. In each case, the highest-numbered generator occurring exactly once in the relator will be eliminated.

Replace any two relators which are both powers of the same word w by the single relator w^m, where m is the gcd of the two powers.

    Print: RngIntElt                    Default: 0

Controls the amount of information printed.

Search through the relators in order, using each in an attempt to shorten subsequent relators by substitution of long common substrings. This is the preferred procedure for simplifying the presentation by searching for common substrings. The algorithm goes through all the relators in order, using each in an attempt to shorten subsequent relators by substitution of long common substrings. Only when an attempt has been made to use each relator in this way does the program commence a new pass with the first relator.

The parameters are described below. Note that not all of them can be specified at the same time.

    Equal: BoolElt                      Default: false

If this is set to be true, then perform substring searching as in the case of command search, except that it is also permissible to substitute when a match is found between two substrings of equal length. If Equal is true, no other parameter should be assigned.

    Relator: RngIntElt                  Default: 0

If n > 0, only relator n is used in an attempt to shorten the subsequent relators. If Relator is true, no other parameter should be assigned.

    NewGenerator: BoolElt               Default: false

If this is set to be true, then search for the most commonly occurring two-generator substring x ast y among the relators. Define a new generator z with relation z = x ast y. The generator number of z will be one higher than the number of the current last generator. Then eliminate one of the generators x and y, by substituting for it in terms of z.

The parameter Strategy specifies which generator is to be eliminated. If it is "Shortest" (default), then eliminate whichever generator occurs less often. If it is "First" or "Second", then eliminate the first (second) generator in the substring. This may increase the length of the relators considerably, but Search(~P: NewGenerator) will repair the damage. If it is "Combination", then perform the equivalent of

> Search(~P: NewGenerator, Strategy := "First");
> Search(~P: NewGenerator);
> Search(~P: NewGenerator, Strategy := "Second");
> Search(~P: NewGenerator);

Only if NewGenerator is true may Strategy may be assigned.

    Strategy: MonStgElt                 Default: "Shortest"

This may only be assigned if NewGenerator is true. See under that parameter for a description of its operation.

Extract the group defined by the current presentation associated with the Tietze process P.

Ngens(P) : Process(Tietze) -> RngIntElt

The number of generators for the presentation currently stored by the Tietze process P.

Nrels(P) : Process(Tietze) -> RngIntElt

The number of relations in the presentation currently stored by the Tietze process P.

     <x_1,x_2,x_3,x_4,x_5,x_6,x_7 | x_1x_2=x_3, x_2x_3=x_4, x_3x_4=x_5,
         x_4x_5=x_6, x_5x_6=x_7, x_6x_7=x_1, x_7x_1=x_2>.

> F<x1, x2, x3, x4, x5, x6, x7> := FreeGroup(7);
> F7<x1, x2, x3, x4, x5, x6, x7> := 
>    quo< F | x1*x2=x3, x2*x3=x4, x3*x4=x5, x4*x5=x6,
>         x5*x6=x7, x6*x7=x1, x7*x1=x2 >;
> P := TietzeProcess(F7);
> for i := 7 to 3 by -1 do
>      EliminateGenerators(~P: Generator := i);
> end for;
> H<x, y> := ExtractGroup(P);
> print H;

Finitely presented group H on 2 generators
Relations
       x^2 * y^-2 * x^-1 * y^-2 * x^-1 * y^-1 * x^-1 * y^-1 = Id(H)
       x * y * x * y^2 * x * y * x * y^-1 * x * y^2 * x * y^2 = Id(H)

> F<x1, x2, x3, x4, x5, x6, x7> := FreeGroup(7);
> F7<x1, x2, x3, x4, x5, x6, x7> := 
>    quo< F | x1*x2=x3, x2*x3=x4, x3*x4=x5, x4*x5=x6,
>       x5*x6=x7, x6*x7=x1, x7*x1=x2>;
>H<x, y> := Simplify(F7: Iterations := 5);
> print H;

Finitely presented group H on 2 generators
Relations
       x^2 * y^-1 * x * y^-1 * x * y^2 * x * y = Id(H)
       x^2 * y^-1 * x^2 * y^-1 * x * y^-2 * x^-1 * y^-1 = Id(H)

Theorem. Let G be a group with a finite presentation on b generators and r relations, and suppose p is an odd prime. Let d denote the rank of the elementary abelian group G_1 = [G, G]G^p and let e denote the rank of G_2 = [G_1, G]G^p. If r - b < d^2/2 - d/2 - d - e or r - b <= d^2/2 - d/2 - d - e + (e + d/2 - d^2/4)d/2, then G has arbitrary large quotients of p-power order.

We present a proof that F(9) is infinite using this result.

> Left := func< b, r | r - b >;
> Right := func< d, e | d^2 div 2 - d div 2 - d - e + 
>                       (e + d div 2 - d^2 div 4)*(d div 2) >;
> 
> 
> F< x1,x2,x3,x4,x5,x6,x7,x8,x9 > := 
>  	Group< x1, x2, x3, x4, x5, x6, x7, x8, x9 | 
>              x1*x2=x3, x2*x3=x4, x3*x4=x5, x4*x5=x6, x5*x6=x7, 
>              x6*x7=x8, x7*x8=x9, x8*x9=x1, x9*x1=x2 >;
>
> print F;
Finitely presented group F on 9 generators
Relations
       x1 * x2 = x3
       x2 * x3 = x4
       x3 * x4 = x5
       x4 * x5 = x6
       x5 * x6 = x7
       x6 * x7 = x8
       x7 * x8 = x9
       x8 * x9 = x1
       x9 * x1 = x2

> print AbelianQuotientInvariants(F);
[ 2, 38 ]
> /*
> Thus the nilpotent quotient of F is divisible by 2 and 19.
> We examine the 2- and 19-quotients of F.
> */
> Q1 := pQuotient(F, 2, 0: Print := 1);
Lower exponent-2 central series for F
Group: F to lower exponent-2 central class 1 has order 2^2
Group: F to lower exponent-2 central class 2 has order 2^3
Group completed. Lower exponent-2 central class = 2, order = 2^3
> Q2 := pQuotient(F, 19, 0: Print := 1);
Lower exponent-19 central series for F
Group: F to lower exponent-19 central class 1 has order 19^1
Group completed. Lower exponent-19 central class = 1, order = 19^1
> /*
>  Thus, the nilpotent residual of F has index 152.
>  We try to locate this subgroup.
>  We first take a 2-generator presentation for F.
> */
> G := Simplify(F);
> print G;
Finitely presented group G on 2 generators
Relations
       G.1^2 * G.2^-1 * G.1^2 * G.2^-1 * G.1 * G.2^-2 * G.1^-1 * G.2^-2 * 
       G.1^-1 * G.2^-1 * G.1^-1 * G.2^-1 = Id(G)
       G.1^2 * G.2^-1 * G.1^2 * G.2^-1 * G.1 * G.2^-1 * G.1^2 * G.2^-1 * 
       G.1 * G.2^-1 * G.1 * G.2^2 * G.1 * G.2 = Id(G)
> H := ncl< G | (G.1, G.2) >;
> print H;
GrpFP: H
Subgroup of group G defined by coset table
Index is 76 = 2^2 * 19
> // We don't have the full nilpotent residual yet so we try again. 
> H := ncl< G | (G.1*G.1, G.2) >;
> print H;
Finitely presented group H
Subgroup of group G defined by coset table
Index is 152 = 2^3 * 19
> // We have it now.
> print AbelianQuotientInvariants(H);
[ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 ]
> /*
> The nilpotent H residual has a 5-quotient. We construct a 
> presentation for H and then calculate d and e for its 5-quotient.
> */
> K := Rewrite(G, H: Simplify := false);
> KP := pQuotientProcess(K, 5, 1);
> d := FactoredOrder(ExtractGroup(KP))[1][2];
> NextClass(~KP);
> e := FactoredOrder(ExtractGroup(KP))[1][2] - d;
> print "d = ", d, "e = ", e;
d =  18 e =  81
> print "Right hand side = ", Right(d, e);
Right hand side =  135
> print "Left hand side = ", Left(Ngens(K), #Relations(K));
Left hand side =  151
> /*
> Since Left is greater than Right, this presentation for H doesn't work 
> so we start eliminating generators.
> */
> K := Simplify(K: Iterations := 20);
> print "Left hand side = ", Left(Ngens(K), #Relations(K));
Left hand side =  130
> /*
> Got it! By Newman's theorem, H has an infinite 5-quotient and so F 
> must be infinite.
> */