SOME COMPUTATIONAL APPROACHES TO GROUPS GIVEN BY A FINITE PRESENTATION^{1}

Joachim Neubüser

Lehrstuhl D für Mathematik RWTH Aachen, 5100 Aachen West Germany

Said Sidki

Departamento de Matemática Universidade de Brasília 70910 - Brasília DF Brasil

0. Introduction

”What is this group like?” could be an alternative title for this paper. Our special interest is in groups which are presented to us as being generated by a small set of elements, be these permutations of vertices of a graph, matrices describing automorphisms of linear codes, or classes of homotopies of a knot described only by the relations that they satisfy (see [Hac 87]).

Although the axioms that define the notion of a group are rather simple, and in spite of the abundance of knowledge about large classes of groups, one is frequently frustrated by the paucity of methods for dealing with groups described by a small set of generators and relations that hold between them.

What is lacking in the standard texts of classical algebra and group theory is a counterpart of numerical methods in differential equations. Yet, such computational methods in group theory have been developed along the years under the influence of external problems as well as from within, especially by the needs of the classification of finite simple groups and the Burnside Groups problem.

It should be emphasized that the present computational methods build on careful analysis of algorithmic aspects of known theories. Also, that the practical use of these algorithms became possible in a meaningful way only with the advent of computer technology.

We will present in this article some of the known computational methods for investigating groups given by generators and relations, comment upon their theoretical background, and illustrate them by way of workedout examples.

1Published as: Alguns Procedimentos Computacionais Para Grupos Dados Por Uma Apresentação Finita, Mathemática Universitaria No. 7, (1988) 77 – 120, Rio de Janeiro

We have made an effort to reduce the requirements to a minimum and have developed some calculations in detail. The reader who wishes to pursue this topic further can learn about the state of the art in [Atk 84].

Contents

0. Introduction.

1. Free groups and presentations; Dehn’s problems; a family C_{q} of presentations.

2. Abelian groups and the elementary divisor algorithm.

3. Novikov’s theorem and the Todd-Coxeter method; C_{1}.

4. C_{2} and the ”low index” method.

5. The Schreier-Sims algorithm for permutation groups.

6. Reidemeister’s theorem, a modified Todd-Coxeter method, and more about C_{1} and C_{2}.

7. Using SL(2, ·) representations.

8. Another example; the nilpotent quotient algorithm.

9. Implementations and computers.

10. An epilogue.

11. Appendix.

12. Bibliography.

1. Free groups and presentations

The identification of a group given by generators and relations may be likened humorously to a detective story where the available clues are few yet sufficient to pin down the suspect.

As an example, let us consider D_{12} and D_{6}, the groups of the Euclidean symmetries of the regular hexagon 123456, and the regular triangle 135.

[figure: 0; 1; 6; 5; 4; 3; 2]

By direct enumeration , D_{12} has twelve elements and D_{6} has six elements. Call the anticlockwise rotation by \frac{2π}{6} around 0 by A, further A^{2} by A_{2}, and the reflection in the line 14 by B. Then A, B are symmetries of the hexagon, and A_{2}, B are symmetries of the triangle. We observe that

A^{6} = 1, B^{2} = 1, B^{−1}AB = A^{−1}, and A_{2}^{3} = 1, B^{2} = 1, B^{−1}A_{2}B = A_{2}^{−1}.

From A_{2}^{3} = 1, we have (A_{2}^{3})^{2} = A_{2}^{6} = 1.

The relation B^{−1}AB = A^{−1} implies, for any integers i, j ≥ 0, that

B^{−j}AB^{j} = B^{−1}(… B^{−1}(B^{−1}AB)B …)B = A^{(−1)^{j}},

and

B^{−j}A^{i}B^{j} = (B^{−j}AB^{j})^{i} = A^{(−1)^{j}i},

that is,

A^{i}B^{j} = B^{j}A^{(−1)^{j}i},

which allows the transport of B^{j} from the right to the left of A^{i}. The elements of the subgroup H of D_{12} generated by A, B, therefore have the form B^{j}A^{i} for 0 ≤ i < 6, 0 ≤ j < 2, and one can easily see this to be a normal form. It follows that H has twelve elements and H = D_{12}. Similarly, one shows that D_{6} is generated by A_{2} and B.

Now suppose that the information provided about a suspect group is that it is generated by two elements a, b subject to the relations

a^{6} = 1, b^{2} = 1, b^{−1}ab = a^{−1},

can one identify this group, up to isomorphism, to be D_{12}? And then, how about D_{6}? The answer to such a question requires the formal introduction of the concept of a free group and of a presentation of a group.

Let X = {x_{1}, …, x_{n}, x_{1}^{−1}, …, x_{n}^{−1}} be a set of 2n different elements. A finite sequence (y_{1}, …, y_{k}) with y_{i} ∈ X, such that no two subsequent elements are of the form x_{i}, x_{i}^{−1} or x_{i}^{−1}, x_{i} as well as the empty sequence ( ) is called a ”reduced word” w(x_{i}). It can be proved that the set of all reduced words is a group if one defines ”multiplication” of two such sequences by their concatenation

(y_{1}, …, y_{k})(y_{k+1}, …, y_{l}) = (y_{1}, …, y_{k}, y_{k+1}, …, y_{l})

followed by the removal of all consecutive pairs of the form x_{i}, x_{i}^{−1} and x_{i}^{−1}, x_{i}. (To show that one arrives at the same result irrespective of the sequence in which removals are performed, is the main part of the proof.) The empty sequence obviously is the neutral element in this group, and the inverse of a sequence is formed by reversing it and changing each x_{i} for x_{i}^{−1} and each x_{i}^{−1} for x_{i}. This group is clearly generated by the sequences (x_{i}), i = 1, …, n. As customary, we shall just write a ”formal product” y_{1}y_{2} ⋯ y_{k} for a sequence (y_{1}, …, y_{k}) with y_{i} ∈ X, and 1 for the empty sequence ( ). This group is called the free group F_{n} of rank n, freely generated by x_{1}, …, x_{n}.

Now let G be any group generated by a set {g_{1}, …, g_{n}}. The fact that each element in F_{n} has a unique reduced form which therefore is a normal form in the generators x_{1}, …, x_{n} shows that the function ϕ : x_{i} ↦ g_{i} extends to an epimorphism ϕ of F_{n} onto G. Hence by the homomorphism theorem G is isomorphic to the factor group of F_{n} by the kernel of ϕ, that is G ≅ F_{n}/ker ϕ. This kernel consists exactly of those words r(x_{i}), for which the ”value” ϕ(r(x_{i})), i.e. the element r(g_{i}) ∈ G obtained by replacing each x_{i}^{±1} by g_{i}^{±1}, is the neutral element of G (which we also denote by 1). This is what is meant by saying that these elements r(x_{i}) are ”relators” corresponding to ”relations” r(g_{i}) = 1 for the generating set {g_{i}} of G.

Any set R = {r_{j}(x_{i})} ⊆ ker ϕ such that ker ϕ is the normal closure of R, (i.e. the smallest normal subgroup of F_{n} containing R) is called a ”defining set of relators” for G with respect to the generating set {g_{i}} and the corresponding set of relations {r_{j}(g_{i}) = 1} a ”defining set of relations”. A set of generators together with a defining set of relations (relators) is called a presentation, and the group G is called finitely presented, if not only the set of generators, but also the defining set of relations is finite.

It is time we return to the question whether the generators a, b together with the defining relations a^{6} = 1, b^{2} = 1, b^{−1}ab = a^{−1}, provide a presentation for D_{12}. In other words, is the factor group of the free group F_{2} by the normal closure N of {x_{1}^{6}, x_{2}^{2}, x_{2}^{−1}x_{1}x_{2}x_{1}} isomorphic to D_{12}? The kernel of the epimorphism ϕ : F_{2} → D_{12} defined by ϕ : x_{1} ↦ A, x_{2} ↦ B, contains x_{1}^{6}, x_{2}^{2}, x_{2}^{−1}x_{1}x_{2}x_{1}. Is N = ker ϕ ? Here we repeat the calculations done for the normal form of the elements in D_{12} in the case of F_{2}/N, generated by Nx_{1}, Nx_{2}, and reach the conclusion that F_{2}/N has at most twelve elements. However, as N ⊆ ker ϕ, F_{2}/N has a multiple of 12 elements, and so N = ker ϕ.

Before continuing let us add two remarks:

(i) A nontrivial group has many generating sets and to each can belong many different defining sets of relations;

(ii) We may reverse the process described above. Let W = {w_{j}(x_{i})} be an arbitrary set of elements of F_{n} and N be the normal closure of W, then {w_{j}(x_{i})} is a defining set of relators for F_{n}/N. So any presentation defines (uniquely up to isomorphism) some group. Such presentations are in fact used very often in certain branches of mathematics, such as topology (see [Hac 87]) to describe groups about which very little is known otherwise, often not even whether they are finite or not.

This was the case, for instance, with the following class of presentations

C_{q} = ⟨ a, b | aba^{−2}bab^{−1} = 1, a(b^{−1}a^{3}b^{−1}a^{−3})^{q} = 1 ⟩

which were sent to one of us in November 1984 by A. Cavicchioli. Although the original question, whether the groups C_{q} and C_{q′} are non-isomorphic for q ≠ q′, has meanwhile been answered by a different approach (see [Cav 86]) they furnish a nice example for the demonstration of computational methods.

This request about C_{q} fits within problems posed by Max Dehn in 1911 [Deh 11] about the existence of universal algorithms for deciding three questions in the class F P of finitely presented groups: let G_{1}, G_{2} be F P groups, furthermore let ϕ_{i} : F_{n_{i}} → G_{i} (i = 1, 2) be the epimorphisms that provide the given finite presentations for these groups,

(1) (Word Problem) given w ∈ F_{n_{1}}, decide whether or not w ∈ ker ϕ_{1},

