<p>A <em>group action</em> is a triple <span class="SimpleMath">(G, Ω, μ)</span>, where <span class="SimpleMath">G</span> is a group, <span class="SimpleMath">Ω</span> a set and <span class="SimpleMath">μ : Ω × G → Ω</span> a function that is compatible with the group arithmetic. We call <span class="SimpleMath">Ω</span> the <em>domain</em> of the action.</p>
<p>In <strong class="pkg">GAP</strong>, <span class="SimpleMath">Ω</span> can be a duplicate-free collection (an object that permits access to its elements via the <span class="SimpleMath">Ω[n]</span> operation, for example a list), it does not need to be sorted (see <code class="func">IsSet</code> (<a href="chap21.html#X80CDAF45782E8DCB"><span class="RefLink">21.17-4</span></a>)).</p>
<p>The acting function <span class="SimpleMath">μ</span> is a binary <strong class="pkg">GAP</strong> function that returns the image <span class="SimpleMath">μ( x, g )</span> for a point <span class="SimpleMath">x ∈ Ω</span> and a group element <span class="SimpleMath">g ∈ G</span>.</p>
<p>In <strong class="pkg">GAP</strong>, groups always act from the right, that is <span class="SimpleMath">μ( μ( x, g ), h ) = μ( x, gh )</span>.</p>
<p><strong class="pkg">GAP</strong> does not test whether the acting function <span class="SimpleMath">μ</span> satisfies the conditions for a group operation but silently assumes that is does. (If it does not, results are unpredictable.)</p>
<p>The first section of this chapter, <a href="chap41.html#X83661AFD7B7BD1D9"><span class="RefLink">41.1</span></a>, describes the various ways how operations for group actions can be called.</p>
<p>Functions for several commonly used action are already built into <strong class="pkg">GAP</strong>. These are listed in section <a href="chap41.html#X81B8F9CD868CD953"><span class="RefLink">41.2</span></a>.</p>
<p>The sections <a href="chap41.html#X87F73CCA7921DE65"><span class="RefLink">41.7</span></a> and <a href="chap41.html#X7FED50ED7ACA5FB2"><span class="RefLink">41.8</span></a> describe homomorphisms and mappings associated to group actions as well as the permutation group image of an action.</p>
<p>The other sections then describe operations to compute orbits, stabilizers, as well as properties of actions.</p>
<p>Finally section <a href="chap41.html#X7FD3D2D2788709B7"><span class="RefLink">41.12</span></a> describes the concept of <q>external sets</q> which represent the concept of a <em><span class="SimpleMath">G</span>-set</em> and underly the actions mechanism.</p>
<h4>41.1 <span class="Heading">About Group Actions</span></h4>
<p>The syntax which is used by the operations for group actions is quite flexible. For example we can call the operation <code class="func">OrbitsDomain</code> (<a href="chap41.html#X86BC8B958123F953"><span class="RefLink">41.4-3</span></a>) for the orbits of the group <var class="Arg">G</var> on the domain <var class="Arg">Omega</var> in the following ways:</p>
<dl>
<dt><strong class="Mark"><code class="code">OrbitsDomain</code><span class="SimpleMath">( G, Ω[, μ] )</span></strong></dt>
<dd><p>The acting function <span class="SimpleMath">μ</span> is optional. If it is not given, the built-in action <code class="func">OnPoints</code> (<a href="chap41.html#X7FE417DD837987B4"><spanclass="RefLink">41.2-1</span></a>) (which defines an action via the caret operator <code class="code">^</code>) is used as a default.</p>
</dd>
<dt><strong class="Mark"><code class="code">OrbitsDomain</code><span class="SimpleMath">( G, Ω, gens, acts[, μ] )</span></strong></dt>
<dd><p>This second version of <code class="func">OrbitsDomain</code> (<a href="chap41.html#X86BC8B958123F953"><span class="RefLink">41.4-3</span></a>) permits one to implement an action induced by a homomorphism: If the group <span class="SimpleMath">H</span> acts on <span class="SimpleMath">Ω</span> via <span class="SimpleMath">μ</span> and <span class="SimpleMath">φ : G → H</span> is a homomorphism, <span class="SimpleMath">G</span> acts on <span class="SimpleMath">Ω</span> via the induced action <span class="SimpleMath">μ'( x, g ) = μ( x, g^φ ).
<p>Here <span class="SimpleMath">gens</span> must be a set of generators of <span class="SimpleMath">G</span> and <span class="SimpleMath">acts</span> the images of <span class="SimpleMath">gens</span> under <span class="SimpleMath">φ</span>. <span class="SimpleMath">μ</span> is the acting function for <span class="SimpleMath">H</span>. Again, the function <span class="SimpleMath">μ</span> is optional and <code class="func">OnPoints</code> (<a href="chap41.html#X7FE417DD837987B4"><span class="RefLink">41.2-1</span></a>) is used as a default.</p>
<p>The advantage of this notation is that <strong class="pkg">GAP</strong> does not need to construct this homomorphism <span class="SimpleMath">φ</span> and the range group <var class="Arg">H</var> as <strong class="pkg">GAP</strong> objects. (If a small group <span class="SimpleMath">G</span> acts via complicated objects <span class="SimpleMath">acts</span> this otherwise could lead to performance problems.)</p>
<p><strong class="pkg">GAP</strong> does not test whether the mapping <span class="SimpleMath">gens ↦ acts</span> actually induces a homomorphism and the results are unpredictable if this is not the case.</p>
</dd>
<dt><strong class="Mark"><code class="code">OrbitsDomain</code><span class="SimpleMath">( xset )</span></strong></dt>
<dd><p>A third variant is to call the operation with an external set, which then provides <span class="SimpleMath">G</span>, <span class="SimpleMath">Ω</span> and <span class="SimpleMath">μ</span>. You will find more about external sets in Section <a href="chap41.html#X7FD3D2D2788709B7"><span class="RefLink">41.12</span></a>.</p>
</dd>
</dl>
<p>For operations like <code class="func">Stabilizer</code> (<a href="chap41.html#X86FB962786397E02"><span class="RefLink">41.5-2</span></a>) of course the domain must be replaced by an element of the domain of the action.</p>
<p><strong class="pkg">GAP</strong> already provides acting functions for the more common actions of a group. For built-in operations such as <code class="func">Stabilizer</code> (<a href="chap41.html#X86FB962786397E02"><span class="RefLink">41.5-2</span></a>) special methods are available for many of these actions.</p>
<p>If one needs an action for which no acting function is provided by the library it can be implemented via a <strong class="pkg">GAP</strong> function that conforms to the syntax</p>
<p><code class="code">actfun( omega, g )</code></p>
<p>where <code class="code">omega</code> is an element of the action domain, <code class="code">g</code> is an element of the acting group, and the return value is the image of <code class="code">omega</code> under <code class="code">g</code>.</p>
<p>For example one could define the following function that acts on pairs of polynomials via <codeclass="func">OnIndeterminates</code> (<a href="chap41.html#X7FA394D27E721E2B"><span class="RefLink">41.2-13</span></a>):</p>
<div class="example"><pre>
OnIndeterminatesPairs:= function( polypair, g )
return [ OnIndeterminates( polypair[1], g ),
OnIndeterminates( polypair[2], g ) ];
end;
</pre></div>
<p>Note that this function <em>must</em> implement a group action from the <em>right</em>. This is not verified by <strong class="pkg">GAP</strong> and results are unpredictable otherwise.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnPoints</code>( <var class="Arg">pnt</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns <code class="code"><var class="Arg">pnt</var> ^ <var class="Arg">g</var></code>. 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 <var class="Arg">pnt</var> and <var class="Arg">g</var> are elements from a common group then <code class="code"><var class="Arg">pnt</var> ^ <var class="Arg">g</var></code> is equal to <var class="Arg">g</var><span class="SimpleMath">^{-1}</span><code class="code">*</code><var class="Arg">pnt</var><code class="code">*</code><var class="Arg">g</var>. The action of a matrix group on vectors from the right is described by both <code class="func">OnPoints</code> and <code class="func">OnRight</code> (<a href="chap41.html#X7960924D84B5B18F"><span class="RefLink">41.2-2</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnRight</code>( <var class="Arg">pnt</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns <code class="code"><var class="Arg">pnt</var> * <var class="Arg">g</var></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 class="func">OnPoints</code> (<a href="chap41.html#X7FE417DD837987B4"><span class="RefLink">41.2-1</span></a>) and <code class="func">OnRight</code>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnLeftInverse</code>( <var class="Arg">pnt</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>returns <span class="SimpleMath"><var class="Arg">g</var>^{-1}</span> <code class="code">* <var class="Arg">pnt</var></code>. Forming the inverse is necessary to make this a proper action, as in <strong class="pkg">GAP</strong> groups always act from the right.</p>
<p><code class="func">OnLeftInverse</code> is used for example in the representation of a right coset as an external set (see <a href="chap41.html#X7FD3D2D2788709B7"><span class="RefLink">41.12</span></a>), that is, a right coset <span class="SimpleMath">Ug</span> is an external set for the group <span class="SimpleMath">U</span> acting on it via <code class="func">OnLeftInverse</code>.)</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnSets</code>( <var class="Arg">set</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <var class="Arg">set</var> be a proper set (see <a href="chap21.html#X80ABC25582343910"><span class="RefLink">21.19</span></a>). <code class="func">OnSets</code> returns the proper set formed by the images of all points <span class="SimpleMath">x</span> of <var class="Arg">set</var> via the action function <code class="func">OnPoints</code> (<a href="chap41.html#X7FE417DD837987B4"><span class="RefLink">41.2-1</span></a>), applied to <span class="SimpleMath">x</span> and <var class="Arg">g</var>.</p>
<p><code class="func">OnSets</code> is for example used to compute the action of a permutation group on blocks.</p>
<p>(<code class="func">OnTuples</code> (<a href="chap41.html#X832CC5F87EEA4A7E"><span class="RefLink">41.2-5</span></a>) is an action on lists that preserves the ordering of entries.)</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnTuples</code>( <var class="Arg">tup</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <var class="Arg">tup</var> be a list. <code class="func">OnTuples</code> returns the list formed by the images of all points <span class="SimpleMath">x</span> of <var class="Arg">tup</var> via the action function <code class="func">OnPoints</code> (<a href="chap41.html#X7FE417DD837987B4"><span class="RefLink">41.2-1</span></a>), applied to <span class="SimpleMath">x</span> and <var class="Arg">g</var>.</p>
<p>(<code class="func">OnSets</code> (<a href="chap41.html#X85AA04347CD117F9"><span class="RefLink">41.2-4</span></a>) is an action on lists that additionally sorts the entries of the result.)</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnPairs</code>( <var class="Arg">tup</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>is a special case of <code class="func">OnTuples</code> (<a href="chap41.html#X832CC5F87EEA4A7E"><span class="RefLink">41.2-5</span></a>) for lists <var class="Arg">tup</var> of length 2.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnSetsSets</code>( <var class="Arg">set</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>implements the action on sets of sets. For the special case that the sets are pairwise disjoint, it is possible to use <code class="func">OnSetsDisjointSets</code> (<a href="chap41.html#X7E23686E7A9D3A20"><span class="RefLink">41.2-8</span></a>). <var class="Arg">set</var> must be a sorted list whose entries are again sorted lists, otherwise an error is triggered (see <a href="chap41.html#X82181CA07A5B2056"><span class="RefLink">41.3</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnSetsDisjointSets</code>( <var class="Arg">set</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>implements the action on sets of pairwise disjoint sets (see also <code class="func">OnSetsSets</code> (<a href="chap41.html#X7C10492081D72376"><span class="RefLink">41.2-7</span></a>)). <var class="Arg">set</var> must be a sorted list whose entries are again sorted lists, otherwise an error is triggered (see <a href="chap41.html#X82181CA07A5B2056"><span class="RefLink">41.3</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnSetsTuples</code>( <var class="Arg">set</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>implements the action on sets of tuples. <var class="Arg">set</var> must be a sorted list, otherwise an error is triggered (see <a href="chap41.html#X82181CA07A5B2056"><span class="RefLink">41.3</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnTuplesSets</code>( <var class="Arg">set</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>implements the action on tuples of sets. <var class="Arg">set</var> must be a list whose entries are again sorted lists, otherwise an error is triggered (see <a href="chap41.html#X82181CA07A5B2056"><span class="RefLink">41.3</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnLines</code>( <var class="Arg">vec</var>, <var class="Arg">g</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>Let <var class="Arg">vec</var> be a <em>normed</em> row vector, that is, its first nonzero entry is normed to the identity of the relevant field, see <code class="func">NormedRowVector</code> (<a href="chap23.html#X785DC60D8482695D"><span class="RefLink">23.2-1</span></a>). The function <codeclass="func">OnLines</code> returns the row vector obtained from first multiplying <var class="Arg">vec</var> from the right with <var class="Arg">g</var> (via <code class="func">OnRight</code> (<a href="chap41.html#X7960924D84B5B18F"><span class="RefLink">41.2-2</span></a>)) and then normalizing the resulting row vector by scalar multiplication from the left.</p>
<p>This action corresponds to the projective action of a matrix group on one-dimensional subspaces.</p>
<p>If <var class="Arg">vec</var> is a zero vector or is not normed then an error is triggered (see <a href="chap41.html#X82181CA07A5B2056"><span class="RefLink">41.3</span></a>).</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnIndeterminates</code>( <var class="Arg">poly</var>, <var class="Arg">perm</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>A permutation <var class="Arg">perm</var> acts on the multivariate polynomial <var class="Arg">poly</var> by permuting the indeterminates as it permutes points.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Permuted</code>( <var class="Arg">list</var>, <var class="Arg">perm</var> )</td><td class="tdright">( method )</td></tr></table></div>
<p>The following example demonstrates <code class="func">Permuted</code> (<a href="chap21.html#X7B5A19098406347A"><span class="RefLink">21.20-17</span></a>) being used to implement a permutation action on a domain:</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnSubspacesByCanonicalBasis</code>( <var class="Arg">bas</var>, <var class="Arg">mat</var> )</td><td class="tdright">( function )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OnSubspacesByCanonicalBasisConcatenations</code>( <var class="Arg">basvec</var>, <var class="Arg">mat</var> )</td><td class="tdright">( function )</td></tr></table></div>
<p>implements the operation of a matrix group on subspaces of a vector space. <var class="Arg">bas</var> must be a list of (linearly independent) vectors which forms a basis of the subspace in Hermite normal form. <var class="Arg">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 class="Arg">bas</var> with <var class="Arg">mat</var>.)</p>
<p><var class="Arg">bas</var> must be given in Hermite normal form, otherwise an error is triggered (see <a href="chap41.html#X82181CA07A5B2056"><span class="RefLink">41.3</span></a>).</p>
<h4>41.3 <span class="Heading">Action on canonical representatives</span></h4>
<p>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 <code class="func">OnSetsSets</code> (<a href="chap41.html#X7C10492081D72376"><span class="RefLink">41.2-7</span></a>), <code class="func">OnSetsDisjointSets</code> (<a href="chap41.html#X7E23686E7A9D3A20"><span class="RefLink">41.2-8</span></a>), <code class="func">OnSetsTuples</code> (<a href="chap41.html#X7ADE244E819035FF"><span class="RefLink">41.2-9</span></a>), <code class="func">OnTuplesSets</code> (<a href="chap41.html#X7FF556CD7E6739A9"><span class="RefLink">41.2-10</span></a>), <code class="func">OnLines</code> (<a href="chap41.html#X86DC2DD5829CAD9A"><span class="RefLink">41.2-12</span></a>) and <code class="func">OnSubspacesByCanonicalBasis</code> (<a href="chap41.html#X85124D197F0F9C4D"><span class="RefLink">41.2-15</span></a>).</p>
<p>If orbit seeds or domain elements are not given in the required form <strong class="pkg">GAP</strong> will issue an error message:</p>
<div class="example"><pre>
<span class="GAPprompt">gap></span> <span class="GAPinput">Orbit(SymmetricGroup(5),[[2,4],[1,3]],OnSetsSets);</span>
Error, Action not well-defined. See the manual section
``Action on canonical representatives''.
</pre></div>
<p>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.</p>
<p>(A similar error could arise if a user-defined action function is used which actually does not implement an action from the right.)</p>
<p>If a group <span class="SimpleMath">G</span> acts on a set <span class="SimpleMath">Ω</span>, the set of all images of <span class="SimpleMath">x ∈ Ω</span> under elements of <span class="SimpleMath">G</span> is called the <em>orbit</em> of <span class="SimpleMath">x</span>. The set of orbits of <span class="SimpleMath">G</span> is a partition of <span class="SimpleMath">Ω</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Orbit</code>( <var class="Arg">G</var>[, <var class="Arg">Omega</var>], <var class="Arg">pnt</var>[, <varclass="Arg">gens</var>, <var class="Arg">acts</var>][, <var class="Arg">act</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>The orbit of the point <var class="Arg">pnt</var> is the list of all images of <var class="Arg">pnt</var> under the action of the group <var class="Arg">G</var> w.r.t. the action function <var class="Arg">act</var> or <code class="func">OnPoints</code> (<a href="chap41.html#X7FE417DD837987B4"><span class="RefLink">41.2-1</span></a>) if no action function is given.</p>
<p>(Note that the arrangement of points in this list is not defined by the operation.)</p>
<p>The orbit of <var class="Arg">pnt</var> will always contain one element that is <em>equal</em> to <varclass="Arg">pnt</var>, however for performance reasons this element is not necessarily <em>identical</em> to <var class="Arg">pnt</var>, in particular if <var class="Arg">pnt</var> is mutable.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Orbits</code>( <var class="Arg">G</var>, <var class="Arg">seeds</var>[, <var class="Arg">gens</var>, <varclass="Arg">acts</var>][, <var class="Arg">act</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Orbits</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Orbits</code>( <var class="Arg">xset</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns a duplicate-free list of the orbits of the elements in <var class="Arg">seeds</var> under the action <var class="Arg">act</var> of <var class="Arg">G</var> or under <code class="func">OnPoints</code> (<a href="chap41.html#X7FE417DD837987B4"><span class="RefLink">41.2-1</span></a>) if no action function is given.</p>
<p>For a permutation group <var class="Arg">G</var>, one may also invoke this as <code class="code">Orbits(<var class="Arg">G</var>)</code>, which returns all the orbits of its natural action on the set of points moved by it. For example the group <span class="SimpleMath">⟨ (1,2,3), (4,5) ⟩</span> has the orbits <span class="SimpleMath">{1,2,3}</span> and <span class="SimpleMath">{4,5}</span>.</p>
<p>(Note that the arrangement of orbits or of points within one orbit is not defined by the operation.)</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitsDomain</code>( <var class="Arg">G</var>, <var class="Arg">Omega</var>[, <var class="Arg">gens</var>, <var class="Arg">acts</var>][, <var class="Arg">act</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitsDomain</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitsDomain</code>( <var class="Arg">xset</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>returns a list of the orbits of <var class="Arg">G</var> on the domain <var class="Arg">Omega</var> (given as lists) under the action <var class="Arg">act</var> or under <code class="func">OnPoints</code> (<a href="chap41.html#X7FE417DD837987B4"><span class="RefLink">41.2-1</span></a>) if no action function is given.</p>
<p>This operation is often faster than <code class="func">Orbits</code> (<a href="chap41.html#X86BCAE17869BBEAA"><span class="RefLink">41.4-2</span></a>). The domain <var class="Arg">Omega</var> must be closed under the action of <var class="Arg">G</var>, otherwise an error can occur.</p>
<p>For a permutation group <var class="Arg">G</var>, one may also invoke this as <code class="code">OrbitsDomain(<var class="Arg">G</var>)</code>, which returns all the orbits of its natural action on the set of points moved by it.</p>
<p>(Note that the arrangement of orbits or of points within one orbit is not defined by the operation.)</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitLength</code>( <var class="Arg">G</var>[, <var class="Arg">Omega</var>], <var class="Arg">pnt</var>[, <var class="Arg">gens</var>, <var class="Arg">acts</var>][, <var class="Arg">act</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<p>computes the length of the orbit of <var class="Arg">pnt</var> under the action function <var class="Arg">act</var> or <code class="func">OnPoints</code> (<a href="chap41.html#X7FE417DD837987B4"><span class="RefLink">41.2-1</span></a>) if no action function is given.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitLengths</code>( <var class="Arg">G</var>, <var class="Arg">seeds</var>[, <var class="Arg">gens</var>, <var class="Arg">acts</var>][, <var class="Arg">act</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitLengths</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitLengths</code>( <var class="Arg">xset</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>computes the lengths of all the orbits of the elements in <var class="Arg">seeds</var> under the action <var class="Arg">act</var> of <var class="Arg">G</var>.</p>
<p>For a permutation group <var class="Arg">G</var>, one may also invoke this as <code class="code">OrbitLengths(<var class="Arg">G</var>)</code>, which returns the lengths of all the orbits of its natural action on the set of points moved by it. For example the group <span class="SimpleMath">⟨ (1,2,3), (5,6) ⟩</span> has the orbit lengths 2 and 3.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitLengthsDomain</code>( <var class="Arg">G</var>, <var class="Arg">Omega</var>[, <var class="Arg">gens</var>, <var class="Arg">acts</var>][, <var class="Arg">act</var>] )</td><td class="tdright">( operation )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitLengthsDomain</code>( <var class="Arg">G</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitLengthsDomain</code>( <var class="Arg">xset</var> )</td><td class="tdright">( attribute )</td></tr></table></div>
<p>computes the lengths of all the orbits of <var class="Arg">G</var> on <var class="Arg">Omega</var>.</p>
<p>This operation is often faster than <code class="func">OrbitLengths</code> (<a href="chap41.html#X8032F73078DF2DDB"><span class="RefLink">41.4-5</span></a>). The domain <var class="Arg">Omega</var> must be closed under the action of <var class="Arg">G</var>, otherwise an error can occur.</p>
<p>For a permutation group <var class="Arg">G</var>, one may also invoke this as <code class="code">OrbitLengthsDomain(<var class="Arg">G</var>)</code>, which returns the length of all the orbits of its natural action on the set of points moved by it.</p>
<p>The <em>stabilizer</em> of a point <span class="SimpleMath">x</span> under the action of a group <span class="SimpleMath">G</span> is the set of all those elements in <span class="SimpleMath">G</span> which fix <span class="SimpleMath">x</span>.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ Stabilizer</code>( <var class="Arg">G</var>[, <var class="Arg">Omega</var>], <var class="Arg">pnt</var>[, <var class="Arg">gens</var>, <var class="Arg">acts</var>][, <var class="Arg">act</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>computes the stabilizer in <var class="Arg">G</var> of the point <var class="Arg">pnt</var>, that is the subgroup of those elements of <var class="Arg">G</var> that fix <var class="Arg">pnt</var>. The stabilizer will have <var class="Arg">G</var> as its parent.</p>
<p>(See Section <a href="chap41.html#X81B8F9CD868CD953"><span class="RefLink">41.2</span></a> for information about specific actions.)</p>
<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="chapBib.html#biBSOGOS">[LNS84]</a>) is used.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ OrbitStabilizerAlgorithm</code>( <var class="Arg">G</var>, <var class="Arg">Omega</var>, <var class="Arg">blist</var>, <var class="Arg">gens</var>, <var class="Arg">acts</var>, <var class="Arg">pntact</var> )</td><td class="tdright">( operation )</td></tr></table></div>
<p>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 <q>package</q> here refers to the <strong class="pkg">GAP</strong> functionality for group actions, not to a <strong class="pkg">GAP</strong> package).</p>
<p><code class="func">OrbitStabilizerAlgorithm</code> performs an orbit stabilizer algorithm for the group <var class="Arg">G</var> acting with the generators <var class="Arg">gens</var> via the generator images <var class="Arg">gens</var> and the group action <var class="Arg">act</var> on the element <var class="Arg">pnt</var>. (For technical reasons <var class="Arg">pnt</var> and <var class="Arg">act</var> are put in one record with components <code class="code">pnt</code> and <code class="code">act</code> respectively.)</p>
<p>The <var class="Arg">pntact</var> record may carry a component <var class="Arg">stabsub</var>. If given, this must be a subgroup stabilizing <em>all</em> points in the domain and can be used to abbreviate stabilizer calculations.</p>
<p>The <var class="Arg">pntact</var> component also may contain the boolean entry <code class="code">onlystab</code> set to <code class="keyw">true</code>. In this case the <code class="code">orbit</code> component may be omitted from the result.</p>
<p>The argument <var class="Arg">Omega</var> (which may be replaced by <code class="keyw">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 class="Arg">blist</var> is given it must be a bit list corresponding to <var class="Arg">Omega</var> in which elements which have been found already will be <q>ticked off</q> with <code class="keyw">true</code>. (In particular, the entries for the orbit of <var class="Arg">pnt</var> still must be all set to <code class="keyw">false</code>). Again the remaining action domain (the bits set initially to <code class="keyw">false</code>) can be used to stop if the orbit cannot grow any longer. Another use of the bit list is if <var class="Arg">Omega</var> is an enumerator which can determine <code class="func">PositionCanonical</code> (<a href="chap21.html#X7B4B10AE81602D4E"><span class="RefLink">21.16-3</span></a>) 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 <var class="Arg">Omega</var> and use a the bit list to keep track whether the element is in the orbit found so far.</p>
<div class="func"><table class="func" width="100%"><tr><td class="tdleft"><code class="func">‣ RepresentativeAction</code>( <var class="Arg">G</var>[, <var class="Arg">Omega</var>], <var class="Arg">d</var>, <var class="Arg">e</var>[, <var class="Arg">gens</var>, <var class="Arg">acts</var>][, <varclass="Arg">act</var>] )</td><td class="tdright">( function )</td></tr></table></div>
<p>computes an element of <var class="Arg">G</var> that maps <var class="Arg">d</var> to <var class="Arg">e</var> under the given action and returns <code class="keyw">fail</code> if no such element exists.</p>
<p>(See Section <a href="chap41.html#X81B8F9CD868CD953"><span class="RefLink">41.2</span></a> for information about specific actions.)</p>
<p>Again the standard method for <code class="func">RepresentativeAction</code> is an orbit-stabilizer algorithm, for permutation groups and standard actions a backtrack algorithm is used.</p>
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
