<html><head><title>[ref] 39 Group Actions</title></head>
<body text="#000000" bgcolor="#ffffff">
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP038.htm">Previous</a>] [<a href ="CHAP040.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<h1>39 Group Actions</h1><p>
<P>
<H3>Sections</H3>
<oL>
<li> <A HREF="CHAP039.htm#SECT001">About Group Actions</a>
<li> <A HREF="CHAP039.htm#SECT002">Basic Actions</a>
<li> <A HREF="CHAP039.htm#SECT003">Orbits</a>
<li> <A HREF="CHAP039.htm#SECT004">Stabilizers</a>
<li> <A HREF="CHAP039.htm#SECT005">Elements with Prescribed Images</a>
<li> <A HREF="CHAP039.htm#SECT006">The Permutation Image of an Action</a>
<li> <A HREF="CHAP039.htm#SECT007">Action of a group on itself</a>
<li> <A HREF="CHAP039.htm#SECT008">Permutations Induced by Elements and Cycles</a>
<li> <A HREF="CHAP039.htm#SECT009">Tests for Actions</a>
<li> <A HREF="CHAP039.htm#SECT010">Block Systems</a>
<li> <A HREF="CHAP039.htm#SECT011">External Sets</a>
</ol><p>
<p>
<a name = "I0"></a>
<a name = "I0"></a>
<a name = "I1"></a>
A <strong>group action</strong> is a triple (<i>G</i>,<i>Omega</i> ,μ), where <i>G</i> is a group,
<var>Omega</var> a set and μ:<i>Omega</i> ×<i>G</i>→<i>Omega</i> a function (whose
action is compatible with the group arithmetic). We call <var>Omega</var> the
<strong>domain</strong> of the action.
<p>
In <font face="Gill Sans,Helvetica,Arial">GAP</font>, <var>Omega</var> can be a duplicate-free collection (an object that
permits access to its elements via the <var>Omega</var>[<var>n</var>] operation, for example a
list), it does not need to be sorted (see <a href="CHAP021.htm#SSEC017.4">IsSet</a>).
<p>
The acting function μ is a <font face="Gill Sans,Helvetica,Arial">GAP</font> function of the form
<p>
<code>actfun(</code><var>pnt</var><code>,</code><var>g</var><code>)</code>
<p>
that returns the image μ(<i>pnt</i> ,<i>g</i> ) for a point <i>pnt</i> ∈ <i>Omega</i> and a
group element <i>g</i> ∈ <i>G</i> .
<p>
Groups always acts from the right, that is
μ(μ(<i>pnt</i> ,<i>g</i> ),<i>h</i> )=μ(<i>pnt</i> ,<i>gh</i> ).
<p>
<font face="Gill Sans,Helvetica,Arial">GAP</font> does not test whether an acting function <code>actfun</code> satisfies the
conditions for a group operation but silently assumes that is does.
(If it does not, results are unpredictable.)
<p>
The first section of this chapter, <a href="CHAP039.htm#SECT001">About Group Actions</a>, describes the
various ways how operations for group actions can be called.
<p>
Functions for several commonly used action are already built into <font face="Gill Sans,Helvetica,Arial">GAP</font>.
These are listed in section <a href="CHAP039.htm#SECT002">Basic Actions</a>.
<p>
The sections <a href="CHAP039.htm#SECT006">The Permutation Image of an Action</a> and
<a href="CHAP039.htm#SECT007">Action of a group on itself</a> describe homomorphisms and mappings associated
to group actions as well as the permutation group image of an action.
<p>
The other sections then describe operations to compute orbits,
stabilizers, as well as
properties of actions.
<p>
Finally section <a href="CHAP039.htm#SECT011">External Sets</a> describes the concept of ``external sets''
which represent the concept of a <strong><i>G</i>-set</strong> and underly the actions mechanism.
<p>
<p>
<h2><a name="SECT001">39.1 About Group Actions</a></h2>
<p><p>
<a name = "I2"></a>
The syntax which is used by the operations for group actions is quite
flexible. For example we can call the operation <code>OrbitsDomain</code> for the orbits
of the group <var>G</var> on the domain <var>Omega</var> in the following ways:
<p>
<code>OrbitsDomain(</code><var>G</var><code>,</code><var>Omega</var><code>[,</code><var>actfun</var><code>])</code>
<p>
The acting function <var>actfun</var> is optional. If it is not given, the built-in
action <code>OnPoints</code> (which defines an action via the caret operator <code>^</code>) is
used as a default.
<p>
<code>OrbitsDomain(</code><var>G</var><code>,</code><var>Omega</var><code>,</code><var>gens</var><code>,</code><var>acts</var><code>[,</code><var>actfun</var><code>])</code>
<p>
This second version (of <code>OrbitsDomain</code>) permits one to implement an action
induced by a homomorphism:
If <var>H</var> acts on <var>Omega</var> via μ and ϕ:<i>G</i>→ <i>H</i> is a
homomorphism, <var>G</var> acts on <var>Omega</var> via
μ′(ω,<i>g</i>)=μ(ω,<i>g</i><sup>ϕ</sup>):
<p>
Here <var>gens</var> must be a set of generators of <var>G</var> and <var>acts</var> the images of
<var>gens</var> under a homomorphism ϕ:<i>G</i>→ <i>H</i>.
<var>actfun</var> is the acting function for <var>H</var>, the call
to <code>ExampleActionFunction</code> implements the induced action of <var>G</var>.
Again, the acting function <var>actfun</var> is optional and <code>OnPoints</code> is used as a
default.
<p>
The advantage of this notation is that <font face="Gill Sans,Helvetica,Arial">GAP</font> does not need to construct
this homomorphism ϕ and the range group <var>H</var> as <font face="Gill Sans,Helvetica,Arial">GAP</font> objects. (If a
small group <var>G</var> acts via complicated objects <var>acts</var> this otherwise could
lead to performance problems.)
<p>
<font face="Gill Sans,Helvetica,Arial">GAP</font> does not test whether the mapping <i>gens</i> →<i>acts</i>
actually induces a homomorphism and the results are unpredictable if this is
not the case.
<p>
<code>OrbitsDomain(</code><var>extset</var><code>) A</code>
<p>
A third variant is to call the operation with an external set (which then
provides <var>G</var>, <var>Omega</var> and <var>actfun</var>. You will find more about external sets in
section <a href="CHAP039.htm#SECT011">External Sets</a>.
<p>
For operations like <code>Stabilizer</code> of course the domain must be replaced by an
element of <var>Omega</var> which is to be acted on.
<p>
<p>
<h2><a name="SECT002">39.2 Basic Actions</a></h2>
<p><p>
<a name = "I3"></a>
<a name = "I4"></a>
<a name = "I5"></a>
<font face="Gill Sans,Helvetica,Arial">GAP</font> already provides acting functions for the more common actions of a
group. For built-in operations such as <code>Stabilizer</code> special methods are
available for many of these actions.
<p>
This section also shows how to implement different actions. (Note that every
action must be from the right.)
<p>
<a name = "SSEC002.1"></a>
<li><code>OnPoints( </code><var>pnt</var><code>, </code><var>g</var><code> ) F</code>
<p>
<a name = "I6"></a>
<a name = "I6"></a>
<a name = "I7"></a>
returns <code></code><var>pnt</var><code> ^ </code><var>g</var><code></code>.
This is for example the action of a permutation group on points,
or the action of a group on its elements via conjugation.
The action of a matrix group on vectors from the right is described by
both <code>OnPoints</code> and <code>OnRight</code> (see <a href="CHAP039.htm#SSEC002.2">OnRight</a>).
<p>
<a name = "SSEC002.2"></a>
<li><code>OnRight( </code><var>pnt</var><code>, </code><var>g</var><code> ) F</code>
<p>
returns <code></code><var>pnt</var><code> * </code><var>g</var><code></code>.
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 <code>OnPoints</code> (see <a href="CHAP039.htm#SSEC002.1">OnPoints</a>) and <code>OnRight</code>.
<p>
<a name = "SSEC002.3"></a>
<li><code>OnLeftInverse( </code><var>pnt</var><code>, </code><var>g</var><code> ) F</code>
<p>
returns <i>g</i> <sup>−1</sup> <code>* </code><var>pnt</var><code></code>.
Forming the inverse is necessary to make this a proper action,
as in <font face="Gill Sans,Helvetica,Arial">GAP</font> groups always act from the right.
<p>
(<code>OnLeftInverse</code> is used for example in the representation of a right
coset as an external set (see <a href="CHAP039.htm#SECT011">External Sets</a>), that is a right coset
<i>Ug</i> is an external set for the group <i>U</i> acting on it via
<code>OnLeftInverse</code>.)
<p>
<a name = "SSEC002.4"></a>
<li><code>OnSets( </code><var>set</var><code>, </code><var>g</var><code> ) F</code>
<p>
<a name = "I8"></a>
<a name = "I8"></a>
<a name = "I9"></a>
Let <var>set</var> be a proper set (see <a href="CHAP021.htm#SECT019">Sorted Lists and Sets</a>).
<code>OnSets</code> returns the proper set formed by the images
<code>OnPoints( </code><var>pnt</var><code>, </code><var>g</var><code> )</code> of all points <var>pnt</var> of <var>set</var>.
<p>
<code>OnSets</code> is for example used to compute the action of a permutation group
on blocks.
<p>
(<code>OnTuples</code> is an action on lists that preserves the ordering of entries,
see <a href="CHAP039.htm#SSEC002.5">OnTuples</a>.)
<p>
<a name = "SSEC002.5"></a>
<li><code>OnTuples( </code><var>tup</var><code>, </code><var>g</var><code> ) F</code>
<p>
Let <var>tup</var> be a list.
<code>OnTuples</code> returns the list formed by the images
<code>OnPoints( </code><var>pnt</var><code>, </code><var>g</var><code> )</code> for all points <var>pnt</var> of <var>tup</var>.
<p>
(<code>OnSets</code> is an action on lists that additionally sorts the entries of
the result, see <a href="CHAP039.htm#SSEC002.4">OnSets</a>.)
<p>
<a name = "SSEC002.6"></a>
<li><code>OnPairs( </code><var>tup</var><code>, </code><var>g</var><code> ) F</code>
<p>
is a special case of <code>OnTuples</code> (see <a href="CHAP039.htm#SSEC002.5">OnTuples</a>) for lists <var>tup</var>
of length 2.
<p>
<a name = "SSEC002.7"></a>
<li><code>OnSetsSets( </code><var>set</var><code>, </code><var>g</var><code> ) F</code>
<p>
Action on sets of sets;
for the special case that the sets are pairwise disjoint,
it is possible to use <code>OnSetsDisjointSets</code> (see <a href="CHAP039.htm#SSEC002.8">OnSetsDisjointSets</a>).
<p>
<a name = "SSEC002.8"></a>
<li><code>OnSetsDisjointSets( </code><var>set</var><code>, </code><var>g</var><code> ) F</code>
<p>
Action on sets of pairwise disjoint sets (see also <a href="CHAP039.htm#SSEC002.7">OnSetsSets</a>).
<p>
<a name = "SSEC002.9"></a>
<li><code>OnSetsTuples( </code><var>set</var><code>, </code><var>g</var><code> ) F</code>
<p>
Action on sets of tuples.
<p>
<a name = "SSEC002.10"></a>
<li><code>OnTuplesSets( </code><var>set</var><code>, </code><var>g</var><code> ) F</code>
<p>
Action on tuples of sets.
<p>
<a name = "SSEC002.11"></a>
<li><code>OnTuplesTuples( </code><var>set</var><code>, </code><var>g</var><code> ) F</code>
<p>
Action on tuples of tuples
<p>
<pre>
gap> g:=Group((1,2,3),(2,3,4));;
gap> Orbit(g,1,OnPoints);
[ 1, 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) ]
gap> Orbit(g,[1,2],OnPairs);
[ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ], [ 3, 1 ], [ 3, 4 ], [ 2, 1 ], [ 1, 4 ],
[ 4, 1 ], [ 4, 2 ], [ 3, 2 ], [ 2, 4 ], [ 4, 3 ] ]
gap> Orbit(g,[1,2],OnSets);
[ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ], [ 3, 4 ], [ 1, 4 ], [ 2, 4 ] ]
</pre>
<p>
<pre>
gap> Orbit(g,[[1,2],[3,4]],OnSetsSets);
[ [ [ 1, 2 ], [ 3, 4 ] ], [ [ 1, 4 ], [ 2, 3 ] ], [ [ 1, 3 ], [ 2, 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 ] ] ]
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 ] ] ]
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 ] ] ]
</pre>
<p>
<a name = "SSEC002.12"></a>
<li><code>OnLines( </code><var>vec</var><code>, </code><var>g</var><code> ) F</code>
<p>
Let <var>vec</var> be a <strong>normed</strong> row vector, that is,
its first nonzero entry is normed to the identity of the relevant field,
<code>OnLines</code> returns the row vector obtained from normalizing
<code>OnRight( </code><var>vec</var><code>, </code><var>g</var><code> )</code> by scalar multiplication from the left.
This action corresponds to the projective action of a matrix group
on 1-dimensional subspaces.
<p>
<pre>
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) ])
</pre>
<p>
<a name = "SSEC002.13"></a>
<li><code>OnIndeterminates( </code><var>poly</var><code>, </code><var>perm</var><code> ) F</code>
<p>
A permutation <var>perm</var> acts on the multivariate polynomial <var>poly</var> by
permuting the indeterminates as it permutes points.
<p>
<a name = "SSEC002.14"></a>
<li><code>Permuted( </code><var>list</var><code>, </code><var>perm</var><code> )</code>
<p>
The following example demonstrates <code>Permuted</code> being used to implement a
permutation action on a domain:
<p>
<pre>
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" ] ]
</pre>
<p>
<a name = "SSEC002.15"></a>
<li><code>OnSubspacesByCanonicalBasis( </code><var>bas</var><code>, </code><var>mat</var><code> ) F</code>
<p>
implements the operation of a matrix group on subspaces of a vector
space. <var>bas</var> must be a list of (linearly independent) vectors which
forms a basis of the subspace in Hermite normal form. <var>mat</var> 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 <var>bas</var> with
<var>mat</var>.)
<p>
<p>
If one needs an action for which no acting function is provided
by the library it can be implemented via a <font face="Gill Sans,Helvetica,Arial">GAP</font> function that
conforms to the syntax
<p>
<code>actfun(</code><var>omega</var><code>,</code><var>g</var><code>)</code>
<p>
For example one could define the following function that acts on pairs of
polynomials via <code>OnIndeterminates</code>:
<pre>
OnIndeterminatesPairs:=function(polypair,g)
return [OnIndeterminates(polypair[1],g),
OnIndeterminates(polypair[2],g)];
end;
</pre>
<p>
Note that this function <strong>must</strong> implement an action from the <strong>right</strong>. This is
not verified by <font face="Gill Sans,Helvetica,Arial">GAP</font> and results are unpredicatble otherwise.
<p>
<p>
<h2><a name="SECT003">39.3 Orbits</a></h2>
<p><p>
If <var>G</var> acts on <var>Omega</var> the set of all images of ω ∈ <i>Omega</i> under
elements of <var>G</var> is called the <strong>orbit</strong> of ω. The set of orbits of <var>G</var>
is a partition of <var>Omega</var>.
<p>
Note that currently <font face="Gill Sans,Helvetica,Arial">GAP</font> does <strong>not</strong> check whether a given point really
belongs to Ω.
For example, consider the following example where the projective action
of a matrix group on a finite vector space shall be computed.
<p>
<pre>
gap> Orbit( GL(2,3), [ -1, 0 ] * Z(3)^0, OnLines );
[ [ Z(3), 0*Z(3) ], [ Z(3)^0, 0*Z(3) ], [ Z(3)^0, Z(3) ], [ Z(3)^0, Z(3)^0 ],
[ 0*Z(3), Z(3)^0 ] ]
gap> Size( GL(2,3) ) / Length( last );
48/5
</pre>
<p>
The error is that <code>OnLines</code> (see <a href="CHAP039.htm#SSEC002.12">OnLines</a>) acts on the set of normed row
vectors (see <a href="CHAP059.htm#SSEC008.11">NormedRowVectors</a>) of the vector space in question,
but that the seed vector is itself not such a vector.
<p>
<a name = "SSEC003.1"></a>
<li><code>Orbit( </code><var>G</var><code>[, </code><var>Omega</var><code>], </code><var>pnt</var><code>, [</code><var>gens</var><code>, </code><var>acts</var><code>, ] </code><var>act</var><code> ) O</code>
<p>
The orbit of the point <var>pnt</var> is the list of all images of <var>pnt</var> under
the action.
<p>
(Note that the arrangement of points in this list is not defined by the
operation.)
<p>
The orbit of <var>pnt</var> will always contain one element that is <strong>equal</strong> to
<var>pnt</var>, however for performance reasons this element is not necessarily
<strong>identical</strong> to <var>pnt</var>, in particular if <var>pnt</var> is mutable.
<p>
<pre>
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 ] ]
</pre>
(See Section <a href="CHAP039.htm#SECT002">Basic Actions</a> for information about specific actions.)
<p>
<a name = "SSEC003.2"></a>
<li><code>Orbits( </code><var>G</var><code>, </code><var>seeds</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>Orbits( </code><var>xset</var><code> ) A</code>
<p>
returns a duplicate-free list of the orbits of the elements in <var>seeds</var>
under the action <var>act</var> of <var>G</var>
<p>
(Note that the arrangement of orbits or of points within one orbit is
not defined by the operation.)
<p>
<a name = "SSEC003.3"></a>
<li><code>OrbitsDomain( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>OrbitsDomain( </code><var>xset</var><code> ) A</code>
<p>
returns a list of the orbits of <var>G</var> on the domain <var>Omega</var> (given as
lists) under the action <var>act</var>.
<p>
This operation is often faster than <code>Orbits</code>.
The domain <var>Omega</var> must be closed under the action of <var>G</var>, otherwise an
error can occur.
<p>
(Note that the arrangement of orbits or of points within one orbit is
not defined by the operation.)
<p>
<pre>
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> ] ]
</pre>
(See Section <a href="CHAP039.htm#SECT002">Basic Actions</a> for information about specific actions.)
<p>
<a name = "SSEC003.4"></a>
<li><code>OrbitLength( </code><var>G</var><code>, </code><var>Omega</var><code>, </code><var>pnt</var><code>, [</code><var>gens</var><code>, </code><var>acts</var><code>, ] </code><var>act</var><code> ) O</code>
<p>
computes the length of the orbit of <var>pnt</var>.
<p>
<a name = "SSEC003.5"></a>
<li><code>OrbitLengths( </code><var>G</var><code>, </code><var>seeds</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>OrbitLengths( </code><var>xset</var><code> ) A</code>
<p>
computes the lengths of all the orbits of the elements in <var>seegs</var> under
the action <var>act</var> of <var>G</var>.
<p>
<a name = "SSEC003.6"></a>
<li><code>OrbitLengthsDomain( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>OrbitLengthsDomain( </code><var>xset</var><code> ) A</code>
<p>
computes the lengths of all the orbits of <var>G</var> on <var>Omega</var>.
<p>
This operation is often faster than <code>OrbitLengths</code>.
The domain <var>Omega</var> must be closed under the action of <var>G</var>, otherwise an
error can occur.
<p>
<pre>
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 ]
</pre>
<p>
<p>
<h2><a name="SECT004">39.4 Stabilizers</a></h2>
<p><p>
<a name = "I10"></a>
<a name = "I10"></a>
<a name = "I11"></a>
<a name = "I10"></a>
<a name = "I11"></a>
<a name = "I12"></a>
The <strong>Stabilizer</strong> of an element ω is the set of all those <i>g</i> ∈ <i>G</i>
which fix ω.
<p>
<a name = "SSEC004.1"></a>
<li><code>OrbitStabilizer( </code><var>G</var><code>, [</code><var>Omega</var><code>, ] </code><var>pnt</var><code>, [</code><var>gens</var><code>, </code><var>acts</var><code>, ] </code><var>act</var><code> ) O</code>
<p>
computes the orbit and the stabilizer of <var>pnt</var> simultaneously in a
single Orbit-Stabilizer algorithm.
<p>
The stabilizer must have <var>G</var> as its parent.
<p>
<a name = "SSEC004.2"></a>
<li><code>Stabilizer( </code><var>G</var><code> [, </code><var>Omega</var><code>], </code><var>pnt</var><code> [, </code><var>gens</var><code>, </code><var>acts</var><code>] [, </code><var>act</var><code>] ) F</code>
<p>
computes the stabilizer in <var>G</var> of the point <var>pnt</var>, that is the subgroup
of those elements of <var>G</var> that fix <var>pnt</var>.
The stabilizer will have <var>G</var> as its parent.
<p>
<pre>
gap> g:=Group((1,3,2),(2,4,3));;
gap> Stabilizer(g,4);
Group([ (1,3,2) ])
</pre>
<p>
The stabilizer of a set or tuple of points can be computed by specifying an
action of sets or tuples of points.
<pre>
gap> Stabilizer(g,[1,2],OnSets);
Group([ (1,2)(3,4) ])
gap> Stabilizer(g,[1,2],OnTuples);
Group(())
gap> 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) ]) )
</pre>
(See Section <a href="CHAP039.htm#SECT002">Basic Actions</a> for information about specific actions.)
<p>
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
<a href="biblio.htm#SOGOS"><cite>SOGOS</cite></a>) is used.
<p>
<a name = "SSEC004.3"></a>
<li><code>OrbitStabilizerAlgorithm( </code><var>G</var><code>, </code><var>Omega</var><code>, </code><var>blist</var><code>, </code><var>gens</var><code>, </code><var>acts</var><code>, </code><var>pntact</var><code> ) F</code>
<p>
This operation should not be called by a user. It is documented however
for purposes to extend or maintain the group actions package.
<p>
<code>OrbitStabilizerAlgorithm</code> performs an orbit stabilizer algorithm for
the group <var>G</var> acting with the generators <var>gens</var> via the generator images
<var>gens</var> and the group action <var>act</var> on the element <var>pnt</var>. (For
technical reasons <var>pnt</var> and <var>act</var> are put in one record with components
<code>pnt</code> and <code>act</code> respectively.)
<p>
The <var>pntact</var> record may carry a component <var>stabsub</var>. If given, this must
be a subgroup stabilizing <strong>all</strong> points in the domain and can be used to
abbreviate stabilizer calculations.
<p>
The argument <var>Omega</var> (which may be replaced by <code>false</code> 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 <var>blist</var> is given it must be
a bit list corresponding to <var>Omega</var> in which elements which have been found
already will be ``ticked off'' with <code>true</code>. (In particular, the entries
for the orbit of <var>pnt</var> still must be all set to <code>false</code>). Again the
remaining action domain (the bits set initially to <code>false</code>) can be
used to stop if the orbit cannot grow any longer.
Another use of the bit list is if <var>Omega</var> is an enumerator which can
determine <code>PositionCanonical</code>s very quickly. In this situation it can be
worth to search images not in the orbit found so far, but via their
position in <var>Omega</var> and use a the bit list to keep track whether the
element is in the orbit found so far.
<p>
<p>
<h2><a name="SECT005">39.5 Elements with Prescribed Images</a></h2>
<p><p>
<a name = "I13"></a>
<a name = "SSEC005.1"></a>
<li><code>RepresentativeAction( </code><var>G</var><code> [, </code><var>Omega</var><code>], </code><var>d</var><code>, </code><var>e</var><code> [, </code><var>gens</var><code>, </code><var>acts</var><code>] [, </code><var>act</var><code>] ) O</code>
<p>
computes an element of <var>G</var> that maps <var>d</var> to <var>e</var> under the given
action and returns <code>fail</code> if no such element exists.
<p>
<pre>
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
</pre>
(See Section <a href="CHAP039.htm#SECT002">Basic Actions</a> for information about specific actions.)
<p>
Again the standard method for <code>RepresentativeAction</code> is an orbit-stabilizer
algorithm, for permutation groups and standard actions a backtrack algorithm
is used.
<p>
<p>
<h2><a name="SECT006">39.6 The Permutation Image of an Action</a></h2>
<p><p>
If <i>G</i> acts on a domain <var>Omega</var>, an enumeration of <var>Omega</var> yields a
homomorphism of <i>G</i> into the symmetric group on {1,…,|<i>Omega</i> |}. In
<font face="Gill Sans,Helvetica,Arial">GAP</font>, the enumeration of the domain <var>Omega</var> is provided by the
<code>Enumerator</code> of <var>Omega</var> (see <a href="CHAP028.htm#SSEC002.2">Enumerator</a>) which of course is <var>Omega</var> itself
if it is a list.
<p>
<a name = "SSEC006.1"></a>
<li><code>ActionHomomorphism( </code><var>G</var><code>, </code><var>Omega</var><code> [, </code><var>gens</var><code>, </code><var>acts</var><code>] [, </code><var>act</var><code>] [, "surjective"] ) O</code>
<li><code>ActionHomomorphism( </code><var>xset</var><code> [, "surjective"] ) A</code>
<li><code>ActionHomomorphism( </code><var>action</var><code> ) A</code>
<p>
computes a homomorphism from <var>G</var> into the symmetric group on |<i>Omega</i> |
points that gives the permutation action of <var>G</var> on <var>Omega</var>.
<p>
By default the homomorphism returned by <code>ActionHomomorphism</code> is not
necessarily surjective (its <code>Range</code> is the full symmetric group) to
avoid unnecessary computation of the image. If the optional string
argument <code>"surjective"</code> is given, a surjective homomorphism is created.
<p>
The third version (which is supported only for <font face="Gill Sans,Helvetica,Arial">GAP</font>3 compatibility)
returns the action homomorphism that belongs to the image
obtained via <code>Action</code> (see <a href="CHAP039.htm#SSEC006.2">Action</a>).
<p>
(See Section <a href="CHAP039.htm#SECT002">Basic Actions</a> for information about specific actions.)
<pre>
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
</pre>
<p>
When acting on a domain, the operation <code>PositionCanonical</code> 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 <code>PositionCanonical</code>
is implemented, for example a <code>RightTransversal</code> (see <a href="CHAP037.htm#SSEC008.1">RightTransversal</a>).
<p>
<a name = "SSEC006.2"></a>
<li><code>Action( </code><var>G</var><code>, </code><var>Omega</var><code> [</code><var>gens</var><code>, </code><var>acts</var><code>] [, </code><var>act</var><code>] ) O</code>
<li><code>Action( </code><var>xset</var><code> ) A</code>
<p>
returns the <code>Image</code> group of <code>ActionHomomorphism</code> called with the same
parameters.
<p>
Note that (for compatibility reasons to be able to get the
action homomorphism) this image group internally stores the action
homomorphism. If <var>G</var> or <var>Omega</var> are exteremly big, this can cause memory
problems. In this case compute only generator images and form the image
group yourself.
<p>
(See Section <a href="CHAP039.htm#SECT002">Basic Actions</a> for information about specific actions.)
<a name = "I14"></a>
The following code shows for example how to create the regular action of a
group:
<pre>
gap> g:=Group((1,2,3),(1,2));;
gap> Action(g,AsList(g),OnRight);
Group([ (1,4,5)(2,3,6), (1,3)(2,4)(5,6) ])
</pre>
<p>
<a name = "SSEC006.3"></a>
<li><code>SparseActionHomomorphism( </code><var>G</var><code>, </code><var>Omega</var><code>, </code><var>start</var><code> [, </code><var>gens</var><code>, </code><var>acts</var><code>] [, </code><var>act</var><code>] ) O</code>
<a name = "SSEC006.3"></a>
<li><code>SortedSparseActionHomomorphism( </code><var>G</var><code>, </code><var>Omega</var><code>, </code><var>start</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>] [, </code><var>act</var><code>] ) O</code>
<p>
<code>SparseActionHomomorphism</code> computes the
<code>ActionHomomorphism(</code><var>G</var><code>,</code><var>dom</var><code>[,</code><var>gens</var><code>,</code><var>acts</var><code>][,</code><var>act</var><code>])</code>, where <var>dom</var>
is the union of the orbits <code>Orbit(</code><var>G</var><code>,</code><var>pnt</var><code>[,</code><var>gens</var><code>,</code><var>acts</var><code>][,</code><var>act</var><code>])</code>
for all points <var>pnt</var> from <var>start</var>. If <var>G</var> acts on a very large domain
<var>Omega</var> not surjectively this may yield a permutation image of
substantially smaller degree than by action on <var>Omega</var>.
<p>
The operation <code>SparseActionHomomorphism</code> will only use <code>=</code> comparisons
of points in the orbit. Therefore it can be used even if no good <code><</code>
comparison method exists. However the image group will depend on the
generators <var>gens</var> of <var>G</var>.
<p>
The operation <code>SortedSparseActionHomomorphism</code> in contrast
will sort the orbit and thus produce an image group which is not
dependent on these generators.
<p>
<pre>
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) ])
</pre>
<p>
For an action homomorphism, the operation <code>UnderlyingExternalSet</code>
(see <a href="CHAP039.htm#SSEC011.16">UnderlyingExternalSet</a>) will return the external set on <var>Omega</var> which
affords the action.
<p>
<p>
<h2><a name="SECT007">39.7 Action of a group on itself</a></h2>
<p><p>
Of particular importance is the action of a group on its elements or cosets
of a subgroup. These actions can be obtained by using <code>ActionHomomorphism</code>
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:
<p>
<a name = "SSEC007.1"></a>
<li><code>FactorCosetAction( </code><var>G</var><code>, </code><var>U</var><code>, [</code><var>N</var><code>] ) O</code>
<p>
This command computes the action of <var>G</var> on the right cosets of the
subgroup <var>U</var>. If the normal subgroup <var>N</var> is given, it is stored as kernel
of this action.
<p>
<pre>
gap> g:=Group((1,2,3,4,5),(1,2));;u:=SylowSubgroup(g,2);;Index(g,u);
15
gap> FactorCosetAction(g,u);
<action epimorphism>
gap> Range(last);
Group([ (1,9,13,10,4)(2,8,14,11,5)(3,7,15,12,6),
(1,7)(2,8)(3,9)(5,6)(10,11)(14,15) ])
</pre>
<p>
A special case is the regular action on all elements:
<a name = "SSEC007.2"></a>
<li><code>RegularActionHomomorphism( </code><var>G</var><code> ) A</code>
<p>
returns an isomorphism from <var>G</var> onto the regular permutation
representation of <var>G</var>.
<p>
<a name = "SSEC007.3"></a>
<li><code>AbelianSubfactorAction( </code><var>G</var><code>, </code><var>M</var><code>, </code><var>N</var><code> ) O</code>
<p>
Let <var>G</var> be a group and <i>M</i> ≥ <i>N</i> be subgroups of a common parent that
are normal under <var>G</var>, such that
the subfactor <i>M</i> /<i>N</i> is elementary abelian. The operation
<code>AbelianSubfactorAction</code> returns a list <code>[</code><var>phi</var><code>,</code><var>alpha</var><code>,</code><var>bas</var><code>]</code> where
<var>bas</var> is a list of elements of <var>M</var> which are representatives for a basis
of <i>M</i> /<i>N</i> , <var>alpha</var> is a map from <var>M</var> into a <i>n</i>-dimensional row space
over <i>GF</i>(<i>p</i>) where [<i>M</i> :<i>N</i> ]=<i>p</i><sup><i>n</i></sup> that is the
natural homomorphism of <var>M</var> by <var>N</var> with the quotient represented as an
additive group. Finally <var>phi</var> is a homomorphism from <var>G</var>
into <i>GL</i><sub><i>n</i></sub>(<i>p</i>) that represents the action of <var>G</var> on the factor
<i>M</i> /<i>N</i> .
<p>
Note: If only matrices for the action are needed, <code>LinearActionLayer</code>
might be faster.
<p>
<pre>
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,8,3,9)(4,10,5,11), (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,8,3,9)(4,10,5,11)
gap> e in c[3];e in c[4];
true
false
</pre>
<p>
<p>
<h2><a name="SECT008">39.8 Permutations Induced by Elements and Cycles</a></h2>
<p><p>
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.
<p>
<a name = "SSEC008.1"></a>
<li><code>Permutation( </code><var>g</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) F</code>
<li><code>Permutation( </code><var>g</var><code>, </code><var>xset</var><code> ) F</code>
<p>
computes the permutation that corresponds to the action of <var>g</var> on the
permutation domain <var>Omega</var> (a list of objects that are permuted). If an
external set <var>xset</var> is given, the permutation domain is the <code>HomeEnumerator</code>
of this external set (see Section <a href="CHAP039.htm#SECT011">External Sets</a>).
Note that the points of the returned permutation refer to the positions
in <var>Omega</var>, even if <var>Omega</var> itself consists of integers.
<p>
If <var>g</var> does not leave the domain invariant, or does not map the domain
injectively <code>fail</code> is returned.
<p>
<a name = "SSEC008.2"></a>
<li><code>PermutationCycle( </code><var>g</var><code>, </code><var>Omega</var><code>, </code><var>pnt</var><code> [, </code><var>act</var><code>] ) F</code>
<a name = "SSEC008.2"></a>
<li><code>PermutationCycleOp( </code><var>g</var><code>, </code><var>Omega</var><code>, </code><var>pnt</var><code>, </code><var>act</var><code> ) O</code>
<p>
computes the permutation that represents the cycle of <var>pnt</var> under the
action of the element <var>g</var>.
<p>
<pre>
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)
</pre>
<a name = "SSEC008.3"></a>
<li><code>Cycle( </code><var>g</var><code>, </code><var>Omega</var><code>, </code><var>pnt</var><code> [, </code><var>act</var><code>] ) O</code>
<p>
returns a list of the points in the cycle of <var>pnt</var> under the action of the
element <var>g</var>.
<p>
<a name = "SSEC008.4"></a>
<li><code>CycleLength( </code><var>g</var><code>, </code><var>Omega</var><code>, </code><var>pnt</var><code> [, </code><var>act</var><code>] ) O</code>
<p>
returns the length of the cycle of <var>pnt</var> under the action of the element
<var>g</var>.
<p>
<a name = "SSEC008.5"></a>
<li><code>Cycles( </code><var>g</var><code>, </code><var>Omega</var><code> [, </code><var>act</var><code>] ) O</code>
<p>
returns a list of the cycles (as lists of points) of the action of the
element <var>g</var>.
<p>
<a name = "SSEC008.6"></a>
<li><code>CycleLengths( </code><var>g</var><code>, </code><var>Omega</var><code>, [, </code><var>act</var><code>] ) O</code>
<p>
returns the lengths of all the cycles under the action of the element
<var>g</var> on <var>Omega</var>.
<p>
<pre>
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 ]
</pre>
<p>
<p>
<h2><a name="SECT009">39.9 Tests for Actions</a></h2>
<p><p>
<a name = "SSEC009.1"></a>
<li><code>IsTransitive( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>IsTransitive( </code><var>xset</var><code> ) P</code>
<p>
returns <code>true</code> if the action implied by the arguments is transitive, or
<code>false</code> otherwise.
<p>
<a name = "I15"></a>
We say that a group <var>G</var> acts <strong>transitively</strong> on a domain <var>D</var> if and
only if for every pair of points <var>d</var> and <var>e</var> there is an element
<var>g</var> of <var>G</var> such that <i>d</i><sup><i>g</i></sup> = <i>e</i>.
<p>
<a name = "SSEC009.2"></a>
<li><code>Transitivity( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>Transitivity( </code><var>xset</var><code> ) A</code>
<p>
returns the degree <i>k</i> (a non-negative integer) of transitivity of the
action implied by the arguments, i.e. the largest integer <i>k</i> such that
the action is <i>k</i>-transitive. If the action is not transitive <code>0</code> is
returned.
<p>
An action is <strong><i>k</i>-transitive</strong> if every <i>k</i>-tuple of points can be
mapped simultaneously to every other <i>k</i>-tuple.
<p>
<pre>
gap> g:=Group((1,3,2),(2,4,3));;
gap> IsTransitive(g,[1..5]);
false
gap> Transitivity(g,[1..4]);
2
</pre>
<p>
<strong>Note:</strong> For permutation groups, the syntax <code>IsTransitive(</code><var>g</var><code>)</code> is also
permitted and tests whether the group is transitive on the points moved by
it, that is the group 〈(2,3,4),(2,3)〉 is transitive (on 3
points).
<p>
<a name = "SSEC009.3"></a>
<li><code>RankAction( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>RankAction( </code><var>xset</var><code> ) A</code>
<p>
returns the rank of a transitive action, i.e. the number of orbits of
the point stabilizer.
<p>
<pre>
gap> RankAction(g,Combinations([1..4],2),OnSets);
4
</pre>
<a name = "SSEC009.4"></a>
<li><code>IsSemiRegular( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>IsSemiRegular( </code><var>xset</var><code> ) P</code>
<p>
returns <code>true</code> if the action implied by the arguments is semiregular, or
<code>false</code> otherwise.
<p>
<a name = "I16"></a>
An action is <strong>semiregular</strong> is the stabilizer of each point is the
identity.
<p>
<a name = "SSEC009.5"></a>
<li><code>IsRegular( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>IsRegular( </code><var>xset</var><code> ) P</code>
<p>
returns <code>true</code> if the action implied by the arguments is regular, or
<code>false</code> otherwise.
<p>
<a name = "I17"></a>
An action is <strong>regular</strong> if it is both semiregular (see <a href="CHAP039.htm#SSEC009.4">IsSemiRegular</a>)
and transitive (see <a href="CHAP039.htm#SSEC009.1">IsTransitive!for group actions</a>). In this case every
point <var>pnt</var> of <var>Omega</var> defines a one-to-one correspondence between <var>G</var>
and <var>Omega</var>.
<p>
<pre>
gap> IsSemiRegular(g,Arrangements([1..4],3),OnTuples);
true
gap> IsRegular(g,Arrangements([1..4],3),OnTuples);
false
</pre>
<a name = "SSEC009.6"></a>
<li><code>Earns( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>Earns( </code><var>xset</var><code> ) A</code>
<p>
returns a list of the elementary abelian regular (when acting on <var>Omega</var>)
normal subgroups of <var>G</var>.
<p>
At the moment only methods for a primitive group <var>G</var> are implemented.
<p>
<a name = "SSEC009.7"></a>
<li><code>IsPrimitive( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>IsPrimitive( </code><var>xset</var><code> ) P</code>
<p>
returns <code>true</code> if the action implied by the arguments is primitive, or
<code>false</code> otherwise.
<p>
<a name = "I18"></a>
An action is <strong>primitive</strong> if it is transitive and the action admits no
nontrivial block systems. See <a href="CHAP039.htm#SECT010">Block Systems</a>.
<p>
<pre>
gap> IsPrimitive(g,Orbit(g,(1,2)(3,4)));
true
</pre>
<p>
<p>
<h2><a name="SECT010">39.10 Block Systems</a></h2>
<p><p>
A <strong>block system</strong> (system of imprimitivity) for the action of <var>G</var> on <var>Omega</var>
is a partition of <var>Omega</var> which -- as a partition -- remains invariant under
the action of <var>G</var>.
<p>
<a name = "SSEC010.1"></a>
<li><code>Blocks( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>seed</var><code>][, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>Blocks( </code><var>xset</var><code>[, </code><var>seed</var><code>] ) A</code>
<p>
computes a block system for the action. If
<var>seed</var> is not given and the action is imprimitive, a minimal nontrivial
block system will be found.
If <var>seed</var> is given, a block system in which <var>seed</var>
is the subset of one block is computed.
The action must be transitive.
<p>
<pre>
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 ] ]
</pre>
(See Section <a href="CHAP039.htm#SECT002">Basic Actions</a> for information about specific actions.)
<p>
<a name = "SSEC010.2"></a>
<li><code>MaximalBlocks( </code><var>G</var><code>, </code><var>Omega</var><code> [, </code><var>seed</var><code>] [, </code><var>gens</var><code>, </code><var>acts</var><code>] [, </code><var>act</var><code>] ) O</code>
<li><code>MaximalBlocks( </code><var>xset</var><code> [, </code><var>seed</var><code>] ) A</code>
<p>
returns a block system that is maximal with respect to inclusion.
maximal with respect to inclusion) for the action of <var>G</var> on <var>Omega</var>.
If <var>seed</var> is given, a block system in which <var>seed</var>
is the subset of one block is computed.
<p>
<pre>
gap> MaximalBlocks(g,[1..8]);
[ [ 1, 2, 3, 8 ], [ 4, 5, 6, 7 ] ]
</pre>
<p>
<a name = "SSEC010.3"></a>
<li><code>RepresentativesMinimalBlocks( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>RepresentativesMinimalBlocks( </code><var>xset</var><code> ) A</code>
<p>
computes a list of block representatives for all minimal (i.e blocks are
minimal with respect to inclusion) nontrivial block systems for the
action.
<p>
<pre>
gap> RepresentativesMinimalBlocks(g,[1..8]);
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 1, 5 ], [ 1, 6 ], [ 1, 7 ], [ 1, 8 ] ]
</pre>
<p>
<a name = "SSEC010.4"></a>
<li><code>AllBlocks( </code><var>G</var><code> ) A</code>
<p>
computes a list of representatives of all block systems for a
permutation group <var>G</var> acting transitively on the points moved by the
group.
<p>
<pre>
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 ] ]
</pre>
<p>
The stabilizer of a block can be computed via the action
<code>OnSets</code> (see <a href="CHAP039.htm#SSEC002.4">OnSets</a>):
<pre>
gap> Stabilizer(g,[1,8],OnSets);
Group([ (1,8)(2,3)(4,5)(6,7) ])
</pre>
<p>
If <var>bs</var> is a partition of <var>omega</var>, given as a set of sets, the stabilizer
under the action <code>OnSetsDisjointSets</code> (see <a href="CHAP039.htm#SSEC002.8">OnSetsDisjointSets</a>) returns the
largest subgroup which preserves <var>bs</var> as a block system.
<pre>
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) ])
</pre>
<p>
<p>
<h2><a name="SECT011">39.11 External Sets</a></h2>
<p><p>
<a name = "I19"></a>
When considering group actions, sometimes the concept of a <strong><i>G</i>-set</strong> is
used. This is the set <var>Omega</var> endowed with an action of <i>G</i>. The elements
of the <i>G</i>-set are the same as those of <var>Omega</var>, however concepts like
equality and equivalence of <i>G</i>-sets do not only consider the underlying
domain <var>Omega</var> but the group action as well.
<p>
This concept is implemented in <font face="Gill Sans,Helvetica,Arial">GAP</font> via <strong>external sets</strong>.
<a name = "SSEC011.1"></a>
<li><code>IsExternalSet( </code><var>obj</var><code> ) C</code>
<p>
An <strong>external set</strong> specifies an action <var>act</var>: <i>Omega</i> ×<i>G</i> → <i>Omega</i> of a group <var>G</var> on a domain <var>Omega</var>. The external set knows the group,
the domain and the actual acting function.
Mathematically, an external set is the set <var>Omega</var>, which is endowed with
the action of a group <var>G</var> via the group action <var>act</var>. For this reason
<font face="Gill Sans,Helvetica,Arial">GAP</font> treats external sets as a domain whose elements are the elements
of <var>Omega</var>. An external set is always a union of orbits.
Currently the domain <var>Omega</var> must always be finite.
If <var>Omega</var> is not a list, an enumerator for <var>Omega</var> is automatically chosen.
<p>
<a name = "SSEC011.2"></a>
<li><code>ExternalSet( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<p>
creates the external set for the action <var>act</var> of <var>G</var> on <var>Omega</var>.
<var>Omega</var> can be either a proper set or a domain which is represented as
described in <a href="CHAP012.htm#SECT004">Domains</a> and <a href="CHAP028.htm">Collections</a>.
<p>
<pre>
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:<enumerator of perm group>>
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) ] ]
</pre>
<p>
The following three attributes of an external set hold its constituents.
<a name = "SSEC011.3"></a>
<li><code>ActingDomain( </code><var>xset</var><code> ) A</code>
<p>
This attribute returns the group with which the external set <var>xset</var> was
defined.
<p>
<a name = "SSEC011.4"></a>
<li><code>FunctionAction( </code><var>xset</var><code> ) A</code>
<p>
the acting function <var>act</var> of <var>xset</var>
<p>
<a name = "SSEC011.5"></a>
<li><code>HomeEnumerator( </code><var>xset</var><code> ) A</code>
<p>
returns an enumerator of the domain <var>Omega</var> with which <var>xset</var> was defined.
For external subsets, this is different from <code>Enumerator( </code><var>xset</var><code> )</code>,
which enumerates only the subset.
<p>
<pre>
gap> ActingDomain(e);
Group([ (1,2,3), (2,3,4) ])
gap> FunctionAction(e)=OnRight;
true
gap> HomeEnumerator(e);
<enumerator of perm group>
</pre>
<p>
Most operations for actions are applicable as an attribute for an external
set.
<p>
<a name = "SSEC011.6"></a>
<li><code>IsExternalSubset( </code><var>obj</var><code> ) R</code>
<p>
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.
<p>
The most prominent external subsets are orbits:
<a name = "SSEC011.7"></a>
<li><code>ExternalSubset( </code><var>G</var><code>, </code><var>xset</var><code>, </code><var>start</var><code>, [</code><var>gens</var><code>, </code><var>acts</var><code>, ]</code><var>act</var><code> ) O</code>
<p>
constructs the external subset of <var>xset</var> on the union of orbits of the
points in <var>start</var>.
<p>
<a name = "SSEC011.8"></a>
<li><code>IsExternalOrbit( </code><var>obj</var><code> ) R</code>
<p>
An external orbit is an external subset consisting of one orbit.
<p>
<a name = "SSEC011.9"></a>
<li><code>ExternalOrbit( </code><var>G</var><code>, </code><var>Omega</var><code>, </code><var>pnt</var><code>, [</code><var>gens</var><code>, </code><var>acts</var><code>, ] </code><var>act</var><code> ) O</code>
<p>
constructs the external subset on the orbit of <var>pnt</var>. The
<code>Representative</code> of this external set is <var>pnt</var>.
<p>
<pre>
gap> e:=ExternalOrbit(g,g,(1,2,3));
(1,2,3)^G
</pre>
<p>
Many subsets of a group, such as conjugacy classes or cosets
(see <a href="CHAP037.htm#SSEC010.1">ConjugacyClass</a> and <a href="CHAP037.htm#SSEC007.1">RightCoset</a>) are implemented as external orbits.
<p>
<a name = "SSEC011.10"></a>
<li><code>StabilizerOfExternalSet( </code><var>xset</var><code> ) A</code>
<p>
computes the stabilizer of <code>Representative(</code><var>xset</var><code>)</code>
The stabilizer must have the acting group <var>G</var> of <var>xset</var> as its parent.
<p>
<pre>
gap> Representative(e);
(1,2,3)
gap> StabilizerOfExternalSet(e);
Group([ (1,2,3) ])
</pre>
<p>
<a name = "SSEC011.11"></a>
<li><code>ExternalOrbits( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>ExternalOrbits( </code><var>xset</var><code> ) A</code>
<p>
computes a list of <code>ExternalOrbit</code>s that give the orbits of <var>G</var>.
<p>
<pre>
gap> ExternalOrbits(g,AsList(g));
[ ()^G, (2,3,4)^G, (2,4,3)^G, (1,2)(3,4)^G ]
</pre>
<p>
<a name = "SSEC011.12"></a>
<li><code>ExternalOrbitsStabilizers( </code><var>G</var><code>, </code><var>Omega</var><code>[, </code><var>gens</var><code>, </code><var>acts</var><code>][, </code><var>act</var><code>] ) O</code>
<li><code>ExternalOrbitsStabilizers( </code><var>xset</var><code> ) A</code>
<p>
In addition to <code>ExternalOrbits</code>, this operation also computes the
stabilizers of the representatives of the external orbits at the same
time. (This can be quicker than computing the <code>ExternalOrbits</code> first and
the stabilizers afterwards.)
<p>
<pre>
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) ])
</pre>
<p>
<a name = "SSEC011.13"></a>
<li><code>CanonicalRepresentativeOfExternalSet( </code><var>xset</var><code> ) A</code>
<p>
The canonical representative of an external set may only depend on <var>G</var>,
<var>Omega</var>, <var>act</var> and (in the case of external subsets) <code>Enumerator( </code><var>xset</var><code> )</code>.
It must not depend, e.g., on the representative of an external orbit.
<font face="Gill Sans,Helvetica,Arial">GAP</font> does not know methods for every external set to compute a
canonical representative . See
<a href="CHAP039.htm#SSEC011.14">CanonicalRepresentativeDeterminatorOfExternalSet</a>.
<p>
<a name = "SSEC011.14"></a>
<li><code>CanonicalRepresentativeDeterminatorOfExternalSet( </code><var>xset</var><code> ) A</code>
<p>
returns a function that
takes as arguments the acting group and the point. It returns a list
of length 3: [<var>canonrep</var>, <var>stabilizercanonrep</var>, <var>conjugatingelm</var>].
(List components 2 and 3 are optional and do not need to be bound.)
An external set is only guaranteed to be able to compute a canonical
representative if it has a
<code>CanonicalRepresentativeDeterminatorOfExternalSet</code>.
<p>
<a name = "SSEC011.15"></a>
<li><code>ActorOfExternalSet( </code><var>xset</var><code> ) A</code>
<p>
returns an element mapping <code>Representative(</code><var>xset</var><code>)</code> to
<code>CanonicalRepresentativeOfExternalSet(</code><var>xset</var><code>)</code> under the given
action.
<p>
<pre>
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)
</pre>
<p>
External sets also are implicitly underlying action homomorphisms:
<p>
<a name = "SSEC011.16"></a>
<li><code>UnderlyingExternalSet( </code><var>ohom</var><code> ) A</code>
<p>
The underlying set of an action homomorphism is the external set on
which it was defined.
<p>
<pre>
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 ] ]
</pre>
<p>
<a name = "SSEC011.17"></a>
<li><code>SurjectiveActionHomomorphismAttr( </code><var>xset</var><code> ) A</code>
<p>
returns an action homomorphism for <var>xset</var> which is surjective.
(As the <code>Image</code> of this homomorphism has to be computed to obtain the
range, this may take substantially longer
than <code>ActionHomomorphism</code>.)
<p>
<p>
[<a href="../index.htm">Top</a>] [<a href = "chapters.htm">Up</a>] [<a href ="CHAP038.htm">Previous</a>] [<a href ="CHAP040.htm">Next</a>] [<a href = "theindex.htm">Index</a>]
<P>
<font face="Gill Sans,Helvetica,Arial">GAP 4 manual<br>December 2008
</font></body></html>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
5e1854624d3bc613bdd0dd13d1ef9ac7
>
files
>
181