(2) (Conjugacy Problem) given u, v ∈ F_{n_{1}}, decide whether or not ϕ_{1}(u) and ϕ_{1}(v) are conjugate in G_{1},

(3) (Isomorphism Problem) decide whether or not G_{1} and G_{2} are isomorphic groups.

2. Abelian groups and the elementary divisor algorithm

(1) The canonical decomposition of finitely presented abelian groups has an algorithmic proof that leads directly to an easy implementation and also to a positive answer to Dehn’s word and isomorphism problems for this specific class of groups. Here, obviously, the conjugacy and word problems are equivalent.

Let A be an abelian group generated by the set {a_{1}, a_{2}, …, a_{n}} satisfying a possibly empty defining set of relations {r_{i}(a_{j}) = 1 | 1 ≤ i ≤ m}. That is, A affords the presentation

⟨a_{1}, a_{2}, …, a_{n} | [a_{i}, a_{j}] = 1 for 1 ≤ i < j ≤ n, r_{i}(a_{j}) = 1 for 1 ≤ i ≤ m ⟩

where the symbol [a_{i}, a_{j}] denotes the commutator a_{i}^{−1}a_{j}^{−1}a_{i}a_{j}. The kernel K of the epimorphism ϕ : F_{n} → A defined by ϕ : x_{i} ↦ a_{i} contains the derived group F′_{n} which is the normal closure of the set {[x_{i}, x_{j}] | 1 ≤ i < j ≤ n}. Thus, ϕ induces the epimorphism ϕ̄: F̄_{n} → A where F̄_{n} = F_{n}/F′_{n} is the free abelian group of rank n.

On rewriting the group operation of F̄_{n} additively, we have that K̄ is generated by

r_{i}(x̄_{j}) = ∑_{j=1}^{n} m_{ij}x̄_{j} (1 ≤ i ≤ m)

where the m_{ij} are integers. We may apply to the n × m matrix M = (m_{ij}) the usual elementary transformations with the exception of multiplication of rows or columns by integers ≠ ±1. These operations produce new bases for F̄_{n} and generating sets for K̄.

Following the procedure which will be described below, M can be transformed into its normal form

( \frac{\begin{aligned}d_{1} \\ & d_{2} \\ & & . & . & . \\ & & & & & d_{k} \end{aligned} 0}{0  0} )

where the set {d_{1}, d_{2}, …, d_{k}} of positive integers, when nonempty, will have the divisibility property d_{1} | d_{2} | … | d_{k} – the elementary divisors of A.

The matrix in normal form provides us with a basis ȳ_{1}, …, ȳ_{n} of F̄_{n} such that r′_{1}(ȳ_{i}) = d_{1}ȳ_{1}, …, r′_{k}(ȳ_{i}) = d_{k}ȳ_{k} is a basis for K̄, and so,

A ≅ F̄_{n}/K̄ ≅ ⟨K̄ + ȳ_{1}⟩ ⊕ … ⊕ ⟨K̄ + ȳ_{n}⟩

where

⟨K̄ + ȳ_{i}⟩ ≅ Z_{d_{i}} (cyclic of order d_{i}) for 1 ≤ i ≤ k,

≅ Z (infinite cyclic) for k + 1 ≤ i ≤ n.

Thus we have arrived at a presentation for A of the form

⟨z_{1}, …, z_{n} | [z_{i}, z_{j}] = 1 (1 ≤ i < j ≤ n), z_{1}^{d_{1}} = … = z_{k}^{d_{k}} = 1, with d_{i} ≥ 1, and d_{1} | d_{2} | … | d_{k} ⟩.

If d_{1} = d_{2} = … = d_{l} = 1, and d_{l+1} ≠ 1, then A has the canonical decomposition

A ≅ Z_{d_{l+1}} ⊕ … ⊕ Z_{d_{k}} ⊕ Z ⊕ … ⊕ Z
n − k

and {d_{l+1}, …, d_{k} ; n − k} is the set of invariants that characterizes A.

(2) To demonstrate the algorithm, it suffices to bring M into the form

M_{1} = ( \begin{matrix}x & 0 \\ 0 & M′ \end{matrix} )

where x | mij^{′} for all entries mij^{′} of M′. This is done as follows for M ≠ 0.

1. Select m_{ij} ∈ M with 0 ≠ | m_{ij} | ≤ | m_{rs} | for all 0 ≠ m_{rs} ∈ M.

2. Interchange rows R_{i} and R_{1}; interchange columns C_{j} and C_{1}; (now 0 ≠ | m_{11} | ≤ | m_{rs} | for all 0 ≠ m_{rs} ∈ M) multiply R_{1} by ±1 to make m_{11} > 0.

3. For j = 2, …, n write m_{1j} = c_{j}m_{11} + r_{j} with 0 ≤ r_{j} < m_{11}; if c_{j} ≠ 0,

subtract c_{j}C_{1} from C_{j}.

(Now 0 ≤ m_{1j} < m_{11} for j = 2, …, n).

4. If there exists m_{1j} ≠ 0 for j ≠ 1, exchange C_{1} and C_{j}; go back to 3.

(This stops when R_{1} = (m_{11}, 0, …, 0)).

5. If m_{11} does not divide all entries of M, select m_{ij}, such that m_{11} |̸ m_{ij}; if j ≠ 1, add C_{1} to C_{j}; write m_{ij} = d_{ij}m_{11} + r_{ij} with 0 < r_{ij} < m_{11}; substract d_{ij}R_{1} from R_{j}; (so, now 0 < m_{ij} < m_{11}) go back to 1.

(Since m_{11} keeps decreasing, eventually m_{11} | m_{ij} for all i, j and we come to point 6).

6. For i = 2, …, m write m_{i,1} = d_{i}m_{11}; if d_{i} ≠ 0,

subtract d_{i}R_{1} from R_{i}.

(3) Given the good grasp we have on finitely presented abelian groups, one of the first methods we apply to a group G which is finitely presented as

⟨ g_{1}, …, g_{n} | r_{1}(g_{i}) = … = r_{m}(g_{i}) = 1 ⟩

is the study of its abelianization Ḡ = G/G′ which has the presentation

⟨a_{1}, …, a_{n} | [a_{i}, a_{j}] = 1 (1 ≤ i < j ≤ n), r_{1}(a_{i}) = … = r_{m}(a_{i}) = 1 ⟩.

For instance for C_{q}:

C̄_{q} = ⟨ a, b | [a, b] = 1, aba^{−2}bab^{−1} = 1, a(b^{−1}a^{3}b^{−1}a^{−3})^{q} = 1 ⟩.

As a and b commute in C̄_{q}, the second and third relation may be rewritten as

1 = aa^{−2}abbb^{−1} = b, 1 = ab^{−q}a^{3q}b^{−q}a^{−3q} = ab^{−2q},

or as

b = 1 , a = b^{2q}.

So

a = b = 1 in C̄_{q}.

That is, C̄_{q} is trivial, or what is the same, C_{q} is a perfect group. An immediate consequence is that the minimal nontrivial finite quotients of C_{q}, if any, are noncyclic simple groups.

3. Novikov’s theorem and the Todd–Coxeter method

While in the last section we saw that Dehn’s problems have a very elegant solution for finitely presented abelian groups, in 1955 P. S. Novikov [Nov 55] published a proof that the word problem is unsolvable. In fact he proved that there exists a finitely presented group G that will defeat any algorithm that claims to decide in a finite number of steps if a given word in the generators of G represents the identity or not. Soon after, also Dehn’s other problems were proved to be algorithmically unsolvable as well as other questions, e. g. to decide from a given presentation if the group presented is finite [Rab 58]. These results leave room only for a more modest attempt than the solution of Dehn’s problems and such a more modest approach had in fact been proposed already in 1936 by J. Todd and H.S.M. Coxeter [ToC 36].

Their method can best be characterized as a ”verification method”: if the group described by a finite presentation is in fact finite, the method will eventually (i. e. after a finite number of steps) stop, having verified this fact, but no bound can be given from the presentation, when this will happen; so if the method has not been successful after a given time, \underline{no} conclusion can be drawn; it is \underline{not} a decision algorithm.

The Todd-Coxeter method actually deals with a slightly more general situation: Given a finite presentation

G = ⟨ g_{1}, …, g_{n} | r_{1}(g_{i}) = 1, …, r_{m}(g_{i}) = 1 ⟩

and a finite set of words

{ s_{1}(g_{i}), …, s_{p}(g_{i}) },

it tries to determine the index of the subgroup U = ⟨ s_{1}(g_{i}), …, s_{p}(g_{i}) ⟩ in G by constructing the permutation representation of G on the set of right cosets of U in G:

φ_{U} : g ↦ ( \begin{matrix}Uh \\ Uhg \end{matrix} ) for all g, h ∈ G.

This is done for the generators of G in a trial-and-error fashion: Cosets of U will be given numbers 1, 2, 3, … starting with 1 := U, but only if the method finishes successfully, will it be certain that different numbers represent different cosets: during the process several numbers may be given inadvertently to the same coset.

For each subgroup generator

s(g_{i}) = g_{i_{1}} … g_{i_{e}}, g_{i_{j}} ∈ {g_{1}, …, g_{n}, g_{1}^{−1}, …, g_{n}^{−1}} = : E,

a one-line ”subgroup table”

g_{i_{1}} g_{i_{2}} … g_{i_{e}}
\overline{1 1}

is set up, expressing the fact that Us(g_{i}) = U. Likewise for each relation r(g_{i}) = g_{i_{1}} … g_{i_{t}} = 1 a ”relation table”,

g_{i_{1}} g_{i_{2}} … g_{i_{t}}

\begin{matrix}1 & 1 \\ 2 & 2 \\ ⋮ & ⋮ \\ k & k \\ ⋮ & ⋮ \end{matrix}

having one line for each coset number defined in the process, reflects the fact that for each coset k := Uh we have k · r(g_{i}) = k.

A single ”coset table” is used for the bookkeeping of the recursive definition of the meaning of the coset numbers:

g_{1} … g_{n} g_{1}^{−1} … g_{n}^{−1}

1 2

⋮ k

⋮

The method proceeds by defining each new coset number l by an equation of the form l := k · g, where k is a previously defined coset number, g a generator or its inverse and the place for this definition in the coset table is still vacant. Together with l := kg the entry k = lg^{−1} is made in the coset table and then both these definitions are inserted into all subgroup and relation tables. Whenever a line closes in one of the subgroup or relation tables, it yields an information of the kind kg = l, called a ”consequence”. Comparing this with the state of the coset table one of three cases can occur:

(i) both of the entries for kg and for lg^{−1} in the coset table are still empty. Then this new information is entered into both places of the coset table and used in the same way as the definitions before;

(ii) these places already contain this information. Then nothing needs to be done;

(iii) one of the places contains a different information, say kg = l′ ≠ l. Then we learn that in fact the \underline{coset numbers} l and l′ denote the same coset, and we have to eliminate one (the bigger) of them. Doing so, we may in fact find more such so-called ”coincidences”.

Let us demonstrate the beginning of the method for the first of Cavicchioli’s groups. We write its presentation in the form

C_{1} = ⟨ a, b | a^{−2}bab^{−1}ab = 1, a^{3}b^{−1}a^{−2}b^{−1} = 1 ⟩

Note that the relations have been cyclically permuted, i.e. conjugated. Transformations like this often are advantageous in order to get neater enumerations. We try to enumerate the cosets of U := ⟨a⟩, so we have one subgroup table

\frac{a}{1 | 1}

which tells us immediately that 1a = 1 (and 1a^{−1} = 1). Introducing these and a first definition 1b =: 2 (and 2b^{−1} = 1) into coset table and relation tables we have

Relation tables:

a^{−1} a^{−1} b a b^{−1} a b a a a b^{−1} a^{−1} a^{−1} b^{−1}

1 1 1 2  1 2  2 1 1 2  1 1 1 1  2 1 2  2

Coset table:

a b a^{−1} b^{−1}
1 1 2 1
2  1

After the further definitions 1b^{−1} =: 3 and 2a =: 4, the first line of the second relation table closes

a a a b^{−1} a^{−1} a^{−1} b^{−1}

\begin{matrix}1 & 1 & 1 & 1 & 3 & 4 & 2 & 1 \\ · & · & · & · & · & · & · & · \end{matrix}

and yields as a first ”consequence” 3a^{−1} = 4 which together with 4a = 3 is entered into the coset table.

The complete sequence of definitions, consequences, and one elimination together with the tables can be found in the Appendix. We just point to two events in this enumeration: after the 9th definition (of coset number 10) it is found that coset numbers 9 and 8 define the same coset, the number 9 is eliminated then. Rather than renumbering, we leave this gap and continue with the definition of coset number 11.

After the definition of coset number 13 all tables are filled without any further ”coincidence” of coset numbers pending. No definitions satisfying the original restriction are possible.

It can be shown from a more general discussion of the procedure (see e. g. [Neu 82]) that whenever this happens, the columns of the coset table give the permutations that multiplication from the right with the generators induces on the cosets of U. This assignment of permutations to the generators of the finitely presented group G defines the permutation representation φ_{U}. Its kernel is

ker φ_{U} = { g | g ∈ G, Uh = Uhg, ∀h ∈ G } = ⋂_{h∈G} h^{−1}Uh,

hence in particular ker φ_{U} ≤ U. By the homomorphism theorem φ_{U}(G) ≅ G/ker φ_{U} and for the indices G : U = φ_{U}(G) : φ_{U}(U), and

|φ_{U}(G)| = G : ker φ_{U} = (G : U) · |φ_{U}(U)|.

In our case of Cavicchioli’s group C_{1}, the permutations obtained for the generators are

a ↦ A = (2 4 3 7 6)(5 8 11 13 10)

b ↦ B = (1 2 5 8 3)(6 10 12 11 7)

(remember we have permutations on 1, …, 13, omitting 9).

Since C_{1} : ⟨a⟩= 12 and |⟨A⟩| = 5, we have

C_{1} : ker φ_{U} = 12 · 5 = 60 = |⟨A, B⟩|.

Of course, if we would enumerate the cosets of the unit group, we might get the order of C_{1}, but as we shall see later, this would require much more space. Rather, in section 6 we can determine the order of C_{1} by a variation of the presently used enumeration. Before this, in the next two sections, we turn to C_{2}. We remark in conclusion of this section that analysing the Todd-Coxeter procedure further, N. Mendelsohn has shown that it has indeed the claimed property of a verification method(see e.g. [Neu82]).

4. C_{2} and the ”low index” method

If we start to investigate

C_{2} = ⟨ a, b | aba^{−2}bab^{−1} = 1, a(b^{−1}a^{3}b^{−1}a^{−3})^{2} = 1 ⟩

by trying again to enumerate the cosets of ⟨a⟩, this time even by computer, we experience disappointment: after having defined several hundred thousand coset numbers, the computer runs out of space, the method has not come to an end and so no conclusion about C_{2} has been reached.

Of course, just taking further chances by trying other sets of words as subgroup generators would not be very satisfactory. Instead, one would prefer a method that would systematically search for \underline{all} subgroups up to a given small upper bound for the index, k say.

Such a method, using the idea of a coset table has been proposed by C. Sims. Let us describe it again generally for a finitely presented group

G = ⟨ g_{1}, …, g_{n} | r_{1}(g_{i}) = 1, …, r_{m}(g_{i}) = 1 ⟩.

It starts a Todd-Coxeter enumeration without using any subgroup generators; if this enumeration has produced more than k coset numbers, then clearly, if this was the enumeration of the cosets of a subgroup U of index ≤ k, some of these coset numbers must represent the same coset. Saying that coset numbers x and y, representing cosets defined in the process recursively by representatives t_{x}(g_{i}) and t_{y}(g_{i}) do in fact define the same coset, amounts to saying that t_{x}(g_{i})t_{y}(g_{i})^{−1} ∈ U. So forcing ”coincidence” of the cosets with numbers x and y and eliminating one of them from the coset table is tantamount to restricting the enumeration to subgroups containing t_{x}(g_{i})t_{y}(g_{i})^{−1}. In Sims’ algorithm such ”forced coincidences” are studied in some lexicographical order, making sure by a backtrack search that each subgroup of index ≤ k is found exactly once. A further refinement gives just one representative from each conjugacy class of subgroups. (For details see again [Neu 82]).

For each class, the number of subgroups in the class is given and for one representative subgroup U of each class a set of generators of U as words in the generators of G as well as the coset table of U. The coset table of course provides us with the images φ_{U}(g_{1}), …, φ_{U}(g_{n}) of the generators g_{1}, …, g_{n} of G under the permutation representation φ_{U} of G on the cosets of U.

Applied by computer to C_{2} with index bound 15 the method yields:

10 classes of subgroups of index 11, 8 classes of subgroups of index 12, 6 classes of subgroups of index 13.

5. The Schreier-Sims algorithm for permutation groups

The information we have obtained about the group C_{2} may not seem to be very strong. However, as we have seen at the end of section 3, because of

G/ker φ_{U} ≅ φ_{U}(G)

we can obtain such factor groups from the (permutation) images of the generators of G that are provided by the ”low index” method. In the case of C_{1} it was easy to obtain the order of φ_{U}(G) since φ_{U}(U) was cyclic; in general we have to generate the permutation group φ_{U}(G) from its generators. A very powerful method for this task is due to C. Sims, we now present the basic idea of this so-called Schreier-Sims method; the reader interested in technical details and practical organization of the method (that are in fact crucial for any efficient implementation) is referred to [Leo 80a,b].

Let H be a group of permutations of the set Ω = {1, 2, …, z}. We define the ”stabilizer chain”

H^{0} := H, H^{i} := Stab_{H^{i−1}}(i) = { h | h ∈ H^{i−1}, h : i ↦ i }.

Then H = H^{0} ≥ H^{1} ≥ … ≥ H^{z−1} = ⟨1⟩. We shall first make use of the natural 1 − 1 correspondence between the cosets of H^{i} in H^{i−1} and the points in the orbit i^{H^{i−1}} = { j ∈ Ω | ∃ h ∈ H^{i−1} with h : i ↦ j } of the point i under the action of H^{i−1}.

Starting with H we can obtain the orbit of 1 under the action of H by applying in turn the generators of H to 1 and then to the images of 1 until no further image is found. Listing alongside with each point in the orbit the generator that produced it as image of an already known one, we obtain simultaneously coset representatives of the cosets as products of such generators.

Let us demonstrate the Schreier-Sims method using the output provided by the ”low index” method for a particular subgroup, say S, of index 12 in C_{2}. This output tells us that the generators a and b of C_{2} are represented by

φ_{S}(a) = A = (2 4 8 11 12 10 9 5 3 7 6)
φ_{S}(b) = B = (1 2 5 4 3)(6 10 12 11 7)

and that the subgroup S is generated by a^{−1}, b^{2}ab, bab^{2}, and b^{−1}a^{3}b^{−1}.

Since we know that C_{2} : S = ⟨A, B⟩ : φ_{S}(S) = 12, it suffices to find the order of S^{∗} := φ_{S}(S) which is generated by

φ_{S}(a^{−1}) = A^{−1}, …, φ_{S}(b^{−1}a^{3}b^{−1}) = B^{−1}A^{3}B^{−1}.

We therefore compute these products of permutations:

A^{−1} = (2 6 7 3 5 9 10 12 11 8 4)
B^{2}AB = (2 8 7 9 4)(5 6 12 10 11)
BAB^{2} = (3 5 8 6 9)(4 10 11 12 7)
B^{−1}A^{3}B^{−1} = (2 3 10 8 6 5 12 4 7 9 11).

