A cohomological criterion for a finitely presented group to be infinite

D.F.Holt^{∗}  W.Plesken

1 Introduction

The problem of proving that a given finitely presented group G is infinite can be very difficult (or impossible) in general, but there are several possible approaches that can be tried, some of which can be rendered much more effective with the assistance of computers. To this list, we add another one, which can be applied if an epimorphism of G onto a finite group H is known. The idea depends on the following criterion.

Criterion 1 If M is any IQH-module, and H^{1}(G, M) ≠ 0 (with the induced action of G on M), then G is infinite.

This criterion is also true of course if H is infinite, but our aim is to apply it to examples in which H is finite. It will be proved in Section 2. The idea is that, when H^{1}(G, M) ≠ 0, the epimorphism ϕ of G onto H can be lifted to an epimorphism of G onto an extension of an infinite torsion free abelian group by H. This means that we are in fact proving that, if K is the kernel of ϕ, then K/[K, K] is infinite. This is in common with the Reidemeister-Schreier approach to the problem (see, for example [Hav 73] or [Neu 81]), in which a presentation for a subgroup S of G is found, which is then abelianized and the invariant factors of S/[S, S] are computed. However, we are able to handle much larger indices |G : K| than would be feasible with the Reidemeister-Schreier approach. In some cases, we can show theoretically that H^{1}(G, M) is nontrivial for a suitable module, and in other cases, provided that we have explicit matrices for M and the dimension is not too big, we can compute H^{1}(G, M) by machine.

Our method turns out to be particularly effective for presentations in which the relators are all proper powers. We demonstrate it, by applying it to some presentations which are derived from some hyperbolic Von Dyck groups, by adjoining a power of another short word. We are able to prove the following result.

Theorem 1 (i) The groups ⟨x, y|x^{2}, y^{3}, (xy)^{7}, [x, y]^{n}⟩ are finite for n ≤ 8, and infinite for n ≥ 9, with the possible (but highly unlikely) exception of n = 11;

(ii) The groups ⟨x, y|x^{2}, y^{4}, (xy)^{5}, (xy^{2})^{n}⟩ are finite for n ≤ 5 and infinite for all n ≥ 6;

(iii) The groups ⟨x, y|x^{3}, y^{3}, (xy)^{4}, (xy^{−1})^{n}⟩ are finite for n ≤ 5 and infinite for all n ≥ 6.

∗supported by Alexander von Humboldt-Stiftung

In order to prove this, we have to find some general methods of handling large values of n, and deal individually with the smaller values. The individual cases are dealt with in Section 3, along with a brief description of some computer programs that we used for this purpose. Of course, these results are dependent on the results of computer calculations. As we shall see in Section 2, when n is sufficiently large, it suffices to find any finite epimorphic image of G in which the images of the words of which the relators are powers actually have the orders specified by the relators - in other words, the presentation does not totally or partially collapse. We shall describe two approaches to this problem. The first, described in Section 4, is to use coset diagrams to produce finite permutation representations of the groups, and with this method we are able to deal with all but finitely many n. The second, is to attempt to map the groups onto P SL(2, q) for suitable q. This reduces to the solution of some quadratic equations in the finite field, and it turns out that, for a given n, only finitely many q can arise. This enables us to deal easily with any particular n, but a general result would involve proving that certain elements in cyclotomic number fields are not units, which we are currently unable to do.

Part(i) of this theorem has now been proved independently by completely different methods by Howie and Thomas [HoT 90] (where additional historical references to this problem and its connection with a conjecture of Coxeter can be found). Using an extension of those methods, Edjvet was finally able to prove that this group is also infinite for n = 11 [Edj 90].

2 General Theory of the Method

Let G = ⟨x_{1}, ..., x_{l}|w_{i}(x_{1}, ..., x_{l}) = 1 for i = 1, ..., m⟩ be a finitely presented group and H and ϕ as in the introduction. The proof of Criterion 1.1 is very simple. If G is finite of order k, then by Corollary 1, page 91 of [Gru 70], kH^{q}(G, M) = 0 for any q > 0 but, since M is a IQG-module and k is invertible in IQ, this implies that H^{q}(G, M) = 0. Hence, if H^{1}(G, M) ≠ 0, then G is infinite. However, in the present context, a group-theoretical interpretation is appropriate. Let K be the kernel of the epimorphism ϕ : G ⟶ H with H finite.

Lemma 1 If H^{1}(G, M) ≠ 0 for some IQG-module M, then the derived subgroup K′ of K is of infinite index in K, and hence in G. More precisely, IQ ⊗_{ZZ} K /K′ and M have a common irreducible IQH- constituent.

Proof: The inflation-restriction sequence (see Proposition 3, page 93 of [Gru 70]) yields the exact sequence 0 ⟶ H^{1}(H, M) ⟶ H^{1}(G, M) ⟶ Hom_{I QH} (K/K′, M). Since H is finite, H^{1}(H, M) = 0, as above, and so Hom_{I QH} (K/K′, M) ≠ 0. q.e.d.

