Computing with Matrix Groups using Permutation Representations

Gene Cooperman^{1}

Larry Finkelstein^{1}

{gene,laf,misha}@ccs.neu.edu College of Computer Science

Northeastern University Boston, MA 02115 / U.S.A.

Michael Tselman^{1}

Abstract

Permutation representations constructed from matrix groups defined over finite fields often have very high degree. New techniques are presented for performing effective computations with the resulting permutation group. These techniques are designed to work in an environment in which the degree of the permutation group is considered too large to permit the use of standard permutation algorithms for solving problems such as computing the order of the group and testing simplicity. The theory has been successfully tested on a representation of the sporadic simple group Ly, discovered by Lyons [10]. In [5], a permutation representation was constructed for Ly of degree 9, 606, 125 on a conjugacy class of subgroups of order 3. Using this permutation representation and no specific knowledge of the group, we are able to apply our methods to construct a base of at most four points for the resulting permutation group, compute its order and verify simplicity. Monte Carlo algorithms for group membership presented in [2] are used to improve the performance of these algorithms.

1 Introduction

A well known technique for computing with subgroups of the general linear group GL(n, q) is to construct a permutation representation for the group and then apply algorithms for computing with permutation groups. Previous efforts at constructing a permutation representation have relied on the action of the matrix group on the set of (q^{n} − 1)/(q − 1) one dimensional subspaces of the underlying vector space V. Software based on ideas of Butler [4], Leon [9] and Sims [12] has been available for years, first in Cayley and later in GAP and Magma. However, the size of the permutation domain grows quickly with n beyond the limitations of modern technology, forcing us to look for other actions.

In [5], we have developed practical methods for constructing the permutation representation from the conjugacy action on a conjugacy class O of subgroups of prime

1Partially supported by NSF Grant CCR-920449.

Int. Symp. on Symbolic and Algebraic Computation (ISSAC-95), ACM Press, 1995, pp. 259–264; copyright ACM order. The key idea is to assign to each subgroup of the conjugacy class a signature that can be efficiently computed and can be used as an index into a hash table T used to store the permutation domain. The signature is computed by taking a randomly chosen vector v and assigning to each subgroup, the image of v under a generator of the subgroup. This allows us to replace matrix-matrix multiplication by vectormatrix multiplication in the course of building T , thereby saving a factor of n in the time to construct T .

In this paper, we assume that a permutation representation has been constructed for G acting on O and present efficient methods for constructing a base for G^{O} and for testing simplicity of G^{O}.

The key to the construction of a base for G^{O} is the fact that each point of O has group theoretic significance, namely a subgroup of G. However, when |O| is very large, space becomes an overriding concern. For example, in in the case of the Lyons sporadic simple group, Ly, |O| has size 9, 606, 125 and so each permutation requires approximately 38MB of storage (assuming a four byte word per entry).

For permutation domains of the size required for Ly, it is difficult to store more than a handful of permutations, and so we have developed the theory for constructing a base in which permutations are never explicitly computed, but rather the hash table T is used to compute the action of a group element, stored as a matrix, on a point of the permutation domain. This increases the time required to perform this operation, in comparison to a simple array reference in the permutation domain, but allows us to store a significant number of group elements represented as matrices in the course of building a strong generating set. For example, in the matrix representation of Ly in GL(111, 5), each group element stored as a matrix requires only 12KB of storage (assuming one byte per matrix entry). Furthermore, the use of the signature described above reduces the complexity of computing the image of a point under the action of a group element in this hybrid setting. The details of the construction are presented in section 3.

Given a base in advance, there are numerous strategies available for computing a strong generating set for G^{O}, and hence determining |G^{O}|. One strategy is to use a heuristic procedure to obtain a candidate strong generating set S and then verify that strong generating set using either the Monte Carlo test described in [2] or the deterministic Brownie-Sims Verify test implemented in Magma. We omit discussion of these techniques in this paper, since they are already well described elsewhere.

In section 4 we give an elementary simplicity test for G^{O}. This algorithm also exploits the fact that the points of the permutation domain have group theoretical significance.

