general.hpp File Reference

General plans for permutation groups. More...

Go to the source code of this file.

Detailed Description

General plans for permutation groups.

Orbits and stabilisers
  • The first task is to implement the calculation of orbits and stabilisers according to section 4.1 in [Handbook of computational group theory].
  • And then, of course, we need to connect to Gap.
  • With exercise 2 in section 4.6.5 in [Handbook of computational group theory] for a subgroup H of S_n (H likely just given by a set of generators) the centraliser C(H) is computable in polynomial time (that is, a set of generating elements).
  • This includes the case of the centraliser of a single element x.
    1. The size is n! / |K(x)|, where K(x) is the conjugacy class of x. (We need a function for computing this size, and also computing the conjugacy class needs to be provided as listing all permutations with the same cycle type.)
    2. Assume the complete cycle decomposition of x is (c_1, ..., c_k).
    3. Then a generating set consists of the c_1, ..., c_k together with generating sets for the block permutation groups which permute cycles of the same length (using the given order, so that only whole blocks are commuted).
    4. In this way some form of "product decomposition" is achieved?

Definition in file general.hpp.