PRESENTATIONS OF FINITE SIMPLE GROUPS: A COMPUTATIONAL APPROACH

R. M. GURALNICK, W. M. KANTOR, M. KASSABOV, AND A. LUBOTZKY

Abstract. All nonabelian finite simple groups of rank n over a field of size q, with the possible exception of the Ree groups ^{2}G_{2}(3^{2e+1}), have presentations with at most 80 relations and bit-length O(log n + log q). Moreover, A_{n} and S_{n} have presentations with 3 generators, 7 relations and bit-length O(log n), while SL(n, q) has a presentation with 7 generators, 25 relations and bit-length O(log n + log q).

Contents

1. Introduction

In [?] we provided short presentations for all alternating groups, and all finite simple groups of Lie type other than the Ree groups ^{2}G_{2}(q), using at most 1000 generators and relations. In [?] we proved the existence of profinite presentations for the same groups using fewer than 20 relations. The goal of the present paper is similar: we will provide presentations for the same simple groups using 2 generators and at most 80 relations. These and other new presentations have the potential advantage that they are simpler than those in [?], at least in the sense of requiring fewer relations; we hope that both types of presentations will turn out to be useful in Computational Group Theory.

The fundamental difference between this paper and [?] is that here we achieve a smaller number of relations at the cost of relinquishing some control over the length of the presentations. Our first result does not deal with lengths at all:

Theorem A. All nonabelian finite simple groups of Lie type, with the possible exception of the Ree groups ^{2}G_{2}(q), have presentations with 2 generators and at most 80 relations.

All symmetric and alternating groups have presentations with 2 generators and 8 relations.

In fact, a similar result holds for all finite simple groups, except perhaps ^{2}G_{2}(q) (the sporadic groups are surveyed in [?]). Both the bounds of 20 relations in [?] and 80 here are not optimal – in all cases we will provide much better bounds, though usually with more generators. Possibly 4 is the correct upper bound for both standard and profinite presentations. Wilson [?] has even conjectured that 2 relations suffice for the universal covers of all finite simple groups.

2000 Mathematics Subject Classification. Primary 20D06, 20F05 Secondary 20J06.

The authors were partially supported by NSF grants DMS 0140578, DMS 0242983, DMS 0600244 and DMS 0354731.

Although we are giving up the requirement of length used in [?], we can still retain some control over a weaker notion of length used in [?, ?] and especially suited for Computer Science complexity considerations: bit-length. This is the total number of bits required to write the presentation, so that all exponents are encoded as binary strings, the sum of whose lengths enters into the bit-length. (The presentation length that had to be kept small in [?] involves at least the much larger sum of the actual exponents; cf. Section ??.)

Theorem B. All nonabelian finite simple groups of rank n over a field of size q, with the possible exception of the Ree groups ^{2}G_{2}(q), have presentations with at most 14 generators, 78 relations and bit-length O(log n + log q).^{1}

Here we view alternating (and symmetric) groups as having rank n − 1 over “the field of size 1” [?]. The bounds in both of the preceding theorems also hold for many of the almost simple groups.

By [?, Lemma 2.1], if we have any presentation of a finite simple group G with at most 78 relations, we obtain a presentation with 2 generators and at most 80 relations (cf. Lemma ?? below). Moreover, the proof of that lemma shows that any pair of generators of G can be used for such a presentation (cf. Corollary ??). “Almost all” pairs of elements of a finite simple group generate the group [?, ?, ?]; some pairs will probably force the length or even the bit-length to be fairly large. Indeed, [?, Lemma 2.1] is so general that it allows us to cheat somewhat: the resulting presentations are not even slightly explicit, and we have no information concerning their bit-lengths. In particular, we are unable to prove Theorem ?? using 2 instead of 14 generators.

In view of [?, Lemma 2.1] or Lemma ??, our goal will be to prove Theorem ??. Much better bounds are obtained in various cases. For example, Theorems ?? and ?? deal with the alternating and symmetric groups, where we go further than any previous types of presentations for these groups in terms of the small number of relations used (cf. [?, ?]):

Theorem C. For each n ≥ 5, A_{n} and S_{n} have presentations with 3 generators, 7 relations and bit-length O(log n), using a bounded number of exponents.

Moreover, for the preceding groups, in addition to the second part of Theorem ?? we show that, if a and b are any generators of G = A_{n} or S_{n}, then there is a presentation of G using 2 generators that map onto a and b, with 9 relations (Corollary ??). There are similar results in all cases of Theorem ?? (cf. Remark ?? in Section ??). However, as already noted, we do not know if it is possible to choose a and b in order to obtain a presentation with bit-length O(log n); nor if it is possible to choose them in order to obtain a bounded number of exponents for groups of Lie type over arbitrarily large degree extensions of a prime field (cf. Remark ?? in Section ??).

In order to obtain all of the presentations in the preceding theorems, although [?] was a starting point we need significantly new methods for unbounded rank n; these ideas may prove to be more practical for actual group computation than some of those in [?]. Moreover, while a few of the arguments used here are streamlined, often simpler, and occasionally improved versions of ones in [?], they are still rather involved. As in [?] we do not use the classification of the finite simple groups in any proofs.

1Logarithms will be to the base 2.

For groups of bounded rank, our presentations can be made to be short in the sense used in [?], at the cost of adding a small number of additional generators and relations (so that [?, (3.3) and (4.16)] will apply; cf. (??) and (??) below). It is our treatment of unbounded rank that contains new ideas to decrease the number of relations in [?] at the expense of the length of the presentation. We provide more than one approach for this purpose: some classical groups are handled in different ways in Sections ?? and ??. The unitary groups are dealt with separately in Section ?? by using an idea of Phan [?] as improved in [?].

In Sections ??–?? we will consider various types of simple groups in order to prove the above theorems, providing better bounds for the number of generators and relations in various cases. For many cases we only give hints regarding the final assertion in Theorem ??.

One of our original motivations for work on presentations was the following

Corollary D (Holt’s Conjecture [?] for simple groups). There is a constant C such that, for every finite simple group G, every prime p and every irreducible 𝔽_{p}[G]-module M, dim H^{2}(G, M) ≤ C dim M.

This conjecture has already been proven twice, in [?, Theorem B′] and [?, Theorem B]. As in [?] it is an immediate consequence of Theorem ??, except for the Ree groups (and these also had to be handled separately in [?]). The proof based on the present paper (using the elementary result [?, Lemma 7.1]) is simpler than the previous proofs, although a smaller, explicit constant C is given in [?]. See [?, Theorem C] for a generalization of the preceding result to all finite groups.

Section ?? contains further remarks concerning these results. For now we note one further unexpected direction:

Efficient presentations. If ⟨X | R⟩ is a presentation of a finite group G, then |R| − |X| is at least the smallest number d(M) of generators of the Schur multiplier M of G; and ⟨X | R⟩ is called an efficient presentation if |R| − |X| = d(M) [?, ?, ?, ?]. The only infinite families of nonsolvable groups known to have efficient presentations appear to be groups having PSL(2, p) as a composition factor when p is prime [?, ?] (cf. (??). Therefore it may be of some interest that Corollaries ??(i) and ??(ii) contain examples of families of groups having efficient presentations with alternating groups as composition factors. For example, for any prime p ≡ 11 (mod 12), there is a a presentation of A_{p+2} × T with 2 generators and 3 relations, where T is the subgroup of index 2 in AGL(1, p). It seems plausible that this can be used to obtain efficient presentations of A_{p+2} with 3 generators and 4 relations for these primes.

Examples ?? and ??, together with Table ?? and Remark ??, deal with presentations for various groups A_{n} and S_{n} when n has a special form. Section ?? contains explicit presentations of S_{n} for all n ≥ 50. For general n it would be desirable to have even fewer relations than in Theorem ??, with the goal of approaching efficiency for alternating groups.

2. Preliminaries

Presentation lengths. In [?, Section 1.2] there is a long discussion of various notions of “lengths” of a presentation ⟨X | R⟩ and some of the relationships among them. Here we only summarize what is needed for the present purposes. length = word length: |X| + sum of the lengths of the words in R within the free

group on X. Thus, length refers to strings in the alphabet X ∪ X^{−1}. This is the notion of length used in [?], and seems the most natural notion from a purely mathematical point of view. We reserve the term short presentation for one having small length. Achieving this was one of the goals in [?], though not of the present paper.

bit-length: the total number of bits required to write the presentation, used in [?] and [?]. All exponents are encoded as binary strings, the sum of whose lengths enters into the bit-length, as does the space required to enumerate the list of generators and relations.

expo-length: the total number of exponents used in the presentation. By comparing the present paper with [?] it becomes clear that small bit-length is much easier to achieve than small length. The properties required of the bit-length bl(w) of a word w are

bl(x) = 1, x ∈ X; bl(w^{n}) ≤ bl(w) + log |n| if n ∈ ℤ\ {0, 1, −1}; and
bl(ww′) ≤ bl(w) + bl(w′)

for any words w, w′. Subgroups. We will use the elementary fact [?, Lemma 2.3] that a group G that has a presentation based on a known group, using presentations of subgroups of that group, has the subgroups automatically built into G:

Lemma 2.1. Let π: F_{X∪Y} → G = ⟨X, Y | R, S⟩ and λ: F_{X} → H = ⟨X | R⟩ be the natural surjections, where H is finite. Assume that α: G → G_{0} is a homomorphism such that α⟨π(X)⟩ ≅ H. Then ⟨π(X)⟩ ≅ H.

In the present paper we will use this freely, often without comments.

Curtis-Steinberg-Tits presentation. This is a standard presentation for groups of Lie type; see [?], [?], [?, Theorem 13.32] and [?, Theorem 2.9.3]. We will generally refer to [?, Sections 5.1 and 5.2] for a discussion of the versions we will use.

3. Symmetric and alternating groups

We will use a presentation for alternating groups, due to Carmichael [?, p. 169], that is more symmetrical than a presentation due to Burnside and Miller ([?, p. 464], [?, p. 366]) in 1911 that was used in [?, (2.6)]. Moreover, Carmichael’s presentation requires less data (i.e., fewer relations):

(3.1)  A_{n+2} = ⟨x_{1}, …, x_{n} | x_{i}^{3} = (x_{i}x_{j})^{2} = 1 whenever i ≠ j⟩,

based on the 3-cycles (i, n + 1, n + 2), 1 ≤ i ≤ n. We will also use the standard presentations

(3.2) A_{4} = ⟨x, y | x^{3} = y^{2} = (xy)^{3} = 1⟩ and A_{5} = ⟨x, y | x^{5} = y^{2} = (xy)^{3} = 1⟩

[?, p. 137]. Presentations are known for the universal central extension of A_{n}, 4 ≤ n ≤ 9, with 2 generators and 2 relations [?, ?]; and for A_{10} using 2 generators and 3 relations [?] (cf. Example ??(??)). These can be used in some of our presentations in Sections ?? and ?? in order to save several relations.

In Section ?? we make crucial use of the symmetry of (??), as follows. Let T = ⟨X | R⟩ be a group acting transitively on {1, …, n}, viewed as acting on {1, …, n, n + 1, n + 2}. Introduce a new generator z corresponding to the 3-cycle (1, n + 1, n + 2). We use additional relations in order to guarantee that |z^{T} | = n in our presented group, as well as a very small number of relations of the form (zz^{t})^{2} = 1 for suitable t ∈ T, in order to use (??).

This idea is reworked several times in order to handle various special degrees n. We glue two such presentations in Section ?? in order to deal with symmetric and alternating groups of arbitrary degrees.

3.1. Using 2-transitive groups for special degrees. The results of this section are summarized in Examples ??. We begin with an integer n ≥ 3, together with

• a group T acting transitively (though not necessarily faithfully) on the unordered pairs of distinct points in {1, …, n} (i.e., T is 2-homogeneous),

• a presentation ⟨X | R⟩ of T,

• a subset X_{1} of T such that T_{1} = ⟨X_{1}⟩ is the stabilizer of 1 (we usually have X_{1} ⊂ X), and

• a word w in X that moves 1 and lies in A_{n} (when w is viewed inside T). The last requirement implies that the permutation group T̄ induced by T may not be inside A_{n}; when it is inside then the following lemma and its proof are somewhat simpler. Note that, if T is not 2-transitive, then T̄ has odd order, and hence lies in A_{n}. (Here the order is odd because an involution in T̄ would allow some ordered 2-set to be moved to any other one.)

Lemma 3.3. If J = ⟨X, z | R, z^{3} = 1, (zz^{w})^{2} = 1, z^{u} = z^{sign(u)} for u ∈ X_{1}⟩, then J ≅ A_{n+2} × T.

Proof. View T as a subgroup of A_{n+2} = Alt {1, …, n, n + 1, n + 2}, with each t ∈ T inducing (n + 1, n + 2)^{sign(t)} on {n + 1, n + 2}. Define φ: X ∪ {z} → A_{n+2} × T by

(3.4)

φ(x) = (x(n + 1, n + 2)^{sign(x)}, x) for x ∈ X
φ(z) = (z′, 1) where z′ = (1, n + 1, n + 2).

Then the image of φ satisfies the defining relations for J, and we obtain a homomorphism φ: J → A_{n+2} × T. We claim that φ is a surjection. For, since T is 2-homogeneous on {1, …, n}, we have ⟨φ(z)^{⟨φ(X)⟩}⟩ = A_{n+2} × 1. Here, A_{n+2} contains ⟨X⟩ = T, while ⟨φ(X)⟩ projects onto T in the second component, so that φ(J) also contains 1 × T. Hence, φ is, indeed, surjective.

Then there is also a surjection π: J → A_{n+2}. By Lemma ??, J has a subgroup we identify with T = ⟨X⟩. We also view z as contained in J.

Since ⟨z⟩^{T_{1}} = ⟨z⟩ by our relations, we have |⟨z⟩^{T} | ≤ n; but |π(⟨z⟩^{T})| = n and so |⟨z⟩^{T} | = n. Similarly, |z^{T ∩A_{n}}| = n. Consequently, T acts on ⟨z⟩^{T} and T ∩ A_{n} acts on z^{T ∩A_{n}} as they do on {1, …, n}.

Moreover, if T is not inside A_{n}, then our sign condition in the presentation implies that |z^{T} | = 2n, and T ∩A_{n} has 2 orbits on z^{T}, namely, z^{T ∩A_{n}} and (z^{−1})^{T ∩A_{n}}.

By 2-homogeneity, any unordered pair of distinct members of ⟨z⟩^{T} is T -conjugate to {⟨z⟩, ⟨z⟩^{w}}. If T ∩ A_{n} is 2-homogeneous, then any unordered pair of distinct members of z^{T} is T ∩ A_{n}–conjugate to {z, z^{w}}. Since the relation (zz^{w})^{2} = 1 in the lemma implies that (z^{w}z)^{2} = 1, it follows that z^{T} satisfies (??), so that N := ⟨z^{T} ⟩ ≅ A_{n+2}.

If T ∩ A_{n} is not 2-homogeneous then, by hypothesis, T is 2-transitive but T ∩ A_{n} is not. We claim that we still have N := ⟨z^{T} ⟩ ≅ A_{n+2}. For, any ordered pair of distinct members of ⟨z⟩^{T} is T ∩ A_{n}–conjugate to (⟨z⟩, ⟨z⟩^{w}) or to one other pair, (⟨z⟩, ⟨z⟩^{y}), say, where y ∈ T ∩A_{n}. Some g ∈ T \A_{n} satisfies (⟨z⟩, ⟨z⟩^{w})^{g} = (⟨z⟩, ⟨z⟩^{y}).

Clearly, z, z^{w}, z^{y} ∈ z^{T ∩A_{n}}. Since g ∉ A_{n}, it follows that both z^{g} and (z^{w})^{g} lie in the other T ∩ A_{n}–class (z^{−1})^{T ∩A_{n}} of z. Thus, z^{g} = z^{−1} and (z^{w})^{g} = (z^{y})^{−1}, so that (zz^{y})^{2} = ([z^{−1}(z^{w})^{−1}]^{2})^{g} = 1 by our relations, and we again have N ≅ A_{n+2} by (??).

Clearly N ⊴ J and J/N ≅ T. Then |J| = |A_{n+2} × T |, so that J ≅ A_{n+2} × T. □

Examples 3.5. (1) Let p be an odd prime, n = p + 1 and T = SL(2, p). Then T has a presentation with 2 generators and 2 relations [?], while T_{1} can be generated by 2 elements. Thus, by the Lemma, A_{p+3} × SL(2, p) has a presentation with 3 generators and 6 relations (cf. Examples ??(??) and ??(??)).

(2) We can do somewhat better by taking T to be AGL(1, p) = P ⋊ T_{1}, with P cyclic of odd prime order p and T_{1} cyclic of order p − 1. By [?], if r and s are integers such that 𝔽_{p}^{∗} = ⟨r⟩ and s(r − 1) ≡ −1 (mod p), then

(3.6)  T = AGL(1, p) = ⟨a, b | a^{p} = b^{p−1}, (a^{s})^{b} = a^{s−1}⟩.

This time |X_{1}| = 1, and hence A_{p+2} × T has a presentation with 3 generators and 5 relations.

(3) An example of a 2-homogeneous group that is not 2–transitive is the subgroup T = AGL(1, p)^{(2)} of index 2 in AGL(1, p) for a prime p ≡ 3 (mod 4), p > 3. This time T = P ⋊ T_{1} with P cyclic of order p and T_{1} cyclic of order (p − 1)/2. By [?],

T = AGL(1, p)^{(2)} = ⟨a, b | a^{p} = b^{(p−1)/2}, (a^{s})^{b} = a^{s−1}⟩,

where this time 𝔽_{p}^{∗}^{2} = ⟨r⟩ and s(r − 1) ≡ −1 (mod p). Once again A_{p+2} × T has a presentation with 3 generators and 5 relations.

(4) For future reference we note that, for any prime p ≡ 3 (mod 4) with p > 3,

AGL(1, p)^{(2)} × ℤ_{2} = ⟨a, b | a^{2p} = b^{(p−1)/2}, (a^{s})^{b} = a^{s−2}⟩,

where s(r − 1) ≡ −2 (mod p), and 𝔽_{p}^{∗}^{2} = ⟨r⟩; since both s and s+p both satisfy the preceding congruence, we may assume that with s odd. For, the presented group T surjects onto AGL(1, p)^{(2)} × ℤ_{2} by sending a → (a′, z) and b → (b′, 1), with a′, b′ playing the roles of a, b in (3), and |z| = 2. Since a^{2ps} = (a^{2ps})^{b} = (a^{2p})^{s−2}, we have a^{4p} = 1. Then (a^{2p})^{s} = a^{2p}, so that (a^{ps})^{b} = a^{p(s−2)} = a^{−ps}, and hence a^{ps} = (a^{ps})^{b^{(p−1)/2}} = a^{−ps} since (p − 1)/2 is odd. Now a^{4p} = 1 = a^{2ps}. Since s is also odd, it follows that a^{2p} = 1, and also that ⟨a⟩ ⊴ T. Then a^{p} ∈ Z(T), and T is as claimed.

Corollary 3.7. If p is prime then A_{p+2} has a presentation with 3 generators, 6 relations and bit-length O(log p).

Proof. By Example ??(2), the lemma provides a presentation for A_{p+2} × AGL(1, p) with 3 generators a, b, z. Under the isomorphism (??) in the lemma, in A_{p+2} × T we have b = (b(p + 1, p + 2), b) for a (p − 1)-cycle b ∈ T_{p} (the point 1 in that lemma is now the point p ≡ 0 fixed by b). Then b^{a} moves 0 (and fixes p + 1 and p + 2), so that b^{a}z = (b^{a}(p + 1, p + 2), b^{a})(z′, 1) = (c, b^{a}) for a p-cycle c. Thus, (b^{a}z)^{p} = (1, b^{a}). Since T is the normal closure of b^{a} in T, imposing the relation (b^{a}z)^{p} = 1 gives a presentation for A_{p+2}. □

Note that this is not, however, a short presentation (cf. Section ??).

For some choices of p we can improve the preceding result:

Corollary 3.8. For any prime p ≡ 11 (mod 12), (i) A_{p+2} × AGL(1, p)^{(2)} has a presentation with 2 generators, 3 relations and bit-

length O(log p); and (ii) A_{p+2} has a presentation with 2 generators, 4 relations and bit-length O(log p).

Proof. (i) Since p ≡ 3 (mod 4), we can let T = AGL(1, p)^{(2)} ≤ A_{p}, r and s be as in Example ??(3). Consider the group J defined by the presentation

⟨a, g | a^{p} = b^{(p−1)/2}, (a^{s})^{b} = a^{s−1}, (zz^{a})^{2} = 1⟩,

where b := g^{3} and z := g^{(p−1)/2}.

First note that A_{p+2} × T satisfies this presentation. Namely, let T act on {1, …, p, p + 1, p + 2}, fixing p + 1 and p + 2. Let g be the product of the 3cycle (1, p + 1, p + 2) and an element of T having two cycles of length (p − 1)/2 on {2, …, p}. Since p ≡ 2 (mod 3), g has order 3(p − 1), so that T = ⟨a, g^{3}⟩ satisfies the presentation in Example ??(3). The final relation (zz^{a})^{2} = 1 holds as in Lemma ?? using w = a.

By Example ??(3) and Lemma ??, J has a subgroup we can identify with T = ⟨a, b⟩. Clearly, T_{p} = T_{0} = ⟨b⟩. The remaining relations z^{3} = 1 and z^{b} = z in Lemma ?? are automatic: they hold in ⟨g⟩. This proves (i).

(ii) This is similar to the preceding corollary. This time b has two cycles of length (p − 1)/2, and we obtain

(3.9) A_{p+2} ≅ ⟨a, g |a^{p} =g^{3κ}, (a^{s})^{g^{3}}= a^{s−1}, (g^{κ}(g^{κ})^{a})^{2}=(g^{3}(g^{κ})^{a}(g^{κ})^{a^{−1}})^{κ+1} =1⟩

with κ = (p − 1)/2, s(r − 1) ≡ −1 (mod p) and 𝔽_{p}^{∗}^{2} = ⟨r⟩, since −1 is a non-square mod p. For, we view (i) as a presentation for A_{p+2} ×AGL(1, p)^{(2)} with generators a and g, and we use b := g^{3} and z := g^{κ}. By (??), as in the proof of Corollary ?? we have bz^{a}z^{a^{−1}} = (b, b)(z′^{a}z′^{a^{−1}}, 1) = (c_{1}c_{2}, b) for disjoint cycles c_{1} and c_{2} of length κ + 1, since a(1) and a(−1) are in different b-cycles. Then (bz^{a}z^{a^{−1}})^{κ+1} = (1, b), and imposing the relation (bz^{a}z^{a^{−1}})^{κ+1} = 1 on the presentation in (i) gives (??). □

Remark 3.10. In the presentations in the preceding corollaries, every cycle (k, k + 1, …, l) (with k − l even) can be written as a word of bit-length O(log p) in the generators. Any even permutation with bounded support can also be expressed as word of bit-length O(log p) in the generators. For all of these elements, the indicated words use a bounded number of exponents.

Namely, all 3-cycles (k, p+1, p+2) = (1, p+1, p+2)^{a^{k−1}} have bit-length O(log p), therefore the same is true of any permutation of bounded support (because it is a product of a bounded number of such 3-cycles). In particular, if x = (1, p)(p + 1, p + 2) then xa = (1, …, p − 1)(p + 1, p + 2) has bit-length O(log p). Since

(xa)^{−k}a^{k} = (p, 1, …, k)(p + 1, p + 2)^{k},

if k < p is even then the (k +1)-cycle (p, 1, …, k) has bit-length O(log p), hence the same is true of all even cycles of the form (k, …, l), l < p. The remaining cycles arise as, for example, (k, …, p)(k, p, p + 1) = (k + 1, …, p, p + 1).

Symmetric groups. There are analogous results for symmetric groups. This time we assume that our group T = ⟨X | R⟩ acts 2-transitively on {1, …, n} and does not lie in A_{n}; let w be a word in X that moves 1 when w is viewed inside T. As above, the obvious examples are AGL(1, p) and PGL(2, p).

Lemma 3.11. If J = ⟨X, z | R, z^{3} = 1, (zz^{w})^{2} = 1, [z, T_{1}] = 1⟩, then J has a normal subgroup T ∩ A_{n+2} modulo which it is S_{n+2}. Moreover, J is isomorphic to a subgroup of index 2 in S_{p+2} × T that projects onto each factor.

Proof. This time view T as a subgroup of S_{n+2} acting on {1, …, n, n + 1, n + 2} but fixing n + 1 and n + 2. Then S_{n+2} acts on a set of size n + 2, while T also acts on a set of size n. View S_{n+2} × T as acting on the disjoint union of these sets, and let H be the subgroup A_{2n+2} ∩ (S_{n+2} × T) of index 2 (recall that T is not inside A_{n}).

This time we map J into H using a simpler version of (??): φ(x) = (x, x) for x ∈ X. We identify T = ⟨X⟩ with a subgroup of J and z with an element of J. As before, T acts on z^{T} as it does on {1, …, n}, and hence is 2-transitive. Then the relation (zz^{w})^{2} = 1 and (??) imply that N := ⟨z^{T} ⟩ ≅ A_{n+2}. Since J/N ≅ T, we have |J| = |A_{n+2}||T | = |H|, so that J ≅ H. □

Corollary 3.12. Let p be a prime.

(i) S_{p+2} has a presentation with 3 generators, 6 relations and bit-length O(log p). (ii) If p ≡ 2 (mod 3) then the subgroup of index 2 in S_{p+2} ×AGL(1, p) that projects

onto each factor has a presentation with 2 generators, 3 relations and bit-length O(log p).

(iii) If p ≡ 2 (mod 3) then S_{p+2} has a presentation with 2 generators, 4 relations and bit-length O(log p).

Proof. Part (i) follows from the preceding lemma together with Example ??(2), while (ii) is proved exactly as in Corollary ?? by using that example. This time in (iii) we obtain

(3.13)  \begin{aligned}S_{p+2} ≅ ⟨a, g | & a^{p} = (g^{3})^{p−1}, (a^{s})^{g^{3}} =a^{s−1}, \\ & (g^{p−1}(g^{p−1})^{a})^{2}= (g^{6}(g^{p−1})^{a^{−1}}(g^{p−1})^{a^{−r}})^{(p+1)/2}= 1⟩ \end{aligned}

with s(r − 1) ≡ −1 (mod p and 𝔽_{p}^{∗} = ⟨r⟩. For, once again we view (ii) as a presentation with generators a and g, we use b := g^{3} and z := g^{p−1}, and then b^{2}z^{a^{−1}}z^{a^{−r}} = (b^{2}, b^{2})(z′^{a^{−1}}z′^{a^{−r}}, 1) = (c, b^{2}) for a (p + 1)/2-cycle c. Factoring out the normal closure of b^{p+1} = b^{2} in T, we obtain (??). □

Remark 3.14. For the presentation in Corollary ??, the assertions in Remark ?? hold once again for even permutations. They also hold for odd permutations if p ≡ 11 (mod 12).

Even permutations are handled as before. Odd permutations are slightly more delicate: they require constructing a transposition of the required bit-length, and we are only able to achieve this when p ≡ 11 (mod 12). First we recall a grouptheoretic version of “Horner’s Rule” [?, (3.3)] for elements v, f in any group:

(3.15)  vv^{f}v^{f^{2}} ⋯ v^{f^{n}} = (vf^{−1})^{n}vf^{n}

for any positive integer n.

Note that

b_{2} := b^{(p−1)/2} = (1, p − 1)(2, p − 2) ⋯ ((p − 1)/2, p − (p − 1)/2) is an odd permutation since p ≡ 3 (mod 4). We will use several additional permutations:

c(i, j) := z^{a^{−i}}(z^{a^{−j}})^{−1}z^{a^{−i}} = (i, j)(p + 1, p + 2) for 1 ≤ i, j ≤ p,

v_{•} := c(1, p − 1)c(2, p − 2) = (1, p − 1)(2, p − 2),

c_{(p−1)/2} := (c(1, 2)a)^{(p−1)/2−2}c(1, 2)a^{−((p−1)/2−2)} = (1, 2, …, (p − 1)/2) since (p − 1)/2 is odd (cf. (??)),

c_{•} := c_{(p−1)/2} c_{(p−1)/2}^{−a^{(p+1)/2}} = (1, 2, …, (p − 1)/2)(p − 1, p − 2, …, p − (p − 1)/2), and

v := (c(1, p − 1)c_{•}^{−1})^{(p−1)/2}c(1, p − 1)c_{•}^{(p−1)/2} = (c(1, p − 1)c_{•}^{−1})^{(p−1)/2}c(1, p − 1)

≡ (1, p − 1)(2, p − 2) ⋯ ((p − 1)/2, p − (p − 1)/2)(p + 1, p + 2) (cf. (??)). Then vb_{2} is the transposition (p + 1, p + 2), as required (compare Section ??).

We do not know if the final assertion in the preceding remark holds when p ≡ 1 (mod 4).

Examples 3.16. We summarize versions of the previous presentations for special values of n. Additional explicit presentations appear in Examples ??.

Consider a prime p > 3.

(1) A_{p+2} =⟨a, b, z |a^{p} = b^{p−1}, (a^{s})^{b} = a^{s−1}, z^{3} = (zz^{a})^{2} = 1, z^{b} = z^{−1}, (b^{a}z)^{p} = 1⟩, where s(r − 1) ≡ −1 (mod p) with 𝔽_{p}^{∗} = ⟨r⟩ (by Corollary ??).

(2) A_{p+2} for p ≡ 11 (mod 12): see (??).

(3) S_{p+2} for p ≡ 2 (mod 3): see (??).

(4) S_{p+2} =⟨a, b, z |a^{p} = b^{p−1}, (a^{s})^{b} = a^{s−1}, z^{3} = (zz^{a})^{2} =[z, b]= 1, (b^{2}z^{a^{−1}}z^{a^{−r}})^{p} =1⟩ for p ≡ 1 (mod 3), where s(r − 1) ≡ −1 (mod p) and 𝔽_{p}^{∗} = ⟨r⟩ (using Corollary ??).

(5) We will give several presentations of A_{p+3} both here and in Example ??(??). Let 𝔽_{p}^{∗} = ⟨j⟩ and jj̄ ≡ 1 (mod p). Then

\begin{aligned}A_{p+3} = ⟨x, y, z | & x^{2} = (xy)^{3}, (xy^{4}xy^{(p+1)/2})^{2}y^{p}x^{2[p/3]} = 1, \\ & z^{3} = (zz^{x})^{2} = [y, z] = [h, z] = 1, (hz^{(xy)^{−1}}z^{(xy^{j})^{−1}})^{(p+1)/2} = 1⟩, \end{aligned}

where we have abbreviated h := yj̄(y^{j})^{x}yj̄x^{−1}. This uses the following presentation for T := SL(2, p), obtained in [?] using [?]:

(3.17)  SL(2, p) = ⟨x, y | x^{2} = (xy)^{3}, (xy^{4}xy^{(p+1)/2})^{2}y^{p}x^{2[p/3]} = 1⟩,

where x and y arise from elements of order 4 and p, respectively. (These correspond to the matrices t and u given later in (??).) Then T_{1} = ⟨X_{1}⟩ with X_{1} := {y, h} in the notation used in Lemma ??; the final relation in the presentation for A_{p+3} is obtained as in the proof of Corollary ??(ii).

\begin{aligned}A_{p+3} = ⟨u, h, t, z | & u^{p} = t^{2} = 1, u^{h} = u^{j^{2}}, h^{t} = h^{−1}, t = uu^{t}u, ht = uj̄(u^{j})^{t}uj̄, \\ & z^{3} = (zz^{t})^{2} = [u, z] = [h, z] = 1, (hz^{(tu)^{−1}}z^{(tu^{j})^{−1}})^{(p+1)/2} = 1⟩. \end{aligned}

This uses Lemma ?? together with the presentation for T := PSL(2, p) given in [?, Theorem 3.6]. A similar presentation can be obtained using the presentation for PSL(2, p) in [?].

(6) Once again let 𝔽_{p}^{∗} = ⟨j⟩. Then

\begin{aligned}S_{p+3} = ⟨u, h, t, z | & u^{p} = t^{2} = 1, u^{h} = u^{j}, h^{t} = h^{−1}, t = uu^{t}u, \\ & z^{3} = (zz^{t})^{2} = [u, z] = [h, z] = 1, (hz^{tu})^{p+1} = 1⟩. \end{aligned}

This uses Lemma ?? together with a presentation ⟨u, h, t | u^{p} = t^{2} = 1, u^{h} = u^{j}, h^{t} = h^{−1}, t = uu^{t}u⟩ for T := PGL(2, p) analogous to [?, Theorem 3.6]. The final relation is obtained as in the proof of Corollary ??(iii). Once again one could also use [?] for a presentation of T .

3.2. Small n. In order to handle a few degrees n < 50 we will need further variations on the idea used in Corollaries ?? and ??. All of the general presentations below have bit-length O(log n), but this is not significant since our goal involves bounded n. We suspect that most readers will wish to skip this section.

In Table ?? we summarize the cases needed later. For this table and our variation on Corollaries ?? and ?? we use the following notation:

Table 1. Some small n

G  n  T  |R| ρ |X_{1}| |x_{1}| gens rels in Ex. ♯
S_{11} 9 + 2  AGL(1, 9)  4 1 1  8  2  6 ??(??)
A_{11} 9 + 2  PSL(2, 8)  2 2 1  4  2  5 ??(??)
A_{11} 9 + 2  AGL(1, 9)^{(2)}  4 2 1  4  2  7 ??(??)
S_{12} 10 + 2  PGL(2, 9)  3 1 2  8  2  6 ??(??)
A_{12} 10 + 2  6.PSL(2, 9)  2 1 2  8  2  5 ??(??)
A_{23} 21 + 2  12.PSL(3,4)  2 1 2  5  2  5 ??(??)
A_{23} \binom{7}{2} + 2 6.A_{7}  2 2 2  5  2  6 ??(??)
A_{24} 22 + 2  12.M_{22}  2 1 2  7  2  5 ??(??)
A_{24} 2 · 11 + 2 AGL(1, 11)^{(2)} × ℤ_{2} 2 3 1  5  2  6 ??(??)
A_{24} 2 · 11 + 2 AGL(1, 11)  2 4 1  5  2  7 ??(??)
A_{47} \binom{10}{2} + 2 A_{10}  2 2 2  8  2  6 ??(??)
A_{47} \binom{10}{2} + 2 A_{10}×SL(2, 7)  4 2 2  7  2  8 ??(??)
A_{48} 2 · 23 + 2 AGL(1, 23)^{(2)} × ℤ_{2} 2 3 1 11 2  6 ??(??)
A_{48} 2 · 23 + 2 AGL(1, 23)  2 4 1 11 2  7 ??(??)

• T is a group acting transitively (though not necessarily faithfully) on {1, …, n}.

• T has exactly ρ orbits of unordered pairs of distinct points.

• T = ⟨X | R⟩.

• T_{1} = ⟨X_{1}⟩, where T_{1} is again the stabilizer of 1.

• x_{1} ∈ X_{1} ∩ X has order k not divisible by 3.

• T is also viewed as a subgroup of Alt {1, …, n + 2}. Thus, ⟨T^{S_{n+2}}⟩ is A_{n+2} if T is in A_{n+2}, and S_{n+2} otherwise.

Proposition 3.18. If T is the normal closure of one of its elements, then ⟨T^{S_{n+2}}⟩ has a presentation with |X| generators and |R| + ρ + |X_{1}| relations.

If T ≤ A_{n} then A_{n+2} × T has a presentation with |X| generators and |R| + ρ + |X_{1}| − 1 relations.

Proof sketch. Let w_{1}, …, w_{ρ} be words in X such that the ρ pairs {1, w_{i}^{−1}(1)} are in different T -orbits. Let X = {x_{1}, … } and R = {r_{1}, … } with each r_{i} a word r_{i}(x_{1}, …) in X. Let X′ := X\ {x_{1}} and X′_{1} := X_{1}\ {x_{1}}. We claim that

J := ⟨X′, g | r_{i}(g^{3}, …) = 1 for all i,
[g^{k}, X′_{1}] = (g^{k}(g^{k})^{w_{j}})^{2} = 1 for all j⟩

is isomorphic to H := A_{2n+2} ∩ (S_{n+2} × T). For, view S_{n+2} × T as acting on the disjoint union {1, …, n, n + 1, n + 2} ˙∪ {1, …, n} with T fixing n+1 and n+2. Let z′:= (1, n + 1, n + 2) and let the integer ν satisfy 3ν ≡ 1 (mod k), so that g := x_{1}^{ν}z′ satisfies g^{3} = x_{1}. Then J surjects onto H as in the proof of Lemma ??.

We can identify T̃ := ⟨g^{3}, X′⟩ with a subgroup of J that is a homomorphic image of our original T. Our hypotheses guarantee that z := g^{k} commutes with X_{1}. Then |zT̃| = n, and we can use (??) as before. □

Examples ??(??) and ??(??) contain further variations on the idea behind the Proposition.

Examples 3.19. (1) n = 11: T = AGL(1, 9) has the presentation ⟨a, b | a^{3} = b^{8} = 1, a^{b^{2}} = aa^{−b}, [a, a^{b}] = 1⟩, ρ = |X_{1}| = 1 and |x_{1}| = 8, so that S_{11} has a presentation with 2 generators and 4 + 1 + 1 relations. However, for use in Theorem ?? it is easier simply to use the presentation of S_{11} with 2 generators and 6 relations in [?, p. 54] (cf. [?, p. 64]). See Remark ?? for a generalization.

(2) n = 11: T = PSL(2, 8) has a presentation with 2 generators and 2 relations [?], ρ = 1, |X_{1}| = 2 and |x_{1}| = 7, so that Proposition ?? produces a presentation of A_{11} with 2 generators and 2 + 2 + 1 relations. Once again, it has long been known that A_{11} has a presentation with 2 generators and 6 relations [?, p. 67].

(3) n = 11: T has index 2 in AGL(1, 9), T has the presentation ⟨a, b | a^{3} = b^{4} = 1, a^{b^{2}} = a^{−1}, [a, a^{b}] = 1⟩, ρ = 2, |X_{1}| = 1 and |x_{1}| = 4, so that A_{11} has a presentation with 2 generators and 4 + 2 + 1 relations. See Remark ?? for a generalization.

(4) n = 12: T = PGL(2, 9) has presentations with 2 generators and 3 relations provided by G. Havas [?]. The following are some of his many presentations related to A_{6}:

\begin{aligned}PGL(2, 9) & = & ⟨a, b | b^{5} = (aba)^{2} = ab^{−1}a^{4}ab^{−1}a^{3}b^{−1}ab^{2} = 1⟩ \\ PGL(2, 9) & = & ⟨a, b | b^{8} = baba^{3}bab^{2} = b^{−1}a^{−1}b^{−2}a^{2}ba^{2}b^{−1} = 1⟩ \\ S_{6} & = & ⟨a, b | a^{−1}b^{−1}a^{3}b^{−1}a^{−2} = (ab)^{5} = b^{−3}a^{−1}b^{−1}a^{2}b^{−2}aba = 1⟩ \\ S_{6} & = & ⟨a, b | a^{4} = b^{−1}ab^{−2}a^{2}b^{2}a^{−1}b^{−1} = aba^{−1}b^{−1}a^{−2}b^{−1}aba^{−1}b = 1⟩. \end{aligned}

This time ρ = 1, |X_{1}| = 2 and we may assume that |x_{1}| = 8, so that S_{12} has a presentation with 2 generators and 3 + 1 + 2 relations. Once again, it has long been known that S_{12} has a presentation with 2 generators and 7 relations in [?, p. 54] (cf. [?, p. 64]).

(5) n = 12, T ≅ 6.PSL(2, 9) ≅ 6.A_{6} has a presentation with 2 generators and 2 relations [?], ρ = 1, |X_{1}| = 2 and |x_{1}| = 8, so that A_{12} has a presentation with 2 generators and 2 + 1 + 2 relations. Once again, it has long been known that A_{12} has a presentation with 2 generators and 7 relations [?, p. 67].

(6) n = 23: T = 12.PSL(3, 4) has a presentation with 2 generators and 2 relations [?], ρ = 1, |X_{1}| = 2 and |x_{1}| = 5, so that Proposition ?? produces a presentation of A_{23} with 2 generators and 2 + 2 + 1 relations.

(7) n = 23: T = 6.A_{7} has a presentation with 2 generators and 2 relations [?], n = \binom{7}{2}, ρ = 2, |X_{1}| = 2 and |x_{1}| = 5, so that A_{23} has a presentation with 2 generators and 2 + 2 + 2 relations.

(8) n = 24: T = 12.M_{22} has a presentation with 2 generators and 2 relations [?], ρ = 1, |X_{1}| = 2 and |x_{1}| = 7, so that Proposition ?? produces a presentation of A_{24} with 2 generators and 2 + 2 + 1 relations.

(9) If p > 3 is prime then A_{p+3} × SL(2, p) has a presentation with 2 generators and 4 relations. Namely, apply Proposition ?? using (??) and |R| = 2 = |X_{1}|, ρ = 1, x_{1} = y. It follows that A_{p+3} has a presentation with 2 generators and 5 relations. We will need this below in (??).

Explicitly, as in Example ??(??) we have

\begin{aligned}A_{p+3} = ⟨x, g | & x^{2} = (xg^{3})^{3}, (xg^{12}xg^{3(p+1)/2})^{2}g^{3p}x^{2[p/3]} = 1, \\ & [g^{p}, h] = (g^{p}(g^{p})^{x})^{2} = 1, (h(g^{p})^{xg^{3}})^{p+1} = 1⟩, \end{aligned}

where h := g^{3}j̄(g^{3}^{j})^{x}g^{3}j̄x^{−1} with 𝔽_{p}^{∗} = ⟨j⟩ and jj̄ ≡ 1 (mod p).

(10) n = 47: T = A_{10} has the following presentation with 2 generators and 3 relations [?]:

A_{10} =⟨a, b|a^{3}b^{−1}ab^{−1}a^{3}ba^{2}b = a^{2}b^{−1}a^{5}b^{−3}a^{3} = a^{−2}bab^{−1}aba^{3}bab^{−1}aba^{−2}b^{−1} = 1⟩,

with |a| = 15, |b| = 12 and |ab| = 8; hence we modify this presentation so that the generators are a and ab. View T as acting on \binom{10}{2} unordered pairs with ρ = 2, |X_{1}| = 2 and x_{1} = ab, so that Proposition ?? produces a presentation of A_{45+2} with 2 generators and 2 + 2 + 2 relations.

(11) If p > 3 is prime then A_{\binom{p+3}{2}+2} has a presentation with 2 generators and 8

relations. For, let T = A_{p+3} × SL(2, p) act on \binom{p+3}{2} unordered pairs of a set of size p+3, with SL(2, p) acting trivially. Apply Proposition ?? using (??), with |X| = 3, |R| = 4, ρ = 2, |X_{1}| = 2 and x_{1} = y. (Note that x_{1} fixes p + 2 and p + 3 in (??).)

There is a similar presentation for A_{\binom{p+2}{2}+2}.

(12) For any prime p ≡ 11 (mod 12), A_{2p+2} has a presentation with 2 generators and 6 relations. We will vary the argument in Proposition ?? (and Lemma ??), using the transitive subgroup T := AGL(1, p)^{(2)}×⟨t⟩ of the transitive group AGL(1, p)×⟨t⟩ of degree 2p, where t is an involution interchanging two blocks of size p. Note that the stabilizer of a point is cyclic of odd order (p−1)/2. Moreover, T has ρ = 3 orbits of unordered pairs of the 2p-set, with orbit-representatives as follows: contained in a block, or of the form {p, t(p)}, or of the form {p, t(1)} (since t interchanges {p, t(1)} and {1, t(p)}).

We view T as a subgroup of A_{2p+2} preserving the two new points 2p + 1 and 2p + 2, with t interchanging these points.

Let

J := ⟨a, g | a^{2p} = b^{(p−1)/2}, (a^{s})^{b} = a^{s−2}, (zz^{sign(w_{i})w_{i}})^{2} = 1 (i = 1, 2, 3)⟩

where s(r − 1) ≡ −2 (mod p) with s odd and r of order (p − 1)/2 (mod p), b := g^{3}, z := g^{(p−1)/2}, and suitable words w_{1}, w_{2}, w_{3} ∈ T (such that the pairs {z, z^{w_{i}}} are in different T -orbits on the 2p-set z^{T}); here sign refers to the behavior on the 2p points. For example, {z, z^{t}}, {z, z^{a^{2}}} and {z, z^{a^{2}t}} are representatives of these T -orbits. As in the proof of Proposition ??, using Example ??(4) we see that A_{2p+2} × T satisfies our presentation.

As usual, using Example ??(4) we can view T as the subgroup ⟨a, b⟩ of J. Exactly as in Lemma ?? (and Proposition ??), |z| = 3, |z^{T} | = 2p, and (zz^{g})^{2} for all g ∈ AGL(1, p)^{(2)} with z^{g} ≠ z while (zz^{−gt})^{2} = 1 for all g ∈ AGL(1, p)^{(2)}.

Then N :=⟨z^{T} ⟩ ≅ A_{2p+2} by (??),and hence J = NT ≅ A_{2p+2}×AGL(1, p)^{(2)}×⟨t⟩. One further relation gives a presentation of A_{2p+2} with 3 generators and 2 + 3 + 1 relations.

Explicitly:

\begin{aligned}A_{2p+2} = ⟨a, g | & a^{2p} = b^{(p−1)/2}, (a^{s})^{b} = a^{s−2}, \\ & (zz^{−t})^{2} = (zz^{a^{2}})^{2} = (zz^{−a^{2}t})^{2} = 1, (tbz^{a^{−1}}z^{a}z^{ta^{−1}}z^{ta})^{p} = 1⟩, \end{aligned}

with z, r and s as above and once again b := g^{3}, z := g^{(p−1)/2} and t := a^{p}, where the last relation is obtained as in the proof of Corollary ??(ii).

(13) For any odd prime p ≡ 2 (mod 3), A_{2p+2} has a presentation with 2 generators and 7 relations. One difference between this example and the preceding one is that we now handle the case p ≡ 1 (mod 4) using T = AGL(1, p).

First note that T acts transitively on a set of size 2p, with cyclic point stabilizer of order (p − 1)/2 and ρ = 4 orbits on unordered pairs of points. We again view T as a subgroup of A_{2p+2} preserving the additional points 2p + 1 and 2p + 2. Once again signs will refer to the actions of elements of T on the 2p-set.

We replace the presentation of T in Example ??(1) by

T = ⟨x, b | (xb^{−2})^{p} = b^{p−1}, ((xb^{−2})^{s})^{b} = (xb^{−2})^{s−2}⟩,

with x := ab^{2} ∈ T of order (p − 1)/2 fixing the point r′ := (1 − r^{2})^{−1}, and r and s as in Example ??(1).

Consider the group

J :=⟨g, b|(xb^{−2})^{p} = b^{p−1}, ((xb^{−2})^{s})^{b} = (xb^{−2})^{s−2}, (zz^{sign(w_{i})w_{i}})^{2} = 1 (i = 1, 2, 3, 4)⟩,

where x := g^{3}, z := g^{(p−1)/2}, and {r′, w_{i}^{−1}(r′)}, 1 ≤ i ≤ 4, are representatives for the orbits of T on pairs of the 2p points. Then J surjects onto A_{2p+2} × T, and we can view T = ⟨x, b⟩ ≤ J. In particular, |g| = 3(p − 1)/2 and so z^{3} = 1.

Since x centralizes z, as usual we obtain |z^{T} | = 2p and N := ⟨z^{T} ⟩ ≅ A_{2p+2} by (??), and then J ≅ A_{2p+2} × T. One further relation produces the desired presentation.

3.3. Gluing alternating and symmetric groups. We now turn to the case of all alternating and symmetric groups, starting with a general gluing lemma:

Lemma 3.20. Let G = ⟨X | R⟩ and Ḡ = ⟨X̄ | R̄⟩ be presentations of S_{n} and S_{m}, respectively, and let m, n > k ≥ l + 2 ≥ 4. Consider embeddings π: G → S_{m+n−k} and π̄: Ḡ → S_{m+n−k} into Sym {−m + k + 1, …, n} such that

π(G) = Sym({1, …, n}) and π̄(Ḡ) = Sym({−m + 1 + k, …, k}).

Suppose that a, b, c, d ∈ G and ā, b̄, c̄, ē ∈ Ḡ, viewed as words in X or X̄, respectively, are nontrivial permutations such that

• π(a) = π̄(ā) ∈ Sym({1, …, l}) < π(G) ∩ π̄(Ḡ),

• π(b) = π̄(b̄) ∈ Sym(l + 1, …, k) < π(G) ∩ π̄(Ḡ),

• π(c) = π̄(c̄) ∈ Sym({1, …, k}) < π(G) ∩ π̄(Ḡ),

• π(d) ∈ Sym({l + 1, …, n}) < π(G), • π̄(ē) ∈ Sym({−m + 1 + k, …, l}) < π̄(Ḡ),

• ⟨π(a), π(c)⟩ = Sym({1, …, k}) < π(G) ∩ π̄(Ḡ),

• ⟨π(b), π(d)⟩ = Sym({l + 1, …, n}) < π(G), and

• ⟨π̄(ā), π̄(ē)⟩ = Sym({−m + 1 + k, …, l}) < π̄(Ḡ). Then

(3.21)  J = ⟨X, X̄ | R, R̄, a = ā, c = c̄, [d, ē] = 1⟩

is a presentation of S_{m+n−k} = Sym {−m + k + 1, …, n}, where ⟨X⟩ = S_{n} acts on {1, …, n} and ⟨X̄⟩ = S_{m} acts on {−m + 1 + k, …, k}.

The following picture might be helpful.

\underline{−m + k + 1, …, 0  1, …, l  l + 1, …, k  k + 1, …, n}
\underline{a = ā}  \underline{b = b̄}
\underline{c = c̄}
\underline{ē}  \underline{d}

Proof. The restrictions on m, n, k and l are designed to guarantee that the desired permutations exist. There is a surjection J → S_{m+n−k} (note that our 3 extra relations are satisfied). By Lemma ??, J has subgroups we identify with G = ⟨X⟩ = S_{n} and Ḡ = ⟨X̄⟩ = S_{m}.

By our relations, a = ā and c = c̄. Then the assumption π(b) = π̄(b̄) states that b and b̄ represent the same element of ⟨a, c⟩ = ⟨ā, c̄⟩, so that the additional relation b = b̄ is forced to hold in J. Then we also have the following relations:

• [d, ā] = [d, a] = 1 because d, a ∈ G = S_{n} have disjoint supports,

• [d, ē] = 1 by the last relation in the presentation (??),

• [b, ā] = [b, a] = 1 because b, a ∈ G have disjoint supports, and

• [b, ē] = [b̄, ē] = 1 because b̄, ē ∈ Ḡ have disjoint supports. Therefore

(3.22)  [⟨b, d⟩, ⟨ā, ē⟩] = 1,

where ⟨b, d⟩ = Sym({l + 1, …, n}) and ⟨ā, ē⟩ = Sym({−m + 1 + k, …, l}).

The symmetric groups G and Ḡ are generated, respectively, by the n − 1 and m − 1 transpositions x_{i} := (i, i + 1), 1 ≤ i < n, and x_{i} := \overline{(i, i + 1)}, −m + 1 + k ≤ i < k. The identification of the two copies of S_{k} = ⟨a, c⟩ = ⟨ā, c̄⟩ in (??) identifies the transpositions x_{i}, 1 ≤ i < k, common to these generating sets, producing a generating set of J consisting of m+n−k −1 involutions. These involutions satisfy the relations in the Coxeter presentation [?]

S_{m+n−k} = ⟨x_{i}, −m + 1 + k ≤ i < n | x_{i}^{2} = (x_{i}x_{i+1})^{3} = (x_{i}x_{j})^{2} = 1

for all possible i, j with j − i ≥ 2⟩:

any two x_{i} either both lie in G, or both lie in Ḡ, or they commute by (??) since one is in ⟨b, d⟩ and the other is in ⟨ā, ē⟩. □

There is a great deal of flexibility in the choice of the elements a, b, c, d, ā, b̄, c̄, ē. In the proof of Theorem ?? we will need to require that |a| = 3, which is possible provided that l ≥ 3.

The last three relations in (??) are similar to ones used in the proof of [?, Theorem 3.17]; and they are used both there and here in essentially the same manner.

However, the situation in that paper was more delicate, due to length considerations: the preceding presentation does not even have bit-length O(log n). We will deal with this requirement when we use this lemma in the proof of Theorems ?? and ??.

Lemma 3.23. A presentation of A_{m+n−k} is obtained as in the preceding lemma by replacing symmetric groups by alternating groups throughout (??) and assuming that m, n > k ≥ l + 3 ≥ 6.

Proof. Once again, the restrictions on m, n, k and l are designed to guarantee that the desired permutations exist. The previous picture can again be used. As in the proof of the preceding lemma, (??) implies that (??) holds.

We will use the presentation (??) with the union of the the generating sets x_{i} := (1, 2, i) for G and x_{j} := \overline{(1, 2, j)} for Ḡ, where 3 ≤ i ≤ n and −m+1+k ≤ j ≤ k but j ≠ 1, 2. As above, (??) implies that (1, 2, i) = \overline{(1, 2, i)} if 3 ≤ i ≤ k.

Then all required relations in (??) are obvious except for

((1, 2, i)\overline{(1, 2, j)})^{2} = 1 with k < i ≤ n and −m + 1 + k ≤ j ≤ 0.

Recall that ⟨b, d⟩ = Alt({l + 1, …, n}) < G = Alt({1, …, n}), where 6 ≤ l + 3 ≤ k < i ≤ n. Then some g ∈ ⟨b, d⟩ sends k to i and fixes 1 and 2. By (??), g commutes with \overline{(1, 2, j)} ∈ ⟨ā, ē⟩. Consequently,

[((1, 2, i)\overline{(1, 2, j)})^{2}]^{g} = ((1, 2, k)\overline{(1, 2, j)})^{2} = (\overline{(1, 2, k)} \overline{(1, 2, j)})^{2} = 1,

as required in (??). □

Corollary 3.24. If A_{m} has a presentation with M relations and if m > k ≥ 6, then A_{2m−k} has a presentation with M + 4 relations. The same holds for the corresponding symmetric groups using the weaker assumption m > k ≥ 4.

Proof. Let G = ⟨X | R⟩ be a presentation for A_{m} with M relations. In Lemma ?? we use m = n and l = 3, but this time we introduce an additional generator y corresponding to an even permutation sending {1, …, m} → {−m + 1 + k, …, k} and inducing the identity on {1, …, k}.

Consider the group

(3.25)  J := ⟨X, y | R, a = a^{y}, c = c^{y}, [d, e^{y}] = 1⟩,

with a, b, c, d, ā := a^{y}, b̄ := b^{y}, c̄ := c^{y}, ē := e^{y} playing the same roles as in Lemma ??. By that lemma with X̄ := X^{y} and R̄ := R^{y}, J has a subgroup K := ⟨X, X^{y}⟩ ≅ A_{2m−k}.

Finally, we add an extra relation to ensure that our generator y is in K and that, as an element of A_{2m−k}, the action of y on {−m + k + 1, …, m} is as described above.

The group S_{2m−k} is dealt with in the same manner. □

Remark 3.26. We have just glued two subgroups A_{m} in order to obtain a group A_{2m−k}, or two subgroups S_{m} in order to obtain a group S_{2m−k}, in each case with suitable restrictions on m and k. There is a variation on this process that glues two subgroups S_{m} in order to obtain a group A_{2m−k} (view S_{m} as lying in A_{m+2}, as was done on occasion in Section ??).

3.4. All alternating and symmetric groups. Before proving Theorem ??, we begin with a weaker result:

Proposition 3.27. For all n ≥ 5, A_{n} and S_{n} have presentations with 3 generators and 10 relations.

Proof. If n ≤ 10 then n = p + 2 or p + 3 for a prime p, and we have already obtained a presentation with fewer relations than required. By Ramanujan’s version of Bertrand’s Postulate [?], in all other cases we can write n = 2p + 4 − k for a prime p and an integer k such that m := p + 2 > k ≥ 6, and then use Corollaries ?? and ??. (A related use of Bertrand’s Postulate appears in [?, Theorem 3.9].) □

This proposition is weaker than Theorem ?? in two significant ways: the number of relations is larger than in that theorem, and bit-length is not mentioned. We deal with the second of these as follows:

Lemma 3.28. In Corollary ?? and Proposition ??, it is possible to choose a, c, d, e such that a is a 3-cycle and the resulting presentation has bit-length O(log n) with a bounded number of exponents, each of which is at most n, if either

(i) the group is A_{n}, or (ii) the group is S_{n} and we used a prime p ≡ 11 (mod 12).

Proof. In Lemma ?? and Corollary ?? we can choose each of the elements a, c, d, e to be a product of a cycle of the form (i, …, j) with i < j and a permutation having bounded support (in fact, in Section ?? each will be chosen to be a cycle). We require a to be a 3-cycle (this is needed in Theorem ??); and then in the symmetric group case we will need c and e to be odd permutations (cf. the hypotheses of Lemma ??).

By Remark ??, when we glue two copies of A_{p+2} using relations of bit-length O(log n), the bit-length and exponents are as required, except perhaps for the crucial additional relation expressing y as word in X ∪ X^{y}.

We now consider y; there is a reasonable amount of flexibility in the choice of y in Corollary ?? (recall that m = p + 2). In that corollary we were permuting the n = 2p + 4 − k points

(3.29) −p − 1 + k, −p + k, ⋯ − 1, 0; 1, …, k; k + 1, k + 2, …, p + 1, p + 2,

where we have alternating or symmetric groups on the first and last p + 2 points, with an A_{k} or S_{k} on the overlap.

If p − k is even then we choose y to be the following product of p + 2 − k transpositions:

(3.30)  y := (−p − 1 + k, p + 2)(−p + k, p + 1) ⋯ (−1, k + 2)(0, k + 1).

We use the following additional permutations:

• x := (−1, k+2)(0, k+1) = [(1, k+2)(2, k+1)]^{(−1,1)(0,2)}, which we have written using permutations from the two alternating groups, and

• u^{−1} := (1, …, k, k + 1, …, p + 2)(1, …, k, 0, −1, …, −p + k − 1)

= (1, …, k, k + 1, …, p + 2)(1, …, k, k + 1, …, p + 2)^{y}.

By Remarks ?? and ??, u and hence also s can be expressed as a word of bit-length O(log p) in X ∪ X^{y} using a bounded number of exponents; then so can

(3.31)  y = xx^{u^{2}}x^{u^{4}} ⋯ x^{u^{p−k}} = (xu^{−2})^{(p−k)/2}xu^{p−k},

using (??).

If p − k is odd let v := (−p − 1 + k, p + 2)(−p + k, p + 1) ⋯ (−3, k + 4) and use

(3.32)  \begin{matrix}y := & v(−2, k + 3)(−1, k + 2, 0, k + 1) \\ = v[(2, k + 3)(1, k + 2, k, k + 1)]^{(2,−2)(1,−1)(0,k)}. \end{matrix}

Then v can be expressed as a word of bit-length O(log p) in X ∪ X^{y} using a calculation similar to (??), and the final term in y is a product of permutations from the two copies of A_{p+2}. Another application of Remarks ?? and ?? completes the proof of (i).

Now (ii) follows from Remark ??. □

Remark 3.33. Using Remark ?? we see that every cycle (k, k +1, …, l) and every element with bounded support in A_{n} has bit-length O(log n) in our generators.

With a bit more number theory, together with Table ??, we obtain an improvement of Proposition ?? that is needed for Theorem ??:

Proposition 3.34. If n ≥ 5 then S_{n} and A_{n} have presentations with 3 generators, 8 relations and bit-length O(log n). Moreover, these presentations use a bounded number of exponents, each of which is at most n.

Proof. We refine the argument in Proposition ??. First consider S_{n}. Here we need to write n = 2p + 4 − k for a prime p ≡ 2 (mod 3) such that m := p + 2 > k ≥ 4, so that we can use Corollaries ?? and ??, and then continue as in the proof of Proposition ??. In view of the requirements on bit-length and exponents, we also require that p ≡ 11 (mod 12) if n ≥ 50, so that Lemma ?? will complete the proof for S_{n}.

According to Dirichlet’s Theorem, for large x there are approximately x/2 log x primes ≤ x of the stated sort, and subtraction yields a prime p in our situation. However, we need a more precise (and effective) result of this type. This is provided in [?] (updating [?, ?, ?] with more precise estimates): if n ≥ 50 then there is such a prime p ≡ 11 (mod 12). A straightforward examination of the cases n < 50 leaves n = 11, 12 or 13 to be dealt with. See [?, p. 54] for presentations of S_{11}, S_{12} and S_{13} with 2 generators and 6, 7 and 7 relations, respectively (cf. [?, p. 64]). (Note that Table ?? contains the cases n = 11, 12, while Corollary ??(i) handles the case n = 13.)

For A_{n} we need to write n = 2p + 4 − k for a prime p ≡ 11 (mod 12) such that m := p+2 > k ≥ 6, then use Corollaries ?? and ??, and again finish as in the proof of Proposition ??, using Lemma ??. Once again, by [?, ?], if n ≥ 50 then there is such a prime p. Another straightforward examination leaves the cases n ≤ 13 and n = 21, 22, 23, 24, 25, 45, 46, 47, 48 or 49 to be dealt with. The cases in which n = p + 2 or p + 3 for some prime p are handled using examples described earlier, and Table ?? handles the remaining cases. (For presentations of A_{11}, A_{12} and A_{13} using 2 generators and 6, 7 and 7 relations, respectively, see [?, p. 67].) □

For the next theorem we will use a presentation in the preceding proposition that is valid for most n. If n ≥ 50 (or, more precisely, if n is not one of the exceptions mentioned in the above proof) then (??) together with one further relation is such a presentation:

(3.35)  A_{n} or S_{n} = ⟨X, y | R, a = a^{y}, c = c^{y}, [d, e^{y}] = 1, y = w⟩,

with ⟨X | R⟩ in (??) or (??) for A_{n} or S_{n}, respectively, a, c, d, e as in Lemma ??, and a suitable word w in X ∪ X^{y} as in (??)–(??). (The properties required of y and w are described at the end of the proof of Corollary ?? and, in gory detail, in the proof of Lemma ??.)

We are now able to prove Theorem ??:

Theorem 3.36. If n ≥ 5 then S_{n} and A_{n} have presentations with 3 generators, 7 relations and bit-length O(log n). Moreover, these presentations use a bounded number of exponents, each of which is at most n.

Proof. Let n = 2m − k with m = p + 2 > k ≥ 6 (cf. the preceding proposition; below we will discuss the existence of a suitable prime p).

Let G = ⟨X | R⟩ be the presentation in Corollary ??(i) or ??(ii), so that |X| = 2, |R| = 3 and one of the following holds:

A_{n} case: T = ⟨a, b⟩ = AGL(1, p)^{(2)} p ≡ 11 (mod 12) G ≅ A_{m} × T
S_{n} case: T = ⟨a, b⟩ = AGL(1, p)  p ≡ 2 (mod 3)  G/(1 × T) ≅ S_{m}.

(In the A_{n} case T has index 2 in AGL(1, p); in the S_{n} case G has index 2 in S_{m}×T.) We also require that p ≡ 11 (mod 12) in the S_{n} case when n ≥ 50.

Let t ∈ T be such that T ∩ A_{m} = ⟨(t^{3})^{T} ⟩ (for example, t = b^{2} works since p ≡ 2 (mod 3) and the order of b is odd in the A_{n} case).

Then the presentation (??) of A_{n} or S_{n} can be rewritten

(3.37)  ⟨X, y | R, t^{3}, a^{y} = a, c^{y} = c, [d^{y}, e] = 1, y = w⟩.

There was a great deal of freedom in our choice of the elements a, b, c, d, e in the proofs of Lemmas ?? and ?? (and Corollary ??). As in Lemma ??, we now choose a so that its image in the alternating or symmetric group G/(1 × T) is a 3-cycle (for the S_{n} case, this requires c to be an odd permutation and l ≥ 3 in the proof of Lemma 3.15).

The presentation (??) has 8 relations and bit-length O(log n).

We use the following additional ingredients:

• Write a ∈ G as a = (a_{1}, ∗) ∈ A_{m} × T with a_{1} of order 3.

• Let ā and â be words in X such that ā = (a_{1}, 1) and â = (a_{1}, t) when evaluated in G.

We claim that the 7-relator group

(3.38)  J := ⟨X, y | R, ā^{y} = â, c^{y} = c, [d^{y}, e] = 1, y = w⟩

is isomorphic to the group in (??).

For, we can view G = ⟨X⟩ ≤ J. Then a, ā, â, c, d, e ∈ J.

Since both ā^{y} = â = (a_{1}, t) and a_{1} have order 3 we have (1, t)^{3} = 1 in J. Thus, J satisfies the presentation (??) and hence is as claimed.

Bit-length: As in the proof of Theorem ??, a, c, d and e can be expressed as words in X of bit-length O(log n) mod T. Since T = ⟨a⟩⟨b⟩ in Corollaries ?? and ??, ā and â have bit-length O(log n) as well.

Finally, we need to discuss whether we have handled all groups A_{n} and S_{n}; or, what amounts to the same thing, for which n a prime p can be found satisfying all of the conditions we have imposed.

As in Proposition ??, (??) takes care of A_{n} except for the cases n ≤ 13 and n = 21, 22, 23, 24, 25, 45, 46, 47, 48, 49; and these are handled exactly as in that proposition.

For the S_{n} case we have imposed a further condition beyond what was used in Proposition ??: we need to write n = 2p + 4 − k for a prime p ≡ 2 (mod 3) such that m = p + 2 > k ≥ l + 2 ≥ 5, and p ≡ 11 (mod 12) if n ≥ 50. (The conditions in Corollary ?? were m = p + 2 > k ≥ l + 2 ≥ 4, but here we need to be able to find a 3-cycle a in A_{l}.) Once again these requirements can be met for all n except if n < 6 or n = 9, 10, 11, and those cases can be handled as before. □

None of the presentations in this or the preceding section has length O(log n). By Remarks ?? and ??, the exponents in (??) are all less than n; there is

also an exponent p + 1 − k used to write u in that remark. As already noted, these presentations have bounded expo-length (cf. Section ??). See Remark ?? in Section ?? for comments concerning the boundedness of expo-length for other families of almost simple groups.

Before continuing, we note the following simple improvement of [?, Lemma 2.1].

Lemma 3.39. Let G = ⟨D⟩ be a finite group having a presentation ⟨X | R⟩; let π: F_{X} → G be the natural map from the free group F_{X} on X. Then G also has a presentation ⟨D | R′⟩ such that |R′| = |D| + |R| − |π(X) ∩ D|.

Proof. We recall the simple idea used in the proof of [?, Lemma 2.1]. Write each x ∈ X as a word v_{x}(D) in D, and each d ∈ D as a word w_{d}(X) in X; and let V (D) = {v_{x}(D) | x ∈ X}. According to the proof of [?, Lemma 2.1], we then obtain another presentation for G:

G = ⟨D | d = w_{d}(V (D)), r(V (D)) = 1, d ∈ D, r ∈ R⟩.

For each d ∈ π(X) ∩ D, one of the above relations can be taken to be d = d, and hence can be deleted. □

In view of the desire in [?] for specific generators (namely, (1, 2) and (1, 2, …, n)), we note the following consequence of the preceding theorem and lemma:

Corollary 3.40. Let G = A_{n} or S_{n}, n ≥ 5.

(i) If a and b are any generators of G, then there is a presentation of G using 2 generators that map onto a and b, and 9 relations.

(ii) There is a presentation of G using 2 generators and 8 relations.

We do not have information concerning the bit-length of any of the resulting presentations.

Proof. Part (i) follows from Theorem ?? and the preceding lemma, using |π(X) ∩ D| ≥ 0.

For (ii), note that we have provided a presentation ⟨X | R⟩ for G such that some element of X projects onto an element a ∈ G that is either a 3-cycle (z in Lemma ??) or has a power that is a 3-cycle (such as g in Corollary ??(ii) or Proposition ??). Let b be any element of G such that G = ⟨a, b⟩. Now use D = {a, b} in the preceding corollary (compare Section ??, Remark ??). □

3.5. An explicit presentation for S_{n}. The presentations in Sections ?? and ?? are not difficult to understand, and they visibly encode information concerning various alternating and symmetric groups. However, the presentations in Theorem ?? are not as explicit as one might wish. Therefore, we will provide a presentation of S_{n} for n odd (see Remark ?? for even n). Although this presentation is in no sense elegant or informative, it does have the significant advantage of using only 7 relations.

Find a prime p ≡ 11 (mod 12) such that n − 1 ≥ p ≥ (n + 2)/2. (This places a mild restriction on n, as seen in the proof of Theorem ?? . For n ≥ 50 there is always such a prime.)

Let k = 2p + 4 − n, so that p + 2 > k ≥ 6. Then k ≡ n ≡ 1 (mod 2), so that p − k is even.

The desired presentation is

S_{n} = ⟨a, g, y | a^{p} = (g^{3})^{p−1}, (a^{s})^{g^{3}} =a^{s−1}, (g^{p−1}(g^{p−1})^{a})^{2}= 1,
a^{y} = â, c^{y} = c, [d^{y}, e] = 1, y = w⟩,

for words a, c, d, e, â, w defined below and integers r and s such that s(r − 1) ≡ −1 (mod p) and 𝔽_{p}^{∗} = ⟨r⟩.

Notes: In order to conform with the notation in Section ??, we view AGL(1, p) as acting on {1, …, p} with a ≡ (1, …, p) ∈ AGL(1, p), but we use p in place of 1 in Lemma ??. Finally, we use a in place of a since the latter plays a prominent role in Section ??.

The permutations in S_{n} indicated below are not part of the presentation, but are provided in order to help keep track of the map ⟨a, g, y⟩ → S_{n} into the symmetric group on the n points (??). The notation used here should not be viewed mod p.

(1) z := g^{p−1} ≡ (p, p + 1, p + 2), b := g^{3} (so that ⟨a, b⟩ = AGL(1, p)),

(2) z(i) := z^{a^{−i}} ≡ (i, p, p + 1) for 1 ≤ i ≤ p, c(i, j) := z(−i)z(−j)^{−1}z(−i) ≡ (i, j)(p + 1, p + 2) for 1 ≤ i < j ≤ p, c_{i} := (c(1, 2)a)^{i−2}c(1, 2)a^{−(i−2)} ≡ (1, 2, …, i) with i odd and 3 ≤ i ≤ p (cf. (??)).

(3) (Constructing a transposition)

b_{2} := b^{(p−1)/2} ≡ (1, p − 1)(2, p − 2) ⋯ ((p − 1)/2, p − (p − 1)/2),

c_{•} := c_{(p−1)/2}c_{(p−1)/2}^{−a^{(p+1)/2}} ≡ (1, 2, …, (p − 1)/2)(p − 1, p − 2, …, p − (p − 1)/2),

v := (c(1, p − 1)c_{•}^{−1})^{(p−1)/2}c(1, p − 1)c_{•}^{(p−1)/2}

≡ (1, p − 1)(2, p − 2) ⋯ ((p − 1)/2, p − (p − 1)/2)(p + 1, p + 2) (cf. (??)), t := vb_{2}c(1, 2) ≡ (1, 2).

(4) a := z(3)^{z(1)z(2)} ≡ (1, 2, 3), c := tc_{k} ≡ (2, …, k) (an odd permutation), d := c_{3}^{−1}az ≡ (3, …, p + 2), e := ac_{k}^{−1}tz ≡ (1, 2, k + 1, …, p + 2), so that e^{y} ≡ (1, 2, 0, −1, …, −p + k − 1) (also odd permutations).

(5) â := a(b^{2}z(1)z(−1))^{(p+1)/2} ∈ {a} × T.

(6) x := [c(1, k + 2)c(2, k + 1)]^{c(1,k+2)^{y}c(2,k+1)^{y}}

≡ (−1, k + 2)(0, k + 1) = [(1, k + 2)(2, k + 1)]^{(−1,1)(0,2)}, u^{−1} := (az)(az)^{y}

≡ (1, …, k, k + 1, k + 2, …, p, p + 1, p + 2)(1, …, k, 0, −1, …, −p + k − 1), w := (xu^{2})^{(p−k)/2}xu^{−(p−k)}

≡ (−p − 1 + k, p + 2)(−p + k, p + 1) ⋯ (−1, k + 2)(0, k + 1) (cf. (??).

Remarks 3.41. 1. In the isomorphism given by (??), z maps to an element of A_{p+2} × {1}. Hence, the element a defined above also maps into A_{p+2} × {1}, so that the element ā used in (??) is just our a. The remainder of the presentation given above is just a straightforward translation from Section ??.

2. A presentation for the alternating groups is similar but slightly simpler: only even permutations are involved.

3. Changes needed when n and k are even: (4′) c := c_{k−1}t ≡ (1, …, k) (an odd permutation),

e := atc_{k−1}^{−1}z ≡ (1, k + 1, …, p + 2) (another odd permutation).

(6′) w := t^{az}t^{az}^{y}t^{az}(xu^{2})^{(p−k−1)/2}xu^{−(p−k−1)} ≡ (−p − 1 + k, p + 2)(−p + k, p + 1) ⋯ (−1, k + 2)(0, k + 1) as before.

3.6. Weyl groups. It is easy to use Theorem ?? to obtain presentations for the Weyl groups of types B_{n} or D_{n}. However, we leave this to the reader, dealing instead with a subgroup W_{n} of those Weyl groups that is needed later (in Section ??).

Let W_{n} := ℤ_{2}^{n−1}⋊A_{n} be the subgroup of the monomial group of ℝ^{n} such that ℤ_{2}^{n−1} consists of all ±1 diagonal matrices of determinant 1, and the alternating group A_{n} permutes the standard basis vectors of ℝ^{n}.

Proposition 3.42. If n ≥ 4 then W_{n} has a presentation with 4 generators, 11 relations and bit-length O(log n). If n = 4 or 5 then W_{n} also has a presentation with 3 generators and 7 relations.

Proof. We first consider the case n ≥ 5. Let ⟨X | R⟩ be a presentation for A = A_{n}. Let σ = (1, 2, 3) ∈ A, choose a 2-element generating set of H := A_{{1,2}}, and consider the group J with the following presentation: Generators: X, s (where s represents diag(−1, −1, 1, …, 1)). Relations:

(1) R.

(2) s^{2} = 1.
(3) [s, H] = 1.
(4) ss^{σ}s^{σ^{2}} = 1.

There is an obvious surjection π: J → W_{n}. We can view A = ⟨X⟩ ≤ J. By (3), \binom{n}{2} ≥ |s^{A}| ≥ |π(s^{A})| = \binom{n}{2}, so that s^{A} can be identified with the 2-sets in I = {1, …, n}. Thus, there are well-defined elements s_{ij} = s_{ji} ∈ s^{A} for all distinct i, j ∈ I.

By (4), s_{1j}s_{jk}s_{k1} = 1 whenever 1, j, k are distinct. Since all s_{ij} are involutions, it follows that s = s_{12} commutes with all s_{1j}, and hence also with all s_{jk}, so that N := ⟨s^{A}⟩ is elementary abelian. Then J = AN has order |W_{n}|.

Now Theorem ?? yields the stated numbers of generators and relations for n ≥ 4. For n = 4 or 5 we instead use (??). □

4. Rank 1 groups

4.1. Steinberg presentation. Each rank 1 group G we consider has a Borel subgroup B = U⋊⟨h⟩, with U a p-group. There is an involution t (mod Z(G) in the case SL(2, q) with q odd) such that h^{t} = h^{−1} (or h^{−q} in the unitary case). The Steinberg presentation for these groups [?, Sec. 4] consists of

• a presentation for B,

• a presentation for ⟨h, t⟩, and

• |U| − 1 relations of the form

(4.1)  u_{0}^{t} = u_{1}h_{0}tu_{2},

with u_{0}, u_{1}, u_{2} nontrivial elements of U and h_{0} ∈ ⟨h⟩ (one relation for each choice of u_{0}).

4.2. Polynomial notation. Our groups will always come equipped with various elements having names such as u or h. For any polynomial g(x) = ∑_{0}^{e} g_{i}x^{i} ∈ ℤ[x], 0 ≤ g_{i} < p, define powers as follows:

(4.2)  [[u^{g(x)}]]_{h} = (u^{g_{0}})(u^{g_{1}})^{h^{1}} ⋯ (u^{g_{e}})^{h^{e}},

so that

(4.3)  [[u^{g(x)}]]_{h} = u^{g_{0}}h^{−1}u^{g_{1}}h^{−1}u^{g_{2}} ⋯ h^{−1}u^{g_{e}}h^{e}

by “Horner’s Rule” [?, (4.14)] (compare (??)).

As in [?, Sec. 4.3], we need to be careful about rearranging the terms in (??) when not all of the indicated conjugates of u commute.

4.3. SL(2, q). In [?] there is a presentation for PSL(2, q) with at most 13 relations; and it follows readily from that presentation that SL(2, q) has one with at most 17 relations. We now provide presentations having fewer relations, based on the matrices

(4.4)  u = (\begin{matrix}1 & 1 \\ 0 & 1 \end{matrix}), t = (\begin{matrix}0 & 1 \\ −1 & 0 \end{matrix}) and h = (\begin{matrix}ζ^{−1} & 0 \\ 0 & ζ \end{matrix}).

Theorem 4.5. SL(2, q) and PSL(2, q) have presentations with 3 generators, 9 relations and bit-length O(log q). When q is even PSL(2, q) has a presentation with 3 generators, 5 relations and bit-length O(log q).

Proof. By [?, pp. 137-138], if q ≤ 9 then SL(2, q) and PSL(2, q) have presentations with 2 generators and at most 4 relations. Assume that q > 9, let ζ be a generator of 𝔽_{q}^{∗}, and let k, l ∈ ℤ be such that ζ^{2k} = ζ^{2l} + 1 and 𝔽_{q} = 𝔽_{p}[ζ^{2k}] (as in [?, Section 3.5.1]).

Set d = gcd(k, l). Then 𝔽_{q} = 𝔽_{p}[ζ^{2d}].

Let m(x) ∈ 𝔽_{p}[x] be the minimal polynomial of ζ^{2d}. If γ ∈ 𝔽_{q}, let g_{γ}(x) ∈ 𝔽_{p}[x] satisfy g_{γ}(ζ^{2d}) = γ and deg g_{γ} < deg m.

We will show that G = SL(2, q) is isomorphic to the group J having the following presentation. Generators: u, t, h. Relations:

(1) u^{p} = 1.

(2) u^{h^{k}} = uu^{h^{l}} = u^{h^{l}}u.
(3) [[u^{m(x)}]]_{h^{d}} = 1 in the notation of (??).
(4) u^{h} = [[u^{g_{ζ^{2}} (x)}]]_{h^{d}}.
(5) [t^{2}, u] = 1 (or t^{2} = 1 in the case PSL(2, q) with q odd).
(6) h^{t} = h^{−1}.
(7) t = uu^{t}u.
(8) ht = [[u^{g_{ζ^{−1}} (x)}]]_{h^{d}} [[u^{g_{ζ}(x)}]]_{h^{d}}^{t} [[u^{g_{ζ^{−1}} (x)}]]_{h^{d}}.

Matrix calculations using (??) easily show that there is a surjection J → G. By (1), (2) and [?, Lemma 4.1] (compare [?, ?, ?]), U := ⟨u^{⟨h^{k},h^{l}⟩}⟩ is elementary abelian; since d = gcd(k, l) we have U = ⟨u^{⟨h^{d}⟩}⟩. By (1) and (3) we can identify U with the additive group of 𝔽_{q} in such a way that h^{d} acts as multiplication by ζ^{2d}. By (4), h acts on U as a transformation of order (q − 1)/(2, q − 1). (Note that U is defined using h^{k} and h^{l} rather than h so that [?, Lemma 4.1] can be used.)

By (7) and (8), J = ⟨U, U^{t}⟩, and J is perfect since U = [U, h]. Moreover, using (6) we see that z := h^{(q−1)/(2,q−1)} is inverted by t, centralizes U and U^{t}, and hence is an element of Z(J) having order 1 or 2.

Thus, ⟨u, h⟩/⟨z⟩ is isomorphic to a Borel subgroup of PSL(2, q). By (6), ⟨h, t⟩/⟨z⟩ is dihedral of order 2(q − 1)/(2, q − 1).

We already know that ⟨h⟩ acts on the nontrivial elements of U with at most 2 orbits, with orbit representatives u^{1} and [[u^{g_{ζ} (x)}]]_{h^{d}} if q is odd. As in the proof of [?, Sec. 4.4.1], (7) and (8) provide the relations (??) required to let us deduce that J/⟨z⟩ ≅ PSL(2, q).

Now J is a perfect central extension of PSL(2, q), and hence is SL(2, q) or PSL(2, q). Finally, (5) distinguishes between these groups when q is odd. The bit-length of the presentation is clear from (??).

Finally, if q is even there are significant simplifications. We may assume that k = d = 1, so that h^{d} = h acts on U = ⟨u^{⟨h^{k},h^{l}⟩}⟩; the induced automorphism has order q − 1 by (3), and (4) can be deleted. Relation (5) can be deleted since (1) and (7) imply that t^{2} = 1; and (8) is not needed since ⟨h⟩ has only one orbit on the nontrivial elements of U. □

Remark 4.6. Every element of SL(2, q) has bit-length O(log q) in our generators. For, this is true of all elements of U by (??), while SL(2, q) = UU^{t}U.

Remark 4.7. If d = 1 then relation (4) can be removed since then h^{d} = h acts as multiplication by ζ^{2}, by (3).

In [?, Section 3.5.1] it was observed that we can choose k = 1, l = 1 or k = 2. Thus, d ≤ 2 for some choice of k and l. If q is even then d = 1. If q ≡ 3 (mod 4) and k = 2 we can change ζ to −ζ^{2} in order to obtain k = 1 and hence d = 1. We can also prove that there are choices for ζ, k, l that yield d = 1 when q ≡ 5 (mod 8), but we do not know how to obtain such choices in general.

Remark 4.8. Now that we have the notation in (??), we can give more examples along the lines of Examples ??(??) and (??). Let q be a power of an odd prime p such that (3, q − 1) = 1; we may assume that q > 5.

(1′) S_{q+2} has a presentation with 2 generators and 6 relations. For, if ζ is as above, ζ + 1 = ζ^{s}, and g(x) is the minimal polynomial of ζ over 𝔽_{p}, then AGL(1, q) ≅ ⟨u, h | u^{p} = h^{q−1}, u^{h^{s}} = uu^{h} = u^{h}u, [[u^{g(x)}]]_{h} = 1⟩; this is proved as above, using [?, Lemma 4.1]. Then Proposition ?? provides the stated presentation.

(3′) A_{q+2} has a presentation with 2 generators and 6 relations – only 5 relations if q ≡ 3 (mod 4). This time let k, l and m(x) be as in the proof of the preceding theorem, and obtain AGL(1, q)^{(2)} ≅ ⟨u, h | u^{p} = h^{(q−1)/2}, u^{h^{k}} = uu^{h^{l}} = u^{h^{l}}u, [[u^{m(x)}]]_{h} = 1⟩, after which Proposition ?? provides the stated presentation (with ρ = (2, (q − 1)/2)).

4.4. Unitary groups. We will obtain presentations for 3-dimensional unitary groups by taking the presentations in [?, Sec. 4.4.2] and deleting the portions that were needed to produce short presentations. We use matrices of the form

(4.9) u = (\begin{matrix}1 & α & β \\ 0 & 1 & −ᾱ \\ 0 & 0 & 1 \end{matrix}), w = (\begin{matrix}1 & 0 & γ \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}), t = (\begin{matrix}0 & 0 & 1 \\ 0 & −1 & 0 \\ 1 & 0 & 0 \end{matrix}), h = (\begin{matrix}ζ̄^{−1} & 0 & 0 \\ 0 & ζ̄/ζ & 0 \\ 0 & 0 & ζ \end{matrix})

with α, β, γ ∈ 𝔽_{q^{2}} arbitrary such that β + β̄ = −αᾱ ≠ 0 and γ = −γ̄ ≠ 0.

Theorem 4.10. SU(3, q) and PSU(3, q) have presentations with 3 generators, 23 and 24 relations, respectively, and bit-length O(log q).

Proof. Let ζ be a generator of 𝔽_{q^{2}}^{∗}. As in [?, Sec. 4.4.2], we will assume that q ≠ 2, 3, 5 and use elements a = ζ^{k}, b = ζ^{l}, where 1 ≤ k, l < q^{2}, such that

a^{2q−1} + b^{2q−1} = 1 and a^{q+1} + b^{q+1} = 1,
𝔽_{q} = 𝔽_{p}[a^{q+1}], and
𝔽_{q^{2}} = 𝔽_{p}[a^{2q−1}] if q is odd while 𝔽_{q} = 𝔽_{p}[a^{2q−1}] if q is even.

Let d = gcd(k, l).

If γ ∈ 𝔽_{q^{2}} write γ′ := γ^{q+1} and γ′′ := γ^{2q−1}, and also let m_{γ}(x) denote its minimal polynomial over 𝔽_{p}. If δ ∈ 𝔽_{p}[γ], let f_{δ;γ}(x) ∈ 𝔽_{p}[x] with f_{δ;γ}(γ) = δ and deg f_{δ;γ} < deg m_{γ} (compare [?, Sec. 4.4.2]).

The required presentation is as follows: Generators: u, h, t. Relations:

(1) w = w^{h^{k}}w^{h^{l}} = w^{h^{l}}w^{h^{k}}, where w is defined by u = u^{h^{k}}u^{h^{l}}w.

(2) w^{p} = 1.

(3) [[w^{m_{a′} (x)}]]_{h^{d}} = 1.

(4) [[w^{f_{ζ′;a′} (x)}]]_{h^{d}} = w^{h}.

(5) u = u^{h^{l}}u^{h^{k}}w_{1}.

(6) [u, w] = [u^{h^{k}}, w] = 1.

(7) u^{p} = w_{2}.

(8) [[u^{m_{a′′} (x)}]]_{h^{d}} = w_{3}.

(9′) [[u^{f_{ζ′′;a′′} (x)}]]_{h^{d}} = uw_{4} if q is odd.

(9′′) ([[u^{f_{α;a′′} (x)}]]_{h^{d}})^{h}[[u^{f_{β;a′′} (x)}]]_{h^{d}} = u^{h^{2}}w_{5} if q is even and ζ′′ satisfies ζ′′^{2} =

αζ′′ + β for α, β ∈ 𝔽_{q}.

(10) [u, u^{h}] = w_{6} and [u^{h^{k}}, u^{h}] = w_{7} if q is even.

(11) t^{2} = 1.

(12) h^{t} = h^{−q}.

(13) u_{i}^{t} = u_{i1}h_{i}tu_{i2} for 1 ≤ i ≤ 7, relations due to Hulpke and Seress [?].

(14) 1 = v_{11}v_{12}^{t}v_{13}t and h = v_{21}v_{22}^{t}v_{23}t.

Here, the elements w_{i} are specific words in of w^{⟨h^{d}⟩}, the elements u_{ij}, v_{ij} are specific words in u^{⟨h^{d}⟩}, and the elements h_{i} are specific powers of h; all depend on the initial choice of u and ζ.

Note that ⟨w^{⟨h^{d}⟩}⟩ is defined using h^{d} rather than h so that [?, Sec. 4.1] can be used together with (1) and (5). See [?, Sec. 4.4.2] for a proof that this is, indeed, a presentation of SU(3, q). As in [?, Sec. 4.4.2], one further relation of bit-length O(log q) produces a presentation for PSU(3, q). □

Remark 4.11. Let U := ⟨u^{⟨h^{d}⟩}⟩. By applying (??) to both Z(U) = ⟨w^{⟨h^{d}⟩}⟩ and U/Z(U), we find that all elements of U have bit-length O(log q), and hence the same holds for SU(3, q) = UU^{t}UU^{t}U.

4.5. Suzuki groups. The short presentation in [?, Section 4.4.3] uses 7 generators and 43 relations for Sz(q). This can be used for ^{2}F_{4}(q) in Section ??. Nevertheless, we note that there is an easy modification similar to what occurred for SL(2, q) and SU(3, q): three generators are powers of a fourth, allowing us to decrease to 4 generators and 31 relations.

5. SL(3, q)

The groups SL(3, q) will reappear more often in the rest of the proof than any other rank 2 groups: we will use SL(3, q) to obtain first all higher-dimensional groups SL(n, q), and then all higher-dimensional classical groups. Therefore we will be more explicit with these groups than the other rank 2 groups (cf. Section ??).

Theorem 5.1. SL(3, q) has a presentation with 4 generators, 14 relations and bitlength O(log q).

Proof. When q ≤ 9 there are presentations with 2 generators and at most 10 relations [?, ?]. (These cases also can be handled directly by a slight variation on the following approach; compare the end of Section ??.) Hence, we will assume that q > 9.

Let SL(2, q) ≅ L = ⟨X | R⟩, with X = {u, t, h} and ⟨ζ⟩ = 𝔽_{q}^{∗} as in the proof of Theorem ??. We view the elements of SL(3, q) as matrices, with L consisting of the matrices ( \begin{matrix}∗ & 0 \\ 0 & 1 \end{matrix} ).

We will show that G = SL(3, q) is isomorphic to the group J having the following presentation.

Generators: X and c (corresponding to the permutation matrix ( \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ) acting as (3, 2, 1)). Relations:

(1) R.

(2) c^{t} = t^{2}c^{2}.
(3) hh^{c}h^{c^{2}} = 1.

(4) u^{h^{c}} = u^{diag(1,ζ^{−1})}, written as a word in X. (The matrix diag(1, ζ^{−1}) is not in L if q is odd, but it can be viewed as inducing an automorphism of L.)

(5) [u^{c}, u] = (u^{t})^{c^{2}}.
(6) [u^{c}, u^{t}] = 1.

Matrix calculations easily show that there is a surjection J → G. There is a subgroup of J we identify with L = ⟨X⟩. We separate the argument into four steps.

1. Computations in ⟨t, c⟩. The relations t^{4} = 1 and (2) imply that

(5.2)  tct = c^{2}, t^{−1}c^{2}t^{−1} = c, t^{−1}c^{3}t = t^{−1}c^{2}t^{−1}tct = cc^{2},

and hence

(5.3)  t^{c} = c^{−1}tctt^{−1} = c^{−1}c^{2}t^{−1} = ct^{−1}, t^{c^{2}} = (ct^{−1})^{c} = t^{−1}c.

It follows that

(5.4) t^{2}(t^{2})^{c^{2}}(t^{2})^{c} = t^{2} · t^{−1}ct^{−1}c · ct^{−1}ct^{−1} = tc(t^{−1}c^{2}t^{−1})ct^{−1} = tccct^{−1} = c^{3}.

2. The action of h, h^{c}, h^{c^{2}}, c^{3} on L. By (??) and (3), (h^{c})^{t} = h^{t^{−1}c^{2}} = (h^{−1})^{c^{2}} = hh^{c}. Consequently, conjugating both sides of (4) by t gives

(u^{h^{c}})^{t}= (u^{t})^{h^{ct}} = (u^{t})^{hh^{c}} = (u^{th})^{h^{c}}
(u^{diag(1,ζ^{−1})})^{t}= (u^{t})^{diag(1,ζ^{−1})^{t}}= (u^{t})^{diag(ζ^{−1},1)} = (u^{t})^{h diag(1,ζ^{−1})} = (u^{th})^{diag(1,ζ^{−1})}.

(Recall that h = diag(ζ^{−1}, ζ) in Section ??.) Thus, by (4), h^{c} acts on L = ⟨u, u^{th}⟩ as conjugation by diag(1, ζ^{−1}). We know how h acts on L since h ∈ L. Now (3) implies that h^{c^{2}} acts on L as conjugation by diag(ζ^{−1}, 1).

If q is odd then t^{2} = h^{(q−1)/2} is in Z(L). It follows that t^{2}, (t^{2})^{c} = (h^{c})^{(q−1)/2} and (t^{2})^{c^{2}} = (h^{c^{2}})^{(q−1)/2} act on L as they should: as conjugation by 1, diag(1, −1) and diag(1, −1), respectively. Now (??) implies that c^{3} = t^{2}(t^{2})^{c^{2}}(t^{2})^{c} acts trivially on L = ⟨X⟩ and hence on J = ⟨X, c⟩. This also holds trivially if q is even.

3. The elements e_{ij}(λ). For all integers m and all λ ∈ 𝔽_{q}, write

\begin{matrix}e_{12}(ζ^{m}) := u^{(h^{m})^{c}}, e_{12}(0) := 1 & e_{21}(λ) := e_{12}(−λ)^{t} \\ e_{23}(λ) := e_{12}(λ)^{c} & e_{32}(λ) := e_{21}(λ)^{c} \\ e_{31}(λ) := e_{12}(λ)^{c^{2}} & e_{13}(λ) := e_{21}(λ)^{c^{2}}. \end{matrix}

Then e_{12}(1) = u, e_{23}(1) = u^{c}, and e_{12}(𝔽_{q}) is an elementary abelian subgroup of L by (4). Then we also have e_{21}(𝔽_{q}) < L. By (??), c = tt^{c} ∈ ⟨X ∪ X^{c}⟩, so that J is generated by the elements e_{ij}(λ).

Clearly, ⟨c⟩ acts on the set of subgroups e_{ij}(𝔽_{q}); in fact ⟨t, c⟩ acts as the symmetric group S_{3} on subscripts (this is the Weyl group of G). For example, by (??), e_{23}(𝔽_{q})^{t} = e_{12}(𝔽_{q})^{ct} = e_{12}(𝔽_{q})^{t^{−1}c^{2}} = e_{13}(𝔽_{q}); and (as we have seen) t^{2} acts correctly on L^{c^{−1}} = L^{c^{2}} and hence also on e_{12}(𝔽_{q})^{c^{2}} = e_{31}(𝔽_{q}). Similarly, t acts correctly on each e_{ij}(𝔽_{q}).

4. Verification of the Steinberg relations (see [?, Section 5.1 or 5.2]). The relations

e_{ij}(λ)e_{ij}(μ) = e_{ij}(λ + μ)

follow from the corresponding relation in L (with {i, j} = {1, 2}) by conjugating with t and c. We will deduce the remaining relations from (5) and (6) by conjugating with t, c, h, h^{c} and h^{c^{2}}; we have seen that these act on the set of subgroups e_{ij}(𝔽_{q}) as they do in G.

We have [e_{23}(1), e_{21}(1)] = [u^{c}, u^{t}] = 1 by (6). Conjugating by h^{x}(h^{c})^{y} we obtain

[e_{23}(ζ^{2y−x}), e_{21}(ζ^{−2x+y})] = 1.

This does not cover all relations of the form [e_{23}(λ), e_{21}(μ)] = 1 since det( \begin{matrix}−1 & 2 \\ −2 & 1 \end{matrix} ) = 3, but this does imply that

[e_{23}(1), e_{21}(μ^{3})] = 1 for all μ ∈ 𝔽_{q}.

The additive subgroup of 𝔽_{q} generated by the cubes in 𝔽_{q}^{∗} is closed under multiplication, and so is a subfield of size ≥ 1 + (q − 1)/3 and hence is all of 𝔽_{q} since q ≠ 4. It follows that

[e_{23}(1), e_{21}(μ)] = 1 for all μ ∈ 𝔽_{q}.

Conjugating this by all h^{x} yields all relations of the form

[e_{23}(λ), e_{21}(μ)] = 1 for all λ, μ ∈ 𝔽_{q}.

Conjugating by ⟨t, c⟩, we obtain

(5.5) [e_{kl}(λ), e_{km}(μ)] = [e_{km}(λ), e_{lm}(μ)] = 1 for all distinct k, l, m and all λ, μ.

Similarly, (5) implies that

[e_{23}(1), e_{12}(1)] = [u^{c}, u] = (u^{t})^{c^{2}} = e_{13}(−1).

Since t acts correctly on each e_{ij}(𝔽_{q}), conjugating by t gives [e_{13}(−1), e_{21}(1)] = e_{23}(1). Conjugating by h^{x}(h^{c})^{y} we obtain

[e_{23}(ζ^{2y−x}), e_{12}(ζ^{2x−y})] = e_{13}(−ζ^{x+y}), [e_{13}(ζ^{x+y}), e_{32}(ζ^{x−2y})] = e_{12}(ζ^{2x−y}).

Once again these do not cover all relations of the form

[e_{23}(λ), e_{12}(μ)] = e_{13}(−λμ) and [e_{13}(λ), e_{32}(μ)] = e_{12}(λμ).

However, using the standard identity [x, ab] = [x, b][x, a]^{b}, together with (??) and the fact that the cubes in 𝔽_{q}^{∗} generate 𝔽_{q} under addition, we deduce all such relations.

Conjugating by ⟨t, c⟩ yields all remaining Steinberg relations. Then J is a homomorphic image of G = SL(3, q), and hence J ≅ G. By Theorem ?? and Remark ??, our presentation has the required bit-length; note that c is the product of an element of L and an element of L^{c}. The presentation uses |R| + 5 = 14 relations. □

In order to obtain a presentation for PSL(3, q) when m := (q −1)/3 is an integer, add the relation h^{m}(h^{2m})^{c} = 1.

Note that the computations in the above proof would be considerably simpler if we added the relation c^{3} = 1; this is a relation we will have available in the proof of Theorem ??.

Remark 5.6. Using Remark ?? we see that each element of SL(3, q) has bit-length O(log q) in our generators.

Remark 5.7. For future use we will need to know that SL(3, q) = ⟨a, a^{(1,2,3)}⟩ for some a ∈ L of order q + 1. For, ⟨a, a^{(1,2,3)}⟩ is an irreducible subgroup of SL(3, q). Using the order of a and the list of possible subgroups [?, ?] proves the claim.

6. SL(n, q)

We now turn to the general case of Theorem B for the groups PSL(n, q), using a variation on the approach in Section ??.

Theorem 6.1. Let n ≥ 4.

(a) SL(n, q) has a presentation with 7 generators, 25 relations and bit-length O(log n + log q).

(b) PSL(n, q) has a presentation with 7 generators, 26 relations and bit-length O(log n + log q).

(c) SL(4, q) has a presentation with 6 generators, 21 relations and bit-length O(log q).

(d) SL(5, q) has a presentation with 6 generators, 22 relations and bit-length O(log q).

Proof. We use two presentations:

• The presentation ⟨X | R⟩ for F = SL(3, q) in Theorem ??. We view F as the group of matrices ( \begin{matrix}∗ & 0 \\ 0 & I \end{matrix} ) in G = SL(n, q) and only write the upper left 3 × 3 block.

• The presentation ⟨Y | S⟩ for T = A_{n} in Theorem ??, where T acts on {1, …, n} (with X and Y disjoint). We view T as permutation matrices.

We will also use the subgroup L = SL(2, q) of F consisting of matrices in the upper left 2 × 2 block. We use the following elements:

c = (\begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}), f = (\begin{matrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & −1 \end{matrix}) ∈ F,

a ∈ L such that ⟨a, a^{f}⟩ = L, (1, 2, 3), (1, 3)(2, 4) ∈ T, and σ and τ = (1, 2)(3, 4) in T interchanging 1 and 2 and generating the setstabilizer T_{{1,2}} of {1, 2} in T.

Bit-length: c, f and a have bit-length O(log q) using Remark ??. We may assume that σ is a cycle of length n − 2 or n − 3 on {3, …, n}; both σ and τ can be viewed as words in Y of bit-length O(log n) (by Remark ??).

We will show that G is isomorphic to the group J having the following presentation. Generators: X, Y. Relations:

(1) R.

(2) S.
(3) c = (1, 2, 3).
(4) a^{σ} = a^{f}.
(5) a^{τ} = a^{f}.
(6) (a^{f})^{σ} = a.
(7) [a, a^{(1,3)(2,4)}] = 1.
(8) [a^{f}, a^{(1,3)(2,4)}] = 1 (needed only when n is 4 or 5).

As usual, there is a surjection π: J → G, and J has subgroups we will identify with F = ⟨X⟩ and T = ⟨Y ⟩. Since τ has order 2, (5) implies that (a^{f})^{τ} = a. Hence, by (4)–(6), ⟨σ, τ⟩ normalizes L, inducing the same automorphism group as ⟨f⟩ on L. In particular, elements of ⟨σ, τ⟩ that fix 1 and 2 must centralize L, while elements interchanging 1 and 2 act as f.

It follows that |L^{T} | ≤ \binom{n}{2}; as usual, we use π to obtain equality. Then L^{T} can be identified with the set of all 2-sets of {1, …, n}. Its subset L^{⟨c⟩} consists of 3 subgroups corresponding to the 2-sets in {1, 2, 3}. Consequently, any two distinct members of L^{T} can be conjugated by a single element of T to one of the pairs L, L^{(1,2,3)} or L, L^{(1,3)(2,4)}. Here ⟨L, L^{(1,2,3)}⟩ = ⟨L, L^{c}⟩ = F by (3).

We will use (7)–(8) to show that [L, L^{(1,3)(2,4)}] = 1. By our comment about elements of ⟨σ, τ⟩, we have a^{(1,2)(5,6)} = a^{f} and a^{(3,4)(5,6)} = a. Then

\begin{aligned}1 & = [a, a^{(1,3)(2,4)}]^{(1,2)(5,6)} = [a^{f}, (a^{(3,4)(5,6)})^{(1,3)(2,4)}] = [a^{f}, a^{(1,3)(2,4)}] \\ 1 & = [a, a^{(1,3)(2,4)}]^{(1,2)(3,4)} = [a^{f}, (a^{f})^{(1,3)(2,4)}] \\ 1 & = [a^{f}, a^{(1,3)(2,4)}]^{(1,2)(3,4)} = [a, (a^{f})^{(1,3)(2,4)}], \end{aligned} ; (6.2)

where the first equations explain the comment in (8).

Thus, any two distinct members of L^{T} either generate a conjugate of F = SL(3, q) or commute. Consequently, N := ⟨L^{T} ⟩ ≅ G (see [?, Sections 5.1 or 5.2] for the Steinberg presentation). Moreover, N ⊴ J, and J/N is a homomorphic image of ⟨Y ⟩ ≅ A_{n} in which c is sent to 1. Thus, J/N = 1.

The bit-length follows easily from those of ⟨X | R⟩ and ⟨Y | S⟩.

We still need to count the number of relations. If n ≥ 6 then we have used 14+7+5 relations by Theorems ?? and ??. However, we can remove one generator and one relation as follows. In Theorem ?? we used a generator “c” (corresponding to the permutation matrix acting as (3, 2, 1)). Hence we replace that element c by a word in Y representing (1, 2, 3) ∈ T in the relations appearing in that theorem. Then (3) is implied by the new presentation ⟨X | R⟩.

If n = 4 or 5 we use the presentation (??) with only 2 generators and 3 relations. Then the preceding presentation requires only 14 + 4 + 6 − 1 relations. Moreover, when n = 4 we can delete σ entirely, saving two further relations (4) and (6); and when n = 5 we can choose σ of order 2 and delete (6).

Finally, we need to add one further relation in order to obtain PSL(n, q). Let h_{i,j} be the matrix with ζ and ζ^{−1} in positions i and j, and 1 elsewhere. Let m = (q − 1)/(d, q − 1). If n is odd, use Remark ?? to obtain the (n − 2)-cycle (2, …, n − 1), and then the additional relation h_{1,n}^{m}(h_{2,n}^{m}(2, …, n − 1))^{n−2} = 1 produces PSL(n, q) with the required bit-length. The case n even is similar. □

7. Remaining rank 2 groups

In this section we will provide presentations required in Theorem ?? for some of the rank 2 groups of Lie type. Since PΩ^{−}(6, q) ≅ PSU(4, q), and we will handle all unitary groups in a different manner in Theorem ??, we only need to consider the groups Sp(4, q), G_{2}(q), ^{3}D_{4}(q) and ^{2}F_{4}(q). Note that the last three groups do not appear inductively as Levi factors of any higher rank groups of Lie type.

7.1. Sp(4, q), G_{2}(q) and ^{3}D_{4}(q). Here the Weyl group is dihedral of order 2m = 8 or 12.

Theorem 7.1. (a) Sp(4, q) has a presentation with 6 generators, 35 relations and

bit-length O(log q).

(b) PSp(4, q) ≅ Ω(5, q) has a presentation with 6 generators, 36 relations and bit-length O(log q).

(c) G_{2}(q) and ^{3}D_{4}(q) have presentations with 6 generators, 40 relations and bitlength O(log q).

Proof. (a) The root system Φ of G = Sp(4, q) has 8 roots, half of them long and half short. Let Π = {α_{1}, α_{2}} be a set of fundamental roots with α_{1} long; there are corresponding rank 1 groups L_{α_{i}} ≅ SL(2, q).

We assume that q > 9 until the end of this proof, and use the presentation ⟨X_{i} | R_{i}⟩ of L_{α_{i}} in Theorem ??, with

(7.2)  X_{i} = {u_{α_{i}}, r_{i}, h_{i}}, i = 1, 2

(here we are using r_{i} instead of t_{i} in order to approximate standard Lie notation; we assume that X_{1} and X_{2} are disjoint). The action of h_{i} on u_{α_{i}} is given in R_{i}, and U_{α_{i}} := ⟨u_{α_{i}}^{⟨h_{i}⟩}⟩ has order q. Let U_{α_{i}}^{♯} := U_{α_{i}}\ {1} . There are (2, q − 1) orbits of ⟨h_{i}⟩ on U_{α_{i}}^{♯}, with orbit representatives u_{α_{i},1} := u_{α_{i}} and u_{α_{i},2} (where u_{α_{i},2} := u_{α_{i}} if q is even). If q is odd then ⟨h_{1}, h_{2}⟩ has 2 orbits on both U_{α_{1}}^{♯} × U_{α_{2}}^{♯} and U_{α_{1}+α_{2}}^{♯} × U_{α_{2}}^{♯}, with respective orbit representatives (u_{α_{1},a}, u_{α_{2}}), a = 1, 2, and (u_{α_{1}+α_{2},a}, u_{α_{2},a}), a = 1, 2 (see [?, Lemma 5.3]).

The root groups U_{α}, α ∈ Φ, will be built into our presentation.

We will show that G is isomorphic to the group J having the following presentation. Generators: X_{1} ∪ X_{2}. Relations:

(1) R_{1} ∪ R_{2}.

(2) h_{1}^{r_{2}}, h_{2}^{r_{1}} and w^{4} are explicit words in {h_{1}, h_{2}}, where w := r_{1}r_{2}.
(3) (u_{α_{i}})^{h_{j}^{w^{n}}} is an explicit word in u_{α_{i}}^{⟨h_{i}⟩} for i ≠ j and 0 ≤ n < 4.

Notation: U_{α_{i}} := ⟨u_{α_{i}}^{⟨h_{i}⟩}⟩ for i = 1, 2, H := ⟨h_{1}, h_{2}⟩, N := ⟨r_{1}, r_{2}, H⟩, and W := N/H (which is isomorphic to D_{8}). Label the subgroups (U_{α_{i}})^{w^{n}}, 0 ≤ n < 4, in the usual way as

U_{α}, α ∈ Φ := {±α_{1}, ±α_{1}, ±(α_{1} + a_{2}), ±(α_{1} + 2a_{2})}

[?, p. 46], so that Φ = α_{1}^{{w^{n}|0≤n<4}} ∪ α_{2}^{{w^{n}|0≤n<4}}.

For i = 1, 2 let u_{α_{i},1} be another name for u_{α_{i}}, and let u_{α_{i},2} stand for an explicit word in u_{α_{i}}^{⟨h_{i}⟩} corresponding to an element of G described above. If α = α_{i}^{w^{n}} for (unique) i ∈ {1, 2} and 0 ≤ n < 4, write u_{α,a} := (u_{α_{i},a})^{w^{n}} for a = 1, 2.

(4) (a) [u_{α_{1}}, u_{α_{1}+2α_{2}}] = [u_{α_{1}}, u_{α_{1}+α_{2}}] = 1.

(b) [u_{α_{1},a}, u_{α_{2}}] is an explicit word in u_{α_{1}}^{⟨h_{1}⟩w^{3}} ∪ u_{α_{2}}^{⟨h_{2}⟩w^{3}} ⊂ U_{α_{1}+2α_{2}} ∪

U_{α_{1}+α_{2}} for a = 1, 2.

(c) [u_{α_{2},a}, u_{α_{1}+α_{2},a}] is an explicit word in u_{α_{1}}^{⟨h_{1}⟩w^{3}} ⊂ U_{α_{1}+2α_{2}} for a =

1, 2.

First of all, the explicit words mentioned in these relations are obtained in G, and have bit-length O(log q) in the generators by Remark ??. It follows that this presentation has bit-length O(log q), and that there is a surjection π: J → G. Moreover, this presentation has |X_{1}| + |X_{2}| = 6 generators and at most |R_{1}| + |R_{2}| + 3 + 8 + 6 = 35 relations.

By (1) there is a subgroup L_{α_{i}} ≅ SL(2, q) of J we can identify with ⟨X_{i}⟩.

By (2), H ⊴ N and W ≅ D_{8}, as stated in (3).

Using L_{α_{i}} we see that U_{α_{i}}^{r_{i}} = U_{−α_{i}}. By (3), H normalizes each subgroup U_{α} = ⟨u_{α}^{H}⟩. It follows that W acts on Φ in the natural manner: there are 8 root groups U_{α}, α ∈ Φ, labeled as in (3) and permuted by N.

Fix roots α and β ≠ ±α. Then H acts by conjugation on the set of all Chevalley commutator relations [?, p. 47], which we write as

(7.3)  [y_{α}, y_{β}] = ∏_{γ} v_{γ} with y_{α} ∈ U_{α}^{♯}, y_{β} ∈ U_{β}^{♯}, v_{γ} ∈ U_{γ},

where γ runs through all positive integral combinations of α and β. Clearly (4) provides us with instances of (??) corresponding to each of the four W -orbits on pairs {α, β} , β ≠ ±α.

If [y_{α}, y_{β}] = 1 with {y_{α}, y_{β}} = {u_{α_{1}}, u_{α_{1}+2α_{2}}} or {u_{α_{1}}, u_{α_{1}+α_{2}}} in (4a), then [U_{α}, U_{β}] = [⟨y_{α}^{H}⟩, ⟨y_{β}^{H}⟩] = 1. (For, the Chevalley commutator relations for G [?, p. 47] show that the corresponding fundamental subgroups of G commute. In particular, already in π(J) = G suitable elements of h_{1}^{N} ∪ h_{2}^{N} act independently on U_{α} and U_{β}.)

If [y_{α}, y_{β}] ≠ 1 for the pairs {y_{α}, y_{β}} in (4b,c) then, by [?, Lemma 5.3], we obtain all relations (??) by conjugating the ones in (4b,c) by elements of H.

At this point we have verified the Steinberg-Curtis-Tits relations mentioned in Section ??. Thus, J is a homomorphic image of the universal group of Lie type for G, and hence is G [?, pp. 312-313].

(b) When q is odd, we just need one further relation to kill the center of Sp(4, q).

(c) These groups are handled in a manner similar to what was done in (a), replacing the number 4 by 6 at suitable places in order to obtain the Weyl group D_{12}. We sketch this very briefly since these groups do not arise in higher rank settings.

Once again we have fundamental subgroups L_{α_{1}} ≅ SL(2, q) and L_{α_{2}} ≅ SL(2, q) or SL(2, q^{3}), where the latter occurs for short α_{2} in ^{3}D_{4}(q). We use versions of (1)–(4), labeling the roots as in [?, p. 46]. However, in order to avoid any use of (3, q − 1) elements u_{α_{1},a} we proceed as follows in (4). The long root groups U_{α} of G generate a subgroup SL(3, q). Relations (5) and (6) from our presentation in Theorem ??, with c := w^{2}, are instances of (??); hence these are the only relations of this sort needed for long α, β. By [?, Lemma 5.3], this is the only situation where we might have needed to use several elements u_{α_{1},a}.

This time W = N/H has seven orbits on pairs {α, β}, β ≠ ±α. Counting, we see that there are only 40 relations. Note the significant savings due to not needing more than one element of any root group U_{α}.

This proves the theorem when q > 9.

It remains to make some straightforward remarks about the remaining cases. For each of these, if L_{α_{i}} is a central extension of PSL(2, q) then it has a presentation ⟨Y_{i} | S_{i}⟩ using 2 generators and at most 3 relations [?, ?, ?]. We do not have to be concerned about lengths of words in these bounded situations, so we can assume that each of the elements u_{α_{i}}, u_{α_{i},a}, r_{i}, h_{i} is replaced by a word in Y_{i}. Once this has been done, we can again write the relations (1)–(4) in our new generating set, and then our previous argument goes through without difficulty. □

7.2. ^{2}F_{4}(q). Here q = 2^{2e+1} > 2. There is no root system in the classical sense, but there are 16 “root groups” U_{i}, 1 ≤ i ≤ 16. There are rank 1 groups L_{1} = Sz(q) and L_{2} = SL(2, q), and we use the presentation ⟨X_{i} | R_{i}⟩ for L_{i} in Section ?? or Theorem ??. If i = 2 then (??) holds, and U_{2} := ⟨u_{2}^{⟨h_{2}⟩}⟩ is elementary abelian of order q. On the other hand, X_{1} has size 7 and contains elements u_{1}, r_{1}, h_{1} behaving essentially as before, except that this time U_{1} = ⟨u_{1}^{⟨h_{1}⟩}⟩ is nonabelian of order q^{2} with Z(U_{1}) = Φ(U_{1}) = ⟨(u_{1}^{2})^{⟨h_{1}⟩}⟩ (where Φ(U_{1}) denotes the Frattini subgroup of U_{1}).

We use the following presentation. Generators: X_{1} ∪ X_{2}. Relations:

(1) R_{1} ∪ R_{2}.

(2) w^{8} = 1, where w := r_{1}r_{2}.
(3) h_{1}^{r_{2}} and h_{2}^{r_{1}} are explicit words in {h_{1}, h_{2}}.

(4) (u_{α_{i}})^{h_{j}^{w^{n}}} is an explicit word in u_{α_{i}}^{⟨h_{i}⟩} for {i, j} = {1, 2} and 0 ≤ n < 8.

Notation: Let u_{i+n} := (u_{i})^{w^{n}} for i = 1, 2 and 1 ≤ n < 8.

(5) [u_{i}, u_{j}] is an explicit product of words in u_{k}^{⟨h_{1},h_{2}⟩}, i < k < j, for the pairs

(i, j) with i = 1 and 2 ≤ j ≤ 8, or i = 2 and j = 4, 6 or 8.

In the presented group J there are again subgroups L_{i} we can identify with ⟨X_{i}⟩, i = 1, 2. Also, ⟨r_{1}, r_{2}⟩ is dihedral of order 16 by (2), and normalizes H := ⟨h_{1}, h_{2}⟩ by (3). It then follows from (4) that H normalizes each subgroup U_{i+n} := (U_{i})^{w^{n}} for i = 1, 2 and 1 ≤ n < 8.

As in the case of the other rank 2 groups, the known actions of h_{1}^{w^{n}} and h_{2}^{w^{n}} in (4) allow us to deduce from (5) an additional relation analogous to (??) for each pair of nontrivial cosets of the form y_{i}Φ(U_{i}), y_{j}Φ(U_{j}), for i, j as in (5) and y_{i} ∈ U_{i}, y_{j} ∈ U_{j} (compare [?, Lemma 5.3]). By using the elementary identity [x, uv] = [x, v][x, u]^{v}, we see that these conjugates of the relations (5) imply all analogues of (??) for these i, j. Finally, we obtain further relations analogous to (??) by conjugating by elements of ⟨w⟩. It is now easy to see that we have all relations required for a presentation of G ([?, p. 412], [?, p. 105] and [?, p. 48] give the 10 formulas implicitly contained in (5)).

There are 16 relations (4) and 10 relations (5), for a total of 7 + 3 generators and 43 + 9 + 1 + 2 + 16 + 10 = 81 relations. As noted in Section ??, these numbers can easily be decreased to 4 + 3 and 31 + 9 + 1 + 2 + 16 + 10.

8. Unitary groups

Since the commutator relations for the odd-dimensional unitary groups are especially complicated (see, for example, [?, Theorem 2.4.5(c)]), we will deal with these groups separately. In fact, when combined with Theorems ?? and ??, recent presentations in [?] allow us to use surprisingly few generators and relations (cf. Theorem ??).

8.1. Phan style presentations. We will outline the presentation of G = SU(n, q), n ≥ 4, in [?], based on one in [?]. In [?], subgroups U_{1}, U_{2} ≅ SU(2, q) of SU(3, q) are called a standard pair if U_{1} and U_{2} are the respective stabilizers in SU(3, q) of perpendicular nonsingular vectors.

Using an orthonormal basis, it is easy to see that G has subgroups U_{i} ≅ SU(2, q), 1 ≤ i ≤ n − 1, and U_{i,j}, 1 ≤ i < j ≤ n − 1, satisfying the following conditions. (P1) If |j − i| > 1 then U_{i,j} is a central product of U_{i} and U_{j}. (P2) For 1 ≤ i < n − 1, U_{i,i+1} ≅ SU(3, q), and U_{i}, U_{i+1} is a standard pair in U_{i,i+1}. (P3) G = ⟨U_{i,j} | 1 ≤ i < j ≤ n − 1⟩.

The presentation we will use is the following analogue of the Curtis-Steinberg-Tits presentation mentioned in Section ??.

Theorem 8.1. [?, ?] If (P1)–(P3) hold in a group G, then G is isomorphic to a factor group of SU(n, q) in each of the following situations.

(a) q > 3 and n ≥ 4.

(b) q = 2 or 3, n ≥ 5 and the following hold: (1) ⟨U_{i,i+1}, U_{i+1,i+2}⟩ ≅ SU(4, q) whenever 1 ≤ i ≤ n − 3; and

(2) if q = 2 then

(i) [U_{i}, U_{j,j+1}] = 1 whenever 1 ≤ i ≤ n − 1, 1 ≤ j ≤ n − 2 and

i ≠ j − 1, j, j + 1, j + 2; and

(ii) [U_{i,i+1}, U_{j,j+1}] = 1 whenever 1 ≤ i ≤ n − 2, 1 ≤ j ≤ n − 2 and

i ≠ j − 2, j − 1, j, j + 1, j + 2.

In [?], it is remarked that (P1)–(P3) do not provide a presentation of SU(n, 2). It is also noted that a standard pair in SU(3, 2) does not generate that group.

8.2. Some specific presentations. When q = 2 or 3 we need to deal with some small groups. The computer package MAGMA [?] contains the following presentation:

\begin{aligned}SU(4, 3) = ⟨x, y | x^{3} & = y^{8} = [y^{4}, x] = (xy)^{7} = [x, (xy^{−1})^{7}] \\ & = [y^{2}, xy^{2}xy^{2}xy^{2}] = xx^{xyx^{−1}y^{−1}xy} = (xyx^{−1}y^{2})^{8}⟩ = 1⟩. \end{aligned}

We also need other small cases [?]:

SU(6, 2) = ⟨a, b | a^{2} = b^{7} = (ab^{3})^{11} = [a, b]^{2}

= [a, b^{2}]^{3} = [a, b^{3}]^{3} = (ab)^{33} = (abab^{2}ab^{3}ab^{−3})^{2} = 1⟩.

SU(5, 2) = ⟨a, b | a^{2} = b^{5} = (ab)^{11} = [a, b]^{3} = [a, b^{2}]^{3} = [a, bab]^{3} = [a, bab^{2}]^{3} = 1⟩.
SU(4, 2) = ⟨a, b | a^{2} = b^{5} = (ab)^{9} = [a, b]^{3} = [a, bab]^{2} = 1⟩.

The last of these is [?, (10.8)].

8.3. Presentations of unitary groups. In this section we will prove the following

Theorem 8.2. Let n ≥ 4.

(a) SU(n, q) has a presentation with 6 generators, 39 relations and bit-length O(log n + log q).

(b) PSU(n, q) has a presentation with 6 generators, 40 relations and bit-length O(log n + log q).

(c) SU(4, q) and SU(5, q) have presentations with 6 generators, 35 relations and bit-length O(log q).

(d) PSU(4, q) and Ω^{−}(6, q) have presentations with 6 generators, 36 relations and bit-length O(log q).

Proof. Let • F := SU(m, q), with m = 3, 4 or 6 and m ≤ n, and

• A := A_{n}, acting on {1, …, n}. We view both of these groups as lying in G = SU(n, q), using an orthonormal basis of the underlying vector space: F consists of the matrices ( \begin{matrix}∗ & 0 \\ 0 & I \end{matrix} ) with an m × m block in the upper left corner, and A consists of permutation matrices.

For each m we assume that we have the following additional information:

• The presentation ⟨X | R⟩ of F in Theorem ??, except in the case of the pairs (m, q) = (4, 2), (4, 3) or (6, 2), in which case ⟨X | R⟩ is given in Section ??.

• The presentation ⟨Y | S⟩ of A in Theorem ?? (where X and Y are disjoint).

• Two generators g, h for W := SU(2, q) < F, where W consists of the matrices ( \begin{matrix}∗ & 0 \\ 0 & I \end{matrix} ) with a 2 × 2 block in the upper left corner, and where g and h can be viewed as words in X of bit-length O(log q) (using Remark ??).

• A word in X of bit-length O(log q) representing the element c_{(1,2,3)} ∈ F that acts as the 3-cycle (1, 2, 3) on the orthonormal basis (cf. Remark ??).

• A word in Y of bit-length O(log n) representing (1, 2, 3) (cf. Remark ??).

• Permutations σ = (1, 2)(3, 4) and τ in A that interchange 1 and 2 and generate the set-stabilizer S_{n−2} of {1, 2} in A, where σ and τ can be viewed as words in Y of bit-length O(log n) (using Remark ??).

Parts (b) and (d) of the theorem are handled at the end of the proof.

Case q > 3: Here we let m = 3. We will show that G is isomorphic to the group J having the following presentation. In view of the preceding remarks, this presentation has the desired bit-length.

Generators: X ∪ Y.

Relations:

(1) R ∪ S.

(2) c_{(1,2,3)} = (1, 2, 3).

(3) g^{σ} = g^{τ} = g^{(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})} and h^{σ} = h^{τ} = h^{(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})}. (The matrix ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) is not in W