2 Construction of a Permutation Representation

In [5] we described how to construct a permutation representation from the conjugation action on a conjugacy class of subgroups of prime order. The motivation for this approach is twofold.

• For many important examples, a permutation representation with close to minimal degree can be constructed in this manner.

• Each subgroup in the conjugacy class has an efficiently computable signature.

The first statement is partially justified by a theoretical result of Babai and Beals [1]. Specifically, if G is simple and ν(G) is the degree of the smallest permutation representation for G, then their result asserts that when G is simple, there is always a conjugacy class of subgroups of prime order whose size is bounded by ν(G)^{c}, for some positive constant c. (W.M. Kantor has indicated to the authors that one can take the bound to be c = 2.) Babai and Beals use this result as the basis for a theory of computing with black box groups.

The second statement is justified by the use of the image of a random vector v as signature, as described in the introduction. It is valid to use v as a signature if and only if no non-identity element of G fixes v. In general, this is a hard condition to test, but if prior knowledge of the group structure is available, lower bounds can be established on the probability that a randomly chosen vector has this property. For example, in the case of Ly, this probability is at least 1 − 3.8 × 10^{−23} [5]. Without knowledge of the group structure, it is still possible to give a lower bound of 1 − 1/q on the reliability of the enumeration, by employing a simple test based on the probability that a randomly chosen vector lies in the fixed point subspace of a non-identity element of G. This will be presented in a forthcoming paper [6].

3 Verification of a Base for a Conjugation Action

Let C be a conjugacy class of G consisting of elements of prime order p and let O = {⟨x⟩: x ∈ C}. We define the permutation representation:

π : G ↦ Sym(O)

by ⟨x⟩^{π(g)} = ⟨g^{−1}xg⟩ = ⟨x⟩^{g} for each x ∈ C, g ∈ G.

For simplicity, we refer to this permutation representation as the conjugation action of G on O. The first result gives a description of the kernel of this action.

Lemma 3.1 If K is the kernel of the action of G on O, then either K = C_{G}(C), or C_{G}(C) is properly contained in K and ⟨C⟩ is an elementary abelian subgroup.

Proof: By definition, K = {g ∈ G: ⟨x⟩^{g} = ⟨x⟩, ∀⟨x⟩ ∈ O}. Clearly C_{G}(C) ⊆ K. Therefore, if K commutes with C, then K = C_{G}(C). We may assume for the remainder of the proof, that C_{G}(C) ≠ K. By construction, K normalizes ⟨x⟩ for each ⟨x⟩ ∈ O. Further, x normalizes K, since K ◁ G . So,

[K, ⟨x⟩] ⊆ ⟨x⟩ ∩ K = 1 or ⟨x⟩ ∀⟨x⟩ ∈ O,

since x has prime order. But K ≠ C_{G}(C) implies that [K, ⟨x⟩] ≠ 1 for at least some ⟨x⟩ ∈ O. In this case, [K, ⟨x⟩] = ⟨x⟩. Therefore, x ∈ K, which implies that C ⊆ K since C is a conjugacy class of G and K ◁ G. It now follows that ⟨C⟩ is elementary abelian. □

C generates an elementary abelian group precisely when C is in the kernel of the action on O. Testing if C is in the kernel is easy since this condition is true if a single element of C acts trivially on O. In the case where ⟨C⟩ is elementary abelian, it is more appropriate to consider the linear action of G on ⟨C⟩ rather than the permutation action and therefore we assume the following for the remainder of this section.

Assumption 3.2 ⟨C⟩ is non-abelian.

As a consequence of this assumption, we then have from Lemma 3.1 that G/C_{G}(C) acts faithfully on O.

We now consider the task of finding a base for G acting on O. The construction of a base requires two steps. The first is to find a set B ⊆ C with the property that C_{G}(B) = C_{G}(C). Note that B can be characterized as a base for the conjugation action of G on C. If O_{B} = {⟨b⟩ : b ∈ B}, then O_{B} is “close” to being a base for G^{O}. The second step is to extend O_{B} to a base for G^{O}. Lemma 3.9 is the key to performing this extension.

