Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind
[Top of Book] [Contents] [Previous Chapter] [Next Chapter]

[MathJax on]

41 Group Actions
41.1 About Group Actions
41.2 Basic Actions
41.2-1 OnPoints
41.2-2 OnRight
41.2-3 OnLeftInverse
41.2-4 OnSets
41.2-5 OnTuples
41.2-6 OnPairs
41.2-7 OnSetsSets
41.2-8 OnSetsDisjointSets
41.2-9 OnSetsTuples
41.2-10 OnTuplesSets
41.2-11 OnTuplesTuples
41.2-12 OnLines
41.2-13 OnIndeterminates
41.2-14 Permuted
41.2-15 OnSubspacesByCanonicalBasis
41.3 Action on canonical representatives
41.4 Orbits
41.4-1 Orbit
41.4-2 Orbits
41.4-3 OrbitsDomain
41.4-4 OrbitLength
41.4-5 OrbitLengths
41.4-6 OrbitLengthsDomain
41.5 Stabilizers
41.5-1 OrbitStabilizer
41.5-2 Stabilizer
41.5-3 OrbitStabilizerAlgorithm
41.6 Elements with Prescribed Images
41.6-1 RepresentativeAction
41.7 The Permutation Image of an Action
41.7-1 ActionHomomorphism
41.7-2 Action
41.7-3 SparseActionHomomorphism
41.8 Action of a group on itself
41.8-1 FactorCosetAction
41.8-2 RegularActionHomomorphism
41.8-3 AbelianSubfactorAction
41.9 Permutations Induced by Elements and Cycles
41.9-1 Permutation
41.9-2 PermutationCycle
41.9-3 Cycle
41.9-4 CycleLength
41.9-5 Cycles
41.9-6 CycleLengths
41.9-7 CycleIndex
41.10 Tests for Actions
41.10-1 IsTransitive
41.10-2 Transitivity
41.10-3 RankAction
41.10-4 IsSemiRegular
41.10-5 IsRegular
41.10-6 Earns
41.10-7 IsPrimitive
41.11 Block Systems
41.11-1 Blocks
41.11-2 MaximalBlocks
41.11-3 RepresentativesMinimalBlocks
41.11-4 AllBlocks
41.12 External Sets
41.12-1 IsExternalSet
41.12-2 ExternalSet
41.12-3 ActingDomain
41.12-4 FunctionAction
41.12-5 HomeEnumerator
41.12-6 IsExternalSubset
41.12-7 ExternalSubset
41.12-8 IsExternalOrbit
41.12-9 ExternalOrbit
41.12-10 StabilizerOfExternalSet
41.12-11 ExternalOrbits
41.12-12 ExternalOrbitsStabilizers
41.12-13 CanonicalRepresentativeOfExternalSet
41.12-14 CanonicalRepresentativeDeterminatorOfExternalSet
41.12-15 ActorOfExternalSet
41.12-16 UnderlyingExternalSet
41.12-17 SurjectiveActionHomomorphismAttr

### 41 Group Actions

A group action is a triple (G, Ω, μ), where G is a group, Ω a set and μ : Ω × G → Ω a function that is compatible with the group arithmetic. We call Ω the domain of the action.

In GAP, Ω can be a duplicate-free collection (an object that permits access to its elements via the Ω[n] operation, for example a list), it does not need to be sorted (see `IsSet` (21.17-4)).

The acting function μ is a binary GAP function that returns the image μ( x, g ) for a point x ∈ Ω and a group element g ∈ G.

In GAP, groups always act from the right, that is μ( μ( x, g ), h ) = μ( x, gh ).

GAP does not test whether the acting function μ satisfies the conditions for a group operation but silently assumes that is does. (If it does not, results are unpredictable.)

The first section of this chapter, 41.1, describes the various ways how operations for group actions can be called.

Functions for several commonly used action are already built into GAP. These are listed in section 41.2.

The sections 41.7 and 41.8 describe homomorphisms and mappings associated to group actions as well as the permutation group image of an action.

The other sections then describe operations to compute orbits, stabilizers, as well as properties of actions.

Finally section 41.12 describes the concept of external sets which represent the concept of a G-set and underly the actions mechanism.

#### 41.1 About Group Actions

The syntax which is used by the operations for group actions is quite flexible. For example we can call the operation `OrbitsDomain` (41.4-3) for the orbits of the group G on the domain Omega in the following ways:

`OrbitsDomain`( G, Ω[, μ] )

  The acting function μ is optional. If it is not given, the built-in action `OnPoints` (41.2-1) (which defines an action via the caret operator `^`) is used as a default.

`OrbitsDomain`( G, Ω, gens, acts[, μ] )

  This second version of `OrbitsDomain` (41.4-3) permits one to implement an action induced by a homomorphism: If the group H acts on Ω via μ and φ : G → H is a homomorphism, G acts on Ω via the induced action μ'( x, g ) = μ( x, g^φ ).

  Here gens must be a set of generators of G and acts the images of gens under φ. μ is the acting function for H. Again, the function μ is optional and `OnPoints` (41.2-1) is used as a default.

  The advantage of this notation is that GAP does not need to construct this homomorphism φ and the range group H as GAP objects. (If a small group G acts via complicated objects acts this otherwise could lead to performance problems.)

  GAP does not test whether the mapping gens ↦ acts actually induces a homomorphism and the results are unpredictable if this is not the case.

`OrbitsDomain`( xset )

  A third variant is to call the operation with an external set, which then provides G, Ω and μ. You will find more about external sets in Section 41.12.

For operations like `Stabilizer` (41.5-2) of course the domain must be replaced by an element of the domain of the action.

#### 41.2 Basic Actions

GAP already provides acting functions for the more common actions of a group. For built-in operations such as `Stabilizer` (41.5-2) special methods are available for many of these actions.

If one needs an action for which no acting function is provided by the library it can be implemented via a GAP function that conforms to the syntax

`actfun( omega, g )`

where `omega` is an element of the action domain, `g` is an element of the acting group, and the return value is the image of `omega` under `g`.

For example one could define the following function that acts on pairs of polynomials via `OnIndeterminates` (41.2-13):

    OnIndeterminatesPairs:= function( polypair, g )
      return [ OnIndeterminates( polypair[1], g ),
               OnIndeterminates( polypair[2], g ) ];
    end;

Note that this function must implement a group action from the right. This is not verified by GAP and results are unpredictable otherwise.

##### 41.2-1 OnPoints

`‣ OnPoints`( pnt, g ) | ( function )

returns `pnt ^ g`. This is for example the action of a permutation group on points, or the action of a group on its elements via conjugation, that is, if both pnt and g are elements from a common group then `pnt ^ g` is equal to g^{-1}`*`pnt`*`g. The action of a matrix group on vectors from the right is described by both `OnPoints` and `OnRight` (41.2-2).

    gap> OnPoints( 1, (1,2,3) );
    2
    gap> OnPoints( (1,2), (1,2,3) );
    (2,3)
    gap> g:= Group( (1,2,3), (2,3,4) );;
    gap> Orbit( g, 1, OnPoints );
    [ 1, 2, 3, 4 ]

##### 41.2-2 OnRight

`‣ OnRight`( pnt, g ) | ( function )

returns `pnt * g`. This is for example the action of a group on its elements via right multiplication, or the action of a group on the cosets of a subgroup. The action of a matrix group on vectors from the right is described by both `OnPoints` (41.2-1) and `OnRight`.

    gap> OnRight( [ 1, 2 ], [ [ 1, 2 ], [ 3, 4 ] ] );
    [ 7, 10 ]
    gap> OnRight( (1,2,3), (2,3,4) );
    (1,3)(2,4)
    gap> g:= Group( (1,2,3), (2,3,4) );;
    gap> Orbit( g, (), OnRight );
    [ (), (1,2,3), (2,3,4), (1,3,2), (1,3)(2,4), (1,2)(3,4), (2,4,3),
      (1,4,2), (1,4,3), (1,3,4), (1,2,4), (1,4)(2,3) ]

