Heiko Dietrich, C. R. Leedham-Green, and E. A. O’Brien

Dedicated to the memory of ´Akos Seress

ABSTRACT. We describe a black-box Las Vegas algorithm to construct standard generators for classical groups defined over finite fields. We assume that the field has size at least 4 and that oracles to solve certain problems are available. Subject to these assumptions, the algorithm runs in polynomial time. A practical implementation of our algorithm is distributed with the computer algebra system MAGMA.

1. Introduction

In [19, 26] we developed constructive recognition algorithms for the classical groups in their natural representation. These are well-analysed and efficient, both theoretically and in practice; our imple- mentations are distributed with the computer algebra system MAGMA[9]. A core idea is to construct centralisers of involutions, and use these to construct, as subgroups of the input group, classical groups of smaller rank, so facilitating recursion. We now develop these ideas to obtain such algorithms for classical groups given as black-box groups.

LetG˜ ≤GL_{d}(q)be a classical group in its natural representation, and letG=hXibe isomorphic to
a central quotient ofG, where˜ Xis a given generating set. Aconstructive recognitionalgorithm forG
constructs a surjective homomorphism fromG˜ toG, and for any giveng ∈ Gconstructs an element
of its inverse image inG. We realise such an algorithm in two stages. For each classical group˜ G, we˜
define a specific ordered set ofstandard generatorsS. The first task is to construct, as words in˜ X,
an ordered subsetSofGthat is the image ofS˜under a surjective homomorphism fromG˜ toG. The
second task is to solve theconstructive membership problemforGwith respect toS: namely, express
g ∈Gas a word inS, and so as a word inX; we also solve the constructive membership forG˜with
respect toS. Now the surjective homomorphism˜ ϕ: ˜G→Gthat mapsS˜toSisconstructive:g˜∈G˜
is written as a wordw( ˜S)inS, and its image˜ ϕ(˜g)isw(S). Similarly, we compute a preimage inG˜of
g ∈Gunderϕ. In summary, we provide an algorithm to solve the first of these tasks; we discuss the
second in Section 1.3.

Babai and Szemer´edi [6] introduced the concept of ablack-box group: group elements are represented by bit strings of uniform length, where more than one bit string may represent the same element. Three oraclesare provided to supply the group-theoretic functions of multiplication, inversion, and checking for equality with the identity element. Ablack-boxalgorithm is one that uses only these oracles. A common assumption is that other oracles are available to perform certain tasks.

For an overview of theMatrix Group Recognition Project, to which this work contributes, see [37].

Much of the background and preliminaries needed for this paper are summarised in [19, 26, 37].

1.1. The groups and their standard copies. Throughout,GLd(q)is the group of invertibled×d
matrices over the fieldGF(q). The groups under discussion areSL_{d}(q),Sp_{d}(q),SU_{d}(q),Ω^{±}_{d}(q), and
Ωd(q). We assume thatq ≥4, andd≥3for the orthogonal groups. All of the groups are perfect, and
with the exception ofΩ^{+}_{4}(q), all are quasisimple.

The definition of these groups, except for the first, depends on the choice of a bilinear or quadratic form. Groups defined by two forms of the same type are conjugate in the corresponding general linear

Key words and phrases. classical groups, constructive recognition, black-box algorithms.

This work was supported in part by the Marsden Fund of New Zealand via grant UOA 105. Dietrich was supported by an ARC-DECRA Fellowship, project DE140100088. The last two authors were supported by GNSAGA-INdAM while this work was completed; we thank our hosts, Patrizia Longobardi and Mercede Maj of the University of Salerno, for their generous hospitality. We thank Damien Burns for early work on the odd characteristic case; we thank Jianbei An, Gerhard Hiss, and Martin Liebeck for helpful discussions; we thank the referee and editor for their comments.

1

group; thestandard copyof a classical group is its unique conjugate which preserves a chosenstandard form. Our standard forms and copies are described in detail in [19, 26]. Thestandard generatorsof a classical group G˜ satisfy a specific standard presentation. The latter is used to define standard generators for a (black-box) groupGisomorphic to a central quotient ofG: namely, a generating set˜ ofGsatisfying this presentation.

We writeSX_{d}(q)for a conjugate of one of the above groups in the natural representation; we callSL,
SU,Sp,Ω, andΩ^{±}thetypeof the group.

Definition 1.1. The standard generatorsS(d, q,SX)of SX_{d}(q) are given in [19, Table 1] and [26,
Tables 1 & 2], depending on whetherqis even or odd.

The definition of the standard generators ofSX_{d}(q)implies afixedchoice of primitive element for the
underlying field. Observe thatS(d, q,SX)has cardinality at most 8 and, with the exception of one
element, thecycleofSX_{d}(q), all standard generators lie in naturally embedded subgroupsSX4(q)of
SX_{d}(q). This observation is crucial since we constructS(d, q,SX)by a recursion to classical groups
of smaller degree.

1.2. Main results. LetG=hXibe isomorphic to a central quotient ofSX_{d}(q). We present and
analyse a black-box Las Vegas algorithm that takes as inputX, and the parameters (d,q,SX) of G,
and outputs standard generators ofGas words inX. All words are given asstraight-line programs
(SLPs) [42, p. 10] which may be regarded as efficiently stored group words inX.

The complexity of a black-box algorithm is measured in terms of the number of calls to the standard oracles for the black-boxG. Letµbe an upper bound on the time required for each group operation.

Our algorithm assumes the existence of the following.

• An oracleOto compute the order of a giveng∈G.

• An oracleΠto compute a given power ofg∈G.

• An oracleξto construct a (nearly) uniformly distributed random element ofGas an SLP inX.

• An oracleχto recognise constructively (a central quotient of)SL_{2}(q).

We abuse notation by identifying the oracle with its cost. We ignore the cost of standard integer operations such as computing the greatest common divisor of two integers.

Our main result is the following theorem; it is proved in Sections 4–6. In Section 7 we discuss the complexity and the cost of realising the oracles.

Theorem 1.2. LetG=hXibe a black-box group isomorphic to a central quotient ofSX_{d}(q). Assume
the availability of the oracles specified above. Ifq≥4, then there is a black-box Las Vegas polynomial-
time algorithm which constructs, asSLPsinX, standard generators forG. The time required by the
algorithm isO(dlogd(µ+ξ+O+ Π) +d((χ+µ) log^{2}q+ξlogqlog logq)).

With minor modifications, which we identify in Section 4, the algorithm works well forq = 3; our algorithm does not apply toq = 2.

1.3. Rewriting. A black-box algorithm, with complexity O(d^{2}q)group operations, to write an
element of Gas an SLP in the standard generators was developed by Ambrose et al. [1]; recently,
Schneider extended this result to cover missing cases. We know of no polynomial-time algorithm to
perform this task.

The implementation of our algorithm accepts as input either a permutation or linear representation of
SX_{d}(q). If the input is an absolutely irreducible representation in defining characteristic, then we use
the polynomial-time algorithm of Costi [18] to perform the rewriting task. Using standard algorithms

for modules, we reduce arbitrary matrix representations in defining characteristic to this case. Recall, from [31], that a faithful linear or projective representation of a finite group of Lie type in cross characteristic has degree which is polynomial inq. Hence, all other input representations have size O(q); so, in these cases, the extension to [1] runs in time polynomial in the size of the input.