The proper setting for constructing B is either the natural embedding of G in the full matrix ring Mat(n, q) or else the homomorphic image of G as a subgroup of Sym(O). Because the arguments are similar, we adopt notation that emphasizes the general nature of the proof. We define two algebraic objects H and Ḡ = G/K. Either H = Mat(n, q) and K=1, so that G = Ḡ, or else H = Sym(O) and K = C_{G}(C). Note that G acts by conjugation as a group of automorphisms of Mat(n, q) and thus familiar group theory definitions such as C_{H}(B), B ⊆ C and N_{G}(M) for M a G-invariant subalgebra of Mat(n, q) make sense. Also, we assume in the case H = Mat(n, q) that whenever we conjugate by an element h ∈ H, that h is a unit in H, i.e. that h ∈ GL(n, q).

Lemma 3.3 If B̄^{h} commutes with C_{H}(B̄) for B̄ ⊆ Ḡ, h ∈ H, then h normalizes C_{H}(B̄).

Proof: Note that B̄^{h} commutes with C_{H}(B̄) implies that C_{H}(B̄) ⊆ C_{H}(B̄^{h}) = C_{H}(B̄)^{h}. But |C_{H}(B̄)| = |C_{H}(B̄)^{h}| and so C_{H}(B̄) = C_{H}(B̄)^{h}. □

Theorem 3.4 Assume a generating set S for G and an element b ∈ C are known. One can find a set, B ⊆ C, of at most log_{2} |G| elements satisfying CḠ(B̄) = CḠ(C̄). Let t be an upper bound on the time to compute C_{H}(B̄′) for B̄′ ⊆ B, and let k be an upper bound on the time to compute if an element of H commutes with C_{H}(B̄′). Then the time to compute B is O(|B||S|k + |B|t).

Proof: The algorithm can be simply described as follows.

Starting with B = {b}, b ∈ C Compute C_{H}(B̄) While there exists (b, g) ∈ B × S untested

If b̄ḡ does not commute with C_{H}(B̄) Add b^{g} to B Compute C_{H}(B̄)

It is claimed that when there are no more untested pairs, CḠ(B̄) = CḠ(C̄). Since ⟨B⟩ ⊆ G and the elements of B form a non-redundant generating set for ⟨B⟩, |B| ≤ log_{2} |G|.

The proof divides into two cases. In the first case, assume that NḠ(C_{H}(B̄)) is proper in Ḡ. Then there exists a g ∈ S, for which ḡ ∉ NḠ(C_{H}(B̄)). By Lemma 3.3, B̄ḡ and C_{H}(B̄) do not commute. So, there is a b ∈ B such that b̄ḡ does not commute with C_{H}(B̄), and our algorithm finds a new pair (b, g) and augments B.

In the second case, NḠ(C_{H}(B̄)) = Ḡ. This implies that for all ḡ ∈ Ḡ, C_{H}(B̄ḡ) = C_{H}(B̄)ḡ = C_{H}(B̄). Hence B̄ḡ commutes with C_{H}(B̄). But C̄ = b̄Ḡ, and so C̄ commutes with C_{H}(B̄). In particular, CḠ(B̄) ⊆ CḠ(C̄). Since the reverse inclusion is clearly true, we may infer that CḠ(B̄) = CḠ(C̄) as claimed.

Given the defined parameters k and t, the timing follows directly from the algorithm. □

When H = Sym(O), so that Ḡ = G/C_{G}(C), it may be the case that CḠ(C̄) is non-trivial. The next results shows that when this happens, G^{O} is imprimitive and this leads to a permutation representation of smaller degree.

Corollary 3.5 If H = Sym(O) and C_{H}(C̄) is non-trivial, then the set of orbits of C_{H}(C̄) forms a proper block system for Ḡ.

