DIMACS Series in Discrete Mathematics and Theoretical Computer Science Volume 00, 0000

Group Membership for Groups with Primitive Orbits

NAMITA SARAWAGI, GENE COOPERMAN, AND

LARRY FINKELSTEIN

Abstract. This paper considers a permutation group G = ⟨S⟩ of degree n with t orbits such that the action on each orbit is primitive. It presents a O(tn^{2} log^{c}(n)) time Monte Carlo group membership algorithm for some constant c. The algorithm is notable for its use of a new theorem showing how to find O(t log^{2} n) generators in O˜ (|S|n) time under a more general form of the above hypotheses. The algorithm relies on new combinatorial methods for computing with groups [CF92] and previous work of Babai, Luks and Seress [BLS88]. In addition, it makes extensive use of a structure theorem for primitive groups by Cameron [Cam81], which can be derived from results of Kantor [Kan79] and the classification of finite simple groups.

1. Introduction

New combinatorial methods for computing with permutation groups have recently been developed which have led to Monte Carlo algorithms for solving fundamental problems that have superior worst case asymptotic performance [BCF^{+}91, BCF^{+}^{+}91, CF92]. The main objective of this paper is to explore the power of these methods when additional assumptions are made concerning the nature of the action on the underlying point set. In particular, we prove the following result. We use the notation O˜ (f(n)) to mean O(f(n) log^{c} n) for some constant c. This work is based on the thesis of Sarawagi [Sar92].

Theorem 1.1. Let G = ⟨S⟩ be a group acting on Ω, such that S ⊆ Sym(Ω), |Ω| = n, G has t orbits, and the action of G on each orbit is primitive. Then

1991 Mathematics Subject Classification. Primary 20C40, 20P05. The authors were supported in part by NSF Grants # CCR-8903952 and CCR-9204469. This paper is in final form and no version of it will be submitted for publication elsewhere.

\begin{matrix}c \\ ◯ \end{matrix}0000 American Mathematical Society 0000-0000/00 $1.00 + $.25 per page

a strong generating set for G can be determined in O˜ (n|S| + tn^{2}) Monte Carlo time.

The proof of Theorem 1.1 is based on the procedure SGS Primitive Orbits in section 2 and given in Theorem 2.1.

The algorithm used to prove Theorem 1.1 relies on a classification of the orbits of a permutation group (Theorem 3.8). This classification of the primitive orbits makes extensive use of the classification of finite simple groups through a result of Cameron [Cam81], which in turn relies on work of Kantor [Kan79]. For our purposes, if G is a permutation group on an n-element set Ω and O is an orbit of G with G^{O} primitive, then O is a small base orbit if |G^{O}| < |O|^{5 log |O|} (Definition 3.13). The Cameron orbits (Definition 3.7) include all orbits that are not small base. In the latter case the structure of G^{O} is well determined by Theorem 3.9. In the special case where G^{O} contains Alt(O) we use an elegant algorithm for finding a 3-cycle due to Babai, Luks and Seress [BLS88]. If such an orbit is not small base, it is called a giant (Definition 3.13), as in [BLS87]. Note that if O is a giant orbit, then |O| ≥ 35 (since otherwise |G^{O}| < |O|^{5 log |O|}).

The algorithm proceeds in two phases. As a pre-processing step, the giant orbits are recognized and the points are re-ordered so that the points of the giant orbits are last in the ordering.

The first phase, described in section 3, uses a typical Sims-type control structure [Sim]. One finds a strong generating set for the action of the group on a non-giant orbit O, and generators for the pointwise set stabilizer of O. The action of the stabilizer subgroup on the next non-giant orbit is then considered. The key to this phase is controlling the number of Schreier generators for each point stabilizer subgroup as we proceed through a sequence of base points in O. Two techniques are used to achieve this control. First, it is noted that if O is a Cameron orbit, then the action on O, of the point stabilizer subgroup, is faithful on its second smallest orbit. Further, the length of that orbit is at most 3\sqrt{|O|}. Second, a new theorem on reduction of generators is proved (Theorem 3.15), which shows that if we are given O^{∼}(t) generators for the current point stabilizer subgroup, then one can efficiently construct a generating set of size O^{∼}(t) for the next point stabilizer subgroup which guarantees that the total time to “process” the orbit is O^{∼}(nt|O|) Monte Carlo time. This reduction is accomplished using a generalization of combinatorial techniques first introduced in [BCF^{+}91] (see also [CF92] in this volume) rather than sifting. An interesting consequence of these techniques is the following corollary to Theorem 3.15 (for H = G).

Corollary 1.2. Let G = ⟨S⟩ be a group acting on Ω with |Ω| = n, and suppose G has t orbits, and the action of G on each orbit is primitive. Then a generating set for G containing O(t log^{2} n) elements can be constructed in O^{∼}(n|S|) Monte Carlo time.

In the second phase, described in section 5, one begins with generators for a normal subgroup N of G which is the pointwise set stabilizer in G of all non-giant orbits. Initially one works with the socle of N, denoted Soc(N). Because each giant orbit has size at least 35, the projection of Soc(N) on a remaining orbit is either trivial or a giant. The key to finding a strong generating set for Soc(N) is the “fast-giant” technique developed by Babai, Luks and Seress [BLS88], which allows the construction of a 3-cycle from a generating set for a giant in O^{∼}(n^{2}) Las Vegas time. Also needed is a fast normal closure algorithm described in [BCF^{+}91] The full strong generating set can then be constructed by viewing N/Soc(N) as a subgroup of an elementary abelian 2-group, and employing techniques of linear algebra.

The algorithms we present in this paper are all Monte Carlo. A Monte Carlo algorithm is a randomized algorithm whose reliability (probability of success) can be increased at the cost of additional time. The Monte Carlo nature of the main algorithm arises through multiple invocations of Monte Carlo subroutines. The subroutines have some small probability of returning an incorrect answer, and multiple invocations of the algorithms can lead to a large overall probability of error. However, all of the subroutines satisfy the property that if they run in time c for some input, and if they are allowed to run for an additional factor of time, t, then the probability of error will be ce^{−t}. Under these circumstances, one can always argue that if such an algorithm is invoked k times, then allowing an additional factor of t = log k time for each invocation will cause the overall probability of error to be bounded by c. The details of the argument are contained in Theorem A.2 of the appendix of [CF92], and formal definitions and related theorems are contained in the same appendix. Thus, some additional number of log n factors suffice to retain a reasonably small probability of error and for this reason, we may omit explicit proofs of reliability.

