If|F|>4, then the algorithms run in time polynomial in the size of the input, subject to the existence of a discrete logarithm oracle forF

Heiko Dietrich, C. R. Leedham-Green, Frank L¨ubeck, and E. A. O’Brien

ABSTRACT. LetG=hXi ≤GL(d,F)be a classical group in its natural representation defined over a finite fieldFof even characteristic. We present Las Vegas algorithms to construct standard generators forGwhich permit us to write an element ofGas a straight-line program inX, and to construct an involution as a straight-line program inX. If|F|>4, then the algorithms run in time polynomial in the size of the input, subject to the existence of a discrete logarithm oracle forF.

In memory of our friend, ´Akos Seress 1. Introduction

Let C ≤ GL(d, q)be a classical group in its natural representation, and letG = hXibe any group isomorphic to C. Informally, a constructive recognition algorithm for G constructs an isomorphism betweenGandCand exploits this isomorphism to write an arbitrary element ofG as a word in its generatorsX. For a more formal definition, see [41, p. 192].

We can realise such an algorithm as follows. For each classical groupC, we define a specific ordered set of standard generators S. The first task is to construct, as words inX, an ordered subsetS^′ofGthat is the image ofSunder an isomorphism betweenC andG. The second task is to solve the constructive membership problem forGwith respect toS^′: namely, expressg∈G as a word inS^′, and so as a word inX. Now the isomorphismϕ:G → C that mapsS^′ toS is constructive: every element inG is first written as a wordg = w(S^′) inS^′, and the image ϕ(g) =w(S)is immediately determined as the corresponding word inS. In a similar way, the inverse ofϕis constructive.

In this paper, as an important special case, we suppose thatGis given in its natural represen- tation, soGandCare conjugate inGL(d, q). Since a conjugating element that mapsGtoCcan be found readily, we may assume thatG=C. The constructive membership problem forCwith respect toSis solved by work of Costi [20]. It remains to constructS^′ ⊆Gas a set of words in the given defining generatorsX; by construction,SandS^′are conjugate inGL(d, q).

Leedham-Green & O’Brien [28] developed a Las Vegas algorithm which solves this problem for odd q. Subject to the existence of a discrete logarithm oracle, the algorithm runs in time polynomial in the size of the input. Efficient implementations are publicly available in the com- putational algebra system MAGMA [6]. The algorithm uses a recursion to classical groups of smaller degree. The first step is to find, by a random search inG, an involution with large±1- eigenspaces. The derived group of the centraliser inGof this involution acts on these eigenspaces

Key words and phrases. classical groups, constructive recognition, even characteristic.

We thank Peter Brooksbank and Robert Wilson for helpful discussions; Bill Kantor for comments on a draft; and Cheryl Praeger for making the results of the preprint [40] available to us. We also thank the referee for many helpful suggestions. Dietrich was funded by a University of Auckland Postdoctoral Fellowship. L¨ubeck acknowledges the generous support of the Alexander von Humboldt Stiftung for a visit by him to the University of Auckland. All authors were partially supported by the Marsden Fund of New Zealand via grant UOA 1015.

1

as the direct product of classical groups in smaller degrees, and these factors are used for the re- cursion.

For even q, the situation is more complex. Since the proportion of elements inGof even order is at most5/q (see [22]), it is not practical, for largeq, to find an involution by a random search. Another obstacle is that the structure of involution centralisers is more complicated than in odd characteristic, and the two groups for a recursion cannot be found in such a centraliser.

In this paper, we present a constructive recognition algorithm for classical groups in their natural representation defined over finite fields of even characteristic. Subject to the existence of a discrete logarithm oracle, we prove that the algorithm runs in time polynomial in the size of the input (provided thatq >4). Our implementation is publicly available in MAGMA.

This work contributes to the Matrix Group Recognition Project; its goal is to provide efficient algorithms to investigate matrix groups defined over finite fields. For an overview of this project, see the survey articles [37, 38].

1.1. The groups and their standard copies. The groups of interest are the special linear group, the symplectic group, the special unitary group, and the orthogonal groups, all over a finite field of even characteristic. The definition of all of these groups, except for the first, depends on the choice of a bilinear or quadratic form. However, the groups defined by two different forms of the same type are conjugate in the corresponding general linear group. The standard copy of a classical group is its unique conjugate which preserves a chosen standard form.

We now describe these groups and their standard forms; we refer to [43] for more details. The form is given as a matrix with respect to some chosen basis. In all cases,dis an integer greater than 1,q is an even prime-power, andV is the underlying row vector space on which the group acts by right multiplication. LetGL(d, q)be the group of all invertibled×dmatrices over the fieldGF(q)withq elements. We denote bydiag(M₁, . . . , M_n) the block diagonal matrix with blocksM₁, . . . , M_n.

• SL(d, q): the subgroup of elements ofGL(d, q)with determinant 1.

• Sp(d, q): the subgroup of elements ofSL(d, q)that preserve a given non-degenerate alternat- ing bilinear form onV. The existence of such a form implies thatdis even. The standard copy is the group that preserves the formF = diag((^{0 1}_{1 0}), . . . ,(^{0 1}_{1 0})).

• SU(d, q): the subgroup of elements ofSL(d, q²)that preserve a given non-degenerate hermit- ian form onV. The standard hermitian forms for even and odd degree areF anddiag(F,1), respectively, withF as defined forSp.

• Ω⁺(d, q): the derived subgroup ofO⁺(d, q), the subgroup of elements ofSL(d, q)that pre- serve a given non-degenerate quadratic form onV of+type. This implies thatdis even, and we assumed ≥ 4. The standard quadratic form of+type isQ = diag((^{0 1}_{0 0}), . . . ,(^{0 1}_{0 0})), which is preserved byg ∈ GL(d, q) if and only ifvgQg^⊺v^⊺ = vQv^⊺for allv ∈ V. The supported bilinear form isQ+Q^⊺=F.

• Ω⁻(d, q): defined as forΩ⁺(d, q), except that the form is of−type. Again,dis even, and we assumed≥4. Ifγis a fixed primitive element ofGF(q²), then the standard quadratic form of−type isdiag((^{0 1}_{0 0}), . . . ,(^{0 1}_{0 0}), ¹₀^a_b

)wherea=γ+γ^qandb=γ^q+1. The supported bilinear form isdiag((^{0 1}_{1 0}), . . . ,(^{0 1}_{1 0}),(⁰_a^a₀)).