1.4. Related work. Kantor & Seress [24] developed the first black-box constructive recognition algorithms for classical groups. The complexity of these algorithms involves a factor ofq. By assuming the availability of the oracleχ, Brooksbank and Kantor [11–14] present algorithms with complexity polynomial ind,logq, and the number of calls toχ.

These algorithms construct Steinberg generators for the group, so the generating set returned has size
O(d^{2}logq) and requires significant storage. In practical applications, when we use the methods of
COMPOSITIONTREE[7], we work with groups having classical groups as homomorphic images and
construct kernels to these homomorphisms; now a small fixed number of standard generators is useful.

Table 1 lists the principal contributors to the stated complexity of each the algorithms of [11–14] and also the comparable costs of our algorithm. In Section 7 we discuss the cost of these oracles, and our additional two,OandΠ.

Algorithm ξ χ µ

SL [11] d^{2}logq d^{3}logdlogq d^{4}logdlog^{3}q
SU [12] d^{2}logd d^{2}logdlogq −
Ω^{}[13] d^{2}logdlogq d^{2}logdlog^{2}q d^{3}log^{2}d

Sp [14] d+ logq 1 d^{2}log^{2}q

Ours d(logd+ logq) dlog^{2}q d(logd+ log^{2}q)
TABLE1. Coefficients of oracles in the complexity of the algorithms

2. Structure of the general algorithm

Our black-box algorithm follows the general approach of our algorithms for the natural representation described in [19, 26]. LetG =hXibe isomorphic to a central quotient of a classical groupSXd(q).

We use a recursion to construct standard generatorsS_{G} ofGas SLPs inX. The base cases of this
recursion are discussed in Section 3.1; in the following, suppose thatGis not a base case.

For odd q, find, by random search, an element of even order that powers to an involution g ∈ G
which corresponds to an element inG˜ with−1- and1-eigenspaces of dimensionm∈[d/3,2d/3]and
d−m, respectively. In the centraliser ofginG, construct two commuting subgroupsH, K ≤Gwith
H ∼= SXm(q)andK ∼= SXd−m(q). Using recursion, construct the standard generatorsS_{H} andS_{K}
ofH andK, respectively. With the exception of the cycle ofG, all standard generators ofGlie in
S_{H} ∪ S_{K}. The cycle ofGis constructed bygluingthe cycles inS_{H} andS_{K}.

For even q, find, by random search, an element that powers to g ∈ G which is the image of an
element inG˜with 1-eigenspace of dimension in[2d/3,5d/6], acting irreducibly on a complement. By
takinggand a random conjugatehofginG, constructH =hg, hi ≤Gisomorphic toSXm(q)with
m∈[d/3,2d/3]. Using recursion, construct the standard generatorsS_{H} ofHand a specific involution
i∈H. InCG(i), findK≤Gwhich is isomorphic toSXd−m(q)and commutes element-wise withH.

By recursion, construct the standard generatorsS_{K}ofK, and, finally, glue the cycles inS_{H} andS_{K}.
To ensure that the algorithm is Las Vegas in the natural representation is easy: modulo a (known) base
change, the standard generators returned are identical to those listed in [19, Table 1] and [26, Tables 1

& 2]. To establish this for the black-box algorithm is more challenging. That groups of Lie type have short presentationswas first established by Guralnicket al. [22]; explicit short presentations, on our

standard generators, for the classical groups appear in [27]. By evaluating the standard presentation of
SX_{d}(q)in the output of our algorithm,S_{G}, we verify the correctness of our result.

The main challenge in developing the black-box algorithm was to devise a strategy for gluing the cycles. Other difficulties arise in the construction of the two smaller subgroups for the recursion.

The remainder of the paper is as follows. In Section 3, we recall some preliminary results. In Sections 4 and 5, we describe the construction of the two smaller subgroups H andK for odd and even q, respectively. In Section 6, we discuss how to glue the cycles ofHandK; this completes the construc- tion of the standard generators ofG. The complexity of our algorithm is discussed in Section 7. We comment on our implementation in Section 8.

3. Preliminaries

3.1. Base cases. IfGis isomorphic to a (central quotient of a) classical group of small rank, then we treat it as a base case.

Definition 3.1. Thebase casesfor evenq areSL_{d}(q)withd≤ 5;SU_{d}(q)withd ≤7;Sp_{d}(q)with
d≤6;Ω^{+}_{d}(q)withd≤8; andΩ^{−}_{d}(q)withd≤10. The base cases for oddqareSLd(q),SUd(q), and
Sp_{d}(q)withd≤4;Ω_{d}(q)withd≤5;Ω^{±}_{d}(q)withd≤6; andΩ_{7}(q)andΩ^{±}_{8}(q)withq≡3 mod 4.

The next theorem follows from [11–14, 16, 30].

Theorem 3.2. LetGbe isomorphic to a central quotient of a base case group SX_{d}(q). There is a
black-box Las Vegas algorithm that constructively recognisesG. Subject to the existence of the relevant
oracles identified in Section1.2, the algorithm runs in timeO((χ+µ) log^{2}q+ξlogqlog logq).

In practice, we sometimes employ algorithms other than those cited above to deal with base cases.

3.2. Automorphism groups of classical groups. The following facts are well-known, see [40, p.

192 & Proposition 13.11] and [21, Sec. 2.2, 2.5, 2.7].

Remark 3.3. a) The universal versions of the finite classical groups are SL_{d}(q), SU_{d}(q), Sp_{2n}(q),
Spin^{±}_{2n}(q), andSpin_{2n+1}(q). IfH is one of these, thenH/Z(H)is the adjoint version. IfH/Z(H)
is simple, thenAut(H)∼= Aut(H/Z(H)); every automorphism ofHcan be written as a product of a
graph, field, diagonal, and inner automorphism.

b) Let H = SL_{d}(q). Then H/Z(H) is simple, the diagonal automorphisms of H are induced by
conjugation with diagonal matrices in GL_{d}(q), and field automorphisms are induced by the usual
Frobenius action on matrix entries. Ifd= 2, then there is no graph automorphism; ifd >2, then the
graph automorphism is the inverse-transpose.

c) LetH = SUd(q)andd≥ 3. Then H/Z(H)is simple, the diagonal automorphisms are induced
by conjugation with diagonal matrices inGU_{d}(q), and there are no graph automorphisms. Field auto-
morphisms act on matrix entries. Recall thatSU_{2}(q)∼= SL2(q).

d) Let H = Sp_{d}(q) andd ≥ 4. Then H/Z(H) is simple and field automorphisms act on matrix
entries. Ifqis even, thenHhas no diagonal automorphisms;Hhas a non-trivial graph automorphism
(of order 2) only ifd = 4. Ifq is odd, then the diagonal automorphisms are induced by conjugation
with elements of the conformal group, andHhas no graph automorphism.

e) LetH = Ω^{+}_{d}(q)with q even and d ≥ 6. Then H is simple, field automorphisms act on matrix
entries, and there are no diagonal automorphisms. Ifd ≥ 6andd 6= 8, then|Out(H)|= 2ewhere
q = 2^{e}; there is a graph automorphism of order 2, induced by conjugation by a certain permutation
matrix, see [33, p. 194]. Ifd= 8, then|Out(H)|= 6ewhereq = 2^{e}; there are graph automorphisms

