One of the most important tools in group theory is the **operation** or
**action** of a group on a certain set.

We say that a group *G* operates on a set *D* if we have a function that
takes each *d in D* and each *g in G* to another element *d^g in D*,
which we call the image of *d* under *g*, such that *d^{identity} = d*
and *(d^g)^h = d^{gh}* for each *d in D* and *g,h in G*.

This is equivalent to saying that an operation is a homomorphism of the
group *G* into the full symmetric group on *D*. We usually call *D* the
**domain** of the operation and its elements **points**.

An example of the usage of the functions in this package can be found in
the introduction to **GAP** (see About Operations of Groups).

In **GAP** group elements usually operate through the power operator,
which is denoted by the caret `^`

. It is possible however to specify
other operations (see Other Operations).

First this chapter describes the functions that take a single element of
the group and compute cycles of this group element and related
information (see Cycle, CycleLength, Cycles, and CycleLengths),
and the function that describes how a group element operates by a
permutation that operates the same way on `[1..`

(see Permutation).
`n`]

Next come the functions that test whether an orbit has minimal or maximal length and related functions (see IsFixpoint, IsFixpointFree, DegreeOperation, IsTransitive, and Transitivity).

Next this chapter describes the functions that take a group and compute orbits of this group and related information (see Orbit, OrbitLength, Orbits, and OrbitLengths).

Next are the functions that compute the permutation group `P` that
operates on `[ 1 .. Length(`

in the same way that `D`) ]`G` operates on
`D`, and the corresponding homomorphism from `G` to `P` (see Operation,
OperationHomomorphism).

Next is the functions that compute block systems, i.e., partitions of `D`
such that `G` operates on the sets of the partition (see Blocks), and
the function that tests whether `D` has such a nontrivial partitioning
under the operation of `G` (see IsPrimitive).

Finally come the functions that relate an orbit of `G` on `D` with the
subgroup of `G` that fixes the first point in the orbit (see
Stabilizer), and the cosets of this subgroup in `G` (see
RepresentativeOperation and RepresentativesOperation).

All functions described in this chapter are in `LIBNAME/"operatio.g"`

.

- Other Operations
- Cycle
- CycleLength
- Cycles
- CycleLengths
- Permutation
- IsFixpoint
- IsFixpointFree
- DegreeOperation
- IsTransitive
- Transitivity
- IsRegular
- IsSemiRegular
- Orbit
- OrbitLength
- Orbits
- OrbitLengths
- Operation
- OperationHomomorphism
- Blocks
- IsPrimitive
- Stabilizer
- RepresentativeOperation
- RepresentativesOperation
- IsEquivalentOperation

The functions in the operation package generally compute with the
operation of group elements defined by the canonical operation that is
denoted with the caret (`^`

) in **GAP**. However they also allow you to
specify other operations. Such operations are specified by functions,
which are accepted as optional argument by all the operations package
functions.

This function must accept two arguments. The first argument will be the point and the second will be the group element. The function must return the image of the point under the group element.

As an example, the function `OnPairs`

that specifies the operation on
pairs could be defined as follows

OnPairs := function ( pair, g ) return [ pair[1] ^ g, pair[2] ^ g ]; end;

The following operations are predefined.

`OnPoints`

:

specifies the canonical default operation. Passing this function is equivalent to specifying no operation. This function exists because there are places where the operation in not an option.

`OnPairs`

:

specifies the componentwise operation of group elements on pairs of points, which are represented by lists of length 2.

`OnTuples`

:

specifies the componentwise operation of group elements on tuples of points, which are represented by lists.`OnPairs`

is the special case of`OnTuples`

for tuples with two elements.

`OnSets`

:

specifies the operation of group elements on sets of points, which are represented by sorted lists of points without duplicates (see Sets).

`OnRight`

:

specifies that group elements operate by multiplication from the right.

`OnLeftInverse`

:

specifies that group elements operate by multiplication by their inverses from the left. This is an operation, unlike`OnLeftAntiOperation`

(see below).

`OnRightCosets`

:

specifies that group elements operate by multiplication from the right on sets of points, which are represented by sorted lists of points without duplicates (see Sets).

`OnLeftCosets`

:

specifies that group elements operate by multiplication from the left on sets of points, which are represented by sorted lists of points without duplicates (see Sets).

`OnLines`

:

specifies that group elements, which must be matrices, operate on lines, which are represented by vectors with first nonzero coefficient one. That is,`OnLines`

multiplies the vector by the group element and then divides the vector by the first nonzero coefficient.

Note that it is your responsibility to make sure that the elements of the
domain `D` on which you are operating are already in normal form. The
reason is that all functions will compare points using the `=`

operation.
For example, if you are operating on sets with `OnSets`

, you will get an
error message it not all elements of the domain are sets.

gap> Cycle( (1,2), [2,1], OnSets ); Error, OnSets: <tuple> must be a set

The former function `OnLeft`

which operated by mulitplication from the
left has been renamed `OnLeftAntiOperation`

, to emphasise the point that
it does not satisify the axioms of an operation, and may cause errors if
supplied where an operation is expected.

`Cycle( `

`g`, `d` )

`Cycle( `

`g`, `d`, `operation` )

`Cycle`

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

The points `e` in the cycle of `d` under the group element `g` are those
for which a power *g^i* exists such that *d^{g^i} = e*.

The first point in the list returned by `Cycle`