We writeSX(d, q)for a conjugate of one of the above groups; this implicitly means thatq is even andd≥ 4if the group is orthogonal. We callSL,SU,Sp, Ω⁺, andΩ⁻the type of the group. A basis of the underlying vector space is hyperbolic ifSX(d, q)is the standard copy with respect to it.

For each standard copy, a specific set of standard generators is defined in Section 2. This generating set has cardinality at most 7. Costi [20] developed an algorithm to write an arbitrary element in the standard copy as a word in these generators; it is deterministic and runs in time polynomial in the input size, cf. [38,§9.1].

Remark 1.1. We consider only classical groups over finite fields of even characteristic. With the exceptions of Sp(2,2)and Sp(4,2), all symplectic groups are simple. With the exception ofSL(2,2), all special linear groups are perfect, and simple if and only ifgcd(d, q−1) = 1.

With the exception ofSU(2,2), all special unitary groups are perfect, and simple if and only if gcd(d, q+ 1) = 1. With the exception ofΩ⁺(4,2), all groups of typeΩ^±are perfect; with the exception ofΩ⁺(4, q), all groups of typeΩ^±are simple.

1.2. Main results. Let G = SX(d, q) with q even. We present and analyse a Las Vegas algorithm that takes as input the type of G and a generating set X, and outputs the standard generators of G as words in X. Usually, these generators are defined with respect to a basis different to that for whichXwas defined, and a matrix relating these bases is also returned. All words are given as straight-line programs (SLPs). Intuitively, SLPs are efficiently stored group words inX; for a formal definition and discussion of their significance, see [41, p. 10].

Unless otherwise stated, all complexities are measured in field operations. Let ξ denote an upper bound to the number of field operations needed to construct an independent (nearly) uniformly distributed random element of a subgroup of SX(d, q). Our algorithms assume the existence of a discrete log oracle: ifG = Ω⁻(4, q) ∼= PSL(2, q²), then the oracle is required forGF(q²), otherwise forGF(q). To simplify statements, we ignore alllog logdandlog logq factors; and we useχto denote an upper bound to the number of field operations equivalent to a call to a discrete logarithm oracle for the appropriate field.

Our main result is the following theorem.

Theorem 1.2. LetX be a generating set of bounded cardinality forG = SX(d, q). There is a Las Vegas algorithm that constructs the standard generators forGas SLPs inX. Ifq >4, then the complexity isO(d((log²q/logd)ξ+d³+d²logdlog³q+ log⁴q+χlogq)).

Guralnick & L¨ubeck [22] proved that the proportion of elements of even order inSX(d, q) is at most 5/q, so a random search for an involution is not feasible for large fields. While the algorithm of Theorem 1.2 can be used to construct an involution, we describe an alternative which is much more efficient.

Theorem 1.3. LetX be a generating set of bounded cardinality forG = SX(d, q). There is a Las Vegas algorithm which constructs an involution ofG as an SLP inX. Ifq > 4, then the complexity isO(ξ+d³logdlog³q+ log⁴q+χlogq).

The corank of a matrix involutioniis the rank ofi−1. A modification of the algorithm of Theorem 1.2 yields an algorithm to construct involutions of large corank. While the theoretical complexity is as in Theorem 1.2, this algorithm is more efficient in practice.

Theorem 1.4. LetX be a generating set of bounded cardinality forG = SX(d, q). There is a Las Vegas algorithm with the same complexity as in Theorem1.2that constructs an involution in Gwith corankras an SLP inX, whereris as follows. IfGis linear or unitary, thenr=⌊d/2⌋.

IfGhas typeSporΩ⁺, thenr = 2⌊d/4⌋. IfGhas typeΩ⁻, then⌊d/4⌋ −1≤r ≤d/2.

Remark 1.5. The restriction to q > 4arises from Theorem 5.1, proved by Praeger, Seress &

Yalc¸ınkaya [40] under this assumption. However, in practice our algorithms also work with comparable efficiency forq∈ {2,4}.

gorithms (see [41, p. 17]) for classical groups. The complexity of these algorithms involves a factor of q. Using a discrete logarithm oracle and [18, 19], Brooksbank and Kantor [10–13]

demonstrate that the complexity of these algorithms can be made polynomial inlogq.

Brooksbank [9] devised Las Vegas algorithms to construct standard generators forSp(d, q), SU(d, q), and Ω^±(d, q) in their natural representations; subject to the existence of a discrete logarithm oracle, the complexity isO(d(ξ+d²logq(d+ logdlog³q+d²logq)) +χlogq). The algorithm of Celler & Leedham-Green [17] forSL(d, q)has complexityO(d⁴q). In all cases, the algorithms construct Steinberg generators for the group.

1.4. Other directions. We have generalised our algorithms to classical groups in arbitrary representations [14]. Costi [20] developed an efficient algorithm to write an element of a classical group, given in an arbitrary absolutely irreducible representation in defining characteristic, as an SLP in the standard generators. A black-box algorithm for this task was developed by Ambrose et al. [1].

2. Standard generators for classical groups

We now define the standard generators forG = SX(d, q), whered = 2nord = 2n+ 1. Let {e1, f1, . . . , en, fn}, or{e1, f1, . . . , en, fn, w}, be a hyperbolic basisBof the naturalG-module V, according as d is even or odd. All matrices of degree dare given with respect to B. A matrix of degree2kis given with respect to{e₁, f₁, . . . , e_k, f_k}; it represents an automorphism ofV which acts on{e₁, f₁, . . . , e_k, f_k}as the given matrix, and trivially on the remainingd− 2k basis elements. Permutation matrices are described by the corresponding permutation. To facilitate uniform exposition, we introduce trivial generators. If the dimension required to define a generator is greater than the dimension of the group, then the generator is assumed to be the identity. For an integerk ≥0let1_k be thek×kidentity matrix; if the degree is clear from the context, then we also write1 = 1_k. Analogously, we denote the zero matrix by0_kor0.

Definition 2.1. The standard generators of SX(d, q) are S(d, q,SX) = {s, t, δ, u, v, x, y} as defined in Table1, whereωis a specified primitive element of the underlying fieldF; if the type isSUthenF= GF(q²), otherwiseF= GF(q). ForΩ⁻(d, q), we choose a primitive elementγ ofGF(q²)so thatω=γ^(q+1).

The group generated byS(3,2,SU)as given in Table1has index 2 inSU(3,2), so we choose a different element fort.

The generator v is the cycle of SX(d, q); all other standard generators of SX(d, q) lie in SX(4, q). This observation is significant since we construct the standard generators by a recursion to classical groups of smaller degree.

