The code described in this chapter is quite complicated and one has to understand quite a lot of theory to use it. The reason for this is that a lot of preparatory data has to be found and supplied by the user in order for this code to run at all. Also the situations in which it can be used are quite special. However, in such a situation, the user is rewarded with impressive performance.
The main reference for the theory is [MNW07]. We briefly recall the basic setup: Let \(G\) be a group acting from the right on some set \(X\). Let \(k\) be a natural number, set \(X_{{k+1}} := X\), and let
\[ U_1 < U_2 < \ldots < U_k < U_{{k+1}} = G \]
be a chain of helper
subgroups. Further, for \(1 \leq i \leq k\) let \(X_i\) be a \(U_i\) set and let \(\pi_i : X_{{i+1}} \to X_i\) be a homomorphism of \(U_i\)-sets.
This chapter starts with a section about the main orbit enumeration function and the corresponding preparation functions. It then proceeds with a section on the used data structures, which will necessarily be rather technical. Finally, the chapter concludes with a section on higher level data structures like lists of orbit-by-suborbit objects and their administration. Note that there are quite a few examples in Chapter 11.
OrbitBySuborbits and its resulting objects‣ OrbitBySuborbit( setup, p, j, l, i, percentage ) | ( function ) |
Returns: an orbit-by-suborbit object
This is the main function in the whole business. All notations from the beginning of this Chapter 9 remain in place. The argument setup must be a setup record lying in the filter IsOrbitBySuborbitSetup (9.3-1) described in detail in Section 9.3 and produced for example by OrbitBySuborbitBootstrapForVectors (9.2-1) or OrbitBySuborbitBootstrapForLines (9.2-2) described below. In particular, it contains all the generators for \(G\) and the helper subgroups acting on the various sets. The argument p must be the starting point of the orbit. Note that the function possibly does not take p itself as starting point but rather its \(U_k\)-minimalisation, which is a point in the same \(U_k\)-orbit as p. This information is important for the resulting stabiliser and words representing the \(U_k\)-suborbits.
The integers j, l, and i, for which \(k+1 \ge \textit{j} \ge \textit{l} > \textit{i} \ge 1\) must hold, determine the running mode. j indicates in which set \(X_j\) the point p lies and thus in which set the orbit enumeration takes place, with \(j=k+1\) indicating the original set \(X\). The value l indicates which group to use for orbit enumeration. So the result will be a \(U_l\) orbit, with \(\textit{l}=\textit{k}+1\) indicating a \(G\)-orbit. Finally, the value i indicates which group to use for the by suborbit
part, that is, the orbit will be enumerated by \(U_{\textit{i}}\)-orbits
. Note that nearly all possible combinations of these parameters actually occur, because this function is also used in the on-the-fly
precomputation happening behind the scenes. The most common usage of this function for the user is \(\textit{j}=\textit{l}=\textit{k}+1\) and \(\textit{i}=k\).
Finally, the integer percentage says, how much of the full orbit should be enumerated, the value is in percent, thus \(100\) means the full orbit. Usually, only values greater than \(50\) are sensible, because one can only prove the size of the orbit after enumerating at least half of it.
The result is an orbit-by-suborbit
object. For such an object in particular the operations Size (9.1-3), Seed (9.1-4), SuborbitsDb (9.1-5), WordsToSuborbits (9.1-6), Memory (9.1-7), Stabilizer (9.1-8), and Seed (9.1-4) are defined, see below.
‣ OrbitBySuborbitKnownSize( setup, p, j, l, i, percentage, knownsize ) | ( function ) |
Returns: an orbit-by-suborbit object
Basically does the same as OrbitBySuborbit (9.1-1) but does not compute the stabiliser by evaluating Schreier words. Instead, the size of the orbit to enumerate must already be known and be given in the argument knownsize. The other arguments are as for the function OrbitBySuborbit (9.1-1).
‣ Size( orb ) | ( method ) |
Returns: an integer
Returns the number of points in the orbit-by-suborbit orb.
‣ Seed( orb ) | ( method ) |
Returns: a point in the orbit
Returns the starting point of the orbit-by-suborbit orb. It is the \(U_i\)-minimalisation of the starting point given to OrbitBySuborbit (9.1-1).
‣ SuborbitsDb( orb ) | ( operation ) |
Returns: a database of suborbits
Returns the data base of suborbits of the orbit-by-suborbit object orb. In particular, such a database object has methods for the operations Memory (9.1-7), TotalLength (9.1-11), and Representatives (9.1-12). For descriptions see below.
‣ WordsToSuborbits( orb ) | ( operation ) |
Returns: a list of words
Returns a list of words in the groups \(U_*\) reaching each of the suborbits in the orbit-by-suborbit orb. Here a word is a list of integers. Positive numbers index generators in following numbering: The first few numbers are numbers of generators of \(U_1\) the next few adjacent numbers index the generators of \(U_2\) and so on until the generators of \(G\) in the end. Negative numbers indicate the corresponding inverses of these generators.
Note that OrbitBySuborbit (9.1-1) takes the \(U_i\)-minimalisation of the starting point as its starting point and the words here are all relative to this new starting point.
‣ Memory( ob ) | ( operation ) |
Returns: an integer
Returns the amount of memory needed by the object ob, which can be either an orbit-by-suborbit object, a suborbit database object, or an object in the filter IsOrbitBySuborbitSetup (9.3-1). The amount of memory used is given in bytes. Note that this includes all hashes, databases, and preparatory data of substantial size. For orbit-by-suborbits the memory needed for the precomputation is not included, ask the setup object for that.
‣ Stabilizer( orb ) | ( method ) |
Returns: a permutation group
Returns the stabiliser of the starting point of the orbit-by-suborbit in orb in form of a permutation group, using the given faithful permutation representation in the setup record.
Note that OrbitBySuborbit (9.1-1) takes the \(U_i\)-minimalisation of the starting point as its starting point and the stabiliser returned here is the one of this new starting point.
‣ StabWords( orb ) | ( operation ) |
Returns: a list of words
Returns generators for the stabiliser of the starting point of the orbit-by-suborbit in orb in form of words as described with the operation WordsToSuborbits (9.1-6). Note again that OrbitBySuborbit (9.1-1) takes the \(U_i\)-minimalisation of the starting point as its starting point and the stabiliser returned here is the one of this new starting point.
‣ SavingFactor( orb ) | ( operation ) |
Returns: an integer
Returns the quotient of the total number of points stored in the orbit-by-suborbit orb and the total number of \(U\)-minimal points stored. Note that the memory for the precomputations is not considered here!
The following operations apply to orbit-by-suborbit database objects:
‣ TotalLength( db ) | ( operation ) |
Returns: an integer
Returns the total number of points stored in all suborbits in the orbit-by-suborbit database db.
‣ Representatives( db ) | ( operation ) |
Returns: a list of points
Returns a list of representatives of the suborbits stored in the orbit-by-suborbit database db.
‣ SavingFactor( db ) | ( operation ) |
Returns: an integer
Returns the quotient of the total number of points stored in the suborbit database db and the total number of \(U\)-minimal points stored. Note that the memory for the precomputations is not considered here!
‣ OrigSeed( orb ) | ( operation ) |
Returns: a point
Returns the original starting point for the orbit, not yet minimalised.
OrbitBySuborbit (9.1-1)‣ OrbitBySuborbitBootstrapForVectors( gens, permgens, sizes, codims, opt ) | ( function ) |
Returns: a setup record in the filter IsOrbitBySuborbitSetup (9.3-1)
All notations from the beginning of this Chapter 9 remain in place. This function is for the action of matrices on row vectors, so all generators must be matrices. The set \(X\) thus is a row space usually over a finite field and the sets \(X_i\) are quotient spaces. The matrix generators for the various groups have to be adjusted with a base change, such that the canonical projection onto \(X_i\) is just to take the first few entries in a vector, which means, that the submodules divided out are generated by the last standard basis vectors.
The first argument gens must be a list of lists of generators. The outer list must have length \(k+1\) with entry \(i\) being a list of matrices generating \(U_i\), given in the action on \(X=X_{{k+1}}\). The above mentioned base change must have been done. The second argument permgens must be an analogous list with generator lists for the \(U_i\). These representations are used to compute membership and group orders of stabilisers. In its simplest form, permgens is a list of permutation representations of the same degree, giving a set of generators for each individual group \(U_i\). Alternatively, if for some \(U_i\), \(i > 1\), it is required that the stabilizer of its action is to be calculated as a matrix group, generators of \(U_i\) in some matrix representation may be supplied. However, it is then mandatory that for all \(1 < i \leq k+1\) the generator lists have the following format: The \(i\)-th entry of permgens is a list concatenating the generator lists of \(U_1\) up to \(U_i\) (in this order) all of whose elements are in either some permutation or some matrix representation. Note that currently, the generators of \(U_1\) need to be always given in a permutation representation. The argument sizes must be a list of length \(k+1\) and entry \(i\) must be the group order of \(U_i\) (again with \(U_{{k+1}}\) being \(G\)). Finally, the argument codims must be a list of length \(k\) containing integers with the \(i\)th entry being the codimension of the \(U_i\)-invariant subspace \(Y_i\) of \(X\) with \(X_i = X/Y_i\). These codimensions must not decrease for obvious reasons, but some of them may be equal. The last argument opt is an options record. See below for possible entries.
The function does all necessary steps to fill a setup record (see 9.3) to be used with OrbitBySuborbit (9.1-1). For details see the code.
Currently, the following components in the options record opt have a meaning:
regvecfachintsIf bound it must be a list. In position \(i\) for \(i>1\) there may be a list of vectors in the \(i\)-th quotient space \(X_i\) that can be used to distinguish the left \(U_{{i-1}}\) cosets in \(U_i\). All vectors in this list are tried and the first one that actually works is used.
regvecfullhintsIf bound it must be a list. In position \(i\) for \(i>1\) there may be a list of vectors in the full space \(X\) that can be used to distinguish the left \(U_{{i-1}}\) cosets in \(U_i\). All vectors in this list are tried and the first one that actually works is used.
stabchainrandomIf bound the value is copied into the stabchainrandom component of the setup record.
nostabchainfullgroupIf bound it must be true or false. If it is unbound or set to true, no stabilizer chain is computed for the group \(U_{k+1}\). Its default value is false.
‣ OrbitBySuborbitBootstrapForLines( gens, permgens, sizes, codims, opt ) | ( function ) |
Returns: a setup record in the filter IsOrbitBySuborbitSetup (9.3-1)
All notations from the beginning of this Chapter 9 remain in place. This does exactly the same as OrbitBySuborbitBootstrapForVectors (9.2-1) except that it handles the case of matrices acting on one-dimensional subspaces. Those one-dimensional subspaces are represented by normalised vectors, where a vector is normalised if its first non-vanishing entry is equal to \(1\).
‣ OrbitBySuborbitBootstrapForSpaces( gens, permgens, sizes, codims, spcdim, opt ) | ( function ) |
Returns: a setup record in the filter IsOrbitBySuborbitSetup (9.3-1)
All notations from the beginning of this Chapter 9 remain in place. This does exactly the same as OrbitBySuborbitBootstrapForVectors (9.2-1) except that it handles the case of matrices acting on spcdim-dimensional subspaces. Those subspaces are represented by fully echelonised bases.
The description in this section is necessarily technical. It is meant more as extended annotations to the source code than as user documentation. Usually it should not be necessary for the user to know the details presented here. The function OrbitBySuborbit (9.1-1) needs an information record of the following form:
‣ IsOrbitBySuborbitSetup( ob ) | ( category ) |
Returns: true or false
Objects in this category are also in IsComponentObjRep. We describe the components, refering to the setup at the beginning of this Chapter 9.
kThe number of helper subgroups.
sizeA list of length \(k+1\) containing the orders of the groups \(U_i\), including \(U_{{k+1}} = G\).
indexA list of length \(k\) with the index \([U_i:U_{{i-1}}]\) in position \(i\) (\(U_0 = \{1\}\)).
elsA list of length \(k+1\) containing generators of the groups in their action on various sets. In position \(i\) we store all the generators for all groups acting on \(X_i\), that is for the groups \(U_1, \ldots, U_i\) (where position \(k+1\) includes the generators for \(G\). In each position the generators of all those groups are concatentated starting with \(U_1\) and ending with \(U_i\).
elsinvThe inverses of all the elements in the els component in the same arrangement.
transA list of length \(k\) in which position \(i\) for \(i>1\) contains a list of words in the generators for a transversal of \(U_{{i-1}}\) in \(U_i\) (with \(U_0 = 1\)).
pifuncProjection functions. This is a list of length \(k+1\) containing in position \(j\) a list of length \(j-1\) containing in position \(i\) a GAP function doing the projection \(X_j \to X_i\). These GAP functions take two arguments, namely the point to map and secondly the value of the pi component at positions [j][i]. Usually pifunc is just the slicing operator in GAP and pi contains the components to project onto as a range object.
piSee the description of the pifunc component.
opA list of \(k+1\) GAP operation functions, each taking a point \(p\) and a generator \(g\) in the action given by the index and returning \(pg\).
infoA list of length \(k\) containing a hash table with the minimalisation lookup data. These hash tables grow during orbit enumerations as precomputations are done behind the scenes.
info[1] contains precomputation data for \(X_1\). Assume \(x \in X_1\) to be \(U_1\)-minimal. For all \(z \in xU_1\) with \(z \neq x\) we store the number of an element in the wordcache mapping \(z\) to \(x\). For \(z=x\) we store a record with two components gens and size, where gens stores generators for the stabiliser Stab\(_{{U_1}}(x)\) as words in the group generators and size stores the size of that stabiliser.
info[i] for \(i>1\) contains precomputation data for \(X_i\). Assume \(x \in X_i\) to be \(U_i\)-minimal. For all \(U_{{i-1}}\)-minimal \(z \in xU_i \setminus xU_{{i-1}}\) we store the number of an element in trans[i] mapping \(z\) into \(xU_{{i-1}}\). For all \(U_{{i-1}}\)-minimal \(z \in xU_{{i-1}}\) with \(z \neq x\) we store the negative of the number of a word in wordcache that is in the generators of \(U_{{i-1}}\) and maps \(z\) to \(x\). For \(z=x\) we store the stabiliser information as in the case \(i=1\).
This information together with the information in the following componente allows the minimalisation function to do its job.
cosetrecogA list of length \(k\) beginning with the index \(1\). The entry at position \(i\) is bound to a function taking \(3\) arguments, namely \(i\) itself, a word in the group generators of \(U_1, \ldots, U_k\) which lies in \(U_i\), and the setup record. The function computes the number j of an element in trans[i], such that the element of \(U_i\) described by the word lies in trans[i][j] U_{{i-1}}.
cosetinfoA list of things that can be used by the functions in cosetrecog.
suborbnrA list of length \(k\) that contains in position \(i\) the number of \(U_i\)-orbits in \(X_i\) archived in info[i] during precomputation.
sumstablA list of length \(k\) that contains in position \(i\) the sum of the point stabiliser sizes of all \(U_i\)-orbits \(X_i\) archived in info[i] during precomputation.
permgensA list of length \(k+1\) containing in position \(i\) generators for \(U_1, \ldots, U_i\) in a faithful permutation representation of \(U_i\). Generators fit to the generators in els. For the variant OrbitBySuborbitKnownSize (9.1-2) the \(k+1\) entry can be unbound.
permgensinvThe inverses of the generators in permgens in the same arrangement.
sampleA list of length \(k+1\) containing sample points in the sets \(X_i\).
stabchainrandomThe value is used as the value for the random option for StabChain calculations to determine stabiliser sizes. Note that the algorithms are randomized if you use this feature with a value smaller than \(1000\).
wordhashA hash to quickly recognise already used words. For every word in the hash the position of that word in the wordcache list is stored as value in the hash.
wordcacheA list of words in the wordcache for indexing purposes.
hashlenInitial length of hash tables used for the enumeration of lists of \(U_i\)-minimal points.
staborblenlimitThis contains the limit, up to which orbits of stabilisers are computed using word action. After this limit, the stabiliser elements are actually evaluated in the group.
stabsizelimitnostoreIf the stabiliser in the quotient is larger than this limit, the suborbit is not stored.
cacheA linked list cache object (see LinkedListCache (5.2-1)) to store already computed transversal elements. The cache nodes are referenced in the transcache component and are stored in the cache cache.
transcacheThis is a list of lists of weak pointer objects. The weak pointer object at position [i][j] holds references to cache nodes of transversal elements of \(U_{i-1}\) in \(U_i\) in representation \(j\).
ORBIn this section we describe the global record ORB, which contains some entries that can tune the behaviour of the orbit-by-suborbit functions. The record has the following components:
MINSHASHLENThis positive integer is the initial value of the hash size when enumerating orbits of stored stabilisers to find all or search through \(U_{{i-1}}\)-minimal vectors in an \(U_i\)-orbit. The default value is \(1000\).
ORBITBYSUBORBITDEPTHThis integer indicates how many recursive calls to OrbitBySubOrbitInner have been done. The initial value is \(0\) to indicate that no such call has happened. This variable is necessary since the minimalisation routine sometimes uses OrbitBySubOrbitInner recursively to complete some precomputation on the fly
during some other orbit-by-suborbit enumeration. This component is always set to \(0\) automatically when calling OrbitBySuborbit (9.1-1) or OrbitBySuborbitKnownSize (9.1-2) so the user should usually not have to worry about it at all.
PATIENCEFORSTABThis integer indicates how many Schreier generators for the stabiliser are tried before assuming that the stabiliser is complete. Whenever a new generator for the stabiliser is found that increases the size of the currently known stabiliser, the count is reset to \(0\) that is, only when ORB.PATIENCEFORSTAB unsuccessful Schreier generators have been tried no more Schreier generators are created. The default value for this component is \(1000\). This feature is purely heuristical and therefore this value has to be adjusted for some orbit enumerations.
PLEASEEXITNOWThis value is usually set to false. Setting it to true in a break loop tells the orbit-by-suborbit routines to exit gracefully at the next possible time. Simply leaving such a break loop with quit; is not safe, since the routines might be in the process of updating precomputation data and the data structures might be left corrupt. Always use this component to leave an orbit enumeration prematurely.
REPORTSUBORBITSThis positive integer governs how often information messages about newly found suborbits are printed. The default value is \(1000\) saying that after every \(1000\) suborbits a message is printed, if the info level is at its default value \(1\). If the info level is increased, then this component does no longer affect the printing and all found suborbits are reported.
TRIESINQUOTIENT and TRIESINWHOLESPACEThe bootstrap routines OrbitBySuborbitBootstrapForVectors (9.2-1), OrbitBySuborbitBootstrapForLines (9.2-2) and OrbitBySuborbitBootstrapForSpaces (9.2-3) all need to compute transversals of one helper subgroup in the next one. They use orbit enumerations in various spaces to achieve this. The component TRIESINQUOTIENT must be a non-negative integer and indicates how often a random vector in the corresponding quotient space is tried to find an orbit that can distinguish between cosets. The other component TRIESINWHOLESPACE also must be a non-negative integer and indicates how often a random vector in the whole space is tried. The default values are \(3\) and \(20\) resepectively.
There are a few functions that help to administrate lists of orbit-by-suborbits.
‣ InitOrbitBySuborbitList( setup, nrrandels ) | ( function ) |
Returns: a list of orbit-by-suborbits object
Creates an object that stores a list of orbit-by-suborbits. The argument setup must be an orbit-by-suborbit setup record and nrrandels must be an integer. It indicates how many random elements in \(G\) should be used to do a probabilistic check for membership in case an orbit-by-suborbit is only partially known.
‣ IsVectorInOrbitBySuborbitList( v, obsol ) | ( function ) |
Returns: fail or an integer
Checks probabilistically, if the element v lies in one of the partially enumerated orbit-by-suborbits in the orbit-by-suborbit list object obsol. If yes, the number of that orbit-by-suborbit is returned and the answer is guaranteed to be correct. If the answer is fail there is a small probability that the point actually lies in one of the orbits but this could not be shown.
‣ OrbitsFromSeedsToOrbitList( obsol, li ) | ( function ) |
Returns: nothing
Takes the elements in the list li as seeds for orbit-by-suborbits. For each such seed it is first checked whether it lies in one of the orbit-by-suborbits in obsol, which must be an orbit-by-suborbit list object. If not found, 51% of the orbit-by-suborbit of the seed is enumerated and added to the list obsol.
This function is a good way to quickly enumerate a greater number of orbit-by-suborbits.
‣ VerifyDisjointness( obsol ) | ( function ) |
Returns: true or false
This function checks deterministically, whether the orbit-by-suborbits in the orbit-by-suborbit list object obsol are disjoint or not and returns the corresponding boolean value. This is not a Monte-Carlo algorithm. If the answer is false, the function writes out, which orbits are in fact identical.
‣ Memory( obsol ) | ( operation ) |
Returns: an integer
Returns the total memory used for all orbit-by-suborbits in the orbit-by-suborbit-list obsol. Precomputation data is not included, ask the setup object instead.
‣ TotalLength( obsol ) | ( operation ) |
Returns: an integer
Returns the total number of points stored in all orbit-by-suborbits in the orbit-by-suborbit-list obsol.
‣ Size( obsol ) | ( method ) |
Returns: an integer
Returns the total number of points in the orbit-by-suborbit-list obsol.
‣ SavingFactor( obsol ) | ( operation ) |
Returns: an integer
Returns the quotient of the total number of points stored in all orbit-by-suborbits in the orbit-by-suborbit-list obsol and the total number of \(U\)-minimal points stored, which is the average saving factor considering all orbit-by-suborbits together. Note that the memory for the precomputations is not considered here!
generated by GAPDoc2HTML