We see that B^{−1}A^{3}B^{−1} = A^{−3}, hence S^{∗} is generated by X := A^{−1}, Y := B^{2}AB, and Z := BAB^{2}. From these we get the orbit of 2 (each first finding of a point in the orbit is underlined):

\begin{matrix}2X = \underline{6} & 6X = & \underline{7} & 8X = \underline{4} & 7X = \underline{3} & 12X = & \underline{11} & 9X = & 10 & 4X = & 2 & 3X = \underline{5} \\ 2Y = \underline{8} & 6Y = & \underline{12} & 8Y = 7 & 7Y = 9 & 12Y = & \underline{10} & 9Y = & 4 & 4Y = & 2 & 3Y = 3 \\ 2Z = 2 & 6Z = & \underline{9} & 8Z = 6 & 7Z = 4 & 12Z = & 7 & 9Z = & 3 & 4Z = & 10 & 3Z = 5 \end{matrix}

At this stage of the computation we see that S^{∗} is transitive on the 11 points 2, …, 12 and from the computation we also have coset representatives T_{2}, …, T_{12} of Stab_{S^{∗}}(2) which we list parallel to the points in the orbit.

2 = 2id  ⇒ T_{2} = id
3 = 7X = 2X^{3}  ⇒ T_{3} = X^{3}  = (2 3 10 8 6 5 12 4 7 9 11)
4 = 8X = 2Y X  ⇒ T_{4} = Y X  = (2 4 6 11 9)(3 5 7 10 8)
5 = 3X = 2X^{4}  ⇒ T_{5} = X^{4}  = (2 5 11 6 9 8 7 10 4 3 12)
6 = 2X  ⇒ T_{6} = X  = (2 6 7 3 5 9 10 12 11 8 4)
7 = 6X = 2X^{2}  ⇒ T_{7} = X^{2}  = (2 7 5 10 11 4 6 3 9 12 8)
8 = 2Y  ⇒ T_{8} = Y  = (2 8 7 9 4)(5 6 12 10 11)
9 = 6Z = 2XZ  ⇒ T_{9} = XZ  = (2 9 11 6 4)(3 8 10 7 5)
10 = 12Y = 2XY^{2} ⇒ T_{10} = XY^{2} = (2 10 11 9 5)(3 12 6 4 7)
11 = 12X = 2XY X ⇒ T_{11} = XY X = (2 11 3 7 5)(6 10 12 9 8)
12 = 6Y = 2XY  ⇒ T_{12} = XY  = (2 12 5 4 8)(3 6 9 11 7)

Having thus found coset representatives of Stab_{S^{∗}}(2) in S^{∗}, we can now invoke a classical theorem of O. Schreier:

Theorem: Let the group G be generated by E := {g_{1}, …, g_{n}}, let U be a subgroup of G, and T = {t_{1}, …, t_{x}} be a set of coset representatives (a ”transversal”) of U in G. Then U is generated by the set of ”Schreier generators”

\{s_{t,g} | s_{t,g} = tg\overline{tg}^{−1}, t ∈ T, g ∈ E\}

where \overline{tg} denotes the coset representative from T of the coset containing the product tg.

In our example, we can obviously now compute these Schreier generators, e. g. for the first generator X, we get the following list:

\begin{aligned}S_{2,X} & = T_{2}X\overline{T_{2}X}^{−1} & = T_{2}XT_{6}^{−1} & = id \\ S_{3,X} & = T_{3}X\overline{T_{3}X}^{−1} & = T_{3}XT_{5}^{−1} & = id \\ S_{4,X} & = T_{4}X\overline{T_{4}X}^{−1} & = T_{4}XT_{2}^{−1} & = (3 9 6 8 5)(4 7 12 11 10) \\ S_{5,X} & = T_{5}X\overline{T_{5}X}^{−1} & = T_{5}XT_{9}^{−1} & = (3 9 6 8 5)(4 7 12 11 10) \\ S_{6,X} & = T_{6}X\overline{T_{6}X}^{−1} & = T_{6}XT_{7}^{−1} & = id \\ S_{7,X} & = T_{7}X\overline{T_{7}X}^{−1} & = T_{7}XT_{3}^{−1} & = id \\ S_{8,X} & = T_{8}X\overline{T_{8}X}^{−1} & = T_{8}XT_{4}^{−1} & = id \\ S_{9,X} & = T_{9}X\overline{T_{9}X}^{−1} & = T_{9}XT_{10}^{−1} & = (3 6 5 9 8)(4 12 10 7 11) \\ S_{10,X} & = T_{10}X\overline{T_{10}X}^{−1} & = T_{10}XT_{12}^{−1} & = (3 9 6 8 5)(4 7 12 11 10) \\ S_{11,X} & = T_{11}X\overline{T_{11}X}^{−1} & = T_{11}XT_{8}^{−1} & = id \\ S_{12,X} & = T_{12}X\overline{T_{12}X}^{−1} & = T_{12}XT_{11}^{−1} & = id \end{aligned}

We see that all the Schreier generators S_{i,X} are powers of the element (3 9 6 8 5)(4 7 12 11 10) and by just doing permutation multiplications the reader can verify that the remaining Schreier generators S_{i,Y} and S_{i,Z} are also powers of this element. Hence the group Stab_{S^{∗}}(2) is cyclic of order 5 and we have |S^{∗}| = 11 · 5 = 55 and |⟨A, B⟩| = 12 · 55 = 660. Moreover ⟨A, B⟩ is twofold transitive, and because of this property and its order ⟨A, B⟩ must be isomorphic to P SL(2, 11).

In our example things were made easy by the fact that Stab_{S^{∗}}(2) turned out to be cyclic. This need not be so easy in general. Indeed the growth of the number of Schreier generators from step to step poses a problem. This is solved - again only stating the basic idea - by the following observation: let at some stage a Schreier generator s be obtained that fixes points 1, …, i−1, that is: s ∈ H^{i−1}, and let s map i to j ≠ i, then s is contained in the coset of H^{i} in H^{i−1} that is characterized by this property. If we have already listed a coset representative r of this coset (obtained, e.g., previously as a Schreier generator) then instead of keeping s, we may keep sr^{−1}, because s and r generate the same subgroup as sr^{−1} and r. However, sr^{−1} will also fix i, hence will be contained in a subgroup ”further down” the stabilizer chain. From this remark we see that we will never have to keep more generators for any subgroup than the maximal number of possible cosets in all the steps of the stabilizer chain, i.e. no more than z + (z − 1) + … + 1 = z(z + 1)/2. Practical implementations again improve greatly on this.

Let us now see, what an implementation of the Schreier-Sims method tells us about Cavicchioli’s group C_{2}. As explained in section 4, we have the permutations φ_{U}(a) and φ_{U}(b) for a representative subgroup U of each of the 24 classes of conjugate subgroups of C_{2} that were found by the low index method. The orders of the permutation groups

⟨ φ_{U}(a), φ_{U}(b) ⟩ ≅ C_{2}/ ∩_{g∈G} U^{g}

obtained by the Schreier-Sims algorithm are given in the second line of the following table:

C_{2} : U  11 12  12  11  12  13
C_{2} : ∩_{g∈G} U^{g} 660 660 95040 11! / 2 12! / 2 13! / 2
No. of classes 2  1  4  8  3  6
No. of kernels  1  2  8  3  6

Since C_{2} was equal to its commutator group, so are the factor groups C_{2}/∩_{g∈G} U^{g}. Comparison with the known list of finite simple groups indeed shows that they are simple and that in a few cases the same normal subgroup of C_{2} was found as intersection of different classes of conjugate subgroups of C_{2}, which explains the last line of the table. What remains are the following different factor groups. Once P SL(2, 11), twice the Mathieu group M_{12}, 8 times A_{11}, 3 times A_{12}, 6 times A_{13}.

Now, if S_{i} = G/N_{i}, i = 1, …, k are simple nonabelian factor groups of a group G with N_{i} ≠ N_{j} for i ≠ j, then G/ ⋂_{i=1}^{k} N_{i} is isomorphic to the direct product ×_{i=1}^{k}S_{i}. So we can conclude that C_{2} has a factor group isomorphic to

P SL(2, 11) × M_{12}^{×2} × A_{11}^{×8} × A_{12}^{×3} × A_{13}^{×6} of order ∼ 1.9 · 10^{153},

a result surely not expected at first sight from the meager looking list of subgroups obtained at the end of section 4.

We close this section by remarking that C. Sims has used refinements of this approach to construct several of the sporadic simple groups as permutation groups. His most spectacular achievement in this field was the construction of the ”Baby-Monster” as a permutation group of degree 13571955000, which of course involved much more theory and very special programming.

6. Reidemeister’s theorem, a modified Todd-Coxeter

method, and more about C_{1} and C_{2}

In the preceding section we have exhibited factor groups of C_{1} and C_{2} that suggest that C_{1} may be finite and C_{2} perhaps not. To show this, we return to Schreier’s theorem which gave us generators for a subgroup U from those of the whole group G and coset representatives of U in G. Since in our application we worked with permutations, this was sufficient. However, if we work with abstract generators, in order to proceed similarly, a defining set of relators for the Schreier generators is needed. This is provided by Reidemeister’s theorem:

Theorem. Let the group G have the finite presentation

G = ⟨ g_{1}, …, g_{n} | r_{1}(g_{i}) = 1, …, r_{m}(g_{i}) = 1 ⟩,

let U ≤ G and T = {t_{1}, …, t_{x}} be a transversal of U in G, then U has the following presentation with respect to the set {s_{t,g}} of Schreier generators:

U = ⟨ s_{t_{l},g_{i}} | τ(t_{l}r_{j}t_{l}^{−1}) = 1, s_{t_{l},g_{i}} = τ(t_{l}g_{i}\overline{t_{l}g_{i}}^{−1}) ⟩

where j = 1, …, m; l = 1, …, x; i = 1, …, n, and where τ is the ”Reidemeister rewriting”. This rewrites a product of the generators g_{i} which lies in U into a product of the Schreier generators of U by the following rule: if