Lemma 2.2. The standard copy ofSX(d, q)is generated byS(d, q,SX).

PROOF. The standard generators forSL,Sp,Ω⁺, andSU(2n, q)are independent of the charac- teristic, cf. [28,§3]. ForΩ⁻andSU(2n+ 1, q), we use a slight modification of the generating

sets for odd characteristic; the proof is similar.

CONSTRUCTIVERECOGNITIONOFCLASSICALGROUPS5

SL(2n, q) (e1, f1) ^{1 1}_{0 1 ω 0}

0ω−1

1_d (e1, . . . , en)(f1, . . . , fn) (e1, f1, e2, f2) 1_d

SL(2n+ 1, q) (e1, f1) ^{1 1}_{0 1 ω 0}

0ω−1

1d (e1, . . . , en)(f1, . . . , fn, w) (e1, f1, e2, f2) 1d

Sp(2n, q) (e1, f1) ^{1 1}_{0 1 ω 0}

0ω−1

(e1, e2)(f1, f2) (e1, . . . , en)(f1, . . . , fn)

1 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1

1d

SU(2n, q) (e1, f1) ^{1 1}_{0 1 ω 0}

0ω−1

q+1

(e1, e2)(f1, f2) (e1, . . . , en)(f1, . . . , fn)

1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1

^{ω 0 0 0}

0ω−q 0 0 0 0 ω−1

0

0 0 0 ωq

!

SU(2n+ 1, q) (e1, f1) ^{1 1}_{0 1} (d, q)6= (3,2)

_{ω 0}

0ω−1

q+1

(e1, e2)(f1, f2) (e1, . . . , en)(f1, . . . , fn)

1d−3 1η1 0 1 0 0 1 1

!

η=Tr(ω,GF(q))⁻¹ω





1d−3

ω 0 0 0ω−1 0 0 0 ωq−1





Ω⁺(2n, q) (e1, f2)(e2, f1)

1 0 0 1 0 1 0 0 0 1 1 0 0 0 0 1

^{ω 0 0 0}

0ω−1 0 0

0 0 ω 0

0 0 0ω−1

!

(e1, e2)(f1, f2) (e1, . . . , en)(f1, . . . , fn)

1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 1

^{ω 0 0 0}

0ω−1 0 0 0 0 ω−1 0

0 0 0 ω

!

Ω⁻(2n, q)





1d−4 0 1 0 0 1 0 0 0 0 0 1 0 0 0η1





γ∈GF(q²)primitive ω=γ^q+1

η=γ+γ^q





1d−4 1 1 1 0 0 1 0 0 0 0 1 0 0η0 1









1d−4 ω 0 0 0 0ω−1 0 0 0 0 1a 0 0 b c





a=γ⁻¹+γ^−q b=γ+γ^q

c=γ^−q+1+γ^q−1+ 1

(e1, e2)(f1, f2) ifn >2

(e1, . . . , en−1)(f1, . . . , fn−1) 1d 1d

TABLE1. Standard generators for classical groups in even characteristic

3. General approach and structure of this paper

We outline our strategy to construct the standard generators S forG = SX(d, q) = hXi. Ifd is “small”, thenGis a base case and we use specialised algorithms to solve the problem. These define a single algorithm, BaseCase, described in Section 10. Here and later a “⋆” within a matrix denotes a submatrix that is not further specified, and whose dimensions are implied by the context.

Definition 3.1. SX(d, q)is a base case if either d ≤ 6, or it is one of the following individual groups: SL(8,2),SU(7,2),SU(9,2),Ω⁻(8,4),Ω⁻(10,4), orSp(d,2)withd∈ {8,10,12}, or Ω^±(d,2)withd∈ {4,6,8,10,12,14}.

If G is not a base case, then we proceed as follows. The first step is to find a naturally embedded subgroup H ∼= SX(m, q) of G where m lies in a prescribed range, for example, m∈[d/3,2d/3]. IfGhas typeSLorSU, thenmis even andSX(m, q)has the same type asG;

otherwiseSX(m, q)has typeΩ⁺andmis a multiple of 4. We describeFirstSX, the algorithm to constructH, in Section 5. Via a base change, we may assume that

H=

SX(m,q) 0 0 1_d−m

≤G.

By recursion, we construct a base change matrixb= diag(⋆,1_d−m), the standard generators S_H of SX(m, q) in H^b, and a certain involution i_H ∈ H^b of corank m/2; all elements are described by SLPs inX. For simplicity, letb = 1_din the following. In the centraliserCG(iH) we find

K =₁

m 0

0 SX(d−m,q)

≤G

whereSX(d−m, q)has the same type asG. We describeSecondSX, the algorithm to construct K, in Section 8. By another recursion, we construct a base change matrixc = diag(1_m, ⋆)and the standard generatorsS_KofSX(d−m, q)inK^c. Again, letc= 1_dfor simplicity.

With the exception of the cyclev ofG, all standard generators ofGlie in S_H ∪ S_K. The missing generator is constructed as follows. First, the elements of S_H ∪ S_K are used to write down a specific involutioni ∈ G. Second, inCG(i) a certain subgroupT of degree 4 (degree 8 ifG is symplectic or orthogonal) is constructed. Finally, a glue elementg is found inT: if v_K ∈ S_K andv_H ∈ S_H are the cycles inKandH, respectively, thenv=v_Kgv_H is the cycle of G. To perform this task, we introduce the algorithmGlueCyclesin Section 9.

We now summarise the main algorithm,StandardGenerators, and discuss it in detail in Section 11.

1) IfGis a base case, then applyBaseCase, otherwise:

2) Construct the subgroupHwithFirstSX.

3) Recursively applyStandardGeneratorstoH.

4) Construct the subgroupKwithSecondSX.

5) Recursively applyStandardGeneratorstoK.

6) Find the glue element and combine recursive solutions withGlueCycles.

The main difference between this algorithm and that for odd characteristic [28] is the con- struction of the two subgroups for the recursion. In odd characteristic, these subgroups can be constructed simultaneously in the centraliser of an involution, and this involution is found by a random search. In even characteristic, we constructH using a different technique, and then constructKas a subgroup of the centraliser inGof an involution of large corank inH.

In Section 12 we present two algorithms to construct involutions. The algorithm to construct an involution of large corank is similar toStandardGenerators, but avoids the gluing of the cycles. Our algorithm to construct an involution of small corank uses recursion to construct H ∼= SX(m, q)for some smallm, usuallym ≤6, as a naturally embedded subgroup ofG. We then apply specialised algorithms to construct an involution inH.

4. Algorithmic preliminaries

