Proc. 23rd ACM Annual Symp. on Theory of Comp. (ACM STOC-23) (1991)

Fast Monte Carlo Algorithms for Permutation Groups

László Babai^{1,2}, Gene Cooperman^{3}, Larry Finkelstein^{3}, Eugene Luks^{4}, and Ákos Seress^{5}

1Department of Computer Science  ^{2}Department of Algebra
University of Chicago  Eötvös University
Chicago, Illinois 60637  Budapest, Hungary H-1088
3College of Computer Science  ^{4}Department of Computer Science
Northeastern University  University of Oregon
Boston, Mass. 02115  Eugene, Oregon 94705

5Department of Mathematics Ohio State University Columbus, Ohio 43210

Fast Monte Carlo Algorithms for Permutation Groups

László Babai^{1,2}, Gene Cooperman^{3}, Larry Finkelstein^{3}, Eugene Luks^{4}, and Ákos Seress^{5}

1Department of Computer Science University of Chicago Chicago, Illinois 60637 2Department of Algebra Eötvös University Budapest, Hungary H-1088 3College of Computer Science Northeastern University Boston, Mass. 02115

4Department of Computer Science University of Oregon Eugene, Oregon 94705 5Department of Mathematics Ohio State University Columbus, Ohio 43210

Abstract

We introduce new Monte Carlo methods to speed up and greatly simplify the manipulation of permutation groups. The methods are of a combinatorial character and use elementary group theory only. We achieve a nearly optimal O(n^{3} log^{c} n) running time for membership testing, an improvement of two orders of magnitude compared to known elementary algorithms and one order of magnitude compared to algorithms which depend on heavy use of group theory.

The permutation groups considered are given by a list of generators. The basic task is to transform this into a data structure called a strong generating set (SGS). Given an SGS, one can rapidly determine the order of G and decide membership in G.

Strong generating sets were introduced by Sims in the 60’s and have been used extensively in computational group theory. Variants of Sims’s elementary algorithm for construction of a SGS have been known to have Θ(n^{5}) worst case behavior, where n is the cardinality of the permutation domain. It was only with extensive references to consequences of the classification of finite simple groups that a much more involved algorithm of Babai, Luks, and Seress reduced the worst case running time to O^{∼}(n^{4}) [BLS2] where the tilde refers to a (log n)^{c} factor.

Using randomization in a novel way, we achieve considerable further speedup in basic permutation group manipulation. We are able to construct an SGS in Monte Carlo time O^{∼}(n^{3}), nearly matching the running time of Gaussian elimination which is a (very) particular case. As a consequence, we can determine the order of G in Monte Carlo time O^{∼}(n^{3}) and subsequently perform membership tests in O(n^{2}) time per test.

The most spectacular speedup is achieved for normal closures, a key ingredient of algorithms in computational group theory, previously thought to depend on prior construction of an SGS. We can now construct normal closures in Monte Carlo time O^{∼}(n^{2}), i.e. essentially linear time.

(The input typically consists of O(n) permutations and thus has length O(n^{2}).)

As a byproduct, for low rank systems of linear equations we actually achieve a speedup over Gaussian elimination.

On the other hand, some of the new techniques are so general, that they allow polynomial time implementations in matrix groups over finite fields and even more generally in “black box groups” (group operations are performed by an oracle). In particular, the normal closure algorithm leads to polynomial time Monte Carlo algorithms to test solvability and nilpotence of such groups.

Our algorithms are nearly optimal, as indicated, for groups with large bases. For the important subcase of groups with small (polylog size) bases, nearly linear time algorithms have been found using entirely different methods. These will be described in a separate paper [BCFS].

1. Introduction

1.1. Permutation group algorithms

Given a chain G = G_{0} ≥ G_{1} ≥ … ≥ G_{n} = 1 of subgroups of a finite group G, a strong generating set (SGS) with respect to this chain is a set T ⊂ G such that T ∩ G_{i} generates G_{i} for each i. Sims [Si] introduced this concept with respect to the point stabilizer subgroup chain for finite permutation groups acting on n points. In that case, G acts on the set Ω = {1, …, n}, and G_{i} is the pointwise stabilizer of the initial segment {1, …, i}.

Strong generatings sets provide the basic data structure in essentially all polynomial time algorithms for permutation groups.

Let G be a group given by a list of s generators. The first asymptotically analyzed variant of Sims’s SGS algorithm [FHL] ran in time O(n^{6}+sn^{2}). This was subsequently improved by Knuth [Kn] and Jerrum [Je] to O(n^{5} + sn^{2}). Knuth’s version follows Sims most closely. It is also shown in a recent version of [Kn] that if G is given by a certain randomized list, than the algorithm actually requires Ω(n^{5}) time on average.