u = g_{i_{1}}^{ε_{1}} ⋯ g_{i_{r}}^{ε_{r}} ∈ U with ε_{j} = ±1,

then

τ(u) = s_{p_{1},g_{i_{1}}}^{ε_{1}} ⋯ s_{p_{r},g_{ir}}^{ε_{r}}

where

p_{j} = \overline{g_{i_{1}} ⋯ g_{i_{j−1}}} if ε_{j} = 1

and

p_{j} = \overline{g_{i_{1}} ⋯ g_{i_{j}}} if ε_{j} = −1.

The correctness of this rewriting is easily seen by just inserting the definition of Schreier generators into the claimed result; for the proof of the theorem the reader is referred to [Joh 80]. For our purpose it is essential to note that Reidemeister rewriting of such a word can be performed, if there is a coset table for the cosets with representatives t_{l}: Since

\overline{g_{i_{1}} ⋯ g_{i_{j}}} = \overline{\overline{g_{i_{1}} ⋯ g_{i_{j−1}}}g_{i_{j}}},

the needed representatives of such products can be looked up recursively in the coset table: if \overline{g_{i_{1}} ⋯ g_{i_{j−1}}} is the representative of a coset with number c, then the number of the coset with representative \overline{g_{i_{1}} ⋯ g_{i_{j}}} is found in the column belonging to the generator g_{i_{j}} in row number c.

Based on this observation, G. Havas has implemented a program which determines the Reidemeister presentation of a subgroup U from its coset table in G. Of course the number of (Schreier-) generators and (Reidemeister-) relations thus obtained will be large (depending on the index of U) and so Havas’ program is equipped with a heuristic program for the elimination of as many as possible of these generators.

Applying Havas’ program to the subgroup S of C_{2} of index 12, used already in section 5, one ends up with the following presentation for the subgroup S on four generators:

S = ⟨ t_{1}, t_{2}, t_{3}, t_{4} | t_{1}t_{2}t_{1}^{−1}t_{2}^{−1} = 1, t_{1}^{5}t_{2}^{−2} = 1, t_{1}^{2}t_{3}t_{1}^{−2}t_{4}t_{3}^{−1}t_{1}t_{4}^{−1} = 1, t_{1}t_{2}t_{4}t_{1}^{−1}t_{3}t_{4}^{−1}t_{2}^{−1}t_{1}^{−1}t_{3}^{−1} = 1, t_{1}^{3}t_{2}t_{4}t_{1}^{−3}t_{2}^{−1}t_{4}^{−1} = 1 ⟩.

If we abelianize, the first and the last relation become trivial and we get the following relation matrix for the commutator factor group S/S′ of S:

( \begin{matrix}\overline{t}_{1} & \overline{t}_{2} & \overline{t}_{3} & \overline{t}_{4} \\ 0 & 0 & 0 & 0 \\ 5 & −2 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ −1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} )

The elementary divisor algorithm transforms this

( \begin{matrix}0 & 0 & 0 & 0 \\ 5 & −2 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ −1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} ) ⟶ ( \begin{matrix}1 & 0 & 0 & 0 \\ 5 & −2 & 0 & 0 \\ −1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} ) ⟶ ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix} )

hence we see that S/S′ is isomorphic to a direct product of a cyclic group of order 2 with two infinite cyclic groups: S/S′ ≅ Z/2Z ⊕ Z ⊕ Z, hence is infinite and hence also C_{2} is an infinite group.

We might use the same program on C_{1} and its subgroup ⟨a⟩ of index 12. Prima facie the number of Schreier generators of the subgroup would be 24. Although, using a special version of Reidemeister’s theorem, this reduces to 13, this is rather inadequate since we know that ⟨a⟩ is cyclic! It is therefore desirable to have an algorithm that will give a presentation for a subgroup with respect to given generators. In fact a modification of the Todd-Coxeter method will do this. Considering the numbers 1, 2, … introduced in it not as denoting cosets but as denoting coset representatives with the neutral element as representative of U we see that the closing of the first subgroup table for a subgroup generator h = h(g_{i}) = g_{i_{1}} … g_{i_{x}} … g_{i_{r}} only yields a consequence of the form kg_{i_{x}} = hl instead of kg_{i_{x}} = l for coset numbers k

and l: g_{i_{1}} … g_{i_{x}} … g_{i_{r}}

\overline{1 … k hl … h1}

Introducing this form of consequences of the closing of a subgroup table into the coset table, further subgroup tables and the relation tables, we see that their entries will also get modified by products of the given subgroup generators. Now in considering the three possible cases that could occur when one has to enter a consequence into the coset table (see section 3) we see that in case (ii) we may have the same coset number but different words w_{1} and w_{2} in the subgroup generators from the new consequence and from the coset table. In such a case w_{1}(h_{j})l = w_{2}(h_{j})l, and we conclude that w_{1}(h_{j})w_{2}(h_{j})^{−1} = 1 is a relation holding for the given subgroup generators. It can be proved (see e.g. [Neu 82] and papers quoted there) that the set of all relations thus arising is a defining set of relations for U with respect to the given generators. The computation is done for C_{1} in the appendix and the 13th and 14th consequences yield that h^{10} = 1, i.e. the subgroup ⟨a⟩ of C_{1} is of order 10. Since the index C_{1} : ⟨a⟩ = 12, the group C_{1} has order 120 and can then easily be identified as being isomorphic to SL(2, 5). It should be mentioned that the implementation of the modified Todd-Coxeter method needs further thoughts in order to keep control of the growing length of the words in the subgroup generators in the case that there are more than one of them (cf [ARo 84]).

7. Using SL(2, .) representations

The study of the complex matrix representations of a group is an essential approach in the theory of finite groups. Here problems on representations translate efficiently into problems about traces of matrices and enter the domain of the theory of characters.

Given a finitely presented group

G = ⟨ g_{1}, …, g_{n} | r_{1}(g_{s}), …, r_{m}(g_{s}) ⟩,

a representation ϕ : G → SL(d, F) is determined by

ϕ(g_{s}) = X_{s} = (x_{ij}^{(s)}) (1 ≤ s ≤ n),

where the entries are solutions of the set of polynominal equations in many variables

det(X_{s}) = 1, r_{i}(X_{s}) = 0, (1 ≤ s ≤ n, 1 ≤ i ≤ m),

for some dimension d, and some field F.

W. Magnus advocates in [Mag 81] the use of representations into SL(2, C) as a tool in combinatorial group theory and expounds on known methods and results, especially on some trace formulas which however do not attain the stature of a general character theory.

We present below some examples where the straightforward study of representations produces definite results for the groups in question.

We define three classes of groups, the second factor groups of the first, and, as shown in (3) below, the third factor groups of the second, which lead to the Cavicchioli groups. For i, j, k, l, q nonzero integers let

\begin{aligned}G(i, j, k) & = ⟨ a, b | a^{i}ba^{j}ba^{k}b^{−1} ⟩, \\ G(i, j, k, l) & = ⟨ a, b | a^{i}ba^{j}ba^{k}b^{−1}, [a, ba^{l}b] ⟩, \\ G(i, j, k, l, q) & = ⟨ a, b | a^{i}ba^{j}ba^{k}b^{−1}, a(b^{−1}a^{−l}b^{−1}a^{l})^{q} ⟩. \end{aligned}

Then, clearly, C_{q} = G(1, −2, 1, −3, q).

(1) Suppose F is a field and

ϕ : G(i, j, k) → SL(2, F)

is a representation such that in the image group

ϕ(a) = A = ( \begin{matrix}α & 0 \\ 0 & α^{−1} \end{matrix} ) , ϕ(b) = B = ( \begin{matrix}β_{11} & β_{12} \\ β_{21} & β_{22} \end{matrix} )

where β_{12}β_{21} ≠ 0. Then we can make β_{21} = 1 by conjugating the image group by

M = ( \begin{matrix}1 & 0 \\ 0 & β_{21} \end{matrix} ) .

We should note that in general ϕ(a) has one of the Jordan canonical forms

( \begin{matrix}α & 0 \\ 0 & α^{−1} \end{matrix} ) , ( \begin{matrix}±1 & 0 \\ 1 & ±1 \end{matrix} )

in some extension of F. Our choice of the first form was done to facilitate the calculations.

The following computations are direct:

A^{i}B = ( \begin{matrix}α^{i}β_{11} & α^{i}β_{12} \\ α^{−i} & α^{−i}β_{22} \end{matrix} ) , BA^{−k} = ( \begin{matrix}β_{11}α^{−k} & β_{12}α^{k} \\ α^{−k} & β_{22}α^{k} \end{matrix} ) ,

A^{i}BA^{j}B = ( \begin{matrix}α^{i+j}β_{11}^{2} + α^{i−j}β_{12} & α^{i+j}β_{11}β_{12} + α^{i−j}β_{12}β_{22} \\ α^{−i+j}β_{11} + α^{−i−j}β_{22} & α^{−i+j}β_{12} + α^{−i−j}β_{22}^{2} \end{matrix} ) .

The relation

A^{i}BA^{j}B = BA^{−k}

is equivalent to the equations:

\begin{aligned}(11) & α^{i+j}β_{11}^{2} + α^{i−j}β_{12} & = & β_{11}α^{−k} \\ (12) & α^{i+j}β_{11}β_{12} + α^{i−j}β_{12}β_{22} & = & β_{12}α^{k} \\ (21) & α^{−i+j}β_{11} + α^{−i−j}β_{22} & = & α^{−k} \\ (22) & α^{−i+j}β_{12} + α^{−i−j}β_{22}^{2} & = & β_{22}α^{k} \end{aligned}

From (12), as β_{12} ≠ 0, we have

(12)′  α^{i+j}β_{11} + α^{i−j}β_{22} = α^{k}

which together with (21) give,

(21)′  α^{2(i−k)} = 1.

Now

