[MathJax on]

6 Orbital Structures

The functions for orbital structures are based on recent work in permutation group algorithms. An orbital structure contains information about orbits and stabilisers of a group acting on a set for the purposes of quickly determining representatives, canonising elements, and transversal elements (directed) orbitals (orbits of ordered pairs of elements of the domain), and undirected orbitals, i.e. orbits of sets of size two.

6.1 Examples

To create an orbital structure we need generators for a group, a set, and an action

gap> os := OrbitalStructure([
> (1,13,4,14,5)(2,10,12,9,8)(3,7,15,6,11)(16,17,18,20,19),
> (1,2,3)(4,6,5)(7,10,13)(8,12,14)(9,11,15)(16,18,21)(17,19,20) ],
> [1..21],
> OnPoints);;
gap> OrbitalRepresentative(os, [16,15]);
[ 16, 1 ]
gap> c := OrbitalCanonizingElement(os, [16, 15]);
(1,10,9,5,15)(2,7,6,8,4)(3,13,14,11,12)(17,20,18,19,21)
gap> OnTuples(c, [16,15]);
[ 16, 1 ]
gap> UnorderedOrbitalRepresentative(os, [16,2]);
[ 1, 16 ]
gap> c := UnorderedOrbitalCanonizingElement(os, [16,15]);
(1,15)(2,4)(3,12)(5,10)(7,8)(11,13)(17,21)(19,20)
gap> OnSets(c, Set([16,15]));
[ 1, 16 ]
gap> AllOrbitalRepresentatives(os)
[ [ 1, 1 ], [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ], [ 1, 16 ],
  [ 1, 18 ], [ 1, 20 ], [ 16, 1 ], [ 16, 2 ], [ 16, 3 ], [ 16, 16 ], [ 16, 17 ] ]
gap> AllUnorderedOrbitalRepresentatives(os)
[ [ 1, 1 ], [ 1, 2 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ], [ 1, 16 ], [ 1, 18 ],
  [ 1, 20 ], [ 16, 16 ], [ 16, 17 ] ]

6.1-1 IsOrbitalStructure

Returns: true or false

6.1-2 OrbitalStructure

Returns: An orbital structure

Given generators, a set, and an action function create an orbital structure. An orbital structure contains a list of orbits of the group generated by gens on domain, a hashmap that maps any element of domain to the index of its orbit in the list of orbits. We choose the smallest element of each orbit as representative. For each orbit, the orbital structure also contains the stabilizer of the chosen orbit representative, together with all orbits of that stabilizer on domain with chosen representatives.

6.1-3 OS_OrbitRepresentative

6.1-4 OS_CanonisingElement

6.1-5 OS_CanonisingElementAndRepresentative

6.1-6 OS_StabilizerOf

6.1-7 OrbitalRepresentative

Returns: pair

Given an orbital structure os and a pair pair of elements of the domain that os is defined on, returns a canonical representative of pair in its orbit of ordered pairs.

6.1-8 AllOrbitalRepresentatives

Return the set of canonical representatives of orbits of pairs under the action of the orbital structure.

6.1-9 OrbitalCanonizingElement

Returns: a group element

Given an orbital structure os and the pair pair returns an element g of the group that maps pair to OrbitalRepresentative(os, pair).

6.1-10 OrbitalCanonizingElementInverse

6.1-11 OrbitalTransversalIterator

Returns: an iterator

Given an orbital structure os and a pair pair, returns an iterator that produces an element g for every element e in the orbit such that OnTuples(OrbitalRepresentative(os, pair), g) = e.

6.1-12 UnorderedOrbitalRepresentative

Returns: pair

Given an orbital structure os and a pair pair of elements of the domain that os is defined on, returns a canonical representative of pair in its orbit of sets.

6.1-13 AllUnorderedOrbitalRepresentatives

Return the set of canonical representatives of orbits of sets of size two under the action of the orbital structure.

6.1-14 UnorderedOrbitalTransversalIterator

Returns: an iterator

Given an orbital structure os and a pair pair, returns an iterator that produces an element g for every element e in the orbit such that OnSets(UnorderedOrbitalRepresentative(os, pair), g) = e.

6.1-15 UnorderedOrbitalCanonizingElement

Returns: a group element

Given an orbital structure os and the pair pair returns an element g of the group that maps pair to UnorderedOrbitalRepresentative(os, pair).

6.1-16 UnorderedOrbitalCanonizingElementInverse

generated by GAPDoc2HTML