is the point `d` itself,
the ordering of the other points is such that each point is the image of
the previous point.

`Cycle`

accepts a function `operation` of two arguments `d` and `g` as
optional third argument, which specifies how the element `g` operates
(see Other Operations).

gap> Cycle( (1,5,3,8)(4,6,7), 3 ); [ 3, 8, 1, 5 ] gap> Cycle( (1,5,3,8)(4,6,7), [3,4], OnPairs ); [ [ 3, 4 ], [ 8, 6 ], [ 1, 7 ], [ 5, 4 ], [ 3, 6 ], [ 8, 7 ], [ 1, 4 ], [ 5, 6 ], [ 3, 7 ], [ 8, 4 ], [ 1, 6 ], [ 5, 7 ] ]

`Cycle`

calls

`Domain([`

`g`]).operations.Cycle( `g`, `d`, `operation` )

and returns the value. Note that the third argument is not optional for
the functions called this way.

The default function called this way is `GroupElementsOps.Cycle`

, which
starts with `d` and applies `g` to the last point repeatedly until `d` is
reached again. Special categories of group elements overlay this default
function with more efficient functions.

`CycleLength( `

`g`, `d` )

`CycleLength( `

`g`, `d`, `operation` )

`CycleLength`

returns the length of the orbit of the point `d`, which may
be an object of arbitrary type, under the group elements `g`. See
Cycle for the definition of cycles.

`CycleLength`

accepts a function `operation` of two arguments `d` and `g`
as optional third argument, which specifies how the group element `g`
operates (see Other Operations).

gap> CycleLength( (1,5,3,8)(4,6,7), 3 ); 4 gap> CycleLength( (1,5,3,8)(4,6,7), [3,4], OnPairs ); 12

`CycleLength`

calls

`Domain([`

`g`]).operations.CycleLength( `g`, `d`, `operation` )

and returns the value. Note that the third argument is not optional for
the functions called this way.

The default function called this way is `GroupElementsOps.CycleLength`

,
which starts with `d` and applies `g` to the last point repeatedly until
`d` is reached again. Special categories of group elements overlay this
default function with more efficient functions.

`Cycles( `

`g`, `D` )

`Cycles( `

`g`, `D`, `operation` )

`Cycles`

returns the set of cycles of the group element `g` on the domain
`D`, which must be a list of points of arbitrary type, as a set of lists
of points. See Cycle for the definition of cycles.

It is allowed that `D` is a proper subset of a domain, i.e., that `D` is
not invariant under the operation of `g`. In this case `D` is silently
replaced by the smallest superset of `D` which is invariant.

The first point in each cycle is the smallest point of `D` in this cycle.
The ordering of the other points is such that each point is the image of
the previous point. If `D` is invariant under `g`, then because `Cycles`

returns a set of cycles, i.e., a sorted list, and because cycles are
compared lexicographically, and because the first point in each cycle is
the smallest point in that cycle, the list returned by `Cycles`

is in
fact sorted with respect to the smallest point in the cycles.

`Cycles`

accepts a function `operation` of two arguments `d` and `g` as
optional third argument, which specifies how the element `g` operates
(see Other Operations).

gap> Cycles( (1,5,3,8)(4,6,7), [3,5,7] ); [ [ 3, 8, 1, 5 ], [ 7, 4, 6 ] ] gap> Cycles( (1,5,3,8)(4,6,7), [[1,3],[4,6]], OnPairs ); [ [ [ 1, 3 ], [ 5, 8 ], [ 3, 1 ], [ 8, 5 ] ], [ [ 4, 6 ], [ 6, 7 ], [ 7, 4 ] ] ]

`Cycles`

calls

`Domain([`

`g`]).operations.Cycles( `g`, `D`, `operation` )

and returns the value. Note that the third argument is not optional for
the functions called this way.

The default function called this way is `GroupElementsOps.Cycles`

, which
takes elements from `D`, computes their orbit, removes all points in the
orbit from `D`, and repeats this until `D` has been emptied. Special
categories of group elements overlay this default function with more
efficient functions.

`CycleLengths( `

`g`, `D` )

`CycleLengths( `

`g`, `D`, `operation` )

`CycleLengths`

returns a list of the lengths of the cycles of the group
element `g` on the domain `D`, which must be a list of points of
arbitrary type. See Cycle for the definition of cycles.

It is allowed that `D` is a proper subset of a domain, i.e., that `D` is
not invariant under the operation of `g`. In this case `D` is silently
replaced by the smallest superset of `D` which is invariant.

The ordering of the lengths of cycles in the list returned by
`CycleLengths`

corresponds to the list of cycles returned by `Cycles`

,
which is ordered with respect to the smallest point in each cycle.

`CycleLengths`

accepts a function `operation` of two arguments `d` and
`g` as optional third argument, which specifies how the element `g`
operates (see Other Operations).

gap> CycleLengths( (1,5,3,8)(4,6,7), [3,5,7] ); [ 4, 3 ] gap> CycleLengths( (1,5,3,8)(4,6,7), [[1,3],[4,6]], OnPairs ); [ 4, 3 ]

`CycleLengths`

calls

`Domain([`

`g`]).operations.CycleLengths( `g`, `D`, `operation` )

and returns the value. Note that the third argument is not optional for
the functions called this way.

The default function called this way is `GroupElementsOps.CycleLengths`

