8 Orbit enumeration by suborbits
  
  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 < \cdots < U_k < U_{{k+1}} = G
  
  
  be  a chain of "helper" subgroups. Further, for 1 le i le k let X_i be a U_i
  set and let pi_i : X_{i+1} -> 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 10.
  
  
  8.1 OrbitBySuborbits and its resulting objects
  
  8.1-1 OrbitBySuborbit
  
  > 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 8 remain in place. The argument setup must be a
  setup record lying in the filter IsOrbitBySuborbitSetup (8.3-1) described in
  detail     in     Section     8.3    and    produced    for    example    by
  OrbitBySuborbitBootstrapForVectors                 (8.2-1)                or
  OrbitBySuborbitBootstrapForLines  (8.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 j ge l > 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 l=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_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 j=l=k+1 and 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 (8.1-3), Seed (8.1-4), SuborbitsDb (8.1-5),
  WordsToSuborbits  (8.1-6),  Memory  (8.1-7),  Stabilizer  (8.1-8),  and Seed
  (8.1-4) are defined, see below.
  
  8.1-2 OrbitBySuborbitKnownSize
  
  > OrbitBySuborbitKnownSize( setup, p, j, l, i, percentage, knownsize ) function
  Returns:  an orbit-by-suborbit object
  
  Basically  does the same as OrbitBySuborbit (8.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 (8.1-1).
  
  8.1-3 Size
  
  > Size( orb ) ________________________________________________________method
  Returns:  an integer
  
  Returns the number of points in the orbit-by-suborbit orb.
  
  8.1-4 Seed
  
  > 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 (8.1-1).
  
  8.1-5 SuborbitsDb
  
  > 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
  (8.1-7),   TotalLength   (8.1-11),   and   Representatives   (8.1-12).   For
  descriptions see below.
  
  8.1-6 WordsToSuborbits
  
  > 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  (8.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.
  
  8.1-7 Memory
  
  > 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 (8.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.
  
  8.1-8 Stabilizer
  
  > 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  (8.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.
  
  8.1-9 StabWords
  
  > 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  (8.1-6). Note again that OrbitBySuborbit (8.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.
  
  8.1-10 SavingFactor
  
  > 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:
  
  8.1-11 TotalLength
  
  > TotalLength( db ) _______________________________________________operation
  Returns:  an integer
  
  Returns  the  total  number  of  points  stored  in  all  suborbits  in  the
  orbit-by-suborbit database db.
  
  8.1-12 Representatives
  
  > Representatives( db ) ___________________________________________operation
  Returns:  a list of points
  
  Returns   a   list  of  representatives  of  the  suborbits  stored  in  the
  orbit-by-suborbit database db.
  
  8.1-13 SavingFactor
  
  > 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!
  
  8.1-14 OrigSeed
  
  > OrigSeed( orb ) _________________________________________________operation
  Returns:  a point
  
  Returns the original starting point for the orbit, not yet minimalised.
  
  
  8.2 Preparation functions for OrbitBySuborbit (8.1-1)
  
  8.2-1 OrbitBySuborbitBootstrapForVectors
  
  > OrbitBySuborbitBootstrapForVectors( gens, permgens, sizes, codims, opt ) function
  Returns:  a setup record in the filter IsOrbitBySuborbitSetup (8.3-1)
  
  All  notations  from  the  beginning of this Chapter 8 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,  but  here  we  have  to  have  permutation
  representations.  These  permutation  representations  are  used  to compute
  membership  and  group  orders  of stabilisers. 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  ith  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 8.3) to be
  used with OrbitBySuborbit (8.1-1). For details see the code.
  
  Currently,  the  following  components  in  the  options  record  opt have a
  meaning:
  
  regvecfachints
        If  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.
  
  regvecfullhints
        If  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.
  
  stabchainrandom
        If bound the value is copied into the stabchainrandom component of the
        setup record.
  
  8.2-2 OrbitBySuborbitBootstrapForLines
  
  > OrbitBySuborbitBootstrapForLines( gens, permgens, sizes, codims, opt ) function
  Returns:  a setup record in the filter IsOrbitBySuborbitSetup (8.3-1)
  
  All  notations  from  the  beginning of this Chapter 8 remain in place. This
  does  exactly  the same as OrbitBySuborbitBootstrapForVectors (8.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.
  
  8.2-3 OrbitBySuborbitBootstrapForSpaces
  
  > OrbitBySuborbitBootstrapForSpaces( gens, permgens, sizes, codims, spcdim, opt ) function
  Returns:  a setup record in the filter IsOrbitBySuborbitSetup (8.3-1)
  
  All  notations  from  the  beginning of this Chapter 8 remain in place. This
  does  exactly  the same as OrbitBySuborbitBootstrapForVectors (8.2-1) except
  that it handles the case of matrices acting on spcdim-dimensional subspaces.
  Those subspaces are represented by fully echelonised bases.
  
  
  8.3 Data structures for orbit-by-suborbits
  
  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 (8.1-1) needs an information
  record of the following form:
  
  8.3-1 IsOrbitBySuborbitSetup
  
  > 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 8.
  
  k
        The number of helper subgroups.
  
  size
        A  list  of  length  k+1  containing  the  orders  of  the groups U_i,
        including U_{k+1} = G.
  
  index
        A  list  of length k with the index [U_i:U_{i-1}] in position i (U_0 =
        1).
  
  els
        A  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, ..., 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.
  
  elsinv
        The  inverses  of  all  the  elements in the els component in the same
        arrangement.
  
  trans
        A  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).
  
  pifunc
        Projection  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 -> 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.
  
  pi
        See the description of the pifunc component.
  
  op
        A  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.
  
  info
        A  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 <> 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 \ 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  <> 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.
  
  cosetrecog
        A 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, ..., 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}}.
  
  cosetinfo
        A list of things that can be used by the functions in cosetrecog.
  
  suborbnr
        A  list  of  length  k  that  contains  in  position  i  the number of
        U_i-orbits in X_i archived in info[i] during precomputation.
  
  sumstabl
        A  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.
  
  permgens
        A list of length k+1 containing in position i generators for U_1, ...,
        U_i in a faithful permutation representation of U_i. Generators fit to
        the  generators  in  els.  For  the  variant  OrbitBySuborbitKnownSize
        (8.1-2) the k+1 entry can be unbound.
  
  permgensinv
        The inverses of the generators in permgens in the same arrangement.
  
  sample
        A list of length k+1 containing sample points in the sets X_i.
  
  stabchainrandom
        The  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.
  
  wordhash
        A  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.
  
  wordcache
        A list of words in the wordcache for indexing purposes.
  
  hashlen
        Initial  length  of  hash  tables used for the enumeration of lists of
        U_i-minimal points.
  
  staborblenlimit
        This  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.
  
  stabsizelimitnostore
        If  the  stabiliser  in  the  quotient  is larger than this limit, the
        suborbit is not stored.
  
  cache
        A  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.
  
  transcache
        This  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.
  
  
  8.3-2 The global record ORB
  
  In  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:
  
  MINSHASHLEN
        This  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.
  
  ORBITBYSUBORBITDEPTH
        This    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    (8.1-1)    or
        OrbitBySuborbitKnownSize  (8.1-2)  so the user should usually not have
        to worry about it at all.
  
  PATIENCEFORSTAB
        This 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.
  
  PLEASEEXITNOW
        This 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.
  
  REPORTSUBORBITS
        This  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 TRIESINWHOLESPACE
        The  bootstrap  routines  OrbitBySuborbitBootstrapForVectors  (8.2-1),
        OrbitBySuborbitBootstrapForLines              (8.2-2)              and
        OrbitBySuborbitBootstrapForSpaces   (8.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.
  
  
  8.4 Lists of orbit-by-suborbit objects
  
  There   are   a   few   functions   that   help  to  administrate  lists  of
  orbit-by-suborbits.
  
  8.4-1 InitOrbitBySuborbitList
  
  > 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.
  
  8.4-2 IsVectorInOrbitBySuborbitList
  
  > 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.
  
  8.4-3 OrbitsFromSeedsToOrbitList
  
  > 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.
  
  8.4-4 VerifyDisjointness
  
  > 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.
  
  8.4-5 Memory
  
  > 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.
  
  8.4-6 TotalLength
  
  > 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.
  
  8.4-7 Size
  
  > Size( obsol ) ______________________________________________________method
  Returns:  an integer
  
  Returns the total number of points in the orbit-by-suborbit-list obsol.
  
  8.4-8 SavingFactor
  
  > 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!