Proof: Since Ḡ acts transitively on O and C_{H}(C̄) is normalized by Ḡ, the set of orbits of C_{H}(C̄) forms a block system for Ḡ. In order to show that the block system is proper, it suffices to show that C_{H}(C̄) acts intransitively on O. By Assumption 3.2, ⟨C⟩ is non-abelian and so ⟨C̄⟩ is a non-trivial subgroup of Ḡ by Lemma 3.1. Since C is a conjugacy class of G, C ∩ C_{G}(C) = ∅. This implies that each x ∈ C acts non-trivially on O but does have fixed points, for example, ⟨x⟩. In particular, each element of C̄ has fixed points on O. It then follows that C_{H}(C̄) acts intransitively as required. □

This result shows how to construct a non-trivial system of imprimitivity for Ḡ acting on O when H = Sym(O) and C_{H}(C̄) is non-trivial. In this case, we can construct a permutation representation for G acting on the set of orbits of C_{H}(C̄) which will have smaller degree than the one for G acting on O and we work with this one instead. Thus for the remainder of the section, we assume that the following assumption holds.

Assumption 3.6 If H = Sym(O), then C_{H}(C̄) = 1.

Under Assumption 3.6, if H = Sym(O) and B is chosen by the algorithm in Theorem 3.4, then B̄ satisfies C_{H}(B̄) = C_{H}(C̄) = 1. Since B ⊆ C, C_{G}(C) ⊆ C_{G}(B), and this implies that C_{G}(B) = C_{G}(C). We can then extract from Theorem 3.4 the following criteria.

Corollary 3.7 B is a base for G^{C} if [B̄S̄, C_{H}(B̄)] = 1.

Remark The most expensive part of the algorithm used to construct B is computing the subgroup C_{H}(B̄), either when H = Mat(n, q) or when H = Sym(O). In the case where H = Mat(n, q), this can be accomplished by solving a system of |B|n^{2} linear equations in n^{2} variables, based on the matrix equations AX = XA where A ∈ B and X represents an arbitrary element of C_{H}(A). In general, the time to solve such a system is O(|B|rn^{4} log q) where r is the rank of the system with n ≤ r ≤ n^{2}. A special case that is important in practice is when ⟨C⟩ acts irreducibly on the underlying vector space. In this case, C_{H}(C) is a field GF (q^{r}) where r|n and G can be viewed as an absolutely irreducible subgroup of GL(n/r, q^{r}). An algorithm for computing C_{H}(C) in this case is described in [7].

The next lemma sometimes provides a faster way to verify that B is a base for G^{C}. The proof is clear.

Lemma 3.8 If ⟨B⟩ is transitive in its conjugate action on C, then B is a base.

The previous results allow us to to obtain a base B for the conjugation action of G on C. By Lemma 3.1 and Assumption 3.2, G/C_{G}(C) has a faithful, transitive representation on O. The following result is the start point for extending O_{B} = {⟨b⟩ : b ∈ B} to a base for G^{O}.

Lemma 3.9 Assume that B is a base for G^{C}. Let Γ = ∪_{⟨b⟩∈O_{B}} ⟨b⟩^{⟨B⟩} ⊆ O and let L be the point stabilizer G_{O_{B}} of O_{B}. Then L/C_{G}(C) acts faithfully on Γ and the action of an element of L on Γ is uniquely determined from its action on each ⟨b⟩ ∈ O_{B}. In particular, this shows that |L/C_{G}(C)| ≤ (p − 1)^{|O_{B}|} and L/C_{G}(C) is abelian.

Proof: To prove that L/C_{G}(C) acts faithfully on Γ, it suffices to show that G_{Γ} = C_{G}(C). Let K = G_{Γ}. Since B leaves Γ invariant, it follows that K is normalized by ⟨B⟩. On the other hand, K normalizes each subgroup of O_{B}, and thus

[K, ⟨b⟩] ⊆ K ∩ ⟨b⟩, ∀⟨b⟩ ∈ O_{B}.