Actually, in the language of lifting an epimorphism G ⟶ H to a homomorphism G ⟶ H M with image not isomorphic to H, the method was already advocated in Section 6 of [Ple 87] and Section 7.5 of [HoP 89]. Although the criterion is universally applicable, more detailed information can be given in special situations.

Definition 1 For a relator w = w(x_{1}, ..., x_{l}) of G, the M-rank r_{M}(w) is defined as the rank of the matrix M(w) := ( w∂_{1}D ; ⋮ ; w∂_{l}D ), where ∂_{i} : F ⟶ ZZF is the Fox-derivative of

the free group F on x_{1}, ..., x_{l} with respect to i (i.e. x_{j}∂_{i} = 0 for j ≠ i and x_{i}∂_{i} = 1), and where D is the matrix representation of F for the IQH-module M, with respect to some basis, and the H-action is pulled back to F via F ⟶ G ⟶ M.

Here, we are regarding M(w) as an ld × d matrix, where each entry w∂_{i}D is a d × d matrix, and dim(M) = d. As explained on page 103 of [HoP 89] (cf. also [Zas 48]), the matrices M(w_{1}), …, M(w_{m}) describe the set of linear equations for the space Der(G, M) of derivations from G to M. More precisely, let ν : G ⟶ M be a derivation, with x_{i}ν = m_{i}. Then the conditions w_{j}ν = 0 for j = 1, …, m reduce to the following system of md linear equations in ld unknowns:

∑_{i=1}^{l} m_{i}(w_{j}∂_{i})D = 0, j = 1, ..., m.

Proposition 1 Let f be the dimension of the subspace of H-fixed points of M, and dim(M) = d. If

∑_{i=1}^{m} r_{M}(w_{i}) < f + (l − 1)d ,

then H^{1}(G, M) ≠ 0.

Proof: Clearly the dimension of InnDer(G, M) (the space of inner derivations from G to M) is equal to d − f, and dim(Der(G, M)) = ld − rank (M(w_{1}) … M(w_{m})) ≥ ld − ∑_{i=1}^{m} r_{M}(w_{i}). Since H^{1}(G, M) = Der(G, M)/InnDer(G, M), this yields dim(H^{1}(G, M)) ≥ (l − 1)d + f − ∑_{i=1}^{m} r_{M}(w_{i}). q.e.d.

To compare this method with the Reidemeister-Schreier method (mentioned in the introduction) for proving a group infinite, we consider the case in which M is a (transitive) permutation module. Such a module has the form IQ_{T}^{H}, where T is a subgroup of H. Let S be the complete inverse image of T in G. Then, as a IQGmodule, M = IQ_{S}^{G}, and by Shapiro’s Lemma (Theorem 2, page 92 of [Gru 70]), we have H^{1}(G, M) ≅ H^{1}(S, IQ) ≅ Hom(S/S′, IQ). Hence the dimension of H^{1}(G, M) is equal to the number of torsion free cyclic factors of S/S′, which is precisely what is calculated by the Reidemeister-Schreier method. The method advocated here seems somewhat simpler (at least theoretically), because it does not involve the intermediate step of finding a presentation of S; it proceeds immediately to the appropriate system of linear equations. However, the principal computational problem that arises seems to be the same in both cases, when the index of S in G grows large; namely integer overflow. Perhaps the main advantage of our method is that we have considerably more freedom in our choice of module. Once we have found a good candidate for H, we can work either theoretically or computationally with any IQH-module and, if we do choose to work with a permutation module (which is often convenient), then we can work directly from the appropriate permutation representation; we do not need to find generators for S, for example.

If the relator w is a proper power of a word, then an upper bound for r_{M}(w) can be estimated from information that is usually available.

Proposition 2 Assume that w = w̃(x_{1}, ..., x_{l})^{a} with a ≥ 2, and let m be the multiplicity of 1 as an eigenvalue of w̃D. Then r_{M}(w) ≤ m.

Proof: M(w) = ( w̃∂_{1}D ; ⋮ ; w̃∂_{l}D ) (1+w̃+...+w̃^{(a−1)})D. But rank (1+w̃+...+w̃^{(a−1)})D = m,

and hence rank (M(w)) ≤ m. q.e.d. As a first application, one gets:

Theorem 2 Let G = ⟨x_{1}, ..., x_{l}|w̃_{i}(x_{1}, ..., x_{l})^{a_{i}} = 1, for i = 1, ..., m⟩ with a_{i} ≥ 2 for each i. Let ϕ be an epimorphism onto a finite group H such that w̃_{i}ϕ has order a_{i} for all i. If

∑_{i=1}^{m} \frac{1}{a_{i}} ≤ l − 1,

then G is infinite.

