• No results found

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


Academic year: 2022

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


Full text


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˜ ≤GLd(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 areSLd(q),Spd(q),SUd(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.



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 writeSXd(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 SXd(q) are given in [19, Table 1] and [26, Tables 1 & 2], depending on whetherqis even or odd.

The definition of the standard generators ofSXd(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, thecycleofSXd(q), all standard generators lie in naturally embedded subgroupsSX4(q)of SXd(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 ofSXd(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)SL2(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 ofSXd(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((χ+µ) log2q+ξ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(d2q)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 SXd(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(d2logq) 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] d2logq d3logdlogq d4logdlog3q SU [12] d2logd d2logdlogq [13] d2logdlogq d2logdlog2q d3log2d

Sp [14] d+ logq 1 d2log2q

Ours d(logd+ logq) dlog2q d(logd+ log2q) 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 generatorsSG 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 generatorsSH andSK ofH andK, respectively. With the exception of the cycle ofG, all standard generators ofGlie in SH ∪ SK. The cycle ofGis constructed bygluingthe cycles inSH andSK.

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 generatorsSH 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 generatorsSKofK, and, finally, glue the cycles inSH andSK. 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 SXd(q)in the output of our algorithm,SG, 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 areSLd(q)withd≤ 5;SUd(q)withd ≤7;Spd(q)with d≤6;Ω+d(q)withd≤8; andΩd(q)withd≤10. The base cases for oddqareSLd(q),SUd(q), and Spd(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 SXd(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((χ+µ) log2q+ξ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 SLd(q), SUd(q), Sp2n(q), Spin±2n(q), andSpin2n+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 = SLd(q). Then H/Z(H) is simple, the diagonal automorphisms of H are induced by conjugation with diagonal matrices in GLd(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 inGUd(q), and there are no graph automorphisms. Field auto- morphisms act on matrix entries. Recall thatSU2(q)∼= SL2(q).

d) Let H = Spd(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 = 2e; 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 = 2e; 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 eachSL2(q)there are field automorphisms; thus,|Out(Ω+4(q))|= 2e2.

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 = 2e.

g) LetH = Ωd(q)with bothdandqodd. ThenHis simple, field automorphisms act on matrix entries, there is no graph automorphism, and|Out(H)|= 2ewhereq =pe; 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) = SL2(q)◦SL2(q)are as for evenq, with the exception that diagonal automorphisms exist.

For an integermlet1m be them×midentity matrix.

Lemma 3.4. LetG= SXd(q)and letH∼= SXm(q)withmeven such that H=SX

m(q) 0 0 1d−m


Suppose that eitherGandHhave the same type, orqis even andHhas typeΩ+andGis orthogonal or symplectic. With some exceptions forH ∼= Ω+4(q), andH ∼= Sp4(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 ofSp4(q), a graph automorphism ofΩ+8(q) of order 3, or a field automorphism ofΩ+4(q) which acts differently on the


3.3. Involution centralisers. IfGis a central quotient ofSXd(q), then the centraliserCG(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−1]kcommute withi. Ifgis random among the elements ofGfor which[i, g]has odd order, theng[i, g]kis random inCG(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 ofSXd(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 dividesql−1but notqi−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(qi−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

[(qe1−(−1)ε)×. . .×(qek −(−1)ε)]/(q−(−1)ε),

where(e1, . . . , ek) is a partition of d, each qe ±1 denotes a cyclic group of that order, and ε = 1 (or −1) if G is linear (or unitary). IfG = Sp2n(q) orG = Ω2n+1(q), then the maximal tori are


(qe1+ 1)×. . .×(qek+ 1)×(qf1−1)×. . .×(qfj−1)where(e+1, . . . , e+k, f1, . . . , fj)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 factorqe−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 forqe+ 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 ofSLd(q) is irreducible ifH contains a ppd(q, d) element, or if it contains two elementsg1 andg2 such that eachgj is a ppd(q, ej)and ppd(q, d−ej)element, where ej ≤ d−ej, andej does not divided−ej, and{e1, d−e1} 6= {e2, d−e2}. The analogous result holds for other classical groups. The proportion of such elements inSXd(q)isO(1/d).

b) A subgroup of an orthogonal or symplecticSXd(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(qn−1+ 1)(q−1). The proportion of such elements inSXd(q)isO(1/d).

c) A subgroup ofSLd(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 inSLd(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

CG˜(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 CG(j) is the image in Gof CG˜(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, thenCG(i)00, the second derived subgroup ofCG(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 ofCG(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 forA1andA2, where the generalised Fitting subgroupF(CG(i)) =CG(i)00is 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 ofSLd(q).

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

(2) Construct three Bray generators ofCG(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, eachajis a ppd(q, ej)element ande1+e2 =d; second, ifbj is a randomhSi-conjugate ofaj, thenha1, b1i andha2, 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 ={a1, b1}andT2 ={a2, b2}, and, to ease exposition, supposeTj ≤Aj. Forg∈ CG(i) we check membership inA1andA2by checking commutativity withhT2iandhT1i, respectively. We decomposeg∈ hSiasg=g1g2g3g4 where eachgjis a power ofgof largest possible order such that

|g1|,|g2|,|g3|are pairwise coprime and none dividesq−1, andg1 ∈A1,g2∈A2,g3 ∈/A1∪A2, and

|g4|dividesq−1. Taking randomg ∈ hSiand adding its componentgj toTj forj = 1,2, we seek witnesses(as in [35]) to establish thathTji=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.

(10) 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+ Π)).

(20) 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 CG(i) is an extension of a central quotient of SLe(q)×SLd−e(q) by a cyclic group (or by a dihedral group whend = 2eandi = −i), the probability thathSi = CG(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+ Π)).

(30) 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 ofSLf(q)is a ppd(k, q)element is approximately 1/kwheref /2< k≤f. Thus the proportion of elements ofF(CG(i))that power to a candidate for a1is approximately1/e1, or(1/e1)(1−1/e1)ife2 ≥e1, and similarly fora2. If we findaj, bj ∈CG(i) with the stated properties, then we can supposehaj, bji ≤ Aj; 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.

(40) Elements ofTj have order coprime toq −1, thus lie in a central quotient ofSLej(q). We first seek witnesses to show thatGj = hTjiis not a central quotient of a classical group that preserves a form. Ifej is even, then we rule out the possibility thatGj 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 thatGj 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 ofSLej(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 setsTjdo not approximate to a random distribution. However the probability thatgj, 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 ofCG(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 ofSLej(q), thus, they must be central quotients ofSLej(q).

Now suppose thatGis a central quotient ofΩ+2n(q). New difficulties arise. Firstly,A1orA2may 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 elementsa1 anda2 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 integerse1 ande2 withe1+e2 = 2n, and integersu1 6= v1 andu2 6= v2, and elementsa1,a2,b1, andb2 are found such thatajhas order the product of a(q, uj)-Zsigmondy prime and a(q, ej −uj)-Zsigmondy prime, andbj has order the product of a(q, vj)-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 thata1andb1 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Ω+e1(q), as opposed toΩe1(q); similarly fora2 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 a1 commutes witha2 and a random conjugate ofa2. Nowa1 anda2 are witnesses thatF(CG(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 ej ≡2 mod 4.

The proportion of elements of Ω+e1(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Ω+e2(q)has order a multiple of this prime tends (slowly) to 1 as e2 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 Ω+e1(q) of the appropriate order remains O(logd/d), and, because e1 ande2 are of comparable size, the probability that a random element ofΩ+e2(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 theTj. 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, A1 andA2 are quotients ofSXe(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 ≤A2with CA2(B)≤Z(A2), for example,B =A2. Sincee≤6is small, elements inBcan in general be readily constructed by taking random Bray generators ofCG(i) to the powerexp(SXe(q)), cf. [5, Corollary 4.2]. Observe thath ∈CG(i), of order not dividing|Z(A2)|, lies inA1 if and only if [h, b] = 1for every generatorb ofB. Using this, we find a non-centralh ∈ A1, and constructA1 as the normal closure ofhinCG(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 toSXd(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˜ ofSXd(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, hui ∼= SXm(q)withm= 2(d−e);

more precisely, modulo a base change,

H˜ =SX

m(q) 0 0 1d−m


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 ∈ GLd(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˜ = SLd(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, replacegbygcwherecis 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= (qk−1)×Sandkis divisible by botheandi.

Sincee > d/3, we know thatk ∈ {e,2e}; nowi|kyields a contradiction toi-2e. Thus,gmust lie in a maximal torusT = (qj−1)×(qf−1)×Twithi|jande|f; as shown above,i-f and, by assumption,p-|T|. Sincee+ 2i > d, it follows thatj=i, henceg∈T = (qi−1)×(qf−1)×T andp-|(qf−1)×T|. Thus, the image ofh=g|g|/pinG˜has a 1-eigenspace of dimensiond−iand acts irreducibly on thei-dimensional space associated withqi−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, hui ∼= 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˜ T0 ≤ 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˜ TCF =TC∩G. It is proved in [36, Theorem˜ 1.3] that

|A( ˜G)|

|G|˜ =X



|W|·|TCF ∩A( ˜G)|


whereCruns over allF-conjugacy classes ofW. Our strategy is to restrict to special classesCwhich allow us to determine lower bounds for|C|/|W|and|TCF∩A( ˜G)|/|TCF|, 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 ofSd corresponding to a partition(i, e, . . .)wherei∈ [d/6, d/3]ande > d/3withe+ 2i > dandi-2e;

call such a classadmissible. Note thatTCF = (qi−1)×(qe−1)×T. Letpandrbe(q, i)-Zsigmondy and(q, e)-Zsigmondy primes, respectively. The proportion of elements inTCF with order divisible by pris at least1/4, thus,|TCF ∩A( ˜G)|/|TCF| ≥1/4for each such classC. In conclusion,

|A( ˜G)|

|G|˜ ≥ 1 4d!


C|C|, whereCruns over all admissible classes.

Letl=dd/6eandu=bd/3c. It remains to estimate the numberN(d)of elements ofSdin 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


= 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


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], Xd−i


1 e ≥

Z d−i d−2i+4


xdx= log

d−i d−2i+ 4

> z1.

Thus, there is an absolute constantz2 >0with N(d)≥d!z1Xu



i ≥d!z1log(u/l)≥d!z2. SinceN(d) =P

C|C|, whereCruns over all admissible classes, there is an absolute constantz3 >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 = (qc+ 1)×(qf±1)×Tsuch thatr|qf±1and e|2f. Sinced˜−c−f < c, the powerh =g|g|/pmust lie in the direct factorqc+ 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 order2d−1˜ d!˜ and theF-conjugacy classes ofW correspond to signed partitions(b1, . . . , bi , c+1, . . . , c+j )ofd˜whereiis odd. The associated maximal torus is

TCF ∼= (qb1 + 1)×. . .×(qbi + 1)×(qc+1 −1)×. . .×(qc+j −1).

If there existz elements inSd˜of cycle type(a1, . . . , ak), then2d−k˜ z elements ofW correspond to each(a1, . . . , ai , a+i+1, . . . , a+k)withiodd.

As before, letc= ( ˜d−3)/2ande∈[c/2 + 4, c+ 3]\ {c,2c/3}. LetCebe 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 are2d−3˜ d!/ce˜ elements inW corresponding to signed partitions(c+, e, . . .), that is,|Ce|= 2d−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, u1, . . . , ut). Each such partition gives rise to2t−1signed partitions (c+, e, u11, . . . , utt) with an even number of i = +, and, as shown above, for each such signed partition there exist2d−2−t˜ d!/ceζ(λ)π(λ)˜ elements inW. Thus, each partition(c, e, u1, . . . , ut) `d˜ yields 2d−3˜ d!/ceζ˜ (λ)π(λ) elements inW corresponding to signed partitions(c+, e, u11, . . . , utt), whereλ = (u1, . . . , ut). Clearly, |Ce|is the sum of these numbers, running over all partitions λ ` d˜−c−e, thus

|Ce|= 2d−3˜ d!˜ ce




ζ(λ)π(λ) = 2d−3˜ d!˜ ce ; the last equation follows sincem! =|Sm|=P

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

Recall that|TCF ∩A( ˜G)|/|TCF| ≥ 1/4for eachF-classC ∈ Ce. In conclusion, there is an absolute constantz >0such that

|A( ˜G)|

|G|˜ ≥ 1 2d+1˜ d!˜


e=dc/2e+3|Ce| ≥ 1 16

Xc+1 e=dc/2e+3


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 ofCG(i).

5.2.1. Involution centralisers. Thecorankof an involutioni∈G˜is the rank of the matrixi−1d. 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∈GLd(F)such that ic=


r 0 1r

0 1d−2r 0 0 0 1r

and the elements ofCG˜c(ic)have upper block triangular form with diagonal blocksa, b, a, of degrees r,d−2r, andr, respectively. Consider the homomorphism

ψ:CG˜c(ic)→GLr(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 = Spd−2r(q)and A= Spr(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 = Spr(q), thenB0 = SXd−2r(q)has the same type asG; if˜ A6= Spr(q), thenB = Spd−2r(q).

The standard formof i is ic; note that, in general, ic 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 Sp4(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)×SXd−2r(q). IfG˜is symplectic or orthogonal, then C ≤ CG˜(i) is sufficientif ψ(C) containsSXd−2r(q) and the projection to the irreducible diagonal block ofAcontainsSpr(q),Spr−1(q), andSpr−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 CG(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 toSLm(q), SUm(q), orΩ+m(q). By construction, there exists an isomorphismϕ:G→G˜to the standard copy ofSXd(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 generatorsSH ofH. Note thatS˜H =ϕ(SH)is an automorphic image of the standard generatorsS(m, q,SX)embedded inH, say˜ α( ˜SH) = 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˜ ∈ {Spd(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 ofSXd(q)so that we can assume thatS˜H =S(m, q,SX).

We useSH to constructi, f ∈Hsuch that there exists a base change matrixc∈GLd(F)with ϕ(i)c=


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

, ϕ(f)c=u0 0

0 u 0 0 0 1d−m

, and ϕ(CH(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 ≤ CG(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




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 ≤CG(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 obtainK1 ≤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 ofCG(i), Theorem 4.1 is essentially applied toSXr(q)×SXd−m(q).

Ifh ∈ K1 is random andϕ(h)has diagonal blocks1r, b,1r, then, as seen in the proof of [19, Lem.

7.1], the element k = (f h(f fh)(|f|−1)/2)2 lies in K andϕ(k) has diagonal blocks 1r, b2,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{x2 |x∈M}generates the group; thus, collectingO(1)elementskof this type suffices


Related documents

Every Las Vegas algorithm can be converted to a Monte Carlo algorithm: just report a random answer if the running time gets too

The condition also implies classical and new results on vector spaces, algebraically closed fields, torsion-free abelian groups and Archimedean ordered abelian

We generalize the Plesken-Fabia´ nska L 2 -quotient algorithm for finitely presented groups on two or three generators to allow an arbitrary number of generators.. The main

For the important infinite family of alternating groups, the present black-box algorithms [3, 4] can only test whether a given black- box group is isomorphic to an alternating or

For square matrices over a field, the classification of conjugacy classes can be reduced to matrices where the characteristic polynomial is a power of an irreducible polynomial; for

In this section, we prove some roundedness results, one of which, Corollary 3.10, plays a crucial role in the proof of Kahn's conjecture for q=5..

If this closure occurs as proposed, this would mean that upgrades at Ludmilla WWTP are incomplete before 3 ML/day of additional effluent is diverted from Larrakeyah (about 30%

In quantum theory the states of a system are vectors in a vector space (more precisely a Hilbert space) V. Now fields should be defined over the complex plane (or more generally over

Moments of the derivative of characteristic polynomials with an application to the Riemann zeta

Or classical analogues: what are the dimensions of the simple rational G modules where G is an algebraic group over a field of positive characteristic (cf. the Lusztig

It remains an open question whether Theorem 4 holds for finite simple classical groups of type A of unbounded rank over fields of bounded size.. We use the notation of [26] for

Sessional Com m ittee on the Environm ent 79.. A strong research and development effort, particularly into the integration of control methods, is essential to the

A classical theorem by O’Nan-Scott says that the primitive groups can be classified into five types: Affine, Almost simple, Simple diagonal, Product and Twisted wreath.... A

 Should I analyse the specification carefully, as in black-box testing, to discover “what the code should be doing”..  Does white-box testing have an advantage, over

Theorem 1.3. There is a Las Vegas algorithm which constructs an involution of G as an SLP in X. A modification of the algorithm of Theorem 1.2 yields an algorithm to

We describe an algorithm to compute a composition tree for a matrix group defined over a finite field, and show how to use the associated structure to carry out computations with

Conversely, given a string C-group one can construct an ARP using an algorithm described by Jacques Tits in 1956.... Abstract regular polytopes and

Theorem 7.2 There is an absolute positive constant c such that if H is a finite simple classical group of Lie rank r defined over a field of odd characteristic, and x is an

Theorem 1.1 There is a black-box polynomial-time Monte Carlo algorithm to determine the characteristic of a quasisimple group G of Lie type, subject to the existence of an oracle

For all but E 8 (q) in even characteristic, our algorithms to construct the SL 2 subgroups and to label the root and toral elements are black-box provided that the algorithms

5.15 At the time of Mr C’s requests for access to the NDIS, the NDIA did not have any policy or guideline dealing specifically with incarcerated individuals and access to the NDIS.

existence. In making such an estimate, the Government Printer was requested to take as understood that each author body would have its report printed by the

I We want to describe finitely generated, infinite groups by a finite amount of information?. I A finite presentation in terms of generators and relators provides such