% This file was created automatically from grpperm.msk.
% DO NOT EDIT!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A  grpperm.msk                 GAP documentation            Alexander Hulpke
%A                                                           Heiko Theissen
%A                                                           Akos Seress
%%
%A  @(#)$Id: grpperm.msk,v 1.39.2.1 2007/08/28 12:58:51 gap Exp $
%%
%Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
%Y  Copyright (C) 2002 The GAP Group
%%
\Chapter{Permutation Groups}

\>IsPermGroup( <obj> ) C

A permutation group is a  group of permutations on  a finite set
$\Omega$ of  positive integers. {\GAP} does *not*  require the user to
specify the operation domain  $\Omega$ when a permutation  group is
defined.


\beginexample
gap> g:=Group((1,2,3,4),(1,2));
Group([ (1,2,3,4), (1,2) ])
\endexample

Permutation groups are groups and therefore all operations for groups (see
Chapter~"Groups") can be applied to them. In many cases special methods are
installed for permutation groups that make computations more effective.

%%  The code for the computation and verification stabilizer chains, for
%%  composition series and the radical is due to \'Akos Seress.
%%  Heiko Thei{\ss}en wrote the backtrack routines which are used to compute for
%%  example centralizers, normalizers and conjugating elements.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{The Natural Action}

The functions `MovedPoints', `NrMovedPoints', `LargestMovedPoint',
and `SmallestMovedPoint' are defined for arbitrary collections of
permutations (see~"Moved Points of Permutations"),
in particular they can be applied to permutation groups.
\beginexample
gap> g:= Group( (2,3,5,6), (2,3) );;
gap> MovedPoints( g );  NrMovedPoints( g );
[ 2, 3, 5, 6 ]
4
gap> LargestMovedPoint( g );  SmallestMovedPoint( g );
6
2
\endexample

The action of a permutation group on the positive integers is a group
action (via the acting function `OnPoints').
Therefore all action functions can be applied
(see the Chapter~"Group Actions"),
for example `Orbit', `Stabilizer', `Blocks', `IsTransitive', `IsPrimitive'.

If one has a list of group generators and is interested in the moved points
(see above) or orbits, it may be useful to avoid the explicit construction
of the group for efficiency reasons.
For the special case of the action of permutations on positive integers
via `^', the following functions are provided for this purpose.

\>OrbitPerms( <perms>, <pnt> ) F

returns the orbit of the positive integer <pnt>
under the group generated by the permutations in the list <perms>.


\>OrbitsPerms( <perms>, <D> ) F

returns the list of orbits of the positive integers in the list <D>
under the group generated by the permutations in the list <perms>.


\beginexample
gap> OrbitPerms( [ (1,2,3)(4,5), (3,6) ], 1 );
[ 1, 2, 3, 6 ]
gap> OrbitsPerms( [ (1,2,3)(4,5), (3,6) ], [ 1 .. 6 ] );
[ [ 1, 2, 3, 6 ], [ 4, 5 ] ]
\endexample

Similarly, several functions concerning the natural action of
permutation groups address stabilizer chains (see~"Stabilizer Chains")
rather than permutation groups themselves, for example `BaseStabChain'
(see~"BaseStabChain").


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Computing a Permutation Representation}

\>IsomorphismPermGroup( <G> ) A

returns an isomorphism $\varphi$ from the group <G> onto
a permutation group <P> which is isomorphic to <G>.
The method will select a suitable permutation representation.


\beginexample
gap> g:=SmallGroup(24,12);
<pc group of size 24 with 4 generators>
gap> iso:=IsomorphismPermGroup(g);
<action isomorphism>
gap> Image(iso,g.3*g.4);
(1,4)(2,3)(5,8)(6,7)(9,12)(10,11)(13,16)(14,15)(17,20)(18,19)(21,24)(22,23)
\endexample

In many cases the permutation representation constructed by
`IsomorphismPermGroup' is regular.

\>SmallerDegreePermutationRepresentation( <G> ) F

Let <G> be a permutation group that acts transitively
on its moved points.
`SmallerDegreePermutationRepresentation' tries to find a faithful
permutation representation of smaller degree.
The result is a group homomorphism onto a permutation group,
in the worst case this is the identity mapping on <G>.

Note that the result is not guaranteed to be a faithful permutation
representation of smallest degree,
or of smallest degree among the transitive permutation representations
of <G>.
Using {\GAP} interactively, one might be able to choose subgroups
of small index for which the cores intersect trivially;
in this case, the actions on the cosets of these subgroups give rise to
an intransitive permutation representation
the degree of which may be smaller than the original degree.

The methods used might involve the use of random elements and the
permutation representation (or even the degree of the representation) is
not guaranteed to be the same for different calls of
`SmallerDegreePermutationRepresentation'.


\beginexample
gap> image:= Image( iso );;  NrMovedPoints( image );
24
gap> small:= SmallerDegreePermutationRepresentation( image );;
gap> Image( small );
Group([ (2,3), (2,4,3), (1,3)(2,4), (1,2)(3,4) ])
\endexample

% gap> p:=Group((1,2,3,4,5,6),(1,2));;p:=Action(p,AsList(p),OnRight);;
% gap> Length(MovedPoints(p));
% 720
% gap> q:=SmallerDegreePermutationRepresentation(p);;
% gap> Length(MovedPoints(Image(q)));
% 6


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Symmetric and Alternating Groups}

The commands `SymmetricGroup' and `AlternatingGroup' (see~"Basic Groups")
construct symmetric and alternating permutation groups.
{\GAP} can also detect whether a given permutation group is a symmetric
or alternating group on the set of its moved points;
if so then the group is called a *natural* symmetric or alternating group,
respectively.

