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)