If f andg are real valued functions, defined on all sufficiently large integers, then f = O(g) means|f(n)|< c|g(n)|for some positive constantcand all sufficiently largen.

A Monte Carlo algorithm is a randomised algorithm that always terminates, but may return a wrong answer with probability less than any specified value. A Las Vegas algorithm is a ran- domised algorithm that never returns an incorrect answer, but may report failure with probability less than any specified value.

Babai [3] presented a Monte Carlo algorithm to construct, in polynomial time, independent nearly uniformly distributed random elements of a finite group. An alternative is the product replacement algorithm of Celler et al. [16], which runs in polynomial time by a result of [39].

For a discussion of both algorithms we refer to [41, pp. 26–30].

Our algorithms usually search for elements ofGhaving a specified property. If1/kis a lower bound for the proportion of such elements inG, then we can readily prescribe the probability of failure of the corresponding algorithm. Namely, to find such an element by random search with a probability of failure less than a givenǫ∈(0,1)it suffices to choose (with replacement) a sample of uniformly distributed random elements inGof size at least⌈−log_e(ǫ)k⌉. We do not include such factors as part of each theorem.

Often it is necessary to investigate the order ofg ∈ GL(d, q), which, due to problems with integer factorisation, cannot be determined in polynomial time. We can, however, determine its pseudo-order, a good multiplicative upper bound for |g|, and the exact power of any specified prime that divides|g|, using a Las Vegas algorithm with complexityO(d³logd+d²logdlogq).

A Las Vegas algorithm with the same complexity allows us to compute large powersgⁿ where 0 ≤ n < q^d. Multiplication and division operations for polynomials of degree doverGF(q) can be performed deterministically with complexityO(dlogd). Using a Las Vegas algorithm, such a polynomial can be factored into its irreducible factors with complexityO(d²logdlogq).

The characteristic and minimum polynomials ofg ∈GL(d, q)can be computed by a Las Vegas algorithm with complexityO(d³logd). We refer to [28,§2 & 10] for more details and references.

If a matrix group acts absolutely irreducibly on its natural module, then the form it preserves (up to scalar multiples) can be determined with complexityO(d³), see [23,§7.5.4]. Conjugating SX(d, q)to its standard copy amounts to finding a hyperbolic basis with respect to the given form;

this can be done with complexityO(d³+d²log²q), see [33, Theorem 1.1].

The following theorem, proved in [5, Corollary 4.2], implies that two random non-scalar g, h ∈ SX(d, q) satisfyg^|h| 6= 1with probability at least 1/2d. Recall that an element isp- regular if its order is not divisible byp.

Theorem 4.1. LetGbe a finite simple classical group acting naturally on a projective space of dimensiond−1, and letpbe a prime. The proportion ofp-regular elements inGis at least1/2d.

We also use the following result on random generation proved in [25].

Lemma 4.2. Let G = SX(d, q) be perfect. An O(1) random search in G yields a bounded generating setXforGsuch that{x² |x∈X}generatesG.

5. Constructing the first subgroup

In this section, we assume thatG= SX(d, q) =hXiis not a base case. The standard generators ofGare constructed via a recursion to two smaller subgroups of classical type. Modulo a base change with matrixb, these subgroups are

H=

SX(m,q) 0 0 1d−m

≤G^b and K=

1m 0

0 SX(d−m,q)

≤G^b,

whereSX(d−m, q)has the same type asG. IfGis linear or unitary, then so isSX(m, q)and mis even; otherwise,SX(m, q)has typeΩ⁺andmis divisible by 4. In each case,mis usually required to lie betweend/3and2d/3.

The construction ofKis considered in Section 8. Here we describe the algorithmFirstSX used to construct H. We first outline the steps and then discuss them in the subsequent sub- sections. In the remainder of this section, unless explicitly stated, the characteristic p of the underlying fieldFcan be either even or odd. Recall that ifg∈Ghas order prime toq, thengis semisimple.

(1) Find a semisimpleg ∈ Gwith 1-eigenspaceE_g of dimensiond−l ∈ [2d/3,5d/6](with some variation for small d) such thatg acts irreducibly on a complement to E_g in V, the naturalG-module. IfGis orthogonal or symplectic, then require thatlis even.

(2) Construct a random conjugateg^h, forh∈G, such that the intersectionEof the1-eigenspaces ofgandg^h has smallest possible dimension (that is,d−2l) and the images ofg−1and g^h−1span a complementI toE. ThenH =hg, g^hileavesE andI invariant, and (in the non-linear case)EandI are non-degenerate subspaces.

Note that the dimension ofI ism= 2l; ifGis orthogonal or symplectic, thenmis divisible by 4. LetH˜ = H|_I be the group generated by the restrictions of g andg^h toI. Lemmas 5.9 and 5.10 show the following: H˜ ≤SX(m, q)(acting onI); ifGis orthogonal, thenSX(m, q)is orthogonal (of possibly different type); ifG= Sp(d, q)withqeven, thenSX(m, q)is orthogonal;

otherwiseSX(m, q)has the same type asG.

In Section 5.1 we describe the construction of the elements g in Step (1). Observe that g|_I ∈SX(m, q)has a 1-eigenspace of dimensionl=m/2and acts irreducibly on a complement inI. Our construction ensures that the order ofg|_I is divisible by a certain Zsigmondy prime (see Definition 5.3).

As we establish in Lemma5.9, the conjugacy class ofg|_I inSX(m, q)is determined by its eigenvalues in its action on I; thereforeg|I andg^h|I are conjugate inSX(m, q). Thusg^h|I is random among all conjugates (g|_I)^c of g|_I, for c ∈ SX(m, q), such that the 1-eigenspaces of (g|_I)^c andg|_I intersect trivially. In this situation, we can apply the following result of Praeger, Seress & Yalc¸ınkaya [40].

Theorem 5.1. Letq > 4. There is an absolute constantκ >0such that the following holds: if H˜ ≤SX(m, q)is as defined above, thenH˜ = SX(m, q)with probability at leastκ.

Our investigations suggest that this theorem also holds forq ≤4.

IfGis orthogonal or symplectic withqeven, thenH˜ = SX(m, q)is orthogonal, see Lemma 5.10. IfH˜ has+type, then we can readily construct the standard generators ofGfrom the stan- dard generators constructed forH and for the second subgroupK ≤G. To simplify exposition, we consider only the case thatH˜ is of+type. Theoretically, this is justified by the following third step ofFirstSX; it does not change the complexity of our main algorithm.