2. Overview of the Main Algorithm

In this section, we provide an overview of our main algorithm and the supporting subroutines. In order to highlight the underlying algorithmic ideas, we defer the formal timing analyses until later sections.

The ordering of Ω ultimately is determined by the algorithm as it processes the orbits in a top down fashion. We will denote by O_{j}, the j^{th} orbit which has been processed and set O^{(i)} = ∪_{j=1}^{i−1}O_{j} for 1 ≤ i ≤ t + 1.

  Procedure SGS Primitive Orbits

Input: (S, Ω) where ⟨S⟩ = G acts on Ω and has t primitive orbits Output: A set U which is an SGS for G

Replace S by S′ such that G = ⟨S′⟩ and |S′| = O˜ (t)

     Test Giants(S, Ω)

Reorder Ω = ∪_{i=1}^{t}O_{i} such that giant orbits are last Initialize S′′ ← S′, i ← 1 and U ← ∅ While i ≤ t and O_{i} is a non-giant orbit do

      (U′, S′′) ← SGS Non-Giant & Orbit Stabilizer(S′, S′′, O_{i}, Ω)

[U′ is a SGS for G_{O^{(i)}}^{O_{i}} and G_{O^{(i+1)}} = ⟨S′′⟩] Add U′ to U Let A be the union of non-trivial orbits of ⟨S′′⟩

     Add SGS Giant Orbits(S′′, A) to U

Return U

Theorem 2.1. The procedure SGS Primitive Orbits is correct and runs in O˜ (n|S| + tn^{2}) Monte Carlo time.

Proof. The first step is to ensure that |S| is not too large. This is accomplished using Theorem 3.3, which shows how to replace S by a generating set S′ so that |S′| = O˜ (t) in O˜ (n|S|) Monte Carlo time. The algorithm then classifies the orbits into types giant and non-giant. This can be done in O˜ (tn^{2}) time (see Section 4). Using this classification, the orbits are reordered so that the nongiant orbits appear before the giant orbits. Let t′ be the number of non-giant orbits.

  For each i, 1 ≤ i ≤ t′, SGS Non-Giant & Orbit Stabilizer(S′, S′′, O_{i}, Ω)

is invoked. This routine outputs a SGS, U′, for G^{O^{(t′+1)}} and generators S′′ for G_{O^{(t′+1)}} in O˜ (tn|O_{i}| + n^{2}) Monte Carlo time by Theorem 3.1. Furthermore, the size of S′′ is O^{∼}(t).

Continuing with i, t′ < i ≤ t, either G_{O^{(t′+1)}}^{O_{i}} is a giant or acts trivially. If the action is that of a a giant, the algorithm invokes the procedure SGS Giant Orbits using the generators for G_{O^{(t′+1)}}. It is shown in Theorem 5.2 that this phase is correct and takes O˜ (tn^{2}) Monte Carlo time. Hence SGS Primitive Orbits is correct and runs in the stated time.

3. Non-Giant Primitive Orbits

The iterative step in the main algorithm for a non-giant orbit can be formulated as follows. We are given a generating set S of size O^{∼}(t) for the normal subgroup N = G_{O^{(i)}} of G. We must produce a set U of strong generators for N^{O^{(i)}} and a generating set S′ for N_{O^{(i)}} = G_{O^{(i+1)}} of size O^{∼}(t). This is accomplished by the next procedure.

  Procedure SGS Non-Giant & Orbit Stabilizer

Input: (S, S′, O, Ω) where S, S′ ⊂ Sym(Ω), |S| = O˜ (t), |S′| = O˜ (t), N = ⟨S′⟩ ⊴ G = ⟨S⟩, G has t primitive orbits and O is a non-giant G orbit. Output: A set U ⊂ N which is an SGS for N^{O} and a generating set S′′ for N_{O} of size O˜ (t).

Let x_{1} be an arbitrary point of O Let O′_{x_{1}} be the smallest orbit of G_{x_{1}} acting on O \ {x_{1}} Reorder the points of O such that x_{1} is first followed by O′_{x_{1}} Set S′′ ← S′, U ← ∅ For each consecutive base point x_{i} (i ≥ 1) in O do Let T be O^{∼}(1) elements of ⟨S′′⟩ such that x_{i}^{⟨T ⟩} = x_{i}^{N_{x_{1},... ,x_{i−1}}} [T is constructed using Lemma 3.2(ii).] Add T to U Let C be a transversal for N_{x_{1},... ,x_{i}} in N_{x_{1},... ,x_{i−1}} built from T Let S_{i} be a set of Schreier generators for N_{x_{1},... ,x_{i}} built from S′′ and C Replace S′′ by a generating set for N_{x_{1},... ,x_{i}} of size O^{∼}(t) built from S_{i} [S′′ is constructed using the argument in Theorem 3.15]

Output U and S′′

Theorem 3.1. The procedure SGS Non-Giant & Orbit Stabilizer runs in Monte Carlo time O^{∼}(n|O|t) and outputs a generating set of size O^{∼}(t) for the point stabilizer of O.

Proof. The proof can be understood by quoting results from Sections 3.2 and 3.3 and deferring formal definitions and proofs of these results until those sections.

We analyze the time to construct S′′ through each iteration of the loop, since this will dominate the running time for the procedure. First observe that by Lemma 3.17 the hypotheses of Theorem 3.15 are satisfied with regard to the subgroup N_{x_{1},... ,x_{i}}.

If log |G^{O}| ≤ 5 log^{2} n (O is a small base orbit), then there are O^{∼}(t|O|) Schreier generators, for N_{x_{1},... ,x_{i}}. By Theorem 3.15, this generating set can be reduced to one of size O^{∼}(t) in Monte Carlo time O^{∼}(t|O|n). Since there are at most O(log^{2} n) base points on O, the total time spent in a small base orbit O is O^{∼}(t|O|n).

