40.7 Construction of Stabilizer Chains

These commands compute a stabilizer chain for the permutation group G; additionally, StabChainMutable is also an attribute for the group homomorphism permhomom whose source is a permutation group.

StabChainOp is an operation with two arguments G and options, the latter being a record which controls some aspects of the computation of a stabilizer chain (see below); StabChainOp returns a mutable stabilizer chain. StabChainMutable is a mutable attribute for groups or homomorphisms, its default method for groups is to call StabChainOp with empty options record. StabChainImmutable is an attribute with immutable values; its default method dispatches to StabChainMutable.

StabChain is a function with first argument a permutation group G, and optionally a record options as second argument. If the value of StabChainImmutable for G is already known and if this stabilizer chain matches the requirements of options, StabChain simply returns this stored stabilizer chain. Otherwise StabChain calls StabChainOp and returns an immutable copy of the result; additionally, this chain is stored as StabChainImmutable value for G. If no options argument is given, its components default to the global variable DefaultStabChainOptions (see DefaultStabChainOptions). If base is a list of positive integers, the version StabChain( G, base ) defaults to StabChain( G, rec( base:= base ) ).

If given, options is a record whose components specify properties of the desired stabilizer chain or which may help the algorithm. Default values for all of them can be given in the global variable DefaultStabChainOptions (see DefaultStabChainOptions). The following options are supported.

base (default an empty list)

A list of points, through which the resulting stabilizer chain shall run. For the base B of the resulting stabilizer chain S this means the following. If the reduced component of options is true then those points of base with nontrivial basic orbits form the initial segment of B, if the reduced component is false then base itself is the initial segment of B. Repeated occurrences of points in base are ignored. If a stabilizer chain for G is already known then the stabilizer chain is computed via a base change.

knownBase (no default value)

A list of points which is known to be a base for the group. Such a known base makes it easier to test whether a permutation given as a word in terms of a set of generators is the identity, since it suffices to map the known base with each factor consecutively, rather than multiplying the whole permutations (which would mean to map every point). This speeds up the Schreier-Sims algorithm which is used when a new stabilizer chain is constructed; it will not affect a base change, however. The component knownBase bears no relation to the base component, you may specify a known base knownBase and a desired base base independently.

reduced (default true)

If this is true the resulting stabilizer chain S is reduced, i.e., the case G⁽ⁱ⁾ = G⁽ⁱ⁺¹⁾ does not occur. Setting reduced to false makes sense only if the component base (see above) is also set; in this case all points of base will occur in the base B of S, even if they have trivial basic orbits. Note that if base is just an initial segment of B, the basic orbits of the points in B \base are always nontrivial.

tryPcgs (default true)

If this is true and either the degree is at most 100 or the group is known to be solvable, GAP will first try to construct a pcgs (see Chapter Polycyclic Groups) for G which will succeed and implicitly construct a stabilizer chain if G is solvable. If G turns out non-solvable, one of the other methods will be used. This solvability check is comparatively fast, even if it fails, and it can save a lot of time if G is solvable.

random (default 1000)

If the value is less than  1000, the resulting chain is correct with probability at least  random/1000. The random option is explained in more detail in Randomized Methods for Permutation Groups.

size (default Size( G ) if this is known,

i.e., if HasSize( G ) is true)

If this component is present, its value is assumed to be the order of the group G. This information can be used to prove that a non-deterministicly constructed stabilizer chain is correct. In this case, GAP does a non-deterministic construction until the size is correct.

limit (default Size( Parent( G ) ) or

StabChainOptions( Parent( G ) ).limit if this is present)

If this component is present, it must be greater than or equal to the order of G. The stabilizer chain construction stops if size limit is reached.

is a record that stores the options with which the stabilizer chain stored in StabChainImmutable has been computed (see StabChain for the options that are supported).

are the options for StabChain which are set as default.

If a base base for a permutation group G and a strong generating set sgs for G with respect to base are given. one must be the appropriate One (in most cases this will be ()). This function constructs a stabilizer chain without the need to find Schreier generators; so this is much faster than the other algorithms.

returns the reduced stabilizer chain corresponding to the base [1,2,3,4,¼].

[Top] [Previous] [Up] [Next] [Index]