\>IsNaturalSymmetricGroup( <group> ) P

A group is a natural symmetric group if it is  a permutation group acting
as symmetric group on its moved points.


\>IsNaturalAlternatingGroup( <group> ) P

A   group is a  natural  alternating group if  it is  a permutation group
acting as alternating group on its moved points.



For groups that are known to be natural symmetric or natural alternating
groups, very efficient methods for computing membership, conjugacy classes,
Sylow subgroups etc.~are used.
\beginexample
gap> g:=Group((1,5,7,8,99),(1,99,13,72));;
gap> IsNaturalSymmetricGroup(g);
true
gap> g;
Sym( [ 1, 5, 7, 8, 13, 72, 99 ] )
gap> IsNaturalSymmetricGroup( Group( (1,2)(4,5), (1,2,3)(4,5,6) ) );
false
\endexample

The following functions can be used to check whether a given group
(not necessarily a permutation group)
is isomorphic to a symmetric or alternating group.

There are no methods yet for IsSymmetricGroup and IsAlternatingGroup!

\>IsSymmetricGroup( <group> ) P

is `true' if the group <group> is isomorphic to a natural symmetric group.


\>IsAlternatingGroup( <group> ) P

Such a group is a group isomorphic to a natural alternating group.




\>SymmetricParentGroup( <grp> ) A

For a permutation group <grp> this function returns the symmetric group
that moves the same points as <grp> does.


\beginexample
gap> SymmetricParentGroup( Group( (1,2), (4,5), (7,8,9) ) );
Sym( [ 1, 2, 4, 5, 7, 8, 9 ] )
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Primitive Groups}

\>ONanScottType( <G> ) A

returns the type of <G> of a primitive permutation group <G>, according
to the O'Nan-Scott classification. The labelling of the different types
is not consistent in the literature, we use the following:
\beginlist
\item{1} Affine.
\item{2} Almost simple.
\item{3a} Diagonal, Socle consists of two normal subgroups.
\item{3b} Diagonal, Socle is minimal normal.
\item{4a} Product action with the first factor primitive of type 3a.
\item{4b} Product action with the first factor primitive of type 3b.
\item{4c} Product action with the first factor primitive of type 2.
\item{5} Twisted wreath product
\endlist
%%  See \cite{eickhulpkeXX} for correspondence to other labellings used
%%  in the literature.
As it can contain letters, the type is returned as a string.

If <G> is not a permutation group or does not act primitively on the
points moved by it, the result is undefined.



\>SocleTypePrimitiveGroup( <G> ) A

returns the socle type of a primitive permutation group. The socle of a
primitive group is the direct product of isomorphic simple groups,
therefore the type is indicated by a record with components `series',
`parameter' (both as described under
`IsomorphismTypeInfoFiniteSimpleGroup',
see~"IsomorphismTypeInfoFiniteSimpleGroup") and `width' for the number of
direct factors.

If <G> does not have a faithful primitive action, the result is undefined.



\beginexample
gap> g:=AlternatingGroup(5);;
gap> h:=DirectProduct(g,g);;
gap> p:=List([1,2],i->Projection(h,i));;
gap> ac:=Action(h,AsList(g),
> function(g,h) return Image(p[1],h)^-1*g*Image(p[2],h);end);;
gap> Size(ac);NrMovedPoints(ac);IsPrimitive(ac,[1..60]);
3600
60
true
gap> ONanScottType(ac);
"3a"
gap> SocleTypePrimitiveGroup(ac);
rec( series := "A", width := 2, 
  name := "A(5) ~ A(1,4) = L(2,4) ~ B(1,4) = O(3,4) ~ C(1,4) = S(2,4) ~ 2A(1,4\
) = U(2,4) ~ A(1,5) = L(2,5) ~ B(1,5) = O(3,5) ~ C(1,5) = S(2,5) ~ 2A(1,5) = U\
(2,5)", parameter := 5 )
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Stabilizer Chains}

Many of the algorithms for permutation groups use a *stabilizer chain* of
the group.
The concepts of stabilizer chains, *bases*, and *strong generating sets* were
introduced by Charles Sims in~\cite{Sim70}.
A further discussion of base change is given in
section~"ext:Generalized Conjugation Technique" in ``Extending {\GAP}''.

Let $B=[b_1, \ldots, b_n]$ be a list of points, $G^{(1)} = G$ and $G^{(i+1)} =
Stab_{G^{(i)}}(b_i)$, such that $G^{(n+1)} = \{ () \}$.
Then the list $[b_1, \ldots, b_n]$ is called a *base* of $G$,
the points $b_i$ are called *base
points*.  A set $S$ of generators for $G$ satisfying the condition $\< S
\cap G^{(i)} >$ = $G^{(i)}$ for each $1 \leq i \leq n$, is called a *strong
generating set* (SGS) of $G$. (More precisely we ought to say that it is a
SGS of $G$ *relative* to $B$).
The chain of subgroups $G^{(i)}$ of $G$ itself is
called the *stabilizer chain* of $G$ relative to $B$.

Since $[b_1, \ldots, b_n]$, where $n$ is the degree of $G$ and $b_i$ are the
moved points of $G$, certainly is a base for $G$ there exists a base for
each permutation group. The number of points in a base is called the
*length* of the base. A base $B$ is called *reduced* if there exists no $i$
such that $G^{(i)} = G^{(i+1)}$. (This however does not imply that no subset
of $B$ could also serve as a base.)
Note that different reduced bases for one permutation group $G$
may have different lengths.
For example, the irreducible degree $416$ permutation representation
of the Chevalley Group $G_2(4)$ possesses reduced bases of length 5 and 7.

Let $R^{(i)}$ be a right transversal of $G^{(i+1)}$ in $G^{(i)}$, i.e. a set
of right coset representatives of the cosets of $G^{(i+1)}$ in $G^{(i)}$.
Then each element $g$ of $G$ has a unique representation of the form $g =
r_n \ldots r_1$ with $r_i \in R^{(i)}$.
The cosets of $G^{(i+1)}$ in $G^{(i)}$ are in bijective correspondence with
the points in $O^{(i)} := b_i^{G^{(i)}}$.
So we could represent a transversal as a list $T$ such that $T[p]$ is a
representative of the coset corresponding to the point $p \in O^{(i)}$,
i.e., an element of $G^{(i)}$ that takes $b_i$ to $p$.
(Note that such a list has holes in all positions corresponding to points
not contained in $O^{(i)}$.)

This approach however will store many different permutations as coset
representatives which can be a problem if the degree $n$ gets bigger. Our
goal therefore is to store as few different permutations as possible such
that we can still reconstruct each representative in $R^{(i)}$, and from
them the elements in $G$. A *factorized inverse transversal* $T$ is a list
where $T[p]$ is a generator of $G^{(i)}$ such that $p^{T[p]}$ is a point
that lies earlier in $O^{(i)}$ than $p$ (note that we consider $O^{(i)}$ as
a list, not as a set). If we assume inductively that we know an element $r
\in G^{(i)}$ that takes $b_i$ to $p^{T[p]}$, then $r T[p]^{-1}$ is an
element in $G^{(i)}$ that takes $b_i$ to $p$. {\GAP} uses such factorized
inverse transversals.

Another name for a factorized inverse transversal is a
*Schreier tree*. The vertices of the tree are the points in $O^{(i)}$,
and the root of the tree is $b_i$.
The edges are defined as the ordered pairs $(p, p^{T[p]})$,
for $p \in O^{(i)} \setminus \{ b_i\}$. The edge $(p, p^{T[p]})$
is labelled with the generator $T[p]$, and the product of edge labels
along the unique path from $p$ to $b_i$ is the inverse of the
transversal element carrying $b_i$ to $p$.

Before we describe the construction of stablizer chains
in~"Construction of Stabilizer Chains",
we explain in~"Randomized Methods for Permutation Groups" the idea of
using non-deterministic algorithms;
this is necessary for understanding the options available for the
construction of stabilizer chains.
After that, in~"Stabilizer Chain Records" it is explained
how a stabilizer chain is stored in {\GAP},
"Operations for Stabilizer Chains" lists operations for stabilizer
chains,
and~"Low Level Routines to Modify and Create Stabilizer Chains" lists
low level routines for manipulating stabilizer chains.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Randomized Methods for Permutation Groups}

\atindex{Schreier-Sims!random}{@Schreier-Sims!random}
For most computations with permutation groups,
it is crucial to construct stabilizer chains efficiently. Sims's
original construction \cite{Sim70} is deterministic, and is called
the Schreier-Sims algorithm, because it is based
on Schreier's Lemma (p. 96 in \cite{Hall}): given $K=\langle S \rangle$
and a transversal $T$ for $K$ mod $L$, one can obtain
$|S||T|$ generators for $L$. This lemma is applied recursively,
with consecutive point stabilizers $G^{(i)}$ and $G^{(i+1)}$
playing the role of $K$ and $L$.

In permutation groups of large degree, the number of Schreier generators
to be processed becomes too large, and the deterministic Schreier-Sims
algorithm becomes impractical. Therefore, {\GAP} uses randomized
algorithms. The method selection process, which is quite different
from Version 3, works the following way.

If a group acts on not more than a hundred points,
Sims's original deterministic algorithm is applied. In groups of
degree greater than hundred, a heuristic algorithm based
on ideas in \cite{BCFS91} constructs a stabilizer chain.
This construction is complemented by a
verify-routine that either proves the correctness of the stabilizer chain
or causes the extension of the chain to a correct one.
The user can influence the verification process by setting
the value of the record component `random'
(cf.~"Construction of Stabilizer Chains").