\begin{aligned}(11)′ & β_{12} & = & α^{−i+j−k}β_{11} − α^{2j}β_{11}^{2} \\ (12)′′ & β_{22} & = & α^{−i+j+k} − α^{2j}β_{11} , \end{aligned}

which when substituted in (22) give α^{−i+j}(α^{−i+j−k}β_{11}−α^{2j}β_{11}^{2})+α^{−i−j}(α^{−i+j+k}−α^{2j}β_{11})^{2} = (α^{−i+j+k}−α^{2j}β_{11})α^{k}, and this in turn leads to

α^{j+k}(α^{−4k} − 2α^{−2k} + α^{2i−2k})β_{11} = α^{i} − α^{−i}.

Since α^{2i} = α^{2k}, we get

α^{j+k}(α^{−2i} − 1)^{2}β_{11} = α^{i}(1 − α^{−2i});

thus, again using α^{2i} = α^{2k},

(22)′  α^{2i} = 1 or β_{11} = \frac{α^{i−j+k}}{α^{2i} − 1}

Using (12)′′, (11)′ in the determinant equation β_{11}β_{22} − β_{12} = 1 gives the same result as (22)′.

Let us suppose α^{2i} ≠ 1. Then, from (11)′ we get

(11)′′ β_{12} = −\frac{α^{4i} − α^{2i} + 1}{(α^{2i} − 1)^{2}} ,

and from (12)′′ we get

(12)′′′ β_{22} = −\frac{α^{−i+j+k}}{α^{2i} − 1} ;

observe that β_{22} = −α^{−2i+2j}β_{11}.

Hence, we have: For any possible choice α ∈ F such that

α^{2(i−k)} = 1 ≠ α^{2i}

the map

ϕ(a) = ( \begin{matrix}α & 0 \\ 0 & α^{−1} \end{matrix} ) , ϕ(b) = ( \begin{matrix}\frac{α^{i−j+k}}{α^{2i} − 1} & −\frac{α^{4i} − α^{2i} + 1}{(α^{2i} − 1)^{2}} \\ 1 & −\frac{α^{−i+j+k}}{α^{2i} − 1} \end{matrix} )

extends to a representation of G(i, j, k) into SL(2, F).

Let C = A^{j}B. Then, det(C) = 1, and

trace(C) = \frac{α^{i+k} − α^{−i+k}}{α^{2i} − 1} = α^{−i+k} = ±1.

Therefore, the characteristic polynomial for C is

x^{2} − trace(C)x + det C = x^{2} ∓ x + 1, (a factor of x^{3} ± 1).

By the Cayley-Hamilton theorem, C satisfies its characteristic equation; so, C^{3} = ∓I, and hence the order of C is 6 or 3.

(2) We propose to obtain a representation

ϕ̄: G(i, j, k, l) → SL(2, F)

from ϕ of the previous section. For such a purpose, A should commute with BA^{l}B. Now, as A is a diagonal noncentral matrix, BA^{l}B is also a diagonal matrix. By direct calculation, we obtain α^{2(l+i−j)} = 1. Therefore ϕ̄ is a representation for any choice of α such that

α^{2i} ≠ 1 = α^{2(i−k)} = α^{2(l+i−j)}.

Using this as well as α^{2k} = α^{2i}, we obtain

BA^{l}B = ( \begin{matrix}−α^{−l} & 0 \\ 0 & −α^{l} \end{matrix} ) = −A^{−l}, hence (A^{l}B)^{2} = −I.

(3) Let G := G(i, j, k, l, q). Then, the last relation (b^{−1}a^{−l}b^{−1}a^{l})^{q} = a^{−1} implies that a commutes with b^{−1}a^{−l}b^{−1} since by it a is a power of b^{−1}a^{−l}b^{−1}a^{l}, and this shows that G is a factor group of G(i, j, k, l). By substituting A, B in this last relation of G, we conclude that ϕ̄ induces a representation ¯ ϕ̄ : G → SL(2, F) if and only if, in addition to the previous conditions on α,

α^{2ql+1} = (−1)^{q}.

Thus, we have accumulated the following torsion relations:

A^{2ql+1} = (−1)^{q}I, (A^{j}B)^{3} = ±I, and (A^{l}B)^{2} = −I,

which constitute a strong set of relations. It is well-known for instance that

⟨ x, y | x^{5}, y^{3}, (xy)^{2} ⟩ is a presentation for A_{5},

and easily then, the image of C_{1} by ¯ϕ̄ is isomorphic to P SL(2, 5) or SL(2, 5).

(4) To illustrate a line of development in the study of ¯ Ḡ := ¯ ϕ̄(G), we restrict our considerations to finite fields F, and come to the conclusion that if 3|ql and |2ql + 1| > 5, then ¯ Ḡ has an infinite number of non-isomorphic quotient groups of type P SL(2, p^{s}) and hence that ¯ Ḡ is an infinite group. Since C_{q} = G(1, −2, 1, −3, q), the above holds for C_{q}, provided q > 1.

In order to reach such a deep understanding it is not surprising that we have to appeal to the classification of the subgroup structure of P SL(2, p^{s}) by L.E. Dickson (cf [Hup 67], vol. 1, p. 213), which states in part, that the nonsolvable subgroups of P SL(2, p^{s}) are isomorphic to P SL(2, p^{s′}) where s′|s, to P GL(2, p^{s′}) where 2s′|s , or to A_{5} if p = 5 or p^{s} ≡ ±1 (mod 10).

By requiring that 3|ql, the orders of A, A^{j}B, and A^{l}B become relatively prime in SL(2, F) modulo the center ⟨−I⟩. Therefore by abelianization, we see that ¯ Ḡ is a perfect group.

How do we choose finite fields F to fit our purpose? Fix (i, j, k, l, q) such that ijklq ≠ 0, 3|ql, and for N = 2ql + 1,

i ≢ 0 (mod N), k ≡ i (mod N), and j ≡ i + l (mod N).

For every prime p not dividing N, let m(p, N), abbreviated by m, be the minimal natural number such that p^{m} ≡ 1 (mod N) and let F_{p} be the finite field GF (p^{m}). Then, F_{p} contains an element α having the multiplicative order |N|.

For every such choice of F_{p}, the image ¯ Ḡ of

¯ϕ̄: G(i, j, k, l, q) → SL(2, F_{p})

is isomorphic to SL(2, F_{p}). By applying Dickson’s theorem, we have for |N| > 5 that G(i, j, k, l, q) has a factor group isomorphic to

×_{P}P SL(2, F_{p})

for any finite set P of primes p |̸ N. This brings us to the end of the line, and in particular to the infiniteness of the Cavicchioli groups C_{q} for q > 1.

8. Another example, the nilpotent quotient algorithm

The mixture of different methods outlined in the example of Cavicchioli’s groups has been applied successfully in the investigation of several presentations. We mention one of them which needed the invocation of a further very powerful algorithm.

H. Heineken (private communication) posed the problem to investigate the groups H_{1} and H_{2}, defined by the presentations :

H_{1} = ⟨ a, b, c | [a, b] = c, [b, c] = a, [c, a] = b ⟩,
H_{2} = ⟨ a, b, c | [a, [a, b]] = c, [b, [b, c]] = a, [c, [c, a]] = b ⟩.

Both are obviously equal to their respective commutator groups. H_{1} can be shown to be trivial by a Todd-Coxeter run (defining more than 100 coset numbers before this conclusion is reached). Attempts to get the order of H_{2} via the Todd-Coxeter method failed. The ”low index” method produces a class of subgroups of index 5, the Schreier-Sims algorithm shows that the factor group by their intersection N is isomorphic to A_{5}. Reidemeister-Schreier produces a rather complicated presentation for N, abelianizing, one gets that N/N′ is isomorphic to a direct product of 5 copies of the cyclic group of order 2. So now we have a factor group H_{2}/N′ of order 60·2^{5} of H_{2}. Further it can be shown that N/N′ under the action of H_{2} is the direct product of a chief factor N_{2}/N′ of order 2 and a chief factor N_{1}/N′ of order 2^{4}, and that H_{2}/N_{1} is isomorphic to SL(2, 5). The method of SL(2, ·) representations, applied to an extension of H_{2} (using the formula manipulation system MAPLE [MAP85]) shows that this is in fact the only SL(2, ·) factor group of H_{2}.

[figure: N_{1}; H_{2}; N; N_{2}; N′; 2^{4}; 2; 60; SL(2, 5); A_{5}]

The hope to prove H_{2} to be infinite by exhibiting a free abelian factor group of a subgroup of small index, however, has failed. We may ask then, if we can find other factor groups of N. If these are to be nilpotent, then by Burnside’s basis theorem they must be groups of order a power of 2 which can be generated by 5 generators.

A method to find such is the nilpotent quotient algorithm of I.D. Macdonald [Mac 74]. This algorithm constructs inductively for a group G given by a finite presentation

G = ⟨ g_{1}, …, g_{n} | R ⟩

(where R is a finite defining set of relations for G) and for a given prime p the factor groups of the ”descending p-central series” defined by

G_{0} := G, G_{i} := [G_{i−1}, G]G_{i−1}^{p}.