##### 41.2-3 OnLeftInverse

`‣ OnLeftInverse`( pnt, g ) | ( function )

returns g^{-1} `* pnt`. Forming the inverse is necessary to make this a proper action, as in GAP groups always act from the right.

`OnLeftInverse` is used for example in the representation of a right coset as an external set (see 41.12), that is, a right coset Ug is an external set for the group U acting on it via `OnLeftInverse`.)

    gap> OnLeftInverse( [ 1, 2 ], [ [ 1, 2 ], [ 3, 4 ] ] );
    [ 0, 1/2 ]
    gap> OnLeftInverse( (1,2,3), (2,3,4) );
    (1,2,4)
    gap> g:= Group( (1,2,3), (2,3,4) );;
    gap> Orbit( g, (), OnLeftInverse );
    [ (), (1,3,2), (2,4,3), (1,2,3), (1,3)(2,4), (1,2)(3,4), (2,3,4),
      (1,2,4), (1,3,4), (1,4,3), (1,4,2), (1,4)(2,3) ]

##### 41.2-4 OnSets

`‣ OnSets`( set, g ) | ( function )

Let set be a proper set (see 21.19). `OnSets` returns the proper set formed by the images of all points x of set via the action function `OnPoints` (41.2-1), applied to x and g.

`OnSets` is for example used to compute the action of a permutation group on blocks.

(`OnTuples` (41.2-5) is an action on lists that preserves the ordering of entries.)

    gap> OnSets( [ 1, 3 ], (1,2,3) );
    [ 1, 2 ]
    gap> OnSets( [ (2,3), (1,2) ], (1,2,3) );
    [ (2,3), (1,3) ]
    gap> g:= Group( (1,2,3), (2,3,4) );;
    gap> Orbit( g, [ 1, 2 ], OnSets );
    [ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ], [ 3, 4 ], [ 1, 4 ], [ 2, 4 ] ]

##### 41.2-5 OnTuples

`‣ OnTuples`( tup, g ) | ( function )

Let tup be a list. `OnTuples` returns the list formed by the images of all points x of tup via the action function `OnPoints` (41.2-1), applied to x and g.

(`OnSets` (41.2-4) is an action on lists that additionally sorts the entries of the result.)

    gap> OnTuples( [ 1, 3 ], (1,2,3) );
    [ 2, 1 ]
    gap> OnTuples( [ (2,3), (1,2) ], (1,2,3) );
    [ (1,3), (2,3) ]
    gap> g:= Group( (1,2,3), (2,3,4) );;
    gap> Orbit( g, [ 1, 2 ], OnTuples );
    [ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ], [ 3, 1 ], [ 3, 4 ], [ 2, 1 ],
      [ 1, 4 ], [ 4, 1 ], [ 4, 2 ], [ 3, 2 ], [ 2, 4 ], [ 4, 3 ] ]

##### 41.2-6 OnPairs

`‣ OnPairs`( tup, g ) | ( function )

is a special case of `OnTuples` (41.2-5) for lists tup of length 2.

##### 41.2-7 OnSetsSets

`‣ OnSetsSets`( set, g ) | ( function )

implements the action on sets of sets. set must be a proper set whose entries are again proper sets (see 21.19).

`OnSetsSets` returns the proper set whose elements are the images obtained by applying the action function `OnSets` (41.2-4) to x and g, for each element x of set.

For the special case that the elements of set are pairwise disjoint, it is possible to use `OnSetsDisjointSets` (41.2-8).

    gap> OnSetsSets( [ [ 1, 2 ], [ 3, 4 ] ], (1,2,3) );
    [ [ 1, 4 ], [ 2, 3 ] ]
    gap> g:= Group( (1,2,3), (2,3,4) );;
    gap> Orbit( g, [ [ 1, 2 ], [ 3, 4 ] ], OnSetsSets );
    [ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 4 ], [ 2, 3 ] ],
      [ [ 1, 3 ], [ 2, 4 ] ] ]

##### 41.2-8 OnSetsDisjointSets

`‣ OnSetsDisjointSets`( set, g ) | ( function )

implements the action on sets of pairwise disjoint sets (see also `OnSetsSets` (41.2-7)). set must be a proper set whose entries are pairwise disjoint proper sets. However, it is not checked that the entries of set are indeed pairwise disjoint.

`OnSetsDisjointSets` returns the proper set whose elements are the images obtained by applying the action function `OnSets` (41.2-4) to x and g, for each element x of set.

##### 41.2-9 OnSetsTuples

`‣ OnSetsTuples`( set, g ) | ( function )

implements the action on sets of tuples. set must be a proper set of lists without holes (see 21.19).

`OnSetsTuples` returns the proper set whose elements are the images obtained by applying the action function `OnTuples` (41.2-5) to x and g, for each element x of set.

    gap> OnSetsTuples( [ [ 1, 2 ], [ 3, 4 ] ], (1,2,3) );
    [ [ 1, 4 ], [ 2, 3 ] ]
    gap> g:= Group( (1,2,3), (2,3,4) );;
    gap> Orbit( g, [ [ 1, 2 ], [ 3, 4 ] ], OnSetsTuples );
    [ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 4 ], [ 2, 3 ] ],
      [ [ 1, 3 ], [ 4, 2 ] ], [ [ 2, 4 ], [ 3, 1 ] ],
      [ [ 2, 1 ], [ 4, 3 ] ], [ [ 3, 2 ], [ 4, 1 ] ] ]

##### 41.2-10 OnTuplesSets

`‣ OnTuplesSets`( tup, g ) | ( function )

implements the action on tuples of sets. tup must be a list without holes whose entries are proper sets (see 21.19).

`OnTuplesSets` returns the list of the corresponding images obtained by applying the action function `OnSets` (41.2-4) to x and g, for each entry x of tup.

    gap> OnTuplesSets( [ [ 2, 3 ], [ 3, 4 ] ], (1,2,3) );
    [ [ 1, 3 ], [ 1, 4 ] ]
    gap> g:= Group( (1,2,3), (2,3,4) );;
    gap> Orbit( g, [ [ 1, 2 ], [ 3, 4 ] ], OnTuplesSets );
    [ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 2, 3 ], [ 1, 4 ] ],
      [ [ 1, 3 ], [ 2, 4 ] ], [ [ 3, 4 ], [ 1, 2 ] ],
      [ [ 1, 4 ], [ 2, 3 ] ], [ [ 2, 4 ], [ 1, 3 ] ] ]

##### 41.2-11 OnTuplesTuples

`‣ OnTuplesTuples`( tup, g ) | ( function )

implements the action on tuples of tuples. tup must be a list without holes whose entries are again lists without holes.

`OnTuplesTuples` returns the list of the corresponding images obtained by applying the action function `OnTuples` (41.2-5) to x and g, for each entry x of the list tup.

    gap> OnTuplesTuples( [ [ 2, 3 ], [ 3, 4 ] ], (1,2,3) );
    [ [ 3, 1 ], [ 1, 4 ] ]
    gap> g:=Group((1,2,3),(2,3,4));;
    gap> Orbit(g,[[1,2],[3,4]],OnTuplesTuples);
    [ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 2, 3 ], [ 1, 4 ] ],
      [ [ 1, 3 ], [ 4, 2 ] ], [ [ 3, 1 ], [ 2, 4 ] ],
      [ [ 3, 4 ], [ 1, 2 ] ], [ [ 2, 1 ], [ 4, 3 ] ],
      [ [ 1, 4 ], [ 2, 3 ] ], [ [ 4, 1 ], [ 3, 2 ] ],
      [ [ 4, 2 ], [ 1, 3 ] ], [ [ 3, 2 ], [ 4, 1 ] ],
      [ [ 2, 4 ], [ 3, 1 ] ], [ [ 4, 3 ], [ 2, 1 ] ] ]

