21.8 MakeStabChain

MakeStabChain( G )
MakeStabChain( G, lst )

MakeStabChain computes a reduced stabilizer chain for the permutation group G.

If no stabilizer chain for G is already known and no argument lst is given, it computes a reduced stabilizer chain for the lexicographically smallest reduced base of G.

If no stabilizer chain for G is already known and an argument lst is given, it computes a reduced stabilizer chain with a base that starts with the points in lst. Note that points in lst that would lead to trivial stabilizers will be skipped (see ExtendStabChain).

Deterministically, the stabilizer chain is computed using the Schreier-Sims-Algorithm, which is described in Leo80. The time used is in practice proportional to the third power of the degree of the group.

If a stabilizer chain for G is already known and no argument lst is given, it reduces the known stabilizer chain.

If a stabilizer chain for G is already known and an argument lst is given, it changes the stabilizer chain such that the result is a reduced stabilizer chain with a base that starts with the points in lst (see ExtendStabChain). Note that points in lst that would lead to trivial stabilizers will be skipped.

The algorithm used in this case is called basechange, which is described in But82. The worst cases for the basechange algorithm are groups of large degree which have a long base.

    gap> s4 := Group( (1,2), (1,2,3,4) );
    Group( (1,2), (1,2,3,4) )
    gap> MakeStabChain( s4 );    # compute a stabilizer chain
    gap> Base( s4 );
    [ 1, 2, 3 ]
    gap> MakeStabChain( s4, [4,3,2,1] );    # perform a basechange
    gap> Base( s4 );
    [ 4, 3, 2 ] 

MakeStabChain mainly works by calling StabChain with appropriate parameters.

Previous Up Top Next
Index