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: 10000

Perform at most n iterations (default: 10000) of the main elimination loop.

    EliminationLimit: RngIntElt         Default: 100

Eliminate at most n generators (default: 100) in each iteration of the main elimination loop.

    LengthLimit: RngIntElt              Default: Infinity

Do not perform eliminations that make the total length of the current relations become larger than n (default: no limit).

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.

    Iterations: RngIntElt               Default: 10000

    EliminatinoLimit: RngIntElt         Default: 100

    LengthLimit: RngIntElt              Default: Infinity

Use the default strategy to simplify the presentation as much as possible. Perform at most i iterations (default: 10000) of the main elimination loop. Eliminate at most n generators (default: 100) on each iteration. Do not eliminate if the total length of the relations would exceed l (default: no limit).

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.

    Count: RngIntElt                    Default: 

Eliminate no more than n generators (default: the process elimination limit).

    Relator: RngIntElt                  Default: 0

If n > 0, try to eliminate a generator using the n-th relator. If no generator is specified by the parameter Gen below, then 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, try to eliminate the n-th generator. If no relation is specified by the parameter Rel above, then the shortest relator in which the n-th generator occurs exactly once (if any) is used.

Simplifies the presentation by repeatedly searching for common substrings in pairs of relators where the length of the substring is greater than half the length of the shorter relator and making the corresponding transformations. Relators of length 1 or 2 are also used to generate simplifications.

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;
> Search(~P);
> H<x, y> := ExtractGroup(P);
> H;
Finitely presented group H on 2 generators
Generators as words in group F7
    x = x1
    y = x2
Relations
    x^-1 * y^-1 * x^-1 * y^-2 * x^-1 * y * x^-1 * y * x^-1 = Id(H)
    x * y^3 * x^-1 * y * x^-1 * y^2 * x * y * x * y^-1 = 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);
> H;
Finitely presented group H on 2 generators
Generators as words in group F7
    x = x1
    y = x2
Relations
    x * y^-1 * x * y^2 * x * y * x^2 * y^-1 = Id(H)
    y * x * y * x * y^2 * x * y^2 * x^-2 = 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 >;
>
> 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

> 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);
> G;
Finitely presented group G on 2 generators
Generators as words in group F
    G.1 = x1
    G.2 = x2
Relations
    G.2 * G.1 * G.2 * G.1 * G.2^2 * G.1 * G.2^2 * G.1^-1 * G.2 * G.1^-2 * G.2 * 
    G.1^-2 = Id(G)
    G.1 * G.2^2 * G.1 * G.2 * 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 = Id(G)
> H := ncl< G | (G.1, G.2) >;
> H;
Finitely presented group H
Index in group G is 76 = 2^2 * 19
Subgroup of group G defined by coset table
> // We don't have the full nilpotent residual yet so we try again. 
> H := ncl< G | (G.1*G.1, G.2) >;
> H;
Finitely presented group H
Index in group G is 152 = 2^3 * 19
Subgroup of group G defined by coset table
> // We have it now.
> 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;
> "d = ", d, "e = ", e;
d =  18 e =  81
> "Right hand side = ", Right(d, e);
Right hand side =  135
> "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 := 1);
> "Left hand side = ", Left(Ngens(K), #Relations(K));
Left hand side =  126
> /*
> Got it! By Newman's theorem, H has an infinite 5-quotient and so F 
> must be infinite.
> */