Proof: Let M = IQH be the regular IQH-module and w_{i} = w̃_{i}^{a_{i}}. Then, by Proposition 2.4, r_{M}(w_{i}) ≤ |H|/a_{i} and, since f = 1 and d = dim(M) = |H| in Proposition 2.3, we get ∑_{i=1}^{m} r_{M}(w_{i}) ≤ |H| ∑_{i=1}^{m} \frac{1}{a_{i}} ≤ (l − 1)|H| < (l − 1)d + 1, and the result follows from Proposition 2.3. q.e.d.

When the hypotheses of this theorem do not hold, we can still sometimes apply (2.3) and (2.4) by using the character of a particular IQH-module.

Example 1 G =< x, y|x^{2}, y^{3}, (xy)^{7}, [x, y]^{9} > is infinite.

Proof: It can be checked that the map x ↦ (1, 3)(2, 9)(4, 5)(6, 7), y ↦ (1, 2, 3)(4, 5, 6)(7, 8, 9) is an epimorphism onto H = P SL(2, 8), and that the images of x, y, xy and [x, y] have orders 2, 3, 7 and 9, respectively. By looking at the character table of H, we find that there is a 7-dimensional rational irreducible character χ_{M}, which takes values −1, −2, 0, and 1 on the elements of orders 2, 3, 7 and 9, respectively. Hence ∑_{i=1}^{m} r_{M}(w_{i}) ≤ 3 + 1 + 1 + 1 = 6 < 7 = d − f, and the result follows from Proposition 2.3. q.e.d.

3 The proof of Theorem 1.2 for small n

The remainder of this paper is devoted to the proof of Theorem 1.2. We shall give the most details for part (i). The proofs of (ii) and (iii) are similar but more straightforward. Let us denote the groups defined in (i), (ii) and (iii) of the theorem by G(1, n), G(2, n) and G(3, n), respectively.

The proofs were carried out with the assistance of two computer programs written by the authors, together with Todd-Coxeter coset enumeration and the low index subgroup program, which are available in CAYLEY, for example. The first of the authors’ programs, which is also mentioned in Chapter 7 of [HoP 89], finds epimorphisms of a given finitely presented group G onto a given permutation group H, and is applicable (at any rate for two-generator groups G) to groups H of order up to at least 10^{6}, provided that representatives of the conjugacy classes of H are known. This program, together with the low index subgroup program was used to find epimorphisms ϕ of the groups G(i, n) onto suitable finite groups H. (The cases in which H is an alternating group were found from the corresponding low index subgroups of H.) In the cases in which H = P SL(2, q) for some q, the method described in Section 5 was used to determine the appropriate q.

The second program computes H^{1}(G, M), as described in Section 2, where M is a module for H, either over the rational numbers or over a finite field of prime order. The finite field computation is useful for two reasons. Firstly, if it turns out that H^{1}(G, M) = 0 for all rational modules, but |H^{1}(G, M)| > |H^{1}(H, M)| for a finite module M, then we can construct an epimorphism of G onto a larger finite group (namely, an extension of M by H), and try again with the new group in place of H. This technique was used, for example, to help handle the cases G(1, 12), G(2, 8) and G(3, 6), below. Secondly, for rational modules M of large dimension in which integer overflow occurs, we can, in practice, determine the dimension of H^{1}(G, M) by computing H^{1}(G, M ⊗_{I Q} F_{p}) for a few large primes p. However, this technique was used mainly to rule out various possibilities, and the final proof does not rely on its use. A special version of this program has been written for permutation modules. For the examples of Theorem 1.2, it can handle such modules of degree several thousand. For a particular group H for which the character table is known, it is often possible to find a set of permutation modules of manageable degrees, which together cover all of the rational irreducible representations of H. (This is the case for the first Janko group, for example.) Of course, for those values of n for which the theorem was proved using this program, we can only report the result of running the program.

By using Todd-Coxeter coset enumeration, we find that G(1, n) is finite for n ≤ 8 and G(2, n) and G(3, n) are finite for n ≤ 5. In fact G(1, 1), G(1, 2), G(1, 3), G(1, 5), G(2, 1), G(2, 3), G(3, 1) and G(3, 2) are trivial |G(1, 4)| = 168, |G(1, 6)| = |G(1, 7)| = 1092, |G(1, 8)| = 10752, |G(2, 2)| = 10, |G(2, 4)| = 160, |G(2, 5)| = 360, |G(3, 3)| = 48, |G(3, 4)| = 168 and |G(3, 5)| = 1080. Since G(1, 4), G(1, 6), G(1, 7), G(1, 8), G(2, 5), G(3, 4) and G(3, 5) are perfect, we can easily identify them, and the other examples are all soluble. We find that G(1, 4) ≅ G(3, 4) ≅ P SL(2, 7), G(1, 6,) ≅ G(1, 7) ≅ P SL(2, 13), G(2, 5) ≅ A_{6}, G(3, 5) is a 3-fold cover of A_{6}, and G(1, 8) is a nonsplit extension of an elementary abelian group of order 2^{6} by P SL(2, 7) (the group L_{3}(2) ⋄ 2 ⋄ (6, 7) in the tables of finite perfect groups in [HoP 89]).