Since ⟨b⟩ ≅ Z_{p} for some prime p, either K commutes with B, or else there exists ⟨b⟩ ∈ O_{B} with [K, ⟨b⟩] = ⟨b⟩. If the latter occurs, then b ∈ K, and so b normalizes, and hence centralizes each ⟨b′⟩ ∈ O_{B}. This implies that b ∈ C_{G}(B) = C_{G}(C), which contradicts Assumption 3.2. Thus K commutes with B and so K = C_{G}(C) as required.

Now, let h ∈ L. The action of h on ⟨b⟩ ∈ O_{B} is determined by a rule that specifies the value of b^{h} ∈ ⟨b⟩, for each ⟨b⟩ ∈ O_{B}. We must show that this rule uniquely determines the action of h on Γ. Let ⟨y⟩ be a point of Γ. Then there exists b_{0} ∈ B and b = b_{1}b_{2} ⋯ b_{k} ∈ ⟨B⟩ with each b_{i} ∈ B, such that ⟨y⟩ = ⟨b_{0}⟩^{b}. But then ⟨y^{h}⟩ = ⟨b_{0}^{bh}⟩ = ⟨b_{0}^{hb′}⟩ = ⟨b_{0}^{b′}⟩ where b′ = b_{1}^{h}b_{2}^{h} ⋯ b_{k}^{h}.

Since each element of L/C_{G}(C) is uniquely determined by its action on the points of O_{B}, it follows that |L/C_{G}(C)| ≤ (p − 1)^{|O_{B}|}. To show that L/C_{G}(C) is abelian, it suffices to prove that the commutator [x, y] of arbitrary elements x, y ∈ L acts trivially on each ⟨b⟩ ∈ O_{B}. But this follows from the fact that x and y normalize ⟨b⟩ and Aut(⟨b⟩) is abelian. □

Lemma 3.9 and the next lemma allow us to deduce an upper bound on the size of a base for G^{O}.

Lemma 3.10 (from [2], Lemma 5.1) Let G ⊆ Sym(Ω) act transitively on Ω. Let b be the size of a minimal base for G and m the minimal size of support for a non-identity element of G. Then bm ≥ |Ω|.

Corollary 3.11 G has a base of size at most |O_{B}|(1 + log_{2}(p − 1)). Consequently, the minimal support of an element of G acting on O is at least |O|/|O_{B}|(1 + log_{2}(p − 1)). In particular, if p = 3, then G has a base of size at most 2|O_{B}| and the minimal support of an element is at least |O|/(2|O_{B}|).

Lemma 3.9 and Corollary 3.11 give us the tools to extend the base O_{B} into a base for the action of G on O. Lemma 3.9 provides (p − 1)^{|O_{B}|} candidates for elements of L. Let H be the set of (p − 1)^{|O_{B}|} − 1 rules that specify the possible action of a non-identity element of L on the |O_{B}| subgroups ⟨b⟩ ∈ O_{B}. For each h ∈ H, the rules prescribed by h allows one to compute ⟨y⟩^{h} without knowing in advance that there exists a corresponding element of L (or even of GL(n, q)).

The following code describes a randomized algorithm for extending O_{B} to a base O_{B′} of G^{O}. The algorithm is Las Vegas in the sense that the only uncertainty is how long the procedure takes, but the answer returned is always correct.

Set O_{B′} ← O_{B}, H′ ← H While H′ ≠ ∅

Let ⟨y⟩ ∈ Γ be randomly chosen For each h ∈ H′

If ⟨y⟩^{h} ≠ ⟨y⟩ Set H′ ← H′ \ {h} If ⟨y⟩ ∉ O_{B′}

Append ⟨y⟩ to O_{B′}

Corollary 3.11 shows that for a fixed element of H, the probability of a random ⟨y⟩ ∈ Γ being moved by h is at least 1/|O_{B}|(1 + log_{2}(p − 1)). Thus with constant probability, after we have examined |O_{B}|(1+log_{2}(p−1)) randomly chosen points, we find a ⟨y⟩ moved by h. In particular, with constant probability, the procedure described above terminates after we have examined 2^{|O_{B}|}|O_{B}|(1+log_{2}(p−1)) randomly chosen elements of O. This works fairly well when |O_{B}| is small. Further work is required to make it efficient when |O_{B}| is “large”.