##### 41.2-12 OnLines

`‣ OnLines`( vec, g ) | ( function )

Let vec be a normed row vector, that is, its first nonzero entry is normed to the identity of the relevant field, see `NormedRowVector` (23.2-1). The function `OnLines` returns the row vector obtained from first multiplying vec from the right with g (via `OnRight` (41.2-2)) and then normalizing the resulting row vector by scalar multiplication from the left.

This action corresponds to the projective action of a matrix group on one-dimensional subspaces.

If vec is a zero vector or is not normed then an error is triggered (see 41.3).

    gap> OnLines( [ 1, 2 ], [ [ 1, 2 ], [ 3, 4 ] ] );
    [ 1, 10/7 ]
    gap> gl:=GL(2,5);;v:=[1,0]*Z(5)^0;
    [ Z(5)^0, 0*Z(5) ]
    gap> h:=Action(gl,Orbit(gl,v,OnLines),OnLines);
    Group([ (2,3,5,6), (1,2,4)(3,6,5) ])

##### 41.2-13 OnIndeterminates

`‣ OnIndeterminates`( poly, perm ) | ( function )

A permutation perm acts on the multivariate polynomial poly by permuting the indeterminates as it permutes points.

    gap> x:=Indeterminate(Rationals,1);; y:=Indeterminate(Rationals,2);;
    gap> OnIndeterminates(x^7*y+x*y^4,(1,17)(2,28));
    x_17^7*x_28+x_17*x_28^4
    gap> Stabilizer(Group((1,2,3,4),(1,2)),x*y,OnIndeterminates);
    Group([ (1,2), (3,4) ])

##### 41.2-14 Permuted

`‣ Permuted`( list, perm ) | ( method )

The following example demonstrates `Permuted` (21.20-17) being used to implement a permutation action on a domain:

    gap> g:=Group((1,2,3),(1,2));;
    gap> dom:=[ "a", "b", "c" ];;
    gap> Orbit(g,dom,Permuted);
    [ [ "a", "b", "c" ], [ "c", "a", "b" ], [ "b", "a", "c" ],
      [ "b", "c", "a" ], [ "a", "c", "b" ], [ "c", "b", "a" ] ]

##### 41.2-15 OnSubspacesByCanonicalBasis

`‣ OnSubspacesByCanonicalBasis`( bas, mat ) | ( function )

`‣ OnSubspacesByCanonicalBasisConcatenations`( basvec, mat ) | ( function )

implements the operation of a matrix group on subspaces of a vector space. bas must be a list of (linearly independent) vectors which forms a basis of the subspace in Hermite normal form. mat is an element of the acting matrix group. The function returns a mutable matrix which gives the basis of the image of the subspace in Hermite normal form. (In other words: it triangulizes the product of bas with mat.)

bas must be given in Hermite normal form, otherwise an error is triggered (see 41.3).

#### 41.3 Action on canonical representatives

A variety of action functions assumes that the objects on which it acts are given in a particular form, for example canonical representatives. Affected actions are for example `OnSetsSets` (41.2-7), `OnSetsDisjointSets` (41.2-8), `OnSetsTuples` (41.2-9), `OnTuplesSets` (41.2-10), `OnLines` (41.2-12) and `OnSubspacesByCanonicalBasis` (41.2-15).

If orbit seeds or domain elements are not given in the required form GAP will issue an error message:

    gap> Orbit(SymmetricGroup(5),[[2,4],[1,3]],OnSetsSets);
    Error, Action not well-defined. See the manual section
    ``Action on canonical representatives''.

In this case the affected domain elements have to be brought in canonical form, as documented for the respective action function. For interactive use this is most easily done by acting with the identity element of the group.

(A similar error could arise if a user-defined action function is used which actually does not implement an action from the right.)

#### 41.4 Orbits

If a group G acts on a set Ω, the set of all images of x ∈ Ω under elements of G is called the orbit of x. The set of orbits of G is a partition of Ω.

##### 41.4-1 Orbit

`‣ Orbit`( G[, Omega], pnt[, gens, acts][, act] ) | ( operation )

The orbit of the point pnt is the list of all images of pnt under the action of the group G w.r.t. the action function act or `OnPoints` (41.2-1) if no action function is given.

(Note that the arrangement of points in this list is not defined by the operation.)

The orbit of pnt will always contain one element that is equal to pnt, however for performance reasons this element is not necessarily identical to pnt, in particular if pnt is mutable.

    gap> g:=Group((1,3,2),(2,4,3));;
    gap> Orbit(g,1);
    [ 1, 3, 2, 4 ]
    gap> Orbit(g,[1,2],OnSets);
    [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 3, 4 ], [ 2, 4 ] ]

(See Section 41.2 for information about specific actions.)

##### 41.4-2 Orbits

`‣ Orbits`( G, seeds[, gens, acts][, act] ) | ( operation )

`‣ Orbits`( G ) | ( attribute )

`‣ Orbits`( xset ) | ( attribute )

returns a duplicate-free list of the orbits of the elements in seeds under the action act of G or under `OnPoints` (41.2-1) if no action function is given.

For a permutation group G, one may also invoke this as `Orbits(G)`, which returns all the orbits of its natural action on the set of points moved by it. For example the group ⟨ (1,2,3), (4,5) ⟩ has the orbits {1,2,3} and {4,5}.

(Note that the arrangement of orbits or of points within one orbit is not defined by the operation.)

##### 41.4-3 OrbitsDomain

`‣ OrbitsDomain`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ OrbitsDomain`( G ) | ( attribute )

`‣ OrbitsDomain`( xset ) | ( attribute )

returns a list of the orbits of G on the domain Omega (given as lists) under the action act or under `OnPoints` (41.2-1) if no action function is given.

This operation is often faster than `Orbits` (41.4-2). The domain Omega must be closed under the action of G, otherwise an error can occur.

For a permutation group G, one may also invoke this as `OrbitsDomain(G)`, which returns all the orbits of its natural action on the set of points moved by it.

(Note that the arrangement of orbits or of points within one orbit is not defined by the operation.)

    gap> g:=Group((1,3,2),(2,4,3));;
    gap> Orbits(g,[1..5]);
    [ [ 1, 3, 2, 4 ], [ 5 ] ]
    gap> OrbitsDomain(g,Arrangements([1..4],3),OnTuples);
    [ [ [ 1, 2, 3 ], [ 3, 1, 2 ], [ 1, 4, 2 ], [ 2, 3, 1 ], [ 2, 1, 4 ],
          [ 3, 4, 1 ], [ 1, 3, 4 ], [ 4, 2, 1 ], [ 4, 1, 3 ],
          [ 2, 4, 3 ], [ 3, 2, 4 ], [ 4, 3, 2 ] ],
      [ [ 1, 2, 4 ], [ 3, 1, 4 ], [ 1, 4, 3 ], [ 2, 3, 4 ], [ 2, 1, 3 ],
          [ 3, 4, 2 ], [ 1, 3, 2 ], [ 4, 2, 3 ], [ 4, 1, 2 ],
          [ 2, 4, 1 ], [ 3, 2, 1 ], [ 4, 3, 1 ] ] ]
    gap> OrbitsDomain(g,GF(2)^2,[(1,2,3),(1,4)(2,3)],
    > [[[Z(2)^0,Z(2)^0],[Z(2)^0,0*Z(2)]],[[Z(2)^0,0*Z(2)],[0*Z(2),Z(2)^0]]]);
    [ [ <an immutable GF2 vector of length 2> ],
      [ <an immutable GF2 vector of length 2>,
          <an immutable GF2 vector of length 2>,
          <an immutable GF2 vector of length 2> ] ]

(See Section 41.2 for information about specific actions.)

##### 41.4-4 OrbitLength

`‣ OrbitLength`( G[, Omega], pnt[, gens, acts][, act] ) | ( operation )

computes the length of the orbit of pnt under the action function act or `OnPoints` (41.2-1) if no action function is given.

##### 41.4-5 OrbitLengths

`‣ OrbitLengths`( G, seeds[, gens, acts][, act] ) | ( operation )

`‣ OrbitLengths`( G ) | ( attribute )

`‣ OrbitLengths`( xset ) | ( attribute )

computes the lengths of all the orbits of the elements in seeds under the action act of G.

For a permutation group G, one may also invoke this as `OrbitLengths(G)`, which returns the lengths of all the orbits of its natural action on the set of points moved by it. For example the group ⟨ (1,2,3), (5,6) ⟩ has the orbit lengths 2 and 3.

##### 41.4-6 OrbitLengthsDomain

`‣ OrbitLengthsDomain`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ OrbitLengthsDomain`( G ) | ( attribute )