(3) Ifq is even andH ∼= SX(m, q)is orthogonal of−type, then we constructively recognise Ω⁻(m, q), and so obtainΩ⁺(m−4, q)as a naturally embedded subgroup ofH(andG); we

returnΩ⁺(m−4, q). Ifm ≤ 8, then we apply the algorithm of [9] to findΩ⁺(4, q) as a naturally embedded subgroup.

Ifqis even andH˜ is orthogonal, then our investigations suggest that the probability thatH˜ is of+type is approximately1/2(or1/3ifq = 2). In practice, we realise Step (3) by repeatedly constructing subgroupsHuntilH˜ is of+type.

5.1. Finding elements with large 1-eigenspace. We prove thatO(1)random elements in Gsuffice, in Step (1), to find one that powers up to a desired element. Forg∈G, denote byE_g the1-eigenspace ofg, and byIg the image ofg−1. Recall that a(q, l)-Zsigmondy primer is one that dividesq^l−1but noq^j −1forj < l. If so, thenqhas orderlmodulor, sor ≥l+ 1.

Zsigmondy primes exist, except for(q, l) = (2,6)and(q,2)withqa Mersenne prime, see [35].

LetF¯be an algebraic closure of the underlying fieldFofG, and define the map Φ : ¯F→F,¯ a7→a^εq,

whereε=−1in caseSUandε= 1in all other cases. The multiset of eigenvalues oft∈ Gin F¯ is invariant underΦ, sinceΦpreserves the characteristic polynomial oft. Letλ(t) ⊢dbe the partition ofddescribing the cycle lengths ofΦacting on this multiset. IfGis of typeSU, andl is even, thenl^′′ := landl^′ := l/2; ifGis of typeSU, andlis odd, thenl^′′ := 2landl^′ := l; in all other casesl^′′=l^′ :=l.

Definition 5.2. Forl∈ {2, . . . , d/2−1}

P_l(G) ={g∈G|gis semisimple,gacts irreducibly onI_g, and dim(E_g) =d−l}.

Definition 5.3. LetP˜_l(G)be the set of allt∈Gwith the following properties:lappears exactly once inλ(t);l^′does not divide any other entry ofλ(t); and there is a(q, l^′′)-Zsigmondy primer dividing|t|.

Lemma 5.4. Elements ofP˜_l(G)power up to elements ofP_l(G).

PROOF. Ifa ∈ ¯Fis an eigenvalue oft ∈ Gcorresponding to a cycle lengtheinλ(t), then the order ofadivides(εq)^e−1. It is easy to see that a(q, l^′′)-Zsigmondy prime does not divide|a|if l^′ ∤e. Lett∈P˜_l(G)with(q, l^′′)-Zsigmondy primerdividing|t|. Lete₁, . . . , e_kbe the entries of λ(t)not equal tol, and letb=|((ǫq)^e1−1)· · ·((ǫq)^ek−1)|. Thent^bhasd−leigenvalues equal to1, andleigenvalues of order divisible byr. To construct a semisimple element with the same properties, we powert^b by p^j, wherep^j is the largest power ofp that divides|t|; in particular, j = 0ifthas pairwise different eigenvalues. The non-trivial eigenvalues of this powergoftlie in a field extension ofFof degree preciselyl^′′, sogacts irreducibly onIg. Lemma 5.5. a) If lis odd andGhas typeSporΩ^±, thenP˜_l(G) is empty. In all other cases the following holds: For every constantα∈(0,1/2)there exists a constantc >0such that for every d > 1, every prime powerq, and every integerl ∈ [αd, d/2)for which (q, l^′′)- Zsigmondy primes exist, the proportion|P˜_l(G)|/|G|is greater thanc/l.

b) There exists a constantc^′ >0such that, for everyd > 5and every prime powerq, ifG = SX(d, q)andP =S

lP˜_l(G), wherelruns over all integers in[d/6, d/3], then|P|/|G|> c^′. PROOF. a) The proof is based on [31]. First,P˜_l(G)is obviously closed under conjugation, and it contains an element ofGif and only if it contains its semisimple part. Therefore the proportion

|P˜_l(G)|/|G|can be determined as in [31, Lemma 2.3]. This reduces the estimate to considering the proportion of elements inP˜_l(G)in maximal tori ofG, and to counting elements in the Weyl

group ofGcorresponding to tori with many elements inP˜_l(G). The conjugacy classes of maxi- mal tori inGare parametrised either by partitions ofdin cases SL and SU, or by signed partitions of⌊d/2⌋. A maximal torus is in all cases a subgroup of a direct product of cyclic groups of order q^j −1 orq^j + 1, where j corresponds to an entry in the partition. For a detailed description see [31,§3].

Consider first the typesSLandSU. For2≤l < d/2, we consider partitions with one entry equal to l, and all other entries not divisible by l^′. From the description of the structure of the corresponding maximal tori, it is clear that these contain elements ofP˜_l(G), and the proportion of such elements is at least1−1/r ≥ 2/3for every(q, l^′′)-Zsigmondy primer. Let W ∼=S_d be the Weyl group, the symmetric group of degreed. For the proportion of elements inW whose cycle type is one of these partitions, a lower bound is given by [31, Lemma 4.2 a), b)]. Using this, and the estimatesl≥αdandd^1/d<3/2, part a) follows forSLandSU.

The remaining types are dealt with similarly. The explicit description of maximal tori shows that cycles induced by Φ on the eigenvalues of t ∈ G come either in pairs or they have even length. This establishes the last statement of a), and we now assume that l is even. Here we consider maximal tori corresponding to elements ofW with a negative cycle of lengthl/2such thatl/2does not divide any other cycle length. It follows, from the description of the structure of these tori, that they contain elements inP˜_l(G), and the proportion of such elements is at least 2/3. The estimate for the proportion of elements in the Weyl group that are considered is reduced to the caseS_⌊d/2⌋using [31, Lemma 4.2 c), d)].

b) This follows from a): for largedthere are at leastd/12−1 differentl to consider and for d > 5 there is always at least one appropriate l, and every element ofG can lie in at most 5 differentP˜_l(G): there can be at most5cycles of different lengths at leastd/6.

Let P andc be as defined in Lemma 5.5 b). For small rank, say d < 60, one can easily compute quite accurate values for the constantc, using [31, Lemma 2.3]. IfGhas typeSLorSU, then ford≤20the proportion of elements inP (if not empty) lies in[0.18,0.4], and for largerd in[0.4,0.5]. For the other types, the proportion is about half as large, which is as expected from the proof above.