4 Verification of Simplicity

We continue with the notation of section 3. Thus C = {x^{g} : g ∈ G} and O = {⟨x^{g}⟩ : g ∈ G}. In this section, we present an elementary test for simplicity of the permutation representation of G on O. We operate under Assumption 3.2, so that C is not in the kernel of the permutation representation. Thus, by Lemma 3.1, Ḡ = G/C_{G}(C) acts faithfully on O. We assume that we know a base and strong generating set for G, and hence the order of G. We also assume that G is primitive. Otherwise, G has a permutation representation of smaller degree and we use that one instead.

Observe that {⟨xz⟩ ∈ O : z ∈ C_{G}(C)} is a block of O containing ⟨x⟩. By our assumption of primitivity, this block must be trivial. Hence if [x, g] ∈ C_{G}(C), then [x, g] = 1. In particular, for each x ∈ C, CḠ(x̄) = C̄_{G}(x). As a consequence of this fact, we may assume that C_{G}(C) = 1 and that Ḡ = G.

Proposition 4.1 If K is a regular normal subgroup of G, then K is an elementary abelian r-subgroup for some prime r.

Proof: The stabilizer in G of the point ⟨x⟩ ∈ O is N_{G}(⟨x⟩). Since K is a regular normal subgroup of G, it follows that N_{K}(⟨x⟩) = 1. In particular, C_{K}(x) = 1. An equivalent formulation is that K admits a fixed point free automorphism x of order p. By a theorem of Thompson, ([8], Kapitel V, Haupsatz 8.14) K is nilpotent. But G^{O} is primitive, and so K must be an elementary abelian r subgroup for some prime r. □

Proposition 4.2 Let N = ⟨C⟩. Then one of the following two cases occurs:

1. G has a regular normal subgroup K, and N = ⟨x⟩K.

2. G has a unique minimal normal subgroup H and N = ⟨x⟩H.

Proof: By the previous result, if K is a regular normal subgroup of G, then K is an elementary abelian r subgroup for some prime r. But then G = KN_{G}(⟨x⟩) and (1) follows. To prove (2), we may assume that G does not have a regular normal subgroup. In this case, G has a unique minimal normal subgroup H, which must be transitive. Thus if g ∈ G, then g = g_{1}h where g_{1} ∈ N_{G}(⟨x⟩) and h ∈ H. Thus

(⟨x⟩)^{g_{1}h} = (⟨x⟩)^{h} ⊆ ⟨x⟩H,

which implies that N ⊆ ⟨x⟩H. On the other hand, since N contains both ⟨x⟩ and H, equality follows. □

It is fairly straightforward to apply this proposition to test the simplicity of G. First compute N = ⟨C⟩. If |N| < |G|, then G is not simple. So, assume that G = N. Case (1) can only arise if |G| involves exactly two distinct primes. But then G is solvable by Burnside’s theorem. Thus if |G| involves more than 2 primes, then we can assume that N = H⟨x⟩ where H is the unique minimal normal subgroup of G.

At this point, simplicity can be verified by showing that x ∈ H, or equivalently that x ∈ [N, N]. An alternative way to verify that x ∈ H is to check if x is conjugate in G to one of its distinct powers.

5 Application to Lyon’s Group

In this section, we assemble the pieces that relate to the construction of the Lyons group. This has the useful side effect of testing the methods described in the previous sections on a large example of independent interest. Initially, we were given two matrices, α, β ∈ GL(111, 5), where |α| = 2 and |β| = 5. These matrices were developed by Robert Wilson and provided to us by Klaus Lux. We assume that we have constructed the hash table T used to store O but do not know the exact structure of G. The goal is to apply the techniques developed in sections 3 and 4.

The first step in constructing a base using the theory developed in section 3 is to construct a subset B ⊆ C with the property that C_{G}(B) = C_{G}(C). In executing the algorithm described in Theorem 3.4, if it is suspected that ⟨C⟩ acts absolutely irreducibly on V, so that C_{G}(C) ⊆ C_{GL(n,q)}(C) = Z(GL(n, q)), then it suffices to find a subset B ⊆ C so that ⟨B⟩ acts absolutely irreducibly as well. One can use the following heuristic.