`‣ OrbitLengthsDomain`( xset ) | ( attribute )

computes the lengths of all the orbits of G on Omega.

This operation is often faster than `OrbitLengths` (41.4-5). The domain Omega must be closed under the action of G, otherwise an error can occur.

For a permutation group G, one may also invoke this as `OrbitLengthsDomain(G)`, which returns the length of all the orbits of its natural action on the set of points moved by it.

    gap> g:=Group((1,3,2),(2,4,3));;
    gap> OrbitLength(g,[1,2,3,4],OnTuples);
    12
    gap> OrbitLengths(g,Arrangements([1..4],4),OnTuples);
    [ 12, 12 ]
    gap> g:=Group((1,2,3),(5,6,7));;
    gap> OrbitLengthsDomain(g,[1,2,3]);
    [ 3 ]
    gap> OrbitLengthsDomain(g);
    [ 3, 3 ]

#### 41.5 Stabilizers

The stabilizer of a point x under the action of a group G is the set of all those elements in G which fix x.

##### 41.5-1 OrbitStabilizer

`‣ OrbitStabilizer`( G[, Omega], pnt[, gens, acts][, act] ) | ( operation )

computes the orbit and the stabilizer of pnt simultaneously in a single orbit-stabilizer algorithm. Returns an immutable record with components `orbit` (the orbit as a list) and `stabilizer` (the point stabilizer, a subgroup of G).

The stabilizer will have G as its parent.

    gap> g:=Group((1,3,2),(2,4,3));;
    gap> orbstab:=OrbitStabilizer(g,[1,2],OnSets);
    rec(
      orbit := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 3, 4 ],
          [ 2, 4 ] ], stabilizer := Group([ (1,2)(3,4) ]) )
    gap> orbstab.orbit;
    [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 3, 4 ], [ 2, 4 ] ]
    gap> orbstab.stabilizer;
    Group([ (1,2)(3,4) ])

##### 41.5-2 Stabilizer

`‣ Stabilizer`( G[, Omega], pnt[, gens, acts][, act] ) | ( function )

computes the stabilizer in G of the point pnt, that is the subgroup of those elements of G that fix pnt. The stabilizer will have G as its parent.

    gap> g:=Group((1,3,2),(2,4,3));;
    gap> stab:=Stabilizer(g,4);
    Group([ (1,3,2) ])
    gap> Parent(stab);
    Group([ (1,3,2), (2,4,3) ])

The stabilizer of a set or tuple of points can be computed by specifying an action of sets or tuples of points.

    gap> Stabilizer(g,[1,2],OnSets);
    Group([ (1,2)(3,4) ])
    gap> Stabilizer(g,[1,2],OnTuples);
    Group(())
    gap> orbstab:=OrbitStabilizer(g,[1,2],OnSets);
    rec(
      orbit := [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 3, 4 ],
          [ 2, 4 ] ], stabilizer := Group([ (1,2)(3,4) ]) )
    gap> Parent(orbstab.stabilizer);
    Group([ (1,3,2), (2,4,3) ])

(See Section 41.2 for information about specific actions.)

The standard methods for all these actions are an orbit-stabilizer algorithm. For permutation groups backtrack algorithms are used. For solvable groups an orbit-stabilizer algorithm for solvable groups, which uses the fact that the orbits of a normal subgroup form a block system (see [LNS84]) is used.

##### 41.5-3 OrbitStabilizerAlgorithm

`‣ OrbitStabilizerAlgorithm`( G, Omega, blist, gens, acts, pntact ) | ( operation )

This operation should not be called by a user. It is documented however for purposes to extend or maintain the group actions package (the word package here refers to the GAP functionality for group actions, not to a GAP package).

`OrbitStabilizerAlgorithm` performs an orbit stabilizer algorithm for the group G acting with the generators gens via the generator images gens and the group action act on the element pnt. (For technical reasons pnt and act are put in one record with components `pnt` and `act` respectively.)

The pntact record may carry a component stabsub. If given, this must be a subgroup stabilizing all points in the domain and can be used to abbreviate stabilizer calculations.

The pntact component also may contain the boolean entry `onlystab` set to `true`. In this case the `orbit` component may be omitted from the result.

The argument Omega (which may be replaced by `false` to be ignored) is the set within which the orbit is computed (once the orbit is the full domain, the orbit calculation may stop). If blist is given it must be a bit list corresponding to Omega in which elements which have been found already will be ticked off with `true`. (In particular, the entries for the orbit of pnt still must be all set to `false`). Again the remaining action domain (the bits set initially to `false`) can be used to stop if the orbit cannot grow any longer. Another use of the bit list is if Omega is an enumerator which can determine `PositionCanonical` (21.16-3) values very quickly. In this situation it can be worth to search images not in the orbit found so far, but via their position in Omega and use a the bit list to keep track whether the element is in the orbit found so far.

#### 41.6 Elements with Prescribed Images

##### 41.6-1 RepresentativeAction

`‣ RepresentativeAction`( G[, Omega], d, e[, gens, acts][, act] ) | ( function )

computes an element of G that maps d to e under the given action and returns `fail` if no such element exists.

    gap> g:=Group((1,3,2),(2,4,3));;
    gap> RepresentativeAction(g,1,3);
    (1,3)(2,4)
    gap> RepresentativeAction(g,1,3,OnPoints);
    (1,3)(2,4)
    gap> RepresentativeAction(g,(1,2,3),(2,4,3));
    (1,2,4)
    gap> RepresentativeAction(g,(1,2,3),(2,3,4));
    fail
    gap> RepresentativeAction(g,Group((1,2,3)),Group((2,3,4)));
    (1,2,4)
    gap>  RepresentativeAction(g,[1,2,3],[1,2,4],OnSets);
    (2,4,3)
    gap>  RepresentativeAction(g,[1,2,3],[1,2,4],OnTuples);
    fail

(See Section 41.2 for information about specific actions.)

Again the standard method for `RepresentativeAction` is an orbit-stabilizer algorithm, for permutation groups and standard actions a backtrack algorithm is used.

#### 41.7 The Permutation Image of an Action

When a group G acts on a domain Ω, an enumeration of Omega yields a homomorphism from G into the symmetric group on { 1, ..., |Ω| }. In GAP, the enumeration of Ω is provided by the `Enumerator` (30.3-2) value of Ω which of course is Ω itself if it is a list.