of order 2 and 3. Ifd= 4, thenΩ^{+}_{4}(q) = SL2(q)×SL2(q). The graph automorphism swaps the two
factors, and for eachSL_{2}(q)there are field automorphisms; thus,|Out(Ω^{+}_{4}(q))|= 2e^{2}.

f) Let H = Ω^{−}_{d}(q)with q even and d ≥ 4. Then H is simple and there are no graph or diagonal
automorphisms. Field automorphisms are induced by the usual action on matrix entries followed by
conjugation by some matrix inGLd(q); thus,|Out(H)|= 2ewhereq = 2^{e}.

g) LetH = Ωd(q)with bothdandqodd. ThenHis simple, field automorphisms act on matrix entries,
there is no graph automorphism, and|Out(H)|= 2ewhereq =p^{e}; there is a diagonal automorphism
of order 2.

h) LetH = Ω^{±}_{d}(q)withd ≥ 4even andq odd. If H 6= Ω^{+}_{4}(q), thenK = H/Z(H) = PΩ^{±}_{d}(q) is
simple, and we can identifyAut(H)withAut(K). The automorphisms ofK are as forΩ^{±}_{d}(q)with
qeven, with two exceptions. There are diagonal automorphisms, and there is no graph automorphism
of order 3. The automorphisms ofΩ^{+}_{4}(q) = SL_{2}(q)◦SL_{2}(q)are as for evenq, with the exception that
diagonal automorphisms exist.

For an integermlet1m be them×midentity matrix.

Lemma 3.4. LetG= SX_{d}(q)and letH∼= SXm(q)withmeven such that
H=_{SX}

m(q) 0 0 1d−m

≤G.

Suppose that eitherGandHhave the same type, orqis even andHhas typeΩ^{+}andGis orthogonal
or symplectic. With some exceptions forH ∼= Ω^{+}_{4}(q), andH ∼= Sp_{4}(q)andH ∼= Ω^{+}_{8}(q)withq even,
every automorphism ofHlifts to an automorphism ofG.

PROOF. This follows from Remark 3.3; note thatα ∈Aut(H)does not lift if its decomposition into
an inner, diagonal, field, and graph automorphism contains a graph automorphism ofSp_{4}(q), a graph
automorphism ofΩ^{+}_{8}(q) of order 3, or a field automorphism ofΩ^{+}_{4}(q) which acts differently on the

twoSL_{2}(q)factors.

3.3. Involution centralisers. IfGis a central quotient ofSX_{d}(q), then the centraliserC_{G}(i)of
an involutioni∈ Gcan be constructed using an algorithm of Bray [10]. Ifg ∈ G, 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. Ifgis random among the elements ofGfor which[i, g]has odd
order, theng[i, g]^{k}is random inC_{G}(i), see [39, Theorem 11]. That suchBray generators,g[i, g]^{k}, of
CG(i)can be constructed follows from the next theorem established in [28, 39].

Theorem 3.5. There is a constantc >0such that ifi∈Gis an involution andGis a central quotient
ofSX_{d}(q), then the proportion ofg∈Gwith[i, g]of odd order is bounded below byc/d.

To construct a Bray generator, we apply the order and power oracles to a random element.

3.4. Zsigmondy primes. Recall that if q is a prime-power and l > 0, then a(q, l)-Zsigmondy
primeris one that dividesq^{l}−1but notq^{i}−1fori < l. Such primes exist, except for(q, l) = (2,6)
and(q, l) = (q,2)with q a Mersenne prime. If an order oracle for G ∼= SXd(q) is available, then
repeated computations of the formgcd(q^{i}−1,|g|)yield alllandrsuch thatris a(q, l)-Zsigmondy
prime dividing|g|. If a(q, l)-Zsigmondy prime divides|g|, thengis appd(q, l)element.

Every semisimple element inG= SXd(q)lies in a maximal torus; the structure of these tori is known, see for example [36, Sec. 3]. IfGis linear or unitary, then its maximal tori are isomorphic to

[(q^{e}^{1}−(−1)^{ε})×. . .×(q^{e}^{k} −(−1)^{ε})]/(q−(−1)^{ε}),

where(e_{1}, . . . , e_{k}) is a partition of d, each q^{e} ±1 denotes a cyclic group of that order, and ε = 1
(or −1) if G is linear (or unitary). IfG = Sp_{2n}(q) orG = Ω2n+1(q), then the maximal tori are

(q^{e}^{1}+ 1)×. . .×(q^{e}^{k}+ 1)×(q^{f}^{1}−1)×. . .×(q^{f}^{j}−1)where(e^{+}_{1}, . . . , e^{+}_{k}, f_{1}^{−}, . . . , f_{j}^{−})is a signed
partition ofn. The maximal tori for Ω^{±}_{2n}(q) are the same, with keven for Ω^{+}, and kodd for Ω^{−}.
Observe that ifCis cyclic of ordernandpis a prime dividingn, then at least1−1/pof all elements
inC have order divisible byp. Hence, ifT is a maximal torus containing a direct factorq^{e}−1with
e > 1and(q, e)-Zsigmondy primes exist, then the proportion of ppd(q, e) elements inT is at least
2/3; a similar observation holds forq^{e}+ 1and ppd(q,2e)elements.

We now summarise easy but important consequences of properties of ppd(q, e)elements as discussed in [35]; to obtain the stated proportions, using [36], we count the number of tori (up to conjugacy) with suitable direct factors.

Remark 3.6. a) A subgroupH ofSL_{d}(q) is irreducible ifH contains a ppd(q, d) element, or if it
contains two elementsg_{1} andg_{2} such that eachg_{j} is a ppd(q, e_{j})and ppd(q, d−e_{j})element, where
ej ≤ d−ej, andej does not divided−ej, and{e_{1}, d−e1} 6= {e_{2}, d−e2}. The analogous result
holds for other classical groups. The proportion of such elements inSX_{d}(q)isO(1/d).

b) A subgroup of an orthogonal or symplecticSX_{d}(q) with d = 2ndoes not preserve a quadratic
form of +type if it contains a ppd(q, d) element; it does not preserve a quadratic form of−type if
it contains a ppd(q, d−2)element of order not dividing(q^{n−1}+ 1)(q−1). The proportion of such
elements inSX_{d}(q)isO(1/d).

c) A subgroup ofSL_{d}(q)does not preserve a bilinear form if it contains a ppd(q, e)element with odd
e > d/2; it does not preserve a sesquilinear form if it contains a ppd(q, e)element with evene > d/2.

The proportion of such elements inSL_{d}(q)isO(1/d).

4. Two smaller subgroups in odd characteristic

As outlined in Section 2, our algorithm for constructive recognition in the natural representation [26]

carries over readily to a black-box algorithm, with the exception of gluing the cycles. We describe gluing in Section 6; here we comment on the construction of the subgroups used for the recursion.

LetGbe isomorphic to a central quotient ofG˜ = SXd(q)withq > 3odd. Ifi∈ G˜is an involution with±1-eigenspacesE±, then

C_{G}_{˜}(i) = (GX(E_{+})×GX(E−))∩G,˜

