% generated by GAPDoc2LaTeX from XML source (Frank Luebeck)
\documentclass[a4paper,11pt]{report}
\usepackage{a4wide}
\sloppy
\pagestyle{myheadings}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage{makeidx}
\makeindex
\usepackage{color}
\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%% strange name because of pdflatex bug:
\definecolor{Chapter }{rgb}{0.0,0.0,1.0}

\usepackage{fancyvrb}

\usepackage{pslatex}

\usepackage[pdftex=true,
        a4paper=true,bookmarks=false,pdftitle={Written with GAPDoc},
        pdfcreator={LaTeX with hyperref package / GAPDoc},
        colorlinks=true,backref=page,breaklinks=true,linkcolor=RoyalBlue,
        citecolor=RoyalGreen,filecolor=RoyalRed,
        urlcolor=RoyalRed,pagecolor=RoyalBlue]{hyperref}

% write page numbers to a .pnr log file for online help
\newwrite\pagenrlog
\immediate\openout\pagenrlog =\jobname.pnr
\immediate\write\pagenrlog{PAGENRS := [}
\newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}}
%% were never documented, give conflicts with some additional packages


\newcommand{\GAP}{\textsf{GAP}}

\begin{document}

\logpage{[ 0, 0, 0 ]}
\begin{titlepage}
\begin{center}{\Huge \textbf{GAP 4 Package \textsf{orb}\mbox{}}}\\[1cm]
\hypersetup{pdftitle=GAP 4 Package \textsf{orb}}
\markright{\scriptsize \mbox{}\hfill GAP 4 Package \textsf{orb} \hfill\mbox{}}
{\Large \textbf{orb --- Methods to enumerate Orbits\mbox{}}}\\[1cm]
{ Version 2.0 \mbox{}}\\[1cm]
{June 2008\mbox{}}\\[1cm]
\mbox{}\\[2cm]
{\large \textbf{J{\"u}rgen M{\"u}ller    \mbox{}}}\\
{\large \textbf{Max Neunh{\"o}ffer    \mbox{}}}\\
{\large \textbf{Felix Noeske    \mbox{}}}\\
\hypersetup{pdfauthor=J{\"u}rgen M{\"u}ller    ; Max Neunh{\"o}ffer    ; Felix Noeske    }
\end{center}\vfill

\mbox{}\\
{\mbox{}\\
\small \noindent \textbf{J{\"u}rgen M{\"u}ller    } --- Email: \href{mailto://juergen.mueller@math.rwth-aachen.de} {\texttt{juergen.mueller@math.rwth-aachen.de}}\\
 --- Homepage: \href{http://www.math.rwth-aachen.de/~Juergen.Mueller} {\texttt{http://www.math.rwth-aachen.de/\texttt{\symbol{126}}Juergen.Mueller}}\\
 --- Address: \begin{minipage}[t]{8cm}\noindent
 Lehrstuhl D f{\"u}r Mathematik, RWTH Aachen, Templergraben 64, 52062 Aachen,
Germany \end{minipage}
}\\
{\mbox{}\\
\small \noindent \textbf{Max Neunh{\"o}ffer    } --- Email: \href{mailto://neunhoef@mcs.st-and.ac.uk} {\texttt{neunhoef@mcs.st-and.ac.uk}}\\
 --- Homepage: \href{http://www-groups.mcs.st-and.ac.uk/~neunhoef} {\texttt{http://www-groups.mcs.st-and.ac.uk/\texttt{\symbol{126}}neunhoef}}\\
 --- Address: \begin{minipage}[t]{8cm}\noindent
 School of Mathematics and Statistics Mathematical Institute University of St
Andrews North Haugh St Andrews, Fife KY16 9SS Scotland, UK \end{minipage}
}\\
{\mbox{}\\
\small \noindent \textbf{Felix Noeske    } --- Email: \href{mailto://felix.noeske@math.rwth-aachen.de} {\texttt{felix.noeske@math.rwth-aachen.de}}\\
 --- Homepage: \href{http://www.math.rwth-aachen.de/~Felix.Noeske} {\texttt{http://www.math.rwth-aachen.de/\texttt{\symbol{126}}Felix.Noeske}}\\
 --- Address: \begin{minipage}[t]{8cm}\noindent
 Lehrstuhl D f{\"u}r Mathematik, RWTH Aachen, Templergraben 64, 52062 Aachen,
Germany \end{minipage}
}\\
\end{titlepage}

\newpage\setcounter{page}{2}
{\small 
\section*{Copyright}
\logpage{[ 0, 0, 1 ]}
 {\copyright} 2005-2008 by J{\"u}rgen M{\"u}ller, Max Neunh{\"o}ffer and Felix
Noeske

 This program is free software: you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation, either version 3 of the License, or (at your option) any later
version. This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
details. You should have received a copy of the GNU General Public License
along with this program. If not, see \href{http://www.gnu.org/licenses/} {\texttt{http://www.gnu.org/licenses/}}. \mbox{}}\\[1cm]
\newpage

\def\contentsname{Contents\logpage{[ 0, 0, 2 ]}}

\tableofcontents
\newpage

  
\chapter{\textcolor{Chapter }{Introduction}}\label{intro}
\logpage{[ 1, 0, 0 ]}
\hyperdef{L}{X7DFB63A97E67C0A1}{}
{
  
\section{\textcolor{Chapter }{Motivation for this package}}\label{philosophy}
\logpage{[ 1, 1, 0 ]}
\hyperdef{L}{X7AC0DE4D8555D291}{}
{
  This package is about orbit enumeration. It bundles fundamental algorithms for
orbit enumeration as well as more sophisticated special-purpose algorithms for
very large orbits. 

 The fundamental methods are basically an alternative implementation to the
orbit algorithms in the \textsf{GAP} library. We tried to make them more flexible and more efficient at the same
time, therefore backwards compatibility with respect to the user interface had
to be given up. In addition, more information about how an orbit was produced
is retained and is available for further usage. These orbit enumeration
algorithms build on even more fundamental code for hash tables. 

 The higher level algorithms basically implement the idea to enumerate an orbit ``by suborbits'' with respect to one or more subgroups. While these orbit-by-suborbit
algorithms are much more efficient in many cases, they very often need careful
and sometimes difficult preparations by the user. They are definitely not
intended to be ``push-the-button-tools'' but require a considerable amount of knowledge from the ``pilot''. 

 Quite a bit of the code in this package consists in fact of interactive tools
to enable users to prepare the data for the orbit-by-suborbit algorithms to
work. }

 
\section{\textcolor{Chapter }{Overview over this manual}}\label{overview}
\logpage{[ 1, 2, 0 ]}
\hyperdef{L}{X786BACDB82918A65}{}
{
  Chapter \ref{install} describes the installation of this package. Chapter \ref{basic} describes our reimplementation of the basic orbit algorithm. Chapter \ref{hash} describes our toolbox for hash tables, whereas Chapter \ref{random} covers tools to use random methods in groups. Chapter \ref{search} describes a lot of tools to search in groups and orbits. These techniques are
basically intended to provide the data structures necessary to run the code
described in Chapter \ref{bysuborbit} to use the orbit-by-suborbit algorithms. Currently, Chapter \ref{quotfinder} is an empty placeholder. In some future version of this package it will
contain a description of code which helps users to find nice quotients of
modules which is also needed for the orbit-by-suborbit algorithms. However,
since the interface to this code is not yet stable, we chose not to document
it as of now, in particular because it relies on other not yet published
packages as of the time of this writing. Finally, Chapter \ref{examples} shows an instructive examples for the more sophisticated usage of this
package. }

  }

  
\chapter{\textcolor{Chapter }{Installation of the \textsf{orb}-Package}}\label{install}
\logpage{[ 2, 0, 0 ]}
\hyperdef{L}{X80F00D467DD002D3}{}
{
  \index{\textsf{orb}} To install this package just extract the package's archive file to the GAP \texttt{pkg} directory.

 By default the \textsf{orb} package is not automatically loaded by \textsf{GAP} when it is installed. You must load the package with \texttt{LoadPackage("orb");} before its functions become available.

 Please, send us an e-mail if you have any questions, remarks, suggestions,
etc. concerning this package. Also, I would like to hear about applications of
this package.

 Juergen M{\"u}ller, Max Neunh{\"o}ffer and Felix Noeske

  }

  
\chapter{\textcolor{Chapter }{Basic orbit enumeration}}\label{basic}
\logpage{[ 3, 0, 0 ]}
\hyperdef{L}{X7D55DB437F5407E8}{}
{
  This package contains a new implementation of the standard orbit enumeration
algorithm. The design principles for this implementation have been: 
\begin{itemize}
\item Allow partial orbit enumeration and later continuation. 
\item Consequently use hashing techniques.
\item Implement stabiliser calculation and Schreier transversals on demand.
\item Allow for searching in orbits during orbit enumeration.
\end{itemize}
 Some of these design principles made it necessary to change the user interface
in comparison to the standard \textsf{GAP} one. 
\section{\textcolor{Chapter }{Enumerating orbits}}\logpage{[ 3, 1, 0 ]}
\hyperdef{L}{X87DF498E7F386786}{}
{
  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. 

 For orbit object creation there is the following function: 

\subsection{\textcolor{Chapter }{Orb}}
\logpage{[ 3, 1, 1 ]}\nobreak
\hyperdef{L}{X86A89A0881CE04F6}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Orb({\slshape gens, point, op[, opt]})\index{Orb@\texttt{Orb}}
\label{Orb}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 An orbit object 



 The argument \mbox{\texttt{\slshape gens}} is either a \textsf{GAP} group object or a list of generators of the group acting, \mbox{\texttt{\slshape point}} is a point in the orbit to be enumerated, \mbox{\texttt{\slshape op}} is a \textsf{GAP} function describing the action of the generators on points in the usual way,
that is, \texttt{\mbox{\texttt{\slshape op}}(p,g)} returns the result of the action of the element \texttt{g} on the point \texttt{p}. 

 The optional argument \mbox{\texttt{\slshape opt}} is a \textsf{GAP} record which can contain quite a few options changing the orbit enumeration.
For a list of possible options see Subsection \ref{orboptions} at the end of this section. 

 The function returns an ``orbit'' object that can later be used to enumerate (a part of) the orbit of \mbox{\texttt{\slshape point}} under the action of the group generated by \mbox{\texttt{\slshape gens}}. 

 If \mbox{\texttt{\slshape gens}} 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. }

 The following operation actually starts the orbit enumeration: 

\subsection{\textcolor{Chapter }{Enumerate}}
\logpage{[ 3, 1, 2 ]}\nobreak
\hyperdef{L}{X7BCD5342793C7A7E}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Enumerate({\slshape orb[, limit]})\index{Enumerate@\texttt{Enumerate}}
\label{Enumerate}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 The orbit object \mbox{\texttt{\slshape orb}} 



 \mbox{\texttt{\slshape orb}} must be an orbit object created by \texttt{Orb} (\ref{Orb}). The optional argument \mbox{\texttt{\slshape limit}} must be a positive integer meaning that the orbit enumeration should stop if \mbox{\texttt{\slshape limit}} points have been found, regardless whether the orbit is complete or not. Note
that the orbit enumeration can be continued by again calling the \texttt{Enumerate} operation. If the argument \mbox{\texttt{\slshape limit}} is omitted, the whole orbit is enumerated, unless other options lead to prior
termination. }

 To see whether an orbit is closed you can use the following filter: 

\subsection{\textcolor{Chapter }{IsClosed}}
\logpage{[ 3, 1, 3 ]}\nobreak
\hyperdef{L}{X81D5A4A97AA9D4B0}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsClosed({\slshape orb})\index{IsClosed@\texttt{IsClosed}}
\label{IsClosed}
}\hfill{\scriptsize (filter)}}\\
\textbf{\indent Returns:\ }
 \texttt{true} or \texttt{false} 



 The result indicates, whether the orbit \mbox{\texttt{\slshape orb}} is already complete or not. }

 Here is an example of an orbit enumeration: 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  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
\end{Verbatim}
 The orbit object \texttt{o} 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 \texttt{AddGeneratorsToOrbit} (\ref{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! 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  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
\end{Verbatim}
 
\subsection{\textcolor{Chapter }{Options for orbits}}\label{orboptions}
\logpage{[ 3, 1, 4 ]}
\hyperdef{L}{X81BF5A087B9E1353}{}
{
  The optional fourth argument \mbox{\texttt{\slshape opt}} of the function \texttt{Orb} (\ref{Orb}) is a \textsf{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: 
\begin{description}
\item[{\texttt{eqfunc}}] This component always has to be given together with the component \texttt{hashfunc}. 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.

 Note that if you use this feature, the hash table cannot grow automatically
any more, unless you also use the components \texttt{hfbig} and \texttt{hfdbig} as well. See the description of \texttt{GrowHT} (\ref{GrowHT}) for an explanation how to use this feature. 
\item[{\texttt{genstoapply}}] This is only used internally and is intentionally not documented.
\item[{\texttt{grpsizebound}}] 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 \texttt{permgens}), 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[{\texttt{hashfunc}}] See component \texttt{eqfunc}.
\item[{\texttt{hashlen}}] Possible values are positive integers. This component determines the initial
size of the hash used for the orbit enumeration. The default value is $10000$. 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[{\texttt{hfbig} and \texttt{hfdbig}}] These components can only be used in connection with \texttt{eqfunc} and \texttt{hashfunc} 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{hashdata} for more details. 
\item[{\texttt{log}}] If this component is set to \texttt{true} then a log of the enumeration of the orbit is written into the components \texttt{log}, \texttt{logind} and \texttt{logpos}. 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 \texttt{log} is stored in \texttt{logind} and the end of those entries is marked by storing the number of the last
generator producing a new point negated.

 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 \texttt{AddGeneratorsToOrbit} (\ref{AddGeneratorsToOrbit}) for details.

 A log needs roughly 3 machine words per point in the orbit as memory. 
\item[{\texttt{lookingfor}}] 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 \texttt{orb.lookingfor}. 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 \texttt{orb.lookingfor}. 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 \textsf{GAP} function into \texttt{opt.lookingfor} 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 \texttt{false} or \texttt{true} and in the latter case the orbit enumeration is stopped. 

 Whenever the orbit enumeration is stopped the component \texttt{found} is set to the number of the found point in the orbit. Access this information
using \texttt{PositionOfFound(orb)}. 
\item[{\texttt{matgens}}] This is not yet implemented. It will allow for stabiliser computations in
matrix groups.
\item[{\texttt{onlystab}}] If this boolean flag is set to \texttt{true} 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 \texttt{opt.grpsizebound} option and when more than half of the orbit is already found, or when \texttt{opt.stabsizebound} is given.
\item[{\texttt{orbsizebound}}] 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[{\texttt{permbase}}] 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 \texttt{opt.permgens} 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[{\texttt{permgens}}] 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 \texttt{Stabilizer(\mbox{\texttt{\slshape orb}})} with \mbox{\texttt{\slshape orb}} being the orbit object and get the stabiliser as a permutation group. The
stabiliser is also stored in the \texttt{stab} component of the orbit object. Furthermore, the size of the stabiliser is
stored in the \texttt{stabsize} component of the orbit object and the component \texttt{stabwords} contains the stabiliser generators as words in the original group generators.
Access these words with \texttt{StabWords(orb)}. Here, a word is a list of integers, where positive integers are numbers of
generators and a negative integer $i$ indicates the inverse of the generator with number $-i$. In this way, complete information about the stabiliser can be derived from
the orbit object. 
\item[{\texttt{report}}] Possible values are non-negative integers. This value asks for a status report
whenever the orbit enumeration has applied all generators to \texttt{opt.report} points. A value of $0$, which is the default, switches off this report. In each report, the total
number of points already found are given.
\item[{\texttt{schreier}}] 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 \texttt{TraceSchreierTreeForward} (\ref{TraceSchreierTreeForward}) and \texttt{TraceSchreierTreeBack} (\ref{TraceSchreierTreeBack}). A Schreier tree needs two additional machine words of memory per point in
the orbit. The \texttt{opt.schreier} flag is automatically set when a stabiliser is computed during orbit
enumeration (see components \texttt{opt.permgens} and \texttt{opt.matgens}).
\item[{\texttt{schreiergenaction}}] The value of this component must be a function with 4 arguments: the orbit
object, an index \mbox{\texttt{\slshape i}}, an integer \mbox{\texttt{\slshape j}}, and an index \mbox{\texttt{\slshape pos}}. It is called, whenever during the orbit enumeration generator number \mbox{\texttt{\slshape j}} was applied to point number \mbox{\texttt{\slshape i}} and the result was an already known point with number \mbox{\texttt{\slshape pos}}. This is no longer done, once the component \texttt{stabcomplete} is set to \texttt{true}, which happens when there is evidence that the stabiliser is already
completely determined.

 This component is used internally when the \texttt{permgens} component was set and the stabiliser is calculated.
\item[{\texttt{stab}}] 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 \texttt{opt.permgens} stabilising the starting point into this component.
\item[{\texttt{stabchainrandom}}] This value can be a positive integer between $1$ and $1000$. If \texttt{opt.permgens} is given, an integer value is used to set the \texttt{random} 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 $1000$ 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[{\texttt{stabsizebound}}] 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 \texttt{opt.orbsizebound} or \texttt{opt.grpsizebound} are given or when \texttt{opt.onlystab} is set.
\item[{\texttt{storenumbers}}] 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 ($4$ or $8$ 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 \texttt{\texttt{\symbol{92}}in} is always fast, but \texttt{Position(\mbox{\texttt{\slshape orb}}, \mbox{\texttt{\slshape point}})} is only fast if \texttt{opt.storenumbers} was set to \texttt{true} or the orbit is ``permutations acting on positive integers''. In the latter case this flag is ignored.
\end{description}
 For some examples using these options see Chapter \ref{examples}. }

 
\subsection{\textcolor{Chapter }{Output components of orbits}}\label{orboutputs}
\logpage{[ 3, 1, 5 ]}
\hyperdef{L}{X7B11180F80A77D48}{}
{
  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 ``\texttt{.\texttt{\symbol{126}}}'' dot exclamation mark notation and you should avoid using these if at all
possible. 
\begin{description}
\item[{\texttt{depth} and \texttt{depthmarks}}] If the orbit has either a Schreier tree or a log, then the component \texttt{depth} holds its depth, that is the maximal number of generator applications needed
to reach any point in the orbit. The corresponding component \texttt{depthmarks} is a list of indices, at position $i$ it holds the index of the first point in the orbit in depth $i$ in the Schreier tree. 
\item[{\texttt{gens}}] The list of group generators.
\item[{\texttt{ht}}] If the orbit uses a hash table it is stored in this component.
\item[{\texttt{op}}] The operation function.
\item[{\texttt{orbind}}] 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 \texttt{orbind} contains in position $i$ the index under which the $i$-th point in the breadth-first search using the new generating set is actually
stored in the orbit.
\item[{\texttt{schreiergen} and \texttt{schreierpos}}] If a Schreier tree of the orbit was kept then both these components are lists
containing integers. If point number $i$ was found by applying generator number $j$ to point number $p$ then position $i$ of \texttt{schreiergen} is $j$ and position $i$ of \texttt{schreierpos} is $p$. You can use the operations \texttt{TraceSchreierTreeForward} (\ref{TraceSchreierTreeForward}) and \texttt{TraceSchreierTreeBack} (\ref{TraceSchreierTreeBack}) to compute words in the generators using these two components.
\item[{\texttt{tab}}] For an orbit in which permutations act on positive integers this component is
bound to a list containing in position $i$ the index in the orbit, where the number $i$ is stored.
\end{description}
 }

 The following operations help to ask additional information about orbit
objects: 

\subsection{\textcolor{Chapter }{StabWords (basic)}}
\logpage{[ 3, 1, 6 ]}\nobreak
\hyperdef{L}{X833670F47BD5632C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{StabWords({\slshape orb})\index{StabWords@\texttt{StabWords}!basic}
\label{StabWords:basic}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
A list of words



 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. }

 

\subsection{\textcolor{Chapter }{PositionOfFound}}
\logpage{[ 3, 1, 7 ]}\nobreak
\hyperdef{L}{X84F62CB679D6B3CE}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{PositionOfFound({\slshape orb})\index{PositionOfFound@\texttt{PositionOfFound}}
\label{PositionOfFound}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
An integer



 If during the orbit enumeration the option \texttt{lookingfor} 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. }

 

\subsection{\textcolor{Chapter }{DepthOfSchreierTree}}
\logpage{[ 3, 1, 8 ]}\nobreak
\hyperdef{L}{X79A6D04C7CBABFC7}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DepthOfSchreierTree({\slshape orb})\index{DepthOfSchreierTree@\texttt{DepthOfSchreierTree}}
\label{DepthOfSchreierTree}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
An integer



 If a Schreier tree or a log was stored during orbit enumeration, then this
operation returns the depth of the Schreier tree. }

 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 \texttt{Orb} command on this orbit as a permutation: 

\subsection{\textcolor{Chapter }{ActionOnOrbit}}
\logpage{[ 3, 1, 9 ]}\nobreak
\hyperdef{L}{X81C12D677CE815C7}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ActionOnOrbit({\slshape orb, grpels})\index{ActionOnOrbit@\texttt{ActionOnOrbit}}
\label{ActionOnOrbit}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 A permutation or \texttt{fail} 



 \mbox{\texttt{\slshape orb}} must be an orbit object and \mbox{\texttt{\slshape grpels}} a list of group elements acting on the orbit. This operation calculates the
action of \mbox{\texttt{\slshape grpels}} on \mbox{\texttt{\slshape orb}} as \textsf{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 \texttt{storenumbers} described in Subsection \ref{orboptions}. }

 

\subsection{\textcolor{Chapter }{OrbActionHomomorphism}}
\logpage{[ 3, 1, 10 ]}\nobreak
\hyperdef{L}{X7EA4E92180F142D3}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrbActionHomomorphism({\slshape g, orb})\index{OrbActionHomomorphism@\texttt{OrbActionHomomorphism}}
\label{OrbActionHomomorphism}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 An action homomorphism 



 The argument \mbox{\texttt{\slshape g}} must be a group and \mbox{\texttt{\slshape orb}} an orbit on which \mbox{\texttt{\slshape g}} acts in the action of the orbit object. This operation returns a homomorphism
into a permutation group acquired by taking the action of \mbox{\texttt{\slshape g}} on the orbit. }

 

\subsection{\textcolor{Chapter }{TraceSchreierTreeForward}}
\logpage{[ 3, 1, 11 ]}\nobreak
\hyperdef{L}{X7F927E787BA898BF}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{TraceSchreierTreeForward({\slshape orb, nr})\index{TraceSchreierTreeForward@\texttt{TraceSchreierTreeForward}}
\label{TraceSchreierTreeForward}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 A word in the generators 



 \mbox{\texttt{\slshape orb}} must be an orbit object with a Schreier tree, that is, the option \texttt{schreier} must have been set during creation, and \mbox{\texttt{\slshape nr}} 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 \mbox{\texttt{\slshape nr}}. Here, a word is a list of integers, where positive integers are numbers of
generators and a negative integer $i$ indicates the inverse of the generator with number $-i$. }

 

\subsection{\textcolor{Chapter }{TraceSchreierTreeBack}}
\logpage{[ 3, 1, 12 ]}\nobreak
\hyperdef{L}{X80615B4D83620AA1}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{TraceSchreierTreeBack({\slshape orb, nr})\index{TraceSchreierTreeBack@\texttt{TraceSchreierTreeBack}}
\label{TraceSchreierTreeBack}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 A word in the generators 



 \mbox{\texttt{\slshape orb}} must be an orbit object with a Schreier tree, that is, the option \texttt{schreier} must have been set during creation, and \mbox{\texttt{\slshape nr}} 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 \mbox{\texttt{\slshape nr}} 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 $i$ indicates the inverse of the generator with number $-i$. }

 

\subsection{\textcolor{Chapter }{ActWithWord}}
\logpage{[ 3, 1, 13 ]}\nobreak
\hyperdef{L}{X7D892CE87E7EBEDB}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ActWithWord({\slshape gens, w, op, p})\index{ActWithWord@\texttt{ActWithWord}}
\label{ActWithWord}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 A point 



 \mbox{\texttt{\slshape gens}} must be a list of group generators, \mbox{\texttt{\slshape w}} a list of positive integers less than or equal to the length of \mbox{\texttt{\slshape gens}}, \mbox{\texttt{\slshape op}} an action function and \mbox{\texttt{\slshape p}} a point. This operation computes the action of the word \mbox{\texttt{\slshape w}} in the generators \mbox{\texttt{\slshape gens}} on the point \mbox{\texttt{\slshape p}} and returns the result. }

 

\subsection{\textcolor{Chapter }{EvaluateWord}}
\logpage{[ 3, 1, 14 ]}\nobreak
\hyperdef{L}{X799D2F3C866B9AED}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{EvaluateWord({\slshape gens, w})\index{EvaluateWord@\texttt{EvaluateWord}}
\label{EvaluateWord}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 A group element 



 \mbox{\texttt{\slshape gens}} must be a list of group generators, \mbox{\texttt{\slshape w}} a list of positive integers less than or equal to the length of \mbox{\texttt{\slshape gens}}. This operation evaluates the word \mbox{\texttt{\slshape w}} in the generators \mbox{\texttt{\slshape gens}} and returns the result. }

 

\subsection{\textcolor{Chapter }{AddGeneratorsToOrbit}}
\logpage{[ 3, 1, 15 ]}\nobreak
\hyperdef{L}{X7D100BE4820039C1}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AddGeneratorsToOrbit({\slshape orb, l[, p]})\index{AddGeneratorsToOrbit@\texttt{AddGeneratorsToOrbit}}
\label{AddGeneratorsToOrbit}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 The orbit object \mbox{\texttt{\slshape orb}} 



 \mbox{\texttt{\slshape orb}} must be an orbit object, \mbox{\texttt{\slshape l}} a list of new generators and, if given, \mbox{\texttt{\slshape p}} must be a list of permutations of equal length. \mbox{\texttt{\slshape p}} must be given if and only if the component \texttt{permgens} 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} list of generators. Note that the order of the points already enumerated will \emph{not} be changed. However, the Schreier tree changes, the component \texttt{orbind} is changed to indicate the order in which the points were found in the
breadth-first search with the new generators and the components \texttt{depth} and \texttt{depthmarks} are changed. 

 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!

 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 }

 

\subsection{\textcolor{Chapter }{MakeSchreierTreeShallow}}
\logpage{[ 3, 1, 16 ]}\nobreak
\hyperdef{L}{X823F7A9A83EACFD0}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MakeSchreierTreeShallow({\slshape orb[, d]})\index{MakeSchreierTreeShallow@\texttt{MakeSchreierTreeShallow}}
\label{MakeSchreierTreeShallow}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 The orbit object \mbox{\texttt{\slshape orb}} 



 Uses \texttt{AddGeneratorsToOrbit} (\ref{AddGeneratorsToOrbit}) to add more generators to the orbit in order to make the Schreier tree
shallower. If \mbox{\texttt{\slshape d}} it is given, generators are added until the depth is less than or equal to \mbox{\texttt{\slshape d}} or until three more generators did not reduce the depth any more. If \mbox{\texttt{\slshape d}} is not given, then the logarithm to base 2 of the orbit length is taken as a
default value. }

 

\subsection{\textcolor{Chapter }{FindSuborbits}}
\logpage{[ 3, 1, 17 ]}\nobreak
\hyperdef{L}{X8566B13379E697F6}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FindSuborbits({\slshape orb, subgens[, nrsuborbits]})\index{FindSuborbits@\texttt{FindSuborbits}}
\label{FindSuborbits}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 A record 



 The argument \mbox{\texttt{\slshape orb}} must be a closed orbit object with a Schreier vector, \mbox{\texttt{\slshape subgens}} a list of generators for a subgroup of the originally acting group. If given, \mbox{\texttt{\slshape nrsuborbits}} must be a lower limit for the number of suborbits.

 The returned record describes the suborbit structure of \mbox{\texttt{\slshape orb}} with respect to the group generated by \mbox{\texttt{\slshape subgens}} using the following components: \texttt{issuborbitrecord} is bound to \texttt{true}, \texttt{o} is bound to \mbox{\texttt{\slshape orb}}, \texttt{nrsuborbits} is bound to the number of suborbits and \texttt{reps} is a list of length \texttt{nrsuborbits} containing the index in the orbit of a representative for each suborbit.
Likewise, \texttt{words} contains words in the original group generators of the orbit that map the
starting point of the orbit to those representatives. \texttt{lens} is a list containing the lengths of the suborbits. The component \texttt{suborbs} is bound to a list of lists, one for each suborbit containing the indices of
the points in the orbit. The component \texttt{suborbnr} is a list with the same length as the orbit, containing in position $i$ the number of the suborbit in which point $i$ in the orbit is contained. 

 Finally, the component \texttt{conjsuborbit} is bound to a list of length \texttt{nrsuborbits}, 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 \mbox{\texttt{\slshape subgens}} 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. }

 

\subsection{\textcolor{Chapter }{OrbitIntersectionMatrix}}
\logpage{[ 3, 1, 18 ]}\nobreak
\hyperdef{L}{X83015A9E823E1AB1}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrbitIntersectionMatrix({\slshape r, g})\index{OrbitIntersectionMatrix@\texttt{OrbitIntersectionMatrix}}
\label{OrbitIntersectionMatrix}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 An integer matrix 



 The argument \mbox{\texttt{\slshape r}} must be a suborbit record as returned by the operation \texttt{FindSuborbits} (\ref{FindSuborbits}) above, describing the suborbit structure of an orbit with respect to a
subgroup. \mbox{\texttt{\slshape g}} must be an element of the acting group. If $k$ is the number of suborbits and the suborbits are $O_1, \ldots, O_k$, then the matrix returned by this operation has the integer $|O_i \cdot \mbox{\texttt{\slshape g}} \cap O_j|$ in its $(i,j)$-entry. }

  }

  }

  
\chapter{\textcolor{Chapter }{Hashing techniques}}\label{hash}
\logpage{[ 4, 0, 0 ]}
\hyperdef{L}{X8705763D8698C0B7}{}
{
  
\section{\textcolor{Chapter }{The idea of hashing}}\label{hashidea}
\logpage{[ 4, 1, 0 ]}
\hyperdef{L}{X814DE39B7C1B1554}{}
{
  If one wants to store a certain set of similar objects and wants to quickly
access a given one (or come back with the result that it is unknown), the
first idea would be to store them in a list, possibly sorted for faster
access. This however still would need $\log(n)$ comparisons to find a given element or to decide that it is not yet stored. 

 Therefore one uses a much bigger array and uses a function on the space of
possible objects with integer values to decide, where in the array to store a
certain object. If this so called hash function distributes the actually
stored objects well enough over the array, the access time is constant in
average. Of course, a hash function will usually not be injective, so one
needs a strategy what to do in case of so-called ``collision'', that is, if more than one object with the same hash value has to be stored. 

 The basic functions to work with hash tables are \texttt{NewHT} (\ref{NewHT}), \texttt{AddHT} (\ref{AddHT}), and \texttt{ValueHT} (\ref{ValueHT}). They are described in Section \ref{hashtables}. In the next section, we first describe the infrastructure for hash
functions. }

 
\section{\textcolor{Chapter }{Hash functions}}\label{hashfunc}
\logpage{[ 4, 2, 0 ]}
\hyperdef{L}{X7AE36B967EB1382B}{}
{
  In the \textsf{orb} package hash functions are chosen automatically by giving a sample object
together with the length of the hash table. This is done with the following
operation: 

\subsection{\textcolor{Chapter }{ChooseHashFunction}}
\logpage{[ 4, 2, 1 ]}\nobreak
\hyperdef{L}{X7ACED4FB7C971A5A}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}}
\label{ChooseHashFunction}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 a record 



 The first argument \mbox{\texttt{\slshape ob}} must be a sample object, that is, an object like those we want to store in the
hash table later on. The argument \mbox{\texttt{\slshape len}} is an integer that gives the length of the hash table. Note that this might be
called later on automatically, when a hash table is increased in size. The
operation returns a record with two components. The component \texttt{func} is a \textsf{GAP} function taking two arguments, see below. The component \texttt{data} is some \textsf{GAP} object. Later on, the hash function will be called with two arguments, the
first is the object for which it should call the hash value and the second
argument must be the data stored in the \texttt{data} component. 

 The hash function has to return values between $1$ and the hash length \mbox{\texttt{\slshape len}} inclusively. 

 This setup is chosen such that the hash functions can be global objects that
are not created during the execution of \texttt{ChooseHashFunction} but still can change their behaviour depending on the data. }

 In the following we just document, for which types of objects there are hash
functions that can be found using \texttt{ChooseHashFunction} (\ref{ChooseHashFunction}). 

\subsection{\textcolor{Chapter }{ChooseHashFunction (gf2vec)}}
\logpage{[ 4, 2, 2 ]}\nobreak
\hyperdef{L}{X803D35D97B6E7CC5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}!gf2vec}
\label{ChooseHashFunction:gf2vec}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a record 



 This method is for compressed vectors over the field \texttt{GF(2)} of two elements. Note that there is no hash function for non-compressed
vectors over \texttt{GF(2)} because those objects cannot efficiently be recognised from their type. 

 Note that you can only use the resulting hash functions for vectors of the
same length. }

 

\subsection{\textcolor{Chapter }{ChooseHashFunction (8bitvec)}}
\logpage{[ 4, 2, 3 ]}\nobreak
\hyperdef{L}{X7B04C17D7DC6E277}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}!8bitvec}
\label{ChooseHashFunction:8bitvec}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a record 



 This method is for compressed vectors over a finite field with up to $256$ elements. Note that there is no hash function for non-compressed such vectors
because those objects cannot efficiently be recognised from their type. 

 Note that you can only use the resulting hash functions for vectors of the
same length. }

 

\subsection{\textcolor{Chapter }{ChooseHashFunction (gf2mat)}}
\logpage{[ 4, 2, 4 ]}\nobreak
\hyperdef{L}{X7F41F51C83E88759}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}!gf2mat}
\label{ChooseHashFunction:gf2mat}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a record 



 This method is for compressed matrices over the field \texttt{GF(2)} of two elements. Note that there is no hash function for non-compressed
matrices over \texttt{GF(2)} because those objects cannot efficiently be recognised from their type. 

 Note that you can only use the resulting hash functions for matrices of the
same size. }

 

\subsection{\textcolor{Chapter }{ChooseHashFunction (8bitmat)}}
\logpage{[ 4, 2, 5 ]}\nobreak
\hyperdef{L}{X847801B87A03AA77}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}!8bitmat}
\label{ChooseHashFunction:8bitmat}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a record 



 This method is for compressed matrices over a finite field with up to $256$ elements. Note that there is no hash function for non-compressed such vectors
because those objects cannot efficiently be recognised from their type. 

 Note that you can only use the resulting hash functions for matrices of the
same size. }

 

\subsection{\textcolor{Chapter }{ChooseHashFunction (int)}}
\logpage{[ 4, 2, 6 ]}\nobreak
\hyperdef{L}{X819264A980D873EE}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}!int}
\label{ChooseHashFunction:int}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a record 



 This method is for integers. }

 