If `random' $=1000$ then a slight extension of an unpublished method of
Sims is used. The outcome of this verification process is always
correct. The user also can prescribe any integer $1 \le x \le 999$
as the value of `random'. In this case, a randomized verification
process from \cite{BCFS91} is applied, and the result of the
stabilizer chain construction is guaranteed to be correct with probability
at least $x/1000$. The practical performance of the algorithm is
much better than the theoretical guarantee.

If the stabilizer chain is not correct then the elements in the
product of transversals $R^{(m)}R^{(m-1)}\cdots R^{(1)}$ constitute a
proper subset of the group $G$ in question.
This means that a membership test with this stabilizer chain
returns `false' for
all elements that are not in $G$,
but it may also return `false' for some elements of $G$;
in other words, the result `true' of a membership test is always correct,
whereas the result `false' may be incorrect.

The construction and verification phases are separated because
there are situations where the verification step can be omitted;
if one happens to know the order of the group in advance then the
randomized construction of the stabilizer chain stops
as soon as the product of the lengths of the basic orbits
of the chain equals the group order, and the chain will be correct
(see the `size' option of the `StabChain' command in~"StabChain").

Although the worst case running time is roughly quadratic for
Sims's verification and roughly linear for the randomized one,
in most examples the running time of the stabilizer chain
construction with `random'$=1000$ (i.e., guaranteed correct output)
is about the same as the running time of randomized verification
with guarantee of at least $90\%$ correctness. Therefore, we suggest
to use the default value `random'$=1000$. Possible uses of
`random'$\<1000$ are when one has to run through a large collection
of subgroups, and a low value of random is used to choose quickly
a candidate for more thorough examination; another use is when
the user suspects that the quadratic bottleneck of the guaranteed
correct verification is hit.

We will illustrate these ideas in two examples.

\beginexample
gap> h:= SL(4,7);;
gap> o:= Orbit( h, [1,0,0,0]*Z(7)^0, OnLines );;
gap> op:= Action( h, o, OnLines );;
gap> NrMovedPoints( op );
400
\endexample

We created a permutation group on 400 points.
First we compute a guaranteed correct stabilizer chain.
(The `StabChain' command is described in~"StabChain".)

%notest
\beginexample
gap> h:= Group( GeneratorsOfGroup( op ) );;
gap> StabChain( h );;  time;
1120
gap> Size( h );
2317591180800
\endexample

Now randomized verification will be used.
We require that the result is guaranteed correct with probability $90\%$.
This means that if we would do this calculation many times over,
{\GAP} would *guarantee* that in least $90\%$ percent of all calculations
the result is correct.
In fact the results are much better than the guarantee,
but we cannot promise that this will really happen.
(For the meaning of the `random' component in the second argument of
`StabChain', see~"StabChain".)

First the group is created anew.

%notest
\beginexample
gap> h:= Group( GeneratorsOfGroup( op ) );;
gap> StabChain( h, rec( random:= 900 ) );;  time;
1410
gap> Size( h );
2317591180800
\endexample

The result is still correct, and the running time is actually somewhat
slower.
If you give the algorithm additional information so that it can check
its results,
things become faster and the result is guaranteed to be correct.

%notest
\beginexample
gap> h:=Group( GeneratorsOfGroup( op ) );;
gap> SetSize( h, 2317591180800 );
gap> StabChain( h );;  time;
170
\endexample

The second example gives a typical group when the verification
with `random' $=1000$ is slow. The problem is that the group
has a stabilizer subgroup $G^{(i)}$ such that the fundamental
orbit $O^{(i)}$ is split into a lot of orbits when we stabilize
$b_i$ and one additional point of $O^{(i)}$.

%notest
\beginexample
gap> p1:=PermList(Concatenation([401],[1..400]));;
gap> p2:=PermList(List([1..400],i->(i*20 mod 401)));;
gap> d:=DirectProduct(Group(p1,p2),SymmetricGroup(5));;
gap> h:=Group(GeneratorsOfGroup(d));;
gap> StabChain(h);;time;Size(h);
1030
192480
gap> h:=Group(GeneratorsOfGroup(d));;
gap> StabChain(h,rec(random:=900));;time;Size(h);
570
192480
\endexample

When stabilizer chains of a group $G$ are created
with `random' $\<1000$, this is noted in the group $G$,
by setting of the record component `random'
in the value of the attribute `StabChainOptions' for $G$
(see~"StabChainOptions").
As errors induced by the random methods might propagate,
any group or homomorphism created from $G$ inherits a `random' component
in its `StabChainOptions' from the corresponding component for $G$.

A lot of algorithms dealing with permutation groups use randomized
methods; however, if the initial stabilizer chain construction
for a group is correct, these further methods will provide
guaranteed correct output.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Construction of Stabilizer Chains}

\>StabChain( <G>[, <options>] ) F
\>StabChain( <G>, <base> ) F
\>StabChainOp( <G>, <options> ) O
\>StabChainMutable( <G> ) AM
\>StabChainMutable( <permhomom> ) AM
\>StabChainImmutable( <G> ) A

These commands compute a stabilizer chain for the permutation group <G>;
additionally, `StabChainMutable' is also an attribute for the group
homomorphism <permhomom> whose source is a permutation group.

(The mathematical background of stabilizer chains is sketched
in~"Stabilizer Chains",
more information about the objects representing stabilizer chains
in {\GAP} can be found in~"Stabilizer Chain Records".)

`StabChainOp' is an operation with two arguments <G> and <options>,
the latter being a record which controls some aspects of the computation
of a stabilizer chain (see below);
`StabChainOp' returns a *mutable* stabilizer chain.
`StabChainMutable' is a *mutable* attribute for groups or homomorphisms,
its default method for groups is to call `StabChainOp' with empty
options record.
`StabChainImmutable' is an attribute with *immutable* values;
its default method dispatches to `StabChainMutable'.

`StabChain' is a function with first argument a permutation group <G>,
and optionally a record <options> as second argument.
If the value of `StabChainImmutable' for <G> is already known and if this
stabilizer chain matches the requirements of <options>,
`StabChain' simply returns this stored stabilizer chain.
Otherwise `StabChain' calls `StabChainOp' and returns an immutable copy
of the result; additionally, this chain is stored as `StabChainImmutable'
value for <G>.
If no <options> argument is given,
its components default to the global variable `DefaultStabChainOptions'
(see~"DefaultStabChainOptions").
If <base> is a list of positive integers,
the version `StabChain( <G>, <base> )' defaults to
`StabChain( <G>, rec( base:= <base> ) )'.

If given, <options> is a record whose components specify properties of
the desired stabilizer chain or which may help the algorithm.
Default values for all of them can be given in the global variable
`DefaultStabChainOptions' (see~"DefaultStabChainOptions").
The following options are supported.
\beginitems
`base' (default an empty list) &
    A list of points, through which the resulting stabilizer chain
    shall run.
    For the base $B$ of the resulting stabilizer chain <S> this means
    the following.
    If the `reduced' component of <options> is `true' then those points
    of `base' with nontrivial basic orbits form the initial segment
    of $B$, if the `reduced' component is `false' then `base' itself
    is the initial segment of $B$.
    Repeated occurrences of points in `base' are ignored.
    If a stabilizer chain for <G> is already known then the stabilizer
    chain is computed via a base change.

`knownBase' (no default value) &
    A list of points which is known to be a base for the group.
    Such a known base makes it easier to test whether a permutation
    given as a word in terms of a set of generators is the identity,
    since it suffices to map the known base with each factor
    consecutively, rather than multiplying the whole permutations
    (which would mean to map every point).
    This speeds up the Schreier-Sims algorithm which is used when a new
    stabilizer chain is constructed;
    it will not affect a base change, however.
    The component `knownBase' bears no relation to the `base'
    component, you may specify a known base `knownBase' and a desired
    base `base' independently.

`reduced' (default `true') &
    If this is `true' the resulting stabilizer chain <S> is reduced,
    i.e., the case  $G^{(i)} = G^{(i+1)}$ does not occur.
    Setting `reduced' to `false' makes sense only if the component
    `base' (see above) is also set;
    in this case all points of `base' will occur in the base $B$ of <S>,
    even if they have trivial basic orbits.
    Note that if `base' is just an initial segment of $B$,
    the basic orbits of the points in $B \setminus `base'$ are always
    nontrivial.

`tryPcgs' (default `true') &
    If this is `true' and either the degree is at most 100 or the group
    is known to be solvable, {\GAP} will first try to construct a pcgs
    (see Chapter~"Polycyclic Groups") for <G> which will succeed and
    implicitly construct a stabilizer chain if <G> is solvable.
    If <G> turns out non-solvable, one of the other methods will be used.
    This solvability check is comparatively fast, even if it fails,
    and it can save a lot of time if <G> is solvable.

`random' (default `1000') &
    If the value is less than~$1000$,
    the resulting chain is correct with probability
    at least~$`random'/1000$.
    The `random' option is explained in more detail
    in~"Randomized Methods for Permutation Groups".