If log |G^{O}| > 5 log^{2} n, then O is a Cameron type orbit for which the smallest orbit of G_{x_{1}} on O \ \{x_{1}\} has length at most 3\sqrt{|O|}, by Lemma 3.12. There are O^{∼}(t|O|) Schreier generators for N_{x_{1}} and so the time to find O^{∼}(t) generators for N_{x_{1}} is O^{∼}(t|O|n), as for the small base case. For successive point stabilizers with i > 1, there are at most O^{∼}(t\sqrt{|O|}) Schreier generators. One can replace them with O^{∼}(t) Schreier generators in O^{∼}(t\sqrt{|O|}n) Monte Carlo time by Theorem 3.15. Since there are at most 3\sqrt{|O|} base points on this orbit, that bounds the number of iterations, and the total time spent on a Cameron type orbit is also O^{∼}(t|O|n).

3.1. Random Subproducts and Subgroup Chain Lengths. The algorithms presented in this paper make heavy use of combinatorial methods for computing with groups based on the notion of random subproducts. This has led to a rich supply of new randomized tools for computing with groups. In this section, we will briefly review the specific ideas we require for this paper, and refer the reader to [CF92] in this volume for a more through treatment, including proofs.

A random subproduct of a sequence of group elements (g_{1}, g_{2}, …, g_{k}) is a product of the form g_{1}^{e_{1}}g_{2}^{e_{2}} ⋯ g_{k}^{e_{k}} where e_{i} ∈ {0, 1} are selected independently from the uniform distribution over {0, 1}. Given a set, S, of generators of a group, G, and a transversal T of a point stabilizer subgroup G_{x} in G, a random Schreier subproduct is formed as follows. Form a random subproduct, g, of the sequence of group elements in S (for h ∈ G, let \overline{h} be the unique element in T such that h\overline{h} ∈ G_{x}), form all Schreier generators tg(\overline{tg})^{−1} for t ∈ T, and then form a random subproduct on this set of Schreier generators.

Random subproducts and random Schreier subproducts, though not purely random elements of G and G_{x}, respectively, have useful properties. The following lemmas describe these properties.

Lemma 3.2. Let G = ⟨S⟩ be an arbitrary permutation group acting on Ω with |Ω| = n.

(i) Let H < G be a proper subgroup. Then the probability that a random subproduct r (formed using S) is not in H is at least 1/2.

(ii) There exists a constant c > 0 such that for arbitrary d ≥ 1, if S′ is a set of cd log n random subproducts on S, then with probability at least 1 − 1/n^{d}, ⟨S′⟩ has the same orbit structure on Ω as G.

(iii) Let x ∈ Ω, T a transversal of G_{x} in G, and \overline{H} < G_{x} is a proper subgroup then the probability that a random Schreier subproduct, r_{x}, formed using S and T, is not in \overline{H}, is at least 1/4.

The proof of (i) and (ii) can be found in [BCF^{+}91] or [CF92]. The next theorem is a generalization of Theorem 2.3 in [BCF^{+}91]. For convenience, we base the proof on the version appearing as Theorem 2.9 in [CF92].

Theorem 3.3. Let G = ⟨S⟩ be a finite group. Let H ≤ G, and let L̂ be a known upper bound on the length of all subgroup chains from H to G. Then for any fixed parameter p such that 0 < p < 1, with probability at least p one can find a set Ŝ with |Ŝ| = O(L̂ log(1/(1 − p))) using O(|S| (log L̂) log(1/(1 − p))) group operations such that ⟨Ŝ, H⟩ = G.

Proof. The proof is given as a modification of the proof of Theorem 2.9 in [CF92] (this volume). One must initialize the S′ of the original proof to T, a generating set for H, instead of the empty set, and interpret the L of the original proof as |T | + L̂. Further, if one replaces ⟨g_{1}, …, g_{i−1}⟩ by ⟨H, g_{1}, …, g_{i−1}⟩ everywhere, then the logic of the proof generalizes verbatim to the current theorem. The new generating set Ŝ is then chosen as S′ \ T, and ⟨Ŝ, H⟩ = G.

Theorem 3.4. (Cameron et al. [CST89]) Any subgroup chain of a permutation group of degree n has length at most 3n/2.

Another variation of the above theorem was proved by Babai [Bab86] with a bound of 2n − 3.

Lemma 3.5. (Scott [Sco79]) Let G = H_{1} × … × H_{r} be the direct product of non-abelian simple groups H_{i}, 1 ≤ i ≤ r. Let M be a subgroup of G which projects onto each H_{i} for 1 ≤ i ≤ r. Then there exists a partition {B_{1}, …, B_{s}} of {1, …, r} such that M = D_{1} × … × D_{s} where each D_{i} is a diagonal subgroup of ×_{j∈B_{i}}H_{j}.

Corollary 3.6. Let W be the disjoint union of r sets W_{i}, each of size at least 2. Suppose that H is a subgroup of G = Alt(W_{1}) × ⋯ × Alt(W_{r}) and H projects onto Alt(W_{i}) for each i. Then the length of any chain of proper subgroups from H to G is at most 2r.

The proof follows easily from Lemma 3.5. If |W_{i}| ≠ 4 for all i, then the alternating groups are simple, and a bound of at most r on the chain can be found. Otherwise, 2r subgroups may be needed.

3.2. Cameron Groups. We begin by defining a class of primitive groups referred to as Cameron groups.

Definition 3.7. Let (k, r, s) be a triple of positive integers such that k ≥ 5 and s ≤ k/2. Let C be the disjoint union of r sets B_{1}, …, B_{r} each of size k and let A = {X ⊂ C | ∀i, |X ∩ B_{i}| = s}. If G is a transitive subgroup of Sym(C) for which each B_{i}, 1 ≤ i ≤ r, is a block of imprimitivity and if G contains Alt(B_{1}) × ⋯ × Alt(B_{r}), then G^{A} is a primitive group (as can be seen by noting that the point stabilizer subgroup must be maximal in G). G^{A} is said to be a Cameron type group with parameters (k, r, s). G^{C} is called the natural or imprimitive Cameron action.

In the discussion to follow, we often directly identify elements X ∈ A with subsets of C satisfying the property |X ∩ B_{i}| = s for 1 ≤ i ≤ r. Note that the socle, Soc(G), has a faithful representation on C as Alt(B_{1}) × ⋯ × Alt(B_{r}), and that Soc(G) is a single minimal, normal subgroup. It is easy to verify that the action of G on the set {X ⊂ C | |X ∩ B_{i}| = s} is primitive, by noting that the point stabilizer subgroup must be maximal in G. Maximality follows from the characterization of the point stabilizer subgroup in Lemma 3.14.