Initialize B to 3 randomly chosen elements of C While ⟨B⟩ does not act absolutely irreducibly on V

Add a randomly chosen element of C to B

The test for absolute irreducibility can be performed using Parker’s Meataxe [11] as implemented in GAP. In the case at hand, this procedure terminates after one iteration, which yields a set B containing three elements satisfying C_{G}(B) = C_{G}(C).

The next step is extending O_{B} to a base for G^{O}. This is done through application of the procedure described in section 3. In particular, this procedure finds only one additional base point, thus yielding a base O_{B′} with precisely four points.

There are numerous strategies available for computing a strong generating set for G^{O} given a base in advance. Because we suspect that G^{O} is isomorphic to the Lyons group, one strategy is to use a heuristic procedure to obtain a candidate strong generating set S and then use either the Monte Carlo strong generating test described in [2] or the deterministic Brownie-Sims Verify routine as implemented in Magma. The knowledge of a small base in advance speeds up both procedures.

In describing the heuristic procedure for computing S, we denote the base points by ⟨b_{i}⟩, i = 1, …, 4, with ⟨b_{1}⟩ understood to be the root of the tree T_{1} used to store O. The construction of T_{i} uses the method described in [5] and employs the same vectors for computing signatures.

Initialize S ← S and Σ_{1} ← S For i = 2 to 4 do

Let Σ_{i} be c_{i} randomly chosen Schreier generators

computed using Σ_{i−1} and T_{i−1} Compute T_{i} with root ⟨b_{i}⟩ and generating set Σ_{i} Append Σ_{i} to S

In each case, the Schreier generators stored in Σ_{i} are computed from a randomly chosen element of T_{i} and Σ_{i}. In this sense, the Schreier generator may be characterized as randomly chosen from amongst all possible Schreier generators. In general though, one can not show that with constant probability, such an element enlarges the current point stabilizer subgroup generated by Σ_{i}. This is why the procedure is heuristic. The parameters c_{2}, c_{3}, c_{4} are inputs to the procedure. In the application at hand, c_{2} and c_{3} were set to 100 and c_{4} was set to 1, since Σ_{4} contained only the identity element. The sizes of T_{2} and T_{3} are respectively 7,185,024 and 750. It should be further noted that the total storage required for all the data structures T_{i} is slightly more than the storage needed for 3 permutations acting on 9, 606, 125 points. The storage required for the Schreier generators is negligible in comparison, which is why we have the luxury of choosing 100 Schreier generators for each point stabilizer subgroup.

The next step is to apply to S one of the strong generating tests referred to earlier. In either test, one necessarily has to sift an element of the group through the data structures T_{i}, i = 1, 2, 3. In the matrix domain, we do not have to perform any matrix multiplications. This follows from the existence of the vector v = v_{init} that was used for constructing signatures. So, for example, if we are attempting to sift g ∈ G_{{⟨b_{1},...,b_{i−1}⟩}} through T_{i}, then the algorithm described in [5] will hash into the table T_{i} using the two signature vectors v^{g^{−1}b_{i}g} and v^{g^{−1}b_{i}^{2}g}. The result is a word w_{i} such that w_{i} ∈ G_{{⟨b_{1},b_{2},...,b_{i−1}⟩}} and gw_{i}^{−1} fixes ⟨b_{i}⟩. In this way, we see that sifting at each level only involves vector-matrix computations. The total complexity is related to the total depths of the trees T_{i}, i = 1, 2, 3. The depths of the trees T_{1} and T_{2} are 5 and 3 respectively, while the 750 elements of T_{3} can be stored directly. At any rate, in sifting, we save a factor of 111, or n in general.