if q is odd, but can be viewed as inducing an automorphism of W.)

(4) [W, W^{(13)(24)}] = 1.

Since there is a surjection π: J → G, there are subgroups of J we can identify with F = ⟨X⟩ and A = ⟨Y ⟩.

By (3), |W^{A}| ≤ \binom{n}{2}, and using π we see that W^{A} consists of \binom{n}{2} subgroups we will call W_{i,j} = W_{j,i}, 1 ≤ i < j ≤ n, where W_{i,j} ≤ F for 1 ≤ i < j ≤ 3. If i, j, k, l are distinct, then (4) and the 4-transitivity of A imply that [W_{i,j}, W_{k,l}] = 1 and ⟨W_{i,j}, W_{i,k}⟩ ≅ ⟨W_{1,2}, W_{1,3}⟩ = F.

Let U_{i} := W_{i,i+1} and U_{i,j} := ⟨U_{i}, U_{j}⟩. These subgroups satisfy (P1)–(P2) and hence, by Theorem ??, N := ⟨U_{i,j} | 1 ≤ i < j ≤ n − 1⟩ is a homomorphic image of G.

We claim that N ⊴ G. For, W_{1,3} ≤ ⟨W_{1,2}, W_{2,3}⟩. By the 3-transitivity of A, it follows that W_{i,k} ≤ ⟨W_{i,j}, W_{j,k}⟩ for all distinct i, j, k. By induction, if i < j + 1 then