In order to complete the proof of Theorem 1.2, it suffices to prove that G(1, n) is infinite for n = 9, 10, 12, 14, 15, 16, 21, 22, 25, 33, 35, 49, 55, 77, 121 and all primes p ≥ 13, and that G(2, n) and G(3, n) are infinite for n = 6, 8, 9, 10, 15, 25 and all primes p ≥ 7. We shall make some remarks about the awkward case G(1, 11) at the end of this section. Theorem 2.5 is applicable for G(1, n) with n ≥ 42, G(2, n) with n ≥ 20 and G(3, n) with n ≥ 12. We shall deal with these cases in Sections 4 and 5, and handle the smaller values of n now. To do this we shall simply describe the group H and the module M in each case. G(1, 9) : H = P SL(2, 8), M = irreducible module of dimension 7 (proof from Proposition 2.3 and character table of H). G(1, 10) : H = P SL(2, 41), M = permutation module of degree 574 on the cosets of a subgroup isomorphic to A_{5}, dim(H^{1}(G, M)) = 1.

G(1, 12) : H is an extension of an irreducible module of order 3^{6} by P SL(3, 2), M is a permutation module of degree 756, dim(H^{1}(G, M)) = 1. G(1, 13) : H = P SL(2, 13), M = irreducible module of dimension 14 (with character value −2 on a 2-element), dim(H^{1}(G, M)) = 1. G(1, 14) : H = P SL(2, 29), M = permutation module of degree 435 on unordered pairs of points, dim(H^{1}(G, M)) = 2. G(1, 15) : H = P SL(2, 29), M = permutation module of degree 435 on unordered pairs of points, dim(H^{1}(G, M)) = 2. G(1, 16) : H is a (nonsplit) extension of a homocyclic abelian group of order 4^{6} by P SL(3, 2), M is a permutation module of degree 336, dim(H^{1}(G, M)) = 1. G(1, 17) : H = P SL(2, 239), M = natural permutation module of degree 240, dim(H^{1}(G, M)) = 1. G(1, 19) : H = P SL(2, 113), M = natural permutation module of degree 114, dim(H^{1}(G, M)) = 1. G(1, 20) : H = P SL(2, 41), M = natural permutation module of degree 42, dim(H^{1}(G, M)) = 1. G(1, 21) : H = A_{22}, M = permutation module of degree 231 on unordered pairs of points, dim(H^{1}(G, M)) = 2. G(1, 22) : H = A_{35}, M = permutation module of degree 595 on unordered pairs of points, dim(H^{1}(G, M)) = 1. G(1, 23) : H = P SL(2, 139), M = natural permutation module of degree 140, dim(H^{1}(G, M)) = 2. G(1, 25) : H = A_{51}, M = permutation module of degree 1275 on unordered pairs of points, dim(H^{1}(G, M)) = 6. G(1, 29) : H = A_{29}, M = permutation module of degree 406 on unordered pairs of points, dim(H^{1}(G, M)) = 4. G(1, 31) : H = A_{63}, M = natural permutation module of degree 63, dim(H^{1}(G, M)) = 2. G(1, 33) : H = A_{15}, M = permutation module of degree 1365 on unordered quadruples of points, dim(H^{1}(G, M)) = 5. G(1, 35) : H = P SL(2, 71), M = natural permutation module of degree 72, dim(H^{1}(G, M)) = 1. G(1, 37) : H = A_{37}, M = permutation module of degree 666 on unordered pairs of points, dim(H^{1}(G, M)) = 8. G(1, 41) : H = P SL(2, 83), M = natural permutation module of degree 84, dim(H^{1}(G, M)) = 2. G(2, 6) : H = S_{5}, M = permutation module of degree 40, dim(H^{1}(G, M)) = 2. G(2, 7) : H = Sz8, M = irreducible module of dimension 28 (proof from Proposition 2.3 and character table of H). G(2, 8) : H is an extension of a (nonabelian) group of order 2^{10} by D_{10}, M is a permutation module of degree 256, dim(H^{1}(G, M)) = 1. G(2, 9) : H = A_{20}, M = permutation module of degree 380 on ordered pairs of points, dim(H^{1}(G, M)) = 2. G(2, 10) : H = P GL(2, 11), M = permutation module of degree 132 on ordered pairs of points, dim(H^{1}(G, M)) = 3.