,
which takes elements from `D`, computes their orbit, removes all points
in the orbit from `D`, and repeats this until `D` has been emptied.
Special categories of group elements overlay this default function with
more efficient functions.

`Permutation( `

`g`, `D` )

`Permutation( `

`g`, `D`, `operation` )

`Permutation`

returns a permutation that operates on the points
`[1..Length(D)]`

in the same way that the group element `g` operates on
the domain `D`, which may be a list of arbitrary type.

It is not allowed that `D` is a proper subset of a domain, i.e., `D` must
be invariant under the element `g`.

`Permutation`

accepts a function `operation` of two arguments `d` and `g`
as optional third argument, which specifies how the element `g` operates
(see Other Operations).

gap> Permutation( (1,5,3,8)(4,6,7), [4,7,6] ); (1,3,2) gap> D := [ [1,4], [1,6], [1,7], [3,4], [3,6], [3,7], > [4,5], [5,6], [5,7], [4,8], [6,8], [7,8] ];; gap> Permutation( (1,5,3,8)(4,6,7), D, OnSets ); ( 1, 8, 6,10, 2, 9, 4,11, 3, 7, 5,12)

`Permutation`

calls

`Domain([`

`g`]).operations.Permutation( `g`, `D`, `operation` )

and returns the value. Note that the third argument is not optional for
the functions called this way.

The default function called this way is `GroupElementsOps.Permutation`

,
which simply applies `g` to all the points of `D`, finds the position of
the image in `D`, and finally applies `PermList`

(see PermList) to the
list of those positions. Actually this is not quite true. Because
finding the position of an image in a sorted list is so much faster than
finding it in `D`, `GroupElementsOps.Permutation`

first sorts a copy of
`D` and remembers how it had to rearrange the elements of `D` to achieve
this. Special categories of group elements overlay this default function
with more efficient functions.

`IsFixpoint( `

`G`, `d` )

`IsFixpoint( `

`G`, `d`, `operation` )

`IsFixpoint`

returns `true`

if the point `d` is a fixpoint under the
operation of the group `G`.

We say that `d` is a **fixpoint** under the operation of `G` if every
element `g` of `G` maps `d` to itself. This is equivalent to saying that
each generator of `G` maps `d` to itself.

As a special case it is allowed that the first argument is a single group
element, though this does not make a lot of sense, since in this case
`IsFixpoint`

simply has to test

.
`d`^`g` = `d`

`IsFixpoint`

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> IsFixpoint( g, 1 ); false gap> IsFixpoint( g, [6,7,8], OnSets ); true

`IsFixpoint`

is so simple that it does all the work by itself, and,
unlike the other functions described in this chapter, does not dispatch
to another function.

`IsFixpointFree( `

`G`, `D` )

`IsFixpointFree( `

`G`, `D`, `operation` )

`IsFixpointFree`

returns `true`

if the group `G` operates without a
fixpoint (see IsFixpoint) on the domain `D`, which must be a list of
points of arbitrary type.

We say that `G` operates **fixpoint free** on the domain `D` if each point
of `D` is moved by at least one element of `G`. This is equivalent to
saying that each point of `D` is moved by at least one generator of `G`.
This definition also applies in the case that `D` is a proper subset of a
domain, i.e., that `D` is not invariant under the operation of `G`.

As a special case it is allowed that the first argument is a single group element.

`IsFixpointFree`

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> IsFixpointFree( g, [1..8] ); true gap> sets := Combinations( [1..8], 3 );; Length( sets ); 56 # a list of all three element subsets of '[1..8]' gap> IsFixpointFree( g, sets, OnSets ); false

`IsFixpointFree`

calls

`G`.operations.IsFixpointFree( `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.IsFixpointFree`

, which
simply loops over the elements of `D` and applies to each all generators
of `G`, and tests whether each is moved by at least one generator. This
function is seldom overlaid, because it is very difficult to improve it.

`DegreeOperation( `

`G`, `D` )

`DegreeOperation( `

`G`, `D`, `operation` )

`DegreeOperation`

returns the degree of the operation of the group `G` on
the domain `D`, which must be a list of points of arbitrary type.

The **degree** of the operation of `G` on `D` is defined as the number of
points of `D` that are properly moved by at least one element of `G`.
This definition also applies in the case that `D` is a proper subset of a
domain, i.e., that `D` is not invariant under the operation of `G`.

`DegreeOperation`

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> DegreeOperation( g, [1..10] ); 8 gap> sets := Combinations( [1..8], 3 );; Length( sets ); 56 # a list of all three element subsets of '[1..8]' gap> DegreeOperation( g, sets, OnSets ); 55

`DegreeOperation`

calls

`G`.operations.DegreeOperation( `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.DegreeOperation`

, which
simply loops over the elements of `D` and applies to each all generators
of `G`, and counts those that are moved by at least one generator. This
function is seldom overlaid, because it is very difficult to improve it.

`IsTransitive( `

`G`, `D` )

`IsTransitive( `

`G`, `D`, `operation` )

`IsTransitive`

returns `true`

if the group `G` operates transitively on
the domain `D`, which must be a list of points of arbitrary type.

We say that a group `G` acts **transitively** on a domain `D` if and only
if for every pair of points `d` and `e` there is an element `g` of `G`
such that *d^g = e*. An alternative characterization of this property is
to say that `D` as a set is equal to the orbit of every single point.

It is allowed that `D` is a proper subset of a domain, i.e., that `D` is
not invariant under the operation of `G`. In this case `IsTransitive`

