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) |