G(2, 11) : H = A_{47}, M = permutation module of degree 1081 on unordered pairs of points, dim(H^{1}(G, M)) = 1. G(2, 13) : H = Sz8, M = natural permutation module of degree 65, dim(H^{1}(G, M)) = 2. G(2, 15) : H = P SL(2, 31), M = permutation module of degree 496 on unordered pairs of points, dim(H^{1}(G, M)) = 6. G(2, 17) : H = A_{17}, M = permutation module of degree 136 on unordered pairs of points, dim(H^{1}(G, M)) = 2. G(2, 19) : H = A_{41}, M = permutation module of degree 861 on unordered pairs of points, dim(H^{1}(G, M)) = 16. G(3, 6) : H = SL(2, 3), M = regular permutation module of degree 24, dim(H^{1}(G, M)) = 4. G(3, 7) : H = P SL(2, 7), M = permutation module of degree 24, dim(H^{1}(G, M)) = 2. G(3, 8) : H = P SL(2, 17), M = permutation module of degree 153 on unordered pairs of points, dim(H^{1}(G, M)) = 2. G(3, 9) : H = P SL(2, 17), M = natural permutation module of degree 18, dim(H^{1}(G, M)) = 1. G(3, 10) : H = P SL(2, 41), M = permutation module of degree 861 on unordered pairs of points, dim(H^{1}(G, M)) = 6. G(3, 11) : H = P SL(2, 23), M = natural permutation module of degree 24, dim(H^{1}(G, M)) = 1.

We conclude this section with some comments on the case G = G(1, 11), which we have been unable to settle. This group has epimorphisms onto P SL(2, 43) and the Janko group J_{1}, and we have verified that there are no other simple epimorphic images of order less than 10^{11}. We have also been able to show that if K_{1} and K_{2} are the kernels of these two epimorphisms, respectively, then K_{1}/K′_{1} is a finite 43-group and K_{2}/K′_{2} is a finite 2-group. Furthermore, by using the Reidemeister-Schreier method, V. Felsch has been able to show that the largest elementary abelian factor group of K_{1}/K′_{1} has order 43^{11}. Unfortunately, these larger epimorphic images of G are currently too big for our programs.

4 The proof of Theorem 1.2 for large n. Method 1: Coset Diagrams

To complete the proof of Theorem 1.2, it remains to show that:

(i) G(1, n) is infinite for n = 49, 55, 121 and primes n > 42;

(ii) G(2, n) is infinite for n = 25 and primes n > 20; and

(iii) G(3, n) is infinite for n = 15, 25 and primes n > 12.

By Theorem 2.5, in order to do this, it suffices to find a finite epimorphic image H of G in which the images of x, y, xy and [x, y] (or xy^{2}) have the orders specified by the presentations. In this section we shall prove this by the use of coset diagrams, except in finitely many cases, which will be dealt with by another method in the next section.

We begin with the case G(1, n). The idea of combining coset diagrams to produce permutation representations of the Hurwitz group ⟨x, y|x^{2}, y^{3}, (xy)^{7}⟩ of large degree was used by Conder in [Con 80], and we are grateful to Richard Parker for helping us construct diagrams with the properties that we require for the current application. A permutation representation of this group can be represented by a diagram like that in Fig. 1. The edges on the small triangles represent the action of y, where the vertices of the triangles are permuted anti-clockwise by y, and the other edges join two points that are interchanged by x. Other points are fixed by x. Points that are fixed by y are represented by heavy dots. Fig. 1 is actually a permutation representation of G(1, 4), with image isomorphic to P SL(2, 7).

[figure: Fig. 1]

The diagram in Fig.2 is incomplete, but would become a permutation representation of G(1, 13) if we were to identify the open ends L and R of the x-edge that we have cut in half. We shall call a diagram of this kind a ‘(2, 3, 7)-brick’. (Since we shall only use a small number of specific examples, we do not need a precise definition of this concept. Roughly speaking, it is a diagram for the Hurwitz group, with one x-edge cut open at the points L and R, such that the left hand and right hand parts of the diagram to the left and right of the dotted vertical lines in Fig. 2 are exactly as they are in Fig. 2.) We shall denote the bricks in Figs. 2 and 3 by B_{13} and B_{31}, respectively, since that in Fig. 3 arises from a representation of G(1, 31).

[figure: Fig. 2; L; A; B; D; C; R]

[figure: Fig. 3; L; A; B; D; C; R]

It is a property of bricks, that if we join any number of them in a circle by identifying point L of one brick with point R of the next, then the element xy still has order 7. To see this, we only have to consider what happens to the points A and C under powers of xy, since it is from these points that we cross over to the next brick. Let us now consider what happens to the commutator z = [x, y]. In a row of bricks of type B_{13}, if we apply z^{8} to the vertex A then we arrive at the vertex B in the next brick to the left, and if we apply z^{5} to B then we get to A in the next brick to the left. Similarly, applying z^{8} to C gets us to D in the next brick to the right, and applying z^{5} to D gets us to C in the next brick to the right. If we apply powers of z to any other vertex in the brick, then we eventually arrive at one of the points A, B, C or D, after which we move into the adjoining brick. Similar conditions apply to bricks of type B_{31}. (z^{22} takes A to B, z^{9} takes B to A, z^{8} takes C to D, and z^{23} takes D to C.) It is now not difficult to see that if we make a circle of 2r copies of B_{13} followed by 2s copies of B_{31}, for any integers r, s ≥ 0, then z will have the order 13r + 31s in the resulting diagram. It follows that we can achieve our aim of finding a finite image of G(1, n) for all sufficiently large n; certainly for all n ≥ 13.31 = 403.