`size' (default `Size( <G> )' if this is known,
        i.e., if `HasSize( <G> )' is `true') &
    If this component is present, its value is assumed to be the order
    of the group <G>.
    This information can be used to prove that a non-deterministically
    constructed stabilizer chain is correct.
    In this case, {\GAP} does a non-deterministic construction until the
    size is correct.

`limit' (default `Size( Parent( <G> ) )' or
         `StabChainOptions( Parent( <G> ) ).limit' if this is present) &
    If this component is present, it must be greater than or equal to
    the order of <G>.
    The stabilizer chain construction stops if size `limit' is reached.
\enditems



\>StabChainOptions( <G> ) AM

is a record that stores the options with which the stabilizer chain
stored in `StabChainImmutable' has been computed
(see~"StabChain" for the options that are supported).


\>`DefaultStabChainOptions' V

are the options for `StabChain' which are set as default.


\>StabChainBaseStrongGenerators( <base>, <sgs>, <one> ) F

If a base <base> for a permutation group $G$ and a strong generating set
<sgs> for $G$ with respect to <base> are given. <one> must be the
appropriate `One' (in most cases this will be `()').
This function constructs a stabilizer chain  without the need to find
Schreier generators;
so this is much faster than the other algorithms.



\>MinimalStabChain( <G> ) A