For an action homomorphism, the operation `UnderlyingExternalSet` (41.12-16) will return the external set on Ω which affords the action.

##### 41.7-1 ActionHomomorphism

`‣ ActionHomomorphism`( G, Omega[, gens, acts][, act][, "surjective"] ) | ( function )

`‣ ActionHomomorphism`( xset[, "surjective"] ) | ( function )

`‣ ActionHomomorphism`( action ) | ( function )

computes a homomorphism from G into the symmetric group on |Omega| points that gives the permutation action of G on Omega. (In particular, this homomorphism is a permutation equivalence, that is the permutation image of a group element is given by the positions of points in Omega.)

The result is undefined if G does not act on Omega.

By default the homomorphism returned by `ActionHomomorphism` is not necessarily surjective (its `Range` (32.3-7) value is the full symmetric group) to avoid unnecessary computation of the image. If the optional string argument `"surjective"` is given, a surjective homomorphism is created.

The third version (which is supported only for GAP3 compatibility) returns the action homomorphism that belongs to the image obtained via `Action` (41.7-2).

(See Section 41.2 for information about specific actions.)

    gap> g:=Group((1,2,3),(1,2));;
    gap> hom:=ActionHomomorphism(g,Arrangements([1..4],3),OnTuples);
    <action homomorphism>
    gap> Image(hom);
    Group(
    [ (1,9,13)(2,10,14)(3,7,15)(4,8,16)(5,12,17)(6,11,18)(19,22,23)(20,21,
        24), (1,7)(2,8)(3,9)(4,10)(5,11)(6,12)(13,15)(14,16)(17,18)(19,
        21)(20,22)(23,24) ])
    gap> Size(Range(hom));Size(Image(hom));
    620448401733239439360000
    6
    gap> hom:=ActionHomomorphism(g,Arrangements([1..4],3),OnTuples,
    > "surjective");;
    gap> Size(Range(hom));
    6

When acting on a domain, the operation `PositionCanonical` (21.16-3) is used to determine the position of elements in the domain. This can be used to act on a domain given by a list of representatives for which `PositionCanonical` (21.16-3) is implemented, for example the return value of `RightTransversal` (39.8-1).

##### 41.7-2 Action

`‣ Action`( G, Omega[, gens, acts][, act] ) | ( function )

`‣ Action`( xset ) | ( function )

returns the image group of `ActionHomomorphism` (41.7-1) called with the same parameters.

Note that (for compatibility reasons to be able to get the action homomorphism) this image group internally stores the action homomorphism. If G or Omega are extremely big, this can cause memory problems. In this case compute only generator images and form the image group yourself.

(See Section 41.2 for information about specific actions.)

The following code shows for example how to create the regular action of a group.

    gap> g:=Group((1,2,3),(1,2));;
    gap> Action(g,AsList(g),OnRight);
    Group([ (1,5,3)(2,6,4), (1,6)(2,5)(3,4) ])

##### 41.7-3 SparseActionHomomorphism

`‣ SparseActionHomomorphism`( G, start[, gens, acts][, act] ) | ( operation )

`‣ SortedSparseActionHomomorphism`( G, start[, gens, acts][, act] ) | ( operation )

`SparseActionHomomorphism` computes the action homomorphism (see `ActionHomomorphism` (41.7-1)) with arguments G, D, and the optional arguments given, where D is the union of the G-orbits of all points in start. In the `Orbit` (41.4-1) calls that are used to create D, again the optional arguments given are entered.)

If G acts on a very large domain not surjectively this may yield a permutation image of substantially smaller degree than by action on the whole domain.

The operation `SparseActionHomomorphism` will only use `\=` (31.11-1) comparisons of points in the orbit. Therefore it can be used even if no good `\<` (31.11-1) comparison method for these points is available. However the image group will depend on the generators gens of G.

The operation `SortedSparseActionHomomorphism` in contrast will sort the orbit and thus produce an image group which does not depend on these generators.

    gap> h:=Group(Z(3)*[[[1,1],[0,1]]]);
    Group([ [ [ Z(3), Z(3) ], [ 0*Z(3), Z(3) ] ] ])
    gap> hom:=ActionHomomorphism(h,GF(3)^2,OnRight);;
    gap> Image(hom);
    Group([ (2,3)(4,9,6,7,5,8) ])
    gap> hom:=SparseActionHomomorphism(h,[Z(3)*[1,0]],OnRight);;
    gap> Image(hom);
    Group([ (1,2,3,4,5,6) ])

#### 41.8 Action of a group on itself

Of particular importance is the action of a group on its elements or cosets of a subgroup. These actions can be obtained by using `ActionHomomorphism` (41.7-1) for a suitable domain (for example a list of subgroups). For the following (frequently used) types of actions however special (often particularly efficient) functions are provided. A special case is the regular action on all elements.

##### 41.8-1 FactorCosetAction

`‣ FactorCosetAction`( G, U[, N] ) | ( operation )

`‣ FactorCosetAction`( G, L ) | ( operation )

This command computes the action of the group G on the right cosets of the subgroup U. If a normal subgroup N of G is given, it is stored as kernel of this action. When calling `FactorCosetAction` with a list of subgroups as the second argument, an action with image isomorphic to the subdirect product of the coset actions of all subgroups is computed. (However a degree reduction may take place if some of the actions are redundant, i.e. there is no guarantee that every subgroup in the list is represented by an orbit.)

    gap> g:=Group((1,2,3,4,5),(1,2));;u:=SylowSubgroup(g,2);;Index(g,u);
    15
    gap> FactorCosetAction(g,u);
    [ (1,2,3,4,5), (1,2) ] -> [ (1,4,7,10,13)(2,5,8,11,14)(3,6,9,12,15),\
      (1,4)(2,6)(3,5)(7,8)(10,12)(13,14) ]
    gap> StructureDescription(Range(last));
    "S5"
    gap> FactorCosetAction(g,[u,SylowSubgroup(g,3)]);;
    gap> Size(Image(last));
    120

The correspondence of points with cosets will, for performance reasons, depend on the method used. It is not guaranteed that it will be the same as used by `RightTransversal` or `RightCosets`.

##### 41.8-2 RegularActionHomomorphism

`‣ RegularActionHomomorphism`( G ) | ( attribute )

returns an isomorphism from G onto the regular permutation representation of G.

##### 41.8-3 AbelianSubfactorAction

`‣ AbelianSubfactorAction`( G, M, N ) | ( operation )

Let G be a group and M ≥ N be subgroups of a common parent that are normal under G, such that the subfactor M/N is elementary abelian. The operation `AbelianSubfactorAction` returns a list `[ phi, alpha, bas ]` where bas is a list of elements of M which are representatives for a basis of M/N, alpha is a map from M into a n-dimensional row space over GF(p) where [M:N] = p^n that is the natural homomorphism of M by N with the quotient represented as an additive group. Finally phi is a homomorphism from G into GL_n(p) that represents the action of G on the factor M/N.

Note: If only matrices for the action are needed, `LinearActionLayer` (45.14-3) might be faster.

    gap> g:=Group((1,8,10,7,3,5)(2,4,12,9,11,6),
    >             (1,9,5,6,3,10)(2,11,12,8,4,7));;
    gap> c:=ChiefSeries(g);;List(c,Size);
    [ 96, 48, 16, 4, 1 ]
    gap> HasElementaryAbelianFactorGroup(c[3],c[4]);
    true
    gap> SetName(c[3],"my_group");;
    gap> a:=AbelianSubfactorAction(g,c[3],c[4]);
    [ [ (1,8,10,7,3,5)(2,4,12,9,11,6), (1,9,5,6,3,10)(2,11,12,8,4,7) ] ->
        [ <an immutable 2x2 matrix over GF2>,
          <an immutable 2x2 matrix over GF2> ],
      MappingByFunction( my_group, ( GF(2)^
        2 ), function( e ) ... end, function( r ) ... end ),
      Pcgs([ (2,9,3,8)(4,11,5,10), (1,6,12,7)(4,10,5,11) ]) ]
    gap> mat:=Image(a[1],g);
    Group([ <an immutable 2x2 matrix over GF2>,
      <an immutable 2x2 matrix over GF2> ])
    gap> Size(mat);
    3
    gap> e:=PreImagesRepresentative(a[2],[Z(2),0*Z(2)]);
    (2,9,3,8)(4,11,5,10)
    gap> e in c[3];e in c[4];
    true
    false