In fact, bricks with the property shared by B_{13} and B_{31}, that the orbits of z move through all of the bricks in the circle, seem to be rather rare, and these are the only two that we have been able to find. It is considerably easier to find bricks in which the orbits of z leave the brick at the same end as they enter it. An example is shown in Fig. 4 (which is not connected). Here z^{5} takes A to D, z^{12} takes D to A, z^{6} takes B to D, and z^{11} takes D to B.

[figure: Fig. 4; L; A; B; D; C; R]

It can be seen (with a little thought), that if we make a circle of r copies of B_{13}, s copies of type B_{31} and one brick like that in Fig. 4, then we get a diagram in which z has order 13r + 31s + 17. Of the values of n that we are trying to deal with, we have now covered all except 43, 47, 49, 53, 55, 59, 67, 71, 73, 89, 97, 103, 107, and 151. In fact, with some difficulty, we managed to find coset diagrams for all of these values except n = 59, but we shall give no more details, since the method described in the next section can be used to cope with a finite number of exceptional cases.

We turn now to the case G(2, n). The method is similar, except that y has 4-cycles rather than 3-cycles. We use (2, 4, 5)-bricks BB_{15}, BB_{35} and BB_{39} with 32, 72 and 80 vertices, respectively. Rather than draw them as diagrams, we give the permutations in cyclic form. In each case, we obtain the brick by cutting open the x-edge (1, d) (where d is the degree), and making 1 the leftmost vertex and d the rightmost point of the brick. BB_{15} : x ↦ (1, 32) (2, 31) (3, 4) (5, 12) (6, 11) (7, 8) (9, 10) (13, 24) (14, 25) (15, 19) (16, 17) (18, 27) (20, 21) (22, 23) (26, 30) (28, 29), y ↦ (1, 5, 10, 7) (2, 31, 20, 30) (3, 32, 4, 6) (8, 13, 16, 12) (9, 18, 21, 19) (11, 14, 15, 22) (17, 27, 28, 29) (23, 26, 24, 25); BB_{35} : x ↦ (1, 72) (2, 68) (3, 62) (4, 18) (5, 47) (6, 50) (7, 17) (8, 28) (9, 34) (10, 70) (11, 57) (12, 23) (13, 61) (14, 16) (15, 43) (19, 21) (20, 53) (22, 35) (24, 39) (25, 26) (27, 30) (29, 58) (31, 55) (32, 51) (33, 37) (36, 52) (38, 67) (40, 54) (41, 48) (42, 56) (44, 60) (45, 64) (46, 65) (49, 71) (59, 63) (66, 69), y ↦ (1, 46, 48, 29) (2, 5, 47, 41) (3, 21, 9, 4) (6, 42, 18, 55) (7, 67, 54, 27) (8, 11, 68, 19) (10, 52, 72, 36) (12, 23, 17, 44) (13, 40, 50, 59) (14, 64, 63, 49) (15, 51, 45, 61) (16, 56, 69, 30) (20, 33, 62, 71) (22, 26, 66, 38) (24, 37, 43, 32) (25, 70, 35, 60) (28, 39, 53, 31) (34, 65, 58, 57); BB_{39} : x ↦ (1, 80) (2, 47) (3, 16) (4, 51) (5, 34) (6, 42) (7, 35) (8, 73) (9, 45) (10, 23) (11, 18) (12, 65) (13, 44) (14, 46) (15, 66) (17, 78) (19, 24) (20, 79) (21, 71) (22, 55) (25, 41) (26, 72) (27, 56) (28, 48) (29, 59) (30, 40) (31, 49) (32, 36) (33, 61) (37, 68) (38, 76) (39, 62) (43, 54) (50, 52) (53, 60) (57, 70) (58, 64) (63, 69) (67, 74) (75, 77), y ↦ (1, 49, 13, 45) (2, 68, 70, 19) (3, 12, 35, 28) (4, 67, 25, 33) (5, 79, 59, 22) (6, 47, 30, 16) (7, 26, 73, 76) (8, 11, 55, 77) (9, 24, 60, 31) (10, 38, 37, 41) (14, 71, 48, 56) (15, 29, 39, 20) (17, 58, 54, 63) (18, 27, 23, 64) (21, 57, 75, 50) (32, 62, 36, 80) (34, 78, 65, 51) (40, 44, 43, 74) (42, 52, 66, 61) (46, 72, 69, 53).

By joining r, s and t copies of bricks BB_{15}, BB_{35} and BB_{39}, respectively, in a circle, we get a permutation representation of G(2, n), for n = 15r + 35s + 39t, which covers all values that we need except for 25, and 27 primes, the highest being 211. Again we shall deal with these remaining cases in the next section.