\begin{aligned}W_{i,j} & ≤ ⟨W_{i,j−1}, W_{j−1,j}⟩ \\ & ≤ ⟨W_{i,i+1}, …, W_{j−2,j−1}, W_{j−1,j}⟩ = ⟨U_{i}, …, U_{j−2}, U_{j−1}⟩ ≤ N. \end{aligned}

Thus, N = ⟨F^{A}⟩ ⊴ J. By (2), J/N is a quotient of A_{n} in which (1, 2, 3) is mapped to 1. Thus, J/N = 1.

Total: |X| + |Y | = 3 + 3 generators and |R| + |S| + 9 = 23 + 7 + 9 relations. This proves (a) when q > 3. For (c), we use the presentation (??) with only 2

generators and 3 relations. Hence, the preceding presentation requires only 23+3+9 relations.

Case q = 3: This time we let m = 4 and use the presentation ⟨X | R⟩ for SU(4, 3) given in Section ??. We assume that n ≥ 5, and that we have

• Words in X representing the elements c_{(1,2,3)}, c_{(2,3,4)} ∈ F that act as the indicated permutations on the orthonormal basis.

We will show that G is isomorphic to the group J having the following presentation.

Generators: X ∪ Y.

Relations:

(1′) R ∪ S.

(2′) c_{(1,2,3)} = (1, 2, 3), c_{(2,3,4)} = (2, 3, 4).