where GX(E±) is the general linear, general unitary, symplectic, or orthogonal group acting onE±.
If j is the image of iinG, then C_{G}(j) is the image in Gof C_{G}_{˜}(i), unless GX(E_{+}) ∼= GX(E−),
and the images of iand −i inG are equal, in which case CG(j) is the image of CG˜(i) extended
by the image of a 2-cycle that interchanges E+ and E−. In [26], we call i a strong involution if
d/3< dim(E−) ≤2d/3. Here we allowd/3≤ dim(E−) ≤2d/3so thatiis a strong involution if
and only if−iis; this has negligible side effects. An involution inGisstrongif it is the image of a
strong involution inG.˜

Ifi ∈Gis a strong involution, thenC_{G}(i)^{00}, the second derived subgroup ofC_{G}(i), is isomorphic to
a central quotient ofSXe(q)×SXd−e(q)withd/3 ≤ e≤ 2d/3. We now describe how to construct
these direct factors as subgroups ofC_{G}(i).

Theorem 4.1. LetG =hXibe a central quotient ofSXd(q)ford≥6and oddq > 3. There exists
a black-box Las Vegas algorithm to construct a strong involutioni ∈ G, and to find generating sets
forA_{1}andA_{2}, where the generalised Fitting subgroupF^{∗}(C_{G}(i)) =C_{G}(i)^{00}is a central quotient of
SXe(q)×SXd−e(q), andA1 andA2 are the images ofSXe(q)andSXd−e(q). The algorithm also
returns the names of these two classical groups. IfGis orthogonal of +type, theniis chosen such
thatA1andA2have+type. The algorithm runs in timeO(dlogd(µ+ξ+O+ Π)).

PROOF. The restriction ondensures thatF^{∗}(CG(i))is a central quotient of the direct product of two
perfect groups.

We prove the theorem by exhibiting an algorithm which has the claimed complexity. Suppose first that
Gis isomorphic to a central quotient ofSL_{d}(q).

(1) By a random search, findg∈Gof even order; seti=g^{|g|/2}andS ={g}.

(2) Construct three Bray generators ofC_{G}(i)and place them inS.

(3) Construct random elements ofhSi, looking for two elements that power to elementsa1 anda2

satisfying the following two conditions: first, eacha_{j}is a ppd(q, e_{j})element ande_{1}+e_{2} =d; second,
ifbj is a randomhSi-conjugate ofaj, thenha_{1}, b1i andha_{2}, b2icommute. Ife1 ∈/ [d/3,2d/3], then
iis not a strong involution and we return to Step (1). If afterO(d)trials no such elements are found,
then repeat Step (2) and then (3).

(4) SetT1 ={a_{1}, b1}andT2 ={a_{2}, b2}, and, to ease exposition, supposeTj ≤Aj. Forg∈ CG(i)
we check membership inA1andA2by checking commutativity withhT_{2}iandhT_{1}i, respectively. We
decomposeg∈ hSiasg=g_{1}g_{2}g_{3}g_{4} where eachg_{j}is a power ofgof largest possible order such that

|g_{1}|,|g_{2}|,|g_{3}|are pairwise coprime and none dividesq−1, andg1 ∈A1,g2∈A2,g3 ∈/A1∪A2, and

|g_{4}|dividesq−1. Taking randomg ∈ hSiand adding its componentg_{j} toT_{j} forj = 1,2, we seek
witnesses(as in [35]) to establish thathT_{j}i=Aj. If this fails, then repeat Steps (2)–(4), and continue.

The presence of these witnesses, which are returned by the procedure, proves that the algorithm has terminated correctly.

We now supply further details for these steps, and assess the complexity of the algorithm.

(1^{0}) By [29], a strong involutioni∈Gis found afterO(logd)repetitions of Step (1); thus, we expect
to return to this stepO(logd)times at a cost ofO(logd(ξ+O+ Π)).

(2^{0}) A sample ofO(d)random elements yields a Bray generator. It is proved in [34, Corollary 1.2]

that the probability that 3 random elements of a finite almost simple groupK, conditional on them
generating K/F^{∗}(K), generateK is greater than 139/150. As observed in [38, Theorem 4.1], the
probability that k+ 1random elements of a finite abelian k-generator group generate the group is
greater than 1/2.72. Since C_{G}(i) is an extension of a central quotient of SL_{e}(q)×SL_{d−e}(q) by a
cyclic group (or by a dihedral group whend = 2eandi = −i), the probability thathSi = C_{G}(i),
with S as in Step (2), is bounded away from 0 by an absolute positive constant. In particular, the
probability that S generates a group containingF^{∗}(CG(i)) is very high (observe S contains g as
well as the Bray generators). The expected number of returns to Step (2) isO(logd), at the cost of
O(dlogd(ξ+µ+O+ Π)).

(3^{0}) Using the notation of the theorem, we may assume thate1 =e, soe2 =d−e. Recall, from [35,
Theorem 5.7], that the probability that an element ofSL_{f}(q)is a ppd(k, q)element is approximately
1/kwheref /2< k≤f. Thus the proportion of elements ofF^{∗}(C_{G}(i))that power to a candidate for
a1is approximately1/e1, or(1/e1)(1−1/e_{1})ife2 ≥e1, and similarly fora2. If we findaj, bj ∈CG(i)
with the stated properties, then we can supposeha_{j}, b_{j}i ≤ A_{j}; the probability of this being false is
exponentially small. The total cost of Step (3) is as in Step (2); the factor oflogdarises as we may
have to return to this step forO(logd)involutions.

(4^{0}) Elements ofT_{j} have order coprime toq −1, thus lie in a central quotient ofSL_{e}_{j}(q). We first
seek witnesses to show thatGj = hT_{j}iis not a central quotient of a classical group that preserves a
form. Ife_{j} is even, then we rule out the possibility thatG_{j} is an image of a symplectic or orthogonal
group by finding a ppd(q, k)element for some oddkgreater thanej/2; similarly, ifqis a square, then
we rule out the possibility thatG_{j} is the image of the unitary group by finding a ppd(q, k) element
for some evenk > ej/2. We are now in a position in which we can, in principle, apply the algorithm
of [35]. That algorithm applies to a subgroupK ofSLn(q), in its natural representation, whereK is
known to act irreducibly, and to preserve no non-zero form. The algorithm seeks witnesses to prove

K = SLn(q)by virtue of their orders. The witnesses are constructed by a random process, and the
algorithm uses only ppd information. Here we have a central quotient ofSL_{e}_{j}(q)rather than the group
itself, but this does not harm the validity of the algorithm.

The remaining issue is that the elements that we place in the generating setsT_{j}do not approximate
to a random distribution. However the probability thatg_{j}, as in (4), is a ppd(q, k)element approximates
closely to the probability that a random element ofAj is a ppd(q, k)element. For smaller values ofk,
the probability is slightly reduced because the chances that an element ofC_{G}(i)will map to an element
of order a multiple of a given(q, k)-Zsigmondy prime in both components is slightly increased. Since
the algorithm in [35] seeks ppd(q, k)elements for large values ofk, this is not a problem. It needs
O(log logd)random elements to find the required witnesses, so Step (4) is asymptotically faster than
Steps (2) and (3). Once these witnesses have been found (and witnesses for one factor all commute
with the witnesses of the other), then we have proved that the algorithm has run correctly: based on
element orders, the groups generated by these witnesses are not isomorphic to central quotients of
propersubgroups ofSL_{e}_{j}(q), thus, they must be central quotients ofSL_{e}_{j}(q).