The motivation for defining Cameron groups is the following theorem due to Cameron [Cam81]. It is based on the classification of finite simple groups, and on work by Kantor on permutation representations of classical groups [Kan79].

Theorem 3.8. [Cam81] Let G be a primitive group acting on n points. If |G| ≥ n^{5 log n}, then n = \binom{k}{s}^{r} and G is a Cameron group of type (k, r, s).

The following lemma gives some properties of a Cameron group. The calculations are based on those in [BLS87, BLS88], but have been re-calculated to achieve tighter bounds. The logarithmic base is 2 unless otherwise specified.

Lemma 3.9. Let G be a Cameron type group with parameters (k, r, s) acting on A. Let |A| = n. Then,

(i) n = \binom{k}{s}^{r}; (ii) rs log(k/s) ≤ log n; (iii) k ≤ \sqrt{2n} when r > 1 or s > 1, otherwise k = n; (iv) log |G| < \frac{(log n) log log n}{s log(k/s)} + \frac{k}{s} log n + \frac{k}{s} log n\frac{log s}{log(k/s)};

Proof. Part (i) is clear. Part (ii) follows from (\frac{k}{s})^{rs} ≤ \binom{k}{s}^{r}. In part (iii), for fixed n, k is maximized when r = 1 and s = 2, and the bound follows from (i). For part (iv), the inequality follows from |G| ≤ r!(k!)^{r} ≤ r!\binom{k}{s}^{rk/s}(s!)^{rk/s} = r!n^{k/s}(s!)^{rk/s}. After applying part (ii), log |G| ≤ r log r + k/s log n + rk/s log(s!) < \frac{(log n) log log n}{s log(k/s)} + \frac{k}{s} log n + \frac{k}{s} log n\frac{log s}{log(k/s)}.

Definition 3.10. Let G = G^{A} be a Cameron type group with parameters (k, r, s). For X ∈ A (and B_{1}, …, B_{r} as in Definition 3.7), define the G_{X}-orbit Σ_{1}(X) to be the set

{Y ∈ A | ∃j, 1 ≤ j ≤ r, ∀i ≠ j, |Y ∩ X ∩ B_{j}| = s − 1, Y ∩ B_{i} = X ∩ B_{i}}.

It is clear that Σ_{1}(X) ⊂ A is an orbit of the point stabilizer subgroup G_{X}. The next lemma provides a finer estimate of calculations based on Theorem 4.1 of [BLS87].

Lemma 3.11. Let G = G^{A} be a Cameron type group. For arbitrary X ∈ A, the action of G_{X} on Σ_{1}(X) is faithful. If G is not a giant, then |Σ_{1}(X)| ≤ 3\sqrt{n} − 1, and therefore Σ_{1}(X) ∪ \{X\} is a base for G of size at most 3\sqrt{n}. If log |G| > 5(log n) log log n, then Σ_{1}(X) is the smallest orbit of G_{X} in A \ {X}.

Proof. The action of G_{X} on C has orbits X ∩ B_{j} and (C \ X) ∩ B_{j} for 1 ≤ j ≤ r. To see that the action is faithful, we show that the kernel is trivial. Let g ∈ G_{X}^{C} be non-trivial. Let g′ ∈ G_{X}^{A} correspond to g under the permutation equivalence. There is a y ∈ B_{j} ⊆ C for some j, such that y^{g} ≠ y. If y ∈ X ∩ B_{j}, choose Y ∈ Σ_{1}(X) such that Y ∩ B_{i} = X ∩ B_{i} for i ≠ j, and Y ∩ B_{j} = ((B_{j} ∩ X) \ {y}) ∪ {z} for arbitrary z ∈ B_{j} \ X. If y ∈ B_{j} \ X, choose Y ∈ Σ_{1}(X) such that Y ∩ B_{i} = X ∩ B_{i} for i ≠ j, but Y ∩ B_{j} = ((B_{j} ∩ X) \ {z}) ∪ {y} for arbitrary z ∈ B_{j} ∩ X. Since y^{g} ≠ y, it is clear that Y^{g′} ≠ Y, and so G_{X} is faithful on Σ_{1}(X).

The length of Σ_{1}(X) is rs(k − s). If G is not a giant, then r > 1 or s > 1, and Lemma 3.9(ii, iii) yields rs(k − s) ≤ (k − s)(log n)/ log(k − s) < k (log n)/ log k ≤ 2^{3/2}\sqrt{n} < 3\sqrt{n}. Direct calculation shows that Σ_{1}(X) is the smallest orbit of G_{X} in A \ {X} except possibly when s ≥ ⌊(k − 1)/2⌋. Consider an orbit Σ_{2}(X) with parameters t_{1} and t_{2} such that for all Y ∈ Σ_{2}(X), |Y ∩ B_{i} \ X| = t_{1} > 0 and |Y ∩ B_{j} \ X| = t_{2} > 0 for some i ≠ j. (It is clear that this property will be preserved for all points in the same orbit.) Then |Σ_{2}(X)| ≥ q\binom{s}{t_{1}}\binom{k−s}{t_{1}}\binom{s}{t_{2}}\binom{k−s}{t_{2}} > |Σ_{1}(X)| when s = t < ⌊(k − 1)/2⌋. Here, q is the number of distinct intersection patterns, (|Y ∩ B_{1} \ X|, …, |Y ∩ B_{r} \ X|), for Y ∈ Σ_{2}(X). It is easy to show that q ≥ r, using the transitivity of the action of G on {B_{1}, …, B_{r}}. Next, consider an orbit Σ_{3}(X) with parameter t such that for all Y ∈ Σ_{3}(X), |Y ∩ B_{i} \ X| = t > 1 and |Y ∩ B_{j} \ X| = 0 for some i and for all j ≠ i. Then |Σ_{3}(X)| = r\binom{s}{t}\binom{k−s}{t} > |Σ_{1}(X)| when s = t < ⌊(k − 1)/2⌋.

