0. Mathematical notes

This is a very brief (and highly compact) recollection of definitions and results in permutation-group theory, taken from Butler 1991.
    - A permutation group G acts on a set of points P on the right.
    - The image of p in P under g in G is denoted p^g and (p^g)^h = p^(gh) for all p, g and h.
    - The orbit of p under G is the set p^G={p^g | g in G} of images of p.
    - The pointwise stabilizer of p in G is the group G_p={g in G | p^g=p} of elements that fix p.
    - A base for G is a sequence B={b1, b2, ..., bk} of points such that only the identity element of G fixes all points in the base.
    - Associated with a base there is a chain of subgroup stabilizers G^(i), i=1, 2, ..., k+1, where G^(i)=G_{b1, b2, ..., b_(i-1)}.
    - A subset S of G is a strong generating set of G relative to B if S contains a generating set for each stabilizer G^(i) in the chain.
    - If we define a total order on P, then there is an induced lexicographical order on G and on the base images B^G. If we insist that b1, b2, ..., bk are the first k points of P then the order on G corresponds to the order on the base images. In any case, the identity element is the smallest element of the group.
    - Given a group G and a stabilizer G_b there is a one-to-one correspondence between the cosets of G_b in G and the points of the orbit b^G. Using the order of permutations defined in the previous point we can choose a representative in each of those cosets.
    - An element g of G is uniquely determined by its base image B^g = {b1^g, b2^g, ..., bk^g}. Actually there is a unique decomposition of g as a product of the representatives of the cosets identified by those images.
    - This equivalence between permutations and base images is the key for a plethora of highly efficient algorithms which can answer any question on the group by using backtracking through the hierarchy of cosets and stabilizers.

Created by Mathematica  (May 16, 2008) Valid XHTML 1.1!