Towards effective algorithms for linear groups
E.A. O’Brien
∗Abstract. One of the major research directions in computational group theory over the past 15 years has been the development of effective algorithms for the investigation of subgroups of GL(d, F) whereF is a finite field. We survey this work.
2000 Mathematics Subject Classification: 20C20, 20C40
1. Introduction
Research activity in computational group theory has concentrated on four pri- mary areas: permutation groups, finitely-presented groups, polycyclic groups, and representation theory.
It is now possible in practice to study the structure of permutation groups having degrees up to about ten million; see Seress [77] for further detail. We can readily compute useful descriptions (for certain quotients) of “large” finitely- presented groups; see Sims [80] for further detail. Effective algorithms for the study of (finite and infinite) polycyclic groups have been developed; see [48, Chapter 8]
for further detail.
While the study of a group via its modular representations is a fundamental area of mathematical research, limited tools exist for such structural investigation.
Consider G=hXi ≤GL(d, F) whereF = GF(q). Natural questions arise. What is the order of G? What are its composition factors? What are its Sylow sub- groups? While similar questions about a subgroup of Sn, the symmetric group of degree n, can be answered theoretically and practically using highly effective polynomial-time algorithms, existing machinery for linear groups is much weaker.
For example, it is difficult to determine (using existing standard functions) the order of a random subgroup of GL(6,52) using either of the major computational group theory systems,GAP[38] and Magma[14].
∗I am most grateful to Bill Kantor for his personal and professional support over many years.
I thank the organisers for the invitation and financial support to participate in the meeting. This work was partially supported by the Marsden Fund of New Zealand via grant UOA124. I thank Peter Brooksbank, Derek Holt, Alice Niemeyer, Cheryl Praeger, ´Akos Seress, and the referee for their careful reading, comments, and corrections to the paper.
A major topic of research over the past 15 years has been the development of effective well-understood algorithms for the study of such groups. An associated goal is to realise the performance of these algorithms in practice.
One measure of performance is that an algorithm is polynomial in the size of the input; forG=hXi ≤GL(d, q), the size of the input is O(|X|d2logq). For a discussion of complexity-related issues, see Seress [77].
1.1. Basic tasks.
Already the most basic computations are expensive for linear groups. Consider multiplying two d×d matrices. Its complexity is O(dω) field operations, where ω= 3 if we employ the traditional algorithm. Strassen’s divide-and-conquer algo- rithm [82] reducesωto log27. However, itsMagmaimplementation demonstrates better performance over the traditional method only for matrices defined over fi- nite fields having degrees in the hundreds. Further, there are overheads: the additional complexity of the implementation and memory used. While Copper- smith & Winograd [37] demonstrate thatω can be smaller than 2.376, this seems of limited practical significance.
Observe that we can compute large powersmof a matrixgin at most 2blog2mc multiplications by the standard recursive algorithm: gm=gm−1g ifmis odd and gm=g(m/2)2ifmis even.
The standard algorithm to compute the characteristic polynomial of a matrix has complexity O(d3) [48, p. 227]. Storjohann [81] presents a deterministic algo- rithm having similar complexity to determine its minimal polynomial; a simpler randomised alternative having worst-case complexityO(d4) is described by Celler
& Leedham-Green [28].
1.2. Randomised and black-box algorithms.
Most of the algorithms for linear groups are randomised: they rely on random selections, and the analysis of their performance assumes that we can select uni- formly distributed random elements.
A Monte Carlo algorithm is a randomised algorithm which may return an incorrect answer to a decision question, and the probability of this event is less than some specified value. ALas Vegasalgorithm is one which never returns an incorrect answer, but may report failure with probability less than some specified value. If one of the answers given by a Monte Carlo algorithm is always correct, then it is one-sided. For a discussion of (concepts related to) these types of algorithms, we refer the reader to Babai [5].
Babai [4] presented a Monte Carlo algorithm to construct in polynomial time nearly uniformly distributed random elements of a finite group. No effective imple- mentation of this algorithm is available. Instead, bothGAP andMagmause the product replacement algorithm of Celler et al. [27]. That this is also polynomial time was established by Pak [73]. For a discussion of both algorithms, we refer
the reader to [77, pp. 26-30]. Leedham-Green & O’Brien [60] present a variation of the latter algorithm to construct random elements of a normal subgroup.
The concept of a black-box group was introduced by Babai & Szemer´edi [10].
In this model, group elements are represented by bit-strings of uniform length; the only group operations permissible are multiplication, inversion, and checking for equality with the identity element.
Seress [77, p. 17] defines ablack-box algorithmas one which does not use specific features of the group representation, nor particulars of how group operations are performed; it can only use the operations listed above. Some of the algorithms surveyed here were first developed in the black-box context, usually under the assumption thatoracles to perform certain tasks are available.
One such is an order oracleto compute the order of an arbitrary element of a group. In Section 2 we describe such an oracle for a linear group.
Another is adiscrete log oraclewhich will provide, for a given non-zero element µof GF(q) and a fixed primitive elementaof GF(q), the unique integer kin the range 1≤k < q for which µ =ak. For a description of discrete log algorithms, see [78, Chapter 4].
Seress [77, Chapter 2] provides an excellent account of black-box algorithms:
these include Monte Carlo algorithms to compute the normal closure of a subgroup and to construct the derived group of a black-box group.
One may intuitively think of a straight-line program for g ∈ G = hXi as an efficiently stored group word on X that evaluates to g. While the length of a word in a given generating set constructed in n multiplications and inversions can increase exponentially with n, the length of the corresponding straight-line program islinearinn. Babai & Szemer´edi [10] prove that every element of a finite groupGhas a straight-line program of length at mostO(log2|G|). In practice, both Magma and GAP exploit straight-line programs. We do not explicitly consider the concept further here, but refer the reader to Seress [77] for a discussion of its theoretical and practical significance, particularly in evaluating homomorphisms and relations.
1.3. The approaches.
Theblack-box group approach, initiated by Babai & Beals [7], seeks to determine the abstract group-theoretic structure ofG. The associated algorithms are black- box, usually Monte Carlo.
Every finite groupGhas a series of characteristic subgroups 1≤O∞(G)≤Soc∗(G)≤Pker(G)≤G,
whereO∞(G) is the largest soluble normal subgroup ofG. Here Soc∗(G)/O∞(G) is the socle of the factor group G/O∞(G), and so Soc∗(G)/O∞(G) is isomorphic to a direct productT1× · · · ×Tk of nonabelian simple groups that are permuted by conjugation inG; further Pker(G) is the kernel of this permutation action. For a more detailed account of this structure, see, for example, [48, pp. 31–32].
GivenG=hXi ≤GL(d, q), Babai & Beals [7] present a Monte Carlo algorithm to construct subgroupsH1, . . . , Hk such that Hi/O∞(Hi) ∼=Ti, orHi acts on a permutation domain of size polynomial in d. If we can construct the Hi, then we can construct G/Pker(G)≤Sk, which can be studied readily using permuta- tion group methods. The remaining theoretical difficulty is the construction of (generators for) the soluble radical ofGin Monte Carlo polynomial time.
By contrast, thegeometric approachseeks to investigate whether a linear group Gsatisfies certain natural and inherent properties in its action on its underlying vector space. If so, it determines anAschbacher categoryofG, identifies anNCG naturally associated with this category, and recursively studiesG/N andN. Our primary focus in this survey is the geometric approach.
Luks [65] proved that we can decide solubility for linear groups in polynomial time, and presenteddeterministicalgorithms to answer a variety of questions for soluble linear groups. These algorithms are polynomial, not in the size of the input groupG, but in thelargest prime divisorof|G|other than the characteristic. This work has been developed and extended by Miyazaki [66]. While Cooperman and O’Brien developed a prototype implementation of Luks’ algorithm in 2000, its full potential has not yet been practically realised.
1.4. The major tasks.
In designing algorithms for the structural investigation of asimplegroupG=hXi, we identify three natural and significant tasks.
• Determine the name ofG.
• Construct an isomorphism betweenGand a “standard” copy ofG.
• Given g ∈G, writeg as a word in X: with considerable abuse of notation, we say that this task is the word-problemforG.
Two major types of algorithms have been developed to solve these tasks. A non-constructive recognition algorithm names G. (More precisely, it may sim- ply establish thatGcontainsa particular named group as a composition factor.) Clearly such an identification is useful. If, for example, we identifyGas a member of a particular family of finite simple groups, then we may apply algorithms toG which are specially designed for this family.
A constructive recognition algorithm constructs an explicit isomorphism be- tween G and a “standard” (or natural) representation H of G and exploits this isomorphism to write an arbitrary element ofGas a word in its defining generators.
For example, if G is an alternating group of degree n, then a constructive recognition algorithm sets up an isomorphism between Gand the standard copy H onnpoints generated by a 3-cycle and an (n−1)- orn-cycle.
Two algorithms which solve the word-problem for a given group, but do not (readily) fit the constructive recognition model, are outlined in Sections 7.4 and 7.5.
As part of their ongoing work on groups of Lie type, Cohen, Murray & Taylor [31] developed the generalised row and column reduction algorithm: for certain matrix representations, this algorithm writes an element of a group of Lie type as a word in its Steinberg generators. This isonecomponent of a solution to the word-problem for these groups. (Of course, we must first construct the Steinberg generators as words in the defining generators of the input group.)
1.5. An overview.
We aim to provide an introduction to this research topic; both its high level of activity and our current state of knowledge dictate that this is a report of “work in progress”. For an excellent survey of related topics, see Kantor & Seress [55].
While it is still too early to predict the final outcome of “matrix group recog- nition”, we believe that a realistic and achievable goal is to provide effective well- understood algorithms to answer many questions for linear groups of “small” de- gree. The principal outstanding practical obstacle is constructive recognition for classical groups, presented as matrix groups in defining characteristic. Increas- ingly, the division between the two approaches sketched in Section 1.3 is artificial.
While some algorithms are developed in a black-box context, usually under the assumption that oracles to perform certain tasks are available, their implemen- tations accept as input a linear group or a permutation group, where algorithms which are not black-box perform such tasks. Further, Mark Stather and others already exploit ideas from both approaches, and we expect that some mixture will ultimately prove most effective at a practical level.
In Section 2 we describe an order oracle for a linear group. Aschbacher’s classifi- cation of maximal subgroups of classical groups into nine categories is summarised in Section 3. Section 4 surveys existing algorithms to decide membership of the categories, and in Section 5 we discuss how to exploit the associated geometry.
In Section 6 we survey non-constructive algorithms which name the finite simple groups, and in Section 7 survey algorithms which solve the word-problem for these groups. Finally, we considershort presentationsfor simple groups, which may be used to verify that the results of randomised algorithms are correct.
2. Determining orders
A natural question is: determine the order of g ∈ GL(d, q). The task currently requires factorisation of numbers of the formqi−1, a problem generally believed not to be solvable in polynomial time. (Since GL(d, q) has elements of orderO(qd), we cannot simply compute powers ofg until we obtain the identity!)
Celler & Leedham-Green [28] present the following algorithm to compute the order ofg∈GL(d, q).
• Compute a “good” multiplicative upper boundE for|g|.
• Now factoriseE=Qm
i=1pαii where the primespi are distinct.
• If m = 1, then calculate gpj1 for j = 1,2, . . . , α1−1 until the identity is constructed.
• If m > 1 then express E = uv, where u, v are coprime and have approx- imately the same number of distinct prime factors. Now gu has order k dividingvandgk has order`say dividingu, and the order ofgisk`. Hence the algorithm proceeds by recursion onm.
How do we obtain a good multiplicative upper bound? Giveng, determine and factorise its minimal polynomial f(x) =Qt
i=1fi(x)mi where deg(fi) = di. Now β= logpmaxmi and set
E = lcm(qd1−1, . . . , qdt−1)×pβ.
Observe that|g|dividesE. Celler & Leedham-Green [28] prove the following:
Theorem 2.1. If we know a factorisation ofE, the cost of the order algorithm is O(d3logqlog logqd)field operations.
If we fail to complete the factorisation ofE, then we obtain apseudo-orderfor g – namely, a multiple of its order by some large prime(s). For most theoretical and practical purposes this suffices.
Implementations of the algorithm in bothGAP and Magmause databases of factorisations of numbers of the formqi−1, prepared as part of the Cunningham Project [18].
A related problem is the following. LetGbe a black-box group having an order oracle, and letNCG: determine the order of an element of G/N.
Leedham-Green & O’Brien [60] present an algorithm for this task. Let g∈G and letm be its order. The basic algorithm iterates the following operation for some preassigned number of times.
• a:= random element ofN;
• m:= gcd(m,|ga|);
It then returnsmas the estimate of the order of the image ofgin G/N.
If the basic algorithm returns m >1, we apply the following refinement. For every prime pdividing m, apply the basic algorithm to gm/p. If the algorithm returns 1 or any number prime to pas the order of the image of gm/p, then the order of the image ofg divides m/p; now repeat this refinement withmreplaced bym/p.
Babai & Shalev [9] prove the following:
Lemma 2.2. Let N be a simple non-abelian normal subgroup of G. The refined algorithm, with high probability, returns the order ofg modulo N as 1 ifg∈N.
Hence this algorithm can decide membership in a normal subgroup (provably so for one which is simple), and thus is important for working with quotients of black-box groups.
A consequence, of practical and theoretical importance, is a one-sided Monte Carlo algorithm to prove that a black-box group G is perfect: we prove that every generator of G is an element of its derived group and so learn that G is perfect. An implementation is available inMagma, and is used extensively in our implementation of the identification algorithm of Section 6.2.
3. Geometry following Aschbacher
As mentioned in the introduction, a classification of the maximal subgroups of GL(d, q) by Aschbacher [3] underpins the “geometric” approach to the study of linear groups. Let Z denote the group of scalar matrices ofG. ThenGisalmost simple modulo scalars if there is a non-abelian simple group T such that T ≤ G/Z≤Aut(T), the automorphism group ofT.
We summarise Aschbacher’s classification as follows: a linear group preserves some natural linear structure in its action on the underlying space and has a normal subgroup related to this structure, or it is almost simple modulo scalars.
More formally, we paraphrase the theorem as follows.
Theorem 3.1. Let V be the vector space of row vectors on which GL(d, q)acts, and letZ be the subgroup of scalar matrices of G. If Gis a maximal subgroup of GL(d, q), then one of the following is true:
C1. Gacts reducibly.
C2. G acts imprimitively: G preserves a decomposition of V as a direct sum V1⊕V2⊕ · · · ⊕Vr of r > 1 subspaces of dimensions, which are permuted transitively by G, and soG≤GL(s, q)oSym(r).
C3. Gacts onV as a group of semilinear automorphisms of a(d/e)-dimensional space over the extension field GF(qe), for some e >1 and so Gembeds in ΓL(d/e, qe). (This includes the class of “absolutely reducible” linear groups, where Gembeds inGL(d/e, qe).)
C4. G preserves a decomposition of V as a tensor productU ⊗W of spaces of dimensions d1, d2>1 overF. Then Gis a subgroup of the central product of GL(d1, q)andGL(d2, q).
C5. Gis definable modulo scalars over a subfield: for some proper subfieldGF(q0) of GF(q),Gg≤GL(d, q0).Z, for someg∈GL(d, q).
C6. For some primer,d=rm andG/Z is contained in the normaliser of an ex- traspecial group of orderr2m+1, or of a group of order22m+2 and symplectic- type.
C7. Gis tensor-induced: it preserves a decomposition ofV asV1⊗V2⊗ · · · ⊗Vm, where eachVi has dimensionr >1 and the set ofVi is permuted byG, and soG/Z≤PGL(r, q)oSym(m).
C8. Gnormalises a classical group in its natural representation.
C9. Gis almost simple modulo scalars.
Of course, the nine Aschbacher categories are not mutually exclusive. Further, seven have a normal subgroup associated with a decomposition.
In broad outline, this theorem suggests that a first step in investigating a linear group is to determine (at least one of) its categories in the Aschbacher classifica- tion. If a category is recognised, then we can investigate the group structure more completely using algorithms designed for this category. Usually, we have reduced the size and nature of the problem. For example, ifG≤GL(d, q) acts imprimi- tively, then we obtain a permutation representation of degree at mostdforG; ifG preserves a tensor product, we now consider two linear groups of smaller degree.
If a proper normal subgroupN exists, we recogniseN and G/N recursively, ulti- mately obtaining a composition series forG. Many questions about the structure ofGcan be answered by first considering its composition factors.
What of the almost simple groups? Liebeck [62] proved that the maximal non- classical subgroups of GL(d, q) have order at mostq3d, small by comparison with GL(d, q) which has orderO(qd2).
Further, the absolutely irreducible representations of degree at most 250 of all quasisimple finite groups are now explicitly known: see Hiss & Malle [43] and L¨ubeck [64]. (Recall thatGisquasisimple ifGis perfect and G/Z(G) is simple.) The algorithmic potential of these lists remains to be realised.
4. Membership of an Aschbacher category
We survey work on deciding if G≤ GL(d, F), where F = GF(q), acting on the underlying vector spaceV, is a member of the first seven Aschbacher categories. In Section 6.1 we report on a Monte-Carlo algorithm which decides ifGis in C8. We first consider an algorithm which plays an important role in such investigations.
4.1. The Smash algorithm.
In essence, theSmash algorithm presented in [46] is a constructive realisation of Clifford’s theorem [30].
Assume that G acts absolutely irreducibly onV. Let S ⊆Gcontain at least one non-scalar element. In summary, this algorithm investigates whether G has certain decompositions with respect to the normal closure hSiG. The possible decompositions correspond to categories in Aschbacher’s theorem.
We now consider these in more detail. LetN be a normal non-scalar subgroup of G. Then, for some t ≥ 1, V splits as a direct sum W1⊕W2⊕ · · · ⊕Wt of irreducible F N-modules, all of the same dimension. For some r, s0 ≥ 1, with rs0 = t, the Wis partition into r sets containing s0 pairwise isomorphic F N- modules each. IfV1, V2, . . . , Vrare each the sum ofs0 pairwise isomorphicWis, so thatV =V1⊕V2⊕ · · · ⊕Vr, thenGpermutes theVis transitively. Four situations arise:
• Ifr >1 thenGacts imprimitively onV (type C2).
• If r = 1 and t > 1 and the Wi are absolutely irreducible as F N-modules, thenV can be recognised as a tensor product preserved by G(type C4).
• If r= 1 and theWi are not absolutely irreducible as F N-modules, then G is semilinear (type C3).
• Otherwise, both r and t equal 1 and N acts absolutely irreducibly on V. NowN/Z(N) is a direct productN0×N0× · · · ×N0ofmcopies of a simple groupN0, andN is a central product ofmgroupsN1, each isomorphic to an extension ofZ(N) byN0. IfN0 is cyclic, thenGnormalises an extraspecial or symplectic-type group (type C6). Otherwise N0 is non-abelian simple.
If m = 1, G is almost simple, and Smash fails to find a decomposition;
otherwisem >1 andGis tensor-induced (type C7).
The complexity of the resulting algorithm is at worstO(d6) [46]. An implementa- tion is distributed withMagma.
4.2. Reducible groups.
The maximal subgroups in this category are the maximal parabolic subgroups.
If the action ofG onV is unipotent, then it is easy to diagonaliseG and we find a composition series for Gby elementary linear algebra. If there is a proper section S of V on which G acts non-trivially, then we write down the action of G on S; the kernel of the resulting homomorphism is the subgroup of G which centralises this section.
TheMeatAxeis a one-sided Monte Carlo algorithm to decide whether or not G acts irreducibly on V. The original algorithm, incorporating ideas of Norton and Parker, is described in [74]. It was generalised and analysed by Holt & Rees [45], a task completed by Ivanyos & Lux [52]. In summary, their algorithm is the following. Let M denote the F G-module and let A denote the F-algebra spanned by the generators ofG. Select a random elementθ of A, determine its characteristic polynomialc(x) ofθ, and factorise it. Letχ=p(θ) wherep(x) is an irreducible factor ofc(x). Henceχ has non-trivial nullspaceN. Ifp(x) is a factor of multiplicity one, thenN is irreducible as anFhθi-module. Now compute the F G-submodule of M generated by a single non-zero vector in N. If we obtain a proper submodule, we conclude that G acts reducibly on V; otherwise we must repeat the random selection a number of times.
The MeatAxe has complexity O(d3.5logq) [45], [52]. Implementations are distributed withGAPandMagma.
4.3. Imprimitive groups.
Groups in this category act irreducibly but imprimitively onV; maximal subgroups in this category are stabilisers of direct sum decompositions V = ⊕ri=1Vi where dim(Vi) =d/r=s. (A spaceVi is ablock, the set{V1, . . . , Vr} is ablock system.) IfGstabilises such a decomposition, then we obtain a homomorphismφ:G7−→
Sym(r) and its kernel is a normal subgroup ofG.
Holtet al. [47] present an algorithm to decide if an absolutely irreducible group Gacts imprimitively on its underlying spaceV.
One of its key components is the MinBlocks algorithm: given a non-trivial subspace of a block of imprimitivity, the algorithm finds the block system with minimal block dimension that contains this subspace.
TheSmashalgorithm of Section 4.1 applies whenGdoes not act faithfully on the system of blocks. If G has a block system containingr blocks of dimension s, then there is a homomorphism fromGtoSr. From a consideration of element orders and characteristic polynomials, we may discover that a particular non-scalar g∈Gmust lie in the kernel of the homomorphism fromGtoSr. If so, we construct its normal closure N = hgiG, and then search for a decomposition with respect toN.
If G acts faithfully as a permutation group on the blocks, then we seek to construct the stabiliser of a block.
Suppose that G acts imprimitively on V with blocks of dimension s, and let H be the stabiliser of one such block, W. Our strategy attempts to findH and W, or to establish that the assumption is false. IfW exists, thenV is isomorphic to the induced module WG, where W is regarded as an F H-module. Thus, W must be irreducible as anF H-module, since otherwiseV would not be irreducible as anF G-module. From [50, Chapter V, Satz 16.6], we have HomF G(WG, V)∼= HomF H(W, V). Since we assume thatV is an absolutely irreducibleF G-module, HomF G(WG, V) has dimension 1 overF. It follows that the onlyF H-submodule ofV that is isomorphic toW isW itself.
This suggests that we try to construct the stabiliser,H, of a fixed but unknown block,W, of dimensions. If we succeed in constructing H, then we can findW by first applying the MeatAxe algorithm to the action of H on V, and then, for eachF H-composition factorVi of dimension s, calculating HomF H(Vi, V). If HomF H(Vi, V) has dimension one, then W is the unique image in V of every nonzero homomorphism, and we can find the block system by applying Min- Blocksto this image.
We may assume that the permutation action of Gon the blocks is primitive, and so H must be a maximal subgroup of Gof index r. We try to construct H by working up a chain of subgroups, starting with a cyclic subgroup and then adjoining new generators. At some point in our construction, our investigations
may prove that no suchH exists, and so we can conclude thatGdoes not preserve a block system with block dimensions.
An implementation of the algorithm is distributed withMagma.
4.4. Semilinear groups.
Groups in this category preserve on V the structure of a vector space over an extension field of GF(q) and maximal subgroups in this category are GL(d/e, qe).e whereeis a prime dividingd.
Assume that the F G-moduleM is irreducible. Holt & Rees [45] describe an extension of the MeatAxe to determine the centralising field E of M together with a d×d matrix which generates E as a field over F. In particular, M is absolutely irreducible if and only ifE=F.
Holtet al. [46] present an algorithm to decide if an absolutely irreducible group acts semilinearly. In summary, we construct a subsetSof random elements of the derived group ofG, and now applySmashto decide ifGpreserves the appropriate decomposition with respect tohSiG=G0.
IfGis both imprimitive and semilinear, we may fail to decide thatGis semi- linear, since repeated calls toSmashalways conclude thatGacts imprimitively.
An implementation of the algorithm is distributed withMagma.
4.5. Tensor products.
Groups in this category preserve on V the structure of a tensor product of two subspaces, and maximal subgroups in this category are subgroups of the central product GL(e, q)◦GL(f, q) whered=ef.
Leedham-Green & O’Brien [58] provide a description of a tensor decomposition ofV in terms of a projective geometry whose flats are certain subspaces ofV. In [59] we exploit this geometrical approach and some other ideas to obtain a practical algorithm to decide tensor decomposability.
Here we summarise the approach, first recalling the concept of equivalence of tensor decompositions.
Definition 4.1. A u-tensor decomposition of V is a linear isomorphism αfrom U ⊗W onto V, where U and W are vector spaces, with U of dimension u. If α:U⊗W →V and β :U0⊗W0 →V areu-tensor decompositions ofV, thenα andβ areequivalentif there are linear isomorphismsφ:U →U0andψ:W →W0 such thatα= (φ⊗ψ)β.
IfV is anF G-module, whereF is the underlying field andGis a group, then a u-tensor decomposition of V as F G-module requiresU and W as above to be F G-modules, andαto be anF G-isomorphism; and in the definition of equivalence φandψare required to beF G-isomorphisms.
Au-projective geometry onV, whereudivides the dimension ofV, is a projec- tive geometry where the k-flats are of dimensionku, the join of two flats is their
sum, and their meet is their intersection. Thus, in au-tensor decomposition ofV, the subspaces ofV that are the images of subspaces ofU⊗W of the formU⊗W0, where W0 runs through the set of subspaces ofW, form au-projective geometry onV. More generally, au-tensor decomposition ofV asF G-module gives rise to a u-projective geometry onV whereW0runs through the set ofF G-submodules of W. This projective geometry isG-invariant, in that the set of flats isG-invariant.
In [58] it was shown that this construction of a u-projective geometry from a tensor decomposition ofV asF G-module sets up a one-to-one correspondence be- tween the set ofG-invariant projective geometries onV and the set of equivalence classes of tensor decompositions of V as F G-module. A point in the projective geometry corresponding to a u-tensor decomposition of V has dimension u as a subspace.
The following theorem is proved in [58].
Theorem 4.2. Let V be a vector space of dimension uw. For each u-tensor de- composition α : U ⊗W 7→ V, define F(α) to be {α(U ⊗X) : X ≤W}. Then the map [α] 7−→ F(α) is a bijection between the set of equivalence classes [α] of u-tensor decompositions ofV and the set of u-projective geometries onV.
In [58] an algorithmFindPoint having complexityO(d3) is presented: given as input a subspace F of V, it determines whether or not F is a flat in a G- invariant u-projective geometry on V, and, in the affirmative case, returns the corresponding tensor decomposition ofV.
Hence the problem of finding a tensor decomposition of an F G-moduleV as U ⊗W, where U and W are modules for a covering group of G, is equivalent to constructing a point in one of the two corresponding projective geometries: a subspace ofV of the form u⊗W orU⊗wforu∈U\ {0}orw∈W\ {0}.
We use two approaches to find a flat in a suitableG-invariant projective geom- etry, or to prove that no such geometry exists.
IfGdoes not act faithfully modulo scalars on one of the factors in the putative tensor decomposition, then (a variation of)Smash constructs the decomposition.
If Gacts faithfully modulo scalars on each of the factors in every tensor decom- position of V, then we consider the H-submodule structure of V for “suitable”
subgroupsH ofG. A subgroupHis suitable if it is guaranteed to act reducibly on at least one of the tensor factors, sayW, in every putative tensor decomposition.
Then at least one of the H-invariant subspaces of V is a non-trivial flat in the correspondingu-projective geometry.
Hence, to apply the algorithm successfully, we wish to construct H ≤Gthat normalises sufficiently few subspaces of V that we can process these subspaces, but which also acts reducibly onW if the required tensor factorisation exists. One simple criterion we employ is the following. If p is the characteristic of F and H is ap-local subgroup, thenH cannot act irreducibly in any dimension greater than one: the subspace ofV centralised by ap-group must be non-trivial, and this space is normalised byH.
Of course no suitableHmay exist and hence the algorithm may fail to complete;
our experience suggests that it is easy to construct the tensor decomposition, but
sometimes difficult to prove that no decomposition exists. An implementation of the algorithm is distributed withMagma.
4.6. Smaller field modulo scalars.
LetG=hXi be an absolutely irreducible subgroup of GL(d, K), and let F be a proper subfield of the finite fieldK.
Glasby, Leedham-Green & O’Brien [40] present an algorithm to decide con- structively whether or not Gis conjugate to a subgroup of GL(d, F).K×, where K× denotes the centre of GL(d, K).
Theorem 4.3. There is a Las Vegas algorithm that takes as input the finite fields F < K, and an absolutely irreducible group G:=hXi ≤GL(d, K), and decides in O(|X|d3)field operations in K, plus O∼(dlogq)field operations in F, whether or notG is conjugate to a subgroup of GL(d, F). If so, then a conjugating matrix is returned; otherwisefalseis returned.
The algorithm of Glasby & Howlett [39] has similar complexity but assumes a discrete logarithm oracle forF. Our algorithm avoids use of the discrete logarithm, and hence its performance is demonstrably better ifF is “large”.
A variation of Theorem 4.3 allows us to decide membership in the Aschbacher category.
Theorem 4.4. There is a Las Vegas algorithm that takes the same input as the algorithm in Theorem 4.3, but with the additional assumption that G0 acts abso- lutely irreducibly on the given KG-moduleV; if G is conjugate to a subgroup of GL(d, F)K×, it returns a conjugating matrix, or otherwise returns false. This algorithm has the same complexity as the algorithm in Theorem4.3.
We also generalise the algorithm of Theorem 4.4 in two ways to address the case whenGacts absolutely irreducibly, butG0 does not. It suffices, for the algorithm of Theorem 4.3 to produce a positive answer, that we find for eachg∈X a scalar kg∈K×such that ifg is replaced bykggthen the resulting set generates a group that can be conjugated into GL(d, F). Thus we find such scalars by considering the elements of X in turn, and then carry out a backtrack search through all possible scalars; in practice we restrict the choice of scalars significantly. The second approach is to use Clifford’s theorem [30] to analyse the structure of the KG-module.
An implementation of the algorithm is distributed withMagma.
4.7. Normalisers of p-groups.
Groups in this category are the normalisers of certain absolutely irreducible, symplectic-typer-groups, whereris a prime,da power ofrandq≡1 (modr).
Niemeyer [69] proved the following.
Theorem 4.5. Letpandrbe primes withr≥3. Letebe the smallest integer such that pe≡1 modr and put q =pe. Let R0 be a given embedding of a symplectic- type extraspecial r-subgroup R of orderr3 and exponent rintoGL(r, q). There is a constructive, one-sided Monte Carlo algorithm which takes as input a group G generated by a set X of matrices in GL(r, q) and decides whether or not G has a normal subgroup isomorphic to R0. The algorithm costsO(ξ+ (logrlog logr+ logq+|X|)µ+δ) field operations, whereµ is the cost of a group operation, ξ is the cost of selecting a random element, and δis the cost of finding an r-th root of an element inGF(q).
The general case is considered by Brooksbank, Niemeyer & Seress [23]. Imple- mentations of these algorithms are available inGAPand Magma.
4.8. Tensor-induced groups.
LetG≤GL(d, q) be tensor-induced. ThenGpreserves a decomposition ofV as U1⊗U2⊗ · · · ⊗Ur
where eachUihas dimensionu >1 andr >1, and the set ofUi is permuted byG.
Leedham-Green & O’Brien [60] present an algorithm to decide if Gis tensor- induced. We may readily reduce to the case whereGacts primitively on the set of tensor factors. In summary, we consider homomorphisms fromGonto aprimitive subgroup ofSr, and construct such mappings, or prove that none exists.
In particular, we construct a set of subsets ofGin one-to-one correspondence with the set of conjugacy classes of subgroups ofGof indexr, each subset gener- ating a group in the corresponding class.
The standard low-index subgroup algorithm described in [80] constructs such classes whenGis a finitely-presented group. Critically, the relations used to obtain subgroups of index at mostrdo not need to be satisfied byG, but rather byG/K where K is a normal subgroup contained in the intersection of the kernels of all homomorphisms ofGinto Sr.
We construct a generating set for a subgroupKofKr, the verbal subgroup of Gcorresponding to the variety generated bySr, by evaluating instances of some known laws of the variety. This we can do modulo the assumption thatrissmall.
(This is a realistic assumption: if we assume that d ≤ 500, then r ≤ 5, unless u= 2, in which caser≤8.)
We next obtain a presentation for a preimage ofG/K; here we use the algorithm of [60] to construct random elements of a normal subgroup, and the algorithm outlined in Section 2 to estimate the order of an element of Gmodulo a normal subgroup.
We apply the low-index subgroup algorithm to this presentation to construct subgroups of bounded index and obtain their preimages inG.
We next determine whether or not a subgroup M of appropriate index in G preserves a tensor decomposition of V with factors U of dimension uand W of
dimensionur−1. IfM does notpreserve such a tensor decomposition, then Gis not tensor-induced and the algorithm terminates.
If M preserves such a tensor decomposition, it remains to decide whether or notGis tensor-induced from a subgroup of indexr. In particular, we determine whether or notW can be decomposed intor−1 tensor factors of dimensionuin such a way that the resulting set ofr u-dimensional tensor factors ofV is permuted byG.
An implementation of the algorithm is distributed withMagma.
5. Exploiting the geometry
In ongoing work, Leedham-Green and O’Brien have developed the concept of a composition tree, which seeks to realise and exploit the Aschbacher classification.
Leedham-Green [57] provides a detailed description of this concept and its practical realisation. Here we summarise it briefly.
A composition series for a group R can be viewed as a labelled rooted binary tree. The nodes correspond to sections of R, the root node to R. A node that corresponds to a sectionKofR, and is not a leaf, has a left descendant correspond- ing to a proper normal subgroup N of K and a right descendant corresponding toK/N. The right descendant is an image under a homomorphism; usually these arise naturally from the Aschbacher category of the group, but we also exploit additional ones applying to unipotent and soluble groups. The left descendant of a node is the kernel of the chosen homomorphism.
The tree is constructed inright depth-first order. Namely, we process the node associated withK: ifK is not a leaf, construct recursively the subtree rooted at its right descendantI, then the subtree rooted at its left descendantN.
It is easy to construct I, since it is the image of K under a homomorphism φ. We generate a random element of N as follows. Let K = hx1, . . . , xmi, and letI=φ(K) =hx1, . . . , xmi. Choose random k∈K, and evaluateφ(k)∈I. By solving the word-problem forI, we establish thatφ(k) =w(x1, . . . , xm). Then the residuek·w(x1, . . . , xm)−1 ∈N. Hence, by selecting sufficient random elements ofK, we construct with high probability a generating set forN.
We assign to the root node R a set of random elements which are used for
“quality control” in constructing the composition tree. Their images and residues are determined for each new node constructed. We test if these random elements satisfy the homomorphism specified; if their images under the homomorphism are in the image; if the residues are in the kernel. If any of these tests fail, we know that the generating set for some kernel which is an ancestor of the node is not correct. We add more generators to this kernel and construct the subtree having this root again.
We solve the word-problemdirectlyfor aleaf– namely, a composition factor of the root groupR – using a variety of techniques which we survey in Section 7. If we solve the word-problem for the left and right descendants of a node, then we
readily solve the word-problem for the node, and so recursively obtain a solution for the root node. Hence, givenx∈GL(d, q), we can decide ifx∈R; if so, we can writexas a word in the user-supplied defining generators ofR.
Recently, Mark Stather refined the composition tree concept to construct a chief treeof a group, whose leaves are the chief factors of the group.
6. Non-constructive recognition
The algorithms to name a finite simple group exploit the concept of a primitive prime divisor.
Letb, ebe positive integers withb >1. A primerdividingbe−1 is a primitive prime divisor ofbe−1 if r|(be−1) butr6 |(bi−1) for 1≤i < e. Zsigmondy [87]
proved thatbe−1 has a primitive prime divisor unless (b, e) = (2,6) ore= 2 and b+ 1 is a power of 2. Recall that
|GL(d, q)|=q(d2)
d
Y
i=1
(qi−1).
Hence primitive prime divisors ofqe−1 for various e≤ddivide both the orders of GL(d, q) and of classical groups.
We say thatg∈GL(d, q) is a ppd(d, q;e)-element (or sometimes simply appd- element) if its order is divisible by some primitive prime divisor ofqe−1.
6.1. Classical groups in natural representation.
Much of the recent activity on algorithms for linear groups was stimulated by Neu- mann & Praeger [68], who presented a Monte Carlo algorithm to decide whether or not a subgroup of GL(d, q) contains SL(d, q).
Niemeyer & Praeger [71] answer the equivalent question for an arbitrary clas- sical group. Underpinning the work is a classification of the subgroups of GL(d, q) containing ppd-elements fore > d/2 obtained by Guralnicket al.[41]. In [71], they refine this classification, focusing on pairs of elements inGwhich are ppd(d, q;e1) and ppd(d, q;e2) for d/2 < e1 < e2 ≤ d. With few exceptions, if G contains such elements, then Gcontains one of the classical groups. They determine the proportion of such ppd-elements in classical groups, and also list the exceptions.
In summary, the resulting Monte Carlo algorithms are highly efficient, having complexityO(log logd(ξ+dω(logq)2)), whereξ is the cost of selecting a random element anddω is the cost of matrix multiplication.
For an excellent account of this and related work, see Praeger [76]. For a report on the resulting implementation, which is distributed withMagma, see [70].
6.2. Black-box groups of Lie type.
Babai et al. [8] present a black-box algorithm to name a group G of Lie type in known defining characteristic p. The algorithm selects a sample of random elements inG, and determines whether the orders of these elements are divisible by certain primitive prime divisors. From this divisibility information, it constructs theArtin invariantsofG: the leading invariant is usually the largestksuch that Gcontains elements of order ppd(p, k)-order. With certain exceptions, the Artin invariants determine G. The algorithm of Altseimer & Borovik [1] distinguishes between PΩ(2m+ 1, q) and PSp(2m, q) for oddq >3.
The central result of [8] is the following.
Theorem 6.1. Given a black-box group G isomorphic to a simple group of Lie type of known characteristic, the standard name of G can be computed using a polynomial-time Monte Carlo algorithm.
In 2001 Malle and O’Brien developed a practical implementation of the result- ing algorithm. Our procedure takes as input a quasisimple group in known defining characteristic. We also include identification procedures for the other quasisimple groups. If the non-abelian composition factor is alternating or sporadic, then we identify it by considering the orders of random elements. Our implementation is distributed withGAPandMagma.
Observe that Theorem 6.1 assumes that the defining characteristic of the input group of Lie type isknown. The algorithm of Kantor & Seress [54] to determine the characteristic does not appear to be practical; an alternative was developed by Liebeck & O’Brien [63] and our implementation is distributed withMagma.
7. Solving the word-problem
We focus on approaches which solve the word-problem – and sometimes provide much additional information – for simple groups.
7.1. Black-box classical groups.
Cooperman, Finkelstein & Linton [36] made a critical breakthrough, presenting a constructive recognition algorithm for GL(n,2).
This inspired the work of Kantor & Seress [53]; in summary, they prove the following.
Theorem 7.1. There is a Las Vegas algorithm which, when given as input a black- box perfect groupG≤GL(d, q)where G/Z(G)is isomorphic to a classical simple groupCof known characteristic, produces a constructive isomorphismG/Z7−→C.
A partial implementation of the algorithm, developed by Brooksbank, Seress and others, is available inGAPandMagma. The algorithm is not polynomial in the size of input: its running time has a factor ofq=pebecause a necessary step is to find an element of orderp.
Recall thatg∈Gisp-singularif its order is divisible byp. A group of Lie type having defining characteristic p has a small proportion of p-singular elements.
Combining the results of Isaacs, Kantor & Spaltenstein [51] and Guralnick &
L¨ubeck [42], we obtain the following.
Theorem 7.2. If Gis a group of Lie type defined overGF(q), then 5q2 < ρ(G)<
5
q, whereρ(G)denotes the proportion of p-singular elements in G.
Brooksbank & Kantor [22] identify that the obstruction to a polynomial-time algorithm for constructive recognition of the classical groups is PSL(2, q). Babai
& Beals [7] formulate the problem explicitly as follows.
Problem 7.3. Find an element of orderpinPSL(2, pe)as a word in its defining generators in polynomial time.
Sinceρ(PSL(2, q))≤2/q, a random search will involveO(q) selections.
A consequence of the work of Landazuri & Seitz [56] is that the degree of a faithful projective representation of PSL(2, q) in cross characteristic is polynomial in q rather than in logq. Hence the critical case is a matrix representation of SL(2, q) in defining characteristic.
Conder & Leedham-Green [32] and Conder, Leedham-Green & O’Brien [33]
present an algorithm which constructively recognises SL(2, q) as a linear group in defining characteristic in time polynomial in the size of the input. The principal result is the following.
Theorem 7.4. LetGbe a subgroup ofGL(d, F)ford≥2, whereF is a finite field of the same characteristic as GF(q); assume thatGis isomorphic modulo scalars toPSL(2, q). Then, subject to a fixed number of calls to a discrete log oracle for GF(q), there is a Las Vegas algorithm that constructs an epimorphism from Gto PSL(2, q)at a cost of at most O(d5τ(d)) field operations, whereτ(d) denotes the number of divisors of d.
Underpinning our work is a well-known characterisation of the absolutely irre- ducible representations of SL(2, q), due to Brauer & Nesbitt [15].
Theorem 7.5. LetKbe a finite field of characteristicp, and letV be an absolutely irreducible KG-module forG= SL(2, q), where q=pe. Suppose thatV cannot be written over a smaller field. Then K is a subfield of GF(q), and V ⊗K GF(q)' T1⊗T2 ⊗ · · · ⊗Tt, where Ti is the si-fold symmetric power Si of the natural GF(q)[G]-module M twisted by the fith power of the Frobenius map, with 0 ≤ f1< f2<· · ·< ft< e, and1≤si< p for alli.
Letq be a power of a primep, and letV be a finite-dimensional vector space over a finite field of characteristic p. In summary, our algorithm takes as input a subset X of the linear group GL(V) that generates a group G isomorphic to SL(2, q) or to PSL(2, q), and constructs the natural projective representation ofG by constructing the image ofX under a homomorphism ofGonto PSL(2, q).
How do we find a transvection in the natural representationH of SL(2, q)? We find by random search an elementaof orderq−1 inH, and a random conjugate b of a. Next we construct c ∈ H and an integer i such that bic and a have a common eigenvector. Observe that [a, bic] is a transvection. While a suitable c can be found easily, computingirelies on a discrete logarithm oracle.
Brooksbank [19], [21] and Brooksbank & Kantor [22] have exploited this work to produce better constructive recognition algorithms for black-box classical groups.
Kantor & Seress [55] summarise the outcome as follows.
Theorem 7.6. There is a Monte Carlo algorithm which, when given as input a black-box G such that C = G/Z(G) is PSL(d, q), PSp(2m, q) or PSU(d, q) and a constructive recognition oracle forSL(2, q), outputs a constructive isomorphism G/Z(G)7−→C. The running time of the resulting algorithms is a polynomial in the input length plus the time of polynomially many calls to theSL(2, q)oracle.
For example, the complexity of Brooksbank’s algorithm [21] for PSU(d, q) is O(d2logd(ξ+χlogq+dlog4q), whereξis the cost of selecting a random element andχis the cost of an SL(2, q)-oracle.
Recently Brooksbank & Kantor [24] developed an algorithm having similar complexity for the orthogonal groups.
7.2. Classical groups in their natural representation.
The algorithm of Celler & Leedham-Green [29] for constructive recognition of SL(d, q) in its natural representation has effective costO(d4q). Recently, Brooks- bank [20] developed similar algorithms for other classical groups in their natural representation: their effective cost is O(d5log2q), subject to calls to an SL(2, q) oracle.
In ongoing work, Leedham-Green and O’Brien are developing new algorithms for the classical groups, given as linear groups in defining characteristic; these use an SL(2, q) oracle and their complexity involves logq.
7.3. Alternating groups.
Bealset al.[11] prove the following.
Theorem 7.7. Black-box groups isomorphic to An or Sn with known value of n can be recognised constructively, inO(ξn+µ|X|nlogn)time, whereξ is the time to construct a random element,µ is the time for a group operation, andX is the input generating set for the group.
Beals et al. [12] present an alternative linear group algorithm designed for the deleted permutation module. Implementations of these algorithms are available in GAPand Magma.
An alternative algorithm, developed by Bratus & Pak [16], was further refined and implemented inMagmaby Derek Holt.
7.4. Using centralisers of involutions.
The centraliser of an involution in a black-box group having an order oracle can be constructed using an algorithm of Bray [17].
Assume we wish to construct elements of CG(h), for involution h∈G. Con- struct a conjugate hk of h, where k is a random element of G. Let D be the dihedral group generated byhandhk, and let the order ofDbe 2n.
(i) If n is odd, D contains an element t such that ht = hk. Then tk−1 is an element of CG(h).
(ii) If n is even, D contains a central involution x. Then x and xk−1 both centraliseh.
It is easy to prove that the elements of CG(h) produced under step (i) are uniformly distributed. Parker & Wilson [75] prove that certain classical groups contain “sufficient” elements of this type having odd order.
Theorem 7.8. There is an absolute constant c such that if G is a finite simple classical group, with natural module of dimensiondover a field of odd characteris- tic, andhis an involution inG, then[h, g]has odd order for at least a proportion c/dof the elementsg∈G.
Borovik [13] considers involution centralisers in the study of black-box groups and announced a weaker version of this theorem. A result similar to Theorem 7.8 is also established for the exceptional groups in [75].
For each sporadic group we can calculate explicitly the proportion of [h, g]
which have odd order. Since, for every class of involutions, this proportion is at least 17%, we can readily construct centralisers.
The centraliser-of-involution algorithm [44] reduces the problem of testing whether an arbitrary g ∈ G is a member of H ≤ G to instances of the same problem for CH(t) for (at most) three involutions t ∈H. The algorithm is con- structive: ifg∈H then it returns a word forgin the generators ofH.
We summarise the algorithm. Assume we are given a black-box group Gwith an order oracle,g∈G, and a subgroupH ofG. We wish to decide whether or not g∈H.
1. Findh∈H such that|gh|= 2`. Now definez= (gh)`.
2. Findx, anH-involution, such that|xz|= 2m. Now definey= (xz)m.
3. ConstructX =CH(x) and decide ify∈X. 4. If so, construct Y =CH(y) and decide ifz∈Y. 5. If so, construct Z=CH(z) and decide ifgh∈Z.
Note thathx, ziisD2m having central involutiony= (xz)m. Hencey is in the centraliser ofxandzis in the centraliser ofy.
If any of the membership tests fail, we immediately conclude that g 6∈ H;
otherwise, on termination, we have proved thatg∈H. An implementation is distributed withMagma.
7.5. The Schreier-Sims approach.
Underpinning most effective algorithms for permutation groups is the concept of abase and strong generating set (BSGS).
Let a group G act faithfully on Ω = {1, . . . , n}. Recall that a base for G is a sequence of points B = [β1, β2, . . . , βk] such that the sequence stabiliser Gβ1,β2,...,βk= 1. This structure determines a chain of stabilisers
G=G(1)≥G(2)≥ · · · ≥G(k)≥G(k+1)= 1,
whereG(i)=Gβ1,β2,...,βi−1. Astrong generating set corresponding toBis a subset S ofGsuch thatG(i)=
S∩G(i)
, fori= 1, . . . , k.
The central task is the construction of basic orbits – the orbitBi of the base point βi+1 under G(i). Observe that |G(i) :G(i+1)|=|Bi|, abasic index. Using Schreier’s Lemma, Sims [79] presented a deterministic algorithm to construct the required strong generating sets. For an analysis of the algorithm, see Seress [77, p. 64].
By contrast, the random Schreier-Sims, introduced by Leon [61], finds gener- ating sets by considering random elements ofG. It is usually significantly faster and provides smaller strong generating sets. In practice, it terminates when some stopping conditionbecomes true. Usually, we stop when a predetermined number, N, of consecutive random elements have all been found to be redundant as strong generators. If the random elements are uniformly distributed, the probability that we do not have a complete BSGS is now less than 2−N. If the order ofGis known in advance, we can terminate when the product of basic indices reaches this value.
Of course, there is a natural faithful action of a linear group G≤GL(d, q) on the underlying vector spaceV = GF(q)d: namely,vg=v·g forv∈V andg∈G.
Hence we can apply the Schreier-Sims algorithm toG and construct a BSGS for its action on the vectors of V, where the base points are standard basis vectors forV. Observe however that the size ofV isqdand so growsexponentiallywithd.
The basic orbits obtained are usually very large; if Gis a simple group, the first basic index is often|G|.
By choosing base points which give shorter basic orbits, we extend signifi- cantly the range of application of the Schreier-Sims. Butler [25] first developed
the Schreier-Sims algorithm for linear groups, choosing as base points the one- dimensional subspaces of V. Murray & O’Brien [67] developed a more general strategy for selecting base points for linear groups which we expect a priori to have “small” orbits. In summary, we select some common eigenvectors for a col- lection of random elements of the group, and use related spaces to obtain a base.
Most critical to the successful application of the Schreier-Sims algorithm is the index|G(i):G(i+1)|. WhileSn has a subgroup of indexn, the “optimal” subgroup chain for GL(d, q) is
GL(d, q)≥qd−1.GL(d−1, q)≥GL(d−1, q)≥. . .
where the leading index is qd−1 and so grows exponentially with d. Further, many linear groups have no “small-degree” permutation representation and so no useful stabiliser-chain. For example, the largest maximal subgroup of the sporadic simple groupJ4 has index 173 067 389.
Despite these limitations, the algorithms underpin most of the long-standing machinery for computing with linear groups. Implementations are available in GAPandMagma, and are very effective for “small” degree representations defined over “small” fields. While the model borrows heavily from permutation groups, it does not write down an explicit permutation representation for the group, relying instead on a stabiliser-chain. See, for example, the algorithm of Butler & Cannon [26] to construct centralisers of elements of linear groups.
An algorithm which uses subset chains to solve the word-problem for black-box groups is described by Ambroseet al.[2].
7.6. Sporadic groups.
Wilson [84] introduced the concept ofstandard generatorsfor the sporadic groups.
He and others provide black-box algorithms for their construction. Generating sets for maximal subgroups, representative of conjugacy classes and other struc- tural information are now obtained by evaluating known words in these standard generators. For further details, see theAtlasWEB site [85].
For each sporadic group, O’Brien & Wilson [72] present black-box algorithms which construct chains of subgroups. For a specific matrix representation, each chain now determines a stabiliser chain for (variations of) the Schreier-Sims algo- rithm. Some subgroups in the chain act reducibly on the underlying vector space;
hence we construct a module composition series, and, by estimating orbit sizes, select “good” base points for the Schreier-Sims algorithm. With this assistance, the Schreier-Sims or the centraliser-of-involution algorithm [44] solves the word- problem for allAtlasrepresentations [85] of most sporadic groups; the exceptions are the Baby Monster and the Monster where strategies developed by Wilson and others are employed [86]. Implementations are available inMagma.
8. Presentations for groups
Most of the algorithms surveyed here are randomised; Monte Carlo or Las Vegas in nature, they rely on random selections.
How do we verify the results obtained? For example, how do we prove that the composition tree for a given group Gis correct? One method of verification is to use a presentation. By constructing a composition tree forG, we obtainM, a group with composition factors the leaves. Then|M| ≤ |G|, perhaps properlyif we fail to construct completely the kernel of a homomorphism. We now construct a presentation forM and verify thatGsatisfies the relations forM. HenceGis a quotient ofM and we conclude thatG=M.
Since we must evaluate relations, we are interested in “short” presentations.
Thelengthof a presentation is the number of symbols needed to write the presen- tation. A presentation forGisshortif its length is O(log2|G|).
Combining the results of Babaiet al.[6], Hulpke & Seress [49], and Suzuki [83], we obtain the following.
Theorem 8.1. For every finite simple group except2G2(q)there is a known short presentation.
For Lie rank at least 2, these are reduced versions of the Curtis-Steinberg-Tits presentations.
Conder, Leedham-Green & O’Brien [34] prove the following.
Theorem 8.2. The alternating and symmetric groups of degree n have presen- tations on logn generators, where the number of relators is O(logn), and the presentation length isO(lognlog logn).
This represents a significant improvement over known (Coxeter) presentations which have length O(n2). The consequent shorter presentations for the classi- cal groups are described in [35].
References
[1] Christine Altseimer and Alexandre V. Borovik. Probabilistic recognition of orthogo- nal and symplectic groups. InGroups and Computation, III (Columbus, OH, 1999), volume 8 ofOhio State Univ. Math. Res. Inst. Publ., pages 1–20. de Gruyter, Berlin, 2001.
[2] Sophie Ambrose, Max Neunh¨offer, Cheryl E. Praeger and Csaba Schneider. Gener- alised sifting in black-box groups. LMS J. Comput. Math., 8:217-250, 2005.
[3] M. Aschbacher. On the maximal subgroups of the finite classical groups. Invent.
Math., 76:469–514, 1984.
[4] L´aszl´o Babai. Local expansion of vertex-transitive graphs and random generation in finite groups.Theory of Computing, (Los Angeles, 1991), pp. 164–174. Association for Computing Machinery, New York, 1991.
[5] L. Babai. Randomization in group algorithms: conceptual questions. InGroups and Computation, II (New Brunswick, NJ, 1995), 1–17, Amer. Math. Soc., Providence, RI, 1–17, 1997.
[6] L. Babai, A.J. Goodman, W.M. Kantor, E.M. Luks, and P.P. P´alfy. Short presen- tations for finite groups.J. Algebra, 194(1):79–112, 1997.
[7] L´aszl´o Babai and Robert Beals. A polynomial-time theory of black box groups. I.
InGroups St. Andrews 1997 in Bath, I, volume 260 of London Math. Soc. Lecture Note Ser., pages 30–64, Cambridge, 1999. Cambridge Univ. Press.
[8] L´aszl´o Babai, William M. Kantor, P´eter P. P´alfy, and ´Akos Seress. Black-box recognition of finite simple groups of Lie type by statistics of element orders. J.
Group Theory, 5(4):383–401, 2002.
[9] L´aszl´o Babai and Aner Shalev. Recognizing simplicity of black-box groups and the frequency ofp-singular elements in affine groups. InGroups and ComputationIII, Ohio State Univ. Math. Res. Inst. Publ., pages 39–62. de Gruyter, Berlin, 2001.
[10] L´aszl´o Babai and Endre Szemer´edi. On the complexity of matrix group problems, I. InProc.25th IEEE Sympos. Foundations Comp. Sci., pages 229–240, 1984.
[11] Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Cheryl E. Praeger, and ´Akos Seress. A black-box group algorithm for recognizing finite symmetric and alternating groups. I. Trans. Amer. Math. Soc., 355(5):2097–2113, 2003.
[12] Robert Beals, Charles R. Leedham-Green, Alice C. Niemeyer, Cheryl E. Praeger, and ´Akos Seress. Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules. J. Alge- bra, 292:4–46, 2005.
[13] A.V. Borovik. Centralisers of involutions in black box groups. In Computational and statistical group theory (Las Vegas, NV/Hoboken, NJ, 2001), 7–20,Contemp.
Math., 298, Amer. Math. Soc., Providence, RI, 2002.
[14] Wieb Bosma, John Cannon, and Catherine Playoust. TheMagmaalgebra system I: The user language. J. Symbolic Comput., 24:235–265, 1997.
[15] R. Brauer and C. Nesbitt. On the modular characters of groups, Ann. of Math.
42:556–590, 1941.
[16] Sergey Bratus and Igor Pak. Fast constructive recognition of a black box group isomorphic toSn or An using Goldbach’s conjecture.J. Symbolic Comput.29:33–
57, 2000.
[17] John N. Bray. An improved method for generating the centralizer of an involution.
Arch. Math. (Basel), 74:241–245, 2000.
[18] John Brillhart, D.H. Lehmer, J.L. Selfridge, Bryant Tuckerman, and S.S.
Wagstaff, Jr. Factorizations of bn ±1, volume 22 of Contemporary Mathe- matics. American Mathematical Society, Providence, RI, second edition, 1988.
http://www.cerias.purdue.edu/homes/ssw/cun/index.html.
[19] Peter A. Brooksbank. A constructive recognition algorithm for the matrix group Ω(d, q). InGroups and Computation, III (Columbus, OH, 1999), volume 8 ofOhio State Univ. Math. Res. Inst. Publ., pages 79–93. de Gruyter, Berlin, 2001.
[20] Peter A. Brooksbank. Constructive recognition of classical groups in their natural representation. J. Symbolic Comput., 35:195–239, 2003.
[21] Peter A. Brooksbank. Fast constructive recognition of black-box unitary groups.
LMS J. Comput. Math., 6:162–197 (electronic), 2003.
[22] Peter A. Brooksbank and William M. Kantor. On constructive recognition of a black box PSL(d, q). InGroups and Computation, III (Columbus, OH, 1999), volume 8 ofOhio State Univ. Math. Res. Inst. Publ., pages 95–111. de Gruyter, Berlin, 2001.
[23] Peter Brooksbank, Alice C. Niemeyer and ´Akos Seress. A reduction algorithm for matrix groups with an extraspecial normal subgroup. These Proceedings.
[24] Peter A. Brooksbank and William M. Kantor. Fast constructive recognition of black box orthogonal groups.J. Algebra, 2006.
[25] Gregory Butler. The Schreier algorithm for matrix groups. In SYMSAC ’76,Proc.
ACM Sympos. symbolic and algebraic computation, pages 167–170, New York, 1976.
(New York, 1976), Association for Computing Machinery.
[26] Gregory Butler and John J. Cannon. Computing in permutation and matrix groups I: Normal closure, commutator subgroups, series.Math. Comp., 39:663–670, 1982.
[27] Frank Celler, Charles R. Leedham-Green, Scott H. Murray, Alice C. Niemeyer and E.A. O’Brien. Generating random elements of a finite group.Comm. Algebra, 23:4931–4948, 1995.
[28] Frank Celler and C.R. Leedham-Green. Calculating the order of an invertible ma- trix. In Groups and Computation II, volume 28 of Amer. Math. Soc. DIMACS Series, pages 55–60. (DIMACS, 1995), 1997.
[29] F. Celler and C.R. Leedham-Green. A constructive recognition algorithm for the special linear group. InThe atlas of finite groups: ten years on (Birmingham, 1995), volume 249 ofLondon Math. Soc. Lecture Note Ser., pages 11–26, Cambridge, 1998.
Cambridge Univ. Press.
[30] A.H. Clifford. Representations induced in an invariant subgroup. Ann. of Math., 38:533–550, 1937.
[31] Arjeh M. Cohen, Scott H. Murray, and D.E. Taylor. Computing in groups of Lie type. Math. Comp. 73:1477-1498, 2003.
[32] Marston Conder and Charles R. Leedham-Green. Fast recognition of classical groups over large fields. InGroups and Computation, III (Columbus, OH, 1999), volume 8 ofOhio State Univ. Math. Res. Inst. Publ., pages 113–121. de Gruyter, Berlin, 2001.
[33] M.D.E. Conder, C.R. Leedham-Green, and E.A. O’Brien. Constructive recognition of PSL(2, q). Trans. Amer. Math. Soc., 358:1203-1221, 2006.
[34] M.D.E. Conder, C.R. Leedham-Green, and E.A. O’Brien. Short presentations for alternating and symmetric groups. Preprint, 2005.
[35] M.D.E. Conder, C.R. Leedham-Green, and E.A. O’Brien. Short presentations for classical groups. Preprint, 2005.
[36] G. Cooperman, L. Finkelstein, and S. Linton. Constructive recognition of a black- box group isomorphic to GL(n,2). In Groups and Computation II, volume 28 of Amer. Math. Soc. DIMACS Series, pages 85–100. (DIMACS, 1995), 1997.
[37] Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic pro- gressions.J. Symbolic Comput. 9:251–280, 1990.