If Σ_{1}(X) is not the smallest orbit, then s ≥ ⌊(k − 1)/2⌋, and one has the estimates s ≥ 2, 2 ≤ k/s ≤ 5/2, n ≥ 10, and log s ≤ log log n. (The last inequality follows from Lemma 3.9(ii).) Applying Lemma 3.9(iv) shows that log |G| ≤ 5(log n) log log n. So, Σ_{1}(X) is the smallest orbit of G_{X} when log |G| > 5(log n) log log n.

Corollary 3.12. If G is primitive of degree n ≥ 2, and log |G| > 5 log^{2} n, then G is of Cameron type and the second smallest orbit of its point stabilizer subgroup, G_{x}, is Σ_{1}(x). Further, the action of G_{x} on Σ_{1}(x) is faithful. If G is not a giant, then |Σ_{1}(x)| < 3\sqrt{n}.

Proof. For n ≥ 2, Theorem 3.8 shows that G is of Cameron type. Since 5 log^{2} n > 5(log n) log log n for n ≥ 2, the remaining conclusions follow from Lemma 3.11.

This motivates the next definition. The restriction of giants to groups of degree n at least 35 avoids certain pathological case that would have arisen in section 5 if n = 4 or n = 6.

Definition 3.13. A small base group is a group of degree n such that log |G| ≤ 5 log^{2} n. A giant is a group of the form S_{n} or A_{n} that is not of type small base. This implies that n > 10 for giants. An orbit of G is identified as large, small base, or Cameron type according to whether the action of G on that orbit is a group of the corresponding type.

Lemma 3.14. Let G = G^{A} be a primitive Cameron group with parameters (k, r, s) such that |A| = n and let G^{C} be the imprimitive Cameron action. Let X ∈ A and let Y_{1}, …, Y_{m} be a sequence of points in Σ_{1}(X). Let H = G_{X,Y_{1},... ,Y_{m}}. Then H has a normal subgroup K such that K^{C} has orbits U_{i} = X_{i} ∩ Y_{1} ∩ ⋯ ∩ Y_{m} and V_{i} = (B_{i} \ X_{i}) ∩ (B_{i} \ Y_{1}) ∩ ⋯ ∩ (B_{i} \ Y_{m}), 1 ≤ i ≤ r and K^{C} = Alt(U_{1}) × Alt(V_{1}) × ⋯ × Alt(U_{r}) × Alt(V_{r}). Furthermore, H^{C} acts faithfully on (∪_{i=1}^{r}U_{i}) ∪ (∪_{i=1}^{r}V_{i}) (and hence permutes the set {U_{1}, V_{1}, …, U_{r}, V_{r}}).

Proof. Note that G_{X} satisfies the conclusion. Note that X \Y_{i} and Y_{i}\X are trivial orbits of G_{X,Y_{1},... ,Y_{i}} for 1 ≤ i ≤ m. Each non-trivial orbit of G_{X,Y_{1},... ,Y_{i−1}} is formed from the set difference of an orbit of G_{X,Y_{1},... ,Y_{i}} and the union of the two trivial orbits. So, the conclusion will continue to be satisfied for all i.

3.3. Main Result. There are two situations where we require reduction of generators. The first is in SGS Primitive Orbits when we are given the initial generating set S for G and want to reduce it to one of size O^{∼}(t). The second occurs in SGS Non-Giant & Orbit Stabilizer when we construct the Schreier generators for a point stabilizer and want to reduce it to one of size O^{∼}(t) for the next round. The hypotheses of the following result are designed to capture both instances.

Theorem 3.15. Let G acting on Ω have t primitive orbits. Let H = ⟨S⟩ be a subgroup of G that acts faithfully on A ⊆ Ω, where A is a union of some of the G-orbits, O_{1}, …, O_{t}. Each O_{i} is either a small base orbit or a Cameron orbit or both. Without loss of generality, assume that the Cameron orbits appear as O_{1}, …, O_{r} for r ≤ t. Assume that if G^{O_{i}} is a Cameron orbit with parameters (k_{i}, r_{i}, s_{i}) and C_{i} supports the natural action of G^{O_{i}}, then the following holds for H^{C_{i}}.

(i) There exist mutually disjoint subsets V_{1}^{i}, …, V_{ℓ_{i}}^{i} of C_{i} such that H^{C_{i}} acts faithfully on U_{i} = ∪_{j=1}^{ℓ_{i}}V_{j}^{i}.

(ii) Alt(V_{1}^{i})×⋯×Alt(V_{ℓ_{i}}^{i}) is normal in H^{U^{i}} (and so H^{U^{i}} permutes the sets

{V_{1}^{i}, …, V_{ℓ_{i}}^{i}}). (iii) ℓ_{i} ≤ 2r_{i} ≤ 2 log n.

Then in O^{∼}(|S|n) Monte Carlo time, one can construct a generating set S′ for H such that |S′| = O(t log^{2} n).

The proof of Theorem 3.15 follows directly from Lemma 3.16 and Theorem 3.3.

Lemma 3.16. Assume the hypotheses of Theorem 3.15 Let M be a subgroup of H generated by Ω(log n) random subproducts of S. Then L(M, H) = O(t log^{2} n).

Proof. Assume first that each of the orbits O_{i} is a Cameron orbit. Let U = ∪_{i=1}^{t}(∪_{j=1}^{ℓ_{i}}V_{j}^{i}), so that G acts faithfully on U and permutes the sets {V_{j}^{i} | 1 ≤ j ≤ ℓ_{i}, 1 ≤ i ≤ t}.

For each V_{j}^{i}, let d_{j}^{i} = min(|V_{j}^{i}| − 2, 6) and define the set \binom{V_{j}^{i}}{d_{j}^{i}} to be the set of

all subsets of V_{j}^{i} of size d_{j}^{i}. Let U = ∪_{i=1}^{t}(∪_{j=1}^{ℓ_{i}}\binom{V_{j}^{i}}{d_{j}^{i}}). Then H acts faithfully on

U and |U| ≤ ∑_{i=1}^{t}(∑_{j=1}^{ℓ_{i}} |V_{j}^{i}|^{6}) ≤ ∑_{i=1}^{t} |U_{i}|^{6} ≤ ∑_{i=1}^{t} |C_{i}|^{6} ≤ ∑_{i=1}^{t} |O_{i}|^{6} ≤ n^{6}. By Lemma 3.2, Ω(log n) random subproducts on S will generate a subgroup M which has high probability of having the same orbits on U as H. Since H_{{V_{j}^{i}}}^{V_{j}^{i}}