Finally, we turn to the case G(3, n). Since we have no involutory generators in this case, we need a different method of joining bricks. In a (3, 3, 4)-brick of degree d, we insist that x always contains the 3-cycle (1, d − 1, d), and we split this cycle along the x-edges {1, d − 1} and {d − 1, d} Thus, when we join bricks, the vertex 1 is mapped by x to the point d − 1 in the next brick to the left, and the vertex d is mapped to the vertex 1 in the next brick to the right. We use the bricks BBB_{8} and BBB_{11} of degrees 18 and 24, as below. BBB_{8} : x ↦ (1, 17, 18) (2, 5, 14) (3, 10, 4) (6, 8, 9) (7, 12, 11) (13, 16, 15), y ↦ (1, 6, 8) (2, 16, 5) (3, 18, 10) (4, 7, 17) (9, 14, 15) (11, 13, 12); BBB_{11} : x ↦ (1, 23, 24) (2, 16, 21) (3, 12, 4) (5, 22, 13) (6, 8, 9) (7, 15, 14) (10, 20, 11) (17, 19, 18), y ↦ (1, 6, 8) (2, 5, 22) (3, 24, 10) (4, 7, 23) (9, 18, 14) (11, 12, 13) (15, 16, 17) (19, 21, 20).

By joining r copies of BBB_{8} with s copies of BBB_{11} in a circle, we achieve a representation of G(3, n), with n = 8r + 11s, and this covers all values of n that we need, except for 15, 17, 23, 25, 29, 31, 37, 47, 53 and 61, which we shall deal with in the following section.

5 The proof of Theorem 1.2 for large n. Method 2: Mapping onto P SL(2, q).

Let G = G(1, n) be the group ⟨x, y|x^{2}, y^{3}, (xy)^{7}, [x, y]^{n}⟩ and let ϕ be an epimorphism of G onto the group H = P SL(2, q), where q = p^{r} is a prime power. We assume also that the images of x, y, xy and [x, y] under ϕ have the orders 2, 3, 7 and n, respectively.

Since H is then certainly an epimorphic image of the Hurwitz group, ⟨x, y|x^{2}, y^{3}, (xy)^{7}⟩, it follows from a result of Macbeath [Mac 69], that either

(i) q = 7,

(ii) r = 1 with p ≡ ±1 (mod 7), or

(iii) r = 3 with p ≡ ±2 or ±3 (mod 7).

It can be checked that, if p = 2, then r = 3 and n = 9, if p = 3 then r = 3 and n = 13, and if q = 7 then n = 4, so let us assume that p > 7. Let u and v be inverse images of ϕ(x) and ϕ(y), respectively, in SL(2, q). Then |u| = 4, and by replacing u and v by −u and −v if necessary, we may assume that |v| = 3 and |uv| = 7. If n is odd, then |[u, v]| may be n or 2n, whereas if n is even |[u, v]| = 2n. Since SL(2, q) has a unique conjugacy

class of elements of order 4, we may assume that u = ( \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ) . Let v = ( \begin{matrix}a & b \\ c & d \end{matrix} )

where ad − bc = 1. Then uv = ( \begin{matrix}c & d \\ −a & −b \end{matrix} ) and [u, v] = ( \begin{matrix}a^{2} + c^{2} & ab + cd \\ ab + cd & b^{2} + d^{2} \end{matrix} ) .

Let χ_{m} denote a primitive mth root of unity (either in the complex numbers or in a finite field) and α_{m} = χ_{m} + χ_{m}^{−1}. If m is not divisible by p, then, it is easily seen (by diagonalizing g) that an element g in SL(2, q) has order m if and only if its trace is equal to α_{m} (for some choice of χ_{m}). We therefore have a+d = −1 and c−b = α_{7}. The trace of [u, v] is equal to a^{2} +b^{2} +c^{2} +d^{2} = a^{2} +b^{2} +c^{2} +(1+a)^{2}, and since −a(1+a)−bc = 1, this is equal to b^{2}+c^{2}−2bc−1 = (b−c)^{2}−1 = α_{7}^{2}−1. Now α_{7}^{2} = χ_{7}^{2}+χ_{7}^{−2}+2 and, by changing our choice of χ_{7}, we may denote this by α_{7} + 2. The trace of [u, v] is therefore equal to α_{7} + 1. Note that α_{7} satisfies the equation P (x) = 0, where P (x) = x^{3} + x^{2} − 2x − 1.

Let us first suppose that n = p. Then [u, v] has order p or 2p and so it has trace 2 or −2. In the first case, we get α_{7} = 1, and since P (1) = −1, this is not satisfied by any value of p. In the second case, α_{7} = −3 and P (x) = −13, and so the only possibility is p = 13, and in fact this case does occur.

We assume from now on that p does not divide n, and so we have the equation (∗) α_{7} + 1 = α_{m}, where m = n or 2n if n is odd, and m = 2n if n is even. Conversely, suppose that this equation has a solution in some finite field of order q = p^{r}, where r = 1 or 3, as in cases (ii) and (iii) above (which ensures that α_{7} lies in the field). Then the equation ad − bc = 1 reduces to a quadratic equation in two variables, for which we can always find a solution in the field, and so P SL(2, q) really is an epimorphic image of G in which the images of x, y, xy and [x, y] have the correct orders.