#### 41.9 Permutations Induced by Elements and Cycles

If only the permutation image of a single element is needed, it might not be worth to create the action homomorphism, the following operations yield the permutation image and cycles of a single element.

##### 41.9-1 Permutation

`‣ Permutation`( g, Omega[, gens, acts][, act] ) | ( function )

`‣ Permutation`( g, xset ) | ( function )

computes the permutation that corresponds to the action of g on the permutation domain Omega (a list of objects that are permuted). If an external set xset is given, the permutation domain is the `HomeEnumerator` (41.12-5) value of this external set (see Section 41.12). Note that the points of the returned permutation refer to the positions in Omega, even if Omega itself consists of integers.

If g does not leave the domain invariant, or does not map the domain injectively then `fail` is returned.

##### 41.9-2 PermutationCycle

`‣ PermutationCycle`( g, Omega, pnt[, act] ) | ( function )

computes the permutation that represents the cycle of pnt under the action of the element g.

    gap> Permutation([[Z(3),-Z(3)],[Z(3),0*Z(3)]],AsList(GF(3)^2));
    (2,7,6)(3,4,8)
    gap> Permutation((1,2,3)(4,5)(6,7),[4..7]);
    (1,2)(3,4)
    gap> PermutationCycle((1,2,3)(4,5)(6,7),[4..7],4);
    (1,2)

##### 41.9-3 Cycle

`‣ Cycle`( g, Omega, pnt[, act] ) | ( function )

returns a list of the points in the cycle of pnt under the action of the element g.

##### 41.9-4 CycleLength

`‣ CycleLength`( g, Omega, pnt[, act] ) | ( function )

returns the length of the cycle of pnt under the action of the element g.

##### 41.9-5 Cycles

`‣ Cycles`( g, Omega[, act] ) | ( function )

returns a list of the cycles (as lists of points) of the action of the element g.

##### 41.9-6 CycleLengths

`‣ CycleLengths`( g, Omega[, act] ) | ( operation )

returns the lengths of all the cycles under the action of the element g on Omega.

    gap> Cycle((1,2,3)(4,5)(6,7),[4..7],4);
    [ 4, 5 ]
    gap> CycleLength((1,2,3)(4,5)(6,7),[4..7],4);
    2
    gap> Cycles((1,2,3)(4,5)(6,7),[4..7]);
    [ [ 4, 5 ], [ 6, 7 ] ]
    gap> CycleLengths((1,2,3)(4,5)(6,7),[4..7]);
    [ 2, 2 ]

##### 41.9-7 CycleIndex

`‣ CycleIndex`( g, Omega[, act] ) | ( function )

`‣ CycleIndex`( G, Omega[, act] ) | ( function )

The cycle index of a permutation g acting on Omega is defined as

z(g) = s_1^{c_1} s_2^{c_2} ⋯ s_n^{c_n}

where c_k is the number of k-cycles in the cycle decomposition of g and the s_i are indeterminates.

The cycle index of a group G is defined as

Z(G) = ( ∑_{g ∈ G} z(g) ) / |G| .

The indeterminates used by `CycleIndex` are the indeterminates 1 to n over the rationals (see `Indeterminate` (66.1-1)).

    gap> g:=TransitiveGroup(6,8);
    S_4(6c) = 1/2[2^3]S(3)
    gap> CycleIndex(g);
    1/24*x_1^6+1/8*x_1^2*x_2^2+1/4*x_1^2*x_4+1/4*x_2^3+1/3*x_3^2

#### 41.10 Tests for Actions

##### 41.10-1 IsTransitive

`‣ IsTransitive`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ IsTransitive`( G ) | ( property )

`‣ IsTransitive`( xset ) | ( property )

returns `true` if the action implied by the arguments is transitive, or `false` otherwise.

We say that a group G acts transitively on a domain D if and only if G acts on D and for every pair of points d, e ∈ D there is an element g in G such that d^g = e.

For a permutation group G, one may also invoke this as `IsTransitive(G)`, which tests whether the group is transitive with respect to its natural action on the set of points moved by it. For example the group ⟨ (2,3,4),(2,3) ⟩ is transitive on the set {2, 3, 4}.

    gap> G:= Group( (2,3,4), (2,3) );;
    gap> IsTransitive( G, [ 2 .. 4 ] );
    true
    gap> IsTransitive( G, [ 2, 3 ] );   # G does not act on [ 2, 3 ]
    false
    gap> IsTransitive( G, [ 1 .. 4 ] );  # G has two orbits on [ 1 .. 4 ]
    false
    gap> IsTransitive( G );  # G is transitive on [ 2 .. 4 ]
    true
    gap> IsTransitive( SL(2, 3), NormedRowVectors( GF(3)^2 ) );
    false
    gap> IsTransitive( SL(2, 3), NormedRowVectors( GF(3)^2 ), OnLines );
    true

##### 41.10-2 Transitivity

`‣ Transitivity`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ Transitivity`( G ) | ( attribute )

`‣ Transitivity`( xset ) | ( attribute )

returns the degree k (a non-negative integer) of transitivity of the action implied by the arguments, i.e. the largest integer k such that the action is k-transitive. If the action is not transitive `0` is returned.

An action is k-transitive if every k-tuple of points can be mapped simultaneously to every other k-tuple.

For a permutation group G, one may also invoke this as `Transitivity(G)`, which returns the degree of transitivity of the group with respect to its natural action on the set of points moved by it. For example the group ⟨ (2,3,4),(2,3) ⟩ is 3-transitive on the set {2, 3, 4}.

    gap> g:=Group((1,3,2),(2,4,3));;
    gap> IsTransitive(g,[1..5]);
    false
    gap> Transitivity(g,[1..4]);
    2
    gap> Transitivity(g);
    2

##### 41.10-3 RankAction

`‣ RankAction`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ RankAction`( xset ) | ( attribute )

returns the rank of the transitive (see `IsTransitive` (41.10-1)) action of G on Omega, i. e., the number of orbits of any point stabilizer.

    gap> RankAction(g,Combinations([1..4],2),OnSets);
    4

##### 41.10-4 IsSemiRegular

`‣ IsSemiRegular`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ IsSemiRegular`( G ) | ( property )

`‣ IsSemiRegular`( xset ) | ( property )

returns `true` if the action implied by the arguments is semiregular, or `false` otherwise.

An action is semiregular if the stabilizer of each point is the identity.

For a permutation group G, one may also invoke this as `IsSemiRegular(G)`, which tests whether the group is semiregular with respect to its natural action on the set of points moved by it. For example the group ⟨ (2,3,4) (5,6,7) ⟩ is semiregular on the set {2, 3, 4, 5, 6, 7}.

##### 41.10-5 IsRegular