contains Alt(V_{j}^{i}) it follows that \binom{V_{j}^{i}}{d_{j}^{i}} is contained in an orbit of M^{U}. But any

element of M^{U} that which takes one d_{j}^{i} subset of V_{j}^{i} to another must stabilize V_{j}^{i}.

So the set stabilizer M_{{V_{j}^{i}}} is d_{j}^{i}-transitive on V_{j}^{i}. So, M_{{V_{j}^{i}}}^{V_{j}^{i}} contains Alt(V_{j}^{i}).

We will use this property to show that L(M, H) = O(t log^{2} n). Note that the orbits of M on U are the same as those of H on U.

Define Ĥ = H^{U_{1}} ×⋯×H^{U_{t}} ≤ Sym(U). We will show that L(M, Ĥ) = O^{∼}(t), which suffices since M ≤ H ≤ Ĥ. Let

K̂ = \_{{1≤i≤t \atop 1≤j≤ℓ_{i}}} Alt(V_{j}^{i}),

so that K̂ ≤ Ĥ. Consider the (possibly unfaithful) action of Ĥ on {V_{j}^{i} | 1 ≤ j ≤ ℓ_{i}, 1 ≤ i ≤ t}. By (iii), there are at most 2t log n elements in this set. Moreover, the kernel of the action contains K̂ with index at most 2^{2t log n}. It then follows from this and the bound on the length of subgroup chains in symmetric groups (Theorem 3.4), that L(K̂, L̂) = L(Ĥ/K̂) ≤ 2t log n + 3/2(2t log n) ≤ 5t log n = O^{∼}(t).

Since K̂ is normal in Ĥ, it remains to estimate L(M, K̂). Let M = M_{0} < M_{1} < ⋯ < M_{p} = Ĥ be a proper chain of subgroups. By retaining only the subgroups in the chain that satisfy M_{i+1} ∩ K̂ > M_{i} ∩ K̂, we construct a new chain

M ∩ K̂ = K_{0} < K_{1} < ⋯ < K_{p′} ≤ K̂

for p′ ≤ p, such that for each r with 1 ≤ r ≤ p there is a unique s such that K_{r} = M_{s} ∩ K̂. Note that L(M ∩ K̂, Ĥ) ≤ p′ + L(K̂, Ĥ). So, we must estimate p′, which will be an upper bound on L(M, K̂).

We show that (K_{r})^{V_{j}^{i}} is either the alternating or trivial group. Let s correspond to r, so that M_{s}∩K̂ = K_{r}. Note that M_{s}∩K̂◁M_{s} and (M_{s})_{{V_{j}^{i}}}^{V_{j}^{i}} ≥ Alt(V_{j}^{i}).

So, (M_{s} ∩ K̂)^{V_{j}^{i}} ◁ (M_{s})^{V_{j}^{i}} ∩ Alt(V_{j}^{i}). Thus, if d_{j}^{i} ≠ 4, then (K_{r})^{V_{j}^{i}} = (M_{s} ∩ K̂)^{V_{j}^{i}} is either Alt(V_{j}^{i}) or the trivial group. Hence, this is true for all K_{r}, 1 ≤ r ≤ p′.

For each K_{r}, the action on each component with d_{j}^{i} ≠ 4 must be alternating or trivial. Let u_{r} be the number of components on which there is an alternating action. By Lemma 3.5, the action on the u_{r} alternating components decomposes into the direct product of v_{r} ≤ u_{r} actions, where each of the v_{r} actions is a diagonal of alternating actions on a subset of the {V_{j}^{i}}. Further, if K_{r+1} < K_{r}, then u_{r+1} > u_{r} or v_{r+1} > v_{r}. Since u_{p′} ≤ 2t log n and v_{p′} ≤ 2t log n, p′ ≤ 4t log n. On the other hand, if each of the orbits have length 4, then a similar argument, in conjunction with Corollary 3.6 shows that v_{p′} ≤ 4t log n and so p′ ≤ 6t log n.

We have shown that the result holds in the case where all the orbits O_{i} are Cameron orbits. The general case now follows easily by applying this result to the action of G on the union of the Cameron orbits and observing that the kernel of the action is faithfully represented on a union of small base group orbits of G on Ω. The kernel has order at most 2^{2t log^{2} n} by Theorem 3.8, yielding a bound of 2t log^{2} n for the subgroup chain length.

The final result in this section describes the situation in which Theorem 3.15 is invoked.

Lemma 3.17. Let G acting on Ω have t primitive orbits and let N be a normal subgroup of G. Let O be a G-orbit and x_{1}, …, x_{ℓ} a sequence of base points in O for N^{O} chosen so that x_{i}, 2 ≤ i ≤ ℓ is in the smallest orbit of G_{x_{1}} acting on O. Let A be the union of O and all G-orbits O_{j} such that N_{O}^{O_{j}} is non-trivial. Then N_{x_{1},... ,x_{i−1}} and A satisfy the hypotheses of Theorem 3.15, where N_{x_{1},... ,x_{i−1}} is identified with H.

Proof. It is clear that N acts faithfully on A. Let O_{j} ⊆ A be a Cameron type orbit with O ≠ O_{j}. Since N_{O}^{O_{j}} is a non-trivial normal subgroup of G^{O_{j}}, N_{O}^{O_{j}} contains the socle of G^{O_{j}}. This is also true for N_{x_{1},... ,x_{ℓ}}^{O_{j}}, and so the hypotheses of Theorem 3.15 are satisfied with regard to N_{x_{1},... ,x_{ℓ}} and O_{j} whenever O_{j} is a non-giant Cameron orbit. It remains to verify the hypotheses when O is a non-giant Cameron orbit. But this follows directly from Lemma 3.14 and the assumption on how the sequence x_{1}, …, x_{ℓ} is chosen.

4. A Monte Carlo Test for Giant Action

In the main procedure SGS Primitive Orbits, it is necessary to classify the t primitive orbits of G into types giant and non-giant. In this section we present a O˜ (tn^{2}) Monte Carlo time algorithm for accomplishing this task. The procedure Test Giants is based on repeated application of Theorem 3.15. This allows for a simple exposition of the algorithm.

  Procedure Test Giants

