Content deleted Content added
m Schreier Sim's is not for any "finite group" but for any "permutation group". For example. this algorithm can not be used for `Finitely Presented Groups` |
Add an explanation of the actual algorithm that is the subject of this page. |
||
Line 17:
In modern computer algebra systems, such as [[GAP computer algebra system|GAP]] and [[Magma computer algebra system|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.
<source lang="cpp">
struct Group
{
uint stabPoint; // An index into the base for the point stabilized by this group's subgroup.
OrbitTree orbitTree; // A tree to keep track of the orbit in our group of the point stabilized by our subgroup.
TransversalSet transversalSet; // A set of coset representatives of this group's subgroup.
GeneratorSet generatorSet; // A set of permutations generating this group.
Group* subGroup; // A pointer to this group's subgroup, or null to mean the trivial 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 )
{
Group* group = new Group;
for( generator in generatorSet )
group->Extend( generator, base );
return group;
}
// Extend the stabilizer chain rooted at this group with the given generator.
void Group::Extend( const Permutation& generator, uint* base )
{
// Sift the given generator to determine whether or not it is redundant.
if( IsMember( generator ) )
return; // Reject the generator! This is the major optimization of Schreier-Sims.
// Our group just got bigger, but the stabilizer chain rooted at our subgroup is still the same.
generatorSet.Add( generator );
// Explore all new orbits we can reach with the addition of the new generator.
// Note that if the tree was empty to begin with, the identity must be returned
// in the set to satisfy a condition of Schreier's lemma.
newTerritorySet = orbitTree.Grow( generator, base );
// By the orbit-stabilizer theorem, the permutations in the returned set are
// coset representatives of the cosets of our subgroup.
for( permutation in newTerritorySet )
transversalSet.Add( permutation );
// We now apply Schreier's lemma to find new generators for our subgroup.
// Some iterations of this loop are redundant, but we ignore that for simplicity.
for( cosetRepresentative in transversalSet )
{
for( generator in generatorSet )
{
schreierGenerator = CalcSchreierGenerator( cosetRepresentative, generator );
if( !subGroup )
subGroup = new SubGroup( stabPoint + 1 );
subGroup->Extend( schreierGenerator, base );
}
}
}
</source>
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 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]].
==References==
| |||