(3′) g^{σ} = g^{τ} = g^{(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})} and h^{σ} = h^{τ} = h^{(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})}.

By (2′) and (3′), g^{σ} = g^{τ} ∈ W and h^{σ} = h^{τ} ∈ W. As before, it follows that W^{A} consists of \binom{n}{2} subgroups W_{i,j} = W_{j,i}, 1 ≤ i < j ≤ n, where W_{i,j} ≤ F for 1 ≤ i < j ≤ 4.

The previous relation (4) follows from the corresponding relation in F = SU(4, q). If i, j, k, l are distinct, then (4) and the 4-transitivity of A give [W_{i,j}, W_{k,l}] = 1,

⟨W_{i,j}, W_{i,k}⟩ ≅ ⟨W_{1,2}, W_{1,3}⟩ ≅ SU(3, q) and ⟨W_{i,j}, W_{i,k}, W_{i,l}⟩ ≅ ⟨W_{1,2}, W_{1,3}, W_{1,4}⟩ = F.

Once again, the subgroups U_{i} := W_{i,i+1} and U_{i,j} := ⟨U_{i}, U_{j}⟩ of J satisfy (P1)–(P2). They also behave as in Theorem ??(b1) since ⟨U_{i,i+1}, U_{i+1,i+2}⟩ ≅ ⟨U_{1,2}, U_{2,3}⟩ = F.

