8.14 Orbit

Orbit( G, d )
Orbit( G, d, operation )

Orbit returns the orbit of the point d, which may be an object of arbitrary type, under the group G as a list of points.

The points e in the orbit of d under the group G are those points for which a group element g of G exists such that d^g = e.

Suppose G has n generators. First we order the words of the free monoid with n abstract generators according to length and for words with equal length lexicographically. So if G has two generators called a and b the ordering is identity, a, b, a^2, ab, ba, b^2, a^3, .... Next we order the elements of G that can be written as a product of the generators, i.e., without inverses of the generators, according to the first occurrence of a word representing the element in the above ordering. Then the ordering of points in the orbit returned by Orbit is according to the order of the first representative of each point e, i.e., the smallest g such that d^g = e. Note that because the orbit is finite there is for every point in the orbit at least one representative that can be written as a product in the generators of G.

Orbit accepts a function operation of two arguments d and g as optional third argument, which specifies how the elements of G operate (see Other Operations).

    gap> g := Group( (1,2,3)(6,7), (3,4,5)(7,8) );;
    gap> Orbit( g, 1 );
    [ 1, 2, 3, 4, 5 ]
    gap> Orbit( g, 2 );
    [ 2, 3, 1, 4, 5 ]
    gap> Orbit( g, [1,6], OnPairs );
    [ [ 1, 6 ], [ 2, 7 ], [ 3, 6 ], [ 2, 8 ], [ 1, 7 ], [ 4, 6 ],
      [ 3, 8 ], [ 2, 6 ], [ 1, 8 ], [ 4, 7 ], [ 5, 6 ], [ 3, 7 ],
      [ 5, 8 ], [ 5, 7 ], [ 4, 8 ] ] 

Orbit calls
G.operations.Orbit( G, d, operation )
and returns the value. Note that the third argument is not optional for functions called this way.

The default function called this way is GroupOps.Orbit, which performs an ordinary orbit algorithm. Special categories of groups overlay this default function with more efficient functions.

Previous Up Top Next
Index

GAP 3.4.4
April 1997