<!-- basic.xml orb package documentation Juergen Mueller Max Neunhoeffer Felix Noeske Copyright (C) 2005-2008 by the authors This chapter explains functionality for basic orbit enumerations. --> <Chapter Label="basic"> <Heading>Basic orbit enumeration</Heading> This package contains a new implementation of the standard orbit enumeration algorithm. The design principles for this implementation have been: <List> <Item>Allow partial orbit enumeration and later continuation. </Item> <Item>Consequently use hashing techniques.</Item> <Item>Implement stabiliser calculation and Schreier transversals on demand.</Item> <Item>Allow for searching in orbits during orbit enumeration.</Item> </List> Some of these design principles made it necessary to change the user interface in comparison to the standard &GAP; one. <Section> <Heading>Enumerating orbits</Heading> The enumeration of an orbit works in at least two stages: First an orbit object is created with all the necessary information to describe the orbit. Then the actual enumeration is started. The latter stage can be repeated as many times as needed in the case that the orbit enumeration stopped for some reason before the orbit was enumerated completely. See below for conditions under which this happens. <P/> For orbit object creation there is the following function: <ManSection> <Func Name="Orb" Arg="gens, point, op [, opt]" /> <Returns> An orbit object </Returns> <Description> The argument <A>gens</A> is either a &GAP; group object or a list of generators of the group acting, <A>point</A> is a point in the orbit to be enumerated, <A>op</A> is a &GAP; function describing the action of the generators on points in the usual way, that is, <C><A>op</A>(p,g)</C> returns the result of the action of the element <C>g</C> on the point <C>p</C>. <P/> The optional argument <A>opt</A> is a &GAP; record which can contain quite a few options changing the orbit enumeration. For a list of possible options see Subsection <Ref Subsect="orboptions"/> at the end of this section. <P/> The function returns an <Q>orbit</Q> object that can later be used to enumerate (a part of) the orbit of <A>point</A> under the action of the group generated by <A>gens</A>. <P/> If <A>gens</A> is a group object, then its generators are taken as the list of generators acting. If the group object knows its size, then this size is used to speed up orbit and in particular stabiliser computations. </Description> </ManSection> The following operation actually starts the orbit enumeration: <ManSection> <Oper Name="Enumerate" Arg="orb [,limit]" /> <Returns> The orbit object <A>orb</A> </Returns> <Description> <A>orb</A> must be an orbit object created by <Ref Func="Orb"/>. The optional argument <A>limit</A> must be a positive integer meaning that the orbit enumeration should stop if <A>limit</A> points have been found, regardless whether the orbit is complete or not. Note that the orbit enumeration can be continued by again calling the <Ref Oper="Enumerate"/> operation. If the argument <A>limit</A> is omitted, the whole orbit is enumerated, unless other options lead to prior termination. </Description> </ManSection> To see whether an orbit is closed you can use the following filter: <ManSection> <Filt Name="IsClosed" Arg="orb" /> <Returns> <K>true</K> or <K>false</K> </Returns> <Description> The result indicates, whether the orbit <A>orb</A> is already complete or not. </Description> </ManSection> Here is an example of an orbit enumeration: <Example><![CDATA[gap> g := GeneratorsOfGroup(MathieuGroup(24)); [ (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23), (3,17,10,7,9)(4,13,14,19,5)(8,18,11,12,23)(15,20,22,21,16), (1,24)(2,23)(3,12)(4,16)(5,18)(6,10)(7,20)(8,14)(9,21)(11,17) (13,22)(15,19) ] gap> o := Orb(g,2,OnPoints); <open Int-orbit, 1 points> gap> Enumerate(o,20); <open Int-orbit, 21 points> gap> IsClosed(o); false gap> Enumerate(o); <closed Int-orbit, 24 points> gap> IsClosed(o); true]]></Example> The orbit object <C>o</C> now behaves like an immutable dense list, the entries of which are the points in the orbit in the order as they were found during the orbit enumeration (note that this is not always true when one uses the function <Ref Oper="AddGeneratorsToOrbit"/>). So you can ask the orbit for its length, access entries, and ask, whether a given point lies in the orbit or not. Due to the hashing techniques used such lookups are quite fast, they usually only use a constant time regardless of the length of the orbit! <Example><![CDATA[gap> Length(o); 24 gap> o[1]; 2 gap> o[2]; 3 gap> o{[3..5]}; [ 23, 4, 17 ] gap> 17 in o; true gap> Position(o,17); 5]]></Example> <Subsection Label="orboptions"> <Heading>Options for orbits</Heading> The optional fourth argument <A>opt</A> of the function <Ref Func="Orb"/> is a &GAP; record and its components change the behaviour of the orbit enumeration. In this subsection we explain the use of the components of this options record. All components are themselves optional. For every component we also describe the possible values in the following list: <List> <Mark><C>eqfunc</C></Mark> <Item>This component always has to be given together with the component <C>hashfunc</C>. If both are given, they are used to set up a hash table to store the points in the orbit. You have to use this if the automatic mechanism to find a suitable hash function does not work for your starting point in the orbit.<P/> Note that if you use this feature, the hash table cannot grow automatically any more, unless you also use the components <C>hfbig</C> and <C>hfdbig</C> as well. See the description of <Ref Func="GrowHT"/> for an explanation how to use this feature. </Item> <Mark><C>genstoapply</C></Mark> <Item>This is only used internally and is intentionally not documented.</Item> <Mark><C>grpsizebound</C></Mark> <Item>Possible values for this component are positive integers. By setting this value one can help the orbit enumeration to complete earlier. The given number must be an upper bound for the order of the group. If the exact group order is given and the stabiliser is calculated during the orbit enumeration (see component <C>permgens</C>), then the orbit enumeration can stop as soon as the orbit is found completely and the stabiliser is complete, which is usually much earlier than after all generator are applied to all points in the orbit.</Item> <Mark><C>hashfunc</C></Mark> <Item>See component <C>eqfunc</C>.</Item> <Mark><C>hashlen</C></Mark> <Item>Possible values are positive integers. This component determines the initial size of the hash used for the orbit enumeration. The default value is <M>10000</M>. If the hash table turns out not to be large enough, it is automatically increased by a factor of two during the calculation. Although this process is quite fast it still improves performance to give a sensible hash size in advance. </Item> <Mark><C>hfbig</C> and <C>hfdbig</C></Mark> <Item>These components can only be used in connection with <C>eqfunc</C> and <C>hashfunc</C> and are otherwise ignored. There values are simply passed on to the hash table created. The idea is to still be able to grow the hash table if need be. See Section <Ref Sect="hashdata"/> for more details. </Item> <Mark><C>log</C></Mark> <Item>If this component is set to <K>true</K> then a log of the enumeration of the orbit is written into the components <C>log</C>, <C>logind</C> and <C>logpos</C>. Every time a new point is found in the orbit enumeration, two numbers are appended to the log, first the number of the generator applied, then the index, under which the new point is stored in the orbit. For each point in the orbit, the start of the entries for that point in <C>log</C> is stored in <C>logind</C> and the end of those entries is marked by storing the number of the last generator producing a new point negated.<P/> The purpose of a log is the following: With a log one can later add group generators to the orbit and thus get a different Schreier tree, such that the resulting orbit enumeration is still a breadth first enumeration using the new generating set! This is desirable to decrease the depth of the Schreier tree. The log helps to implement this in a way, such that the old generators do not again have to be applied to all the points in the orbit. See <Ref Oper="AddGeneratorsToOrbit"/> for details.<P/> A log needs roughly 3 machine words per point in the orbit as memory. </Item> <Mark><C>lookingfor</C></Mark> <Item>This component is used to search for something in the orbit. The idea is that the orbit enumeration is stopped when some condition is met. This condition can be specified with a great flexibility. The first way is to store a list of points into <C>orb.lookingfor</C>. In that case the orbit enumeration stops, when a point is found that is in that list. A second possiblity is to store a hash table object into <C>orb.lookingfor</C>. Then every newly found point in the orbit is looked up in that hash table and the orbit enumeration stops as soon as a point is found that is also in the hash table. The third possibility is functional: You can store a &GAP; function into <C>opt.lookingfor</C> which is called for every newly found point in the orbit. It gets both the orbit object and the point as its two arguments. This function has to return <K>false</K> or <K>true</K> and in the latter case the orbit enumeration is stopped. <P/> Whenever the orbit enumeration is stopped the component <C>found</C> is set to the number of the found point in the orbit. Access this information using <C>PositionOfFound(orb)</C>. </Item> <Mark><C>matgens</C></Mark> <Item>This is not yet implemented. It will allow for stabiliser computations in matrix groups.</Item> <Mark><C>onlystab</C></Mark> <Item>If this boolean flag is set to <K>true</K> then the orbit enumeration stops once the stabiliser is completely determined. Note that this can only be known, if a bound for the group size is given in the <C>opt.grpsizebound</C> option and when more than half of the orbit is already found, or when <C>opt.stabsizebound</C> is given.</Item> <Mark><C>orbsizebound</C></Mark> <Item>Possible values for this component are positive integers. The given number must be an upper bound for the orbit length. Giving this number helps the orbit enumeration to stop earlier, when the orbit is found completely.</Item> <Mark><C>permbase</C></Mark> <Item>This component is used to tell the orbit enumerator that a certain list of points is a base of the permutation representation given in the <C>opt.permgens</C> component. This information is often available beforehand and can drastically speed up the calculation of Schreier generators, especially for the common case that they are trivial. The value is just a list of integers.</Item> <Mark><C>permgens</C></Mark> <Item>If this component is set, it must be set to a list of permutations, that represent the same group as the generators used to define the orbit. This permutation representation is then used to calculate the stabiliser of the starting point. After the orbit enumeration is complete, you can call <C>Stabilizer(<A>orb</A>)</C> with <A>orb</A> being the orbit object and get the stabiliser as a permutation group. The stabiliser is also stored in the <C>stab</C> component of the orbit object. Furthermore, the size of the stabiliser is stored in the <C>stabsize</C> component of the orbit object and the component <C>stabwords</C> contains the stabiliser generators as words in the original group generators. Access these words with <C>StabWords(orb)</C>. Here, a word is a list of integers, where positive integers are numbers of generators and a negative integer <M>i</M> indicates the inverse of the generator with number <M>-i</M>. In this way, complete information about the stabiliser can be derived from the orbit object. </Item> <Mark><C>report</C></Mark> <Item>Possible values are non-negative integers. This value asks for a status report whenever the orbit enumeration has applied all generators to <C>opt.report</C> points. A value of <M>0</M>, which is the default, switches off this report. In each report, the total number of points already found are given.</Item> <Mark><C>schreier</C></Mark> <Item>This boolean flag decides, whether a Schreier tree is stored together with the orbit. A Schreier tree just stores for each point, which generator was applied to which other point in the orbit to get it. Thus, having the Schreier tree enables the usage of the operations <Ref Oper="TraceSchreierTreeForward"/> and <Ref Oper="TraceSchreierTreeBack"/>. A Schreier tree needs two additional machine words of memory per point in the orbit. The <C>opt.schreier</C> flag is automatically set when a stabiliser is computed during orbit enumeration (see components <C>opt.permgens</C> and <C>opt.matgens</C>).</Item> <Mark><C>schreiergenaction</C></Mark> <Item>The value of this component must be a function with 4 arguments: the orbit object, an index <A>i</A>, an integer <A>j</A>, and an index <A>pos</A>. It is called, whenever during the orbit enumeration generator number <A>j</A> was applied to point number <A>i</A> and the result was an already known point with number <A>pos</A>. This is no longer done, once the component <C>stabcomplete</C> is set to <K>true</K>, which happens when there is evidence that the stabiliser is already completely determined.<P/> This component is used internally when the <C>permgens</C> component was set and the stabiliser is calculated.</Item> <Mark><C>stab</C></Mark> <Item>This component is used to tell the orbit enumerator that a subgroup of the stabiliser of the starting point is already known. Store a subgroup of the group generated by the permutations in <C>opt.permgens</C> stabilising the starting point into this component.</Item> <Mark><C>stabchainrandom</C></Mark> <Item>This value can be a positive integer between <M>1</M> and <M>1000</M>. If <C>opt.permgens</C> is given, an integer value is used to set the <C>random</C> option when calculating a stabiliser chain to compute the size of the group generated by the Schreier generators. Although this size computation can be speeded up considerably, the user should be aware that for values smaller than <M>1000</M> this triggers a Monte Carlo algorithm that can produce wrong results with a certain error probability. A verification of the obtained results is advisable. Note however, that such computations can only err in one direction, namely underestimating the size of the group.</Item> <Mark><C>stabsizebound</C></Mark> <Item>Possible values for this component are positive integers. The given number must be an upper bound for the size of the stabiliser. Giving this number helps the orbit enumeration to stop earlier, when also <C>opt.orbsizebound</C> or <C>opt.grpsizebound</C> are given or when <C>opt.onlystab</C> is set.</Item> <Mark><C>storenumbers</C></Mark> <Item>This boolean flag decides, whether the positions of points in the orbit are stored in the hash. The memory requirement for this is one machine word (<M>4</M> or <M>8</M> bytes depending on the architecture) per point in the orbit. If you just need the orbit itself this is not necessary. If you however want to find the position of a point in the orbit efficiently after enumeration, then you should switch this on. That is, the operation <C>&bslash;in</C> is always fast, but <C>Position(<A>orb</A>, <A>point</A>)</C> is only fast if <C>opt.storenumbers</C> was set to <K>true</K> or the orbit is <Q>permutations acting on positive integers</Q>. In the latter case this flag is ignored.</Item> </List> For some examples using these options see Chapter <Ref Chap="examples"/>. </Subsection> <Subsection Label="orboutputs"> <Heading>Output components of orbits</Heading> The following components are bound in an orbit object. There might be some more, but those are implementation specific and not guaranteed to be there in future versions. Note that you have to access these components using the <Q><C>.~</C></Q> dot exclamation mark notation and you should avoid using these if at all possible. <List> <Mark><C>depth</C> and <C>depthmarks</C></Mark> <Item>If the orbit has either a Schreier tree or a log, then the component <C>depth</C> holds its depth, that is the maximal number of generator applications needed to reach any point in the orbit. The corresponding component <C>depthmarks</C> is a list of indices, at position <M>i</M> it holds the index of the first point in the orbit in depth <M>i</M> in the Schreier tree. </Item> <Mark><C>gens</C></Mark> <Item>The list of group generators.</Item> <Mark><C>ht</C></Mark> <Item>If the orbit uses a hash table it is stored in this component.</Item> <Mark><C>op</C></Mark> <Item>The operation function.</Item> <Mark><C>orbind</C></Mark> <Item>If generators have been added to the orbit later then the order in which the points are actually stored in the orbit might not correspond to a breadth first search. To cover this case, the component <C>orbind</C> contains in position <M>i</M> the index under which the <M>i</M>-th point in the breadth-first search using the new generating set is actually stored in the orbit.</Item> <Mark><C>schreiergen</C> and <C>schreierpos</C></Mark> <Item>If a Schreier tree of the orbit was kept then both these components are lists containing integers. If point number <M>i</M> was found by applying generator number <M>j</M> to point number <M>p</M> then position <M>i</M> of <C>schreiergen</C> is <M>j</M> and position <M>i</M> of <C>schreierpos</C> is <M>p</M>. You can use the operations <Ref Oper="TraceSchreierTreeForward"/> and <Ref Oper="TraceSchreierTreeBack"/> to compute words in the generators using these two components.</Item> <Mark><C>tab</C></Mark> <Item>For an orbit in which permutations act on positive integers this component is bound to a list containing in position <M>i</M> the index in the orbit, where the number <M>i</M> is stored.</Item> </List> </Subsection> The following operations help to ask additional information about orbit objects: <ManSection> <Oper Name="StabWords" Arg="orb" Label="basic"/> <Returns>A list of words</Returns> <Description> If the stabiliser was computed during the orbit enumeration, then this function returns the stabiliser generators found as words in the generators. A word is a sequence of integers, where positive integers stand for generators and negative numbers for their inverses. </Description> </ManSection> <ManSection> <Oper Name="PositionOfFound" Arg="orb"/> <Returns>An integer</Returns> <Description> If during the orbit enumeration the option <C>lookingfor</C> was used and the orbit enumerator looked for something, then this operation returns the index in the orbit, where the something was found most recently. </Description> </ManSection> <ManSection> <Oper Name="DepthOfSchreierTree" Arg="orb"/> <Returns>An integer</Returns> <Description> If a Schreier tree or a log was stored during orbit enumeration, then this operation returns the depth of the Schreier tree. </Description> </ManSection> We present a few more operations one can do with orbit objects. One can express the action of a given group element in the group generated by the generators given in the <C>Orb</C> command on this orbit as a permutation: <ManSection> <Oper Name="ActionOnOrbit" Arg="orb, grpels"/> <Returns> A permutation or <K>fail</K> </Returns> <Description> <A>orb</A> must be an orbit object and <A>grpels</A> a list of group elements acting on the orbit. This operation calculates the action of <A>grpels</A> on <A>orb</A> as &GAP; permutations, where the numbering of the points is in the same order as the points have been found in the orbit. Note that this operation is particularly fast if the orbit is an orbit of a permutation group acting on positive integers or if you used the option <C>storenumbers</C> described in Subsection <Ref Subsect="orboptions"/>. </Description> </ManSection> <ManSection> <Oper Name="OrbActionHomomorphism" Arg="g, orb"/> <Returns> An action homomorphism </Returns> <Description> The argument <A>g</A> must be a group and <A>orb</A> an orbit on which <A>g</A> acts in the action of the orbit object. This operation returns a homomorphism into a permutation group acquired by taking the action of <A>g</A> on the orbit. </Description> </ManSection> <ManSection> <Oper Name="TraceSchreierTreeForward" Arg="orb, nr"/> <Returns> A word in the generators </Returns> <Description> <A>orb</A> must be an orbit object with a Schreier tree, that is, the option <C>schreier</C> must have been set during creation, and <A>nr</A> must be the number of a point in the orbit. This operation traces the Schreier tree and returns a word in the generators that maps the starting point to the point with number <A>nr</A>. Here, a word is a list of integers, where positive integers are numbers of generators and a negative integer <M>i</M> indicates the inverse of the generator with number <M>-i</M>. </Description> </ManSection> <ManSection> <Oper Name="TraceSchreierTreeBack" Arg="orb, nr"/> <Returns> A word in the generators </Returns> <Description> <A>orb</A> must be an orbit object with a Schreier tree, that is, the option <C>schreier</C> must have been set during creation, and <A>nr</A> must be the number of a point in the orbit. This operation traces the Schreier tree and returns a word in the generators that maps the point with number <A>nr</A> to the starting point. As above, a word is here a list of integers, where positive integers are numbers of generators and a negative integer <M>i</M> indicates the inverse of the generator with number <M>-i</M>. </Description> </ManSection> <ManSection> <Oper Name="ActWithWord" Arg="gens, w, op, p"/> <Returns> A point </Returns> <Description> <A>gens</A> must be a list of group generators, <A>w</A> a list of positive integers less than or equal to the length of <A>gens</A>, <A>op</A> an action function and <A>p</A> a point. This operation computes the action of the word <A>w</A> in the generators <A>gens</A> on the point <A>p</A> and returns the result. </Description> </ManSection> <ManSection> <Oper Name="EvaluateWord" Arg="gens, w"/> <Returns> A group element </Returns> <Description> <A>gens</A> must be a list of group generators, <A>w</A> a list of positive integers less than or equal to the length of <A>gens</A>. This operation evaluates the word <A>w</A> in the generators <A>gens</A> and returns the result. </Description> </ManSection> <ManSection> <Oper Name="AddGeneratorsToOrbit" Arg="orb, l [,p]"/> <Returns> The orbit object <A>orb</A> </Returns> <Description> <A>orb</A> must be an orbit object, <A>l</A> a list of new generators and, if given, <A>p</A> must be a list of permutations of equal length. <A>p</A> must be given if and only if the component <C>permgens</C> was specified upon creation of the orbit object. The new generators are appended to the old list of generators. The orbit object is changed such that it then shows the outcome of a breadth-first orbit enumeration with the <Emph>new</Emph> list of generators. Note that the order of the points already enumerated will <Emph>not</Emph> be changed. However, the Schreier tree changes, the component <C>orbind</C> is changed to indicate the order in which the points were found in the breadth-first search with the new generators and the components <C>depth</C> and <C>depthmarks</C> are changed. <P/> Note that all this is particularly efficient if the orbit has a log. If you add generators to an orbit with log, the old generators do not have to be applied again to all points!<P/> Note that new generators can actually enlarge an orbit if they generate a larger group than the old ones alone. Note also that when adding generators, the orbit is automatically enumerated completely </Description> </ManSection> <ManSection> <Oper Name="MakeSchreierTreeShallow" Arg="orb [, d]"/> <Returns> The orbit object <A>orb</A> </Returns> <Description> Uses <Ref Oper="AddGeneratorsToOrbit"/> to add more generators to the orbit in order to make the Schreier tree shallower. If <A>d</A> it is given, generators are added until the depth is less than or equal to <A>d</A> or until three more generators did not reduce the depth any more. If <A>d</A> is not given, then the logarithm to base 2 of the orbit length is taken as a default value. </Description> </ManSection> <ManSection> <Oper Name="FindSuborbits" Arg="orb, subgens [,nrsuborbits]"/> <Returns> A record </Returns> <Description> The argument <A>orb</A> must be a closed orbit object with a Schreier vector, <A>subgens</A> a list of generators for a subgroup of the originally acting group. If given, <A>nrsuborbits</A> must be a lower limit for the number of suborbits.<P/> The returned record describes the suborbit structure of <A>orb</A> with respect to the group generated by <A>subgens</A> using the following components: <C>issuborbitrecord</C> is bound to <K>true</K>, <C>o</C> is bound to <A>orb</A>, <C>nrsuborbits</C> is bound to the number of suborbits and <C>reps</C> is a list of length <C>nrsuborbits</C> containing the index in the orbit of a representative for each suborbit. Likewise, <C>words</C> contains words in the original group generators of the orbit that map the starting point of the orbit to those representatives. <C>lens</C> is a list containing the lengths of the suborbits. The component <C>suborbs</C> is bound to a list of lists, one for each suborbit containing the indices of the points in the orbit. The component <C>suborbnr</C> is a list with the same length as the orbit, containing in position <M>i</M> the number of the suborbit in which point <M>i</M> in the orbit is contained. <P/> Finally, the component <C>conjsuborbit</C> is bound to a list of length <C>nrsuborbits</C>, containing for each suborbit the number the suborbit reached from the starting point by the inverse of the word used to reach the orbit representative. This latter information probably only makes sense when the subgroup generated by <A>subgens</A> is contained in the point stabiliser of the starting point of the orbit, because then this is the so-called conjugate suborbit of a suborbit. </Description> </ManSection> <ManSection> <Oper Name="OrbitIntersectionMatrix" Arg="r, g"/> <Returns> An integer matrix </Returns> <Description> The argument <A>r</A> must be a suborbit record as returned by the operation <Ref Oper="FindSuborbits"/> above, describing the suborbit structure of an orbit with respect to a subgroup. <A>g</A> must be an element of the acting group. If <M>k</M> is the number of suborbits and the suborbits are <M>O_1, \ldots, O_k</M>, then the matrix returned by this operation has the integer <M>|O_i \cdot <A>g</A> \cap O_j|</M> in its <M>(i,j)</M>-entry. </Description> </ManSection> <!-- RegularRepresentationSchurBasisElm intentionally left out. --> </Section> <!-- ############################################################ --> </Chapter>