returns the reduced stabilizer chain corresponding to the base
$[1,2,3,4,\ldots]$.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Stabilizer Chain Records}

If a  permutation group  has a   stabilizer chain, this   is stored  as a
recursive structure. This  structure  is itself  a record~<S>  and it has
(1)~components that provide information about  one level~$G^{(i)}$ of the
stabilizer chain (which  we call  the  ``current stabilizer'')  and (2)~a
component `stabilizer'  that  holds   another such  record,   namely  the
stabilizer chain  of    the next stabilizer~$G^{(i+1)}$.  This  gives   a
recursive  structure  where the  ``outermost''  record  representing  the
``topmost'' stabilizer is bound to the group record component `stabChain'
and   has the components explained below.
Note: Since the structure is recursive, *never print a stabilizer chain!*
(Unless you want to exercise the scrolling capabilities of your terminal.)
\beginitems
`identity' &
        the identity element of the current stabilizer.

`labels' &
        a list of permutations which contains labels for the Schreier tree
        of  the current stabilizer,  i.e., it contains
        elements for the factorized
        inverse transversal.  The  first entry  is this list  is
        always the  `identity'.
        Note that {\GAP} tries to arrange things so that the `labels'
        components are identical (i.e., the same {\GAP} object)
        in every stabilizer of the chain;
        thus the `labels' of a stabilizer do not necessarily all lie
        in the this stabilizer (but see `genlabels' below).