The notorious n^{5} bound was brought down by Babai, Luks and Seress [BLS2] in an O^{∼}(n^{4} +sn^{2}) algorithm which digs deeply into the normal structure of G and requires several consequences of the classification of finite simple groups for its analysis. This algorithm was recently improved to O^{∼}(sn^{3}) [BLS3]. (It is reasonable to assume s ≤ n and in fact often s is much smaller (s = 2 is a frequent case.)

In the present paper we achieve considerable Monte Carlo speedups over the previously known algorithms. A further advantage of the new algorithms is that their analysis is completely elementary; and purely combinatorial in nature.

One of the first difficulties to overcome is the growth of the number of generators for subgroups constructed. Although any set of ≥ 2n generators of a permutation group of degree n is redundant, we may not know which generators to delete. Our first result solves this problem:

• We construct O(n) generators for a group from an initially given set of s generators in Monte Carlo time O(sn log n).

Henceforth when using the expression “we construct a subgroup”, it is understood that we construct a list of O(n) generators for that subgroup; and, if not specified otherwise, the input groups are also assumed to be given by lists of O(n) generators.

Here are our main results for permutation groups G ≤ Sym(Ω) where |Ω| = n. The notation O^{∼}(f(n)) refers to a function bounded by f(n)(log n)^{c} for some constant c.

• Given a group G and a subgroup H, each by a list of O(n) generators, we construct the normal closure of H in G in Monte Carlo time O^{∼}(n^{2});

• Given a group G and a point x ∈ Ω, we construct the stabilizer of x in Monte Carlo time O(kn^{2}), where k is the length of the orbit of x;

• Given a group G we construct the point stabilizer chain (SGS) in Monte Carlo time O^{∼}(n^{3}).

Using Jerrum’s “labeled branching” data structure we keep the space requried by these algorithms at O(n^{2}), i.e. linear compared to an input of O(n) permutations.

Combining the first and the last bullet points and some more information regarding the nature of the SGS to be constructed, we can state our main result.

Theorem 1.1. Given a permutation group of degree n by a list of s generators, we construct the point stabilizer chain (SGS) in Monte Carlo time O^{∼}(n^{3} + sn). – We can determine the order of G within the same time bound, and set up Jerrum’s “labeled branching” data structure which supports membership tests for G in O(n^{2}) time per test. – The algorithm uses O^{∼}(n(n+s)) space. – It can be upgraded to Las Vegas, running in time O(n^{4} + sn log n) (no hidden log factors).

The O^{∼}(n^{3}) time bound is optimal within a polylog factor in the sense that it includes Gaussian elimination as a very special case.

The Las Vegas upgrade (cf. Section 1.2) is obtained by combining our Monte Carlo algorithm with the O(n^{4}) deterministic strong generation test of Cooperman and Finkelstein [CF]. This might be significant in implementations because it allows to take advantage of favorable circumstances by early termination.

Previous polynomial-time randomized algorithms for permutation groups have been largely limited to heuristic algorithms which were difficult to analyze. Faster base change algorithms [Ba1, CFS] were some of the first algorithms to provide a rigorous analysis for the use of uniformly distributed random group elements. However, no method is known to generate uniformly random elements of G without first constructing a strong generating set.

The main idea elaborated in the present paper is that under certain circumstances, products of random subsets of the generators can successfully emulate truly random elements. This idea seems to have appeared first in the superfast Las Vegas handling of the symmetric group by Babai, Luks and Seress [BLS2]. There, it is shown that O(log n) such random products are likely to generate a subgroup H with orbit structure identical to G. This yields in particular O(log n) generators of a doubly transitive subgroup in Monte Carlo time O(|S|n log(n)) assuming G = ⟨S⟩ is doubly transitive. Both the number of generators thus obtained and the time required are almost an order of magnitude smaller than the O(n) generators obtained deterministically in time O(|S|n^{2}).

1.2. Reliability, and spreader sets of permutations

A Monte Carlo algorithm is a randomized algorithm which may give a wrong answer or report failure with small probability. A Las Vegas algorithm [Ba1] is a Monte Carlo algorithm which never gives a wrong answer.

Our Monte Carlo algorithms are not Las Vegas, so we shall never be sure of the correctness of the output. The probability of error, however, can be made less than exp(−(log n)^{C}) for any constant C within the time bounds stated.

Combining our algorithm with the deterministic O(n^{4}) time “strong generating test” of Cooperman and Finkelstein [CF], we obtain an O(n^{4}) Las Vegas SGS algorithm. (Note, however, that now, an O^{∼}(sn^{3}) deterministic SGS algorithm also exists [BLS3].)

It would be desirable to increase the reliability of our algorithms to exponential without the loss of an extra order of magnitude in running time. This depends on whether or not an explicit construction can be found to replace a set of random permutations used in the algorithm. We state this problem below.

Let M = {1, …, m}, M̄ = M ∪ {0, m + 1}, H ⊆ M, and H̄ = H ∪ {0, m + 1}. For x ∈ H, let

δ_{H}(x) = min_{y∈H̄\{x}} |x − y|.

(Distance to nearest neighbor.) Define δ(H) = ∑_{x∈H} δ_{H}(x) and spread(H) = δ(H)/(m+1). Obviously, 0 ≤ spread(H) ≤ 1 (in fact, |H|/(m + 1) ≤ spread(H) ≤ 1 − 1/(|H| + 1). We use this quantity, the spreading factor of H, to measure how evenly the set H is spread out within M. We say that H is ϵ-spread if spread(H) ≥ ϵ.

Let P = {π_{1}, …, π_{r}} ⊂ S_{m} be a set of permutations of M. We call P an (ϵ, m)-spreader if for every nonempty set H ⊆ M, at least one of the sets H^{π_{j}} is ϵ-spread (j = 1, …, r). The greatest such ϵ is the spreading factor of P.

Theorem 1.2. With large probability, a set of r = O(log m) random permutations is a (1/48, m)-spreader.

Some computational evidence suggests the spreading factor 1/48 could be improved to about 1/4.

Spreaders will be a key component of some of our algorithms, including the superefficient normal closure. The reliability of the random spreaders given by Theorem 1.2 is 1 − m^{−c′} for an arbitrary constant c′. Because of the crucial role they play, it would be of great importance to construct guaranteed spreaders either by way of a Las Vegas construction or by an explicit construction, or at least to improve their reliability to exponential.

1.3. Black box groups

Some of the new algorithms are so general, they work even in the “black box group” model. In this model, introduced in [BSz], group elements are encoded by strings of uniform length n, and group operations are performed by an oracle (the black box). If the group G is given by the strings representing a set of generators, then G is called a black box group.

The most important implementation of the black box group model is matrix groups over finite fields, a class of of group representations where hardly any of the important computational tasks are solvable in polynomial time. In particular, even in the case of 1 × 1 matrices, membership is closely related to discrete logarithms and is not believed to be solvable in polynomial time.

While the rudimentary task of membership remains intractable, some global structural properties of the group can be recovered in Monte Carlo polynomial time, even in the general context of black box groups.

Theorem 1.3. Let G be a black box group with elements encoded as strings of length n. Suppose G is given by a list of s generators. Then the number of generators can be reduced to O(n) by a Monte Carlo algorithm consisting of O(s log n) group operations. Moreover, if both G and a subgroup H are given by O(n) generators, then the normal closure of H in G can be constructed by a Monte Carlo algorithm consisting of O^{∼}(n) group operations.

Corollary 1.4. Let G be as in Theorem 1.3. Then one can perform each of the following tasks in Monte Carlo polynomial time: (a) construct the commutator subgroup;

(b) decide whether or not G is solvable; (c) nilpotent. If G is solvable, the commutator chain can be constructed; and if G is nilpotent, the descending central series can be constructed.

The proof of these results is a simple combination of the algorithm to reduce the number of generators and the fast normal closure algorithm.

1.4. Pruning redundant systems of linear equations

There is a curious consequence of the generator pruning algorithm to low rank matrices. If a matrix over a field F has m rows and rank r then Gaussian elimination requires Θ(mr) row operations to determine the rank or to solve a system of linear equations.

If r < ϵm for some small ϵ > 0 but r itself is not bounded, we can achieve considerable savings by first replacing the m rows by a set of O(r) rows using our Monte Carlo algorithms. With large probability, the rows obtained will generate the same row space. The new rows are obtained as sums of subsets of the original rows and will require O(m log r) row operations to compute. Subsequently we can complete the work by Gaussian elimination, using O(r^{2}) row operations.

Corollary. A system of m linear equations of rank r can be solved (or found inconsistent) (with a small probability of error) using O(r^{2} + m log r) row operations. (Gaussian elimination would require O(mr) row operations.)

A “repeated doubling” trick achieves this complexity even if no a priori estimate of r is available.

2. Random subproducts

In this section, random subproducts are defined and our first technical goal, reduction of the number of generators, is achieved. This algorithm works in general even for black box groups. The application to low rank systems of equations stated in Section 1.4 follows immediately. As another application, we achieve a second main goal, efficient computation of generators for a stabilizer subgroup in a permutation group.

2.1. Reduction of generators

Definition 2.1. A 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}. To obtain a random subproduct, select the e_{i} independently from the uniform distribution over {0, 1}. A random subproduct of length ℓ is obtained as follows: first select at random a subset of size ℓ of the g_{i}; then form a random subproduct of them (with respect to the inherited ordering). (Note that in this terminology, a random subproduct of length ℓ is expected to be a product of ℓ/2 terms.)

Suppose now that G acts on Ω and K ⊂ Ω is not stabilized by G. Then, as observed in [BLS2, section 6.2], with probability ≥ 1/2, K is not stabilized by a random subproduct of the generators of G. We state a consequence of this observation.

Lemma 2.2. If K is a non-empty, proper subset of the finite group G (K is not necessarily a group), and G has generators (g_{1}, g_{2}, …, g_{k}), then for a random subproduct g = g_{1}^{e_{1}}g_{2}^{e_{2}} ⋯ g_{k}^{e_{k}}, Prob(Kg ≠ K) ≥ 1/2. For K a subgroup, this implies that Prob(g ∉ K) ≥ 1/2.

Proof. Note that G acts transitively in its regular representation (in which G acts on itself by either left or right multiplication). Thus, there is only one orbit in the regular representation, and K is a proper subset of it. The previous observation now yields the proof.

Theorem 2.3. Let G = ⟨S⟩ be a finite group. Let |S| = s, and let L be a known upper bound on the length of all subgroup chains in G. Then, using O(s log(L)) group operations, one can with fixed but high probability find a generating set S′ with |S′| = O(L).

Proof. (Informal sketch.) Assume s > 4L or else there is nothing to do. Successively place in S′, cL random subproducts each of length s/L. After this phase, with high probability, all but L of the elements of S are in ⟨S′⟩. If this were not true then, for a randomly chosen g ∈ S, we would have Prob(g ∉ ⟨S′⟩) > L/s. So each of the cL random subproducts would have probability at least (1 − (1 − L/s)^{s/L})/2 ≈ (1 − 1/e)/2 of not being in the previously constructed ⟨S′⟩. For sufficiently large c, this would violate the bound L on the length of subgroup chains.

After the initial round, we choose a new constant c′ and continue for log(L) more rounds. In the ith round, as i varies from 1 to log(L), we form c′L/2^{i} random subproducts, each of length 2^{i}s/L, and add them to S′. For a sufficiently large constant c′, with high probability the number of elements of S not in ⟨S′⟩ will then be at most L/2^{i}.

The last statement follows by induction. To see this, note that if |S−⟨S′⟩| ≤ L/2^{i−1}, then either |S−⟨S′⟩| ≤ L/2^{i} and the induction step is done, or else L/2^{i} < |S − ⟨S′⟩| ≤ L/2^{i−1}. In the last case, there is a fixed constant p, such that with probability at least p, a random subset of size 2^{i}s/L contains exactly one element of S not in ⟨S′⟩; so, with probability at least p/2, a random subproduct of length 2^{i}s/L captures exactly one new element of S not in ⟨S′⟩. Hence, for sufficiently large c′, the number of “uncaptured” elements of S will be reduced below L/2^{i} as advertised. So, log(L) rounds suffice with high probability.

An alternative algorithm uses spreaders (cf. Section 1.2) with similar efficiency. (Cf. Section 3.2.)

In applying this result to permutation groups, we requre the following lemma from [Ba2], [CST].

Lemma 2.4. Any subgroup chain in S_{n} has length at most 2n − 3.

Consequently, L = 2n is a valid bound for permutation groups of degree n.

When applying Theorem 2.3 to black box groups where elements are encoded by binary strings of length n, we may use the obvious upper bound log |G| ≤ n on the length of subgroup chains.

2.2. Group closure systems

The proof of Theorem 2.3 actually yields the following more general result. Let U be an arbitrary set and Φ a family of subsets closed under intersections, such that U ∈ Φ. We call the pair (U, Φ) a closure system. The members of Φ are called closed sets; and the closure cl(S) of a subset S is the intersection of all closed sets containing S. The set S is said to generate its closure.

We call (U, Φ) a group closure system, if in addition, U is a group under a certain operation, and all closed subsets are subgroups. (Note: not all subgroups need to be closed.)

Examples of group closure systems abound: consider groups with any sublattice of their subgroups, e.g. the normal subgroups; or rings with any sublattice of their subrings, e.g. their ideals; or vector spaces and their subspace lattice.

Theorem 2.5. Let (U, Φ) be a group closure system. Assume that U is generated by a finite set S, |S| = s, and let L be a known finite upper bound on the length of all chains of closed sets. Then, using O(s log(L)) group operations, one can with fixed but high probability find a generating set S′ with |S′| = O(L).

The proof is identical with that of Theorem 2.3. An application of this result to the subspaces of the row space of a matrix justifies the argument given in Section 1.4. (Take L to be the rank of the matrix.)

2.3. Schreier generators and point stabilizers

Our next task, of great importance for permutation groups, is to construct generators for subgroups. The common technique is Schreier generators, which we now define.

Definition 2.5. A (right) transversal of the subgroup H in the group G is a complete set of (right) coset representatives of H in G.

Definition 2.6. Let G =< S > be a group, H a subgroup, and T a transversal of H in G. For each t ∈ T and g ∈ S, let t′ be the unique element of T such that tg ∈ Ht′. Then the element tgt^{′−1} is called a Schreier generator of H.

The total number of Schreier generators is |S| · |T |.

Fact 2.7. The Schreier generators generate H.

The difficulty with (repeatedly) using Schreier generators is in their rapidly growing number. This obstacle is removed using Theorem 2.3: first we construct the Schreier generators; then we reduce their number to O(L). All this takes |S||T | log L group operations, assuming we can quickly determine t′, given tg (t ∈ T, g ∈ S).

We apply this result to the point stabilizers in permutation groups.

Corollary 2.8. Let G = ⟨S⟩ ≤ Sym(Ω) be a permutation group of degree n = |Ω|. Assume |S| = s = O(n). Let x ∈ Ω. Then we can find a set of O(n) generators of the stabilizer subgroup G_{x} in Monte Carlo time O(n^{2}k log n) where k is the length of the G-orbit of x.

Proof. To construct a transversal of G_{x} in G, we consider the action of the generators of G on the orbit x^{G}. This is described by a graph which has sk (directed) edges, labeled by generators. The coset representative corresponding to point y of this orbit is the product of the labels along the x−y path in a spanning tree. This requires a total of O(nsk) time.

Now the sk Schreier generators are also constructed in time O(nsk). Finally the reduction of their number to O(n) is accomplished via Theorem 2.3 in time O(nsk log n).

It follows that we can construct the entire stabilizer chain in Monte Carlo time O(n^{4} log n), by repreated application of Corollary 2.8, using the trivial bound k ≤ n.

We have thus obtained a strikingly simple SGS construction in O^{∼}(n^{4}) Monte Carlo time. (Such a bound albeit deterministically but with a few extra log factors, has previously been reached using big guns [BLS2].) Combined with the O(n^{4}) deterministic strong generation test of Cooperman and Finkelstein [CF], our Monte Carlo algorithm is upgraded to Las Vegas without loss of efficiency.

We should mention that with a different application of random subproducts, we can actually do a little better, achieving O(n^{4}) (again, Las Vegas) time.

3. Superfast Monte Carlo Normal Closure

The normal closure of a subgroup H in a group G is the smallest normal subgroup of G containing H.

The methods of the previous section can be used to construct the normal closure in time O(n^{3}) in permutation groups of degree n.

In this section we shall use spreaders (cf. Section 1.2) to achieve an even faster algorithm.

Theorem 3.1. If H ≤ G ≤ S_{n} then the normal closure of H in G can be constructed in Monte Carlo time O(n^{2} log^{3}(n)).

Here we assume that both G and H are given by lists of O(n) generators. This assumption is justified in view of Theorem 2.3 (cf. Lemma 2.4).

The key concept responsible for the speedup is random prefixes. The idea is that once we computed a long product of generators, it seems wasteful to use it only once. Since all the prefixes have been computed along the way, we wish to use the prefixes as well. We randomize the prefixes in two different ways. First, we randomize the order in which the elements are multiplied together; and then we select at random which prefix we want to use.

In order to ensure that a random prefix will indeed behave like a random subproduct in the sense that it will have a good chance of adding something to our current subgroup, we require that the order in which the elements are arranged spreads out the generators which are not in our current subgroup. Since we don’t know which are these generators, instead we require that every nonempty set be spread out, i.e. we need a spreader set of permutations (cf. Section 1.2).

3.1. Random spreaders

We use the terminology and notation introduced in Section 1.2.

Lemma 3.2. Let H be a random subset of size h ≠ 0 of M = {1, …, m}. Then with probability > 1 − c^{h}, spread(H) > 1/48, where c = .85.

Proof. (Sketch.) Let f be a random injective map from H_{0} = {1, …, h} to M, and H the range of f. Recall that M̄ = M ∪ {0, m + 1}; H̄_{0} is defined analogously. We extend f to an H̄_{0} → M̄ function by setting f(0) = 0 and f(h + 1) = m + 1.

For simplicity we assume 4|h. First we estimate the probability of the event A(ϵ) that there exist k = h/4 pairs of elements a_{i}, b_{i} ∈ H̄_{0} such that all the a_{i}, b_{i} are distinct and f(a_{i}) < f(b_{i}) < f(a_{i}) + ϵ(m + 1).

Let us first fix the set of the 2k elements affected. This can be done in \binom{h}{2k} ways. Then choose a perfect matching of the 2k elements selected; this can be done in (2k − 1)(2k − 3) ⋯ 1 ways. Order the pairs by their smallest elements; and finally, within the i^{th} pair, decide arbitrarily, which element will be designated a_{i} and which will be b_{i}. This last step can have 2^{k} outcomes.

Next, determine f by assigning random values to f(a_{1}), f(b_{1}), f(a_{2}), f(b_{2}), etc., in this order. Once f(a_{i}) has been decided upon, the probability that f(b_{i}) falls in the interval f(a_{i}) < f(b_{i}) < f(a_{i}) + ϵ(m + 1) is at most ϵ(m + 1)/(m + 1 − 2i). We conclude that

Prob(A(ϵ)) < \binom{h}{2k}2^{k}(ϵ(m + 1))^{k} ∏_{i=1}^{k} \frac{(2k + 1 − 2i)}{(m + 1 − 2i)} .

The right hand side is less than 2^{h+k}(ϵ(m+1))^{k}/\binom{m/2}{k} which in turn is approximately (6ϵh)^{h/4} (recall that k = h/4). In particular, Prob(A(1/(12h))) < (.85)^{h}.

Now assume that A(ϵ) fails. Then it is easy to see that for at least h/4 elements x ∈ H, δ_{H}(x) ≥ ϵ(m + 1), hence spread(H) ≥ ϵh/4. In particular for ϵ = 1/(12h) we obtain spread(H) ≥ 1/48, and this happens with probability > 1 − (.85)^{h}.

Now we are ready to prove Theorem 1.2.

Theorem 3.3. Let P = {π_{1}, …, π_{r}} be a set of random permutations of M = {1, …, m}. Assume r > C log m for some constant C. Then P is a (1/48, m)-spreader with probability > 1 − m^{−c′} where c′ = 0.23C − 1.

Proof. The probability that the spreading factor of a set of size h is < 1/48 is at most c^{hr}, where c = .85, according to the Lemma. Consequently the probability that this happens for at least one nonempty subset is at most

∑_{h=1}^{m} c^{hr}\binom{m}{h} = (1 + c^{r})^{m} − 1 < 2c^{r}m < m^{−c′},

assuming 2c^{r}m < m^{−c′}, i.e. r > 4.3((1 + c′) log m + 1).

3.2 Random prefixes and fast normal closure

Definition 3.4. A random prefix of a sequence of group elements (g_{1}, g_{2}, …, g_{k}) is an instance of a product of the first i elements, for i a random integer from 1 through k.

The following result applies to black box groups where n is the length of the strings representing each group element. It also applies to permutation groups of degree n. In both cases, we know that all subgroup chains have length O(n).

Theorem 3.5. Let G and K ≤ G be finite groups and assume all subgroup chains in G have length O(n) where n is a parameter. Assume further that G and K are given by generating sets of size O(n). Then one can construct O(n) generators for the normal closure of K in G with fixed but arbitrarily high probability using O(n log^{3}(n)) group operations.

Proof. The algorithm for constructing a sequence T of generators of the normal closure, denoted by ⟨K^{G}⟩, is described first. Fix ϵ > 0, say ϵ = 1/48, and construct an ϵ-spreader P = {π_{1}, …, π_{r}} ⊂ S_{m} for some large enough value of m (m will be of the order O(n log^{2} n)) where r = O(log m). (According to Theorem 3.3, a set of random permutations will suffice.)

Let S_{K} and S_{G} be sequences of the generators for K and G. Initially set T to S_{K}. Pre-compute all r(|T | + |S_{G}|) prefixes resulting from the members of P being applied to T and to S_{G} separately. (We use the identity element for padding, i.e. to fill slots if m is greater than S_{G} or the current size of T. Since T will be augmented at each step, the prefixes corresponding to T must be stored in balanced search trees, in the following way: the elements of T are stored, in the given order, at the leaves of a balanced binary tree (including those elements to be computed in the future; their current value is the identity). Each internal node will represent the product of the elements at the leaves in the corresponding subtree. A new element of T is inserted by replacing the identity element (which currently occupies its leaf) by its actual value. Note that each insertion-update costs O(log m) group operations only. We maintain one such tree for each π_{i}.

Now select two members π_{i} and π_{j} of P at random. Take a random prefix τ of T^{π_{i}} and conjugate it by a random prefix of S_{G}^{π_{j}}.

It follows from the spreader property of P that if ⟨T ⟩ ≠ ⟨K^{G}⟩ then, with probability Ω(1/r^{2}), the new conjugate φ will belong to ⟨K^{G}⟩ − ⟨T ⟩ (see below).

Append φ to T and update each of the r trees. (One would like to add the conjugate to T only if it is not already in ⟨T ⟩, but this cannot be efficiently tested.)

Stop when Cnr^{2} conjugates have been added to T. Finally reduce the number of generators of ⟨T ⟩ to O(n).

Correctness and timing must be verified next. As long as K^{G} ≠ ⟨T ⟩, the probability of each single conjugate adding to the group ⟨T ⟩ is Ω(1/r^{2}). But this cannot go on for too long, since any subgroup chain is of length O(n) by assumption. ¿From this a routine argument concludes that for sufficiently large C, the Cnr^{2} additional conjugates will generate K^{G} with large probability.

The timing is dominated by the time it takes to update the dynamic trees. There will be O(nr^{2}) updates, each at the cost of O(log n) group operations. Noting that r = O(log n), we obtain the stated time bound.

To see the claimed probability of a single conjugate being new, first identify M = {1, …, m} in Theorem 3.3 with S_{G} = {g_{1}, …, g_{m}} (padding with the identity element as needed). Identify H ⊆ S_{G} as H = {i: ⟨T ⟩^{g_{i}} ≠ ⟨T ⟩}.

Providing that a suitable π_{j} was chosen, the probability of a random prefix σ of S_{G}^{π_{j}} having the same property is Ω(1). Next, identify M with T = {h_{1}, …, h_{n′}} and for a given prefix σ of S_{G}^{π_{j}}, identify H ⊆ T as H = {j: h_{j}^{σ} ∉ ⟨T ⟩}. If the random prefix σ satisfied its condition ⟨T ⟩^{σ} ≠ ⟨T ⟩, then again, providing a suitable π_{i} was chosen, the probability of a random prefix τ of T^{π_{i}} having the same property is Ω(1).

Hence for random π_{i}, π_{j} ∈ P, the probability of success is Ω(1/r^{2}).

4. Point Stabilizer Sequences in Monte Carlo O(n^{3} log^{3} n)

Finally, enough machinery has been developed to present the faster algorithm for constructing point stabilizer sequences, and solving the group membership problem. First, certain concepts from permutation groups, which form the basis of a divide-and-conquer strategy, must be defined. The point stabilizer subgroup (defined in the first section) stabilizing x is denoted G_{x}. The pointwise set stabilizer subgroup containing all group elements fixing {α_{1}, …, α_{i}} is denoted G_{{α_{1},...,α_{i}}}. For G acting on Ω, the orbit O ⊆ Ω of x ∈ Ω under G is denoted x^{G} = {x^{g}: g ∈ G}. G is transitive on Ω (or just transitive, where the action is clear) if Ω contains only one orbit under G. G is intransitive if it’s not transitive. For Ψ ⊆ Ω such that Ψ^{G} = Ψ, we denote G^{Ψ} the set of permutations of G restricted to mappings on Ψ alone. Next, if there exists a set B ⊂ Ω with |B| ≥ 2 and B ≠ Ω such that for each g ∈ G either B^{g} = B or B^{g} ∩ B = ∅, then B is a block of imprimitivity of G. G is imprimitive if it is transitive and has a block of imprimitivity. If G is transitive and not imprimitive, then it is primitive. Finally, a group element g is sifted through a subgroup chain G_{k} ≤ ⋯ ≤ G_{1} with residue h if g can be factored in terms of coset representatives of G_{i} in G_{i−1} and a residual group element in G_{k}.

In contrast to the previously fastest published algorithm [BLS2], this new algorithm does not require results from the classification of finite simple groups. The algorithm does run faster if appeal is made to the result from the classification that only S_{n} and A_{n} are 6-transitive, and so the algorithm is presented in a form which takes advantage of that result. A separate classification-independent proof [Wi] by Wielandt shows that among permutation groups of degree n, only S_{n} and A_{n} are 3 log n-transitive. A weaker result by Jordan [Jo] states that only S_{n} and A_{n} are t-transitive where t = c log^{2} n/ log log n. Using one of these weaker results on transitivity adds a factor of log n and log^{2} n, respectively, to the running time.

Theorem 4.1. Given O(n^{2}) generators of a finite permutation group G acting on n points, one can construct a strong generating set for G in O(n^{3} log^{3} n) Monte Carlo time. The space requirement of the procedure is O(n^{2} log^{2} n).

The result, a strong generating set U, is returned as a sequence corresponding to a chain of subgroups G = G_{1} ≥ G_{2} ≥ ... ≥ G_{k} = 1 of length k = O(n) such that ∪_{j=i}^{k}U[j] is a set of generators for the i^{th} subgroup of the chain. For each i < k, there are two possibilities. The first one is that G_{i+1} is the stabilizer of a point in a permutation action of G_{i} (not necessarily on the original permutation domain Ω; it may have been augmented by blocks of imprimitivity in an orbit of some G_{j}, j ≤ i). In the second case, G_{i+1} is the pointwise stabilizer of an orbit O of G_{i} such that G_{i}^{O} is a giant (i.e., S_{|O|} or A_{|O|}). In the first case, U[i] is a transversal of G_{i+1} in G_{i} while in the second case U[i] is an SGS for G_{i}^{O} encoded in a labelled branching [Je] using |O| permutations (in order to satisfy the space constraints). Labelled branchings allow to sift group elements, test membership, and generate random group elements as fast as complete coset tables.

It is possible that U is not a strong generating set of G for a subgroup chain consisting of pointwise set stabilizers in a permutation action of G (since the action of G may not be extended to blocks of imprimitivity in an orbit of G_{x}). However, U enables us to generate uniformly distributed random elements of G in O(n^{2}) time and so, by Cooperman, Finkelstein, Sarawagi [CFS], we can construct an SGS V for the pointwise stabilizer subgroup chain on the original permutation domain Ω in O(n log^{2} |G|) = O(n^{3} log^{2} n) time. This new SGS supports membership testing in O(n^{2} log n) time and requires O(n^{2} log n) space. Furthermore, in O(n^{2} log n) time, it is possible to construct a labelled branching from V on Ω, supporting membership testing in O(n^{2}) time and requiring O(n^{2}) space by Cooperman and Finkelstein [CF].

Roughly speaking, the algorithm always tries to compute generators for the stabilizer of a point in the smallest orbit of the group at hand and add the transversal of the point stabilizer to U. Moreover, it tries to work in primitive groups; hence, if the action on the smallest orbit is imprimitive then it adds blocks of imprimitivity to the permutation domain, and firts computes the pointwise stabilizer of these blocks. The last consideration is that if the primitive group at hand is a giant then, counting transitivity, the algorithm recognizes it and switches to a routine designed especially to handle the giants. Throughout the algorithm, the points of the permutation domain are marked by integers, denoting the priority which ones we want to stabilize first. Initially, each point has mark 0; if G is not transitive then the points of the smallest orbit get mark 1; if the action on this orbit is not primitive, a system of blocks of imprimitivity is added with mark 2; etc.

The main routine is SGS(H, Ψ) where H is a group acting on the set Ψ. The output is a strong generating set. Descriptions of the subsidiary routines are deferred for later. In contrast to previous sections, times are reported here in terms of the asymptotic number of applications of a permutation mapping to a point, rather than the number of group multiplications. Hence O(f(n)n) time is reported rather than O(f(n)) group multiplications. The change in convention is desirable since, besides group multiplications, we have to perform some graph theoretical subroutines.

Given a group G acting on Ω, one initially sets the global variable n to |Ω|, U = ∅, and transitivity to

0. Groups always will be given by O(n) generators (by Theorem 2.3, we can suppose that G is given this way). We set the mark m(x) = 0 for all x ∈ Ω. SGS(G, Ω) is then called. All internal calculations on permutations are carried out on all n points and possibly additional points (such as points corresponding to the action on blocks).

Procedure SGS

Input: (H, Ψ) where H is a group acting on Ψ. Global variables: n, transitivity. Output: strong generating set in the form of the sequence U described above.

If Ψ = ∅ then STOP. mark ← max{m(x) : x ∈ Ψ} O ← {x ∈ Ψ : m(x) = mark} CASE:

H^{O} is intransitive:

transitivity ← 0

Let O_{1} ← smallest orbit of H^{O} For x ∈ O_{1}, m(x) ← mark + 1 Call SGS(H, Ψ)

H^{O} is imprimitive:

Let B ← Blocks(H, O) Ψ ← B ∪ Ψ For x ∈ B, m(x) ← mark + 1 Call SGS(H, Ψ)

Else: [H^{O} is primitive]

transitivity = transitivity + 1
If transitivity ≥ 6 then

[H^{O} is Sym(O) or Alt(O)] Call Fast Giant(H, O, Ψ) [It adds an SGS of H^{O} to U]

T ← Normal Generators(H, O, Ψ \ O)
H ← Normal Closure(T, H, Ψ \ O)

Call SGS(H, Ψ \ O) Else

x ← first(O) H_{x} ← Point Stab(H, x, O, Ψ) U ← U ∪ (transversal of H_{x} in H) Call SGS(H_{x}, Ψ \ {x})

The subsidiary routines are now described and timings given. With the descriptions of the subsidiary routines, it will be clear that the algorithm is correct. Descriptions of the routines are given first, followed by a proof of timing for Theorem 4.1.

Recall that n refers to the the full set of points on which G originally acts, while we may consider the action of a subgroup H (or its homomorphic image) acting non-trivially on a set Ψ. In all cases, we assume that H is defined by O(n) generators Gen(H). Further, we can always assume that |Ψ| ≤ 2n, since adding the action on blocks of imprimitivity is the only way in which Ψ can grow. Doing so, adds a new orbit with at most half as many points as the original orbit on which the group was acting.

Blocks(H, O): Returns blocks of imprimitivity for H acting on O. This assumes that H is transitive on O. It can be done in time O(|Gen(H)||O|^{2}) ≤ O(n|O|^{2}) [At].

Point Stab(H, x, O, Ψ): This returns O(n) generators for H_{x} in O(|O|n^{2} log n) Monte Carlo time, by appeal to Cor. 2.8.

Fast Giant(H, O, Ψ): If the restriction of H to act on O, H^{O}, is either Sym(O) or Alt(O) then the routine adds a set of size O(|O|) to U whose restriction to O is a strong generating set for H^{O}. Given O(n) generators of H, one can find O(log(|O|)) group elements of H which generate H^{O} in their action on O in time O(n^{2} log(|O|), by a technique using random subproducts described in [BLS2 (section 6.2)]. Then O(|O| log |O|) Schreier generators for a point stabilizer subgroup of H^{O} can be constructed in time O(n|O| log |O|). Since the point stabilizer subgroup of H^{O} must also be symmetric or alternating, continuing the same method one can alternately find reduced generating sets of size O(log |O|) and point stabilizers. Altogether, an SGS for H^{O} is constructed in O(n|O|^{2} log^{2} |O|) time such that each point stabilizer is generated by O(log |O|) elements. In O(n|O|^{2}) further time, the two generators of H^{O} needed for the presentation of H^{O} in [BLS2 (section 7)] and a labelled branching constructed from these two generators can be obtained. We add this labelled branching to U.

Normal Generators(H, O, Ψ − O: Group elements T (called normal generators) are constructed whose action on O is trivial, such that ⟨T^{H}⟩ = H^{Ψ−O}. For a general description, see [BLS2 (Lemma 7.1)]. In this setting, the routine is invoked only when O is an orbit on which H acts as the symmetric or alternating group. Having constructed a point stabilizer chain for the points of O, all generators of H are sifted through the point stabilizer chain in time O(n^{2}|O|), until their residue acts trivially on O. The residues are added to the set T. Then, a presentation for H^{O} of size |O| is added to T and the conjugates {h^{g} : g ∈ Gen(H), h ∈ Gen(H^{O}}) are sifted as in [BLS2]. (Note that H^{O} has only two generators.) Thus the overall timing to create the normal generators will be O(n^{2}|O|).

Normal Closure(T, H, Ψ \ O): The normal closure can be executed in time O(n^{2} log^{3} n) by Theorem 3.1.

Next, we estimate the total time requirement of calls to these subroutines during the execution of the algorithm. We claim that Σ|O| = O(n), where O runs over orbits of intermediate groups H such that Fast Giant(H, O, Ψ) is called. This is true since the pointwise stabilizer chain of points in such orbits defines a Σ|O| long subgroup chain of the original group G. We obtain immediately that calls to Fast Giant add O(n) permutations to U and the total time requirement for calls

of Fast Giant, Normal Generators, Normal Closure is

O(n^{3} log^{3} n).

In order to estimate the cost of calls to Point Stab and the size of U, we need the following lemma. Define an antigreedy sequence for G acting on Ψ to be (α_{1}, α_{2}, …, α_{n}), where α_{i} ∈ Ψ−{α_{1}, …, α_{i−1}} and α_{i} is in the smallest orbit of G_{{α_{1},...,α_{i−1}}}. Note that in general, a group does not have a unique anti-greedy sequence. Define G^{(i)} = G_{{α_{1},...,α_{i−1}}}.

Lemma 4.2. Let G be a uniprimitive group acting on Ψ with |Ψ| = n. Let the smallest orbit under G_{x}, Δ, have length |Δ| = d. Then for an anti-greedy sequence (α_{i}), and for all j, |α_{j}^{G^{(j)}}| ≤ d. (G^{(k)} is always taken with respect to the ordering (α_{i}).)

Proof: Recall that a primitive group G is uniprimitive if G is not 2-transitive. Let x = α_{1} ∈ Ψ. So, |α_{2}^{G^{(2)}}| = d. Assume the theorem is false, and let j be the smallest integer such that |α_{j}^{G^{(j)}}| > d. Let Γ_{i} = {α_{1}, …, α_{i}}. Let K = {g ∈ G: x^{g} ∈ Γ_{j−1}}. If ∪_{g∈K}Γ_{j−1}^{g} = Γ_{j−1}, then Γ_{j−1} is a block of imprimitivity, in contradiction to the imprimitivity of G.

Otherwise, there is a g ∈ K and an ℓ < j, such that α_{ℓ}^{g} ∉ Γ_{j−1}. For g fixed, let ℓ be the smallest integer satisfying the previous condition. This implies that |(α_{ℓ}^{g})^{G^{(ℓ)}}| ≥ |(α_{ℓ}^{g})^{G^{(j)}}| ≥ |α_{j}^{G^{(j)}}| > d. Yet |α_{ℓ}^{G^{(ℓ)}}| ≤ d. So,

there is a h ∈ G^{(j)} such that α_{ℓ}^{ghg^{−1}} ∉ α_{ℓ}^{G^{(ℓ)}}. Since ℓ was the least integer satisfying its condition, Γ_{ℓ−1}^{g} ⊂ Γ_{j−1}. This combined with h ∈ G^{(j)} yields ghg^{−1} ∈ G^{(ℓ)}, which contradicts the defining property of h. Hence α_{ℓ}^{g} ∉ Γ_{j−1} for ℓ < j also leads to a contradiction, and the Lemma is true.

Lemma 4.3. The algorithm SGS(G, Ω), |Ω| = n, creates an SGS U of size ≤ 6n log^{2} n.

Proof: We prove the lemma by induction on n. Let f(k) denote the maximum size of SGS created from input on k points and let f(G) be the size of the SGS created from input G ≤ Sym(Ω), |Ω| = k. If G is intransitive than we obtain the estimate f(G) ≤ Σf(k_{i}), where Σk_{i} ≤ k (Σk_{i} < k is possible since stabilizing the first orbit may stabilize points in other orbits as well). If G is transitive but imprimitive than we obtain f(G) ≤ f(m) + Σf(k_{i}), where 2 ≤ m ≤ k/2 is the size of a block system of G, each k_{i} ≤ k/m, and Σk_{i} ≤ k. The function 6k log^{2} k satisfies this recursion as well. If G is a giant then f(G) ≤ 5k + k since the algorithm adds transversals for the stabilizers of the first five points to U and then adds an SGS of size < k for the rest. Finally, if G is primitive and not a giant then either f(G) ≤ 4k +f(m)+Σf(k_{i}), where 2 ≤ m ≤ k/2, each k_{i} ≤ k/m, and ∑ k_{i} ≤ k or f(G) ≤ 5k+∑ f(k_{i}) where each k_{i} ≤ k/2 and ∑ k_{i} ≤ k. The first case occurs when after stabilizing ≤ 4 points, we arrive to a transitive, imprimitive group. The second case occurs when after stabilizing ≤ 4 points, we obtain a uniprimitive group. This is the point where we use Lemma 4.2: since the algorithm processes points in an anti-greedy sequence, the length k_{i} of orbits it encounters cannot exceed the length of the first orbit it processes, which is clearly < k/2. Again, it is easy to check that the function 6k log^{2} k satisfies both of these recursions.

Lemma 4.3 implies that the total cost of calls of Point Stab is O(n^{3} log^{3} n) since the addition of a transversal of size m to U requires O(mn^{2} log n) time. Finally, we estimate the cost of orbit computations during the algorithm and the total cost of calls of the routine Blocks. For a fixed subgroup G_{i} in the subgroup chain created by the algorithm, the total cost of orbit computations in calls SGS(G_{i}, Ψ) is O(n^{2}) so the O(n) bound on subgroup chain lenghts gives O(n^{3}) total time requirement.

If Blocks(H, O) was called such that H^{O} is primitive then, in the next step, the algorithm added |O| permutations to U. Hence the O(n log^{2} n) bound on the size of U proves that the cost of such calls of Blocks(H, O) is ∑_{O} O(n|O|^{2}) = O(n^{3} log^{2} n). Finally, we claim that ∑ |O| = O(n log n) for those blocks O where Blocks(H, O) was called with H^{O} imprimitive. This claim can be proven along the lines of Lemma 4.3, finishing the proof of Theorem 4.1.

References.

[At] M.D. Atkinson, “An algorithm for finding the blocks of a permutation group”, Math. Comp. 29 (1975), pp. 911–913.

[Ba1] L. Babai, “Monte Carlo algorithms in graph isomorphism testing”, Université de Montréal Tech. Report D.M.S. 79-10, 1979.

[Ba2] L. Babai, “On the Length of Chains of Subgroups in the Symmetric Group”, Comm. in Algebra 14 (1986), pp. 1729–1736.

[BCFS] L. Babai, G. Cooperman, L.Finkelstein, and Á. Seress, “Nearly Linear Time Algorithms for Permutation Groups with a Small Base”, manuscript

[BLS1] L. Babai, E. Luks, and Á. Seress, “Permutation Groups in NC”, Proc. 19th ACM STOC (1987), pp. 409–420.

[BLS2] L. Babai, E. Luks, and Á. Seress, “Fast Management of Permutation Groups”, Proc. 28th IEEE FOCS (1988), pp. 272–282.

[BLS3] L. Babai, E. Luks, and Á. Seress, “Fast Deterministic Management of Permutation Groups”, in preparation.

[BS] L. Babai and Á. Seress, “On the Degree of Transitivity of Permutation Groups: A Short Proof”, J. Combinatorial Theory: Series A 45(2) (1987), pp. 310–315.

[BSz] L. Babai, E. Szemerédi, “On the complexity of matrix group problems I”, 25th IEEE FOCS, Palm Beach FL (1984), pp. 229-240.

[BFP] C.A. Brown, L. Finkelstein, and P.W. Purdom, “A New Base Change Algorithm for Permutation Groups”, SIAM J. Computing 18 (1989), pp. 1037-1047.

[CST] P.J. Cameron, R. Solomon, A. Turull, “Chains of subgroups in symmetric groups”, J. of Algebra 127 (1989), pp. 340-352.

[CF] G. Cooperman and L. Finkelstein, “A Strong Generating Test and Short Presentations for Permutation Groups”, to appear in J. Symbolic Computation.

[CFS] G. Cooperman, L. Finkelstein and N. Sarawagi, “A Random Base Change Algorithm for Permutation Groups”, Proc. of the 1990 International Symposium on Symbolic and Algebraic Manipulation (ISSAC-90), ACM press and Addison-Wesley, Aug., 1990.

[FHL] M. Furst, J. Hopcroft and E. Luks, “Polynomial Time Algorithms For Permutation Groups”, Proc. 21st IEE FOCS (1980), pp. 36–41.

[Je] M. Jerrum, “A Compact Representation for Permutation Groups”, J. Algorithms 7 (1986), pp. 60–78.

[Jo] C. Jordan, “Nouvelles recherches sur la limite de transitivité des groupes non alternés”, Bull. Soc. Math. France 1 (1873), pp. 35–60.

[Kn] D.E. Knuth, “Notes on Efficient Representation of Permutation Groups” (1981), unpublished manuscript.

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

[Wi] H. Wielandt, “Abschätzungen für den Grad einer Permutationsgruppe von vorgeschriebenem Transitivitätsgrad”, Dissertation, Berlin, 1934. Schriften Math. Seminars Inst. Angew. Math. Univ. Berlin 2 (1934), pp. 151–174.