(Here the relative commutator group [U, V] of two subgroups U and V of G is the normal closure of the set of all commutators [u, v], u ∈ U, v ∈ V, and U^{p} is the normal closure of the set of p^{th} powers of the elements of U. If G_{k} = ⟨1⟩ but G_{k−1} ≠ ⟨1⟩, we shall say that G is of p-class k. For each factor group G/G_{i} a special kind of presentation will be constructed that we first have to discuss.

Let P be a p-group and

P_{0} := P > P_{1} > … > P_{r} = ⟨1⟩

be a series of normal subgroups P_{i} ⊲ P such that P_{i−1}/P_{i} is of order p and contained in the centre of G/P_{i}, then this is called a p-step central series of P. Choosing for each i = 1, …, r an element a_{i} such that ⟨P_{i}a_{i}⟩ = P_{i−1}/P_{i}, we obtain a generating set {a_{1}, …, a_{r}} of P for which defining relations of the form

a_{i}^{p} = a_{i+1}^{ν_{i,i+1}} ⋯ a_{r}^{ν_{i,r}} for i = 1, …, r

(*)

[a_{j}, a_{i}] = a_{j+1}^{ν_{j,i,i+1}} ⋯ a_{r}^{ν_{j,i,r}} for j > i

can be found. Each element in P can be written in the form

a_{1}^{α_{1}} ⋯ a_{r}^{α_{r}} with 0 ≤ α_{i} < p,

and multiplication of two elements in this form can be performed by ”collecting” the product into such a form using the relations in a fashion similar to that explained in section 2 for the dihedral groups.

Now any set of relations of the form (*) clearly defines a p-group of order ≤ p^{r}. That it need not be of order p^{r} is seen by the example of the presentation

⟨ a_{1}, a_{2}, a_{3} | a_{1}^{2} = a_{2}, a_{2}^{2} = a_{3}, a_{3}^{2} = 1, [a_{2}, a_{1}] = a_{3}, [a_{3}, a_{1}] = 1, [a_{3}, a_{2}] = 1⟩.

The group defined by it is not of order 2^{3} but of order 2^{2}, and this is seen in a systematic way by evaluating a_{1}^{3} in two ways:

a_{1}a_{2} = a_{1}a_{1}^{2} = a_{1}^{3} = a_{1}^{2}a_{1} = a_{2}a_{1} = a_{1}a_{2}[a_{2}, a_{1}] = a_{1}a_{2}a_{3},

and so a_{3} = 1.

Calling a presentation (*) ”consistent” if it defines a p-group of order p^{r}, one can prove that one can check consistency by analogous systematic two-way evaluation of a finite set of test words of the forms

a_{i}^{p+1}, a_{j}a_{i}^{p}, a_{j}^{p}a_{i}, and a_{k}a_{j}a_{i} with k > j > i.

(See [New 76] for details).

Having defined these terms we can now state that the nilpotent quotient algorithm determines recursively a consistent presentation of form (*) for each factor group G/G_{i} of the descending p-central series of G.

Consider again a finitely presented group

G = ⟨ g_{1}, …, g_{n} | R ⟩.

G/G_{1} is the largest elementary abelian p-factor group of G, so it can be obtained by performing the elementary divisor algorithm modulo p. This will yield a presentation

(1) G/G_{1} = ⟨ a_{1}, …, a_{d} | a_{i}^{p} = 1, [a_{j}, a_{i}] = 1 ⟩

where the a_{i} may be chosen from the cosets ḡ_{i} = G_{1}g_{i} of the generators g_{i} of G in the given presentation. Note that by Burnside’s basis theorem the minimal number of generators of any p -factor group G will be at most d. G/G_{1} also has a presentation

(2) G/G_{1} = ⟨ g_{1}, …, g_{n}, a_{1}, …, a_{d} | R, g_{i} = ∏ a_{k}^{ν_{k}}, a_{k}^{p} = 1, [a_{j}, a_{k}] = 1 ⟩

in which for each a_{k} there will be a relation a_{k} = g_{i_{k}}. These will be called the ”definitions” of the a_{k} and will not be changed in the sequel.

The computation of G/G_{2} from G/G_{1} (and quite analogously G/G_{i} from G/G_{i−1}) is now done in three steps.

(i) For the first step we define a p-cover C(H) of a p-group H of p-class b to be a p-group K of p-class b + 1 with K/K_{b} ≅ H, which is maximal with this property. A presentation for the p-cover C(G/G_{1}) is obtained from the presentation (1) of G/G_{1} by modifying all relations in (1) that are not definitions into congruences modulo newly introduced central generators a_{k} of order p.

(ii) The presentation of C(G/G_{1}), so obtained, is of form (*) but need not be consistent. Evaluating the consistency testwords, we get a finite number of equations between the newly introduced generators. Since these are all central of order p, we thus have to solve a system of homogeneous linear equations over the field of p elements in order to eliminate redundant generators and to get a consistent presentation of type (*) for C(G/G_{1}).

(iii) In a third step, those relations in (2) that express the g_{i} in terms of the a_{k}, and that are not tabooed as being definitions of the a_{k}, are also modified by new generators (made central and of order p). Then these expressions for the g_{i} are used to eliminate the g_{i}, that is, to write the relations R in terms of a_{k}’s. These are then collected and possibly lead to further homogeneous linear equations between the newly introduced generators and hence to further eliminations.

After the three steps, we now have a consistent presentation for G/G_{2} of type (*) and can start the construction of G/G_{3} and so on. This nilpotent quotient algorithm has had its most interesting applications to Burnside groups, it was used e.g. by M. F. Newman and G. Havas to show that the restricted Burnside group B̄(4, 4), i.e. the largest nilpotent group on 4 generators, having exponent 4, has order 2^{422}. See [HaN 80] for a report on these applications as well as for a good description of the method.

Applying this nilpotent quotient algorithm to the presentation of the normal subgroup N of Heineken’s group H_{2}, we obtain that N has a maximal 2-factor group of order 2^{24}, so altogether we have a factor group of order 60 · 2^{24} of H_{2}. At this point we have reached the end of present day’s exploration of H_{2}, several attempts to investigate presentations of other subgroups have not brought any further information, so we may very well be at the end of today’s computational possibilities without having been able to settle the question if H_{2} is in fact of order 60 · 2^{24} or perhaps even infinite.

New methods, e.g. for finding soluble quotients have recently been proposed and are presently being implemented, may be they will allow us to tell more about this and other groups.

So this example may serve to show that the methods of computational group theory of course have their limits, but also that it is a field still very much in development and open for new ideas.

9. Implementations and computers^{2}

All methods that have been mentioned in this article have been implemented, in most cases with many improvements and refinements too technical to be described here, as well as many other algorithms in computational group theory. The most comprehensive system of group theoretical programs is CAYLEY [Can 84]; it builds on the storage management system STACKHANDLER and has its own problem oriented language which can be used to write programs combining the algorithms implemented in the system. CAYLEY has originally been written in FORTRAN, nowadays a translation into C is available. More specialized systems are CAS [NPP 84] for the interactive work with characters, SOGOS [LNS 84] for working with soluble groups, and SPAS for the calculation with presentations, containing i.a. Todd-Coxeter, Modified Todd-Coxeter, Reidemeister-Schreier and Low-Index methods. CAMAC is a system for the application of group theory in combinatorics and coding theory.

2This section has been revised and updated by the first author on June, 7^{th}, 1989.

A new system, GAP, has recently been released which is designed in a different way. It has a small kernel, written in C that contains dynamic storage management, an interpreter of the GAP language, and basic operations. The GAP language is a PASCAL-like programming language with special datatypes such as permutations, finite field elements, vectors, and matrices. The programming language allows to write algorithms in their most general setting, e.g. the same piece of code could be used to compute the orbit of a point under a permutation group, of a vector under a matrix group, or the conjugacy class of an element in any kind of group. An interactive programming environment eases writing, debugging and improving programs. It allows, for example, to trace program execution, to inspect the situation in great detail after an error has occured, or to time the execution to identify the time critical parts. GAP comes with a library of group theoretical algorithms for computing with groups, e.g. for finding the centralizer of an element in a permutation group. All the algorithms are written in the GAP programming language, and thus can easily be modified by the user if necessary.

While CAYLEY is sold commercially for several thousand dollars, the other systems are distributed freely for refund of the cost of the material, i.e. the floppy or cartridge and the manual.

Contact addresses are:

CAYLEY:  J. Cannon, Department of Pure Mathematics,

University of Sydney, Sydney, NSW 2006, Australia.

CAS, SOGOS, J. Neubüser, Lehrstuhl D für Mathematik, RWTH,
SPAS, GAP: D5100 Aachen, West Germany.
CAMAC:  J. Leon, Department of Mathematics,

University of Illinois at Chicago, Box 4348, Chicago, Ill. 60680, USA.

In addition to these, there exist ”stand-alone” implementations of single algorithms. In addition to the ones given above a good address (e.g. for Todd-Coxeter, nilpotent quotient etc.) is:

G. Havas: Key Center for Software Technology, Department of Computer Science, University of Queensland, St. Lucia, Queensland 4067, Australia.

All these programs run very well on workstations having something like ≥ 40 MByte accessible through virtual store management and a CPU equivalent to a Motorola 68020. UNIX is becoming the operating system of choice for many implementations, but there are e.g. VAX implementations under VMS for CAYLEY, CAS, SOGOS, SPAS, and GAP. Because of its structure GAP works on even smaller computers like MAC II and ATARI ST.

10. An epilogue

The methods of ”computational group theory”, of which only a few could be sketched in this paper, as well as those of ”computer algebra” dealing with polynomial arithmetic and integration of functions and differential equations in closed form have become powerful tools in research. Therefore they should also find their place in teaching mathematics. This does not necessarily mean the introduction of new courses, the discussion of such methods can be integrated into the existing ones, enriching them with algorithmic aspects. Moreover, at the graduate level, students can learn to both implement and use such methods in the context of their masters theses.

In Brazil, universities will soon face the problem that they will have to train a majority of their MSc students for later work in industry, as is already the case in highly industrialized countries. If pure mathematics is to play its rôle in this, such a combination of acquiring the abilities of logical analysis and reasoning that the training as a mathematician has always given with the skills of the use of the computer for their application, will be ideal for this aim.

11. Appendix

The appendix contains the calculation of the modified coset table for the group C_{1} with subgroup U = ⟨a⟩.

Definitions, consequences, the elimination of coset number 9 and the finding of the relations for the subgroup generator are listed in a protocole in the order in which they occur. Definitions and consequences are numbered separately by D1, …, and C1, …, respectively.

In the relation tables, places that yield consequences are underlined. Each new consequence is marked with its number in the protocole, which is put at the end below the underlining. Duplications of already known consequences are underlined by dashed lines. The conseqences yielding the defining relator for the subgroup generator are underlined with dotted lines.

In the coset table, definitions are underlined, entries that are consequences are marked with the number of the respective consequence in the protocole.

Before the coset number 9 is eliminated, it occurs in several places in the relation tables. There it is crossed out and its replacement is put next to it.

If all entries are stripped of the powers of h, the original Todd-Coxeter procedure is regained.

C_{1} = ⟨ a, b | a^{−2}bab^{−1}ab = 1, a^{3}b^{−1}a^{−2}b^{−1} = 1 ⟩, U = ⟨a⟩, h := a

Subgroup table

a / (1 h1)

First relation table

a^{−1}  a^{−1}  b  a  b^{−1}  a  b
1 h^{−1}1  h^{−2}1  h^{−2}2  h^{−2}4  h^{−3}4  3  1

2

2  6  h^{−2}7  h^{−1}6  h^{−1}2  h^{−1}1  1  2

4

3 h^{−3}4  h^{−3}2  h^{−3}5  h̸^{−3} 9̸ h8  h^{−4}5  8  3

7

4  2  6  h^{−1}10  h^{−1}5  h^{−1}2  h^{−1}4  4

5

5 10  13  h^{−1}13  h^{−1}10  6  2  5

11

6 h^{−2}7  h^{−2}3  h^{−2}1  h^{−1}1  h^{−1}3  h^{−1}7  6 - - - - - - - -
7  3  h^{−3}4  h^{−2}4  h3  h8  11  7

8

8 h^{−4}5  h^{−4}10  h^{−4}12  h^{−5}12  h^{−5}10  h^{−5}5  8

9

9̸  5̸  1̸0̸  9̸
10 13  h^{−2}11  h^{−2}7  6  h^{−1}7  h6  10
11 h8  h^{−3}5  h^{2}8  h11  h^{−4}12  h^{−5}12 11 - - - - - - - - -
12 h12  h^{2}12  h^{7}11  h^{9}13  h^{10}13  10  12 ........................ 13
13 h^{−2}11  h^{−1}8  h^{−1}3  h^{−1}7  h^{−1}11  h13  13

12

Second relation table

a  a  a  b^{−1}  a^{−1}  a^{−1}  b^{−1}
1 h1  h^{2}1  h^{3}1  h^{3}3  4  2  1

1

2  4  h^{3}3  h^{3}7  h^{3}11  9̸ h^{4}8  5  2 - - - - - - - - - - - -
3  7  h^{2}6  h^{2}2  h^{2}1  h1  1  3

3

4 h^{3}3  h^{3}7  h^{5}6  h^{4}7  h^{4}3  h4  4 - - - - - - - - - - -
5 9̸ h^{4}8  h^{3}11  h^{5}13  h^{6}13  h^{4}11  h^{5}8  5 - - - - - - - - - - - -
6  2  4  h^{3}3  h^{3}8  h^{−1}5  h^{−1}10 6

6

7 h^{2}6  h^{2}2  h^{2}4  h4  h2  h6  7 - - - - - - - -
8 h^{−1}11  h13  h10  h^{2}6  7  3  8 - - - - - - - - - -
9̸  9̸
10  5  h^{4}8  h^{3}11  h^{−2}12  h^{−1}12  12  10

10

11 h^{2}13  h^{2}10  h^{2}5  h^{2}2  h^{2}6  7  11 - - - - - - - - - - -
12 h^{−1}12 h^{−2}12 h^{−3}12 h^{−3}10  h^{−3}13  h^{5}11 12 .......................... 14
13 10  5  h^{4}8  h^{−1}5  h^{−1}10  h^{−1}13 13

Coset table

a  b  a^{−1}  b^{−1}
1 h1_{0}  \underline{2}  h^{−1}1_{0}  \underline{3}
2  \underline{4}  \underline{5}  \underline{6}  \underline{1}
3  \underline{7}  \underline{1}  h^{−3}4_{1}  \underline{8}
4 h^{3}3_{1}  h4_{2}  \underline{2}  h^{−1}4_{2}
5 9̸ h^{4}8_{6} h^{5}8_{7}  \underline{10}  \underline{2}
6  \underline{2}  h^{−1}10_{5} h^{−2}7_{3} h^{−1}7_{4}
7 h^{2}6_{3}  h6_{4}  \underline{3}  \underline{11}
8 h^{−1}11_{8}  \underline{3}  h^{−4}5_{6} h^{−5}5_{7}
9̸  \underline{5̸}
10  \underline{5}  \underline{12}  \underline{13}  h6_{5}
11 h^{2}13_{12}  \underline{7}  h8_{8} h^{−5}12_{10}
12 h^{−1}12_{9} h^{5}11_{10} h12_{9}  \underline{10}
13  \underline{10}  h^{−1}13_{11} h^{−2}11_{12} h13_{11}

Protocol (D=Definition, C=Consequence)

C0 1a = h1, 1a^{−1} = h^{−1}1
D1 1b  =: 2
D2 1b^{−1} =: 3
D3 2a  =: 4
C1  3a^{−1} = h^{−3}4, 4a  = h^{3}3
C2  4b^{−1} = h^{−1}4, 4b  = h4
D4 2b  =: 5
D5 2a^{−1} =: 6
D6 3a  =: 7
C3  7a = h^{2}6, 6a^{−1} = h^{−2}7
C4 7b = h6, 6b^{−1} = h^{−1}7
D7 3b^{−1} =: 8
D8 5a  =: 9
D9 5a^{−1} =: 10
C5  6b = h^{−1}10, 10b^{−1} = h6
\begin{matrix}C6  8a^{−1} = h^{−4}5, 5a  = h^{4}8 \\ from coset table 5a  =  9 \end{matrix} \} ⟹ 9 = h^{4}8
C7  8b^{−1} = h^{−5}5, 5b  = h^{5}8
D10 7b^{−1} =: 11
C8 11a^{−1} = h8, 8a = h^{−1}11
D11 10b =: 12
C9  12a = h^{−1}12, 12a^{−1} = h12
C10  11b^{−1} = h^{−5}12, 12b = h^{5}11
D12 10a^{−1} =: 13
C11  13b = h^{−1}13, 13b^{−1} = h13
C12  13a^{−1} = h^{−2}11, 11a = h^{2}13