`genlabels' &
        a list of integers indexing some of the permutations in the
        `labels' component. The    `labels' addressed in this   way
        form a generating set for the current stabilizer. If the
        `genlabels' component is empty,  the rest of the stabilizer chain
        represents  the trivial subgroup, and  can be ignored, e.g., when
        calculating the size.

`generators' &
        a list of generators for the current stabilizer. Usually, it is
        `labels\{ genlabels \}'.

`orbit' &
        the vertices of  the Schreier tree,  which  form the basic  orbit
        $b_i^{G^{(i)}}$, ordered in such a way that the  base point $b_i$ is

`transversal' &
	The factorized inverse transversal found during the orbit algorithm.
	The element <g> stored at `transversal[<i>]' will map <i> to another
	point <j> that in the Schreier tree is closer to the base point. By
	iterated application (`transversal[<j>]' and so on) eventually the
	base point is reached and an element that maps <i> to the base
	point foiund as product.

`translabels' &
	An index list such that 
	`transversal[<j>] =  labels[ translabels[<j>] ]'.
	This list takes up comparatively little memory and is used to speed
	up base changes.

`stabilizer' &
        If  the  current stabilizer is  not   yet the trivial  group, the
        stabilizer chain continues with   the stabilizer of  the  current
        base  point,  which is    again  represented as  a   record  with
        components `labels',    `identity',    `genlabels', `generators',
        `orbit',     `translabels',  `transversal'     (and      possibly
        `stabilizer'). This record is bound to the `stabilizer' component
        of the current stabilizer. The last member  of a stabilizer chain
        is recognized  by the fact that  it has no `stabilizer' component
        bound.
\enditems
It is possible that different stabilizer  chains share the same record as
one of their iterated `stabilizer' components.

\beginexample
gap> g:=Group((1,2,3,4),(1,2));;
gap> StabChain(g);
<stabilizer chain record, Base [ 1, 2, 3 ], Orbit length 4, Size: 24>
gap> BaseOfGroup(g);
[ 1, 2, 3 ]
gap> StabChainOptions(g);
rec( random := 1000 )
gap> DefaultStabChainOptions;
rec( reduced := true, random := 1000, tryPcgs := true )
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Operations for Stabilizer Chains}

\>BaseStabChain( <S> ) F

returns the base belonging to the stabilizer chain <S>.


\>BaseOfGroup( <G> ) A

returns a base of the permutation group <G>.
There is *no* guarantee that a stabilizer chain stored in <G>
corresponds to this base!



\>SizeStabChain( <S> ) F

returns the product of the orbit lengths in the stabilizer chain <S>,
that is, the order of the group described by <S>.


\>StrongGeneratorsStabChain( <S> ) F

returns a strong generating set corresponding to the stabilizer chain <S>.


\>GroupStabChain( [<G>, ] <S> ) F

constructs a permutation group with stabilizer chain <S>, i.e., a group
with  generators `Generators( <S>  )'   to  which <S> is assigned as
component  `stabChain'. If the  optional argument <G> is  given, the
result  will have the parent <G>.


\>OrbitStabChain( <S>, <pnt> ) F

returns the orbit of <pnt> under the group described by the stabilizer
chain <S>.


\>IndicesStabChain( <S> ) F

 returns a list of the indices of the stabilizers in the stabilizer
 chain <S>.


\>ListStabChain( <S> ) F

returns a list that contains at position $i$ the stabilizer of the first
$i-1$ base points in the stabilizer chain <S>.


\>ElementsStabChain( <S> ) F

returns a list of all elements of the group described by the stabilizer
chain <S>.



\>InverseRepresentative( <S>, <pnt> ) F

calculates the transversal element which  maps <pnt> back to  the base
point of  <S>. It just  runs back through the  Schreier tree from <pnt>
to the root and multiplies the labels along the way.


\>SiftedPermutation( <S>, <g> ) F

sifts the permutation <g> through the stabilizer chain <S> and returns
the result after the last step.

The element <g> is sifted as follows: <g> is replaced by
`<g> \* InverseRepresentative( <S>, <S>.orbit[1]^<g> )',
then <S> is replaced by `<S>.stabilizer' and this process is repeated
until <S> is trivial or `<S>.orbit[1]^<g>' is not in the basic orbit
`<S>.orbit'.
The remainder <g> is returned, it is the identity permutation if and
only if the original <g> is in the group $G$ described by
the original~<S>.