Once again, the subgroup N generated by all U_{i,j} is isomorphic to G. As before, N is normal in J = ⟨X, Y ⟩ and hence is J.

Total: |X| + |Y | = 2 + 3 generators and |R| + |S| + 6 = 8 + 7 + 6 relations.

Case q = 2: This time we let m = 6. Using the presentations in Section ?? we may assume that n ≥ 7, and that we have

• Generators g′, h′ for V := SU(3, 2) as words in X;

• Words in X representing elements c_{(1,2,3)}, c_{(2,3,4,5,6)} ∈ F that act as the indicated permutations on the orthonormal basis; and

• Two permutations σ′ = (1, 2)(4, 5) and τ′ that generate the set-stabilizer of {1, 2, 3} in A and can be viewed as words in Y of bit-length O(log n) (cf. Remark ??).

We will show that G is isomorphic to the group J having the following presentation.

Generators: X ∪ Y.

Relations:

(1′′) R ∪ S.

(2′′) c_{(1,2,3)} = (1, 2, 3), c_{(2,3,4,5,6)} = (2, 3, 4, 5, 6).

(3′′) g^{σ} = g^{τ} = g^{(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})} and g^{σ} = h^{τ} = h^{(\begin{matrix}0 & 1 \\ 1 & 0 \end{matrix})}.

(4′′) g′^{τ′} = g′^{c[τ′]} and h′^{τ′} = g′^{c[τ′]}, where c[τ′] denotes the automorphism of V induced by the permutation matrix for the restriction of τ′ to the first 3 coordinates.

As before, it follows from (2′′) and (3′′) that W^{A} consists of \binom{n}{2} subgroups W_{i,j} = W_{j,i}, 1 ≤ i < j ≤ n, where W_{i,j} < F for 1 ≤ i < j ≤ 6. The previous relation (4) follows from the corresponding relation in F = SU(6, 2).

If i, j, k, l are distinct, then W_{i,j} commutes with W_{k,l} by (4) and the 4-transitivity of A.

By (2′′), σ′ ∈ ⟨c_{(1,2,3)}, c_{(2,3,4,5,6)}⟩ < F, so that V^{σ′} = V. As before, (4′′) then implies that V^{A} consists of \binom{n}{3} subgroups V_{i,j,k} for distinct i, j, k ∈ \{1, …, n\}, where V_{i,j,k} ≤ F for 1 ≤ i, j, k ≤ 6 and W_{i,j} ≤ V_{i,j,k}.