Now let R = ∏_{α_{m}} ∏_{α_{7}}(α_{m}−1−α_{7}) = ∏_{α_{m}}(α_{m}^{3}−2α_{m}^{2}−α_{m}+1) where we now regard α_{7} and α_{m} as complex numbers, and the product is taken over the algebraic conjugates of α_{7} and α_{m}. Since R is the norm of α_{m} −1−α_{7} in the appropriate cyclotomic number field, it is an integer. It is clear that (∗) will have a solution in the field of order q if and only if one of the terms in the product is trivial in this field, which is the case if and only if p|R. It now follows that, for a given n, only finitely many P SL(2, q) can occur as epimorphic images of G. The value of R can easily be computed on a programmable pocket calculator for values of m up to about 80. For larger values of m, R gets rapidly bigger, and so an arbitrary precision arithmetic system, such as the UNIX ’bc’ is better. We find that R is ±1 for m = 1, 2, 3, 4, 5, 6, 10, 16, 19, 22, 24, 34, 54 and 60 (or equivalently α_{m} − 1 − α_{7} is a unit), and we conjecture that R is never a unit for m > 60, although we are unable to prove this. We also have to avoid the primes 2, 3 and 7 and primes dividing m, since we have already excluded these from consideration, but by considering theses cases we see that they can only arise for m = 9.2^{x}(p = 2), m = 13.3^{x}(p = 3) or m = 4.7^{x}(p = 7). (For example, for m = 39, R = 27 and for m = 56, R = −343.) However, we find that for all of the numbers left over from Section 4 (i.e. 43, 47, 49, 53, 55, 59, 67, 71, 73, 89, 97, 103, 107, 151), we can find a suitable q, which enables us to complete the proof of Theorem 1.2 (i). In particular, for n = m = 59 (which was the only number that we were completely unable to deal with by other methods), we find that R = −2514581, which is prime, and the

reader can check that u = ( \begin{matrix}0 & 1 \\ −1 & 0 \end{matrix} ) and v = ( \begin{matrix}1 & 14695 \\ 803913 & −2 \end{matrix} ) really does induce an

epimorphism onto P SL(2, 2514581) in this case. (However, there is also an epimorphism onto P SL(2, 797917), in which m = 2n = 118.)

The analysis for the groups G(2, n) and G(3, n) is very similar. In place of equation (*), we obtain the equations α_{m} = \sqrt{2}α_{5}, and α_{m} = 1 − \sqrt{2}, respectively, (where m = n or 2n, as before) and the expression R becomes R(2) = ∏_{α_{m}}(α_{m}^{4} − 6α_{m}^{2} + 4) and R(3) = ∏_{α_{m}}(α_{m}^{2} − 2α_{m} − 1) respectively. It is routine to check that there is an appropriate prime p dividing R(2) or R(3) for each of the exceptional cases, which implies that G(2, n) or G(3, n) can be mapped onto P SL(2, p^{r}) for some r. For example, for m = 211, R(2) = −1596853450017939816800419382349915776955956759249.

References

[Con 80] M.D.E. Conder, ‘Generators for alternating and symmetric groups’, J. Lon. Math. Soc. 22 (1980), 75-86.

[Edj 90] M. Edjvet, ‘An example of an infinite group’, manuscript.

[Gru 70] K.W. Gruenberg, “Cohomological Topics in Group theory”, Springer Lecture Notes in Mathematics, vol. 143, 1970.

[Hav 73] G. Havas, ‘A Reidemeister-Schreier program’, “Proceedings of the Second International Conference on the Theory of Groups”, Canberra 1973 (Springer Lecture Notes in Mathematics, vol. 372, 197 ), pp. 347-356.

[HoP 89] D. Holt and W. Plesken, “Perfect groups”, Oxford University Press, 1989.

[HoT 90] J. Howie and R. Thomas, ‘On the asphericity of presentations for the groups (2, 3, p; q) and a conjecture of Coxeter’, University of Leicester Department of Computing Studies, Technical Report CSD-36.

[Mac 69] A.M. Macbeath, ‘Generators of linear fractional groups’, “Number Theory”, Proc. of Symposia in Pure Mathematics 12 (American Mathematical society, Providence, R.I., 1969), pp. 14-32.

[Neu 81] J. Neubüser, ‘An elementary introduction to coset table methods in computational group theory’, “Groups-St. Andrews 1981”, LMS Lecture Notes Vol.71, CUP 1982, pp. 1-45.

[Ple 87] W. Plesken, ‘Towards a soluble quotient algorithm’, J. Symbolic Computation 4, 1987, 111-22.

[Zas 48] H. Zassenhaus, ‘Über einen Algorithmus zur Bestimmung der Raumgruppen’, Comment. Math. Helvet. 21, 117-41.

Addresses:

University of Warwick Mathematics Institute Coventry CV4 7AL Great Britain

RWTH Aachen Lehrstuhl B für Mathematik Templergraben 64 5100 Aachen W. Germany