This paper presents a new algorithm for determining the order of a solvable permutation group from a set of generators. During the computation, a base and strong generating set and a polycyclic generating sequence are also obtained.
The following problem is frequently encountered while computing with groups: Given a set X of permutations on a finite set ~, determine the order of the group G generated by X. Usually we are also asked to determine a base and strong generating set for G. Among the known algorithms, the one with the best asymptotic behaviour is given in Jerrum (1986). Let n = I~1. Assuming that X is not too large, say IX[ < n, we can find a base and strong generating set for G in time 0(n 5) for the worst case. Another algorithm, the Schreier-Todd-Coxeter method described in Leon (1980), is frequently used in actual computation. Its worst case complexity has not been determined.
In the present paper we present an algorithm which may be used when the group G is solvable. The algorithm involves a recursive step. If the input generating set X does not generate a solvable group G, then the recursion continues indefinitely. In order to handle this possibility, one can specify a limit to the depth of the recursion which, if attained, indicates that G is not solvable. When G is solvable, the recursion depth of the algorithm is bounded by the derived length of G. In Dixon (1968) it is shown that the derived length of a solvable permutation group of degree n is at most (5 log3 n)/2.
The group-theoretic terminology used in this paper is standard. The symmetric group on ~ will be denoted by 2(~). Permutations act on the right. Additional background concerning the computational aspects of the theory of permutation groups may be found in Cannon (1984).
Let X be a set of permutations of a finite set f2 and let fl be a sequence fll ..... fir of points of ~. For 1 N i\_< r let X (0 be the set of elements of X which fix/71 ..... fl~-1 and let A~ be the orbit of H (~ = . The sequence fl is a base for G and X is a strong generating set for G relative to fl if a(X, fl) = rGf, or equivalently, U = G. In choosing the u~(c~), we J"