Most of the algorithms for permutation groups need a stabilizer chain of the group. The concept of stabilizer chains was introduced by Charles Sims in Sim70.
If [b_1, ldots, b_n] is a list of points, G^{(1)} = G and G^{(i+1)} = Stab_{G^{(i)}}(b_i) such that G^{(n+1)} = { () }. The list [b_1, ldots, b_n] is called a base of G, the points b_i are called basepoints. A set S of generators for G satisfying the condition < S cap G^{(i)} > = G^{(i)} for each 1 leq i leq n, is called a strong generating set (SGS) of G. More precisely we ought to say that a set S that satisfies the conditions above is a SGS of G relative to B. The chain of subgroups of G itself is called the stabilizer chain of G relative to B.
Since [b_1, ldots, b_n], where n is the degree of G and b_i are the moved points of G, certainly is a base for G there exists a base for each permutation group. The number of points in a base is called the length of the base. A base B is called reduced if no stabilizer in the chain relative to B is trivial, i.e., there exists no i such that G^{(i)} = G^{(i+1)}. Note that different reduced bases for one group G may have different length. For example, the Chevalley Group G_2(4) possesses reduced bases of length 5 and 7.
Let R^{(i)} be a right transversal of G^{(i+1)} in G^{(i)}, i.e., a set of right coset representatives of the cosets of G^{(i+1)} in G^{(i)}. Then each element g of G has a unique representation of the following form g = r_n ldots r_1 with r_i in R^{(i)}. Thus with the knowledge of the transversals R^{(i)} we know each element of G, in principle. This is one reason why stabilizer chains are one of the most useful tools for permutation groups. Furthermore basic group theory tells us that we can identify the cosets of G^{(i+1)} in G^{(i)} with the points in O^{(i)} := b_i^{G^{(i)}}. So we could represent a transversal as a list T such that T[p] is a representative of the coset corresponding to the point p in O^{(i)}, i.e., an element of G^{(i)} that takes b_i to p.
For permutation groups of small degree this might be possible, but for permutation groups of large degree it is still not good enough. Our goal then is to store as few different permutations as possible such that we can still reconstruct each representative in R^{(i)}, and from them the elements in G. A factorized inverse transversal T is a list where T[p] is a generator of G^{(i)} such that p^{T[p]} is a point that lies earlier in O^{(i)} than p (note that we consider O^{(i)} as a list not as a set). If we assume inductively that we know an element r in G^{(i)} that takes b_i to p^{T[p]}, then r T[p]^{-1} is an element in G^{(i)} that takes b_i to p.
A stabilizer chain (see StabChain, Permutation Group Records) is stored recursively in GAP. The group record of a permutation group G with a stabilizer chain has the following additional components.
orbit:orbit[1] (which is the basepoint) under
the action of the generators.
transversal:
stabilizer:orbit[1] in the group
generated by generators. The components of this record are
again generators, orbit, transversal, identity and
stabilizer. The
last stabilizer in the stabilizer chain only contains the
components generators, which is an empty list, and identity.
stabChain:stabChain
record are described in section Permutation Group Records.
Note that the values of these components are changed by functions that change, extend, or reduce a base (see StabChain, ExtendStabChain, and ReduceStabChain).
Note that the records that represent the stabilizers are not group
records (see Group Records). Thus you cannot take such a stabilizer
and apply group functions to it. The last stabilizer in the stabilizer
chain is a record whose component generators is empty.
Below you find an example for a stabilizer chain for the symmetric group of degree 4.
rec(
identity := (),
generators := [ (1,2), (1,2,3,4) ],
orbit := [ 1, 2, 4, 3 ],
transversal := [ (), (1,2), (1,2,3,4), (1,2,3,4) ],
stabilizer := rec(
identity := (),
generators := [ (3,4), (2,4) ],
orbit := [ 2, 4, 3 ],
transversal := [ , (), (3,4), (2,4) ],
stabilizer := rec(
identity := (),
generators := [ (3,4) ],
orbit := [ 3, 4 ],
transversal := [ ,, (), (3,4) ],
stabilizer := rec(
identity := (),
generators := [ ]
)
)
)
)
GAP 3.4.4