\begin{matrix}C13 h^{10}13a = 10 \\ from coset table 13a = 10 \end{matrix} \} ⟹ \underline{h^{10} = 1}

\begin{matrix}C14 h^{−3}13a^{−1} = h^{5}11 \\ from coset table h^{−3}13a^{−1} = h^{−5}11 \end{matrix} \} ⟹ \underline{h^{10} = 1}

12. Bibliography

[Atk 84] M.D. Atkinson, ed., Computational group theory. Academic Press, London (1984).

[ARo 84] D.G. Arrell, E.F. Robertson, A modified Todd-Coxeter Algorithm. pp. 27-32 in [Atk 84].

[Can 84] J.J. Cannon, An introduction to the group theory language, Cayley. pp. 145-183 in [Atk 84].

[Cav 86] A. Cavicchioli, A countable class of non-homeomorphic homology spheres with Heegard genus 2. Geom. Dedicata 20 (1986) 345-348.

[Deh 11] M. Dehn, Über unendliche diskontinuierliche Gruppen. Math. Annalen 71 (1911) 116-144.

[Hac 86] D. Hacon, O invariante de Jones e outros invariantes de nos. Matematica Universitaria No 3 (1986) 61-83.

[HaN 80] G. Havas, M.F. Newman, Application of computers to questions like those of Burnside. Lecture Notes in Math. 806, Springer, Berlin (1980) 211-230.

[Hup 67] B. Huppert, Endliche Gruppen I. Springer-Verlag (1967).

[Joh 80] D.L. Johnson, Topics in the theory of group presentations. LMS Lecture Notes Series 42, Cambridge U.P. (1980).

[Leo 80a] J.S. Leon, Finding the order of a permutation group. pp. 511-517 in: B. Cooperstein, G. Mason, eds.: Proc. Symp. Pure Math. 37, AMS (1980).

[Leo 80b] J.S. Leon, On an algorithm for finding a base and a strong generating set for a group given by generating permutations. Math. Comp. 35 (1980) 941-974.

[LNS 84] R. Laue, J. Neubüser, U. Schoenwaelder, Algorithms for finite soluble groups and the SOGOS system. pp. 105-135 in [Atk 84].

[Mac 74] I.D. Macdonald, A computer application to finite p-groups. J. Austral. Math. Soc. 17 (1974) 102-112.

[Mag 81] W. Magnus, The uses of 2 by 2 matrices in combinatorial group theory. A survey. Resul. der Mat. 4 (1981) 171 - 192.

[MAP 85] B.W. Char, K.O. Geddes, G.H. Gonnet, S.M. Watt, MAPLE Reference Manual. Symbolic Computation Group, Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1 (1985).

[Neu 82] J. Neubüser, An elementary introduction to coset table methods in computational group theory. pp. 1-45 in: C. Campbell, E. Robertson, eds.: Groups St. Andrews 81, LMS Lecture Note Series 71, Cambridge U.P. (1982).

[New 76] M.F. Newman, Calculating presentations for certain kinds of quotient groups, pp. 2-8 in: R.D. Jenks, ed.: SYMSAC 76, Assoc. Comp. Mach., New York, (1976).

[NPP 84] J. Neubüser, H. Pahlings, W. Plesken, CAS; Design and use of a system for the handling of characters of finite groups. pp. 195-247 in [Atk 84].

[Nov 55] P.S. Novikov, On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. im Steklov 44 (1955) 143pp; AMS Translations, ser. 2, 9 (1958) 1-122.

[Rab 58] M.O. Rabin, Recursive unsolvability of group theoretic problems. Ann. of Math., 67 (1958) 172-194.

[ToC 36] J.A. Todd, H.S.M. Coxeter, A practical method for enumerating cosets of a finite abstract group. Proc. Edinburgh Math. Soc. 5 (1936) 26-34.