Remark 5.6. If t ∈ G, where G has type other than SU, then the cycle lengths induced by Φ on the multiset of eigenvalues of t are the degrees of the irreducible factors over F of the characteristic polynomial oft. Now letGhave typeSU. Iff is the minimum polynomial overF of somea∈F¯^×, then we denote byf˜the minimum polynomial ofa^−q. To computef˜fromf: raise the coefficients to theq-th power, reverse coefficients, and normalise. IfΦinduces a cycle of odd lengthlon the eigenvalues oft, then the characteristic polynomial oftcontains an irreducible factorf = ˜f of degreeloverFwhose zeroes are the elements of the cycle. IfΦinduces a cycle of even lengthl, its elements are the zeroes of two irreducible factorsf andf˜6=f of degreel/2 overF. Therefore, in all cases, elements inP are easy to detect by computing and factorising characteristic polynomials.

Remark 5.7. Ifdis small, thenP may be empty. We usually solve this problem by extending the range forlin the definition of P to[2, d/2). Ford ∈ {3,4}we search for elements gthat have one eigenvalue with multiplicity1, and another with multiplicityd−1. We take the derived subgroup ofhg, g^hiasH. Such elementsgare easy to find. For example, in case SL, ift ∈ G satisfiesλ(t) = (1, d−1), theng =t^b withb = (q^d−1−1)/(q−1)is a desired element, with probability1−1/q.

We summarise the resulting algorithmFindElement: it takes as input the generating set XofGand returnsg∈P˜_l(G)for somel∈[d/6, d/3](with some variation for smalld).

(i) Construct random t ∈ G, factorise its characteristic polynomial, and compute λ(t) as in Remark 5.6, so determiningl.

(ii) Ift∈P˜_l(G), then powertup tog∈P_l(G)and returng, otherwise go back to (i).

Lemma 5.5 shows that it suffices to selectO(1)random elementstin order to constructg.

This, and the results cited in Section 4, shows the algorithm is Las Vegas and has complexity O(ξ+d³logd+d²logdlogq).

5.2. Constructing the subgroupH. We now show that it is easy to find a conjugate ofg∈ P˜l(G)in sufficiently general position. Recall thatV is the naturalG-module,Eg = ker(g−1), andI_g = im (g−1).

Lemma 5.8. Letg ∈P_l(G)and letT be the set ofh ∈ Gsuch thatdim(E_g∩E_gh) =d−2l (the smallest possible value) andV = (E_g∩E_gh)⊕I_g⊕I_gh. There exists an absolute constant c >0, independent ofland the type ofG, such that|T|/|G|> c.

PROOF. We give a detailed proof only forGof typeSL; the proportion|T|/|G|is larger ifGis not of this type.

Since gis semisimple,V = E_g ⊕I_g. We choose an ordered basis ofV such that the first d−lvectors generateE_g, and the lastlvectors generateI_g. We estimate the cardinality ofT by counting images of these basis vectors under a suitable linear transformationh∈T. We start by mapping the firstlbasis vectors such that their images, together withEg, span the whole space.

This ensures thatE_g∩E_ghhas minimal dimension.

For1 ≤j ≤l, we map thej-th basis vector to a vector outside the span of the union ofEg

with the set of previously chosen images; there areq^d−q^d−l+j−1possible choices. Then we map the remainingd−2lbasis vectors ofEgto arbitrary vectors outside the span of the already chosen images. Ifl+ 1≤j≤d−l, then there areq^d−q^j−1 choices for thej-th basis vector. Finally, we map the basis vectors ofI_gso that their images span a complement to(E_g∩E_gh)⊕I_g. Thus the image of thej-th basis vector ford−l+ 1≤j≤dmust be outside the span of the previously chosenj−1images, and outside the span of the union of(E_g∩E_gh)⊕I_gwith the set of images of the basis vectors indexed byd−l+ 1toj−1. These two subspaces of dimensionj−1> d/2 have an intersection of dimension at least2j−2−d. This yields at leastq^d−2q^j−1+q^2j−2−d possible images (the last one divided byq−1to get an element with determinant1).

Comparing with|G|= (Q_d

j=1(q^d−q^j−1))/(q−1)we get a lower bound

|T|/|G| ≥Yl j=1

q^d−q^d−l+j−1 q^d−q^j−1 ·Yd

j=d−l+1

q^d−2q^j−1+q^2j−2−d q^d−q^j−1 . For the first factor of the product, observe that

Yl j=1

1−q^d−l+j−1−q^j−1 q^d−q^j−1

>Yl

j=1 1− q^d

q^d−q^j−1 · 1

q

l−j+1!

>Yl

k=1 1−4

3 · 1

q k!

. For fixedq, this last expression converges to some positive constant asl→ ∞(because the geometric seriesP

j1/q^jconverges). For the second factor, we find a positive lower bound with a similar estimate; the critical term is the last, but it is easily checked that it is at least1/2.

Evaluations of the formulae show thatc, forq = 2or4, is bounded below by0.08and0.47 respectively. Our investigations suggest that forq = 2the proportion|T|/|G|is about0.25.

Lemma 5.9. Letg∈P_l(G), and leth∈Tas in Lemma5.8.

a) E =Eg∩EghandI =Ig⊕Ighare invariant underhg, g^hi.

b) IfGpreserves some form, thenEandIare mutually orthogonal, and non-degenerate spaces.

c) If G is orthogonal, then E and I are non-degenerate quadratic spaces, possibly of type different to that ofG.

d) IfGis not an orthogonal group in even dimension, then the conjugacy class of a semisimple element inGis determined by its eigenvalues inF¯(with multiplicities). In the remaining case this is true if and only if the element has an eigenvalue 1, otherwise there are two semisimple classes whose elements have the same eigenvalues.

e) The restrictionsg|_I andg^h|_I are conjugate within the group preserving the form specified in b)andc).

PROOF. a) Clearly,E_g∩E_ghandI_g⊕I_ghare fixed by each ofgandg^h; for example, ifv∈I_g, thenvg^h =v+v(g^h−1)∈Ig⊕Igh.

b) SupposeGpreserves a formβ(·,·). Letv =w(g−1)∈Ig, andw^′ ∈Eg. Thenβ(v, w^′) = β(wg, w^′)−β(w, w^′) = β(w, w^′g⁻¹)−β(w, w^′) = 0, thusI_g andE_g are orthogonal. Hence E_g ∩E_ghis orthogonal toI_g⊕I_gh. SinceV is the direct sum of these spaces,I_g ⊕I_ghis the orthogonal complement ofE_g∩E_gh. Thus the form restricted to each ofE_g∩E_ghandI_g⊕I_gh is non-degenerate.