In view of the transitivity properties of A, if i, j, k, l, r, s are distinct then ⟨V_{i,j,k}, V_{i,j,l}⟩ ≅ ⟨V_{1,2,3}, V_{1,2,4}⟩ ≅ SU(4, 2) and [V_{i,j,k}, V_{l,r,s}] = 1.

Let U_{i} := W_{i,i+1}, U_{i,i+1} := V_{i,i+1,i+2} and U_{i,j} := ⟨U_{i}, U_{j}⟩ iff |i − j| > 1.

The subgroups U_{i,j} satisfy (P1)–(P2). They also behave as in Theorem ??(b1) since ⟨U_{i,i+1}, U_{i+1,i+2}⟩ ≅ ⟨U_{1,2}, U_{2,3}⟩ = SU(4, 2). The conditions in Theorem ??(b2) also hold since they hold for the subgroups U_{i}, U_{i,i+1}, U_{j,j+1} that lie in F.

Hence, the subgroup N generated by all U_{i,j} is isomorphic to G. As before, N is normal in J = ⟨X, Y ⟩ and hence is J.

Total: |X| + |Y | = 2 + 3 generators and |R| + |S| + 8 = 8 + 7 + 8 relations. This proves (a) and (c) for all q. For (b) and (d) we note that a presentation

of each group in question is obtained as in the proof of Theorem ?? by adding one new relation of bit-length O(log n + log q) to a presentation in (a) or (c). □

9. General case

We now complete the proofs of Theorems ?? and ??.

Theorem 9.1. All finite simple groups of Lie type and rank n ≥ 3 over 𝔽_{q} have presentations with at most 14 generators, 76 relations and bit-length O(log n+log q).

Proof. We use a variation on the methods in [?, Section 6.2]. By Theorems ??, ?? and ??, we may assume that G is neither a special linear nor unitary group.

Until the end of the proof we assume that our simple group G is the simply connected group of the given type. As usual, Π = {α_{1}, …, α_{n}} is the set of fundamental roots of G, and for each i there are root groups U_{±α_{i}}. Case 1: G is a classical group. Number Π as in [?, Section 6.2]: the subsystem {α_{1}, …, α_{n−1}} is of type A_{n−1}, α_{n} is an end node root and is connected to only one root α_{j} in the Dynkin diagram (here j = n−1 except for type D_{n}, when j = n−2). Let

(9.2) G_{1} = ⟨U_{±α_{i}} | 1 ≤ i < n⟩, G_{2} = ⟨U_{±α_{n}}, U_{±α_{j}}⟩, L_{2} = ⟨U_{±α_{n}}⟩, L = ⟨U_{±α_{j}}⟩.

Then G_{1} has type A_{n−1} and G_{2} is a rank 2 classical group.

Let L_{1} be the subgroup of G_{1} generated by the root groups that commute with L_{2}. Then L_{1} is of type A_{n−2} unless G has type D_{n}, in which case L_{1} is of type A_{1} × A_{n−3}.

We will use the following presentations (with X and Y disjoint):

• The presentation ⟨X | R⟩ for G_{1} in Theorem ??; and

• The presentation ⟨Y | S⟩ for G_{2} in Theorems ?? and ??(d). (The latter presentation is needed for the universal cover of Ω^{−}(6, q) rather than for general unitary groups.)

Choose two generators for L_{1}, two for L_{2} and two for L, all viewed as words in X or Y.

Bit-length: Generators for the subgroup ⟨U_{±α_{1}}⟩ ≅ SL(2, q) are used in the presentation ⟨X | R⟩ (cf. Section ??). Thus, by Remark ??, each element of ⟨U_{±α_{1}}⟩ has bit-length O(log q) in X.

Recall that the presentation in Theorem ?? was used in the proof of Theorem ??. Hence, the cycles in Remark ?? have bit-length O(log n) in X. Since L_{2} = ⟨U_{±α_{n}}⟩ and L = ⟨U_{±α_{j}}⟩ can each be obtained by conjugating ⟨U_{±α_{1}}⟩ using one of those cycles, it follows that our generators for these groups have bit-length O(log n+log q) in X. Similarly, in view of Remark ?? the proof of Theorem ?? shows that our two generators for L have bit-length O(log q) in terms of Y.

We need to be more careful with our choice of generators of L_{1} in order to achieve the desired bit-length. We will assume that G does not have type D_{n}; the omitted case is very similar. If n − 1 = 2, we can use any pair of generators by Remark ??. Assume that n − 1 ≥ 3. We temporarily write elements of L_{1} ≅ SL_{n−1} using (n − 1) × (n − 1) matrices. View ⟨U_{±α_{1}}⟩ = ( \begin{matrix}∗ & 0 \\ 0 & I \end{matrix} ) with 2 × 2 blocks ∗, inside SL(3, q) = ⟨U_{±α_{1}}, U_{±α_{2}}⟩ = ( \begin{matrix}∗ & 0 \\ 0 & I \end{matrix} ) with 3 × 3 blocks ∗. Choose a ∈ ⟨U_{±α_{1}}⟩ such that SL(3, q) = ⟨a, a^{(1,2,3)}⟩ (cf. Remark ??). The monomial transformation g := (1, 2, …, n − 1) or (1, 2, …, n − 1, −1, −2, …) = r_{12} (2, …, n − 1) is in L_{1}; and g has bit-length O(log n + log q) in X by the preceding paragraph. Note that a^{(1,2,3)} = a^{g}: since n − 1 ≥ 3, (1, 2, 3) and g agree on the first two coordinates. Then L_{1} ≥ ⟨a, g⟩ ≥ ⟨⟨a, a^{g}⟩^{⟨g⟩}⟩ = ⟨⟨a, a^{(1,2,3)}⟩^{⟨g⟩}⟩ = ⟨SL(3, q)^{⟨g⟩}⟩ = L_{1}, where a and a^{g} have bit-length O(log n + log q) in X.

We will show that G is isomorphic to the group J having the following presentation. In view of the preceding remarks, this presentation has the desired bit-length.

Generators: X, Y.

Relations:

(1) R ∪ S.

(2) [L_{1}, L_{2}] = 1.

More precisely, impose the four obvious commutation relations using pairs of words in X or Y that map onto the chosen generators for L_{1} or L_{2}.

(3) Identify the copies of L in G_{1} and G_{2}. More precisely, take the two generators for L, viewed as words in X and also in Y, and impose the equality of the corresponding words.

We claim that J ≅ G. For, clearly J surjects onto G, and hence we may assume that G_{1} = ⟨X⟩ and G_{2} = ⟨Y ⟩, L, L_{1} and L_{2} are subgroups of J. Clearly J is generated by the fundamental root groups contained in G_{1} or G_{2}. Any two of these root groups satisfy the Curtis-Steinberg-Tits relations (see the references in Section ??): either they are both in G_{1} or G_{2}, or they commute since [L_{1}, L_{2}] = 1. Thus, J is a homomorphic image of the universal finite group of Lie type of the given type, which proves the claim.

By Theorems ??, ??, ?? and ??(c), if the type is not D_{n} then the number of generators is |X| + |Y | ≤ 7 + 6 and the number of relations is |R| + |S| + 6 ≤ 25 + 36 + 6 = 67 (since 4 relations are required to ensure that [L_{1}, L_{2}] = 1 and 2 to identify the copies of L). For type D_{n} these numbers become 7 + 4 and 25 + 14 + 6.

As in [?, ?], in each case we can kill the center of G with at most one additional relation of bit-length O(log n + log q), except for some of the groups D_{n}, where two relations may be needed. Thus, in all cases we use at most 13 generators and at most 69 relations for all simple classical groups.

This proves the theorem for the classical groups. Howeover, for use in F_{4}(q), when G ≅ Sp(6, q) we can use the presentation in Theorem ?? instead of the one in Theorem ??. This time |X| + |Y | = 4 + 6 and |R| + |S| + 6 = 14 + 36 + 6 = 56.

Case 2: G is an exceptional group. We modify the above argument slightly. If G is the universal cover of E_{n}(q) with 6 ≤ n ≤ 8, for a suitable numbering of Π we can define G_{1}, G_{2}, L_{1}, L_{2}, L essentially as in (??): G_{1} still has type A_{n−1}, G_{2} has type A_{2}, and this time L_{1} has type A_{2} × A_{n−4}. Since L_{1} is still generated by 2 elements, precisely as above we obtain |X|+|Y | = 7+4 and |R|+|S|+6 = 25+14+6.

If G is F_{4}(q), then G_{1} = Sp(6, q), and both G_{2} and L_{1} have type A_{2}. We just saw that G_{1} has a presentation with 10 generators and 57 relations. By Theorem ?? we obtain |X| + |Y | = 10 + 4 and |R| + |S| + 6 = 56 + 14 + 6 = 76.

Similarly, if G is the universal cover of ^{2}E_{6}(q), then G_{1} = SU(6, q) and G_{2} and L_{1} both have type A_{2}. Using Theorems ??(a) and ??, we obtain |X| + |Y | = 8 + 4 and |R| + |S| + 6 = 43 + 14 + 6 = 63.

Since ⟨X | R⟩ and ⟨Y | S⟩ have bit-length O(log q), the same is true of our presentation for G.

Once again we can kill the center of G with at most one additional relation of bit-length O(log q). □

Proof of Theorems ?? and ??. As pointed out in Section ??, Theorem ?? follows from Theorem ?? and [?, Lemma 2.1]. Theorem ?? is contained in Theorems ??, ??, ??, ??, ??, ?? and ??, together with Sections ?? and ??. □

10. Additional presentations of classical groups

We now provide an alternative to the approach in the preceding section for presentations of classical groups. We will use Section ?? and its notation concerning the group W = W_{n} = ℤ_{2}^{n−1}⋊A_{n}, consisting of n × n real monomial matrices with respect to an orthonormal basis v_{1}, …, v_{n} of ℝ^{n}.

10.1. Groups of type D_{n}. By Theorem ??, since PΩ^{+}(6, q) ≅ PSL(4, q) we only need to consider the case n ≥ 4. We will use Proposition ?? to imitate the argument in Theorem ??.

Theorem 10.1. The group Ω^{+}(2n, q) has a presentation with

(a) 8 generators, 31 relations and bit-length O(log n + log q) if n ≥ 4, and

(b) 8 generators, 29 relations and bit-length O(log q) if n = 4 or 5. At most one additional relation of bit-length O(log n + log q) is needed in order to obtain a presentation for PΩ^{+}(2n, q).

Proof. There is a hyperbolic basis e_{1}, f_{1}, …, e_{n}, f_{n} of V = 𝔽_{q}^{2n} associated with G = Ω^{+}(2n, q). Then W consists of isometries. Moreover, W lies in G and permutes the pairs {e_{i}, f_{i}}, 1 ≤ i ≤ n: if n ≥ 5 then W is perfect, and for n = 4 we can see this by restricting from the group Ω^{+}(10, q).

Each element of W can be viewed using two different vector spaces: ℝ^{n} and V. In the action on V, we write elements in terms of the standard orthonormal basis v_{1}, …, v_{n}. The resulting diagonal elements of W are the elements leaving each pair {e_{i}, f_{i}} invariant. Since these two views are potentially confusing (especially when q is even), we will initially write elements in both manners.

We digress in order to observe that, when q is odd, W does not lift to an isomorphic copy inside the universal cover Ĝ of G. For, recall Steinberg’s criterion [?, Corollary 7.6]: an involution in Ω^{+}(2n, q) lifts to an element of order 4 in the spin group if and only if the dimension of its −1 eigenspace on V is ≡ 2 (mod 4). Apply this to diag(−1, −1, 1, …, 1) = (e_{1}, f_{1})(e_{2}, f_{2}) ∈ W in order to obtain an element of order 4 in Ĝ, which proves our claim.

We view F = SL(3, q) as the subgroup of G preserving the subspaces ⟨e_{1}, e_{2}, e_{3}⟩ and ⟨f_{1}, f_{2}, f_{3}⟩ while fixing the remaining basis vectors. We use

• the presentation ⟨X | R⟩ for F in Theorem ?? and

• the presentation ⟨Y | S⟩ for W = W_{n} in Proposition ?? (where X and Y are

disjoint), together with the following elements:

• c = (\begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}), f = (\begin{matrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & −1 \end{matrix})∈ F;

• a ∈ F such that L := ⟨a, a^{f}⟩ ≅ SL(2, q) consists of all matrices ( \begin{matrix}∗ & 0 \\ 0 & 1 \end{matrix} ) in F;

• (3, 2, 1) = (e_{3}, e_{2}, e_{1})(f_{3}, f_{2}, f_{1}), (1, 3)(2, 4) = (e_{1}, e_{3})(e_{2}, e_{4})(f_{1}, f_{3})(f_{2}, f_{4}) ∈ W and s = diag(−1, −1, 1, …, 1) = (e_{1}, f_{1})(e_{2}, f_{2}) ∈ Y; and

• σ and τ = (1, 2)(3, 4) = (e_{1}, e_{2})(e_{3}, e_{4})(f_{1}, f_{2})(f_{3}, f_{4}) ∈ W that generate the subgroup of W fixing ⟨v_{1} − v_{2}⟩ (within ℝ^{n}) and send v_{1} − v_{2} to v_{2} − v_{1}.

Bit-length: c, f and a have bit-length O(log q) using Remark ??. We may assume that σ is the product of diag(−1, −1, −1, −1, 1, …) and a cycle of odd length n − 2 or n − 3 on {3, …, n}; both σ and τ can then be viewed as words in Y of bit-length O(log n) (by Remark ??).

We will show that G is isomorphic to the group J having the following presentation. Generators: X, Y. Relations:

(1) R.

(2) S.
(3) c = (3, 2, 1).
(4) a^{σ} = a^{f}, a^{τ} = a^{f}.
(5) (a^{f})^{σ} = a.
(6) [a, a^{(1,3)(2,4)}] = 1.
(7) [a^{f}, a^{(1,3)(2,4)}] = 1 if n = 4 or 5.
(8) [a, a^{s^{(3,2,1)}}] = 1.
(9) [a^{f}, a^{s^{(3,2,1)}}] = 1 if n = 4.

There is a surjection J → G, in view of the previous remark concerning the universal cover of G together with the fact that the chosen element f acts on L in the same manner as any element of W that interchanges 1 and 2.

As usual, we may assume that F = ⟨X⟩ and W = ⟨Y ⟩ lie in J. By (4) and (5), ⟨σ, τ⟩ normalizes L (since τ has order 2 we also have (a^{f})^{τ} = a). As usual, it follows that L^{W} can be identified with the set of n(n − 1) pairs {±α} of vectors α = ±v_{i} ± v_{j} ∈ ℝ^{n}, i ≠ j, in the root system Φ of type D_{n}. The groups in L^{W} produce corresponding root groups X_{α}, α ∈ Φ.

Any unordered pair of distinct, non-opposite roots can be moved by W to one of the following pairs within ℝ^{n}:

(i) v_{1} − v_{2}, v_{1} + v_{2}  (ii) v_{1} − v_{2}, v_{1} − v_{3}
(iii) v_{1} − v_{2}, v_{3} − v_{1}  (iv) v_{1} − v_{2}, v_{3} − v_{4}.

Then the corresponding root groups can be moved in the same manner. Let N := ⟨L^{W} ⟩ = ⟨X_{α} | α ∈ Φ⟩ = ⟨F^{W} ⟩ ⊴ J. We need to verify the Steinberg relations for the root groups X_{α}. The pairs

(ii) and (iii) already lie in F = SL(3, q), so the desired relations are immediate. It remains to consider the cases (i) and (iv).

As in (??) (inside the proof of Theorem ??), (6) and (7) imply that the root groups determined by (iv) commute.

Before considering (i), we note that (4) and (5) imply that every element of W that interchanges v_{1} −v_{2} and v_{2} −v_{1} also interchanges a and a^{f}. Two such elements are s and, when n ≥ 5, also (1, 2)(4, 5). Since t := s^{(3,2,1)} = diag(1, −1, −1, 1, …, 1) commutes with s, and t^{(1,2)(4,5)} = diag(−1, 1, −1, 1, …, 1) = st, by (8) we have

\begin{matrix}1 = [a^{s}, (a^{s})^{t}] = [a^{f}, (a^{f})^{t}] \\ 1 = [a^{(1,2)(4,5)}, a^{t(1,2)(4,5)}] = [a^{f}, (a^{(1,2)(4,5)s})^{t}] = [a^{f}, a^{t}]. \end{matrix}

By (9), the second of these relations also holds when n = 4. Then also 1 = [a^{f}^{t}, a]. Now the root groups X_{v_{1}−v_{2}} < L_{v_{1}−v_{2}} = L = ⟨a, a^{f}⟩ and X_{v_{1}+v_{2}} < L_{v_{1}+v_{2}} = L^{t} = ⟨a^{t}, a^{f}^{t}⟩ commute, as required for (i).

Thus, N ≅ G. Relation (3) pulls (1, 2, 3) into N, so that J/N = 1.

Now use Proposition ?? in order to obtain a presentation for Ω^{+}(2n, q) having the stated numbers of generators and relations. Finally, at most one further relation of bit-length O(log n + log q) is needed to kill the center. □

This should be compared to the presentations for these groups in Section ?? using 11 generators and 46 relations.

10.2. Groups of type B_{n} and C_{n}. This time we will glue W_{n} and a group of type B_{2} or C_{2}.

Theorem 10.2. The groups Sp(2n, q), Ω(2n + 1, q) and Ω^{−}(2n + 2, q) have presentations with

(a) 10 generators, 58 relations and bit-length O(log n + log q) if n ≥ 4,

(b) 9 generators, 57 relations and bit-length O(log q) if n = 4 or 5, and

(c) 8 generators, 52 relations and bit-length O(log q) if n = 3. At most one additional relation of bit-length O(log n + log q) is needed in order to obtain a presentation for PSp(2n, q) or PΩ^{−}(2n + 2, q).

Proof. The root system Φ of type C_{n} or B_{n} for G = Sp(2n, q), Ω(2n + 1, q) or Ω^{−}(2n + 2, q) consists of the vectors ±v_{i} ± v_{j} for 1 ≤ i < j ≤ n, and all ±2v_{i} or ±v_{i}, respectively. We may assume that a fundamental system is

Π = {α_{1}, α_{j} = v_{j+1} − v_{j} | 2 ≤ j ≤ n − 1} ,

where α_{1} = 2v_{1} or v_{1}.

We will use the subgroup L_{12} ≅ Sp(4, q), Ω(5, q) or Ω^{−}(6, q) corresponding to the root subsystem Φ_{12} generated by α_{1} and α_{2}, and its rank 1 subgroups L_{1} and L_{2} determined by ±α_{1} and ±α_{2}, respectively. We will also need the subgroup L_{23} corresponding to the root subsystem generated by α_{2} and α_{3}.

There is a hyperbolic basis e_{1}, f_{1}, …, e_{n}, f_{n} associated with G (with additional basis vectors v, or v and v′, perpendicular to all of these in the orthogonal cases). We may assume that W = W_{n} permutes these 2n vectors, with its normal subgroup ℤ_{2}^{n−1} fixing each pair {e_{i}, f_{i}}. We may assume that the support of L_{12} is ⟨e_{1}, f_{1}, e_{2}, f_{2}⟩ (or ⟨e_{1}, f_{1}, e_{2}, f_{2}, v⟩ or ⟨e_{1}, f_{1}, e_{2}, f_{2}, v, v′⟩ in the orthogonal cases); and if n ≥ 4 then the support of L_{2}^{(1,3)(2,4)} is ⟨e_{3}, e_{4}, f_{3}, f_{4}⟩, so that

(10.3)  [L_{12}, L_{2}^{(1,3)(2,4)}] = 1.

Similarly,

(10.4)  [L_{1}, L_{2}^{c^{2}}] = 1.

We will use the following elements, writing matrices for L_{2} using the vectors e_{1}, e_{2} (and, implicitly, also their “duals” f_{1}, f_{2}), and writing elements of W using ℝ^{n}:

• c = (1, 2, 3) = (e_{1}, e_{2}, e_{3})(f_{1}, f_{2}, f_{3}) ∈ W and s = diag(−1, −1, 1, …, 1) = (e_{1}, f_{1})(e_{2}, f_{2}) ∈ Y;

• (2, 3, 4) = (e_{2}, e_{3}, e_{4})(f_{2}, f_{3}, f_{4}), (1, 3)(2, 4) = (e_{1}, e_{3})(e_{2}, e_{4})(f_{1}, f_{3})(f_{2}, f_{4}) ∈ W if n ≥ 4;

• σ, τ ∈W generating the stabilizer W_{{±v_{1},±v_{2}}}=W_{{{e_{1},f_{1}},{e_{2},f_{2}}}} ≅ ℤ_{2}^{n−1}⋊S_{n−2};

• h = diag(ζ^{−1}, ζ) generating the torus that normalizes the root subgroups X_{±α_{2}} of L_{2} := L_{α_{2}};

• u = ( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ) ∈ X_{α_{2}};

• a ∈ L_{2} such that L_{2} = ⟨a, a^{s}⟩;

• a_{2} ∈ L_{2} such that L_{2} = ⟨a_{2}, a_{2}^{r_{2}h}⟩;

• b ∈ L_{12} such that L_{12} = ⟨b, b^{s}⟩; and

• two generators for L_{1}. Bit-length: Once again, by Remarks ?? and ?? the stated elements of L_{1}, L_{2} and

L_{12} have bit-length O(log q), while σ and τ have bit-length O(log n). The required elements a, a_{2} and b exist. For b, use the fact that PSp(4, q) ≅

PΩ(5, q) and then, in the orthogonal 5- or 6-dimensional group L_{12}, choose an element b of order (q^{2} + 1)/(2, q − 1) such that ⟨b, b^{s}⟩ has no proper invariant subspace of dimension > 1. (This means that ⟨b, b^{s}⟩ is irreducible, except in the case PΩ(5, q), q even.)

We will use the following presentations:

• a presentation ⟨X | R⟩ for L_{12} ≅ Sp(4, q), Ω(5, q) or Ω^{−}(6, q) when G = Sp(2n, q), Ω(2n + 1, q) or Ω^{−}(2n + 2, q), respectively; and

• a presentation ⟨Y | S⟩ for W = W_{n} (where X and Y are disjoint). We have corresponding root groups X_{α} whenever α ∈ Φ_{12}.

As in Section ??, in the orthogonal cases with q odd W does not lift to an isomorphic subgroup of the universal cover.

We will show that G is isomorphic to the group J having the following presentation. Generators: X, Y. Relations:

(1) R.

(2) S.

(3) x′^{σ} and x′^{τ} written as words in X, for each x′ ∈ {b, b^{s}}.

(4) (2, 3, 4) commutes with L_{1} if n ≥ 4.

(5) c^{r_{2}} = r_{2}^{2}c^{2}.

(6) hh^{c}h^{c^{2}} = 1.

(7) a_{2}^{h^{c}} = a_{2}^{diag(1,ζ^{−1})} written as a word in X.

(8) [u^{c}, u] = (u^{r_{2}})^{c^{2}}.

(9) [u^{c}, u^{r_{2}}] = 1.

(10) [b, a^{(1,3)(2,4)}] = 1 if n ≥ 4.

(11) [L_{1}, L_{2}^{c^{2}}] = 1 if n = 3.

(12) s written as a word in L_{1} ∪ L_{2} if n = 3. Note that the relations (2)–(6) in Theorem ?? are the present relations (5)–(9)

for L_{23} := ⟨L_{2}, c⟩ ≅ SL(3, q). Also, the present relations (10) and (11) follow from (??) and (??). Therefore, as usual, there is a surjection J → G, and we may assume that L_{12} = ⟨X⟩, W = ⟨Y ⟩ and L_{23} = ⟨L_{2}, c⟩ lie in J. Case n ≥ 4: Relations (3) and (4) imply that ⟨W_{{±v_{1},±v_{2}}}, (2, 3, 4)⟩ = W_{{±v_{1}}} normalizes L_{1}. As usual, it follows that |L_{1}^{W} | = n. Similarly, by (3), |L_{12}^{W}| = n(n − 1)/2 and each element of W_{{±v_{1},±v_{2}}} acts correctly on L_{12}. Then the normalizer of L_{2} in W_{{±v_{1},±v_{2}}} has index 2, so that |L_{2}^{W} | ≤ n(n − 1). As usual, it follows that |L_{2}^{W} | = n(n − 1). Starting with the root subgroups X_{α_{1}} and X_{α_{2}} of L_{12}, in J we obtain the “correct” set X_{α_{1}}^{W} ∪ X_{α_{2}}^{W} = {X_{α} | α ∈ Φ} of root subgroups.

We will verify that the Steinberg relations hold for N := ⟨X_{α_{1}}^{W} ∪ X_{α_{2}}^{W}⟩ = ⟨L_{12}^{W}⟩ ⊴ J, after which we will have J/N = 1 by (10). Many of the required relations are already available for L_{12} and L_{23}.

Any unordered pair α, β of distinct, non-opposite roots can be moved by W to one of

(i) α_{1}, ±α_{2}, (ii) α_{1}, ±α_{1} ± α_{2}, (iii) α_{1}, α_{4}, (iv) α_{2}, α_{3}, or (v) α_{2}, α_{4}. Only pairs (iii) and (v) are not inside L_{12} or L_{23}.

Since each element of W_{{±v_{1},±v_{2}}} acts correctly on L_{12}, s′ := s^{(1,3)(2,4)} commutes with L_{12} (cf. (??)). By (10),

1 = [b, a^{(1,3)(2,4)}]^{s} = [b^{s}, a^{s′(1,3)(2,4)}] = [b^{s}, a^{(1,3)(2,4)}]
1 = [b, a^{(1,3)(2,4)}]^{s′} = [b, (a^{s})^{(1,3)(2,4)}]
1 = [b, a^{(1,3)(2,4)}]^{ss′} = [b^{s′}^{s}, (a^{s′s})^{(1,3)(2,4)}] = [b^{s}, (a^{s})^{(1,3)(2,4)}].

Now [L_{12}, L_{2}^{(1,3)(2,4)}] = [⟨b, b^{s}⟩, ⟨a, a^{s}⟩^{(1,3)(2,4)}] = 1, which takes care of the pairs (iii) and (v).

Thus, J is a central extension of G. We already noted that J cannot be the universal cover in the orthogonal cases. Hence, J = N ≅ G.

For the counts in (a) and (b) use Theorems ?? and ?? together with Proposition ??. Case n = 3: Once again, |L_{1}^{W} | = 3 and |L_{2}^{W} | = 6, and we obtain root groups X_{α}, α ∈ Φ.

This time we consider the subgroup M := ⟨L_{12}, L_{23}⟩ of N := ⟨X_{α_{1}}^{W} ∪ X_{α_{2}}^{W}⟩ = ⟨L_{12}^{W}⟩ ⊴ J. By the Curtis-Tits-Steinberg presentation mentioned in Section ??, in order to prove that G ≅ M we only need to consider pairs X_{α}, X_{β} of root groups with α, β lying in the subsystem of Φ determined by one of the pairs {α_{1}, α_{2}}, {α_{2}, α_{3}} or {α_{1}, α_{3}}. In the first two cases the desired relations already hold in L_{12} or L_{23}. The last case is covered by (11).

It follows that M ≅ G. As in (??), from (12) we obtain W = ⟨s, c⟩ ≤ M. Then J = N = M ≅ G. This time we use the presentation for W_{3} ≅ A_{4} in (??). Hence, in (c) this presentation for J uses only 6 + 2 generators and at most 36 + 3 + 7 + 4 relations. □

Recall that we already had presentations for these groups in Section ?? having at most 13 generators and at most 67 relations.

11. Concluding remarks

1. Short and bounded presentations are goals of one aspect of Computational Group Theory ([?, pp. 290-291] and [?, p. 184]). Such presentations have various applications, such as in [?, ?] for gluing together presentations in a normal series in order to obtain a presentation for a given matrix group. The presentations in the present paper are not short in the sense of length used in [?, ?, ?]. However, they have the potential advantage that they are simpler than those in [?], at least in the sense of requiring fewer relations. We hope that both types of presentations will turn out to be useful in Computational Group Theory.

2. The presentations for S_{n} and A_{n} in Section ?? that are related to prime numbers appear to be practical. The ones in Section ?? for general n have one unusual and awkward relation y = w, expressing y as a word in X ∪ X^{y}; see (??) and the description of this word in the proof of Theorem ??. Experimentation appears to be needed in order to find a “nice” additional relation of this sort. That is, the presentation in Section ?? is among the easiest to describe of the presentations obtained using our methods, but it may not be the best in practice.

3. We used the presentations (??) of A_{4} and A_{5} in the proofs of Proposition ?? and Theorems ??, ?? and ??. If we had instead used the corresponding presentations of SL(2, 3) or SL(2, 5), with 2 generators and 2 relations, we could have saved an additional relation.

There are further small-rank cases where we could have proceeded in the same manner. Presentations are known for the universal central extension of A_{n}, n ≤ 9, with 2 generators and 2 relations [?, ?]; and for A_{10} using 2 generators and 3 relations [?] (cf. Example ??(??)). For these small n such presentations can be used in our presentations in order to save several relations.

4. As in the proof of Corollary ??, Lemma ?? can be used in order to decrease the number of relations by one in Theorem ??. The easiest way to see this is to use the “3/2-generation” of all finite simple groups [?], according to which any one of our generators a is a member of a generating pair {a, b}; and then proceed as in Corollary ??. However, this uses an unnecessary amount of machinery, since each of our generating sets contains a member a for which a suitable b can be found without much difficulty.

5. For the groups S_{n}, A_{n} and SL(n, q) we were careful to make the number of relations small. For the other groups we were somewhat less careful. It is likely that one can obtain presentations of these groups with fewer relations using ideas provided here.

In particular, the presentations of rank 2 groups in Section ?? undoubtedly could be improved using the more careful approach in Section ??. For example, there should be no need for both u_{α_{i},1} and u_{α_{i},2}.

The number of relations in Proposition ?? probably can be improved somewhat by using the ideas in Sections ?? and ?? in place of Theorem ??.

Phan-type presentations for orthogonal groups [?, ?] should help decrease the numbers of relations in Sections ??, ?? and ??.

6. Theorem ?? did not deal with all central extensions of orthogonal groups, in particular, it did not handle spin groups. These can be dealt with in the same manner, by using a double cover of W_{n}.

7. There is a small generating subset of each finite simple group G producing a Cayley graph of diameter O(log |G|) [?, ?]. Such generators need to be incorporated into Theorem ?? in order to obtain somewhat shorter presentations.

8. As observed in Section ?? we have constructed presentations for alternating and symmetric groups with bounded expo-length. The remaining presentations in this paper do not have this property, unless we only consider groups over bounded degree extensions of the prime field. An obstacle to our obtaining presentations with bounded expo-length is that we do not know sufficiently nice presentations of 𝔽_{q} when this field has large degree over the prime field 𝔽_{p}.

In Section ??, we started with a presentation of 𝔽_{q} (as an algebra over 𝔽_{p}) of the form 𝔽_{q} = 𝔽_{p}[x, y]/(m(x), y − g_{ζ^{2}}(x)), where x, y map onto ζ^{2d} and ζ^{2}, respectively, and used it to obtain a presentation of SL(2, q).

Roughly speaking, short (with length O(log q)) presentations of 𝔽_{q} as an algebra over 𝔽_{p} yield presentations of SL(2, q) with short bit-length. However in order to obtain a presentation of SL(2, q) with bounded expo-length using the same method, we would need a presentation of 𝔽_{q} in which every relation involves only a bounded number of monomials. This is a computational question concerning “sparse” constructions of finite fields about which little appears to be known [?]. The same remarks also apply to the unitary and Suzuki groups.

Acknowledgements: We are grateful to George Havas for providing the presentations in Example ??(??, ??), to John Bray for providing the presentations in Section ??, and to Bob Griess for pointing out Steinberg’s criterion [?, Corollary 7.6] used in Section ??.

References

[Ar] E. Artin, Theorie der Zöpfe. Abh. Hamburg 4 (1925) 47–72.

[BGKLP] L. Babai, A. J. Goodman, W. M. Kantor, E. M. Luks and P. P. Pálfy, Short presentations for finite groups. J. Algebra 194 (1997) 79–112.

[BKL] L. Babai, W. M. Kantor and A. Lubotzky, Small diameter Cayley graphs for finite simple groups. European J. Combinatorics 10 (1989) 507–522.

[Bau] G. Baumslag, A finitely presented metabelian group with a free abelian derived group of infinite rank. Proc. Amer. Math. Soc. 35 (1972) 61–62.

[BGHS] C. Bennett, R. Gramlich, C. Hoffman and S. Shpectorov, Curtis-Phan-Tits theory, pp. 13–29 in: Groups, Combinatorics and Geometry (Durham, 1990; Eds. M. W. Liebeck and J. Saxl), Lond. Math. Soc. Lecture Note 165. Cambridge University Press, Cambridge 1992.

[BeS] C. D. Bennett and S. Shpectorov, A new proof of Phan’s theorem. J. Group Theory 7 (2004) 287–310.

[Bn] D. J. Benson, Representations and cohomology. I. 2nd ed., Cambridge Stud. Adv. Math. 30, Cambridge University Press, Cambridge 1998.

[Bray] J. Bray, personal communication.

[BCLO] J. Bray, M. D. E. Conder, C. R. Leedham-Green and E. A. O’Brien, Short presentations for alternating and symmetric groups (preprint).

[Bre] R. Breusch, Zur Verallgemeinerung des Bertrandschen Postulates, dass zwischen x und 2x stets Primzahlen liegen. Math. Z. 34 (1932) 505–526.

[Bur] W. Burnside, Theory of Groups of Finite Order, 2nd ed. Cambridge University Press, Cambridge 1911.

[CR1] C. M. Campbell and E. F. Robertson, Classes of groups related to F^{a,b,c}. Proc. Roy. Soc. Edinburgh A78 (1977/78) 209–218.

[CR2] C. M. Campbell and E. F. Robertson, A deficiency zero presentation for SL(2, p). Bull. London Math. Soc. 12 (1980) 17–20.

[CR3] C. M. Campbell and E. F. Robertson, The efficiency of simple groups of order < 10^{5}. Comm. Algebra 10 (1982), 217–225.

[CRKMW] C. M. Campbell, E. F. Robertson, T. Kawamata, I. Miyamoto and P. D. Williams, Deficiency zero presentations for certain perfect groups. Proc. Roy. Soc. Edinburgh 103A (1986) 63–71.

[CRW] C. M. Campbell, E. F. Robertson and P. D. Williams, On presentations of PSL(2, p^{n}). J. Austral. Math. Soc. 48 (1990) 333–346.

[CHRR1] C. M. Campbell, G. Havas and C. Ramsay and E. F. Robertson, Nice efficient presentations for all small simple groups and their covers (to appear).

[CHRR2] C. M. Campbell, G. Havas and C. Ramsay and E. F. Robertson, On the efficiency of the simple groups with order less than a million and their covers (to appear).

[CMY] J. J. Cannon, J. McKay and K.-C. Young. The non-abelian simple groups G, |G| < 10^{5} — presentations. Comm. Algebra 7 (1979) 1397–1406.

[CP] J. J. Cannon and C. Playoust, An introduction to Magma. School of Math. and Stat., Univ. Sydney, 1993.

[Carm] R. D. Carmichael, Introduction to the theory of groups of finite order. Ginn, Boston 1937.

[Cart] R. W. Carter, Simple groups of Lie type. Wiley, London 1972.

[CHR] M. Conder, G. Havas and C. Ramsay, Efficient presentations for the Mathieu simple group M_{22} and its cover, pp. 33–42 in: Finite Geometries, groups, and computation (Eds. A. Hulpke et al.), deGruyter, Berlin 2006.

[CoMo] H. S. M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, 3rd ed. Springer, New York-Heidelberg 1972.

[Cur] C. W. Curtis, Central extensions of groups of Lie type. J. reine angew. Math. 220 (1965) 174–185.

[Di] J. D. Dixon, The probability of generating the symmetric group. Math. Z. 110 (1969) 199–205.

[Er] P. Erdös, Über die Primzahlen gewisser arithmetischer Reihen. Math. Z. 39 (1935) 473–491.

[GaN] J. von zur Gathen and M. Nöcker, Polynomial and normal bases for finite fields. J. Cryptology 18 (2005) 337–355.

[GLS] D. Gorenstein, R. Lyons and R. Solomon, Amer. Math. Soc., Providence, R.I., 1998.

[Gr] R. Gramlich, Developments in finite Phan theory. Innov. Incidence Geom. (to appear).

[GHNS] R. Gramlich, C. Hoffman, W. Nickel and S. Shpectorov, Even-dimensional orthogonal groups as amalgams of unitary groups. J. Algebra 284 (2005) 141–173.

[Gri] R. L. Griess, Jr., Schur multipliers of finite simple groups of Lie type. Trans. Amer. Math. Soc. 183 (1973) 355–421.

[Gru] K. Gruenberg, Relation Modules of Finite Groups. Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 25. Amer. Math. Soc., Providence, R.I., 1976.

[GrK] K. Gruenberg, and L. G. Koväcs, Proficient presentations and direct products of finite groups. Bull. Austral. Math. Soc. 60 (1999), 177–189.

[GH] R. M. Guralnick and C. Hoffman, The first cohomology group and generation of simple groups, Proceedings of a Conference on Groups and Geometry, Siena, Trends in Mathematics, 81-90, Birkäuser Verlag, 1998.

[GK] R. M. Guralnick and W. M. Kantor, Probabilistic generation of finite simple groups. J. Algebra 234 (2000) 743–792.

[GKKL1] R. M. Guralnick, W. M. Kantor, M. Kassabov and A. Lubotzky, Presentations of finite simple groups: a quantitative approach (to appear in J. Amer. Math. Soc.). http://trefoil.math.ucdavis.edu/0602.5508

[GKKL2] R. M. Guralnick, W. M. Kantor, M. Kassabov and A. Lubotzky, Presentations of finite simple groups: a cohomological and profinite approach (to appear in Groups, Geometry and Dynamics). http://trefoil.math.ucdavis.edu/0711.2817

[Har] R. W. Hartley, Determination of the ternary linear collineation groups whose coefficients lie in the GF(2^{n}). Ann. Math. 27 (1926) 140–158.

[Hav] G. Havas, personal communication.

[Ho] D. F. Holt, On the second cohomology group of a finite group. Proc. Lond. Math. Soc. 55 (1987) 22–36.

[HEO] D. F. Holt, B. Eick and E. A. O’Brien, Handbook of computational group theory. Chapman & Hall, Boca Raton 2005.

[HS] A. Hulpke and Á. Seress, Short presentations for three-dimensional unitary groups. J. Algebra 245 (2001) 719–729.

[Ka] W. M. Kantor, Some topics in asymptotic group theory, pp. 403-421 in: Groups, Combinatorics and Geometry (Durham, 1990; Eds. M. W. Liebeck and J. Saxl), Lond. Math. Soc. Lecture Note 165. Cambridge University Press, Cambridge 1992.

[KLu] W. M. Kantor and A. Lubotzky, The probability of generating a finite classical group. Geom. Dedicata 36 (1990) 67–87.

[KS] W. M. Kantor and Á. Seress, Computing with matrix groups, pp. 123–137 in: Groups, combinatorics and geometry (Durham, 2001; Eds. A. A. Ivanov et al.). World Sci. Publ., River Edge, NJ 2003.

[LG] C. R. Leedham-Green, The computational matrix group project, pp. 229–247 in: Groups and Computation III (Eds. W. M. Kantor and Á. Seress). deGruyter, Berlin-New York 2001.

[LiSh] M. W. Liebeck and A. Shalev, The probability of generating a finite simple group. Geom. Dedicata 56 (1995) 103–113.

[Lu] A. Lubotzky, Pro-finite presentations. J. Algebra 242 (2001), 672–690.

[Mil] G. A. Miller, Abstract definitions of all the substitution groups whose degrees do not exceed seven. Amer. J. Math. 33 (1911) 363–372.

[Mit] H. H. Mitchell, Determination of the ordinary and modular ternary linear groups. Trans. Amer. Math. Soc. 12 (1911) 207–242.

[Mol] K. Molsen, Zur Verallgemeinerung des Bertrandschen Postulates. Deutsche Math. 6 (1941) 248–256.

[Moo] E. H. Moore, Concerning the abstract groups of order k! and \frac{1}{2} k! holohedrically isomorphic with the symmetric and the alternating substitution groups on k letters. Proc. Lond. Math. Soc. 28 (1897) 357–366.

[Mor] P. Moree, Bertrand’s postulate for primes in arithmetical progressions. Comput. Math. Appl. 26 (1993) 35–43.

[Neu] B. H. Neumann, On some finite groups with trivial multiplicator. Publ. Math. Debrecen 4 (1956) 190–194.

[Ph] K. W. Phan, On groups generated by three-dimensional special unitary groups I. J. Austral. Math. Soc. Ser. A23 (1977) 67–77.

[Ra] S. Ramanujan, A proof of Bertrand’s Postulate. J. Indian Math. Soc. 11 (1919) 181– 182.

[Ro] E. F. Robertson, Efficiency of finite simple groups and their covering groups, pp. 287–294 in: Finite groups–coming of age, Contemp. Math. 45, Amer. Math. Soc., Providence, R.I., 1985.

[Se] J.-P. Serre, Galois Cohomology, Springer, Berlin 2002.

[Sim] C. C. Sims, Computation with finitely presented groups. Cambridge Univ. Press, Cambridge 1994.

[Soi] L. Soicher (in preparation).

[St1] R. Steinberg, Lectures on Chevalley groups (mimeographed notes). Yale University 1967.

[St2] R. Steinberg. Generators, relations and coverings of algebraic groups, II. J. Algebra 71 (1981) 527–543.

[Sun] J. G. Sunday, Presentations of the groups SL(2, m) and PSL(2, m). Canad. J. Math. 24 (1972) 1129–1131.

[Suz] M. Suzuki, On a class of doubly transitive groups. Ann. of Math. 75 (1962) 105–145.

[Ti1] J. Tits, Les groupes de Lie exceptionnels et leur interprétation géométrique. Bull. Soc. Math. Belg. 8 (1956) 48–81.

[Ti2] J. Tits, Buildings of spherical type and finite BN-pairs. Springer, Berlin-New York 1974.

[To] J. A. Todd. A note on the linear fractional group. J. Lond. Math. Soc. 7, 195–200.

[Wi] J. S. Wilson, Finite axiomatization of finite soluble groups. J. Lond. Math. Soc. 74 (2006) 566–582.

Department of Mathematics, University of Southern California, Los Angeles, CA 90089-2532 USA

E-mail address: guralnic@usc.edu

Department of Mathematics, University of Oregon, Eugene, OR 97403 USA

E-mail address: kantor@math.uoregon.edu

Department of Mathematics, Cornell University, Ithaca, NY 14853-4201 USA

E-mail address: kassabov@math.cornell.edu

Department of Mathematics, Hebrew University, Givat Ram, Jerusalem 91904 Israel

E-mail address: alexlub@math.huji.ac.il