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 for*Gwith 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 in*G 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_{1}, . . . , M_{n}) the block diagonal matrix with
blocksM_{1}, . . . , 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^{2})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^{2}), then the standard quadratic form
of−type isdiag((^{0 1}_{0 0}), . . . ,(^{0 1}_{0 0}), ^{1}_{0}^{a}_{b}

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

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 if*SX(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^{2}), then the oracle is required
forGF(q^{2}), 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. Let*X

*be a generating set of bounded cardinality for*G = SX(d, q). There is a

*Las Vegas algorithm that constructs the standard generators for*G

*as SLPs in*X. Ifq >4, then

*the complexity is*O(d((log

^{2}q/logd)ξ+d

^{3}+d

^{2}logdlog

^{3}q+ log

^{4}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. Let*X

*be a generating set of bounded cardinality for*G = SX(d, q). There is a

*Las Vegas algorithm which constructs an involution of*G

*as an SLP in*X. Ifq > 4, then the

*complexity is*O(ξ+d

^{3}logdlog

^{3}q+ log

^{4}q+χlogq).

*The corank of a matrix involution*iis 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. Let*X

*be a generating set of bounded cardinality for*G = SX(d, q). There is a

*Las Vegas algorithm with the same complexity as in Theorem*1.2

*that constructs an involution in*G

*with corank*r

*as an SLP in*X, wherer

*is as follows. If*G

*is linear or unitary, then*r=⌊d/2⌋.

*If*G*has type*Sp*or*Ω^{+}*, then*r = 2⌊d/4⌋. IfG*has 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^{2}logq(d+ logdlog^{3}q+d^{2}logq)) +χlogq). The
algorithm of Celler & Leedham-Green [17] forSL(d, q)has complexityO(d^{4}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_{1}, f_{1}, . . . , e_{k}, f_{k}}; it represents an automorphism
ofV which acts on{e_{1}, f_{1}, . . . , 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_{k}or0.

**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^{2}), otherwiseF= GF(q). ForΩ^{−}(d, q), we choose a primitive elementγ
ofGF(q^{2})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 of*SX(d, q)

*is generated by*S(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))^{−}^{1}ω

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^{2})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=γ^{−}^{1}+γ^{−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”, thenG*is 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_{d}in the following. In the centraliserCG(iH)
we find

K =_{1}

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_{K}ofSX(d−m, q)inK^{c}. Again, letc= 1_{d}for 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 element*g is found inT: if
v_{K} ∈ S_{K} andv_{H} ∈ S_{H} are the cycles inKandH, respectively, thenv=v_{K}gv_{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^{3}logd+d^{2}logdlogq).

A Las Vegas algorithm with the same complexity allows us to compute large powersg^{n} 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^{2}logdlogq).

The characteristic and minimum polynomials ofg ∈GL(d, q)can be computed by a Las Vegas
algorithm with complexityO(d^{3}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^{3}), 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^{3}+d^{2}log^{2}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 by*p.

* Theorem 4.1. Let*G

*be a finite simple classical group acting naturally on a projective space of*

*dimension*d−1, and letp

*be a prime. The proportion of*p-regular elements inG

*is at least*1/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 set*X

*for*G

*such that*{x

^{2}|x∈X}

*generates*G.

**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 fieldF*can be either even or odd. Recall that if*g∈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^{h}ileavesE 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. Let*q > 4. There is an absolute constantκ >0

*such that the following holds: if*H˜ ≤SX(m, q)

*is as defined above, then*H˜ = 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 that**O(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. For**l∈ {2, . . . , d/2−1}

P_{l}(G) ={g∈G|gis semisimple,gacts irreducibly onI_{g}, and dim(E_{g}) =d−l}.

**Definition 5.3. Let**P˜_{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 of*P˜

_{l}(G)

*power up to elements of*P

_{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_{1}, . . . , e_{k}be the entries of
λ(t)not equal tol, and letb=|((ǫq)^{e}^{1}−1)· · ·((ǫq)^{e}^{k}−1)|. Thent^{b}hasd−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* l*is odd and*G*has type*Sp*or*Ω^{±}*, then*P˜_{l}(G) *is empty. In all other cases*
*the following holds: For every constant*α∈(0,1/2)*there exists a constant*c >0*such 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 than*c/l.

*b) There exists a constant*c^{′} >0*such that, for every*d > 5*and every prime power*q, ifG =
SX(d, q)*and*P =S

lP˜_{l}(G), wherel*runs 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. If**dis 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^{h}iasH. 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^{3}logd+d^{2}logdlogq).

**5.2. Constructing the subgroup**H. 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. Let*g ∈P

_{l}(G)

*and let*T

*be the set of*h ∈ G

*such that*dim(E

_{g}∩E

_{g}h) =d−2l

*(the smallest possible value) and*V = (E

_{g}∩E

_{g}h)⊕I

_{g}⊕I

_{g}h. There exists an absolute constant c >0, independent ofl

*and the type of*G, 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_{g}hhas 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−1}possible 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_{g}so that their images span a complement to(E_{g}∩E_{g}h)⊕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_{g}h)⊕I_{g}with 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^{j}converges). 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. Let*g∈P

_{l}(G), and leth∈T

*as in Lemma*5.8.

a) E =Eg∩Egh*and*I =Ig⊕Igh*are invariant under*hg, g^{h}i.

*b) If*G*preserves some form, then*E*and*I*are 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 of*G.

*d) If*G*is not an orthogonal group in even dimension, then the conjugacy class of a semisimple*
*element in*G*is determined by its eigenvalues in*F¯*(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 restrictions*g|_{I} *and*g^{h}|_{I} *are conjugate within the group preserving the form specified in*
b)*and*c).

