We describe a black-box Las Vegas algorithm to construct standard generators for classical groups defined over finite fields

(1)

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Ω⁺₄(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

(2)

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₂(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²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²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

(3)

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²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²logq d³logdlogq d⁴logdlog³q SU [12] d²logd d²logdlogq − Ω[13] d²logdlogq d²logdlog²q d³log²d

Sp [14] d+ logq 1 d²log²q

Ours d(logd+ logq) dlog²q d(logd+ log²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_KofK, 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

(4)

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 construction 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Ω₇(q)andΩ^±₈(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²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 automorphisms act on matrix entries. Recall thatSU₂(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

(5)

of order 2 and 3. Ifd= 4, thenΩ⁺₄(q) = SL2(q)×SL2(q). The graph automorphism swaps the two factors, and for eachSL₂(q)there are field automorphisms; thus,|Out(Ω⁺₄(q))|= 2e².

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= Ω⁺₄(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Ω⁺₄(q) = SL₂(q)◦SL₂(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 ∼= Ω⁺₄(q), andH ∼= Sp₄(q)andH ∼= Ω⁺₈(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₄(q), a graph automorphism ofΩ⁺₈(q) of order 3, or a field automorphism ofΩ⁺₄(q) which acts differently on the

twoSL₂(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]^kcommutes withi, or has even order2k, in which case both [i, g]^kand[i, g⁻¹]^kcommute withi. Ifgis random among the elements ofGfor which[i, g]has odd order, theng[i, g]^kis 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ⁱ−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ⁱ−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)^ε)×. . .×(q^e^k −(−1)^ε)]/(q−(−1)^ε),

where(e₁, . . . , 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

(6)

(qê¹+ 1)×. . .×(qê^k+ 1)×(q^f¹−1)×. . .×(q^f^j−1)where(e⁺₁, . . . , e⁺_k, f₁⁻, . . . , 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ê−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ê+ 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₁ andg₂ 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₁, d−e1} 6= {e₂, 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ⁿ⁻¹+ 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)⁰⁰, 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₁andA₂, where the generalised Fitting subgroupF^∗(C_G(i)) =C_G(i)⁰⁰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+ Π)).

(7)

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|/2andS ={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_jis a ppd(q, e_j)element ande₁+e₂ =d; second, ifbj is a randomhSi-conjugate ofaj, thenha₁, b1i andha₂, 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₁, b1}andT2 ={a₂, b2}, and, to ease exposition, supposeTj ≤Aj. Forg∈ CG(i) we check membership inA1andA2by checking commutativity withhT₂iandhT₁i, respectively. We decomposeg∈ hSiasg=g₁g₂g₃g₄ where eachg_jis a power ofgof largest possible order such that

|g₁|,|g₂|,|g₃|are pairwise coprime and none dividesq−1, andg1 ∈A1,g2∈A2,g3 ∈/A1∪A2, and

|g₄|dividesq−1. Taking randomg ∈ hSiand adding its componentg_j toT_j forj = 1,2, we seek witnesses(as in [35]) to establish thathT_ji=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⁰) 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⁰) 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⁰) 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₁)ife2 ≥e1, and similarly fora2. If we findaj, bj ∈CG(i) with the stated properties, then we can supposeha_j, b_ji ≤ 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⁰) 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_jiis 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

(8)

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_jdo 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₁orA₂may be an image ofΩ⁺₄(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₁ anda₂ 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₁ ande₂ withe₁+e₂ = 2n, and integersu₁ 6= v₁ andu₂ 6= v₂, 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₁andb₁ 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₁(q), as opposed toΩ⁻_e₁(q); similarly fora₂ 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₁ commutes witha₂ and a random conjugate ofa₂. Nowa₁ anda₂ 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₁(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₂(q)has order a multiple of this prime tends (slowly) to 1 as e₂ 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₁(q) of the appropriate order remains O(logd/d), and, because e₁ ande₂ are of comparable size, the probability that a random element ofΩ⁺_e₂(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.

(9)

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₁ andA₂ 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₂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₂)|, lies inA₁ 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^ui ∼= 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|/pinG, 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.

(10)

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^cwherecis 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ⁱ−1)×(q^f−1)×T^∗ andp-|(q^f−1)×T^∗|. Thus, the image ofh=g^|g|/pinG˜has a 1-eigenspace of dimensiond−iand acts irreducibly on thei-dimensional space associated withqⁱ−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^ui ∼= 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

(11)

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₀ ≤ 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ⁱ−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_din 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.

(12)

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₁.

Thus, there is an absolute constantz₂ >0with N(d)≥d!z₁Xu

i=l

1

i ≥d!z₁log(u/l)≥d!z₂. SinceN(d) =P

C|C|, whereCruns over all admissible classes, there is an absolute constantz₃ >0 with|A( ˜G)|/|G| ≥˜ _4d!¹ 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|/pmust 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⁻₁, . . . , b⁻_i , c⁺₁, . . . , c⁺_j )ofd˜whereiis odd. The associated maximal torus is

T_C^F ∼= (q^b⁻¹ + 1)×. . .×(q^b⁻ⁱ + 1)×(q^c⁺¹ −1)×. . .×(q^c⁺^j −1).

If there existz elements inS_d_˜of cycle type(a₁, . . . , a_k), then2^d−k^˜ z elements ofW correspond to each(a⁻₁, . . . , a⁻_i , a⁺_i+1, . . . , a⁺_k)withiodd.

As before, letc= ( ˜d−3)/2ande∈[c/2 + 4, c+ 3]\ {c,2c/3}. LetC_ebe 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₁, . . . , u_t). Each such partition gives rise to2^t−1signed partitions (c⁺, e⁻, u₁¹, . . . , 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₁¹, . . . , u_t^t), whereλ = (u₁, . . . , 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;

(13)

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=

₁

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=₁ _?

0 Spr−1(q)

or A=

₁ _? _?

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⁰ = 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₄(q) andΩ⁺₈(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.

(14)

5.2.2. The second subgroup. LetG = hXi be isomorphic to SXd(q) and let H ≤ Gbe constructed 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) =₁

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=

₁

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

, ϕ(f)^c=_u₀ ₀

0 u 0 0 0 1d−m

, and ϕ(C_H(i))^c=_{A ?} ₀

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 1d−m0

0 0 u

,

and

ϕ(CG(i))⁰=CG˜(ϕ(i))⁰=

A ? ? 0 SXd−m(q) ?

0 0 A

; as in Theorem 5.4, denote byψthe projectionCG˜(ϕ(i))⁰ →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) = ₁

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₁ ≤C with

ϕ(K1) = ₁

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₁ 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)² lies in K andϕ(k) has diagonal blocks 1r, b²,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² |x∈M}generates the group; thus, collectingO(1)elementskof this type suffices