# Some Developed Examples

## `Example: F29 (ex-c85753)`

The finiteness of the last of the Fibonacci groups, $F(9)$, was settled in 1988 by M.F. Newman using the following result:

**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 \leq 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.

```magma
> 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 > :=
>     FPGroup< 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$.

```magma
> Q1 := pQuotient(F, 2, 0: Print := 1);
Class limit set to 127.

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);
Class limit set to 127.

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$.

```magma
> G := Simplify(F);
> G;
Finitely presented group G on 2 generators
Generators as words in group F
   G.1 = x4
   G.2 = x5
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 haven’t got the full nilpotent residual yet, so we try again.

```magma
> 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

```

Now, we have it.

```magma
> AbelianQuotientInvariants(H);
[ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 ]

```

The nilpotent residual $H$ has a 5-quotient. We construct a presentation for $H$ and then calculate $d$ and $e$ for its 5-quotient.

```magma
> 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. Thus we start eliminating generators.

```magma
> K := Simplify(K: Iterations := 1);
> "Left hand side = ", Left(Ngens(K), #Relations(K));
Left hand side =  136
> K := Simplify(K: Iterations := 1);
> "Left hand side = ", Left(Ngens(K), #Relations(K));
Left hand side =  123

```

Got it! By Newman’s theorem, $H$ has an infinite $5$-quotient and so $F$ must be infinite.

## `Example: L372 (ex-82d19f)`

In this example, we consider a – quite unpleasant – presentation for some group $G$. In fact, it is a presentation for the group ${{\operatorname{PSL}}}_3(7)\!\!:\!\!2$, but we assume that we do not know this and want to compute the order of the finitely presented group $G$ using coset enumeration.

We note in passing that the strategy outlined in this example is, together with other approaches, applied by the function [`Order`](fp-group-properties.md#function-grpfp-1-order).

```magma
> F<a,b,c> := FreeGroup(3);
> rels := [ a^4, b^2, (a,b)^3, (a*b)^8, ((a*b)^2*(a^-1*b)^3)^2,
>  c^2, (c*a*c*a^2)^2, (c*a)^3*(c*a^-1)^3,
>  c*a*b*c*a^-1*b*a^-1*c*a*b*c*a^2*a*b*a^-1,
>  c*a*b*c*b*a*c*a*c*a^-1*b*c*b*a^-1*c*a^-1,
>  c*a*b*a^-1*c*a*b*a^-1*c*a*b*a^-1*c*a*b*a^-1,
>  c*b*a^2*b*c*b*c*a^2*c*b*c*b*a^2*b,
>  c*a^2*c*b*a*c*b*a*c*b*a*c*a^-1*c*a*b*a^-1,
>  c*a^-1*b*a*c*a^-1*b*a*c*b*a*b*a^2*b*a^-1*b,
>  c*a*b*a^-1*b*c*b*a^-1*b*c*a^-1*b*a*b*a*c*b*c*b,
>  c*a*c*b*a*b*c*a*c*b*a*b*c*a*c*b*a*b,
>  c*b*a^-1*b*c*a^-1*c*a^-1*b*a*b*c*b*c*a^2*b*a*b*a^-1,
>  c*b*a^-1*b*a*b*c*b*a^-1*b*a*b*c*b*a^-1*b*a*b,
>  c*a^2*b*a^-1*b*c*b*c*b*a^-1*b*a*c*b*a^2*b*a^-1*b
> ];
> G<a,b,c> := quo< F | rels >;

```

As it happens, trying to determine the order of $G$ by enumerating the cosets of the trivial subgroup is quite hard. – Even the predefined enumeration strategy `"Hard"` (cf. [`ToddCoxeter`](subgroup-general.md#function-grpfp-1-toddcoxeter) and [`CosetEnumerationProcess`](subgroup-general.md#function-grpfp-cosetenumerationprocess)) does not give a finite result.

```magma
> time ToddCoxeter(G, sub<G|> : Strategy := "Hard");
0
Time: 199.620

```

Of course we could try to increase the workspace for the coset enumeration, but we decide to be more clever. Trying random words in the generators of $G$, we easily find some subgroup $S$ of $G$ with pretty small index in $G$.

```magma
> S := sub< G | b, c*a*c*b*a*b >;
> time Index(G, S);
114
Time: 0.120

```

We now have to compute the order of $S$. In order to be able to do this using coset enumeration, we have to construct a presentation for $S$ by rewriting $S$ w.r.t. $G$.

```magma
> time R := Rewrite(G, S : Simplify := false);
Time: 0.030

```

However, the presentation obtained by Reidemeister-Schreier rewriting without any simplification is not suitable for coset enumeration: it contains too many generators and its total length is quite high.

```magma
> NumberOfGenerators(R);
133
> PresentationLength(R);
14384

```

An enumeration with the predefined enumeration strategy `"Hard"` does not produce a finite result. (Note that in consideration of the high total relator length, we select a coset table based enumeration style; cf. [`CosetEnumerationProcess`](subgroup-general.md#function-grpfp-cosetenumerationprocess).)

```magma
> time ToddCoxeter(R, sub<R|> : Strategy := "Hard", Style := "C");
0
Time: 4.330

```

On the other hand, simplifying the presentation by reducing the number of generators as much as possible is not a good idea either, since the total relator length grows massively.

```magma
> time Rs := Simplify(R);
Time: 43.900
> NumberOfGenerators(Rs);
3
> PresentationLength(Rs);
797701

```

Again, an enumeration with the predefined enumeration strategy `"Hard"` does not produce a finite result.

```magma
> time ToddCoxeter(Rs, sub<Rs|> : Strategy := "Hard", Style := "C");
0
Time: 22015.849

```

The best strategy is, to simplify the presentation obtained from the Reidemeister-Schreier procedure by eliminating generators until the total length of the relators starts to grow.

```magma
> time Rsl := SimplifyLength(R);
Time: 0.330
> NumberOfGenerators(Rsl);
48
> PresentationLength(Rsl);
7152

```

A coset enumeration for this presentation produces a finite result in a reasonable amount of time.

```magma
> time ToddCoxeter(Rsl, sub<Rsl|> : Strategy := "Hard", Style := "C");
32928
Time: 289.410

```

This finally proves that $G$ is finite and has order $32928 * 114 = 3753792$.