PROOF. a) Clearly,E_{g}∩E_{g}handI_{g}⊕I_{g}hare 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^{−1})−β(w, w^{′}) = 0, thusI_{g} andE_{g} are orthogonal. Hence
E_{g} ∩E_{g}his orthogonal toI_{g}⊕I_{g}h. SinceV is the direct sum of these spaces,I_{g} ⊕I_{g}his the
orthogonal complement ofE_{g}∩E_{g}h. Thus the form restricted to each ofE_{g}∩E_{g}handI_{g}⊕I_{g}h
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^{h}i. 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^{h}iis isomorphic toSX(m, q).

We can verify the latter using the one-sided Monte Carlo recognition algorithm of [35]; this has
complexityO(ξ+d^{3}logdlog^{3}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 on*I

_{g}⊕I

_{g}h

*preserved by*g

*and*g

^{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_{1}onU which
supportsγ: namely,B1is ag-invariant quadratic form withB1(u+v) =B1(u)+B1(v)+γ(u, v)

for allu, v ∈ U. Conjugating B_{1} byh defines ag^{h}-invariant quadratic formB_{2} onU h. Now
define a quadratic formBonU⊕U hbyB(v1+v2) =B1(v1) +B2(v2) +β(v1, v2)forv1∈U
andv_{2} ∈U h. We prove that this form is invariant under the action ofg^{2}; sinceghas odd order,
this shows thatB isg-invariant. SinceU isg-invariant, it suffices to prove thatB(vg^{2}) =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^{2} =f(v)(g+ 1) +vand theg-invariance ofB_{1}that

B(vg^{2}) = B1(f(v)(g+ 1)) +B2(v) +β(f(v)(g+ 1), v)

= β(f(v)g, f(v)) +B_{2}(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^{2})

= β(vg, v(g^{2}−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_{g}h⊕(E_{g}∩E_{g}h), andm. Observe thatm∈[d/3,2d/3]with variations for smalld.

Hence, our previous discussion proves the following.

* Lemma 5.11. Algorithm*FirstSX

*is correct and Las Vegas; if*q > 4, then it has complexity O(ξ+d

^{3}logdlog

^{3}q+ log

^{4}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 in*Gif 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_{r}as 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. Let*i∈G= SX(d, q)

*be a good involution of corank*r≤d/2

*and let*F

*be the un-*

*derlying field of*G. There exists a base change matrixc∈GL(d,F)

*such that*i

^{c}=

_{1}

r 0 1r

0 1d−2r 0 0 0 1r

*and the elements of*CG^{c}(i^{c})*have upper block triangular form with diagonal blocks*a, b, a, of de-
*gree*r,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 as*G. Otherwise, in the orthogonal case, the image contains
Sp(r, q)^{′}×SX(d−2r, q), whereSX(d−2r, q)*has the same type as*G.

We calli^{∗}:=i^{c}*the standard form of*i. 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. Let*G= 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) *and*i_{K} ∈ SX(d−m, q)*are good involutions, then*diag(i_{H}, i_{K})*is a good*
*involution in*G.

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]^{k}and[i, g^{−1}]^{k}commute 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]^{k}*is a Bray generator of*C_{G}(i). Bray &

Wilson [8] prove the following.

* Theorem 6.3. Let*G= SX(d, q)

*and let*i∈G

*be an involution. There is a constant*c >0

*such*

*that the proportion of*g∈G

*with*[i, g]

*of odd order is bounded below by*c/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. Let*i

*be a good involution in*G= SX(d, q)

*in standard form. A bounded generat-*

*ing set for a sufficient subgroup of*C

_{G}(i)

*can be constructed using a Monte Carlo algorithm with*

*complexity*O(logd(ξ+d

^{3}logd+d

^{2}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^{3}logd+d^{2}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}^{1}2) > _{π}^{6}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 corank**4in
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_{1} be the matrix of a quadratic
form of+or−type supportingF1, that is,Q1+Q^{⊺}_{1} =F1, and define

Q=
_{Q}

2 0 F2

0 Q1 0 0 0 Q3

whereQ_{2} = diag(0,1,1,1)andQ_{3} = 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_{G}_{1}(i) and
CG2(i), where

i=
_{1}

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}^{1}_{2}) = (^{a}_{a}^{2}_{4} ^{a}_{a}^{1}_{3}) (^{w}_{w}^{1}_{2}).

*Then*

CG1(i) =n

g=_{δ ⋆ ⋆}

0x ⋆ 0 0δ

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

*where*Sp(d−8, q)*preserves the form*F_{1}*, and the entries*⋆*are subject to the sole constraint that*
g*lies in*G_{1}*. (Such entries may be found for every choice of*δ *and*x.) The same holds whenG_{1}
*is replaced by*G2*; here*x∈Ω^{±}(d−8, q)*is required to preserve the associated quadratic form*
Q_{1}*.*

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_{1}orG_{2}.

Taking G_{1} 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_{1}, 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=
_{1}

4 0 y

0 1d−8 0 0 0 I4

∈G_{1} *if and only if*y*has the form*

y11 y12 y13 y14

y21 y22 y23 y13

y31 y32 y22 y12

y41y31+y12y21+y13y11+y14

,

*and*g∈G_{2}*if, in addition,*y_{14}= 0*and*y_{13}^{2} =y_{23}*and*y^{2}_{12}=y_{32}*and*y_{11}^{2} +y_{41}+y_{11}= 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_{G}_{j}(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. As**S1-module,A1 is isomorphic to the direct sum of three copies ofGF(q)with
trivialS_{1}-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