checks whether for every pair of points `d`, `e` of `D` there is an
element `g` of `G`, such that *d^g = e*. This can also be characterized
by saying that `D` is a subset of the orbit of every single point.

`IsTransitive`

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> IsTransitive( g, [1..8] ); false gap> IsTransitive( g, [1,6] ); false # note that the domain need not be invariant gap> sets := Combinations( [1..5], 3 );; Length( sets ); 10 # a list of all three element subsets of '[1..5]' gap> IsTransitive( g, sets, OnSets ); true

`IsTransitive`

calls

`G`.operations.IsTransitive( `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.IsTransitive`

, which
tests whether `D` is a subset of the orbit of the first point in `D`.
This function is seldom overlaid, because it is difficult to improve it.

`Transitivity( `

`G`, `D` )

`Transitivity( `

`G`, `D`, `operation` )

`Transitivity`

returns the degree of transitivity of the group `G` on the
domain `D`, which must be a list of points of arbitrary type. If `G`
does not operate transitively on `D` then `Transitivity`

returns 0.

The **degree of transitivity** of the operation of `G` on `D` is the
largest `k` such that `G` operates `k`-fold transitively on `D`. We say
that `G` operates `k`-**fold transitively** on `D` if it operates
transitively on `D` (see IsTransitive) and the stabilizer of one point
`d` of `D` operates

-fold transitively on `k`-1`Difference(`

.
Because the stabilizers of the points of `D`,[`d`])`D` are conjugate this is
equivalent to saying that the stabilizer of **each** point `d` of `D`
operates

-fold transitively on `k`-1`Difference(`

.
`D`,[`d`])

It is not allowed that `D` is a proper subset of a domain, i.e., `D` must
be invariant under the operation of `G`.

`Transitivity`

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> Transitivity( g, [1..8] ); 0 gap> Transitivity( g, [1..5] ); 3 gap> sets := Combinations( [1..5], 3 );; Length( sets ); 10 # a list of all three element subsets of '[1..5]' gap> Transitivity( g, sets, OnSets ); 1

`Transitivity`

calls

`G`.operations.Transitivity( `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.Transitivity`

, which
first tests whether `G` operates transitively on `D`. If so, it returns

`Transitivity(Stabilizer(`

; `G`,Difference(`D`,[`D`[1]]),`operation`)+1

if not, it simply returns 0. Special categories of groups overlay this
default function with more efficient functions.

`IsRegular( `

`G`, `D` )`IsRegular( `

`G`, `D`, `operation` )

`IsRegular`

returns `true`

if the group `G` operates regularly on the
domain `D`, which must be a list of points of arbitrary type, and `false`

otherwise.

A group `G` operates **regularly** on a domain `D` if it operates
transitively and no element of `G` other than the idenity leaves a point
of `D` fixed. An equal characterisation is that `G` operates
transitively on `D` and the stabilizer of any point of `D` is trivial.
Yet another characterisation is that the operation of `G` on `D` is
equivalent to the operation of `G` on its elements by multiplication from
the right.

It is not allowed that `D` is a proper subset of a domain, i.e., `D` must
be invariant under the operation of `G`.

`IsRegular`

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> IsRegular( g, [1..5] ); false gap> IsRegular( g, Elements(g), OnRight ); true gap> g := Group( (1,2,3), (3,4,5) );; gap> IsRegular( g, Orbit( g, [1,2,3], OnTuples ), OnTuples ); true

`IsRegular`

calls

`G`.operations.IsRegular( `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.IsRegular`

, which tests
if `G` operates transitively and semiregularly on `D` (see IsTransitive
and IsSemiRegular).

`IsSemiRegular( `

`G`, `D` )

`IsSemiRegular( `

`G`, `D`, `operation` )

`IsSemiRegular`

returns `true`

if the group `G` operates semiregularly on
the domain `D`, which must be a list of points of arbitrary type, and
`false`

otherwise.

A group `G` operates **semiregularly** on a domain `D` if no element of `G`
other than the idenity leaves a point of `D` fixed. An equal
characterisation is that the stabilizer of any point of `D` is trivial.
Yet another characterisation is that the operation of `G` on `D` is
equivalent to multiple copies of the operation of `G` on its elements by
multiplication from the right.

It is not allowed that `D` is a proper subset of a domain, i.e., `D` must
be invariant under the operation of `G`.

`IsSemiRegular`

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,4)(5,7)(6,8), (1,3)(2,4)(5,6)(7,8) );; gap> IsSemiRegular( g, [1..8] ); true gap> g := Group( (1,2)(3,4)(5,7)(6,8), (1,3)(2,4)(5,6,7,8) );; gap> IsSemiRegular( g, [1..8] ); false gap> IsSemiRegular( g, Orbit( g, [1,5], OnSets ), OnSets ); true

`IsSemiRegular`

calls

`G`.operations.IsSemiRegular( `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.IsSemiRegular`

, which
computes a permutation group `P` that operates on `[1..Length(`

in
the same way that `D`)]`G` operates on `D` (see Operation) and then checks
if this permutation group operations semiregularly. This of course only
works because this default function is overlaid for permutation groups
(see Operations of Permutation Groups).