Having verified the strong generating set, and hence the order of G^{O}, we now wish to verify simplicity. We use the method described in section 4. In the case where |G^{O}| = |Ly|, primitivity on O can be checked from the size of the orbits of the point stabilizer, since any block is a union of a subset of these orbits and the size of a block divides |O|. Proving that ⟨C⟩^{O} = G^{O} can be reduced to verifying that ⟨B⟩^{O} = G^{O}. The easiest way to do this, again working within our space constraints, is to start from scratch, but this time with generating set B instead of {α, β} and constructing the permutation representation on ⟨b_{1}⟩^{⟨B⟩} ⊆ O. This can be done more efficiently than in the initial computation of a strong generating set for G^{O}, since we know in advance, |G^{O}| and |T |_{i}, i = 1, 2, 3. Finally, we “suspect” that each x ∈ C is inverted by 1/2 of the elements in G_{⟨x⟩}^{O}, and so finding an element that confirms this fact is easy. This certifies the simplicity of the permutation group.

6 Acknowledgments

The authors gratefully acknowledge discussions with the following people: Alexander Hulpke, Bill Kantor, Wolfgang Lempken, Steve Linton, Gene Luks, Klaus Lux, Gerhard Michler, Reiner Staszewski and Michael Weller. The authors especially acknowledge that the matrix generators for the Lyons group, for which these techniques were tested, were developed by Robert Wilson and provided to us by Klaus Lux. Finally, we thank Bill Kantor for originally suggesting the “testbed” of the Lyons group.

7 Bibliography

References

[1] L. Babai and R. Beals, “Las Vegas Algorithms for Matrix Groups”, Proc. 24th IEEE FOCS (1993), pp. 427– 436.

[2] L. Babai, G. Cooperman, L. Finkelstein and Á. Seress, “Nearly Linear Time Algorithms for Permutation Groups with a Small Base”, Proc. of the 1991 International Symposium on Symbolic and Algebraic Computation (ISSAC ’91), Bonn, pp. 200–209, July, 1991.

[3] R. Beals, “Computing blocks of imprimitivity for smallbase groups in nearly linear time,” DIMACS Series in Discrete Mathematics and Theoretical Computer Science 11, 1993, pp. 17–26, L. Finkelstein and W.M. Kantor (eds.), AMS, Providence, RI. 11, 1993, pp. 17–26, L. Finkelstein and W.M. Kantor (eds.), AMS, Providence, RI.

[4] G. Butler, “The Schreier Algorithm for Matrix Groups”, SYMSAC ’76 (Proc. 1976 ACM Symp.on Symbolic and Algebraic Computation. Yorktown Heights, 1976) R.D. Jenks (ed.). ACM. New York. pp 167-170.

[5] G. Cooperman, L. Finkelstein, B. York and M. Tselman, “Constructing Permutation Representations for Large Matrix Groups”, Proc. of International Symposium on Symbolic and Algebraic Computation (ISSAC ’94), ACM Press, pp. 134–138.

[6] G. Cooperman, L. Finkelstein, M. Tselman and B. York, “Constructing Permutation Representations for Matrix Groups”, preprint.

[7] D. F. Holt and S. Rees “Testing modules for irreducibility”, manuscript.

[8] B. Huppert, “Endliche Gruppen I”, Springer Verlag, New York, 1967.

[9] J. Leon, “On an Algorithm for Finding a Base and Strong Generating Set for a Group Given by a Set of Generating Permutations”, Math. Comp. 35 (1980), pp. 941–974.

[10] R. Lyons, “Evidence for a New Finite Simple Group”, Journal of Algebra, 20 (1972), 540–569.

[11] R. Parker, ‘The computer calculation of modular characters. (The Meat-Axe)’, in M. Atkinson (ed.), Computational Group Theory, Academic Press, London, 267-74, 1984.

[12] C.C. Sims, “Computation with Permutation Groups”, in Proc. Second Symposium on Symbolic and Algebraic Manipulation, edited by S.R. Petrick, ACM Press, New York, 1971, pp. 23–28.

[13] C.C. Sims, “The Existence and Uniqueness of Lyons Group”, Proceeding of the Gainseville Conference, (1972), pp 138–141.