40.8 Stabilizer Chain Records

If a permutation group has a stabilizer chain, this is stored as a recursive structure. This structure is itself a record S and it has (1) components that provide information about one level  G⁽ⁱ⁾ of the stabilizer chain (which we call the ``current stabilizer'') and (2) a component stabilizer that holds another such record, namely the stabilizer chain of the next stabilizer  G<sup>(i+1)</sup>. This gives a recursive structure where the ``outermost'' record representing the ``topmost'' stabilizer is bound to the group record component stabChain and has the components explained below. Note: Since the structure is recursive, never print a stabilizer chain! (Unless you want to exercise the scrolling capabilities of your terminal.)

identity

the identity element of the current stabilizer.

labels

a list of permutations which contains labels for the Schreier tree of the current stabilizer, i.e., it contains elements for the factorized inverse transversal. The first entry is this list is always the identity, for reasons explained below under translabels. Note that GAP tries to arrange things so that the labels components are identical (i.e., the same GAP object) in every stabilizer of the chain; thus the labels of a stabilizer do not necessarily all lie in the this stabilizer (but see genlabels below).

genlabels

a list of integers indexing some of the permutations in the labels component. The labels addressed in this way form a generating set for the current stabilizer. If the genlabels component is empty, the rest of the stabilizer chain represents the trivial subgroup, and can be ignored, e.g., when calculating the size.

generators

a list of generators for the current stabilizer. Usually, it is labels{ genlabels }.

orbit

the vertices of the Schreier tree, which form the basic orbit b_i^G(i), ordered in such a way that the base point b_i is first in the list.

translabels

the factorized inverse transversal that was found during the orbit algorithm carried out with the inverses of labels{ genlabels }, starting from the base point. The directed edge from the point i to the point j = i ^g in the Schreier tree is represented by labels[ translabels[j] ] = g in the stabilizer chain (note that i can be reconstructed as j^g-1 from this information). The entries in the translabels component are thus just integers giving the positions of the appropriate labels in the labels component. The base point itself (i.e., the root of the Schreier tree) corresponds to the entry 1 in translabels. This makes it possible to assign transversal{ orbit } := labels{ translabels{ orbit } } (see sublist!assignment in the Reference Manual and transversal below). The translabels component pays off handsomely in the stabilizer chain conjugation (see Generalized Conjugation Technique in ``Extending GAP'').

transversal

is another representation of the factorized inverse transversal: as a list with transversal[j] = labels[ translabels[j] ] (the base point itself has entry ()). To look up an entry in this list is faster than to evaluate the expression on the right hand side, and since this operation appears most often in permutation group code (e.g., in the function InverseRepresentative below), the speed-up is really worth this extra record component.

stabilizer

If the current stabilizer is not yet the trivial group, the stabilizer chain continues with the stabilizer of the current base point, which is again represented as a record with components labels, identity, genlabels, generators, orbit, translabels, transversal (and possibly stabilizer). This record is bound to the stabilizer component of the current stabilizer. The last member of a stabilizer chain is recognized by the fact that it has no stabilizer component bound.

gap> g:=Group((1,2,3,4),(1,2));;
gap> StabChain(g);
rec(
  labels := [ (), (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ],
  genlabels := [ 2, 3, 4, 5 ],
  generators := [ (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ],
  identity := (),
  relativeOrders := [ 2, 3, 2, 2 ],
  stabilizer := rec(
      labels := [ (), (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ],
      genlabels := [ 2, 3 ],
      generators := [ (3,4), (2,4,3) ],
      identity := (),
      stabilizer := rec(
          labels := [ (), (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ],
          genlabels := [ 2 ],
          generators := [ (3,4) ],
          identity := (),
          stabilizer := rec(
              labels := [ (), (3,4), (2,4,3), (1,4)(2,3), (1,2)(3,4) ],
              genlabels := [  ],
              generators := [  ],
              identity := () ),
          orbit := [ 3, 4 ],
          translabels := [ ,, 1, 2 ],
          transversal := [ ,, (), (3,4) ] ),
      orbit := [ 2, 3, 4 ],
      translabels := [ , 1, 3, 3 ],
      transversal := [ , (), (2,4,3), (2,4,3) ] ),
  orbit := [ 1, 2, 4, 3 ],
  translabels := [ 1, 5, 4, 4 ],
  transversal := [ (), (1,2)(3,4), (1,4)(2,3), (1,4)(2,3) ])
gap> BaseOfGroup(g);
[ 1, 2, 3 ]
gap> StabChainOptions(g);
rec(
  random := 1000 )
gap> DefaultStabChainOptions;
rec(
  reduced := true,
  random := 1000,
  tryPcgs := true )

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