\subsection{\textcolor{Chapter }{ChooseHashFunction (perm)}}
\logpage{[ 4, 2, 7 ]}\nobreak
\hyperdef{L}{X7BAD070A79E54131}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}!perm}
\label{ChooseHashFunction:perm}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a record 



 This method is for permutations. }

 

\subsection{\textcolor{Chapter }{ChooseHashFunction (intlist)}}
\logpage{[ 4, 2, 8 ]}\nobreak
\hyperdef{L}{X7C7C0CDB7DCE95B4}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}!intlist}
\label{ChooseHashFunction:intlist}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a record 



 This method is for lists of integers. }

 

\subsection{\textcolor{Chapter }{ChooseHashFunction (NBitsPcWord)}}
\logpage{[ 4, 2, 9 ]}\nobreak
\hyperdef{L}{X80C0C39080BFAA8F}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}!NBitsPcWord}
\label{ChooseHashFunction:NBitsPcWord}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a record 



 This method is for kernel Pc words. }

 

\subsection{\textcolor{Chapter }{ChooseHashFunction (IntLists)}}
\logpage{[ 4, 2, 10 ]}\nobreak
\hyperdef{L}{X87C1B2F7871B7EA4}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}!IntLists}
\label{ChooseHashFunction:IntLists}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a record 



 This method is for lists of integers. }

 