Input: (S, Ω) where S ⊆ Sym(Ω), |S| = O˜ (t), G = ⟨S⟩ and G has t primitive orbits. Output: Each orbit is identified as type giant or non-giant

For each orbit O of G do

If |O| < 35 then mark O as non-giant Else set S′ ← S Choose points x_{1}, …, x_{6} in O For i ← 1 to 6 do Let T be O^{∼}(1) random subproducts of ⟨S′⟩ such that x_{i}^{⟨T ⟩} = x_{i}^{G_{x_{1},... ,x_{i−1}}} If |x_{i}^{⟨T ⟩}| ≠ |O| − i + 1 then Mark O as a non-giant and break from the loop Let C be a transversal for G_{x_{1},... ,x_{i}} in G_{x_{1},... ,x_{i−1}} built from T Let S′′ be a set of Schreier generators for G_{x_{1},... ,x_{i}} built from S′′ and C Replace S′ by a generating set for G_{x_{1},... ,x_{i}} of size O^{∼}(t) built from S′′

Theorem 4.1. Procedure Test Giants is correct and runs in Monte Carlo time O(tn^{2}).

Proof. The algorithm simply tests whether G^{O} is 6-transitive. The correctness of this approach is a consequence of the classification of finite simple groups [Gor82]. In addition, we need to invoke Lemma 3.17 in order to ensure that the the hypotheses of Theorem 3.15 apply. The time for each orbit is easily seen to be O^{∼}(t|O|n) from Theorem 3.15 and this then leads to the stated time bound.

5. Giant Orbits

In this section, we describe the procedure SGS Giant Orbits. When this procedure is called, SGS Primitive Orbits has computed a set of O^{∼}(t) generators for the pointwise stabilizer of all the non-giant orbits. Since this subgroup is normal, the action on the remaining non–trivial orbits must be of giant type. This justifies the assumptions made for the input to SGS Giant Orbits. The procedure constructs a strong generating set for the input group in two stages. First, SGS Alt Orbits (described later) is invoked to compute a strong generating set for the alternating action on each orbit and then a standard linear algebra argument is invoked in order to complete the strong generating set to one for the entire group. Corollary 5.1 reveals the structure of G as a direct product of alternating groups which act diagonally on subsets of the orbits.

  Procedure SGS Giant Orbits

Input: (S, A) where ⟨S⟩ = G ≤ Sym(Ω), G acts faithfully on A ⊆ Ω, A is a union of giant orbits O_{1}, …, O_{t} of G and |S| = O^{∼}(t). Output: T such that T is a SGS for G with respect to an ordering determined by the algorithm.

   T ← SGS Alt Orbits(S, A)

[T is a SGS for G ∩ (Alt(O_{1}) × ⋯ × Alt(O_{t}))]

Let S′ = {s ∈ S | s|_{O_{i}} is odd for some O_{i}} [Simulate Gaussian elimination on G/G′] For i ← 1 to t do Let s′ be the first element of S′ such that s′|_{O_{i}} is odd (if it exists) If such an s′ exists then Set S′ ← S′ \ {s′} Set s′ ← the residue of sifting s′ through T on O_{i} [s′|_{O_{i}} is now a 2-cycle] Set T ← T ∪ {s′} Set S′ ← S′s′^{−1} Replace each s ∈ S′ by the residue of sifting s through T on O_{i} [S′^{O_{i}} is now trivial]

Return T

The next procedure makes use of a fast normal closure routine, developed in [BCF^{+}91], and described further in [CF92] (this volume). It also refers to a procedure Three Cycle due to Babai, Luks and Seress and is described in [BLS88]. If a group specified by a generating set of size O^{∼}(n) contains the alternating group, then this procedure will construct a three-cycle in O^{∼}(n^{2}) Las Vegas time.

Procedure SGS Alt Orbits

Input: (S, A) as in SGS Giant Orbits Output: a SGS, T, for G ∩ (Alt(O_{1}) × ⋯ × Alt(O_{t}))

with respect to an ordering determined by the algorithm.

Initialize T ← ∅ Let all orbits be unmarked. Mark the first orbit, O_{1}, of G Let x ∈ O_{1} and S′ a set of Schreier generators for G_{x_{1}} formed from S For i ← 2 to t do If S′ has a fixed point on O_{i} then mark O_{i} [In our setting, this is true if and only if G_{O_{1}}^{O_{i}} is trivial.]

Let T′ be a SGS for G^{O_{1}} ∩ Alt(O_{1}) whose elements act as 3-cycles on O_{1} [By invoking 3-Cycle] Replace each element in T′ by its square [This ensures that T′ ⊆ Alt(Ω)] For each unmarked orbit O of G do Let S′′ be a generating set for S^{O_{1}∪O} of size O^{∼}(1) [Found by applying Theorem 3.15]

 Set σ\overline{O} ← Element Fixing an Orbit(S′′, O_{1}, O)

Let O be the set unmarked orbits on which σ\overline{0} acts non-trivially Let \overline{O} = ∪_{O∈O}O and n\overline{O} = |O| Let σ′ ; \overline{O} be the residue of sifting σ\overline{O} through T [σ′ ; \overline{O}|\overline{O} = σ\overline{O}|\overline{O} and is trivial elsewhere.] Let S′ ; \overline{O} be a set of O(n) generators for the normal closure of ⟨σ′ ; \overline{O}⟩ in G [The “fast normal closure” routine is used”] Let S′′ ; \overline{O} be a reduced set of O^{∼}(n\overline{0}) generators for ⟨S′ ; \overline{O}⟩

 Set T ← Prepend (SGS Alt Orbits(S′′ ; \overline{O}, \overline{O}), T)

Mark all orbits in \overline{O} Set T ← Prepend(T′, T) Return T

Procedure Element Fixing an Orbit

Input: (S, O_{1}, O_{2}) where O_{1} and O_{2} are unlinked giant orbits for G = ⟨S⟩ and |S| = O^{∼}(1). Output: An element of G_{O_{1}} which acts non-trivially on O_{2}.

   σ ← Three Cycle (S, O_{1})

Set σ ← σ^{2} [to ensure that σ ∈ Alt(O_{1} ∪ O_{2})] Let σ|_{O_{1}} = (a b c), σ|_{O_{2}} = δ If δ is non-trivial then

