The Schreier–Sims algorithm is an algorithm in computational group theory, named after the mathematicians Otto Schreier and Charles Sims. This algorithm can find the order of a finite permutation group, determine whether a given permutation is a member of the group, and other tasks in polynomial time. It was introduced by Sims in 1970, based on Schreier's subgroup lemma. The running time was subsequently improved by Donald Knuth in 1991. Later, an even faster randomized version of the algorithm was developed.
Background and timing The algorithm is an efficient method of computing a base and strong generating set (BSGS) of a permutation group. In particular, an SGS determines the order of a group and makes it easy to test membership in the group. Since the SGS is critical for many algorithms in computational group theory, computer algebra systems typically rely on the Schreier–Sims algorithm for efficient calculations in groups. The running time of Schreier–Sims varies on the implementation. Let G ≤ S n {\displaystyle G\leq S_{n}} be given by t {\displaystyle t} generators. For the deterministic version of the algorithm, possible running times are:
O ( n 2 log 3 | G | + t n log | G | ) {\displaystyle O(n^{2}\log ^{3}|G|+tn\log |G|)} requiring memory O ( n 2 log | G | + t n ) {\displaystyle O(n^{2}\log |G|+tn)}
O ( n 3 log 3 | G | + t n 2 log | G | ) {\displaystyle O(n^{3}\log ^{3}|G|+tn^{2}\log |G|)} requiring memory O ( n log 2 | G | + t n ) {\displaystyle O(n\log ^{2}|G|+tn)}
The use of Schreier vectors can have a significant influence on the performance of implementations of the Schreier–Sims algorithm. The Monte Carlo variations of the Schreier–Sims algorithm have the estimated complexity:
O ( n log n log 4 | G | + t n log | G | ) {\displaystyle O(n\log n\log ^{4}|G|+tn\log |G|)} requiring memory O ( n log | G | + t n ) {\displaystyle O(n\log |G|+tn)} . Modern computer algebra systems, such as GAP and Magma, typically use an optimized Monte Carlo algorithm.
Outline of basic algorithm Following is C++-style pseudo-code for the basic idea of the Schreier-Sims algorithm. It is meant to leave out all finer details, such as memory management or any kind of low-level optimization, so as not to obfuscate the most important ideas of the algorithm. Its goal is not to compile.
Notable details left out here include the growing of the orbit tree and the calculation of each new Schreier generator. In place of the orbit tree, a Schreier vector can be used, but the idea is essentially the same. The tree is rooted at the identity element, which fixes the point stabilized by the subgroup. Each node of the tree can represent a permutation that, when combined with all permutations in the path from the root to it, takes that point to some new point not visited by any other node of the tree. By the orbit-stabilizer theorem, these form a transversal of the subgroup of our group that stabilizes the point whose entire orbit is maintained by the tree. Calculating a Schreier generator is a simple application of the Schreier's subgroup lemma. Another detail left out is the membership test. This test is based upon the sifting process. A permutation is sifted down the chain at each step by finding the containing coset, then using that coset's representative to find a permutation in the subgroup, and the process is repeated in the subgroup with that found permutation. If the end of the chain is reached (i.e., we reach the trivial subgroup), then the sifted permutation was a member of the group at the top of the chain.
References Knuth, Donald E. "Efficient representation of perm groups". Combinatorica 11 (1991), no. 1, 33–43. Seress, A., Permutation Group Algorithms, Cambridge U Press, 2002. Sims, Charles C. "Computational methods in the study of permutation groups", in Computational Problems in Abstract Algebra, pp. 169–183, Pergamon, Oxford, 1970.