\subsection{\textcolor{Chapter }{ChooseHashFunction (MatLists)}}
\logpage{[ 4, 2, 11 ]}\nobreak
\hyperdef{L}{X80E195168734F8E3}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ChooseHashFunction({\slshape ob, len})\index{ChooseHashFunction@\texttt{ChooseHashFunction}!MatLists}
\label{ChooseHashFunction:MatLists}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a record 



 This method is for lists of matrices. }

 }

 
\section{\textcolor{Chapter }{Using hash tables}}\label{hashtables}
\logpage{[ 4, 3, 0 ]}
\hyperdef{L}{X8424E70E78FAA203}{}
{
  The following functions are needed to use hash tables. For details about the
data structures see Section \ref{hashdata}. 

\subsection{\textcolor{Chapter }{NewHT}}
\logpage{[ 4, 3, 1 ]}\nobreak
\hyperdef{L}{X7FD5A22A86DACF26}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{NewHT({\slshape sample, len})\index{NewHT@\texttt{NewHT}}
\label{NewHT}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a new hash table object 



 A new hash table for objects like \mbox{\texttt{\slshape sample}} of length \mbox{\texttt{\slshape len}} is created. Note that it is a good idea to choose a prime number as the hash
length due to the algorithm for collision handling which works particularly
well in that case. The hash function is chosen automatically. The resulting
object can be used with the functions \texttt{AddHT} (\ref{AddHT}) and \texttt{ValueHT} (\ref{ValueHT}). It will start with length \mbox{\texttt{\slshape len}} but will grow as necessary. }

 

\subsection{\textcolor{Chapter }{AddHT}}
\logpage{[ 4, 3, 2 ]}\nobreak
\hyperdef{L}{X7D9D6CF37FA68C39}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{AddHT({\slshape ht, ob, val})\index{AddHT@\texttt{AddHT}}
\label{AddHT}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 an integer or fail 



 Stores the object \mbox{\texttt{\slshape ob}} into the hash table \mbox{\texttt{\slshape ht}} and stores the value \mbox{\texttt{\slshape val}} together with \mbox{\texttt{\slshape ob}}. The result is \texttt{fail} if an error occurred, which can only be that the hash table is already full.
This can only happen, if the hash table cannot grow automatically. 

 If no error occurs, the result is an integer indicating the place in the hash
table where the object is stored. Note that once the hash table grows
automatically this number is no longer the same! 

 If the value \mbox{\texttt{\slshape val}} is \texttt{true} for all objects in the hash, no extra memory is used for the values. All other
values are stored in the hash. The value \texttt{fail} cannot be stored as it indicates that the object is not found in the hash. 

 See Section \ref{hashdata} for details on the data structures and especially about memory requirements. }

 

\subsection{\textcolor{Chapter }{ValueHT}}
\logpage{[ 4, 3, 3 ]}\nobreak
\hyperdef{L}{X853825AB7DE1F99C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ValueHT({\slshape ht, ob})\index{ValueHT@\texttt{ValueHT}}
\label{ValueHT}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 the stored value, \texttt{true}, or \texttt{fail} 



 Looks up the object \mbox{\texttt{\slshape ob}} in the hash table \mbox{\texttt{\slshape ht}}. If the object is not found, \texttt{fail} is returned. Otherwise, the value stored with the object is returned. Note
that if this value was \texttt{true} no extra memory is used for this. }

 The following function is only documented for the sake of completeness and for
emergency situations, where \texttt{NewHT} (\ref{NewHT}) tries to be too intelligent. 

\subsection{\textcolor{Chapter }{InitHT}}
\logpage{[ 4, 3, 4 ]}\nobreak
\hyperdef{L}{X7D6AA1618657386C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InitHT({\slshape len, hfun, eqfun})\index{InitHT@\texttt{InitHT}}
\label{InitHT}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a new hash table object 



 This is usually only an internal function. It is called from \texttt{NewHT} (\ref{NewHT}). The argument \mbox{\texttt{\slshape len}} is the length of the hash table, \mbox{\texttt{\slshape hfun}} is the hash function record as returned by \texttt{ChooseHashFunction} (\ref{ChooseHashFunction}) and \mbox{\texttt{\slshape eqfun}} is a comparison function taking two arguments and returning \texttt{true} or \texttt{false}. 

 Note that automatic growing is switched on for the new hash table which means
that if the hash table grows, a new hash function is chosen using \texttt{ChooseHashFunction} (\ref{ChooseHashFunction}). If you do not want this, change the component \texttt{cangrow} to \texttt{false} after creating the hash table. }

 

\subsection{\textcolor{Chapter }{GrowHT}}
\logpage{[ 4, 3, 5 ]}\nobreak
\hyperdef{L}{X86E9DEC68728425C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{GrowHT({\slshape ht, ob})\index{GrowHT@\texttt{GrowHT}}
\label{GrowHT}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 nothing 



 This is a more or less internal function. It is called when the space in a
hash table becomes scarce. The first argument \mbox{\texttt{\slshape ht}} must be a hash table object, the second a sample point. The function increases
the hash size by a factor of 2. This makes it necessary to choose a new hash
function. Usually this is done with the usual \texttt{ChooseHashFunction} method. However, one can assign the two components \texttt{hfbig} and \texttt{hfdbig} to a function and a record respectively. In that case, upon growing the hash,
a new hash function is created by taking the function \texttt{hfbig} together with \texttt{hfdbig} as second data argument and reducing the resulting integer modulo the hash
length. In this way one can specify a hash function suitable for all hash
sizes by simply producing big enough hash values. }

 }

 
\section{\textcolor{Chapter }{ The data structures for hash tables }}\label{hashdata}
\logpage{[ 4, 4, 0 ]}
\hyperdef{L}{X8069137484662072}{}
{
  A hash table object is just a record with the following components: 
\begin{description}
\item[{\texttt{els}}]  A \textsf{GAP} list storing the elements. Its length can be as long as the component \texttt{len} indicates but will only grow as necessary when elements are stored in the
hash. 
\item[{\texttt{vals}}]  A \textsf{GAP} list storing the corresponding values. If a value is \texttt{true} nothing is stored here to save memory. 
\item[{\texttt{len}}]  Length of the hash table.
\item[{\texttt{nr}}]  Number of elements stored in the hash table.
\item[{\texttt{hf}}]  The hash function (value of the \texttt{func} component in the record returned by \texttt{ChooseHashFunction} (\ref{ChooseHashFunction})). 
\item[{\texttt{hfd}}]  The data for the second argument of the hash function (value of the \texttt{data} component in the record returned by \texttt{ChooseHashFunction} (\ref{ChooseHashFunction})). 
\item[{\texttt{eqf}}]  A comparison function taking two arguments and returning \texttt{true} for equality or \texttt{false} otherwise. 
\item[{\texttt{collisions}}]  Number of collisions (see below). 
\item[{\texttt{accesses}}]  Number of lookup or store accesses to the hash. 
\item[{\texttt{cangrow}}]  A boolean value indicating whether the hash can grow automatically or not.
\item[{\texttt{ishash}}]  Is \texttt{true} to indicate that this is a hash table record.
\end{description}
 
\subsection{\textcolor{Chapter }{ Memory requirements }}\logpage{[ 4, 4, 1 ]}
\hyperdef{L}{X81BD00DE877E2C0D}{}
{
  Due to the data structure defined above the hash table will need one machine
word ($4$ bytes on 32bit machines and $8$ bytes on 64bit machines) per possible entry in the hash if all values
corresponding to objects in the hash are \texttt{true} and two machine words otherwise. This means that the memory requirement for
the hash itself is proportional to the hash table length and not to the number
of objects actually stored in the hash! 

 In addition one of course needs the memory to store the objects themselves. }

 
\subsection{\textcolor{Chapter }{ Handling of collisions }}\logpage{[ 4, 4, 2 ]}
\hyperdef{L}{X8238A6C0834A48F4}{}
{
  If two or more objects have the same hash value, the following is done: If the
hash value is coprime to the hash length, the hash value is taken as ``the increment'', otherwise $1$ is taken. The code to find the proper place for an object just repeatedly adds
the increment to the current position modulo the hash length. Due to the
choice of the increment this will eventually try all places in the hash table.
Every such increment step is counted as a collision in the \texttt{collisions} component in the hash table. This algorithm explains why it is sensible to
choose a prime number as the length of a hash table. }

 
\subsection{\textcolor{Chapter }{ Efficiency }}\logpage{[ 4, 4, 3 ]}
\hyperdef{L}{X836F7C2C7932FEAE}{}
{
  Hashing is efficient as long as there are not too many collisions. It is not a
problem if the number of collisions (counted in the \texttt{collisions} component) is smaller than the number of accesses (counted in the \texttt{accesses} component). 

 A high number of collisions can be caused by a bad hash function, because the
hash table is too small (do not fill a hash table to more than about 80\%), or
because the objects to store are just not well enough distributed. Hash tables
will grow automatically if too many collisions are detected. }

 }

  }

  
\chapter{\textcolor{Chapter }{Caching techniques}}\label{cache}
\logpage{[ 5, 0, 0 ]}
\hyperdef{L}{X86BA72E27E278718}{}
{
  
\section{\textcolor{Chapter }{The idea of caching}}\label{cacheidea}
\logpage{[ 5, 1, 0 ]}
\hyperdef{L}{X87639FAC8621A75A}{}
{
  If one wants to work with a large number of large objects which require some
time to prepare and one does not know beforehand, how often one will need each
one, it makes sense to work with some sort of cache. A cache is a data
structure to keep some of the objects already produced but not too many of
them to waste a lot of memory. That is, objects which have not been used for
some time can automatically be removed from the cache, whereas the objects
which are used more frequently stay in the cache. This chapter describes an
implementation of this idea used in the orbit-by-suborbit algorithms. }

 
\section{\textcolor{Chapter }{Using caches}}\label{cacheusage}
\logpage{[ 5, 2, 0 ]}
\hyperdef{L}{X7B269D167B6C9BF6}{}
{
  A cache is created using the following operation: 

\subsection{\textcolor{Chapter }{LinkedListCache}}
\logpage{[ 5, 2, 1 ]}\nobreak
\hyperdef{L}{X7FF40AE981FE6F75}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{LinkedListCache({\slshape memorylimit})\index{LinkedListCache@\texttt{LinkedListCache}}
\label{LinkedListCache}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 A new cache object 



 This operation creates a new linked list cache that uses at most \mbox{\texttt{\slshape memorylimit}} bytes to store its entries. The cache is organised as a linked list, newly
cached objects are appended at the beginning of the list, when the used memory
grows over the limit, old objects are removed at the end of this list
automatically. }

 New objects are entered into the hash with the following function: 

\subsection{\textcolor{Chapter }{CacheObject}}
\logpage{[ 5, 2, 2 ]}\nobreak
\hyperdef{L}{X7ECBA1228365BDC4}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{CacheObject({\slshape c, ob, mem})\index{CacheObject@\texttt{CacheObject}}
\label{CacheObject}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 A new node in the linked list cache 



 This operation enters the object \mbox{\texttt{\slshape ob}} into the cache \mbox{\texttt{\slshape c}}. The argument \mbox{\texttt{\slshape mem}} is an integer with the memory usage of the object \mbox{\texttt{\slshape ob}}. The object is prepended to the linked list cache and enough objects at the
end are removed to enforce the memory usage limit. }

 

\subsection{\textcolor{Chapter }{ClearCache}}
\logpage{[ 5, 2, 3 ]}\nobreak
\hyperdef{L}{X7E1D239886BC762C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ClearCache({\slshape c})\index{ClearCache@\texttt{ClearCache}}
\label{ClearCache}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 Nothing 



 Completely clears the cache \mbox{\texttt{\slshape c}} removing all nodes. }

 A linked list cache is used as follows: Whenever you compute one of the
objects you store it in the cache using \texttt{CacheObject} (\ref{CacheObject}) and retain the linked list node that is returned. The usual place to retain it
would be in a weak pointer object, such that this reference does not prevent
the object to be garbage collected. When you next need this object, you check
its corresponding position in the weak pointer object, if the reference is
still there, you just use it and tell the cache that it was used again by
calling \texttt{UseCacheObject} (\ref{UseCacheObject}), otherwise you create it anew and store it in the cache again. 

 As long as the object stays in the cache it is not garbage collected and the
weak pointer object will still have its reference. As soon as the object is
thrown out of the cache, the only reference to its node is the weak pointer
object, thus if a garbage collection happens, it can be garbage collected.
Note that before that garbage collection happens, the object might still be
accessible via the weak pointer object. In this way, the available main memory
in the workspace is used very efficiently and can be freed immediately when
needed. 

\subsection{\textcolor{Chapter }{UseCacheObject}}
\logpage{[ 5, 2, 4 ]}\nobreak
\hyperdef{L}{X819FD13C7CCC6810}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{UseCacheObject({\slshape c, r})\index{UseCacheObject@\texttt{UseCacheObject}}
\label{UseCacheObject}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 Nothing 



 The argument \mbox{\texttt{\slshape c}} must be a cache object and \mbox{\texttt{\slshape r}} a node for such a cache. The object is either moved to the front of the linked
list (if it is still in the cache) or it is re-cached. If necessary, objects
at the end are removed from the cache to enforce the memory usage limit. }

 }

  }

  
\chapter{\textcolor{Chapter }{Random elements}}\label{random}
\logpage{[ 6, 0, 0 ]}
\hyperdef{L}{X8151A51884B7EE2C}{}
{
  In this chapter we describe some fundamental mechanisms to produce (pseudo-)
random elements that are used later in Chapter \ref{search} about searching in groups and orbits. 
\section{\textcolor{Chapter }{Randomizing mutable objects}}\logpage{[ 6, 1, 0 ]}
\hyperdef{L}{X83F87C898304A0C8}{}
{
  For certain types of mutable objects one can get a ``random one'' by calling the following operation: 

\subsection{\textcolor{Chapter }{Randomize}}
\logpage{[ 6, 1, 1 ]}\nobreak
\hyperdef{L}{X83DD8B39864A2C94}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Randomize({\slshape ob[, rs]})\index{Randomize@\texttt{Randomize}}
\label{Randomize}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 nothing 



 The mutable object \mbox{\texttt{\slshape ob}} is changed in place. The value afterwards is random. The optional second
argument \mbox{\texttt{\slshape rs}} must be a random source and the random numbers used to randomize \mbox{\texttt{\slshape ob}} are created using the random source \mbox{\texttt{\slshape rs}} (see  (\textbf{Reference: Random Sources})). If \mbox{\texttt{\slshape rs}} is not given, then the global \textsf{GAP} random number generator is used. 

 Currently, there are \texttt{Randomize} methods for compressed vectors and compressed matrices over finite fields. See
also the \textsf{cvec} package for methods for \texttt{cvec}s and \texttt{cmat}s. }

 For vectors and one-dimensional subspaces there are two special functions to
create a list of random objects: 

\subsection{\textcolor{Chapter }{MakeRandomVectors}}
\logpage{[ 6, 1, 2 ]}\nobreak
\hyperdef{L}{X7BBA80B882867C36}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MakeRandomVectors({\slshape sample, number[, rs]})\index{MakeRandomVectors@\texttt{MakeRandomVectors}}
\label{MakeRandomVectors}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a list of random vectors 



 \mbox{\texttt{\slshape sample}} must be a vector for the mutable copies of which \texttt{Randomize} (\ref{Randomize}) is applicable and \mbox{\texttt{\slshape number}} must be a positive integer. If given, \mbox{\texttt{\slshape rs}} must be a random source. This function creates a list of \mbox{\texttt{\slshape number}} random vectors with the same type as \mbox{\texttt{\slshape sample}} using \texttt{Randomize} (\ref{Randomize}). For the creation of random numbers the random source \mbox{\texttt{\slshape rs}} is used or, if not given, the global \textsf{GAP} random number generator. }

 

