21.22 Operations of Permutation Groups

All functions that deal with operations of groups are applicable to permutation groups (see Operations of Groups). This section describes which functions are implemented specially for permutation groups. Functions not mentioned here are handled by the default methods described in the respective sections.

IsSemiRegular( G, D, opr )

IsSemiRegular returns true if G operates semiregularly on the domain D and false otherwise.

If D is a list of integers and opr is OnPoints, IsSemiRegular uses the lemma that says that such an operation is semiregular if all orbits of G on D have the same length, and if for an arbitrary point p of D and for each generator g of G there is a permutation z_g (not necessarily in G) such that p^{z_g} = p^g and which commutes with all elements of G, and if there is a permutation z (again not necessarily in G) that permutes the orbits of G on D setwise and commutes with all elements of G. This can be tested in time proportional to o n^2 + d n, where o is the size of a single orbit, n is the number of generators of G, and d is the size of D.

RepresentativeOperation( G, d, e, opr )

RepresentativeOperation returns a permutation perm in G that maps d to e in respect to the given operation opr if such a permutation exists, and false otherwise.

If the operation is OnPoints, OnPairs, OnTuples, or OnSets and d and e are positive integers or lists of integers, a basechange is performed and the representative is computed from the factorized inverse transversal (see Stabilizer Chains and StabChain).

If the operation is OnPoints, OnPairs, OnTuples or OnSets and d and e are permutations or lists of permutations, a backtrack search is performed (see PermGroupOps.ElementProperty).

Stabilizer( G, D, opr )

Stabilizer returns the stabilizer of D in G using the operation opr on the D. If D is a positive integer (respectively a list of positive integers) and the operation opr is OnPoints (respectively OnPairs or OnTuples) a basechange of G is performed (see MakeStabChain). If D is a set of positive integers and the operation opr is OnSets a backtrack algorithm for set-stabilizers of permutation groups is performed.

Blocks( G, D [, seed ] [, operation ] )

Returns a partition of D being a minimal block system of G in respect to the operation opreration on the objects of D. If the argument seed is given the objects of seed are contained in the same block. If D is a list of positive integers an Atkinson algorithm is performed.

Theoretically the algorithm lies in {cal{O}}(n^3 m) but in practice it is mostly in {cal{O}}(n^2 m) with m the number of generators and n the cardinality of D.

Previous Up Top Next
Index

GAP 3.4.4
April 1997