The Schreier–Sims algorithm is an
algorithm in
computational group theory, named after the mathematicians
Otto Schreier and
Charles Sims Charles Sims may refer to:
* Charles Sims (painter) (1873–1928), British painter
* Charles Sims (mathematician) (1938–2017), American mathematician
* Charles Sims (aviator) (1899–1929), British World War I flying ace
* Charles Sims (America ...
. This algorithm can find the
order
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...
of a finite permutation group, test membership (is a given permutation contained in a group?), and many other tasks in polynomial time. It was introduced by Sims in 1970, based on
Schreier's subgroup lemma In mathematics, Schreier's lemma is a theorem in group theory used in the Schreier–Sims algorithm and also for finding a presentation of a subgroup.
Statement
Suppose H is a subgroup of G, which is finitely generated with generating set S, tha ...
. The timing 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 mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to it ...
. 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
be given by
generators. For the
deterministic
Determinism is a philosophical view, where all events are determined completely by previously existing causes. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping motives and consi ...
version of the algorithm, possible running times are:
*
requiring memory
*
requiring memory
The use of
Schreier vectors can have a significant influence on the performance of implementations of the Schreier–Sims algorithm.
For
Monte Carlo variations of the Schreier–Sims algorithm, we have the following estimated complexity:
:
requiring memory
In modern computer algebra systems, such as
GAP and
Magma, an optimized
Monte Carlo algorithm is typically used.
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. It does not need to actually compile.
struct Group
;
// The given set of generators need not be a strong generating set. It just needs to generate the group at the root of the chain.
Group* MakeStabChain(const GeneratorSet& generatorSet, uint* base)
// Extend the stabilizer chain rooted at this group with the given generator.
void Group::Extend(const Permutation& generator, uint* base)
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 matter of applying
Schreier's subgroup lemma In mathematics, Schreier's lemma is a theorem in group theory used in the Schreier–Sims algorithm and also for finding a presentation of a subgroup.
Statement
Suppose H is a subgroup of G, which is finitely generated with generating set S, tha ...
.
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.
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the Acm Turing award, ACM Turing Award, informally considered the Nobel Pri ...
"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.
{{DEFAULTSORT:Schreier-Sims algorithm
Computational group theory
Permutation groups