\subsection{\textcolor{Chapter }{MakeRandomLines}}
\logpage{[ 6, 1, 3 ]}\nobreak
\hyperdef{L}{X7DF0A6E885A4EE42}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{MakeRandomLines({\slshape sample, number[, rs]})\index{MakeRandomLines@\texttt{MakeRandomLines}}
\label{MakeRandomLines}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a list of normalised random vectors 



 \mbox{\texttt{\slshape sample}} must be a vector for the mutable copies of which \texttt{Randomize} (\ref{Randomize}) is applicable and \mbox{\texttt{\slshape number}} must be a positive integer. If given, \mbox{\texttt{\slshape rs}} must be a random source. This function creates a list of \mbox{\texttt{\slshape number}} normalised random vectors with the same type as \mbox{\texttt{\slshape sample}} using \texttt{Randomize} (\ref{Randomize}). ``Normalised'' here means that the first non-zero entry in the vector is equal to $1$. For the creation of random numbers the random source \mbox{\texttt{\slshape rs}} is used or, if not given, the global \textsf{GAP} random number generator. }

 }

 
\section{\textcolor{Chapter }{Product replacement}}\label{prodrepl}
\logpage{[ 6, 2, 0 ]}
\hyperdef{L}{X7B46C06479401BED}{}
{
  For computations in finite groups product replacement algorithms are a viable
method of generating pseudo-random elements. This section describes a
framework and an object type to provide these algorithms. Roughly speaking a ``product replacer object'' is something that is created with a list of group generators and produces a
sequence of pseudo random group elements using some random source for random
numbers. 

\subsection{\textcolor{Chapter }{ProductReplacer}}
\logpage{[ 6, 2, 1 ]}\nobreak
\hyperdef{L}{X8290E4C57DE25CD4}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ProductReplacer({\slshape gens[, opt]})\index{ProductReplacer@\texttt{ProductReplacer}}
\label{ProductReplacer}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 a new product replacer object 



 \mbox{\texttt{\slshape gens}} must be a list of group generators. If given, \mbox{\texttt{\slshape opt}} is a \textsf{GAP} record with options. The operation creates a new product replacer object
producing pseudo random elements in the group generated by the generators \mbox{\texttt{\slshape gens}}. 

 The exact algorithm used is explained below after the description of the
options. 

 The following components in the options record have a defined meaning: 
\begin{description}
\item[{\texttt{randomsource}}] A random source object that is used to generate the random numbers used. If
none is specified the global \textsf{GAP} random number generator is used. 
\item[{\texttt{scramble}}] The \texttt{scramble} value in the algorithm described below can be set using this option. The
default value is $100$. 
\item[{\texttt{scramblefactor}}] The \texttt{scramblefactor} value in the algorithm described below can be set using this option. The
default value is $10$. 
\item[{\texttt{addslots}}] The \texttt{addslots} value in the algorithm described below can be set using this option. The
default value is $10$. 
\item[{\texttt{maxdepth}}] If \texttt{maxdepth} is set, then the production of pseudo random elements starts all over whenever \texttt{maxdepth} product replacements have been performed. The rationale behind this is that
the elements created should be evenly distributed but that the expressions in
the generators should not be too long. A good compromise is usually to set \texttt{maxdepth} to $200$ or $300$. 
\item[{\texttt{noaccu}}] Without this option set to \texttt{true} the ``rattle'' version of product replacement is used which involves an accumulator and uses
two products per random element. To use the ``shake'' version with only one product replacement per random element set this
component to \texttt{true}. 
\item[{\texttt{normalin}}] There is a variant of the product replacement algorithm that produces elements
in the normal closure of the group generated by a list of elements. It needs
random elements in the ambient group in which the normal closure is defined.
This is implemented here by setting the \texttt{normalin} component to a product replacer object working in the ambient group. It is
recommended to switch off the accumulator in the product replacer object for
the ambient group. Then to produce one random element in the normal closure
needs three multiplications. 
\end{description}
 The algorithm used does the following: A list of \texttt{Length(}\mbox{\texttt{\slshape gens}}\texttt{)+addslots} elements is created that starts with the elements \mbox{\texttt{\slshape gens}} and is filled up with random generators from \mbox{\texttt{\slshape gens}}. A product replacement randomly chooses two elements in the list and replaces
one of them by the product of the two. One step in the algorithm is to do one
product replacement followed by post-multiplying the result to the accumulator
if one is used. First \texttt{Maximum(Length(}\mbox{\texttt{\slshape gens}}\texttt{)*scramblefactor,scramble)} steps are performed. After this initialisation for every random element
requested one step is done done and the resulting element returned. }

 

\subsection{\textcolor{Chapter }{Next}}
\logpage{[ 6, 2, 2 ]}\nobreak
\hyperdef{L}{X7AB4297E78216855}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Next({\slshape pr})\index{Next@\texttt{Next}}
\label{Next}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 a (pseudo-) random group element g 



 \mbox{\texttt{\slshape pr}} must be a product replacer object. This operation makes the object generate
the next random element and return it. }

 

\subsection{\textcolor{Chapter }{Reset}}
\logpage{[ 6, 2, 3 ]}\nobreak
\hyperdef{L}{X7EAED8EB78CCEDE2}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Reset({\slshape pr})\index{Reset@\texttt{Reset}}
\label{Reset}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 nothing 



 \mbox{\texttt{\slshape pr}} must be a product replacer object. This operation resets the object in the
sense that it resets its random source (see \texttt{Reset}) and reinitialises the random element generation as described above. }

 }

  }

  
\chapter{\textcolor{Chapter }{Searching in groups and orbits}}\label{search}
\logpage{[ 7, 0, 0 ]}
\hyperdef{L}{X7DF379C283FE23EF}{}
{
  
\section{\textcolor{Chapter }{Searching using orbit enumeration}}\logpage{[ 7, 1, 0 ]}
\hyperdef{L}{X85BB0EBC7F0D8329}{}
{
  As described in Subsection \ref{orboptions} the standard orbit enumeration routines can perform search operations during
orbit enumeration. If one is looking for a shortest word in the generators of
a group to express a group element with a certain property, then this natural
breadth-first search can be used, for example by letting the group act on its
own elements, either by multiplication or by conjugation. 

 All technical instructions to do this are already given in Subsection \ref{orboptions}, so we are content to provide an example here. Assume you want to find the
shortest way to express some $7$-cycle in the symmetric group $S_{{10}}$ as a product of generators $a := $\texttt{(1,2,3,4,5,6,7,8,9,10)} and $b := $\texttt{(1,2)}. Then you could do this in the following way: 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> gens := [(1,2,3,4,5,6,7,8,9,10),(1,2)];
  [ (1,2,3,4,5,6,7,8,9,10), (1,2) ]
  gap> o := Orb(gens,(),OnRight,rec( report := 2000,
  > lookingfor := 
  > function(o,x) return NrMovedPoints(x) = 7 and Order(x)=7; end,
  > schreier := true ));
  <open orbit, 1 points with Schreier tree looking for sth.>
  gap> Enumerate(o);
  <open orbit, 614 points with Schreier tree looking for sth.>
  gap> w := TraceSchreierTreeForward(o,PositionOfFound(o));
  [ 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2 ]
  gap> ActWithWord(o!.gens,w,o!.op,o[1]);                  
  (1,10,9,8,7,6,5)
  gap> o[PositionOfFound(o)] = ActWithWord(o!.gens,w,o!.op,o[1]);
  true
  gap> EvaluateWord(o!.gens,w);
  (1,10,9,8,7,6,5)
\end{Verbatim}
 The result shows that $a^6 \cdot (a\cdot b)^3$ is a $7$-cycle and that there is no word in $a$ and $b$ with fewer than $12$ letters expressing a $7$-cycle. 

 Note that we can go on with the above orbit enumeration to find further words
to express $7$-cycles. }

 
\section{\textcolor{Chapter }{Random searches in groups}}\logpage{[ 7, 2, 0 ]}
\hyperdef{L}{X7F6A0E447E369404}{}
{
  Another possibility to look for elements in a group satisfying certain
properties is to look at random elements, usually obtained by doing product
replacement (see Section \ref{prodrepl}). Although this can lead to very long expressions as words in the generators,
one can cope with this problem by using the \texttt{maxdepth} option of the product replacer objects, which just reinitialises the product
replacement table after a certain number of product replacements has been
performed. To organise all this conveniently, there is the concept of ``random searcher objects'' described here. 

\subsection{\textcolor{Chapter }{RandomSearcher}}
\logpage{[ 7, 2, 1 ]}\nobreak
\hyperdef{L}{X7971BF5D8099E557}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RandomSearcher({\slshape gens, testfunc[, opt]})\index{RandomSearcher@\texttt{RandomSearcher}}
\label{RandomSearcher}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 a random searcher object 



 \mbox{\texttt{\slshape gens}} must be a list of group generators, \mbox{\texttt{\slshape testfunc}} a function taking as argument one group element and returning \texttt{true} or \texttt{false}. \mbox{\texttt{\slshape opt}} is an optional options record. For possible options see below. 

 At first, the random searcher object is just initialised but no random
searching is performed. The actual search is triggered by the \texttt{Search} (\ref{Search}) operation (see below). The idea of random searcher objects is that a product
replacer object is created and during a search random elements are produced
using this product replacer object, and for each group element produced the
function \mbox{\texttt{\slshape testfunc}} is called. If this function returns \texttt{true}, the search stops and the group element found is returned. 

 The following options can be bound in the options record \mbox{\texttt{\slshape opt}}: 
\begin{description}
\item[{\texttt{exceptions}}] This component can be a list to initialise the exception list in the random
searcher object. Group elements in this list are not considered as successful
searches. This list is also used to continue search operations to found more
suitable group elements as every group element considered ``found'' is added to that list before returning it. Thus every element will only be
found once. 
\item[{\texttt{maxdepth}}] Sets the \texttt{maxdepth} option of the created product replacer object. This limits the length of the
expression as product of the generators of the found group elements. 
\item[{\texttt{addslots}}] Sets the \texttt{addslots} option of the created product replacer object. 
\item[{\texttt{scramble}}] If this component is bound at all, then the created product replacer object is
created with options \texttt{scramble=100} and \texttt{scramblefactor=10} (the default values), otherwise the options \texttt{scramble=0} and \texttt{scramblefactor=0} are used, leading to no scrambling at all. See \texttt{ProductReplacer} (\ref{ProductReplacer}) for details on the product replacement algorithm. 
\end{description}
 Note that of course the generators in \mbox{\texttt{\slshape gens}} may have memory. However, the function \mbox{\texttt{\slshape testfunc}} is called with the group element with memory stripped off. }

 

\subsection{\textcolor{Chapter }{Search}}
\logpage{[ 7, 2, 2 ]}\nobreak
\hyperdef{L}{X835FBD72853595BE}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Search({\slshape rs})\index{Search@\texttt{Search}}
\label{Search}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 a group element 



 Runs the search with the random searcher object \mbox{\texttt{\slshape rs}} and returns with the first group element found. }

 }

 
\section{\textcolor{Chapter }{The dihedral trick and applications}}\logpage{[ 7, 3, 0 ]}
\hyperdef{L}{X833CDEF4843DF5C5}{}
{
  With the ``dihedral'' trick we mean the following: Two involutions $a$ and $b$ in a group always generate a dihedral group. Thus, to find a pseudo-random
element in the centraliser of an involution $a$, we can proceed as follows: Create a pseudo-random element $c$, then $b := a^c$ is another involution. If then $ab$ has order $2o$, we can use $(ab)^o$. Otherwise, if the order of $ab$ is $2o-1$, then $(ab)^o \cdot c^{{-1}}$ centralises $a$. 

 This trick allows to efficiently produce elements in the centraliser of an
involution and thus, with high probability, generators for the full
centraliser. 

 There are the following functions: 

\subsection{\textcolor{Chapter }{FindInvolution}}
\logpage{[ 7, 3, 1 ]}\nobreak
\hyperdef{L}{X84659F6786852150}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FindInvolution({\slshape pr})\index{FindInvolution@\texttt{FindInvolution}}
\label{FindInvolution}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 an involution 



 \mbox{\texttt{\slshape pr}} must be a product replacer object (see Section \ref{prodrepl}). Searches an involution by finding a random element of even order and
powering up. Returns the involution. }

 

\subsection{\textcolor{Chapter }{FindCentralisingElementOfInvolution}}
\logpage{[ 7, 3, 2 ]}\nobreak
\hyperdef{L}{X7FBBCD5C82211934}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FindCentralisingElementOfInvolution({\slshape pr, a})\index{FindCentralisingElementOfInvolution@\texttt{FindCentralisingElementOfInvolution}}
\label{FindCentralisingElementOfInvolution}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a group element 



 \mbox{\texttt{\slshape pr}} must be a product replacer object (see Section \ref{prodrepl}). Produces one random element and builds an element the centralises the
involution \mbox{\texttt{\slshape a}} using the dihedral trick described above. }

 

\subsection{\textcolor{Chapter }{FindInvolutionCentralizer}}
\logpage{[ 7, 3, 3 ]}\nobreak
\hyperdef{L}{X80CEAEAB7EDB57FE}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FindInvolutionCentralizer({\slshape pr, a, nr})\index{FindInvolutionCentralizer@\texttt{FindInvolutionCentralizer}}
\label{FindInvolutionCentralizer}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a list of \mbox{\texttt{\slshape nr}} group elements 



 \mbox{\texttt{\slshape pr}} must be a product replacer object (see Section \ref{prodrepl}) and \mbox{\texttt{\slshape a}} and involution. This function uses \texttt{FindCentralisingElementOfInvolution} (\ref{FindCentralisingElementOfInvolution}) \mbox{\texttt{\slshape nr}} times to produce an element centralising the involution \mbox{\texttt{\slshape a}} and returns the list of results. }

 }

 
\section{\textcolor{Chapter }{Orbit statistics on vector spaces}}\logpage{[ 7, 4, 0 ]}
\hyperdef{L}{X7DE53BFB7A82324D}{}
{
  The following two functions are tools to get a rough and quick estimate about
the average orbit length of a group acting on a vector space. 

\subsection{\textcolor{Chapter }{OrbitStatisticOnVectorSpace}}
\logpage{[ 7, 4, 1 ]}\nobreak
\hyperdef{L}{X80E95A9D82ADB62D}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrbitStatisticOnVectorSpace({\slshape gens, size, ti})\index{OrbitStatisticOnVectorSpace@\texttt{OrbitStatisticOnVectorSpace}}
\label{OrbitStatisticOnVectorSpace}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 nothing 



 \mbox{\texttt{\slshape gens}} must be a list of matrix group generators and \mbox{\texttt{\slshape size}} an integer giving the order of the group generated by \mbox{\texttt{\slshape gens}}. \mbox{\texttt{\slshape ti}} is an integer specifying the number of seconds to run. This function
enumerates orbits of random vectors in the natural space the group is acting
on. The average length and some other information is printed on the screen. }

 

\subsection{\textcolor{Chapter }{OrbitStatisticOnVectorSpaceLines}}
\logpage{[ 7, 4, 2 ]}\nobreak
\hyperdef{L}{X8124E7F17C95BECB}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrbitStatisticOnVectorSpaceLines({\slshape gens, size, ti})\index{OrbitStatisticOnVectorSpaceLines@\texttt{OrbitStatisticOnVectorSpaceLines}}
\label{OrbitStatisticOnVectorSpaceLines}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 nothing 



 \mbox{\texttt{\slshape gens}} must be a list of matrix group generators and \mbox{\texttt{\slshape size}} an integer giving the order of the group generated by \mbox{\texttt{\slshape gens}}. \mbox{\texttt{\slshape ti}} is an integer specifying the number of seconds to run. This function
enumerates orbits of random one-dimensional subspaces in the natural space the
group is acting on. The average length and some other information is printed
on the screen. }

 }

 