\>MinimalElementCosetStabChain( <S>, <g> ) F

Let $G$ be the group described by the stabilizer chain <S>.
This function returns a permutation $h$ such that $G <g> = G h$
(that is, $<g> / h \in G$) and with the additional property that
the list of images under $h$ of the base belonging to <S> is minimal
w.r.t.~lexicographical ordering.


\>LargestElementStabChain( <S>, <id> ) F

Let $G$ be the group described by the stabilizer chain <S>.
This function returns the element $h \in G$ with the property that
the list of images under $h$ of the base belonging to <S> is maximal
w.r.t.~lexicographical ordering.
The second argument must be an identity element (used to start the
recursion)



\>ApproximateSuborbitsStabilizerPermGroup( <G>, <pnt> ) F

returns an approximation of the orbits of `Stabilizer( <G>, <pnt> )'
on all points of the orbit `Orbit( <G>, <pnt> )',
without computing the full point stabilizer;
As not all Schreier generators are used,
the result may represent the orbits of only a subgroup of the point
stabilizer.




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Low Level Routines to Modify and Create Stabilizer Chains}

These operations modify a stabilizer chain or obtain new chains with
specific properties. They are rather technical and should only be used if
such low-level routines are deliberately required. (For all functions in
this section the parameter <S> is a stabilizer chain.)

\>CopyStabChain( <S> ) F

This function returns a copy of the stabilizer chain <S>
that has no mutable object (list or record) in common with <S>.
The `labels'  components of the result are possibly shared by several
levels, but superfluous labels are removed.
(An entry in `labels' is superfluous if it does not occur among the
`genlabels' or `translabels' on any of the levels which share that
`labels' component.)

This is useful for  stabiliser sub-chains that  have been obtained as
the (iterated) `stabilizer' component of a bigger chain.


\>CopyOptionsDefaults( <G>, <options> ) F

sets components in a stabilizer chain options record <options> according
to what is known about the group <G>. This can be used to obtain a new
stabilizer chain for <G> quickly.


\>ChangeStabChain( <S>, <base>[, <reduced>] ) F

changes or reduces a stabilizer chain <S> to be adapted to the base
<base>.
The optional argument <reduced> is interpreted as follows.
\beginitems
`reduced = false' : &
    change the stabilizer chain, do not reduce it,

`reduced = true' : &
    change the stabilizer chain, reduce it.
\enditems


\>ExtendStabChain( <S>, <base> ) F

extends the stabilizer chain <S> so that it corresponds to base <base>.
The original base of <S> must be a subset of <base>.


\>ReduceStabChain( <S> ) F

changes the stabilizer chain <S> to a reduced stabilizer chain by
eliminating trivial steps.


%%declaration{ConjugateStabChain}
\>RemoveStabChain( <S> ) F

<S> must be a stabilizer record in a stabilizer chain. This chain then
is cut off at <S> by changing the entries in <S>. This can be used to
remove trailing trivial steps.


\>EmptyStabChain( <labels>, <id>[, <pnt>] ) F

constructs  a   stabilizer  chain  for   the trivial   group with
`identity=<id>' and `labels=$\{id\}\cup  labels$'  (but of course with
`genlabels=[ ]' and `generators=[ ]'). If the optional third argument
<pnt>  is present, the only stabilizer   of the chain is initialized
with the  one-point basic orbit  `[ <pnt> ]' and with `translabels' and
`transversal' components.


\>InsertTrivialStabilizer( <S>, <pnt> ) F

`InsertTrivialStabilizer' initializes the current stabilizer with <pnt>
as `EmptyStabChain' did,  but  assigns the original <S> to the  new
`<S>.stabilizer' component,  such that  a new level with trivial basic
orbit (but identical  `labels' and `ShallowCopy'ed `genlabels' and
`generators') is  inserted.
This function should be used only if <pnt> really is fixed by the generators
of <S>, because then new generators can be added and the orbit and
transversal at the same time extended with
`AddGeneratorsExtendSchreierTree'.


\>IsFixedStabilizer( <S>, <pnt> ) F

returns `true'  if <pnt> is fixed by   all generators of  <S> and `false'
otherwise.


\>AddGeneratorsExtendSchreierTree( <S>, <new> ) F

adds the elements  in <new> to the list  of generators of <S> and at the
same time extends the  orbit and transversal. This is the only legal way
to extend  a  Schreier tree (because this involves careful handling of
the tree components).




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Backtrack}

A main use for stabilizer chains is in backtrack algorithms for permutation
groups. {\GAP} implements a partition-backtrack algorithm as described in
\cite{Leon91} and refined in \cite{Theissen97}.

\>SubgroupProperty( <G>, <Pr>[, <L> ] ) F

<Pr> must be a one-argument function that returns `true' or `false' for
elements of <G> and the subset of elements of <G> that fulfill <Pr> must
be a subgroup. (*If the latter is not true the result of this operation
is unpredictable!*) This command computes this subgroup.
The optional argument <L> must be a subgroup of the set of all elements
fulfilling <Pr> and can be given if known
in order to speed up the calculation.


\>ElementProperty( <G>, <Pr>[, <L>[, <R>]] ) F