c) LetQbe the quadratic form preserved byGwith associated bilinear formF =Q+Q^⊺. By part a), the naturalG-module decomposes intoV =E ⊥I, and with respect to a suitable basis, the matrixF has block diagonal form; we may also assume thatQis an upper triangular block matrix. Note thatvkQk^⊺v^⊺= vQv^⊺for everyv ∈V andk ∈ hg, g^hi. Since the 1-eigenspaces ofg|_I andg^h|_I intersect trivially,Qis a block diagonal matrix.

d) The semisimple conjugacy classes ofGare parametrised by orbits of the Weyl group on ele- ments of a maximal torus, see [15, Propositions 3.7.2 & 3.7.3]; in characteristic 2 the centralisers of semisimple elements are connected, but the proof of [15, Proposition 3.7.3] remains correct even if the group is not of simply-connected type. An explicit description of maximal tori in the natural representation and the Weyl group action is given in [31, Section 3]; our claim follows easily from that description.

e) Since both restrictions have 1 as an eigenvalue, the result follows from d).

Letg ∈ P_l(G), andm = 2l. By Lemma 5.8 and Theorem 5.1, the construction of O(1) random elements is sufficient to find h ∈ Gsuch thatH = hg, g^hiis isomorphic toSX(m, q).

We can verify the latter using the one-sided Monte Carlo recognition algorithm of [35]; this has complexityO(ξ+d³logdlog³q).

We now suppose thatG = Sp(d, q) andq is even. The next lemma shows that in this case H preserves a quadratic form, henceH ∼= SX(m, q)is orthogonal by Theorem 5.1. Recall that gacts irreducibly on the orthogonal complementIgof its 1-eigenspaceEg, andIg∩Igh={0}.

Sincegis semisimple, it has odd order.

Lemma 5.10. There is a quadratic form onI_g⊕I_ghpreserved bygandg^h.

PROOF. WriteU = I_g. Let β be a non-degenerate bilinear form left invariant bySp(d, q); so β is unique up to multiplication by a non-zero scalar. The spaceU, together with the restriction γ = β|_U×U, is a symplectic space, and every semisimple element ofSp(U) lies in a maximal torus of an orthogonal group onU. Thus, there exists ag-invariant quadratic formB₁onU which supportsγ: namely,B1is ag-invariant quadratic form withB1(u+v) =B1(u)+B1(v)+γ(u, v)

for allu, v ∈ U. Conjugating B₁ byh defines ag^h-invariant quadratic formB₂ onU h. Now define a quadratic formBonU⊕U hbyB(v1+v2) =B1(v1) +B2(v2) +β(v1, v2)forv1∈U andv₂ ∈U h. We prove that this form is invariant under the action ofg²; sinceghas odd order, this shows thatB isg-invariant. SinceU isg-invariant, it suffices to prove thatB(vg²) =B(v) for allv∈U h. Forv∈V definef(v) =vg−v. SincegcentralisesV /U it follows thatf takes values inU, and hence, by restriction, defines a linear map fromU htoU. Letv ∈U h. It follows fromvg² =f(v)(g+ 1) +vand theg-invariance ofB₁that

B(vg²) = B1(f(v)(g+ 1)) +B2(v) +β(f(v)(g+ 1), v)

= β(f(v)g, f(v)) +B₂(v) +β(f(v)(g+ 1), v),

so it suffices to prove thatβ(f(v)g, f(v)) =β(f(v)(g+ 1), v). But this follows from β(v, f(v)) = β(v, vg) =β(vg, vg²)

= β(vg, v(g²−1) +v)

= β(vg, f(v)(g+ 1) +v)

= β(v+f(v), f(v)(g+ 1) +v).

SimilarlyB is preserved byg^h.

If q is even and H is orthogonal, then we apply Step (3) to ensure that H is of + type.

AlgorithmFirstSXreturnsH∼= SX(m, q), a base change matrix reflecting the decomposition V =I_g⊕I_gh⊕(E_g∩E_gh), andm. Observe thatm∈[d/3,2d/3]with variations for smalld.

Hence, our previous discussion proves the following.

Lemma 5.11. AlgorithmFirstSXis correct and Las Vegas; ifq > 4, then it has complexity O(ξ+d³logdlog³q+ log⁴q).

6. Centralisers of involutions

We consider G = SX(d, q) with d ≥ 4, and d ≥ 8 ifG is orthogonal. An involution iinG is good inGif either Gis linear or unitary, or ihas even corank and vF i^⊺v^⊺ = 0for allv in the natural G-module, whereF is the alternating form preserved by G. (Recall thatΩ^±(d, q) preserves the alternating form supported by the quadratic form.) Aschbacher & Seitz [2] describe the centraliser of an involution in Chevalley groups over fields of even size. (Our good involutions are those of typec_ras defined in [2].) The next theorem follows from [2, (4.2), (4.3), (6.2), (7.6), (7.7), (7.9), (8.5), (8.6), (8.10), (8.12)].

Theorem 6.1. Leti∈G= SX(d, q)be a good involution of corankr≤d/2and letFbe the un- derlying field ofG. There exists a base change matrixc∈GL(d,F)such thati^c =

₁

r 0 1r

0 1d−2r 0 0 0 1r

and the elements ofCG^c(i^c)have upper block triangular form with diagonal blocksa, b, a, of de- greer,d−2r, andr, respectively. Consider the homomorphism

ψ:C_G^c(i^c)→GL(r,F)×GL(d−2r,F), _{a ⋆ ⋆}

0b ⋆ 0 0a

7→(a, b).

If G is linear, unitary, or symplectic, then the image ofψ contains SX(r, q) ×SX(d−2r, q) with both factors of the same type asG. Otherwise, in the orthogonal case, the image contains Sp(r, q)^′×SX(d−2r, q), whereSX(d−2r, q)has the same type asG.

We calli^∗:=i^cthe standard form ofi. The centraliser of a good involutioni∈Gin standard form has the structure given in Theorem 6.1. The following easy observation is used in Sections 11 and 12.

Lemma 6.2. LetG= SX(d, q)and H =

SX(m,q) 0 0 1d−m

≤G and K =

1m 0

0 SX(d−m,q)

≤G.

If i_H ∈ SX(m, q) andi_K ∈ SX(d−m, q)are good involutions, thendiag(i_H, i_K)is a good involution inG.