Now suppose thatGis a central quotient ofΩ^{+}_{2n}(q). New difficulties arise. Firstly,A_{1}orA_{2}may be
an image ofΩ^{+}_{4}(q); secondly, we must reject the involutioniif its centraliser is a central quotient of
two orthogonal groups of−type; finally, we cannot choose the elementsa_{1} anda_{2} to act irreducibly
on the respective direct factors because such elements do not exist. The impact of the first is limited to
a minor change in the associated statistics. The others we address by seeking elements with one of the
following sets of properties.

(a) There exist even integerse_{1} ande_{2} withe_{1}+e_{2} = 2n, and integersu_{1} 6= v_{1} andu_{2} 6= v_{2}, and
elementsa1,a2,b1, andb2 are found such thatajhas order the product of a(q, uj)-Zsigmondy prime
and a(q, e_{j} −u_{j})-Zsigmondy prime, andb_{j} has order the product of a(q, v_{j})-Zsigmondy prime and
a(q, ej−vj)-Zsigmondy prime, anda1andb1 both commute witha2andb2, cf. Remark 3.6. These
elements are sought by powering up random elements ofhSi. Again it is almost certain thata_{1}andb_{1}
correspond to elements of one factor, and thata2andb2correspond to elements of the other. Also,a1

andb1, together, serve as irreducibility witnesses (as dida1 alone in the special linear case), and also
as witnesses to the fact that they generate a subgroup ofΩ^{+}_{e}_{1}(q), as opposed toΩ^{−}_{e}_{1}(q); similarly fora_{2}
andb2. Thus the algorithm proceeds as before.

(b) Elements are found that power to ppd(q, ej) elements aj, j = 1,2, where e1 +e2 = 2n, and
a_{1} commutes witha_{2} and a random conjugate ofa_{2}. Nowa_{1} anda_{2} are witnesses thatF^{∗}(C_{G}(i))
is a central factor of the direct product of two groups of typeΩ^{−}, and the involutioni is rejected.

As pointed out in [26, Lemma 2.2], we fall into the Ω^{−} case if and only if both q ≡ 3 mod 4and
e_{j} ≡2 mod 4.

The proportion of elements of Ω^{+}_{e}_{1}(q) satisfying the order condition imposed in (a) is O(logd/d).

However, if, in the notation of (a), eitheru1 ore1 −u1 is small, then the probability that a random
element ofΩ^{+}_{e}_{2}(q)has order a multiple of this prime tends (slowly) to 1 as e_{2} tends to infinity. But
consider larged: if we just count the cases that arise whene1/3 ≤ v1 ≤2e1/3, then the proportion
of elements of Ω^{+}_{e}_{1}(q) of the appropriate order remains O(logd/d), and, because e_{1} ande_{2} are of
comparable size, the probability that a random element ofΩ^{+}_{e}_{2}(q)has order a multiple of one of the
relevant primes is bounded away from zero by an absolute positive constant. The requisite proportions
are given, to more accuracy than required here, in [26, Section 8].

The other groups are dealt with in the same style.

The algorithm of Theorem 4.1 may be trivially extended to deal with smaller values ofd, provided that
iis chosen so thatF^{∗}(CG(i))is a central quotient of the direct product of two perfect groups.

In practice, the steps in this algorithm can run faster by applying various simple devices, such as using
conjugation to generate new elements of theT_{j}. Theoretically, the most expensive step of the algorithm
is (2): we must testO(d)random elements to obtain a Bray generator of the involution.

Recall [5, Corollary 4.2]: ifpis a prime andGis a finite simple classical group acting naturally on a projective space of dimensiond−1, then the proportion ofp-regular elements inGis at least1/2d.

Remark 4.2. In the gluing process, we deal with the following situation: the involution i ∈ G is
not strong and, using the previous notation, A_{1} andA_{2} are quotients ofSX_{e}(q)andSXd−e(q)with
e≤6. In contrast to the above discussion, this timeeis known, and we only want to constructA1. We
proceed as follows. The first step is to use a modification of Theorem 4.1 to constructB ≤A_{2}with
CA2(B)≤Z(A2), for example,B =A2. Sincee≤6is small, elements inBcan in general be readily
constructed by taking random Bray generators ofC_{G}(i) to the powerexp(SX_{e}(q)), cf. [5, Corollary
4.2]. Observe thath ∈C_{G}(i), of order not dividing|Z(A_{2})|, lies inA_{1} if and only if [h, b] = 1for
every generatorb ofB. Using this, we find a non-centralh ∈ A1, and constructA1 as the normal
closure ofhinC_{G}(i)by applying the algorithm of [42, Theorem 2.3.9]; we use Remark 3.6 and [35]

to verify the correctness of our computation.

Remark 4.3. The caseq = 3requires special care, here and in gluing (see Section 6). The principal reason is that one of the factorsAj may be soluble. In all other important respects, the algorithm is identical with that for larger oddq, and displays similar performance.

5. Two smaller subgroups in even characteristic

Throughout this section, letq 6= 2be even and letG =hXi. To simplify exposition, we assume that
Gis isomorphic toSX_{d}(q), and not to an arbitrary central quotient. We also assume that Gisnota
base case. Letϕ:G → G˜ be an (unknown) isomorphism to the standard copy G˜ ofSX_{d}(q), with
underlying fieldF. The aim of this section is to construct, as SLPs inX, generators for commuting
subgroupsH ∼= SXm(q)andK∼= SXd−m(q)ofG, where, in general,m∈[d/3,2d/3].

5.1. Constructing the first subgroup. In [19, Sec. 5], we devised an algorithm to constructH˜ ≤
G˜ withH˜ ∼= SXm(q). In general, m ∈ [d/3,2d/3]is even, andH˜ has the same type as G; if˜ G˜ is
symplectic or orthogonal, thenmis divisible by 4 andH˜ has typeΩ^{+}.

We briefly recall this construction. By a random search, findg ∈G˜that powers toh ∈ G˜ which has
a 1-eigenspace of dimensione∈[2d/3,5d/6]and acts irreducibly on a complement. A construction
ofO(1)random elements ofG˜suffices to finduso thatH˜ =hh, h^{u}i ∼= SXm(q)withm= 2(d−e);

more precisely, modulo a base change,

H˜ =_{SX}

m(q) 0 0 1d−m

≤G.˜

Motivated by that approach, we now develop a black-box algorithm to constructH ≤ Gwith H ∼=
SXm(q)andϕ(H) = ˜Has above. We seekg∈Gwhose order is divisible by two Zsigmondy primes,
saypandr satisfying (Z1) and (Z2) below, which witness that the image ofg^{|g|/p}inG, firstly, acts˜
irreducibly on a subspace of dimensioni∈[d/6, d/3]and, secondly, acts trivially on a complement to
this space.

IfG∼= Ω^{−}_{d}(q), then we seekH∼= Ω^{+}_{m}(q)withm∈ {d−4, d−6}divisible by 4. While our algorithm
is capable of constructing subgroups of other ranks, this restriction arises from gluing; we explain this
in more detail in Remark 6.1.

We start with an easy observation.

Lemma 5.1. Leth ∈ GL_{d}(q)have ane-dimensional1-eigenspace. If his a ppd(q, d−e) element,
thenhacts irreducibly on a complement to its 1-eigenspace.