`ElementProperty' returns an element $\pi$ of the permutation group <G>
such that the one-argument function <Pr> returns `true' for $\pi$.
It returns `fail' if no such element exists in <G>.
The optional arguments <L> and <R> are subgroups of <G> such that the
property <Pr> has the same value for all elements in the cosets <L><g>
and <g><R>, respectively.



A typical example of using the optional subgroups <L> and <R> is the
conjugacy test for elements <a> and <b> for which one can set
$<L>:=C_G(<a>)$ and $<R>:=C_G(<b>)$.

\beginexample
gap> propfun:= el -> (1,2,3)^el in [ (1,2,3), (1,3,2) ];;
gap> SubgroupProperty( g, propfun, Subgroup( g, [ (1,2,3) ] ) );
Group([ (1,2,3), (2,3) ])
gap> ElementProperty( g, el -> Order( el ) = 2 );
(2,4)
\endexample

Chapter~"Permutations" describes special operations to construct
permutations in the symmetric group without using backtrack constructions.

Backtrack routines are also called by the methods for permutation groups
that compute centralizers, normalizers, intersections, conjugating elements
as well as
stabilizers for the operations of a permutation group
`OnPoints', `OnSets', `OnTuples' and `OnSetSets'. Some of these methods use
more specific refinements than `SubgroupProperty' or `ElementProperty'.
For the definition of refinements, and how one can define refinements, see
Section~"ext:The General Backtrack Algorithm with Ordered Partitions" in
``Extending {\GAP}''.

\>TwoClosure( <G> ) A

The *2-closure* of a transitive permutation group <G> on $n$ points is
the largest subgroup of $S_n$ which has the same orbits on sets of
ordered pairs of points as the group <G> has.
It also can be interpreted as the stabilizer of the orbital graphs of
<G>.


\beginexample
gap> TwoClosure(Group((1,2,3),(2,3,4)));
Sym( [ 1 .. 4 ] )
\endexample

\>`InfoBckt' V

is the info class for the partition backtrack routines.



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Working with large degree permutation groups}

Permutation groups of large degree (usually at least a few 10000) can pose
a challenge to the heuristics used in the algorithms for permutation groups.
This section lists a few useful tricks that may speed up calculations with
such large groups enormously.

The first aspect concerns solvable groups: A lot of calculations (including
an initial stabilizer chain computation thanks to the algorithm from
\cite{Sims90b}) are faster if a permutation group is known to be solvable.
On the other hand, proving nonsolvability can be expensive for higher
degrees. Therefore {\GAP} will automatically test a permutation group for
solvability, only if the degree is not exceeding 100.
(See also the `tryPcgs' component of `StabChainOptions'.)
It is therefore beneficial to tell a group of larger degree, which is known
to be solvable, that it is, using `SetIsSolvableGroup(<G>,true)'.

The second aspect concerns memory usage. A permutation on more than 65536
points requires 4 byte per point for storing. So permutations on 256000
points require roughly 1MB of storage per permutation. Just storing the
permutations required for a stabilizer chain might already go beyond the
available memory, in particular if the base is not very short. In such a
situation it can be useful, to replace the permutations by straight line
program elements (see~"Straight Line Program Elements").

The following code gives an example of usage:
We create a group of degree 231000. Using straight line program elements,
one can compute a stabilizer chain in about 200 MB of memory.

% don't attempt to run this example through the manual checker -- it takes
% *ages* to run and *lots* of memory!
% besides the input data is not given ...
\begintt
gap> Read("largeperms"); # read generators from file
gap> gens:=StraightLineProgGens(permutationlist);;
gap> g:=Group(gens);
<permutation group with 5 generators>
gap> # use random algorithm (faster, but result is monte carlo)
gap> StabChainOptions(g).random:=1;;
gap> Size(g); # enforce computation of a stabilizer chain
3529698298145066075557232833758234188056080273649172207877011796336000
\endtt

Without straight line program elements, the same calculation runs into
memory problems after a while even with 512MB of workspace:
\begintt
gap> h:=Group(permutationlist);
<permutation group with 5 generators>
gap> StabChainOptions(h).random:=1;;
gap> Size(h);
exceeded the permitted memory (`-o' command line option) at
mlimit := 1; called from
SCRMakeStabStrong( S.stabilizer, [ g ], param, orbits, where, basesize,
 base, correct, missing, false ); called from
 SCRMakeStabStrong( S.stabilizer, [ g ], param, orbits, where, basesize,
...
\endtt

The advantage in memory usage however is paid for in runtime: Comparisons of
elements become much more expensive. One can avoid some of the related
problems by registering a known base with the straight line program elements
(see~`StraightLineProgGens'). In this case element comparison will only
compare the images of the given base points.
If we are planning to do extensive calculations with the group, it can even
be worth to recreate it with straight line program elements knowing a
previously computed base:

\begintt
gap> # get the base we computed already
gap> bas:=BaseStabChain(StabChainMutable(g));
[ 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55,
...
  2530, 2533, 2554, 2563, 2569 ]
gap> gens:=StraightLineProgGens(permutationlist,bas);;
gap> g:=Group(gens);;
gap> SetSize(g,
> 3529698298145066075557232833758234188056080273649172207877011796336000);
gap> Random(g);; # enforce computation of a stabilizer chain
\endtt

As we know already base and size, this second stabilizer chain calculation
is much faster than the first one and takes less memory.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E