\section{\textcolor{Chapter }{Finding generating sets of subgroups}}\logpage{[ 7, 5, 0 ]}
\hyperdef{L}{X7F051A447E2E8573}{}
{
  The following function can be used to find generators of a subgroup of a group $G$, expressed as a straight line program in the generators of $G$. 

\subsection{\textcolor{Chapter }{FindShortGeneratorsOfSubgroup}}
\logpage{[ 7, 5, 1 ]}\nobreak
\hyperdef{L}{X80BB35D380A972BB}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{FindShortGeneratorsOfSubgroup({\slshape G, U, membershiptest})\index{FindShortGeneratorsOfSubgroup@\texttt{FindShortGeneratorsOfSubgroup}}
\label{FindShortGeneratorsOfSubgroup}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a record described below 



 The arguments \mbox{\texttt{\slshape U}} and \mbox{\texttt{\slshape G}} must be \textsf{GAP} group objects with \mbox{\texttt{\slshape U}} being a subgroup of \mbox{\texttt{\slshape G}}. The argument \mbox{\texttt{\slshape membershiptest}} must be a function taking two arguments, namely a group element and a group,
that checks, whether the group element lies in the group or not, returning \texttt{true} or \texttt{false} accordingly. You can usually just use the function \texttt{\texttt{\symbol{92}}in} as third argument. 

 This function does a breadth-first search to find elements in \mbox{\texttt{\slshape U}} using the generators of \mbox{\texttt{\slshape G}}. It then uses calculates the size of the group generated and proceeds in this
way, until a generating system for \mbox{\texttt{\slshape U}} is found in terms of the generators of \mbox{\texttt{\slshape G}}. Those generators are guaranteed to be shortest words in the generators of \mbox{\texttt{\slshape G}} lying in \mbox{\texttt{\slshape U}}. 

 The function returns a record with two components bound: \texttt{gens} is a list of generators for \mbox{\texttt{\slshape U}} and \texttt{slp} is a \textsf{GAP} straight line program expressing exactly those generators in the generators of \mbox{\texttt{\slshape G}}. 

 Note that this function only performs satisfactorily when the index of \mbox{\texttt{\slshape U}} in \mbox{\texttt{\slshape G}} is not to huge. It also helps if the groups come in a representation in which \textsf{GAP} can compute efficiently for example as permutation groups. }

 }

  }

  
\chapter{\textcolor{Chapter }{Orbit enumeration by suborbits}}\label{bysuborbit}
\logpage{[ 8, 0, 0 ]}
\hyperdef{L}{X7CC7EC257DD466E3}{}
{
  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 \cite{MNW}. 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}} \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 \ref{examples}. 
\section{\textcolor{Chapter }{\texttt{OrbitBySuborbits} and its resulting objects}}\logpage{[ 8, 1, 0 ]}
\hyperdef{L}{X819508B17A733D53}{}
{
  

\subsection{\textcolor{Chapter }{OrbitBySuborbit}}
\logpage{[ 8, 1, 1 ]}\nobreak
\hyperdef{L}{X79B161FD84AB8C68}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrbitBySuborbit({\slshape setup, p, j, l, i, percentage})\index{OrbitBySuborbit@\texttt{OrbitBySuborbit}}
\label{OrbitBySuborbit}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 an orbit-by-suborbit object 



 This is the main function in the whole business. All notations from the
beginning of this Chapter \ref{bysuborbit} remain in place. The argument \mbox{\texttt{\slshape setup}} must be a setup record lying in the filter \texttt{IsOrbitBySuborbitSetup} (\ref{IsOrbitBySuborbitSetup}) described in detail in Section \ref{obsodatastrucs} and produced for example by \texttt{OrbitBySuborbitBootstrapForVectors} (\ref{OrbitBySuborbitBootstrapForVectors}) or \texttt{OrbitBySuborbitBootstrapForLines} (\ref{OrbitBySuborbitBootstrapForLines}) described below. In particular, it contains all the generators for $G$ and the helper subgroups acting on the various sets. The argument \mbox{\texttt{\slshape p}} must be the starting point of the orbit. Note that the function possibly does
not take \mbox{\texttt{\slshape p}} itself as starting point but rather its $U_k$-minimalisation, which is a point in the same $U_k$-orbit as \mbox{\texttt{\slshape p}}. This information is important for the resulting stabiliser and words
representing the $U_k$-suborbits. 

 The integers \mbox{\texttt{\slshape j}}, \mbox{\texttt{\slshape l}}, and \mbox{\texttt{\slshape i}}, for which $k+1 \ge \mbox{\texttt{\slshape j}} \ge \mbox{\texttt{\slshape l}} > \mbox{\texttt{\slshape i}} \ge 1$ must hold, determine the running mode. \mbox{\texttt{\slshape j}} indicates in which set $X_j$ the point \mbox{\texttt{\slshape p}} lies and thus in which set the orbit enumeration takes place, with $j=k+1$ indicating the original set $X$. The value \mbox{\texttt{\slshape l}} indicates which group to use for orbit enumeration. So the result will be a $U_l$ orbit, with $\mbox{\texttt{\slshape l}}=\mbox{\texttt{\slshape k}}+1$ indicating a $G$-orbit. Finally, the value \mbox{\texttt{\slshape i}} indicates which group to use for the ``by suborbit'' part, that is, the orbit will be enumerated ``by $U_{\mbox{\texttt{\slshape 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 $\mbox{\texttt{\slshape j}}=\mbox{\texttt{\slshape l}}=\mbox{\texttt{\slshape k}}+1$ and $\mbox{\texttt{\slshape i}}=k$. 

 Finally, the integer \mbox{\texttt{\slshape 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 \texttt{Size} (\ref{Size:fororb}), \texttt{Seed} (\ref{Seed}), \texttt{SuborbitsDb} (\ref{SuborbitsDb}), \texttt{WordsToSuborbits} (\ref{WordsToSuborbits}), \texttt{Memory} (\ref{Memory:forob}), \texttt{Stabilizer} (\ref{Stabilizer:obso}), and \texttt{Seed} (\ref{Seed}) are defined, see below. }

 

\subsection{\textcolor{Chapter }{OrbitBySuborbitKnownSize}}
\logpage{[ 8, 1, 2 ]}\nobreak
\hyperdef{L}{X86CCD9B98156155E}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrbitBySuborbitKnownSize({\slshape setup, p, j, l, i, percentage, knownsize})\index{OrbitBySuborbitKnownSize@\texttt{OrbitBySuborbitKnownSize}}
\label{OrbitBySuborbitKnownSize}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 an orbit-by-suborbit object 



 Basically does the same as \texttt{OrbitBySuborbit} (\ref{OrbitBySuborbit}) 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 \mbox{\texttt{\slshape knownsize}}. The other arguments are as for the function \texttt{OrbitBySuborbit} (\ref{OrbitBySuborbit}). }

 

\subsection{\textcolor{Chapter }{Size (fororb)}}
\logpage{[ 8, 1, 3 ]}\nobreak
\hyperdef{L}{X83C66D4A8603CA56}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Size({\slshape orb})\index{Size@\texttt{Size}!fororb}
\label{Size:fororb}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 an integer 



 Returns the number of points in the orbit-by-suborbit \mbox{\texttt{\slshape orb}}. }

 

\subsection{\textcolor{Chapter }{Seed}}
\logpage{[ 8, 1, 4 ]}\nobreak
\hyperdef{L}{X7EBEA64D7A5F78E3}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Seed({\slshape orb})\index{Seed@\texttt{Seed}}
\label{Seed}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a point in the orbit 



 Returns the starting point of the orbit-by-suborbit \mbox{\texttt{\slshape orb}}. It is the $U_i$-minimalisation of the starting point given to \texttt{OrbitBySuborbit} (\ref{OrbitBySuborbit}). }

 

\subsection{\textcolor{Chapter }{SuborbitsDb}}
\logpage{[ 8, 1, 5 ]}\nobreak
\hyperdef{L}{X80B78B657E77A485}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SuborbitsDb({\slshape orb})\index{SuborbitsDb@\texttt{SuborbitsDb}}
\label{SuborbitsDb}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 a database of suborbits 



 Returns the data base of suborbits of the orbit-by-suborbit object \mbox{\texttt{\slshape orb}}. In particular, such a database object has methods for the operations \texttt{Memory} (\ref{Memory:forob}), \texttt{TotalLength} (\ref{TotalLength:fordb}), and \texttt{Representatives} (\ref{Representatives}). For descriptions see below. }

 

\subsection{\textcolor{Chapter }{WordsToSuborbits}}
\logpage{[ 8, 1, 6 ]}\nobreak
\hyperdef{L}{X7B5E783478A337C9}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{WordsToSuborbits({\slshape orb})\index{WordsToSuborbits@\texttt{WordsToSuborbits}}
\label{WordsToSuborbits}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 a list of words 



 Returns a list of words in the groups $U_*$ reaching each of the suborbits in the orbit-by-suborbit \mbox{\texttt{\slshape 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 \texttt{OrbitBySuborbit} (\ref{OrbitBySuborbit}) 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. }

 

\subsection{\textcolor{Chapter }{Memory (forob)}}
\logpage{[ 8, 1, 7 ]}\nobreak
\hyperdef{L}{X7926C96485985614}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Memory({\slshape ob})\index{Memory@\texttt{Memory}!forob}
\label{Memory:forob}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 an integer 



 Returns the amount of memory needed by the object \mbox{\texttt{\slshape ob}}, which can be either an orbit-by-suborbit object, a suborbit database object,
or an object in the filter \texttt{IsOrbitBySuborbitSetup} (\ref{IsOrbitBySuborbitSetup}). 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. }

 

\subsection{\textcolor{Chapter }{Stabilizer (obso)}}
\logpage{[ 8, 1, 8 ]}\nobreak
\hyperdef{L}{X840AFA7987535AC5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Stabilizer({\slshape orb})\index{Stabilizer@\texttt{Stabilizer}!obso}
\label{Stabilizer:obso}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 a permutation group 



 Returns the stabiliser of the starting point of the orbit-by-suborbit in \mbox{\texttt{\slshape orb}} in form of a permutation group, using the given faithful permutation
representation in the setup record. 

 Note that \texttt{OrbitBySuborbit} (\ref{OrbitBySuborbit}) 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. }

 

\subsection{\textcolor{Chapter }{StabWords}}
\logpage{[ 8, 1, 9 ]}\nobreak
\hyperdef{L}{X7F496D9B7C44DAAB}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{StabWords({\slshape orb})\index{StabWords@\texttt{StabWords}}
\label{StabWords}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 a list of words 



 Returns generators for the stabiliser of the starting point of the
orbit-by-suborbit in \mbox{\texttt{\slshape orb}} in form of words as described with the operation \texttt{WordsToSuborbits} (\ref{WordsToSuborbits}). Note again that \texttt{OrbitBySuborbit} (\ref{OrbitBySuborbit}) 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. }

 

\subsection{\textcolor{Chapter }{SavingFactor (fororb)}}
\logpage{[ 8, 1, 10 ]}\nobreak
\hyperdef{L}{X802068267DACF3F6}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SavingFactor({\slshape orb})\index{SavingFactor@\texttt{SavingFactor}!fororb}
\label{SavingFactor:fororb}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 an integer 



 Returns the quotient of the total number of points stored in the
orbit-by-suborbit \mbox{\texttt{\slshape 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: 

\subsection{\textcolor{Chapter }{TotalLength (fordb)}}
\logpage{[ 8, 1, 11 ]}\nobreak
\hyperdef{L}{X79DB081F827B53CB}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{TotalLength({\slshape db})\index{TotalLength@\texttt{TotalLength}!fordb}
\label{TotalLength:fordb}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 an integer 



 Returns the total number of points stored in all suborbits in the
orbit-by-suborbit database \mbox{\texttt{\slshape db}}. }

 

\subsection{\textcolor{Chapter }{Representatives}}
\logpage{[ 8, 1, 12 ]}\nobreak
\hyperdef{L}{X81ABF8407AF16C34}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Representatives({\slshape db})\index{Representatives@\texttt{Representatives}}
\label{Representatives}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 a list of points 



 Returns a list of representatives of the suborbits stored in the
orbit-by-suborbit database \mbox{\texttt{\slshape db}}. }

 

\subsection{\textcolor{Chapter }{SavingFactor (fordb)}}
\logpage{[ 8, 1, 13 ]}\nobreak
\hyperdef{L}{X79552A1086449062}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SavingFactor({\slshape db})\index{SavingFactor@\texttt{SavingFactor}!fordb}
\label{SavingFactor:fordb}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 an integer 



 Returns the quotient of the total number of points stored in the suborbit
database \mbox{\texttt{\slshape db}} and the total number of $U$-minimal points stored. Note that the memory for the precomputations is not
considered here! }

 

\subsection{\textcolor{Chapter }{OrigSeed}}
\logpage{[ 8, 1, 14 ]}\nobreak
\hyperdef{L}{X7A96D6D37F0EC46A}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrigSeed({\slshape orb})\index{OrigSeed@\texttt{OrigSeed}}
\label{OrigSeed}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 a point 



 Returns the original starting point for the orbit, not yet minimalised. }

 }

 