We now describe the construction ofH in detail forSL. Letϕ: G → G˜ = SL_{d}(q). By a random
search, findg∈Gsuch that

(Z1) |g|is divisible by a(q, i)-Zsigmondy primepwithi∈[d/6, d/3];

(Z2) |g|is divisible by a(q, e)-Zsigmondy primerwithi-2eande+ 2i > d.

We can also assume thatghas odd order; otherwise, replacegbyg^{c}wherecis the smallest 2-power
satisfyingc≥2d−2; nowgis semisimple and lies in some maximal torus ofG.

Lemma 5.2. Ifg ∈ G ∼= SLd(q) satisfies(Z1) and(Z2), then the image ofh = g^{|g|/p} inG˜ has a
1-eigenspace of dimensiond−i∈[2d/3,5d/6]and acts irreducibly on a complement.

PROOF. Suppose thatglies in a maximal torusS= (q^{k}−1)×S^{∗}andkis divisible by botheandi.

Sincee > d/3, we know thatk ∈ {e,2e}; nowi|kyields a contradiction toi-2e. Thus,gmust lie
in a maximal torusT = (q^{j}−1)×(q^{f}−1)×T^{∗}withi|jande|f; as shown above,i-f and, by
assumption,p-|T^{∗}|. Sincee+ 2i > d, it follows thatj=i, henceg∈T = (q^{i}−1)×(q^{f}−1)×T^{∗}
andp-|(q^{f}−1)×T^{∗}|. Thus, the image ofh=g^{|g|/p}inG˜has a 1-eigenspace of dimensiond−iand
acts irreducibly on thei-dimensional space associated withq^{i}−1, see Lemma 5.1.

Suppose we have found g ∈ Gsatisfying (Z1) and (Z2), and set h = g^{|g|/p}. As outlined in [19],
it follows from [41] that the construction ofO(1)random elements ofGsuffices to findusuch that
H =hh, h^{u}i ∼= SLm(q), wherem= 2i∈[d/3,2d/3]. We could use [4] to verify thatH ∼= SLm(q).

More efficiently, we proceed as follows. First, we use Remark 3.6 and consider a sample ofO(d) random elements in H until we find witnesses that H does not preserve a bilinear or sesquilinear form, and it acts irreducibly on anm-dimensional space. Then we apply [35] as in Theorem 4.1 and seek witnesses thatHis isomorphic toSLm(q). If we cannot find these witnesses, then we construct anotherH; onlyO(1)repetitions are required.

The strategy for unitary, symplectic, and orthogonal types is similar. One change is due to the different
structure of maximal tori, which requires an adjustment of the Zsigmondy prime divisors we seek; for
smalld, this requires specialised techniques. A second is that the isomorphism type ofH ∼= SXm(q)
is not uniquely determined ifGis orthogonal or symplectic; bothΩ^{+}_{m}(q)andΩ^{−}_{m}(q)are possible. We
use Remark 3.6 to detect one or the other. If we confirmH ∼= Ω^{−}_{m}(q), then we constructively recognise
Hand replaceHbyH^{?}≤HwithH^{?}∼= Ω^{+}_{m−4}(q); having constructively recognisedH, we can write
down generators forH^{?}. (Alternatively, we could construct a new group untilH ∼= Ω^{+}_{m}(q).)

We now analyse the complexity of the resulting algorithm.

Lemma 5.3. There is a black-box Las Vegas algorithm which takes as inputG∼= SXd(q), which is not a base case, and constructsH≤GwithH∼= SXm(q), admittingK≤CG(H)withK∼= SXd−m(q);

in general,m∈[d/3,2d/3]is even. IfGis linear or unitary, then so isH. In all other cases,His of
typeΩ^{+}andmis divisible by 4. IfGhas typeΩ^{−}, thenm∈ {d−4, d−6}is divisible by4. The time
required isO(d(ξ+O) + Π +µ).

PROOF. The correctness of the algorithm is established in [19, Sec. 5]; it remains to show that the construction ofO(1)random elements inGis sufficient to findg∈Gsatisfying (Z1) and (Z2) above.

(IfGhas typeΩ^{−}, then we show thatO(d)random elements suffice.) We give the proof in detail for
SLandΩ^{−}; the remaining cases are dealt with analogously. In the following, we assume thatdis large
enough so that all required Zsigmondy primes exist and intervals are non-empty. We use Remark 3.6
and [35] as in Theorem 4.1 to verify that the output of this algorithm,H, satisfiesH ∼= SXm(q); this
verification dominates the overall complexity.

First, supposeG ∼= SLd(q) = ˜G. LetGˆ be a simply connected reductive algebraic group such that
Gˆ^{F} = ˜Gfor some Frobenius morphismF. Callg ∈ G˜ admissible if some power ofghas odd order

and satisfies (Z1) and (Z2) above. LetA( ˜G)be the set of all admissibleg ∈G. By the multiplicative Jordan decomposition, everyg ∈ G˜ can be written uniquely asg = suwheres ∈G˜ is semisimple, u ∈ G˜ is unipotent, andsu = us. Sinceg = su ∈ A( ˜G) if and only if s ∈ A( ˜G), andA( ˜G) is invariant under conjugation, we can apply [36, Theorem 1.3] to estimate the proportion|A( ˜G)|/|G|˜. For convenience, we recall this result here.

LetFbe the underlying field ofG. Let˜ T_{0} ≤ G˜ be anF-stable maximal torus with Weyl group W.
TheG-conjugacy classes of˜ F-stable maximal tori inG˜are in one-to-one correspondence with theF-
conjugacy classes ofW. For anF-conjugacy classCinW, denote byTC ≤Gˆ a representative of the
correspondingG-conjugacy class of maximal tori, and let˜ T_{C}^{F} =T_{C}∩G. It is proved in [36, Theorem˜
1.3] that

|A( ˜G)|

|G|˜ =X

C

|C|

|W|·|T_{C}^{F} ∩A( ˜G)|

|T_{C}^{F}|

whereCruns over allF-conjugacy classes ofW. Our strategy is to restrict to special classesCwhich
allow us to determine lower bounds for|C|/|W|and|T_{C}^{F}∩A( ˜G)|/|T_{C}^{F}|, thus providing a lower bound
for|A( ˜G)|/|G|.˜

If the type is SL, then W = Sd, the symmetric group of degree d, and the F-classes of W are
the conjugacy classes of W, so parametrised by partitions of d. LetC be a conjugacy class ofS_{d}
corresponding to a partition(i, e, . . .)wherei∈ [d/6, d/3]ande > d/3withe+ 2i > dandi-2e;

call such a classadmissible. Note thatT_{C}^{F} = (q^{i}−1)×(q^{e}−1)×T^{∗}. Letpandrbe(q, i)-Zsigmondy
and(q, e)-Zsigmondy primes, respectively. The proportion of elements inT_{C}^{F} with order divisible by
pris at least1/4, thus,|T_{C}^{F} ∩A( ˜G)|/|T_{C}^{F}| ≥1/4for each such classC. In conclusion,

|A( ˜G)|

|G|˜ ≥ 1 4d!

X

C|C|, whereCruns over all admissible classes.