`‣ IsRegular`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ IsRegular`( G ) | ( property )

`‣ IsRegular`( xset ) | ( property )

returns `true` if the action implied by the arguments is regular, or `false` otherwise.

An action is regular if it is both semiregular (see `IsSemiRegular` (41.10-4)) and transitive (see `IsTransitive` (41.10-1)). In this case every point pnt of Omega defines a one-to-one correspondence between G and Omega.

For a permutation group G, one may also invoke this as `IsRegular(G)`, which tests whether the group is regular with respect to its natural action on the set of points moved by it. For example the group ⟨ (2,3,4) ⟩ is regular on the set {2, 3, 4}.

    gap> IsSemiRegular(g,Arrangements([1..4],3),OnTuples);
    true
    gap> IsRegular(g,Arrangements([1..4],3),OnTuples);
    false

##### 41.10-6 Earns

`‣ Earns`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ Earns`( xset ) | ( attribute )

returns a list of the elementary abelian regular (when acting on Omega) normal subgroups of G.

At the moment only methods for a primitive group G are implemented.

##### 41.10-7 IsPrimitive

`‣ IsPrimitive`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ IsPrimitive`( G ) | ( property )

`‣ IsPrimitive`( xset ) | ( property )

returns `true` if the action implied by the arguments is primitive, or `false` otherwise.

An action is primitive if it is transitive (see `IsTransitive` (41.10-1)) and the action admits no nontrivial block systems. See 41.11 for the definition of block systems.

For a permutation group G, one may also invoke this as `IsPrimitive(G)`, which tests whether the group is primitive with respect to its natural action on the set of points moved by it. For example the group ⟨ (2,3,4),(2,3) ⟩ is primitive on the set {2, 3, 4}.

For an explanation of the meaning of all the inputs, please refer to 41.1.

Note: This operation does not tell whether a matrix group is primitive in the sense of preserving a direct sum of vector spaces. To do this use `IsPrimitiveMatrixGroup` or `IsPrimitive` from the package IRREDSOL.

    gap> IsPrimitive(g,Orbit(g,(1,2)(3,4)));
    true

#### 41.11 Block Systems

A block system (system of imprimitivity) for the action of a group G on an action domain Ω is a partition of Ω which –as a partition– remains invariant under the action of G. For operations concerning block systems, GAP assumes that G acts transitively on Ω (see `IsTransitive` (41.10-1)). One may get wrong results or error messages (perhaps at a much later stage) if this condition is not satisfied.

##### 41.11-1 Blocks

`‣ Blocks`( G, Omega[, seed][, gens, acts][, act] ) | ( operation )

`‣ Blocks`( xset[, seed] ) | ( attribute )

computes a block system for the transitive (see `IsTransitive` (41.10-1)) action of G on Omega. If seed is not given and the action is imprimitive, a minimal nontrivial block system will be found. If seed is given, a block system in which seed is the subset of one block is computed.

The result is undefined if the action is not transitive.

    gap> g:=TransitiveGroup(8,3);
    E(8)=2[x]2[x]2
    gap> Blocks(g,[1..8]);
    [ [ 1, 8 ], [ 2, 3 ], [ 4, 5 ], [ 6, 7 ] ]
    gap> Blocks(g,[1..8],[1,4]);
    [ [ 1, 4 ], [ 2, 7 ], [ 3, 6 ], [ 5, 8 ] ]

(See Section 41.2 for information about specific actions.)

##### 41.11-2 MaximalBlocks

`‣ MaximalBlocks`( G, Omega[, seed][, gens, acts][, act] ) | ( operation )

`‣ MaximalBlocks`( xset[, seed] ) | ( attribute )

returns a block system that is maximal (i.e., blocks are maximal with respect to inclusion) for the transitive (see `IsTransitive` (41.10-1)) action of G on Omega. If seed is given, a block system is computed in which seed is a subset of one block.

The result is undefined if the action is not transitive.

    gap> MaximalBlocks(g,[1..8]);
    [ [ 1, 2, 3, 8 ], [ 4 .. 7 ] ]

##### 41.11-3 RepresentativesMinimalBlocks

`‣ RepresentativesMinimalBlocks`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ RepresentativesMinimalBlocks`( xset ) | ( attribute )

computes a list of block representatives for all minimal (i.e blocks are minimal with respect to inclusion) nontrivial block systems for the transitive (see `IsTransitive` (41.10-1)) action of G on Omega.

The result is undefined if the action is not transitive.

    gap> RepresentativesMinimalBlocks(g,[1..8]);
    [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ], [ 1, 7 ],
      [ 1, 8 ] ]

##### 41.11-4 AllBlocks

`‣ AllBlocks`( G ) | ( attribute )

computes a list of representatives of all block systems for a permutation group G acting transitively on the points moved by the group.

Each representative in the returned list is sorted and contains the smallest point moved by G.

    gap> AllBlocks(g);
    [ [ 1, 8 ], [ 1, 2, 3, 8 ], [ 1, 4, 5, 8 ], [ 1, 6, 7, 8 ], [ 1, 3 ],
      [ 1, 3, 5, 7 ], [ 1, 3, 4, 6 ], [ 1, 5 ], [ 1, 2, 5, 6 ], [ 1, 2 ],
      [ 1, 2, 4, 7 ], [ 1, 4 ], [ 1, 7 ], [ 1, 6 ] ]

The stabilizer of a block can be computed via the action `OnSets` (41.2-4):

    gap> Stabilizer(g,[1,8],OnSets);
    Group([ (1,8)(2,3)(4,5)(6,7) ])

If `bs` is a partition of the action domain, given as a set of sets, the stabilizer under the action `OnSetsDisjointSets` (41.2-8) returns the largest subgroup which preserves `bs` as a block system.

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

#### 41.12 External Sets

When considering group actions, sometimes the concept of a G-set is used. This is a set Ω endowed with an action of G. The elements of the G-set are the same as those of Ω, however concepts like equality and equivalence of G-sets do not only consider the underlying domain Ω but the group action as well.

This concept is implemented in GAP via external sets.

The constituents of an external set are stored in the attributes `ActingDomain` (41.12-3), `FunctionAction` (41.12-4) and `HomeEnumerator` (41.12-5).

Most operations for actions are applicable as an attribute for an external set.

The most prominent external subsets are orbits, see `ExternalOrbit` (41.12-9).

Many subsets of a group, such as conjugacy classes or cosets (see `ConjugacyClass` (39.10-1) and `RightCoset` (39.7-1)) are implemented as external orbits.

External sets also are implicitly underlying action homomorphisms, see `UnderlyingExternalSet` (41.12-16) and `SurjectiveActionHomomorphismAttr` (41.12-17).

##### 41.12-1 IsExternalSet

`‣ IsExternalSet`( obj ) | ( category )

An external set specifies a group action μ: Ω × G ↦ Ω of a group G on a domain Ω. The external set knows the group, the domain and the actual acting function. Mathematically, an external set is the set Ω, which is endowed with the action of a group G via the group action μ. For this reason GAP treats an external set as a domain whose elements are the elements of Ω. An external set is always a union of orbits. Currently the domain Ω must always be finite. If Ω is not a list, an enumerator for Ω is automatically chosen, see `Enumerator` (30.3-2).

##### 41.12-2 ExternalSet

`‣ ExternalSet`( G, Omega[, gens, acts][, act] ) | ( operation )

creates the external set for the action act of G on Omega. Omega can be either a proper set, or a domain which is represented as described in 12.4 and 30, or (to use less memory but with a slower performance) an enumerator (see `Enumerator` (30.3-2) ) of this domain.

The result is undefined if G does not act on Omega.

    gap> g:=Group((1,2,3),(2,3,4));;
    gap> e:=ExternalSet(g,[1..4]);
    <xset:[ 1, 2, 3, 4 ]>
    gap> e:=ExternalSet(g,g,OnRight);
    <xset:[ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2),
      (1,3,4), (1,3)(2,4), (1,4,2), (1,4,3), (1,4)(2,3) ]>
    gap> Orbits(e);
    [ [ (), (1,2)(3,4), (1,3)(2,4), (1,4)(2,3), (2,4,3), (1,4,2),
          (1,2,3), (1,3,4), (2,3,4), (1,3,2), (1,4,3), (1,2,4) ] ]