\section{\textcolor{Chapter }{Preparation functions for \texttt{OrbitBySuborbit} (\ref{OrbitBySuborbit})}}\logpage{[ 8, 2, 0 ]}
\hyperdef{L}{X7C0335D97C990559}{}
{
  

\subsection{\textcolor{Chapter }{OrbitBySuborbitBootstrapForVectors}}
\logpage{[ 8, 2, 1 ]}\nobreak
\hyperdef{L}{X830E221D84E44A64}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrbitBySuborbitBootstrapForVectors({\slshape gens, permgens, sizes, codims, opt})\index{OrbitBySuborbitBootstrapForVectors@\texttt{OrbitBySuborbitBootstrapForVectors}}
\label{OrbitBySuborbitBootstrapForVectors}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a setup record in the filter \texttt{IsOrbitBySuborbitSetup} (\ref{IsOrbitBySuborbitSetup}) 



 All notations from the beginning of this Chapter \ref{bysuborbit} 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 \mbox{\texttt{\slshape 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 \mbox{\texttt{\slshape 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 \mbox{\texttt{\slshape 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 \mbox{\texttt{\slshape 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 \mbox{\texttt{\slshape opt}} is an options record. See below for possible entries. 

 The function does all necessary steps to fill a setup record (see \ref{obsodatastrucs}) to be used with \texttt{OrbitBySuborbit} (\ref{OrbitBySuborbit}). For details see the code. 

 Currently, the following components in the options record \mbox{\texttt{\slshape opt}} have a meaning: 
\begin{description}
\item[{\texttt{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. 
\item[{\texttt{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. 
\item[{\texttt{stabchainrandom}}] If bound the value is copied into the \texttt{stabchainrandom} component of the setup record.
\end{description}
 }

 

\subsection{\textcolor{Chapter }{OrbitBySuborbitBootstrapForLines}}
\logpage{[ 8, 2, 2 ]}\nobreak
\hyperdef{L}{X799056597EA62513}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrbitBySuborbitBootstrapForLines({\slshape gens, permgens, sizes, codims, opt})\index{OrbitBySuborbitBootstrapForLines@\texttt{OrbitBySuborbitBootstrapForLines}}
\label{OrbitBySuborbitBootstrapForLines}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a setup record in the filter \texttt{IsOrbitBySuborbitSetup} (\ref{IsOrbitBySuborbitSetup}) 



 All notations from the beginning of this Chapter \ref{bysuborbit} remain in place. This does exactly the same as \texttt{OrbitBySuborbitBootstrapForVectors} (\ref{OrbitBySuborbitBootstrapForVectors}) 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$. }

 

\subsection{\textcolor{Chapter }{OrbitBySuborbitBootstrapForSpaces}}
\logpage{[ 8, 2, 3 ]}\nobreak
\hyperdef{L}{X7919B1AB7D68780D}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrbitBySuborbitBootstrapForSpaces({\slshape gens, permgens, sizes, codims, spcdim, opt})\index{OrbitBySuborbitBootstrapForSpaces@\texttt{OrbitBySuborbitBootstrapForSpaces}}
\label{OrbitBySuborbitBootstrapForSpaces}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a setup record in the filter \texttt{IsOrbitBySuborbitSetup} (\ref{IsOrbitBySuborbitSetup}) 



 All notations from the beginning of this Chapter \ref{bysuborbit} remain in place. This does exactly the same as \texttt{OrbitBySuborbitBootstrapForVectors} (\ref{OrbitBySuborbitBootstrapForVectors}) except that it handles the case of matrices acting on \mbox{\texttt{\slshape spcdim}}-dimensional subspaces. Those subspaces are represented by fully echelonised
bases. }

 }

 
\section{\textcolor{Chapter }{Data structures for orbit-by-suborbits}}\label{obsodatastrucs}
\logpage{[ 8, 3, 0 ]}
\hyperdef{L}{X80F036B378A3FD32}{}
{
  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 \texttt{OrbitBySuborbit} (\ref{OrbitBySuborbit}) needs an information record of the following form: 

\subsection{\textcolor{Chapter }{IsOrbitBySuborbitSetup}}
\logpage{[ 8, 3, 1 ]}\nobreak
\hyperdef{L}{X7CFD48C17B48CDDD}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsOrbitBySuborbitSetup({\slshape ob})\index{IsOrbitBySuborbitSetup@\texttt{IsOrbitBySuborbitSetup}}
\label{IsOrbitBySuborbitSetup}
}\hfill{\scriptsize (Category)}}\\
\textbf{\indent Returns:\ }
 \texttt{true} or \texttt{false} 



 Objects in this category are also in \texttt{IsComponentObjRep}. We describe the components, refering to the setup at the beginning of this
Chapter \ref{bysuborbit}. 
\begin{description}
\item[{\texttt{k}}]  The number of helper subgroups. 
\item[{\texttt{size}}]  A list of length $k+1$ containing the orders of the groups $U_i$, including $U_{{k+1}} = G$. 
\item[{\texttt{index}}]  A list of length $k$ with the index $[U_i:U_{{i-1}}]$ in position $i$ ($U_0 = \{1\}$). 
\item[{\texttt{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, \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$. 
\item[{\texttt{elsinv}}]  The inverses of all the elements in the \texttt{els} component in the same arrangement. 
\item[{\texttt{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$). 
\item[{\texttt{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 \textsf{GAP} function doing the projection $X_j \to X_i$. These \textsf{GAP} functions take two arguments, namely the point to map and secondly the value
of the \texttt{pi} component at positions \texttt{[j][i]}. Usually \texttt{pifunc} is just the slicing operator in \textsf{GAP} and \texttt{pi} contains the components to project onto as a range object. 
\item[{\texttt{pi}}]  See the description of the \texttt{pifunc} component. 
\item[{\texttt{op}}]  A list of $k+1$ \textsf{GAP} operation functions, each taking a point $p$ and a generator $g$ in the action given by the index and returning $pg$. 
\item[{\texttt{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. 

 \texttt{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 \texttt{wordcache} mapping $z$ to $x$. For $z=x$ we store a record with two components \texttt{gens} and \texttt{size}, where \texttt{gens} stores generators for the stabiliser Stab$_{{U_1}}(x)$ as words in the group generators and \texttt{size} stores the size of that stabiliser. 

 \texttt{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 \texttt{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 \texttt{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. 
\item[{\texttt{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, \ldots, U_k$ which lies in $U_i$, and the setup record. The function computes the number \texttt{j} of an element in \texttt{trans[i]}, such that the element of $U_i$ described by the word lies in \texttt{trans[i][j]
U{\textunderscore}\texttt{\symbol{123}}\texttt{\symbol{123}}i-1\texttt{\symbol{125}}\texttt{\symbol{125}}}. 
\item[{\texttt{cosetinfo}}]  A list of things that can be used by the functions in \texttt{cosetrecog}. 
\item[{\texttt{suborbnr}}]  A list of length $k$ that contains in position $i$ the number of $U_i$-orbits in $X_i$ archived in \texttt{info[i]} during precomputation. 
\item[{\texttt{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 \texttt{info[i]} during precomputation. 
\item[{\texttt{permgens}}]  A 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 \texttt{els}. For the variant \texttt{OrbitBySuborbitKnownSize} (\ref{OrbitBySuborbitKnownSize}) the $k+1$ entry can be unbound. 
\item[{\texttt{permgensinv}}]  The inverses of the generators in \texttt{permgens} in the same arrangement. 
\item[{\texttt{sample}}]  A list of length $k+1$ containing sample points in the sets $X_i$. 
\item[{\texttt{stabchainrandom}}]  The value is used as the value for the \texttt{random} option for \texttt{StabChain} calculations to determine stabiliser sizes. Note that the algorithms are
randomized if you use this feature with a value smaller than $1000$. 
\item[{\texttt{wordhash}}]  A hash to quickly recognise already used words. For every word in the hash the
position of that word in the \texttt{wordcache} list is stored as value in the hash. 
\item[{\texttt{wordcache}}]  A list of words in the wordcache for indexing purposes. 
\item[{\texttt{hashlen}}]  Initial length of hash tables used for the enumeration of lists of $U_i$-minimal points. 
\item[{\texttt{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. 
\item[{\texttt{stabsizelimitnostore}}]  If the stabiliser in the quotient is larger than this limit, the suborbit is
not stored. 
\item[{\texttt{cache}}] A linked list cache object (see \texttt{LinkedListCache} (\ref{LinkedListCache})) to store already computed transversal elements. The cache nodes are
referenced in the \texttt{transcache} component and are stored in the cache \texttt{cache}. 
\item[{\texttt{transcache}}] This is a list of lists of weak pointer objects. The weak pointer object at
position \texttt{[i][j]} holds references to cache nodes of transversal elements of $U_{i-1}$ in $U_i$ in representation $j$. 
\end{description}
 }

 
\subsection{\textcolor{Chapter }{The global record \texttt{ORB}}}\logpage{[ 8, 3, 2 ]}
\hyperdef{L}{X855663F5790EA2D0}{}
{
  In this section we describe the global record \texttt{ORB}, which contains some entries that can tune the behaviour of the
orbit-by-suborbit functions. The record has the following components: 
\begin{description}
\item[{\texttt{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$.
\item[{\texttt{ORBITBYSUBORBITDEPTH}}] This integer indicates how many recursive calls to \texttt{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 \texttt{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 \texttt{OrbitBySuborbit} (\ref{OrbitBySuborbit}) or \texttt{OrbitBySuborbitKnownSize} (\ref{OrbitBySuborbitKnownSize}) so the user should usually not have to worry about it at all. 
\item[{\texttt{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 \texttt{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. 
\item[{\texttt{PLEASEEXITNOW}}] This value is usually set to \texttt{false}. Setting it to \texttt{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 \texttt{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. 
\item[{\texttt{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. 
\item[{\texttt{TRIESINQUOTIENT} and \texttt{TRIESINWHOLESPACE}}] The bootstrap routines \texttt{OrbitBySuborbitBootstrapForVectors} (\ref{OrbitBySuborbitBootstrapForVectors}), \texttt{OrbitBySuborbitBootstrapForLines} (\ref{OrbitBySuborbitBootstrapForLines}) and \texttt{OrbitBySuborbitBootstrapForSpaces} (\ref{OrbitBySuborbitBootstrapForSpaces}) 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 \texttt{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 \texttt{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. 
\end{description}
 }

 }

 
\section{\textcolor{Chapter }{Lists of orbit-by-suborbit objects}}\logpage{[ 8, 4, 0 ]}
\hyperdef{L}{X8696CFD08768508D}{}
{
  There are a few functions that help to administrate lists of
orbit-by-suborbits. 

\subsection{\textcolor{Chapter }{InitOrbitBySuborbitList}}
\logpage{[ 8, 4, 1 ]}\nobreak
\hyperdef{L}{X7FB77D827E31AE24}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{InitOrbitBySuborbitList({\slshape setup, nrrandels})\index{InitOrbitBySuborbitList@\texttt{InitOrbitBySuborbitList}}
\label{InitOrbitBySuborbitList}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 a list of orbit-by-suborbits object 



 Creates an object that stores a list of orbit-by-suborbits. The argument \mbox{\texttt{\slshape setup}} must be an orbit-by-suborbit setup record and \mbox{\texttt{\slshape 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. }

 

\subsection{\textcolor{Chapter }{IsVectorInOrbitBySuborbitList}}
\logpage{[ 8, 4, 2 ]}\nobreak
\hyperdef{L}{X87CB441882F43F62}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsVectorInOrbitBySuborbitList({\slshape v, obsol})\index{IsVectorInOrbitBySuborbitList@\texttt{IsVectorInOrbitBySuborbitList}}
\label{IsVectorInOrbitBySuborbitList}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 \texttt{fail} or an integer 



 Checks probabilistically, if the element \mbox{\texttt{\slshape v}} lies in one of the partially enumerated orbit-by-suborbits in the
orbit-by-suborbit list object \mbox{\texttt{\slshape obsol}}. If yes, the number of that orbit-by-suborbit is returned and the answer is
guaranteed to be correct. If the answer is \texttt{fail} there is a small probability that the point actually lies in one of the orbits
but this could not be shown. }

 

\subsection{\textcolor{Chapter }{OrbitsFromSeedsToOrbitList}}
\logpage{[ 8, 4, 3 ]}\nobreak
\hyperdef{L}{X7D82CE2579A50B2C}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{OrbitsFromSeedsToOrbitList({\slshape obsol, li})\index{OrbitsFromSeedsToOrbitList@\texttt{OrbitsFromSeedsToOrbitList}}
\label{OrbitsFromSeedsToOrbitList}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 nothing 



 Takes the elements in the list \mbox{\texttt{\slshape 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 \mbox{\texttt{\slshape 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 \mbox{\texttt{\slshape obsol}}. 

 This function is a good way to quickly enumerate a greater number of
orbit-by-suborbits. }

 

\subsection{\textcolor{Chapter }{VerifyDisjointness}}
\logpage{[ 8, 4, 4 ]}\nobreak
\hyperdef{L}{X83A306918461D700}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{VerifyDisjointness({\slshape obsol})\index{VerifyDisjointness@\texttt{VerifyDisjointness}}
\label{VerifyDisjointness}
}\hfill{\scriptsize (function)}}\\
\textbf{\indent Returns:\ }
 \texttt{true} or \texttt{false} 



 This function checks deterministically, whether the orbit-by-suborbits in the
orbit-by-suborbit list object \mbox{\texttt{\slshape obsol}} are disjoint or not and returns the corresponding boolean value. This is not a
Monte-Carlo algorithm. If the answer is \texttt{false}, the function writes out, which orbits are in fact identical. }

 

\subsection{\textcolor{Chapter }{Memory (forobsol)}}
\logpage{[ 8, 4, 5 ]}\nobreak
\hyperdef{L}{X7ED405017E3A56CD}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Memory({\slshape obsol})\index{Memory@\texttt{Memory}!forobsol}
\label{Memory:forobsol}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 an integer 



 Returns the total memory used for all orbit-by-suborbits in the
orbit-by-suborbit-list \mbox{\texttt{\slshape obsol}}. Precomputation data is not included, ask the setup object instead. }

 

\subsection{\textcolor{Chapter }{TotalLength (forobsol)}}
\logpage{[ 8, 4, 6 ]}\nobreak
\hyperdef{L}{X7D52885787865E81}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{TotalLength({\slshape obsol})\index{TotalLength@\texttt{TotalLength}!forobsol}
\label{TotalLength:forobsol}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 an integer 



 Returns the total number of points stored in all orbit-by-suborbits in the
orbit-by-suborbit-list \mbox{\texttt{\slshape obsol}}. }

 

\subsection{\textcolor{Chapter }{Size (forobsol)}}
\logpage{[ 8, 4, 7 ]}\nobreak
\hyperdef{L}{X7C4255287D394742}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Size({\slshape obsol})\index{Size@\texttt{Size}!forobsol}
\label{Size:forobsol}
}\hfill{\scriptsize (method)}}\\
\textbf{\indent Returns:\ }
 an integer 



 Returns the total number of points in the orbit-by-suborbit-list \mbox{\texttt{\slshape obsol}}. }

 

\subsection{\textcolor{Chapter }{SavingFactor (forobsol)}}
\logpage{[ 8, 4, 8 ]}\nobreak
\hyperdef{L}{X7BFE12DE85CCE143}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{SavingFactor({\slshape obsol})\index{SavingFactor@\texttt{SavingFactor}!forobsol}
\label{SavingFactor:forobsol}
}\hfill{\scriptsize (operation)}}\\
\textbf{\indent Returns:\ }
 an integer 



 Returns the quotient of the total number of points stored in all
orbit-by-suborbits in the orbit-by-suborbit-list \mbox{\texttt{\slshape 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! }

 }

  }

  
\chapter{\textcolor{Chapter }{Finding nice quotients}}\label{quotfinder}
\logpage{[ 9, 0, 0 ]}
\hyperdef{L}{X7BDEA65183A3AE7B}{}
{
  This chapter will be written when the \textsf{chop} is documented and released, because the functions to be described here depend
on that package. 

 For the moment it should be enough to say that the functions to be described
here are used to find nice quotient modules for the orbit algorithms using the
orbit-by-suborbit techniques described in Chapter \ref{bysuborbit}.  }

  
\chapter{\textcolor{Chapter }{Examples}}\label{examples}
\logpage{[ 10, 0, 0 ]}
\hyperdef{L}{X7A489A5D79DA9E5C}{}
{
  To actually run an orbit enumeration by suborbits, we have to collect some
insight into the structure of the group under consideration and into its
representation theory. In general, preparing the input data is more of an art
than a science. The mathematical details are described in \cite{MNW}. 

 In Section \ref{M11example} we present a small example of the usage of the orbit-by-suborbit machinery. We
use the sporadic simple Mathieu group $M_{{11}}$ acting projectively on its irreducible module of dimension 24 over the field
with 3 elements. 

 In Section \ref{Fi23example} we present another example of the usage of the orbit-by-suborbit programs. In
this example we determine 35 of the 36 double coset representatives of the
sporadic simple Fischer group $Fi_{{23}}$ with respect to its seventh maximal subgroup. 

 In Section \ref{Co1example} we present a bigger example of the usage of the orbit-by-suborbit machinery.
In this example the orbit lengths of the sporadic simple Conway group $Co_{{1}}$ acting in in its irreducible projective representation over the field with $5$ elements in dimension $24$ are determined, which were previously unknown. These orbit lengths were needed
to rule out a case in \cite{LongOrbits}. 

 In Section \ref{Borbit} we present as an extended worked example how to enumerate the smallest
non-trivial orbit of the sporadic simple Baby Monster group $B$. We give a log of a \textsf{GAP} session with explanations in between, being intended to illustrate a few of
the tools which are available in the \textsf{orb} package as well as in related packages. Actually, the \textsf{orb} package has also been applied to two much larger permutation actions of $B$, namely its action on its 2B involutions, having degree $\approx 1.2\cdot 10^{13}$, and its action on the cosets of a maximal subgroup isomorphic to $Fi_{23}$, having degree $\approx 1.0\cdot 10^{15}$; for details see \cite{MueBMCo2} and \cite{MNW}, respectively. 

 Note that for all this to work you have to acquire and install the packages \textsf{IO}, \textsf{cvec}, and \textsf{atlasrep}, and for Section \ref{Borbit} you additionally need the packages \textsf{chop} and \textsf{genss}. 

   
\section{\textcolor{Chapter }{The Mathieu group $M_{{11}}$ acting in dimension $24$}}\label{M11example}
\logpage{[ 10, 1, 0 ]}
\hyperdef{L}{X7CD0993B7A8F5DA5}{}
{
  The example in this section is very small but our intention is that everything
can still be analysed and looked at more or less by hand. We want to enumerate
orbits of the Mathieu group $M_{{11}}$ acting projectively on its irreducible module of dimension 24 over the field
with 3 elements. All the files for this example are located in the \texttt{examples/m11PF3d24} subdirectory of the \textsf{orb} package. Then you simply run the example in the following way: 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> ReadPackage("orb","examples/m11PF3d24/M11OrbitOnPF3d24.g");
  ...
  gap> o := OrbitBySuborbit(setup,v,3,3,2,100);
  ...
  #I  OrbitBySuborbit found 100% of a U3-orbit of size 7 920
  ...
\end{Verbatim}
 

 Everything works instantly as it would have without the orbit-by-suborbits
method. (Depending on whether the matrix and permutation generators for $M_{{11}}$ are already stored locally, some time might be needed to fetch them.) The
details of this computation can be directly read off from the code in the file \texttt{M11OrbitOnPF3d24.g}: 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  LoadPackage("orb");
  LoadPackage("io");
  LoadPackage("cvec");
  LoadPackage("atlasrep");
  
  SetInfoLevel(InfoOrb,2);
  pgens := AtlasGenerators("M11",1).generators;
  
  gens := AtlasGenerators("M11",14).generators;
  cgens := List(gens,CMat);
  basech := CVEC_ReadMatFromFile(Filename(DirectoriesPackageLibrary("orb",""),
            "examples/m11PF3d24/m11basech.cmat"));
  basechi := basech^-1;
  cgens := List(cgens,x->basech*x*basechi);
  
  ReadPackage("orb","examples/m11PF3d24/m11slps.g");
  pgu2 := ResultOfStraightLineProgram(s2,pgens);
  pgu1 := ResultOfStraightLineProgram(s1,pgu2);
  cu2 := ResultOfStraightLineProgram(s2,cgens);
  cu1 := ResultOfStraightLineProgram(s1,cu2);
  
  setup := OrbitBySuborbitBootstrapForLines(
           [cu1,cu2,cgens],[pgu1,pgu2,pgens],[20,720,7920],[5,11],rec());
  setup!.stabchainrandom := 900;
  
  v := ZeroMutable(cgens[1][1]);
  Randomize(v);
  ORB_NormalizeVector(v); 
  
  Print("Now do\n  o := OrbitBySuborbit(setup,v,3,3,2,100);\n");
\end{Verbatim}
 

 We are using two helper subgroups $U_1 < U_2 < M_{11} $, where $U_2\cong A_2.2$ is the largest maximal subgroup of $M_{11}$, having order $720$, and $U_2\cong 5:4$ is a maximal subgroup of $U_2$ of order $20$, see \cite{CCN85} or the \textsf{CTblLib} package. The quotient spaces we use for the helper subgroups have dimensions $5$ and $11$ respectively. Straight line programs to compute generators of the helper
subgroups in terms of the given generators of $M_{11}$, and an appropriate basis exhibiting the quotients, have already been
computed, and are stored in the files \texttt{m11slps.g} and \texttt{m11basech.cmat}, respectively. (In Section \ref{Borbit} we show in detail how such straight line programs and suitable bases can be
found using the tools available in in the \textsf{orb} package.) The command \texttt{OrbitBySuborbitBootstrapForLines} invokes the precomputation, and in particular says that we want to use
projective action. }

  
\section{\textcolor{Chapter }{The Fischer group $Fi_{{23}}$ acting in dimension $1494$ }}\label{Fi23example}
\logpage{[ 10, 2, 0 ]}
\hyperdef{L}{X7C6E7A1A7CC73262}{}
{
  The example in this section shows how to compute 35 of the 36 double coset
representatives of the Fischer group $Fi_{{23}}$ with respect to its the seventh maximal subgroup $H\cong 3_+^{1+8}.2_-^{1+6}.3_+^{1+2}.2S_4$, which has order $3\,265\,173\,504\approx 3.2\cdot 10^9$ and index $[Fi_{{23}}\colon H]=1\,252\,451\,200 \approx 1.3 \cdot 10^9$, see \cite{CCN85} or the \textsf{CTblLib} package. All the files for this example are located in the \texttt{examples/fi23m7} subdirectory of the \textsf{orb} package. You simply run the example in the following way: 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> ReadPackage("orb","examples/fi23m7/GOrbitByKOrbitsPrepare.g");
  ...
  gap> ReadPackage("orb","examples/fi23m7/GOrbitByKOrbitsSearch35.g");
  ...
\end{Verbatim}
 

 We will not go into the details of the computation here, but they can be read
off directly from the code in the files in that directory. In the first part,
run by the file \texttt{GOrbitByKOrbitsPrepare.g}, we prepare the necessary input data, by using similar techniques as
described at length in Section \ref{Borbit}. (Actually, this example has been dealt with before the advent of the
packages \textsf{chop} and \textsf{genss}, hence we are using appropriate private code instead.) We are using two
helper subgroups $U_1 < U_2 < H < Fi_{{23}}$, being $3$-subgroups of $H$ of order $81$ and $6561$, respectively. The 1494-dimensional irreducible representation of $Fi_{{23}}$ over the field with 2 elements contains a vector that is fixed by $H$, such that the action on its $Fi_{{23}}$-orbit is isomorphic to the action on the cosets of $H$. 

 The second part, in the file \texttt{GOrbitByKOrbitsSearch35.g}, is the actual enumeration of $H$-orbits: 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  setup := OrbitBySuborbitBootstrapForVectors(
           [cu1gens,cu2gens,cngens],[u1gensp,u2gensp,ngensp],
           [81,6561,3265173504],[10,30],rec());
  obsol := InitOrbitBySuborbitList(setup,40);
  l := Orb(cggens,v,OnRight,rec(schreier := true));
  Enumerate(l,100000);
  OrbitsFromSeedsToOrbitList(obsol,l);
  origseeds := List(obsol,OrigSeed); 
  positions :=  List(origseeds,x->Position(l,x));
  words := List(positions,x->TraceSchreierTreeForward(l,x));
\end{Verbatim}
 Note that this computation finds only 35 of the 36 double coset
representatives. The last corresponds to a very short suborbit which is very
difficult to find. Knowing the number of missing points, we guess the
stabiliser in $H$ of a missing representative, and find the latter amongst the fixed points of
the stabiliser. We can then choose the one which lies in the $G$-orbit we have nearly enumerated above. 

 These double coset representatives were needed to determine the 2-modular
character table of $Fi_{{23}}$. Details of this can be found in \cite{Fi23mod2}. }

  
\section{\textcolor{Chapter }{The Conway group $Co_1$ acting in dimension $24$ }}\label{Co1example}
\logpage{[ 10, 3, 0 ]}
\hyperdef{L}{X7D7BDBF87E7C45ED}{}
{
  The example in this section shows how to compute all suborbit lengths of the
Conway group $Co_1$, in its irreducible projective action on a module of dimension 24 over the
field with 5 elements. All the files for this example are located in the \texttt{examples/co1F5d24} subdirectory of the \textsf{orb} package. Then you simply run the example in the following way: 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> ReadPackage("orb","examples/co1F5d24/Co1OrbitOnPF5d24.g");
  ...
  gap> ReadPackage("orb","examples/co1F5d24/Co1OrbitOnPF5d24.findall.g");
  ...
\end{Verbatim}
 

 We will not go into the details of the first part of the computation here, as
they are very similar to those reproduced in Section \ref{M11example}, and can be directly read off from the code in the file \texttt{Co1OrbitOnPF5d24.g}: We are using three helper subgroups $U_1 < U_2 < U_3 < Co_1$, where $Co_1$ has order $4\,157\,776\,806\,543\,360\,000\approx 4.2\cdot 10^{18}$, see \cite{CCN85} or the \textsf{CTblLib} package, and where $U_3\cong 2_+^{1+8}.O_8(2)$ is the fifth maximal subgroup of $Co_1 $, having order $89\,181\,388\,800\approx 8.9\cdot 10^{10}$, while $U_2\cong [2^8]\colon S_6(2)$ is a maximal subgroup of $U_3$ of order $371\,589\,120\approx 3.7\cdot 10^{8}$, and $U_1\cong 2^6\colon L_3(2)$ is a maximal subgroup of $S_6(2)$ of order $10\,752\approx 1.1\cdot 10^{4}$. The projective action comes from the irreducible 24-dimensional linear
representation of the Schur cover $2.Co_1$ of $Co_1$, which by \cite{Jansen} is the smallest faithful representation of $2.Co_1$ over the field GF(5), and the quotient spaces we use for the helper subgroups
have dimensions $8$, $8$ and $16$ respectively. 

 The details of the second part can be directly read off from the code in the
file \texttt{Co1OrbitOnPF5d24.findall.g}: 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  oo := InitOrbitBySuborbitList(setup,80);
  l := MakeRandomLines(v,1000);
  OrbitsFromSeedsToOrbitList(oo,l);
  intervecs := CVEC_ReadMatFromFile(Filename(DirectoriesPackageLibrary("orb",""),
               "examples/co1F5d24/co1interestingvecs.cmat"));
  OrbitsFromSeedsToOrbitList(oo,intervecs);
  Length(oo!.obsos);
  Sum(oo!.obsos,Size);
  (5^24-1)/(5-1);
\end{Verbatim}
 

 Note that this example needs about 2GB of main memory on a 32bit machine and
probably nearly 4GB on a 64bit machine. However, the orbit lengths were
previously unknown before they were computed with this program. The orbit
lengths were needed to rule out a case in \cite{LongOrbits}. }

  
\section{\textcolor{Chapter }{The Baby Monster $B$ acting on its 2A involutions}}\label{Borbit}
\logpage{[ 10, 4, 0 ]}
\hyperdef{L}{X781209EE7C9D3E0E}{}
{
  The example in this section shows how to enumerate the smallest non-trivial
orbit of the Baby Monster group $B$. All the files for this example are located in the \texttt{examples/bmF2d4370} subdirectory of the \textsf{orb} package. You may simply run the example in the following way: 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> ReadPackage("orb","examples/bmF2d4370/BMOrbitOnF2d4370partI.g");
  ...
  gap> ReadPackage("orb","examples/bmF2d4370/BMOrbitOnF2d4370partII.g");
  ... 
\end{Verbatim}
 

 In the sequel we comment in detail on how the necessary input data actually is
prepared. We begin by loading the packages we are going to use.  
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> LoadPackage("orb");
  ...
  gap> LoadPackage("io");
  ...
  gap> LoadPackage("cvec");
  ...
  gap> LoadPackage("atlasrep");
  ...
  gap> LoadPackage("chop");
  ...
  gap> LoadPackage("genss");
  ...  
\end{Verbatim}
 

 The one-point stabilisers associated to the smallest non-trivial orbit of $B$ are its largest maximal subgroups $E \cong 2.^2E_6(2).2$, which are the centralisers of its 2A involutions. Here $E$ is a bicyclic extension of the twisted Lie type group $^2E_6(2)$, and has index $[B\colon E]=13\,571\,955\,000 \approx 1.4 \cdot 10^{10}$, see \cite{CCN85} or the \textsf{CTblLib} package. 

 We first try to find a matrix representation of $B$ such that the $B$-orbit we look for is realised as a set of vectors in the underlying vector
space. The smallest faithful representation of $B$ over the field GF(2), by \cite{Jansen} having dimension 4370, springs to mind. Explicit matrices in terms of standard
generators in the sense of \cite{Wil96} are available in \cite{AGR}, and are accessibe through the \textsf{atlasrep} package. Moreover, we find generators of $E$ by applying a straight line program, also available in the \textsf{atlasrep} package, expressing generators of $E$ in terms of the generators of $B$. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> gens := AtlasGenerators("B",1).generators;
  [ <an immutable 4370x4370 matrix over GF2>, 
    <an immutable 4370x4370 matrix over GF2> ]
  gap> bgens := List(gens,CMat);
  [ <cmat 4370x4370 over GF(2,1)>, <cmat 4370x4370 over GF(2,1)> ] 
  gap> slpbtoe := AtlasStraightLineProgram("B",1).program;;
  gap> egens := ResultOfStraightLineProgram(slpbtoe,bgens);
  [ <cmat 4370x4370 over GF(2,1)>, <cmat 4370x4370 over GF(2,1)> ] 
\end{Verbatim}
 

 We look for a non-zero vector being fixed by both generators of $E$. It turns out that the latter have a common fixed space of dimension 1. Then,
since $E$ is a maximal subgroup, the stabiliser in $B$ of the non-zero vector $v$ in that fixed space coincides with $E$. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> x := egens[1]-egens[1]^0;;
  gap> nsx := NullspaceMat(x);
  <immutable cmat 2202x4370 over GF(2,1)>
  gap> y := nsx * (egens[2]-egens[2]^0);;
  gap> nsy := NullspaceMat(y);
  <immutable cmat 1x2202 over GF(2,1)>
  gap> v := nsy[1]*nsx;
  <immutable cvec over GF(2,1) of length 4370> 
\end{Verbatim}
 

 Storing eight elements of GF(2) into 1 byte, to store a vector of length 4370
needs 547 bytes plus some organisational overhead resulting in about 580
bytes, hence to store the full $B$-orbit of $v$ we need $580 \cdot [B\colon E] \approx 7.9 \cdot 10^{12}$ bytes. Hence we try to find helper subgroups suitable to achieve a saving
factor of $\approx 10^4$, i. e. allowing to store only one out of $\approx 10^4$ vectors. To this end, we look for a pair $U_1<U_2$ of helper subgroups such that $|U_2| \approx 10^5$, where we take into account that typically the overall saving factor achieved
is somewhat smaller than the order of the largest helper subgroup.  

 By \cite{CCN85}, and a few computations with subgroup fusions using the \textsf{CTblLib} package, the derived subgroup $E' \cong 2.{}^2E_6(2)$ of $E$ turns out to possess maximal subgroups $2 \times Fi_{{22}}$ and $2.Fi_{{22}}$, where $Fi_{{22}}$ denotes one of the sporadic simple Fischer groups, and where the former
constitute a unique conjugacy class with associated normalizers in $E$ of shape $2 \times Fi_{{22}}.2$, while the latter consist of two conjugacy classes being self-normalising and
interchanged by $E$. 

 Now $Fi_{{22}}$ has a unique conjugacy class of maximal subgroups $M_{{12}}$, where the latter denotes one of the sporadic simple Mathieu groups; the
subgroups $M_{{12}}$ lift to a unique conjugacy class of subgroups $M_{{12}}$ of $2.Fi_{{22}}$, which turn out to constitute a conjugacy class of subgroups of $E$ different from the subgroups $M_{{12}}$ being contained in $Fi_{{22}}$. Anyway, we have $|M_{{12}}|=95\,040$, hence $U_2=M_{{12}}$ seems to be a good candidate for the larger helper subgroup. In particular,
there is a unique conjugacy class of maximal subgroups $L_2(11)$ of $M_{{12}}$, and since $|L_2(11)|=660$ and $[M_{{12}}\colon L_2(11)]=144$ letting $U_1=L_2(11)$ seems to be a good candidate for the smaller helper subgroup. Recall that $U_1$ and $U_2$ are useful helper subgroups only if we are able to find suitable quotient
modules allowing for the envisaged saving factor. 

 To find $U_1$ and $U_2$, we first try to find a subgroup $Fi_{{22}}$ or $2.Fi_{{22}}$ of $E$. We start a random search, aiming at finding standard generators of either $Fi_{{22}}$ or $2.Fi_{{22}}$, and we use \texttt{GeneratorsWithMemory} in order to be able to express the generators found as words in the generators
of $E$. To accelerate computations we first construct a small representation of $E$; by \cite{Jansen} the smallest faithful irreducible representation of $Fi_{{22}}$ over GF(2) has dimension 78, hence we cannot do better for $E$; note that the latter is a representation of $\overline{E}:=E/Z(E) \cong {}^2E_6(2).2$. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> SetInfoLevel(InfoChop,2);
  gap> m := Module(egens);
  <module of dim. 4370 over GF(2)>
  gap> r := Chop(m);
  ...
  rec( ischoprecord := true, 
    db := [ <abs. simple module of dim. 78 over GF(2)>, 
            <trivial module of dim. 1 over GF(2)>, 
            <abs. simple module of dim. 1702 over GF(2)>, 
            <abs. simple module of dim. 572 over GF(2)> ], 
    mult := [ 5, 4, 2, 1 ], acs := [ 1, 2, 3, 1, 4, 1, 1, 2, 2, 3, 1, 2 ], 
    module := <reducible module of dim. 4370 over GF(2)> )
  gap> i := Position(List(r.db,Dimension),78);;
  gap> egens78 := GeneratorsWithMemory(RepresentingMatrices(r.db[i]));
  [ <<immutable cmat 78x78 over GF(2,1)> with mem>, 
    <<immutable cmat 78x78 over GF(2,1)> with mem> ] 
\end{Verbatim}
 

 By \cite{AGR}, standard generators $a,b$ of $Fi_{{22}}$ are given as follows: $a$ is an element of the 2A conjugacy class of $Fi_{{22}}$, and $b$, $ab$, and $(ab)^4bab(abb)^2$ have order 13, 11, and 12, respectively; standard generators of $2.Fi_{{22}}$ are lifts of standard generators of $Fi_{{22}}$ having the same order fingerprint. The 2A conjugacy class of $Fi_{{22}}$ fuses into the 2A conjugacy class of $\overline{E}$, where the latter is obtained as the 11-th power of the unique conjugacy
class of elements of order 22, and $\overline{E}$ has only one conjugacy class of elements of order 13. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> o := Orb(egens78,StripMemory(egens78[1])^0,OnRight,rec(schreier := true,
  >             lookingfor := function(o,x) return Order(x)=22; end));
  <open orbit, 1 points with Schreier tree looking for sth.>
  gap> Enumerate(o);
  <open orbit, 393 points with Schreier tree looking for sth.>
  gap> word := TraceSchreierTreeForward(o,PositionOfFound(o));
  [ 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 2 ]
  gap> g2a := Product(egens78{word})^11;
  <<immutable cmat 78x78 over GF(2,1)> with mem>
  gap> o := Orb(egens78,StripMemory(egens78[1])^0,OnRight,rec(schreier := true,
  >             lookingfor := function(o,x) return Order(x)=13; end));
  <open orbit, 1 points with Schreier tree looking for sth.>
  gap> Enumerate(o);
  <open orbit, 144 points with Schreier tree looking for sth.>
  gap> word := TraceSchreierTreeForward(o,PositionOfFound(o));
  [ 1, 2, 1, 2, 1, 2, 1, 2, 2 ]
  gap> b := Product(egens78{word});
  <<immutable cmat 78x78 over GF(2,1)> with mem> 
\end{Verbatim}
 

 We search through the $\overline{E}$-conjugates of \texttt{g2a} until we find a conjugate $a$ together with $b$ fulfilling the defining conditions of standard generators of $Fi_{{22}}$, and moreover fulfilling the relations of the associated presentation of $Fi_{{22}}$ available in \cite{AGR}. 

 To find conjugates, we use the product replacement algorithm to produce pseudo
random elements of $\overline{E}$. Assuming a genuine random search, the success probability of this approach
is as follows: Letting $\overline{E'}:=E'/Z(E') \cong {}^2E_6(2)$, out of the $|\overline{E'}|/|C_{\overline{E'}}(g2a)|$ conjugates of \texttt{g2a} there are $|C_{{ \overline{E'} }}(b)|/|C_{{ \overline{E'} }}(Fi_{{22}})| =|C_{{
\overline{E'} }}(b)|$ elements together with the fixed element $b$ giving standard generators of $Fi_{{22}}$. Since $Fi_{{22}}$ has two conjugacy classes of elements of order 13, and there are three
conjugacy classes of subgroups $Fi_{{22}}$ of $\overline{E'}$, the success probability is $6 \cdot |C_{{ \overline{E'} }}(g2a)| \cdot |C_{{ \overline{E'}
}}(b)|/|\overline{E'}| \approx 2 \cdot 10^{-5}$. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> pr := ProductReplacer(egens78,rec(maxdepth := 150));
  <product replacer nrgens=2 slots=12 scramble=100 maxdepth=150 steps=0 (rattle)>
  gap> i := 0;;
  gap> repeat
  >      i := i + 1; 
  >      x := Next(pr);
  >      a := g2a^x;
  >    until IsOne((a*b)^11) and IsOne(((a*b)^4*b*a*b*(a*b*b)^2)^12) and
  >      IsOne((a*b^2)^21) and IsOne(Comm(a,b)^3) and 
  >      IsOne(Comm(a,b^2)^3) and IsOne(Comm(a,b^3)^3) and
  >      IsOne(Comm(a,b^4)^2) and IsOne(Comm(a,b^5)^3) and
  >      IsOne(Comm(a,b*a*b^2)^3) and IsOne(Comm(a,b^-1*a*b^-2)^2) and
  >      IsOne(Comm(a,b*a*b^5)^2) and IsOne(Comm(a,b^2*a*b^5)^2);
  gap> i;
  53271 
\end{Verbatim}
   

 Note that the initial state of the random number generator does influence this
randomised result: it may very well be that you see some other value for $i$. 

 Due to a presentation being available we have proved that the elements found
generate a subgroup $Fi_{{22}}$. If we had not had a presentation at hand, we might only have been able to
find elements fulfilling the defining conditions of standard generators of $Fi_{{22}}$, but still generating a subgroup of another isomorphism type. In that case,
for further checks we can use the following tools: We try to find a short
orbit of vectors, and using a randomized Schreier-Sims algorithm gives a lower
bound for the order of the group seen. However, we can use the action on the
orbit to get a homomorphism into a permutation group, allowing to prove that
the group generated indeed has $Fi_{{22}}$ as a quotient. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> S := StabilizerChain(Group(a,b),rec(TryShortOrbit := 30,
  >                                        OrbitLengthLimit := 5000));
  ...
  <stabchain size=64561751654400 orblen=3510 layer=1 SchreierDepth=8>
   <stabchain size=18393661440 orblen=2816 layer=2 SchreierDepth=7>
    <stabchain size=6531840 orblen=1680 layer=3 SchreierDepth=7>
     <stabchain size=3888 orblen=243 layer=4 SchreierDepth=5>
      <stabchain size=16 orblen=16 layer=5 SchreierDepth=2>
  gap> Size(S)=Size(CharacterTable("Fi22"));
  true 
  gap> p := Group(ActionOnOrbit(S!.orb,[a,b]));;
  gap> DisplayCompositionSeries(p);
  G (2 gens, size 64561751654400)
   | Fi(22)
  1 (0 gens, size 1) 
\end{Verbatim}
 

 We now return to our original representation.  
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> SetInfoLevel(InfoSLP,2); 
  gap> slpetofi22 := SLPOfElms([a,b]);
  <straight line program>
  gap> Length(LinesOfStraightLineProgram(slpetofi22));
  278
  gap> SlotUsagePattern(slpetofi22);;
  gap> fgens := ResultOfStraightLineProgram(slpetofi22,egens);
  ...
  [ <cmat 4370x4370 over GF(2,1)>, <cmat 4370x4370 over GF(2,1)> ] 
  gap> a := fgens[1];;
  gap> b := fgens[2];; 
  gap> IsOne(b^13);
  true
  gap> IsOne((a*b)^11);
  true
  gap> IsOne((a*b^2)^21);
  true 
\end{Verbatim}
 

 By construction the group generated by $a,b$ is $Fi_{{22}}$ or $2 \times Fi_{{22}}$ or $2.Fi_{{22}}$. Note that due to different seeds in the random number generator it is in
fact possible at this stage that you have created a different group as
displayed here! In our outcome, since $a$ has even order, and both $b$ and $ab$ have odd order, we cannot possibly have $2 \times Fi_{{22}}$; and by the presentation of $2.Fi_{{22}}$ available in \cite{AGR} the order of $ab^2$ being 21 implies that we cannot possibly have $2.Fi_{{22}}$ either. Hence we indeed have found standard generators of $Fi_{{22}}$. If we had hit one of the cases $2 \times Fi_{{22}}$ or $2.Fi_{{22}}$, we could just continue the above search until we find a subgroup $Fi_{{22}}$, or using the above order fingerprint we could easily modify the elements
found to obtain standard generators of either $Fi_{{22}}$ or $2.Fi_{{22}}$. 

 Now, standard generators of $U_2=M_{{12}}$ in terms of standard generators of $Fi_{{22}}$, and generators of $U_1=L_2(11)$ in terms of standard generators of $M_{{12}}$ are accessible in the \textsf{atlasrep} package. Note that if we had found a subgroup $2.Fi_{{22}}$ above, since $M_{{12}}$ lifts to a subgroup $2 \times M_{{12}}$ of $2.Fi_{{22}}$, it would again be easy to find standard generators of $M_{{12}}$ from the generators of $M_{{12}}$ or $2 \times M_{{12}}$ respectively provided by the \textsf{atlasrep} package. Anyway, the next task is to find good quotient modules such that the
helper subgroups have longish orbits on vectors. To this end, we restrict to $M_{{12}}$ and compute the radical series of the restricted module. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> slpfi22tom12 := AtlasStraightLineProgram("Fi22",14).program;;
  gap> slpm12tol211 := AtlasStraightLineProgram("M12",5).program;;
  gap> mgens := ResultOfStraightLineProgram(slpfi22tom12,fgens);
  [ <cmat 4370x4370 over GF(2,1)>, <cmat 4370x4370 over GF(2,1)> ]
  gap> lgens := ResultOfStraightLineProgram(slpm12tol211,mgens);
  [ <cmat 4370x4370 over GF(2,1)>, <cmat 4370x4370 over GF(2,1)> ] 
  gap> m := Module(mgens);;
  gap> r := Chop(m);;
  ...
  gap> rad := RadicalSeries(m,r.db);
  ...
  rec( 
    db := [ <abs. simple module of dim. 144 over GF(2)>, 
            <abs. simple module of dim. 44 over GF(2)>, 
            <simple module of dim. 32 over GF(2) splitting field degree 2>, 
            <abs. simple module of dim. 10 over GF(2)>, 
            <trivial module of dim. 1 over GF(2)> ],
    module := <reducible module of dim. 4370 over GF(2)>,
    basis := <immutable cmat 4370x4370 over GF(2,1)>,
    ibasis := <immutable cmat 4370x4370 over GF(2,1)>,
    cfposs := [ [ [ 1 .. 144 ], [ 145 .. 288 ], [ 289 .. 432 ], [ 433 .. 576 ],
  ...
    isotypes := [ [ 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3,
                    3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 ],
  ...
    isradicalrecord := true ) 
\end{Verbatim}
 

 We observe that there are faithful irreducible quotients of dimensions 10, 32,
44, and 144. Since we look for a quotient module such that $M_{{12}}$ has many regular orbits on vectors, we ignore the irreducible module of
dimension 10. We consider the one of dimension 32. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> i := Position(List(rad.db,Dimension),32);;
  gap> mgens32 := RepresentingMatrices(rad.db[i]);
  [ <immutable cmat 32x32 over GF(2,1)>, <immutable cmat 32x32 over GF(2,1)> ]
  gap> OrbitStatisticOnVectorSpace(mgens32,95040,30);
  Found length     95040, have now   24 orbits, average length: 93060 
\end{Verbatim}
 This is excellent indeed. Hence we pick a summand of dimension 32 in the first
radical layer, and apply the associated base change to all the generators. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> bgens := List(bgens,x->rad.basis*x*rad.ibasis);;
  gap> egens := List(egens,x->rad.basis*x*rad.ibasis);;
  gap> fgens := List(fgens,x->rad.basis*x*rad.ibasis);;
  gap> mgens := List(mgens,x->rad.basis*x*rad.ibasis);;
  gap> lgens := List(lgens,x->rad.basis*x*rad.ibasis);;
  gap> j := Position(rad.isotypes[1],i);;
  gap> l := rad.cfposs[1][j];;
  gap> Append(l,Difference([1..4370],l));
  gap> bgens := List(bgens,x->ORB_PermuteBasisVectors(x,l));;
  gap> egens := List(egens,x->ORB_PermuteBasisVectors(x,l));;
  gap> fgens := List(fgens,x->ORB_PermuteBasisVectors(x,l));;
  gap> mgens := List(mgens,x->ORB_PermuteBasisVectors(x,l));;
  gap> lgens := List(lgens,x->ORB_PermuteBasisVectors(x,l));; 
\end{Verbatim}
 

 We consider the irreducible quotient module of $M_{{12}}$ of dimension 32, whose restriction to $L_2(11)$ turns out to be is semisimple. The irreducible quotients of dimension 10 are
too small to have too many regular orbits, but the direct sum of two of them
turns out to work fine. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> lgens32 := List(lgens,x->ExtractSubMatrix(x,[1..32],[1..32]));
  [ <cmat 32x32 over GF(2,1)>, <cmat 32x32 over GF(2,1)> ]
  gap> m := Module(lgens32);;
  gap> r := Chop(m);
  ...
  gap> soc := SocleSeries(m,r.db);
  ...
  rec( issoclerecord := true,
    db := [ <simple module of dim. 10 over GF(2) splitting field degree 2>,
            <trivial module of dim. 1 over GF(2)>,
            <abs. simple module of dim. 10 over GF(2)> ],
    module := <reducible module of dim. 32 over GF(2)>,
    basis := <cmat 32x32 over GF(2,1)>, ibasis := <cmat 32x32 over GF(2,1)>,
    cfposs := [ [ [ 1 .. 10 ], [ 11 ], [ 12 ], [ 13 .. 22 ], [ 23 .. 32 ] ] ],
    isotypes := [ [ 1, 2, 2, 3, 3 ] ] )
  gap> i := Position(List(soc.db,x->[Dimension(x),DegreeOfSplittingField(x)]),
  >                                 [10,1]);;
  gap> j := Position(soc.isotypes[1],i);;
  gap> l := Concatenation(soc.cfposs[1]{[j,j+1]});;
  gap> lgens32 := List(lgens32,x->soc.basis*x*soc.ibasis);
  [ <cmat 32x32 over GF(2,1)>, <cmat 32x32 over GF(2,1)> ]
  gap> lgens20 := List(lgens32,x->ExtractSubMatrix(x,l,l));
  [ <cmat 20x20 over GF(2,1)>, <cmat 20x20 over GF(2,1)> ]
  gap> OrbitStatisticOnVectorSpace(lgens20,660,30);
  Found length       660, have now 4401 orbits, average length: 598 
\end{Verbatim}
 

 We apply the appropriate base change to all the generators. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> t := ORB_EmbedBaseChangeTopLeft(soc.basis,4370);
  <cmat 4370x4370 over GF(2,1)>
  gap> ti := ORB_EmbedBaseChangeTopLeft(soc.ibasis,4370);
  <cmat 4370x4370 over GF(2,1)>
  gap> bgens := List(bgens,x->t*x*ti);;
  gap> egens := List(egens,x->t*x*ti);;
  gap> fgens := List(fgens,x->t*x*ti);;
  gap> mgens := List(mgens,x->t*x*ti);;
  gap> lgens := List(lgens,x->t*x*ti);; 
  gap> Append(l,Difference([1..4370],l));
  gap> bgens := List(bgens,x->ORB_PermuteBasisVectors(x,l));;
  gap> egens := List(egens,x->ORB_PermuteBasisVectors(x,l));;
  gap> fgens := List(fgens,x->ORB_PermuteBasisVectors(x,l));;
  gap> mgens := List(mgens,x->ORB_PermuteBasisVectors(x,l));;
  gap> lgens := List(lgens,x->ORB_PermuteBasisVectors(x,l));; 
\end{Verbatim}
 

 Having reached the ultimate choice of basis, we recreate the fixed vector \texttt{v}. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> x := egens[1]-egens[1]^0;;
  gap> nsx := NullspaceMat(x);;
  gap> y := nsx * (egens[2]-egens[2]^0);;
  gap> nsy := NullspaceMat(y);;
  gap> v := nsy[1]*nsx;; 
\end{Verbatim}
 

 Finally we need small faithful permutation representations of the helper
subgroups. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> mgens32 := List(mgens,x->ExtractSubMatrix(x,[1..32],[1..32]));
  [ <cmat 32x32 over GF(2,1)>, <cmat 32x32 over GF(2,1)> ]
  gap> S := StabilizerChain(Group(mgens32),rec(TryShortOrbit := 10));
  ...
  <stabchain size=95040 orblen=3960 layer=1 SchreierDepth=7>
   <stabchain size=24 orblen=24 layer=2 SchreierDepth=4>
  gap> p := Group(ActionOnOrbit(S!.orb,mgens32));
  <permutation group with 2 generators>
  gap> i := SmallerDegreePermutationRepresentation(p);;
  gap> pp := Group(List(GeneratorsOfGroup(p),x->ImageElm(i,x)));
  <permutation group with 2 generators>
  gap> m12 := MathieuGroup(12);;
  gap> i := IsomorphismGroups(pp,m12);;
  gap> mpermgens := List(GeneratorsOfGroup(pp),x->ImageElm(i,x));
  [ (5,7)(6,11)(8,9)(10,12), (1,10,3)(2,11,12)(4,5,6)(7,9,8) ]
  gap> lpermgens := ResultOfStraightLineProgram(slpm12tol211,mpermgens);
  [ (1,8)(2,5)(3,9)(4,7)(6,11)(10,12), (1,8,3)(2,7,12)(4,6,9)(5,11,10) ] 
\end{Verbatim}
 

 We could just go on from here, however, sometimes it is useful to save all the
created data to disk. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> f := IO_File("data.gp","w");;
  gap> IO_Pickle(f,"seed");; 
  gap> IO_Pickle(f,v);; 
  gap> IO_Pickle(f,"generators");; 
  gap> IO_Pickle(f,bgens);; 
  gap> IO_Pickle(f,egens);; 
  gap> IO_Pickle(f,fgens);; 
  gap> IO_Pickle(f,mgens);; 
  gap> IO_Pickle(f,lgens);;
  gap> IO_Pickle(f,"permutations");; 
  gap> IO_Pickle(f,mpermgens);; 
  gap> IO_Pickle(f,lpermgens);;
  gap> IO_Close(f);; 
\end{Verbatim}
 

 This can be loaded again, in particular into a new \textsf{GAP} session, as follows. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> LoadPackage("orb");;
  ...
  gap> LoadPackage("cvec");;
  ...
  gap> f := IO_File("data.gp");
  <file fd=4 rbufsize=65536 rpos=1 rdata=0>
  gap> IO_Unpickle(f);
  "seed"
  gap> v:=IO_Unpickle(f);;
  gap> IO_Unpickle(f);
  "generators"
  gap> bgens := IO_Unpickle(f);;
  gap> egens := IO_Unpickle(f);;
  gap> fgens := IO_Unpickle(f);;
  gap> mgens := IO_Unpickle(f);;
  gap> lgens := IO_Unpickle(f);;
  gap> IO_Unpickle(f);
  "permutations"
  gap> mpermgens := IO_Unpickle(f);;
  gap> lpermgens := IO_Unpickle(f);;
  gap> IO_Close(f);; 
\end{Verbatim}
 

 Now we are prepared to actually run the orbit enumeration. Note that for the
following memory estimates we assume that we are running things on a 64bit
machine. On a 32bit machine the overhead is smaller. We expect that all the
vectors in the smaller quotient of dimension 20 will enumerated; needing 3
bytes per vector for the actual data which results in 40 bytes including
overhead, this amounts to $40 \cdot 2^{20} \approx 42$ MB of memory space. Since $2^{32} \approx 4.3 \cdot 10^9$ is less than $[B\colon E]$, we also expect that the larger quotient of dimension 32 will be enumerated
completely, by $L_2(11)$-orbits; needing 4 bytes per vector for the actual data resulting in 40 bytes
including overhead, and assuming a saving factor as suggested by \texttt{OrbitStatisticOnVectorSpace} yields an estimated memory requirement of $40 \cdot 2^{32} \cdot 1/598 \approx 287$ MB. For the large $B$-orbit, being enumerated by $M_{{12}}$-orbits, we similarly get an estimated memory requirement of $584 \cdot [B\colon E] \cdot 1/93060 \approx 85$ MB. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  gap> setup := OrbitBySuborbitBootstrapForVectors(
  >             [lgens,mgens,bgens],[lpermgens,mpermgens,[(),()]],
  >             [660,95040,4154781481226426191177580544000000],[20,32],rec());
  #I  Calculating stabilizer chain for whole group...
  #I  Trying smaller degree permutation representation for U2...
  #I  Trying smaller degree permutation representation for U1...
  #I  Enumerating permutation base images of U_1...
  #I  Looking for U1-coset-recognising U2-orbit in factor space...
  #I  OrbitBySuborbit found 100% of a U2-orbit of size 95 040
  #I  Found 144 suborbits (need 144)
  <setup for an orbit-by-suborbit enumeration, k=2>
  gap> o := OrbitBySuborbitKnownSize(setup,v,3,3,2,51,13571955000);
  #I  OrbitBySuborbit found 100% of a U2-orbit of size 1
  #I  OrbitBySuborbit found 100% of a U2-orbit of size 23 760
  ...
  #I  OrbitBySuborbit found 51% of a U3-orbit of size 13 571 955 000
  <orbit-by-suborbit size=13571955000 stabsize=306129918735099415756800 (
  51%) saving factor=56404> 
\end{Verbatim}
 

 Indeed the saving factor actually achieved is smaller than the best possible
estimate given above, but it still has the same order of magnitude. }

      }

 \def\bibname{References\logpage{[ "Bib", 0, 0 ]}
\hyperdef{L}{X7A6F98FD85F02BFE}{}
}

\bibliographystyle{alpha}
\bibliography{orb}

\def\indexname{Index\logpage{[ "Ind", 0, 0 ]}
\hyperdef{L}{X83A0356F839C696F}{}
}


\printindex

\newpage
\immediate\write\pagenrlog{["End"], \arabic{page}];}
\immediate\closeout\pagenrlog
\end{document}