The centraliserCG(i)of an involutioni∈Gcan be constructed using an algorithm of Bray [7]. Ifgis an arbitrary element ofG, then[i, g]either has odd order2k+ 1, in which caseg[i, g]^k commutes withi, or has even order2k, in which case both[i, g]^kand[i, g⁻¹]^kcommute withi.

Ifg is random among the elements ofGfor which[i, g]has odd order, theng[i, g]^k is random inC_G(i), see [36, Theorem 11]. Such an elementg[i, g]^kis a Bray generator ofC_G(i). Bray &

Wilson [8] prove the following.

Theorem 6.3. LetG= SX(d, q)and leti∈Gbe an involution. There is a constantc >0such that the proportion ofg∈Gwith[i, g]of odd order is bounded below byc/logd.

The equivalent theorem for odd characteristic is proved in [36]. Our investigations suggest that the proportion for even characteristic is greater than some absolute positive constant independent of the rank.

Leti∈Gbe a good involution in standard form. A subgroupC ofC_G(i)is sufficient if its imageψ(C)under the projection in Theorem 6.1 is the same asψ(C_G(i)).

Theorem 6.4. Letibe a good involution inG= SX(d, q)in standard form. A bounded generat- ing set for a sufficient subgroup ofC_G(i)can be constructed using a Monte Carlo algorithm with complexityO(logd(ξ+d³logd+d²logdlogq)).

PROOF. Theorem 6.3 shows that it suffices to considerO(logd)random elements to construct a random element of C_G(i). The results cited in Section 4 imply that the test for each element – to decide if it has even order and to compute a power – requiresO(d³logd+d²logdlogq)field operations.

LetKbe the image of the projection ofψ(CG(i))into one of the direct factors of the range of ψ, that is, intoGL(r,F)orGL(d−2r,F). The probability that two random elements of a cyclic group C generate C isQ

(1− _p¹2) > _π⁶2, where the product is over all primes pdividing |C|.

Hence we obtain elements whose image in the cyclic quotientQ:=K/K^′generatesQ, so we can construct a generator ofQ. By multiplying a random element ofC_G(i)by an appropriate power of the preimage of this generator, we obtain random elements of K^′. Kantor & Lubotzky [25]

prove that a bounded number of random elements generateK^′. 6.1. An involution that is not good. We now consider a certain involution of corank4in a group of type SpandΩ^±. In contrast to our previous discussion, this involution is not good.

Its centraliser is, up to conjugacy, described in [2]. However, in Section 9 we need explicit knowledge of the centraliser structure with respect to a particular hyperbolic basis.

LetF1be the matrix of a non-degenerate alternating form of rankd−8, and let F =

04 0 F2

0 F1 0 F2 0 04

with F2 =

_{0 0 0 1}

0 0 1 0 0 1 0 0 1 0 0 1

.

ThenF is the matrix of a non-degenerate alternating form. LetQ₁ be the matrix of a quadratic form of+or−type supportingF1, that is,Q1+Q^⊺₁ =F1, and define

Q= _Q

2 0 F2

0 Q1 0 0 0 Q3

whereQ₂ = diag(0,1,1,1)andQ₃ = diag(0,0,0,1). NowQis a matrix of a quadratic form supporting F, of the same type as Q1. Let G1 = Sp(d, q) andG2 = Ω^±(d, q) be the groups preserving F and Q, respectively. In the remainder of this section we determineC_G1(i) and CG2(i), where

i= ₁

4 0 14

0 1d−8 0 0 0 14

(6.1)

is a non-good involution of corank 4 contained inG1andG2. Lemma 6.5. Let∆≤SL(4, q)be the subgroup of elements

δ =

_{1 0 0 0}

u1 a1 a2 0 u2 a3 a4 0 v w1 w2 1

∈SL(4, q) where (^u_u¹₂) = (^a_a²₄ ^a_a¹₃) (^w_w¹₂).

Then

CG1(i) =n

g=_{δ ⋆ ⋆}

0x ⋆ 0 0δ

|δ∈∆, x∈Sp(d−8, q)o ,

whereSp(d−8, q)preserves the formF₁, and the entries⋆are subject to the sole constraint that glies inG₁. (Such entries may be found for every choice ofδ andx.) The same holds whenG₁ is replaced byG2; herex∈Ω^±(d−8, q)is required to preserve the associated quadratic form Q₁.

PROOF. The centraliser ofiinGL(d, q)is the set of matrices of the same shape as the matricesg in the lemma, except that∆is replaced byGL(d,4), andxmay be any element ofGL(d−8, q), and there is no restriction on the entries marked⋆. Thus we need only consider the condition that a matrix of this shape should lie inG₁orG₂.

Taking G₁ first, and considering the copy of δ in the bottom right corner, it is easy to see that a necessary condition for g to lie in G1 is for δ to lie in ∆. Conversely, if δ ∈ ∆ and x∈Sp(d−8, q)thendiag(δ, x, δ)∈G₁, as is straightforward to check.

Now considerCG2(i)and letδ∈∆andx∈Ω^±(d−8, q)as in the statement of the lemma.

Then

_δ0δ′

0x 0 0 0 δ

∈CG2(i) if δ^′ =

_{0 0 0 0}

0a2+a3 a1+a4 0 0a1+a4 a2+a3 0 0 w2 w1 0

.

A routine calculation proves the following.

Lemma 6.6.

g= ₁

4 0 y

0 1d−8 0 0 0 I4

∈G₁ if and only ifyhas the form

y11 y12 y13 y14

y21 y22 y23 y13

y31 y32 y22 y12

y41y31+y12y21+y13y11+y14

,

andg∈G₂if, in addition,y₁₄= 0andy₁₃² =y₂₃andy²₁₂=y₃₂andy₁₁² +y₄₁+y₁₁= 0.

Forj∈ {1,2}letAj be the subgroup ofGjconsisting of matricesgas in Lemma 6.6. Note that the set of elements

_δ0δ′

0x 0 0 0 δ

∈CG_j(i) with δ =

_{1 0 0 0}

0a1a2 0 0a3a4 0 0 0 0 1

∈∆

and δ^′ = 0 if j = 1, forms a group, S_j ≤ C_Gj(i), isomorphic to SL(2, q). AlsoS_j acts by conjugation onA_j; or, equivalently, on the corresponding additive group of matrices of the form y, also by conjugation.

Remark 6.7. AsS1-module,A1 is isomorphic to the direct sum of three copies ofGF(q)with trivialS₁-action, twoGF(q)-modules each of dimension 2 with naturalSL(2, q)-action, and one copy of sl(2, q), the group of 2×2 matrices overGF(q) of trace zero. AsS2-module, A2 is