Let U be a set of O^{∼}(1) generators for G_{a,b,c} [Found by repeated application of Theorem 3.15 ] Let g be an element of U such that [g, σ] = [g, δ] ≠ 1 [Since Alt(O_{2}) ≤ ⟨S⟩^{O_{2}}, δ is not centralized by S]

Return([g, σ]) Else [δ = (a b c)] Let T be a SGS for G^{O_{1}} constructed from (a b c) with T ⊆ G_{O_{2}} For each s ∈ S do Let s′ ∈ G_{O_{1}} be the residue of s sifted through T If s′ ≠ 1 return(s′)

5.1. Giant Orbits: Proof of Correctness. The proof of correctness for SGS Alt Orbits follows directly from the following result.

Corollary 5.1. Assume that G ≤ Sym(Ω) and that Soc(G) acts as the full alternating group on each orbit O_{i}, 1 ≤ i ≤ t of G. Then there exists a partition of {O_{1}, …, O_{t}} into subsets {B_{1}, …, B_{s}} such that Soc(G) is the direct product of alternating groups, with each direct factor acting as a diagonal subgroup on the orbits in precisely one of the blocks B_{i} and fixes pointwise the orbits in the other blocks. Furthermore, if σ ∈ Soc(G), then the normal closure of ⟨σ⟩ in G is the product of the diagonal subgroups corresponding to the blocks B_{i} on whose orbits σ acts non-trivially.

Theorem 5.2. Let G = ⟨S⟩ act on Ω with |Ω| = n. Assume that G has t giant orbits and that |S| = O^{∼}(t). Then the procedure SGS Giant Orbits constructs a SGS for G in O^{∼}(tn^{2}) Monte Carlo time.

Proof. The proof of correctness and the timing for SGS Giant Orbits is clear once the corresponding results have been proved for SGS Alt Orbits.

The correctness of SGS Alt Orbits relies on Corollary 5.1. As long as there are unmarked orbits, the procedure will construct a non-identity element σ′ ; \overline{O} which fixes pointwise each marked orbit and acts non-trivially on the union \overline{O} of a subset of unmarked orbits. In the notation of Corollary 5.1, \overline{O} is the union of a certain number of the B′_{i}s. Thus the normal closure of σ′ ; \overline{O} in G is a direct factor of Soc(G) consisting of the pointwise stabilizer in Soc(G) of Ω \ \overline{O}. A recursive call is made and once a strong generating set has been computed it is prepended to the set T which holds elements of the strong generating set currently being accumulated.

In analyzing the timing, it is straightforward to show that the top-level call to SGS Alt Orbits takes time O(tn^{2}) aside from the recursive calls to smaller problems. By induction, each recursive call to a subproblem takes time O(n\overline{O}n^{2}), where n\overline{O} is the number of orbits O_{i} in \overline{O} and \overline{O} is a union of blocks B_{j} as given in Corollary 5.1. Since a recursive call at the top-level never involves an orbit O_{i} more than once, the total time spent on the recursive calls is O^{∼}(tn^{2}).

References

[Bab86] L. Babai. On the length of chains of subgroups in the symmetric group. Comm. in Algebra, 14:1729–1736, 1986.

[BCF^{+}91] L. Babai, G. Cooperman, L. Finkelstein, E.M. Luks, and Á. Seress. Fast Monte

Carlo algorithms for permutation groups. In Proc. 23rd ACM STOC, pages 90–100, 1991. [BCF^{+}^{+}91] L. Babai, G. Cooperman, L. Finkelstein, and Á. Seress. Nearly Linear Time Al-

gorithms for Permutation Groups with a Small Base. In Proc. ISSAC ’91 (International Symposium on Symbolic and Algebraic Computation ’91), ACM Press, pages 200–209, 1991.

[BFP89] C.A. Brown, L. Finkelstein, and P.W. Purdom. A new base change algorithm for permutation group. SIAM J. Computing, 18:1037–1047, 1989.

[BLS87] L. Babai, E. Luks, and Á. Seress. Permutation groups in NC. In Proc. 19th ACM STOC, pages 409–420, 1987.

[BLS88] L. Babai, E. Luks, and Á. Seress. Fast management of permutation groups. In Proc. 19th IEEE FOCS, pages 272–282, 1988.

[Cam81] P.J. Cameron. Finite permutation groups and finite simple groups. Bull. London Math. Soc., 13:1–22, 1981.

[CF92] G. Cooperman and L. Finkelstein. Combinatorial tools for computational group theory. In DIMACS Proceedings (this volume), 1992.

[CFS90] G. Cooperman, L. Finkelstein, and N. Sarawagi. A random base change algorithm for permutation groups. In Proc. of 1990 International Symposium on Symbolic and Algebraic Computation, pages 161–168, Tokyo, Japan, August 1990. ACM Press and Addison-Wesley.

[CST89] P.J. Cameron, R. Solomon, and A. Turull. Chains of subgroups in symmetric groups. J. of Algebra, 127:340–352, 1989.

[Gor82] D. Gorenstein. The Classification of Finite Simple Groups, Vol. 1. Plenum Press, New York, 1982.

[Kan79] W.M. Kantor. Permutation representations of the finite classical groups of small degree or rank. J. Algebra, 60:158–168, 1979.

[Luk90] E. Luks. Lectures on polynomial-time computation in groups. Technical Report NU-CCS-90-16, College of Computer Science, Northeastern University, 1990.

[Sar92] N. Sarawagi. Computational Group Theory and Applications to Search. Ph.D. Thesis, Northeastern University, 1992.

[Sco79] L. Scott. Representations in characteristic p. The Santa Cruz Conference on Finite Groups, 1980, Amer. Math. Soc., 319–322.

[Sim] C.C. Sims. Computation with permutation groups. In Proc. Second Symposium on Symbolic and Algebraic Manipulation, ACM Press, New York, 1971, pages 23–28.

College of Computer Science, Northeastern University, Boston, Massachusetts 02115

Current address: Namita Sarawagi, Department of Mathematics and Computer Science, Rhode Island College, N. Providence, RI 02911

E-mail address: gene@ccs.northeastern.edu, laf@ccs.northeastern.edu, and FACSARAWAGI@ric.edu