`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.

`OrbitLength( `

`G`, `d` )

`OrbitLength( `

`G`, `d`, `operation` )

`OrbitLength`

returns the length of the orbit of the point `d`, which may
be an object of arbitrary type, under the group `G`. See Orbit for the
definition of orbits.

`OrbitLength`

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> OrbitLength( g, 1 ); 5 gap> OrbitLength( g, 10 ); 1 gap> OrbitLength( g, [1,6], OnPairs ); 15

`OrbitLength`

calls

`G`.operations.OrbitLength( `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.OrbitLength`

, which
performs an ordinary orbit algorithm. Special categories of groups
overlay this default function with more efficient functions.

`Orbits( `

`G`, `D` )

`Orbits( `

`G`, `D`, `operation` )

`Orbits`

returns the orbits of the group `G` on the domain `D`, which
must be a list of points of arbitrary type, as a set of lists of points.
See Orbit for the definition of orbits.

It is allowed that `D` is a proper subset of a domain, i.e., that `D` is
not invariant under the operation of `G`. In this case `D` is silently
replaced by the smallest superset of `D` which is invariant.

The first point in each orbit is the smallest point, the other points of
each orbit are ordered in the standard order defined for orbits (see
Orbit). Because `Orbits`

returns a set of orbits, i.e., a sorted list,
and because those orbits are compared lexicographically, and because the
first point in each orbit is the smallest point in that orbit, the list
returned by `Orbits`

is in fact sorted with respect to the smallest
points the orbits.

`Orbits`

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> Orbits( g, [1..8] ); [ [ 1, 2, 3, 4, 5 ], [ 6, 7, 8 ] ] gap> Orbits( g, [1,6] ); [ [ 1, 2, 3, 4, 5 ], [ 6, 7, 8 ] ] # the domain is not invariant gap> sets := Combinations( [1..8], 3 );; Length( sets ); 56 # a list of all three element subsets of '[1..8]' gap> Orbits( g, sets, OnSets ); [ [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 2, 3, 4 ], [ 1, 2, 5 ], [ 1, 3, 4 ], [ 2, 4, 5 ], [ 2, 3, 5 ], [ 1, 4, 5 ], [ 3, 4, 5 ], [ 1, 3, 5 ] ], [ [ 1, 2, 6 ], [ 2, 3, 7 ], [ 1, 3, 6 ], [ 2, 4, 8 ], [ 1, 2, 7 ], [ 1, 4, 6 ], [ 3, 4, 8 ], [ 2, 5, 7 ], [ 2, 3, 6 ], [ 1, 2, 8 ], [ 2, 4, 7 ], [ 1, 5, 6 ], [ 1, 4, 8 ], [ 4, 5, 7 ], [ 3, 5, 6 ], [ 2, 3, 8 ], [ 1, 3, 7 ], [ 2, 4, 6 ], [ 3, 4, 6 ], [ 2, 5, 8 ], [ 1, 5, 7 ], [ 4, 5, 6 ], [ 3, 5, 8 ], [ 1, 3, 8 ], [ 3, 4, 7 ], [ 2, 5, 6 ], [ 1, 4, 7 ], [ 1, 5, 8 ], [ 4, 5, 8 ], [ 3, 5, 7 ] ], [ [ 1, 6, 7 ], [ 2, 6, 7 ], [ 1, 6, 8 ], [ 3, 6, 7 ], [ 2, 6, 8 ], [ 2, 7, 8 ], [ 4, 6, 8 ], [ 3, 7, 8 ], [ 3, 6, 8 ], [ 4, 7, 8 ], [ 5, 6, 7 ], [ 1, 7, 8 ], [ 4, 6, 7 ], [ 5, 7, 8 ], [ 5, 6, 8 ] ], [ [ 6, 7, 8 ] ] ]

`Orbits`

calls

`G`.operations.Orbits( `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.Orbits`

, which takes an
element from `D`, computes its orbit, removes all points in the orbit
from `D`, and repeats this until `D` has been emptied. Special
categories of groups overlay this default function with more efficient
functions.

`OrbitLengths( `

`G`, `D` )

`OrbitLengths( `

`G`, `D`, `operation` )

`OrbitLengths`

returns a list of the lengths of the orbits of the group
`G` on the domain `D`, which may be a list of points of arbitrary type.
See Orbit for the definition of orbits.

It is allowed that `D` is proper subset of a domain, i.e., that `D` is
not invariant under the operation of `G`. In this case `D` is silently
replaced by the smallest superset of `D` which is invariant.

The ordering of the lengths of orbits in the list returned by
`OrbitLengths`

corresponds to the list of cycles returned by `Orbits`

,
which is ordered with respect to the smallest point in each orbit.

`OrbitLengths`

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> OrbitLengths( g, [1..8] ); [ 5, 3 ] gap> sets := Combinations( [1..8], 3 );; Length( sets ); 56 # a list of all three element subsets of '[1..8]' gap> OrbitLengths( g, sets, OnSets ); [ 10, 30, 15, 1 ]

`OrbitLengths`

calls

`G`.operations.OrbitLenghts( `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.OrbitLengths`

, which
takes an element from `D`, computes its orbit, removes all points in the
orbit from `D`, and repeats this until `D` has been emptied. Special
categories of groups overlay this default function with more efficient
functions.

`Operation( `

`G`, `D` )

`Operation( `

`G`, `D`, `operation` )

`Operation`

returns a permutation group with the same number of
generators as `G`, such that each generator of the permutation group
operates on the set `[1..Length(D)]`

in the same way that the
corresponding generator of the group `G` operates on the domain `D`,
which may be a list of arbitrary type.

It is not allowed that `D` is a proper subset of a domain, i.e., `D` must
be invariant under the element `g`.

`Operation`

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

The function `OperationHomomorphism`

(see OperationHomomorphism) can be
used to compute the homomorphism that maps `G` onto the new permutation
group. Of course if you are only interested in mapping single elements
of `G` into the new permutation group you may also use `Permutation`

(see
Permutation).

gap> g := Group( (1,2,3)(6,7), (3,4,5)(7,8) );; gap> Operation( g, [1..5] ); Group( (1,2,3), (3,4,5) ) gap> Operation( g, Orbit( g, [1,6], OnPairs ), OnPairs ); Group( ( 1, 2, 3, 5, 8,12)( 4, 7, 9)( 6,10)(11,14), ( 2, 4)( 3, 6,11) ( 5, 9)( 7,10,13,12,15,14) )

`Operation`

calls

`G`.operations.Operation( `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.Operation`

, which
simply applies each generator of `G` to all the points of `D`, finds the
position of the image in `D`, and finally applies `PermList`

(see
PermList) to the list of those positions. Actually this is not quite
true. Because finding the position on an image in a sorted list is so
much faster than finding it in `D`, `GroupElementsOps.Operation`

first
sorts a copy of `D` and remembers how it had to rearrange the elements of
`D` to achieve this. Special categories of groups overlay this default
function with more efficient functions.

`OperationHomomorphism( `

`G`, `P` )

Group Homomorphisms) from the group `G` to the permutation group `P`, which
must be the result of a prior call to `Operation`

(see Operation) with
`G` or a group of which `G` is a subgroup (see IsSubgroup) as first
argument.

gap> g := Group( (1,2,3)(6,7), (3,4,5)(7,8) );; gap> h := Operation( g, [1..5] ); Group( (1,2,3), (3,4,5) ) gap> p := OperationHomomorphism( g, h ); OperationHomomorphism( Group( (1,2,3)(6,7), (3,4,5)(7,8) ), Group( (1,2,3), (3,4,5) ) ) gap> (1,4,2,5,3)(6,7,8) ^ p; (1,4,2,5,3) gap> h := Operation( g, Orbit( g, [1,6], OnPairs ), OnPairs ); Group( ( 1, 2, 3, 5, 8,12)( 4, 7, 9)( 6,10)(11,14), ( 2, 4)( 3, 6,11) ( 5, 9)( 7,10,13,12,15,14) ) gap> p := OperationHomomorphism( g, h );; gap> s := SylowSubgroup( g, 2 ); Subgroup( Group( (1,2,3)(6,7), (3,4,5)(7,8) ), [ (7,8), (7,8), (2,5)(3,4), (2,3)(4,5) ] ) gap> Images( p, s ); Subgroup( Group( ( 1, 2, 3, 5, 8,12)( 4, 7, 9)( 6,10)(11,14), ( 2, 4) ( 3, 6,11)( 5, 9)( 7,10,13,12,15,14) ), [ ( 2, 4)( 5, 9)( 7,12)(10,15)(13,14), ( 2, 4)( 5, 9)( 7,12)(10,15)(13,14), ( 2,14)( 3, 6)( 4,13)( 7,15)( 8,11)(10,12), ( 2,12)( 3, 8)( 4, 7)( 6,11)(10,14)(13,15) ] ) gap> OperationHomomorphism( g, Group( (1,2,3), (3,4,5) ) ); Error, Record: element 'operation' must have an assigned value

`OperationHomomorphism`

calls

`P`.operations.OperationHomomorphism( `G`, `P` )

and returns the value.

The default function called this way is `GroupOps.OperationHomomorphism`

,
which uses the fields

, `P`.operationGroup

, and
`P`.operationDomain

(the arguments to the `P`.operationOperation`Operation`

call that
created `P`) to construct a generic homomorphism `h`. This
homomorphism uses

`Permutation(`

`g`,`h`.range.operationDomain,`h`.range.operationOperation)

to compute the image of an element `g` of `G` under `h`. It uses
`Representative`

to compute the preimages of an element `p` of `P` under
`h`. And it computes the kernel by intersecting the cores (see Core)
of the stabilizers (see Stabilizer) of representatives of the orbits of
`G`. Look under **OperationHomomorphism** in the index to see for which
groups and operations this function is overlaid.

`Blocks( `

`G`, `D`, `seed` )

`Blocks( `

`G`, `D`, `seed`, `operation` )

In this form `Blocks`

returns a block system of the domain `D`, which may
be a list of points of arbitrary type, under the group `G`, such that the
points in the list `seed` all lie in the same block. If no such
nontrivial block system exists, `Blocks`

returns `[ `

. `D` ]`G` must
operate transitively on `D`, otherwise an error is signalled.

`Blocks( `

`G`, `D` )

`Blocks( `

`G`, `D`, `operation` )

In this form `Blocks`

returns a minimal block system of the domain `D`,
which may be a list of points of arbitrary type, under the group `G`. If
no nontrivial block system exists, `Blocks`

returns `[ `

. `D` ]`G` must
operate transitively on `D`, otherwise an error is signalled.

A **block system** `B` is a list of blocks with the following properties.
Each block `b` of `B` is a subset of `D`. The blocks are pairwise
disjoint. The union of blocks is `D`. The image of each block under
each element `g` of `G` is as a set equal to some block of the block
system. Note that this implies that all blocks contain the same number
of elements as `G` operates transitive on `D`. Put differently a block
system `B` of `D` is a partition of `D` such that `G` operates with
`OnSets`

(see Other Operations) on `B`. The block system that consists
of only singleton sets and the block system consisting only of `D` are
called **trivial**. A block system `B` is called **minimal** if there is no
nontrivial block system whose blocks are all subsets of the blocks of `B`
and whose number of blocks is larger than the number of blocks of `B`.

`Blocks`

accepts a function `operation` of two arguments `d` and `g` as
optional third, resp. fourth, 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> Blocks( g, [1..5] ); [ [ 1 .. 5 ] ] gap> Blocks( g, Orbit( g, [1,2], OnPairs ), OnPairs ); [ [ [ 1, 2 ], [ 3, 2 ], [ 4, 2 ], [ 5, 2 ] ], [ [ 1, 3 ], [ 2, 3 ], [ 4, 3 ], [ 5, 3 ] ], [ [ 1, 4 ], [ 2, 4 ], [ 3, 4 ], [ 5, 4 ] ], [ [ 1, 5 ], [ 2, 5 ], [ 3, 5 ], [ 4, 5 ] ], [ [ 2, 1 ], [ 3, 1 ], [ 4, 1 ], [ 5, 1 ] ] ]

`Blocks`

calls

`G`.operations.Blocks( `G`, `D`, `seed`, `operation` )

and returns the value. If no seed was given as argument to `Blocks`

it
passes the empty list. Note that the fourth argument is not optional for
functions called this way.

The default function called this way is `GroupOps.Blocks`

, which computes
a permutation group `P` that operates on `[1..Length(`

in the same
way that `D`)]`G` operates on `D` (see Operation) and leaves it to this
permutation group to find the blocks. This of course works only because
Operations of Permutation Groups).

`IsPrimitive( `

`G`, `D` )

`IsPrimitive( `

`G`, `D`, `operation` )

`IsPrimitive`

returns `true`

if the group `G` operates primitively on the
domain `D`, which may be a list of points of arbitrary type, and `false`

otherwise.

A group `G` operates **primitively** on a domain `D` if and only if `D`
operates transitively (see IsTransitive) and has only the trivial block
systems (see Blocks).

`IsPrimitive`

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> IsPrimitive( g, [1..5] ); true gap> IsPrimitive( g, Orbit( g, [1,2], OnPairs ), OnPairs ); false

`IsPrimitive`

calls

`G`.operations.IsPrimitive( `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.IsPrimitive`

, which
simply calls `Blocks( `

and tests whether the
returned block system is `G`, `D`, `operation` )`[ `

. This function is seldom overlaid,
because all the important work is done in `D` ]`Blocks`

.

`Stabilizer( `

`G`, `d` )

`Stabilizer( `

`G`, `d`, `operation` )

`Stabilizer`

returns the stabilizer of the point `d` under the operation
of the group `G`.

The **stabilizer** *S* of *d* in *G* is the subgroup of those elements *g*
of *G* that fix *d*, i.e., for which *d^g = d*. The right cosets of *S*
correspond in a canonical way to the points *p* in the orbit *O* of *d*
under *G*; namely all elements from a right coset *S g* map *d* to the
same point *d^g in O*, and elements from different right cosets *S g*
and *S h* map *d* to different points *d^g* and *d^h*. Thus the index of
the stabilizer *S* in *G* is equal to the length of the orbit *O*.
`RepresentativesOperation`

(see RepresentativesOperation) computes a
system of representatives of the right cosets of *S* in *G*.

`Stabilizer`

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> g.name := "G";; gap> Stabilizer( g, 1 ); Subgroup( G, [ (3,4,5)(7,8), (2,5,3)(6,7) ] ) gap> Stabilizer( g, [1,2,3], OnSets ); Subgroup( G, [ (7,8), (6,8), (2,3)(4,5)(6,7,8), (1,2)(4,5)(6,7,8) ] )

`Stabilizer`

calls

`G`.operations.Stabilizer( `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.Stabilizer`

, which
computes the orbit of *d* under *G*, remembers a representative *r_e* for
each point *e* in the orbit, and uses Schreier's theorem, which says
that the stabilizer is generated by the elements *r_e g r_{e^g}^{-1}*.
Special categories of groups overlay this default function with more
efficient functions.

`RepresentativeOperation( `

`G`, `d`, `e` )

`RepresentativeOperation( `

`G`, `d`, `e`, `operation` )

`RepresentativeOperation`

returns a representative of the point `e` in
the orbit of the point `d` under the group `G`. If `d` = `e` then
`RepresentativeOperation`

returns

, otherwise it is not
specified which group element `G`.identity`RepresentativeOperation`

will return if
there are several that map `d` to `e`. If `e` is not in the orbit of `d`
under `G`, `RepresentativeOperation`

returns `false`

.

An element *g* of *G* is called a **representative** for the point *e* in
the orbit of *d* under *G* if *g* maps *d* to *e*, i.e., *d^g = e*. Note
that the set of such representatives that map *d* to *e* forms a right
coset of the stabilizer of *d* in *G* (see Stabilizer).

`RepresentativeOperation`

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> RepresentativeOperation( g, 1, 5 ); (1,5,4,3,2)(6,8,7) gap> RepresentativeOperation( g, 1, 6 ); false gap> RepresentativeOperation( g, [1,2,3], [3,4,5], OnSets ); (1,3,5,2,4) gap> RepresentativeOperation( g, [1,2,3,4], [3,4,5,2], OnTuples ); false

`RepresentativeOperation`

calls

`G`.operations.RepresentativeOperation( `G`, `d`, `e`, `operation` )

and returns the value. Note that the fourth argument is not optional for
functions called this way.

The default function called this way is
`GroupOper.RepresentativeOperation`

, which starts a normal orbit
calculation to compute the orbit of `d` under `G`, and remembers for each
point how it was obtained, i.e., which generator of `G` took which orbit
point to this new point. When the point `e` appears this information can
be traced back to write down the representative of `e` as a word in the
generators. Special categories of groups overlay this default function
with more efficient functions.

`RepresentativesOperation( `

`G`, `d` )

`RepresentativesOperation( `

`G`, `d`, `operation` )

`RepresentativesOperation`

returns a list of representatives of the
points in the orbit of the point `d` under the group `G`.

The ordering of the representatives corresponds to the ordering of the
points in the orbit as returned by `Orbit`

(see Orbit). Therefore
`List( RepresentativesOperation(`

.
`G`,`d`), r-`d`^r ) = Orbit(`G`,`d`)

An element *g* of *G* is called a **representative** for the point *e* in
the orbit of *d* under *G* if *g* maps *d* to *e*, i.e., *d^g = e*. Note
that the set of such representatives that map *d* to *e* forms a right
coset of the stabilizer of *d* in *G* (see Stabilizer). The set of all
representatives of the orbit of *d* under *G* thus forms a system of
representatives of the right cosets of the stabilizer of *d* in *G*.

`RepresentativesOperation`

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> RepresentativesOperation( g, 1 ); [ (), (1,2,3)(6,7), (1,3,2), (1,4,5,3,2)(7,8), (1,5,4,3,2) ] gap> Orbit( g, [1,2], OnSets ); [ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ], [ 2, 4 ], [ 1, 4 ], [ 3, 4 ], [ 2, 5 ], [ 1, 5 ], [ 4, 5 ], [ 3, 5 ] ] gap> RepresentativesOperation( g, [1,2], OnSets ); [ (), (1,2,3)(6,7), (1,3,2), (1,2,4,5,3)(6,8,7), (1,4,5,3,2)(7,8), (1,3,2,4,5)(6,8), (1,2,5,4,3)(6,7), (1,5,4,3,2), (1,4,3,2,5)(6,7,8), (1,3,2,5,4) ]

`RepresentativesOperation`

calls

`G`.operations.RepresentativesOperation( `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.RepresentativesOperation`

, which computes the orbit of `d` with
the normal algorithm, but remembers for each point *e* in the orbit a
representative *r_e*. When a generator *g* of *G* takes an old point *e*
to a point *f* not yet in the orbit, the representative *r_f* for *f* is
computed as *r_e g*. Special categories of groups overlay this default
function with more efficient functions.

`IsEquivalentOperation( `

`G`, `D`, `H`, `E` )

`IsEquivalentOperation( `

`G`, `D`, `H`, `E`, `operationH` )

`IsEquivalentOperation( `

`G`, `D`, `operationG`, `H`, `E` )

`IsEquivalentOperation( `

`G`, `D`, `operationG`, `H`, `E`, `operationH` )

`IsEquivalentOperation`

returns `true`

if `G` operates on `D` in like `H`
operates on `E`, and `false`

otherwise.

The operations of *G* on *D* and *H* on *E* are equivalent if they have
the same number of generators and there is a permutation *F* of the
elements of *E* such that for every generator *g* of *G* and the
corresponding generator *h* of *H* we have *Position( D, D_i^g ) =
Position( F, F_i^h )*. Note that this assumes that the mapping defined
by mapping *G.generators* to *H.generators* is a homomorphism (actually
an isomorphism of factor groups of *G* and *H* represented by the
respective operation).

`IsEquivalentOperation`

accepts functions `operationG` and `operationH`
of two arguments `d` and `g` as optional third and sixth arguments, which
Other Operations).

gap> g := Group( (1,2)(4,5), (1,2,3)(4,5,6) );; gap> h := Group( (2,3)(4,5), (1,2,3)(4,5,6) );; gap> IsEquivalentOperation( g, [1..6], h, [1..6] ); true gap> h := Group( (1,2), (1,2,3) );; gap> IsEquivalentOperation(g,[[1,4],[2,5],[3,6]],OnPairs,h,[1..3]); true gap> h := Group( (1,2), (1,2,3)(4,5,6) );; gap> IsEquivalentOperation( g, [1..6], h, [1..6] ); false gap> h := Group( (1,2,3)(4,5,6), (1,2)(4,5) );; gap> IsEquivalentOperation( g, [1..6], h, [1..6] ); false # the generators must correspond

`IsEquivalentOperation`

calls

and
returns the value. Note that the third and sixth argument are not
optional for functions called this way.
`G`.operations.IsEquivalentOperation(`G`,`D`,`oprG`,`H`,`E`,`oprH`)

The default function called this way is `GroupOps.IsEquivalentOperation`

,
which tries to rearrange `E` so that the above condition is satisfied.
This is done one orbit of `G` at a time, and for each such orbit all the
orbits of `H` of the same length are tried to see if there is one which
can be rearranged as necessary. Special categories of groups overlay
this function with more efficient ones.

GAP 3.4.4

April 1997