Letl=dd/6eandu=bd/3c. It remains to estimate the numberN(d)of elements ofS_{d}in admissible
classes, that is, elements of cycle type(i, e, . . .)withi∈[l, u],e+ 2i > d, andi-2e. For this, we run
overi∈[l, u]ande∈[d−2i+ 1, d−i], and count how many elements of cycle type(i, e, . . .)exist.

First, we show that there is no over-counting. Sincee > d/3≥iande+ 2i > d, (#) d−e−i∈[0, . . . , i−1],

andeis the unique largest entry in the cycle decomposition. Now suppose we encounter cycle types (i, e, j, . . .)and(j, e, i, . . .)withi, j ∈[l, u],e∈[d−2i+1, d−i]∩[d−2j+1, d−j], andi+j+e≤d.

The latter, together with(#), impliesj≤d−i−e≤i−1, hencej < i. By symmetry, we geti < j, a contradiction. Thus, there is no over-counting.

We next determine the number N˜(d) of elements of cycle type (i, e, . . .) with i ∈ [l, u] and e ∈ [d−2i+ 1, d−i]as

N˜(d) = Xu i=l

Xd−i e=d−2i+1

d i

d−i e

(i−1)!(e−1)!(d−e−i)!

= d!Xu i=l

Xd−i e=d−2i+1

1 ie.

For eachi, there are at most three2e∈[2d−4i+ 2, . . . ,2d−2i]withi|2e, hence ignoring the three largest summands inPd−i

e=d−2i+1 1

ie yields a lower bound forN(d); in summary, N(d) ≥ d!Xu

i=l

1 i

Xd−i e=d−2i+4

1 e.

There is an absolute constantz1>0such that for large enoughdand alli∈[d/6, d/3],
X^{d−i}

e=d−2i+4

1 e ≥

Z d−i d−2i+4

1

xdx= log

d−i d−2i+ 4

> z_{1}.

Thus, there is an absolute constantz_{2} >0with
N(d)≥d!z_{1}Xu

i=l

1

i ≥d!z_{1}log(u/l)≥d!z_{2}.
SinceN(d) =P

C|C|, whereCruns over all admissible classes, there is an absolute constantz_{3} >0
with|A( ˜G)|/|G| ≥˜ _{4d!}^{1} N(d) ≥ z3, which proves the claim forSL. The typesSp,SU, andΩ^{+} are
dealt with analogously.

Now consider G ∼= Ω^{−}_{d}(q) = ˜G and write d˜ = d/2. Suppose d˜is odd, define c = ( ˜d−3)/2,
and suppose d is large enough such that c/2 > 6. We want to find g ∈ G which, in the natural
representation, acts irreducibly on a space of dimensiond˜−3and as the identity on a complement.

For this, we seekg∈Gwith order divisible by a(q,2c)-Zsigmondy primepand by a(q, e)-Zsigmondy
primerwithe ∈[c/2 + 4, c+ 3]\ {c,2c/3}. Note thate-2c; thus, ifgis such an element, then it
must lie in a maximal torus ofGisomorphic toT = (q^{c}+ 1)×(q^{f}±1)×T^{∗}such thatr|q^{f}±1and
e|2f. Sinced˜−c−f < c, the powerh =g^{|g|/p}must lie in the direct factorq^{c}+ 1; hence, in the
natural representation,hacts irreducibly on a space of dimension2c= ˜d−3and as the identity on a
complement.

The Weyl groupW ofΩ^{−}_{d}(q)has order2^{d−1}^{˜} d!˜ and theF-conjugacy classes ofW correspond to signed
partitions(b^{−}_{1}, . . . , b^{−}_{i} , c^{+}_{1}, . . . , c^{+}_{j} )ofd˜whereiis odd. The associated maximal torus is

T_{C}^{F} ∼= (q^{b}^{−}^{1} + 1)×. . .×(q^{b}^{−}^{i} + 1)×(q^{c}^{+}^{1} −1)×. . .×(q^{c}^{+}^{j} −1).

If there existz elements inS_{d}_{˜}of cycle type(a_{1}, . . . , a_{k}), then2^{d−k}^{˜} z elements ofW correspond to
each(a^{−}_{1}, . . . , a^{−}_{i} , a^{+}_{i+1}, . . . , a^{+}_{k})withiodd.

As before, letc= ( ˜d−3)/2ande∈[c/2 + 4, c+ 3]\ {c,2c/3}. LetC_{e}be the union of allF-classes
corresponding to signed partitions(c^{+}, e^{−}, . . .). Note thatd−c−e < c/2˜ and there ared!/ce˜ elements
inSd˜of cycle type(c, e, . . .); we claim that there are2^{d−3}^{˜} d!/ce˜ elements inW corresponding to signed
partitions(c^{+}, e^{−}, . . .), that is,|C_{e}|= 2^{d−3}^{˜} d!/ce.

To prove the claim, let λ = (u1, . . . , ut) be a partition ofd˜−c−e. Defineπ(λ) = u1. . . ut and
ζ(λ) =n!, wherenis the number ofui = 1. Using this notation,Sd˜containsd!/ceζ(λ)π(λ)˜ elements
corresponding to the partition(c, e, u_{1}, . . . , u_{t}). Each such partition gives rise to2^{t−1}signed partitions
(c^{+}, e^{−}, u^{}_{1}^{1}, . . . , u^{}_{t}^{t}) with an even number of i = +, and, as shown above, for each such signed
partition there exist2^{d−2−t}^{˜} d!/ceζ(λ)π(λ)˜ elements inW. Thus, each partition(c, e, u1, . . . , ut) `d˜
yields 2^{d−3}^{˜} d!/ceζ˜ (λ)π(λ) elements inW corresponding to signed partitions(c^{+}, e^{−}, u^{}_{1}^{1}, . . . , u^{}_{t}^{t}),
whereλ = (u_{1}, . . . , u_{t}). Clearly, |C_{e}|is the sum of these numbers, running over all partitions λ `
d˜−c−e, thus

|C_{e}|= 2^{d−3}^{˜} d!˜
ce

X

λ`d−e−c˜

1

ζ(λ)π(λ) = 2^{d−3}^{˜} d!˜
ce ;
the last equation follows sincem! =|S_{m}|=P

λ`mm!/ζ(λ)π(λ)for every integerm≥1.

Recall that|T_{C}^{F} ∩A( ˜G)|/|T_{C}^{F}| ≥ 1/4for eachF-classC ∈ C_{e}. In conclusion, there is an absolute
constantz >0such that

|A( ˜G)|

|G|˜ ≥ 1
2^{d+1}^{˜} d!˜

Xc+1

e=dc/2e+3|C_{e}| ≥ 1
16

Xc+1 e=dc/2e+3

1

ce > z/d;

recall thate∈[c/2 + 2, c+ 3]\ {c,2c/3}, so we estimate the sum over all sucheby running withe fromdc/2e+ 2toc+ 1. The case of evend˜is dealt with analogously.

5.2. Constructing the second subgroup. LetG =hXibe isomorphic toSXd(q) and letH ≤
G be constructed as in Lemma 5.3. We now describe the construction ofK ≤ G such that K ∼=
SXd−m(q)andHcommutes withK. The approach is to constructively recogniseH, explicitly write
down a suitable involutioni ∈ H, and then to findK inCG(i). As a first step, we comment on the
structure ofC_{G}(i).

5.2.1. Involution centralisers. Thecorankof an involutioni∈G˜is the rank of the matrixi−1_{d}.
The next theorem describes the structure of involution centralisers in G; it is a modification of [19,˜
Theorem 6.1], and was proved by Aschbacher & Seitz [2].

Theorem 5.4. Leti∈G˜ be an involution of corankr≤d/2. There existsc∈GL_{d}(F)such that
i^{c}=

_{1}

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 degrees
r,d−2r, andr, respectively. Consider the homomorphism

ψ:C_{G}_{˜}c(i^{c})→GL_{r}(F)×GLd−2r(F), _{a ? ?}

0 b ? 0 0a

7→(a, b).

(i) If G˜ is linear or unitary, then the image of ψ contains A× B with A = SXr(q) and B = SXd−2r(q), both of the same type asG.˜

(ii) IfG˜is symplectic, then the image ofψisA×BwithB = Sp_{d−2r}(q)and
A= Sp_{r}(q) or A=_{1} _{?}

0 Spr−1(q)

or A=

_{1} _{?} _{?}

0 Spr−2(q)?

0 0 1

.

(iii) IfG˜ is orthogonal, then the image ofψ isA×B with Aas in (ii). If A = Sp_{r}(q), thenB^{0} =
SXd−2r(q)has the same type asG; if˜ A6= Sp_{r}(q), thenB = Sp_{d−2r}(q).

The standard formof i is i^{c}; note that, in general, i^{c} is not in the standard copy G. If˜ i ∈ G˜ is
an involution of specific corankr ∈ {2, . . . , d/2}, then its image under every automorphism of G˜
has the same corank. (We remark that this actually holds for all SXd(q), including base cases, with
the exceptions of Sp_{4}(q) andΩ^{+}_{8}(q): these have graph automorphisms which change the corank of
involutions.) This allows us to define the corank of an involutioni∈Gviaϕ:G→G.˜

Leti∈G˜be an involution of corankr < d/2in standard form; letψandAbe as in Theorem 5.4. If
G˜is linear or unitary, thenC ≤CG˜(i)issufficientifψ(C)≥SXr(q)×SX_{d−2r}(q). IfG˜is symplectic
or orthogonal, then C ≤ C_{G}_{˜}(i) is sufficientif ψ(C) containsSXd−2r(q) and the projection to the
irreducible diagonal block ofAcontainsSp_{r}(q),Sp_{r−1}(q), andSp_{r−2}(q), respectively. Ifi∈Gis an
involution, then a sufficient subgroup ofCG(i)is defined via the isomorphism ϕ:G → G˜ followed
by a conjugation.

Theorem 5.5. Let ibe an involution in G = hXi ∼= SXd(q). There is a black-box Monte Carlo algorithm which constructs, asSLPsinX, a generating set for a sufficient subgroup ofCG(i); it runs in timeO(d(µ+ξ+O+ Π)).

PROOF. It suffices to consider O(d) random elements to construct a Bray generator of C_{G}(i). As
explained in the proof of [19, Theorem 6.4], a constant number of Bray generators suffices to generate

a sufficient subgroup.

5.2.2. The second subgroup. LetG = hXi be isomorphic to SXd(q) and let H ≤ Gbe con-
structed as in Lemma 5.3, henceH is isomorphic toSL_{m}(q), SU_{m}(q), orΩ^{+}_{m}(q). By construction,
there exists an isomorphismϕ:G→G˜to the standard copy ofSX_{d}(q)such that

H˜ =ϕ(H) =

SXm(q) 0 0 1d−m

.

We now describe the construction ofK≤GwithK∼= SXd−m(q)of the same type asGsuch that
K˜ =ϕ(K) =_{1}

m 0

0 SXd−m(q)

.

By recursion, we construct standard generatorsS_{H} ofH. Note thatS˜_{H} =ϕ(S_{H})is an automorphic
image of the standard generatorsS(m, q,SX)embedded inH, say˜ α( ˜S_{H}) = S(m, q,SX)withα ∈
Aut( ˜H). IfH˜ is linear or unitary, then so isG, hence˜ αlifts to an automorphism ofG, see Remark˜
3.3. If H˜ is orthogonal, thenα lifts to an automorphism of G˜ ∈ {Sp_{d}(q),Ω^{±}_{d}(q)}, with possible
exceptions forH˜ ∼= Ω^{+}_{m}(q) withm ∈ {4,8}, see Lemma 3.4. We comment on this case in Remark
5.8; for now, suppose thatH6∼= Ω^{+}_{m}(q)withm∈ {4,8}. Under these assumptions,ϕcan be modified
by an automorphism ofSX_{d}(q)so that we can assume thatS˜_{H} =S(m, q,SX).

We useS_{H} to constructi, f ∈Hsuch that there exists a base change matrixc∈GL_{d}(F)with
ϕ(i)^{c}=

_{1}

r 1r 0 0 1r 0 0 0 1d−m

, ϕ(f)^{c}=_{u}_{0} _{0}

0 u 0 0 0 1d−m

, and ϕ(C_{H}(i))^{c}=_{A ?} _{0}

0 A 0 0 0 1d−m

where r = m/2, A ∼= SXr(q) acts irreducibly, and u ∈ SXr(q) is fixed-point free of odd order.

We then apply the next proposition to construct the required subgroupK ≤ C_{G}(i). To visualise the
situation, we now assume thatϕis chosen such thatϕ(i)has standard form, and

ϕ(f) =_{u} _{0} _{?}

0 1d−m0

0 0 u

,

and

ϕ(CG(i))^{0}=CG˜(ϕ(i))^{0}=

A ? ? 0 SXd−m(q) ?

0 0 A

;
as in Theorem 5.4, denote byψthe projectionCG˜(ϕ(i))^{0} →A×SXd−m(q).

Proposition 5.6. There is a black-box Las Vegas algorithm which, using the above notation, constructs
fromiandfa subgroupK ≤C_{G}(i)withK ∼= SXd−m(q)and

K˜ =ϕ(K) =
_{1}

r 0 0

0 SXd−m(q) 0

0 0 1r

.

The algorithm runs in timeO(d(µ+ξ+O+ Π)).

PROOF. Suppose first thatGis not of typeΩ^{−}; hencem ∈[d/3,2d/3], and thereforemandd−m
are approximately equal. Using Theorem 5.5, we find a sufficient subgroup C ≤ CG(i), and then
constructK as a subgroup ofC. Applying a simple modification of Theorem 4.1, we obtainK_{1} ≤C
with

ϕ(K1) =
_{1}

r ? ?

0 SXd−m(q) ?

0 0 1r

.

We stress that, by construction ofi, the types and degrees ofSXd−m(q)andA∼= SXr(q)are known;

thus, modulo a normal 2-subgroup ofC_{G}(i), Theorem 4.1 is essentially applied toSX_{r}(q)×SX_{d−m}(q).

Ifh ∈ K_{1} is random andϕ(h)has diagonal blocks1_{r}, b,1_{r}, then, as seen in the proof of [19, Lem.

7.1], the element k = (f h(f f^{h})^{(|f|−1)/2})^{2} lies in K andϕ(k) has diagonal blocks 1r, b^{2},1r. It is
proved in [23] that anO(1)random search in a perfect classical group suffices to find a generating set
M such that{x^{2} |x∈M}generates the group; thus, collectingO(1)elementskof this type suffices