##### 41.12-3 ActingDomain

`‣ ActingDomain`( xset ) | ( attribute )

This attribute returns the group with which the external set xset was defined.

##### 41.12-4 FunctionAction

`‣ FunctionAction`( xset ) | ( attribute )

is the acting function with which the external set xset was defined.

##### 41.12-5 HomeEnumerator

`‣ HomeEnumerator`( xset ) | ( attribute )

returns an enumerator of the action domain with which the external set xset was defined. For external subsets, this is in general different from the `Enumerator` (30.3-2) value of xset, which enumerates only the subset.

    gap> ActingDomain(e);
    Group([ (1,2,3), (2,3,4) ])
    gap> FunctionAction(e)=OnRight;
    true
    gap> HomeEnumerator(e);
    [ (), (2,3,4), (2,4,3), (1,2)(3,4), (1,2,3), (1,2,4), (1,3,2),
      (1,3,4), (1,3)(2,4), (1,4,2), (1,4,3), (1,4)(2,3) ]

##### 41.12-6 IsExternalSubset

`‣ IsExternalSubset`( obj ) | ( representation )

An external subset is the restriction of an external set to a subset of the domain (which must be invariant under the action). It is again an external set.

##### 41.12-7 ExternalSubset

`‣ ExternalSubset`( G, Omega, start[, gens, acts], act ) | ( operation )

constructs the external subset of Omega on the union of orbits of the points in start.

The result is undefined if G does not act on Omega.

##### 41.12-8 IsExternalOrbit

`‣ IsExternalOrbit`( obj ) | ( representation )

An external orbit is an external subset consisting of one orbit.

##### 41.12-9 ExternalOrbit

`‣ ExternalOrbit`( G, Omega, pnt[, gens, acts], act ) | ( operation )

constructs the external subset on the orbit of pnt. The `Representative` (30.4-7) value of this external set is pnt.

The result is undefined if G does not act on Omega.

    gap> e:=ExternalOrbit(g,g,(1,2,3));
    (1,2,3)^G

##### 41.12-10 StabilizerOfExternalSet

`‣ StabilizerOfExternalSet`( xset ) | ( attribute )

computes the stabilizer of the `Representative` (30.4-7) value of the external set xset. The stabilizer will have the acting group of xset as its parent.

    gap> Representative(e);
    (1,2,3)
    gap> StabilizerOfExternalSet(e);
    Group([ (1,2,3) ])

##### 41.12-11 ExternalOrbits

`‣ ExternalOrbits`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ ExternalOrbits`( xset ) | ( attribute )

computes a list of external orbits that give the orbits of G.

    gap> ExternalOrbits(g,AsList(g));
    [ ()^G, (2,3,4)^G, (2,4,3)^G, (1,2)(3,4)^G ]

##### 41.12-12 ExternalOrbitsStabilizers

`‣ ExternalOrbitsStabilizers`( G, Omega[, gens, acts][, act] ) | ( operation )

`‣ ExternalOrbitsStabilizers`( xset ) | ( attribute )

In addition to `ExternalOrbits` (41.12-11), this operation also computes the stabilizers of the representatives of the external orbits at the same time. (This can be quicker than computing the `ExternalOrbits` (41.12-11) value first and the stabilizers afterwards.)

    gap> e:=ExternalOrbitsStabilizers(g,AsList(g));
    [ ()^G, (2,3,4)^G, (2,4,3)^G, (1,2)(3,4)^G ]
    gap> HasStabilizerOfExternalSet(e[3]);
    true
    gap> StabilizerOfExternalSet(e[3]);
    Group([ (2,4,3) ])

##### 41.12-13 CanonicalRepresentativeOfExternalSet

`‣ CanonicalRepresentativeOfExternalSet`( xset ) | ( attribute )

The canonical representative of an external set xset may only depend on the defining attributes G, Omega, act of xset and (in the case of external subsets) `Enumerator( xset )`. It must not depend, e.g., on the representative of an external orbit. GAP does not know methods for arbitrary external sets to compute a canonical representative, see `CanonicalRepresentativeDeterminatorOfExternalSet` (41.12-14).

##### 41.12-14 CanonicalRepresentativeDeterminatorOfExternalSet

`‣ CanonicalRepresentativeDeterminatorOfExternalSet`( xset ) | ( attribute )

returns a function that takes as its arguments the acting group and a point. This function returns a list of length 1 or 3, the first entry being the canonical representative and the other entries (if bound) being the stabilizer of the canonical representative and a conjugating element, respectively. An external set is only guaranteed to be able to compute a canonical representative if it has a `CanonicalRepresentativeDeterminatorOfExternalSet`.

##### 41.12-15 ActorOfExternalSet

`‣ ActorOfExternalSet`( xset ) | ( attribute )

returns an element mapping `Representative(xset)` to `CanonicalRepresentativeOfExternalSet(xset)` under the given action.

    gap> u:=Subgroup(g,[(1,2,3)]);;
    gap> e:=RightCoset(u,(1,2)(3,4));;
    gap> CanonicalRepresentativeOfExternalSet(e);
    (2,4,3)
    gap> ActorOfExternalSet(e);
    (1,3,2)
    gap> FunctionAction(e)((1,2)(3,4),last);
    (2,4,3)

##### 41.12-16 UnderlyingExternalSet

`‣ UnderlyingExternalSet`( acthom ) | ( attribute )

The underlying set of an action homomorphism acthom is the external set on which it was defined.

    gap> g:=Group((1,2,3),(1,2));;
    gap> hom:=ActionHomomorphism(g,Arrangements([1..4],3),OnTuples);;
    gap> s:=UnderlyingExternalSet(hom);
    <xset:[[ 1, 2, 3 ],[ 1, 2, 4 ],[ 1, 3, 2 ],[ 1, 3, 4 ],[ 1, 4, 2 ],
    [ 1, 4, 3 ],[ 2, 1, 3 ],[ 2, 1, 4 ],[ 2, 3, 1 ],[ 2, 3, 4 ],
    [ 2, 4, 1 ],[ 2, 4, 3 ],[ 3, 1, 2 ],[ 3, 1, 4 ],[ 3, 2, 1 ], ...]>
    gap> Print(s,"\n");
    [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 2 ], [ 1, 3, 4 ], [ 1, 4, 2 ],
      [ 1, 4, 3 ], [ 2, 1, 3 ], [ 2, 1, 4 ], [ 2, 3, 1 ], [ 2, 3, 4 ],
      [ 2, 4, 1 ], [ 2, 4, 3 ], [ 3, 1, 2 ], [ 3, 1, 4 ], [ 3, 2, 1 ],
      [ 3, 2, 4 ], [ 3, 4, 1 ], [ 3, 4, 2 ], [ 4, 1, 2 ], [ 4, 1, 3 ],
      [ 4, 2, 1 ], [ 4, 2, 3 ], [ 4, 3, 1 ], [ 4, 3, 2 ] ]

##### 41.12-17 SurjectiveActionHomomorphismAttr

`‣ SurjectiveActionHomomorphismAttr`( xset ) | ( attribute )

returns an action homomorphism for the external set xset which is surjective. (As the `Image` (32.4-6) value of this homomorphism has to be computed to obtain the range, this may take substantially longer than `ActionHomomorphism` (41.7-1).)

[Top of Book] [Contents] [Previous Chapter] [Next Chapter]
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 Bib Ind

generated by GAPDoc2HTML