%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%W  stbchain.tex              GAP documentation            Heiko Thei\3en
%%
%H  @(#)$Id: stbchain.tex,v 4.18 2002/10/14 12:38:11 gap Exp $
%%
%Y  Copyright 1997,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,   Germany
%%
\PreliminaryChapter{Stabilizer Chains}

This  chapter contains some rather  technical complements to the material
handled in the chapters~"ref:Permutations" and "ref:Permutation Groups" of
the reference manual.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Generalized Conjugation Technique}

The command `ConjugateGroup( <G>, <p> )' (see~"ref:ConjugateGroup" in the
reference manual) for a  permutation  group  <G>  with  stabilizer  chain
equips its result also with a stabilizer chain, namely with the chain  of
<G> conjugate by <p>. Conjugating a stabilizer chain by a permutation <p>
means replacing all the points which appear in the `orbit' components  by
their images under <p> and replacing every permutation <g> which  appears
in a `labels' or `transversal' component  by  its  conjugate  $g^p$.  The
conjugate $g^p$ acts on the mapped points  exactly  as  <g>  did  on  the
original points, i.e., $(pnt.p). g^p = (pnt.g).p$. Since the  entries  in
the `translabels' components are integers pointing to  positions  of  the
`labels' list, the `translabels' lists just have to be  permuted  by  <p>
for the conjugated stabilizer.  Then  `generators'  is  reconstructed  as
`labels\{  genlabels  \}'  and  `transversal\{  orbit  \}'  as  `labels\{
translabels\{ orbit \} \}'.

\index{generalized conjugation technique}
This conjugation technique can be generalized. Instead of mapping  points
and  permutations  under  the  same  permutation  <p>,  it  is  sometimes
desirable (e.g., in the context of permutation  group  homomorphisms)  to
map the points with an arbitrary mapping <map> and the permutations  with
a homomorphism <hom> such that the compatibility of the actions is  still
valid:   $map(pnt).hom(g) = map(pnt.g)$.   (Of   course    the   ordinary
conjugation is a special case  of  this,  with   $map(pnt) = pnt.p$   and
$hom(g) = g^p$.)

In  the  generalized  case,  the  ``conjugated''  chain  need  not  be  a
stabilizer chain for the image of <hom>, since the  ``preimage''  of  the
stabilizer of $map(b)$ (where <b> is a base point) need not fix <b>,  but
only fixes the preimage $map^{-1}(map(b))$ setwise. Therefore the  method
can be applied only to one level and the next stabilizer must be computed
explicitly. But if <map> is injective, we have $map(b).hom(g)=map(b) \iff
b.g=b$, and if this holds, then $g=w(g_1,\ldots,g_n)$ is a  word  in  the
generators $g_1,\ldots,g_n$ of the stabilizer of~<b> and
% replaced \buildrel *\over= by {$*$}{$=$} ... easiest compromise for HTML
$hom(g) =^\*    w(hom(g_1),\ldots,hom(g_n))$    is    in    the
``conjugated'' stabilizer. If, more generally, <hom> is a  right  inverse
to  a  homomorphism~$\varphi$  (i.e.,  $\varphi(hom(g))=g\,\forall   g$),
equality $\*$ holds modulo ${\rm Ker}\,\varphi$; in this  case  the
``conjugated'' chain  can  be  made  into  a  real  stabilizer  chain  by
extending  each  level  with  the  generators  ${\rm  Ker}\,\varphi$  and
appending a proper stabilizer chain of~${\rm Ker}\,\varphi$ at  the  end.
These special cases will occur in the algorithms  for  permutation  group
homomorphisms (see~"ref:Group Homomorphisms" in the reference manual).

To ``conjugate'' the  points  (i.e.,  `orbit')  and  permutations  (i.e.,
`labels') of the Schreier tree, a loop is set up over  the  `orbit'  list
constructed during the orbit algorithm, and  for  each  vertex  <b>  with
unique edge $a(l)b$ ending at <b>, the label <l> is mapped with <hom> and
<b> with <map>. We assume  that  the  `orbit'  list  was  built  w.r.t.~a
certain ordering of the labels, where $l'\<l$ means that every  point  in
the orbit was mapped with $l'$ before it was mapped with <l>. This  shape
of the `orbit' list is guaranteed if the Schreier tree is  extended  only
by `AddGeneratorsExtendSchreierTree', and it is then also guaranteed  for
the ``conjugated'' Schreier tree. (The ordering of the labels  cannot  be
read from the Schreier tree, however.)

In the generalized case, it can happen that  the  edge  $a(l)b$  bears  a
label <l> whose image is ``old'', i.e., equal to the image of an  earlier
label $l'\<l$. Because of the compatibility of the actions we  then  have
$map(b) = map(a). hom(l)^{-1} = map(a).hom(l')^{-1}  =  map(a{l'}^{-1})$,
so $map(b)$ is already equal to the image  of  the  vertex  $a{l'}^{-1}$.
This vertex must have been  encountered  before  $b  =  al^{-1}$  because
$l'\<l$. We conclude that the image of a label can be ``old'' only if the
vertex at the end of the corresponding edge has an  ``old''  image,  too,
but then it need not be ``conjugated'' at all. A similar  remark  applies
to labels which map under <hom> to the identity.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{The General Backtrack Algorithm with Ordered Partitions}

\begingroup%
\def\calR{{\cal R}} \def\I{{\cal I}}%

Section "ref:Backtrack" in the reference manual describes the basic
functions for a backtrack search. The purpose of
this section  is  to document  how  the general   backtrack algorithm  is
implemented in {\GAP} and which  parts you have to modify  if you want to
write your own backtrack routines.

\medskip
\atindex{ordered partitions!internal representation}{|indexit}
{\bsf Internal   representation  of  ordered   partitions.}\quad   {\GAP}
represents  an  ordered  partition  as  a  record  with   the   following
components.
\beginitems
`points' &
        a list  of all points contained in  the  partition, such that the
        points of each cell from lie consecutively,

`cellno' &
        a list whose <i>th entry is the number of the cell which contains
        the point <i>,

`firsts' &
        a list  such that  `points[firsts[<j>]]'  is  the first point  in
        `points' which is in cell <j>,

`lengths' &
        a list of the  cell lengths.
\enditems
Some of the information is  redundant, e.g., the  `lengths' could also be
read off the `firsts' list,  but since this   need not be increasing,  it
would    require some searching. Similar  for    `cellno', which could be
replaced by a systematic search  of `points', keeping  track of what cell
is currently being  traversed. With the above  components, the <m>th cell
of   a partition <P> is   expressed as `<P>.points{  [ <P>.firsts[<m>] ..
<P>.firsts[<m>] +  <P>.lengths[<m>]  -  1  ]   }'. The   most   important
operations, however, to be performed upon <P> are the splitting of a cell
and the reuniting  of the two parts. Following  the strategy  of J.~Leon,
this is done as follows:

\beginlist%ordered

\item{(1)}
The points which make up the cell that is to be split are sorted so  that
the ones that remain inside occupy positions `[ <P>.firsts[<m>] .. <last>
]' in the list `<P>.points' (for a suitable value of <last>).

\item{(2)}
The  points  at  positions  `[  <last>   +   1   ..   <P>.firsts[<m>]   +
<P>.lengths[<m>] - 1 ]' will form the additional cell. For this new  cell
requires additional entries are added to the lists `<P>.firsts'  (namely,
`<last>+1')    and    `<P>.lengths'    (namely,    `<P>.firsts[<m>]     +
<P>.lengths[<m>] - <last> - 1').

\item{(3)}
The entries of the sublist `<P>.cellno{ [ <last>+1 ..  <P>.firsts[<m>]  +
P.lengths[<m>]-1 ] }' must be set to the number of the new cell.

\item{(4)}
The entry `<P>.lengths[<m>]' must be reduced to `<last> - <P>.firsts[<m>]
+ 1'.

\endlist

Then reuniting the  two cells requires  only the reversal of steps~2 to~4
above. The list `<P>.points' need not be rearranged.

\medskip
{\bsf Functions for setting up  an R-base.}\quad This subsection explains
some  {\GAP}  functions   which   are   local   to   the   library   file
`lib/stbcbckt.gi' which contains the code for backtracking in permutation
groups. They are mentioned here because you might find them helpful  when
you want  to  implement  you  own  backtracking  function  based  on  the
partition concept. An important argument to most of the functions is  the
R-base $\calR$, which you should regard as a black box. We will tell you how
to set it up, how to maintain it and where to pass it as argument, but it
is not necessary for you to know its internal representation. However, if
you insist to learn the whole story: Here are the record components  from
which an R-base is made up:

\beginitems
`domain' &
    the set $\Omega$ on which the group $G$ operates

`base' &
    the sequence $(a_1,\ldots,a_r)$ of base points

`partition' &
    an  ordered  partition, initially  $\Pi_0$, this  will be  refined to
    $\Pi_1,\ldots,\Pi_r$ during the backtrack algorithm

`where' &
    a list such that $a_i$ lies in cell number `where[ $i$ ]' of $\Pi_i$

`rfm' &
    a    list whose $i$th entry  is   a  list of   refinements which take
    $\Sigma_i$  to $\Sigma_{i+1}$;  the    structure of a  refinement  is
    described below

`chain' &
    a (copy of a) stabilizer  chain for $G$ (not  if  $G$ is a  symmetric
    group)

`fix' &
    only if  $G$ is a  symmetric group:  a list whose  $i$ entry contains
    `Fixcells( $\Pi_i$ )'

`level' &
    initially equal to `chain',  this will be changed  to chains  for the
    stabilizers  $G_{a_1\dots  a_i}$    for  $i=1,\ldots,r$  during   the
    backtrack algorithm; if $G$ is a  symmetric group, only the number of
    moved points is stored for each stabilizer

`lev' &
    a  list   whose  $i$th  entry   remembers   the  `level' entry    for
    $G_{a_1\ldots a_{i-1}}$

`level2', `lev2' &
    a similar  construction   for a second  group  (used  in intersection
    calculations), `false' otherwise.  This second group $H$ activated if
    the R-base  is constructed as  `EmptyRBase(  [ $G$, $H$  ], $\Omega$,
    $\Pi_0$ )' (if `$G$ = $H$', {\GAP} sets `level2 = true' instead).

`nextLevel' &
    this is described below
\enditems

As  our guiding example, we  present  code for the function `Centralizer'
which calculates the centralizer of an element $g$ in the group $G$. (The
real code is more general and has a few more subtleties.)

\)\kernttindent 1 $\Pi_0$ := TrivialPartition( $\Omega$ );
\)\kernttindent 2 $\calR$ := EmptyRBase( $G$, $\Omega$, $\Pi_0$ );
\)\kernttindent 3 $\calR$.nextLevel := function( $\Pi$, <rbase> )
\)\kernttindent 4 local \ $fix$,  $p$,  $q$,  $where$;
\)\kernttindent 5 \quad NextRBasePoint( $\Pi$, <rbase> );
\)\kernttindent 6 \quad $fix$ := Fixcells( $\Pi$ );
\)\kernttindent 7 \quad for $p$  in $fix$  do
\)\kernttindent 8 \qquad $q$ := $p$ ^ $g$;
\)\kernttindent 9 \qquad $where$ := IsolatePoint( $\Pi$, $q$ );
\)\kernttindent10 \qquad if $where$ \<> false  then
\)\kernttindent12 \quad\qquad Add( $fix$, $q$ );
\)\kernttindent13 \quad\qquad ProcessFixpoint( $\calR$, $q$ );
\)\kernttindent14 \quad\qquad AddRefinement( $\calR$, "Centralizer", %
              [ $\Pi$.cellno[ $p$ ], $q$, $where$ ] );
\)\kernttindent15 \quad\qquad if $\Pi$.lengths[ $where$ ] = 1  then
\)\kernttindent16 \qquad\qquad $p$ := FixpointCellNo( $\Pi$, $where$ );
\)\kernttindent17 \qquad\qquad ProcessFixpoint( $\calR$, $p$ );
\)\kernttindent18 \qquad\qquad AddRefinement( $\calR$, "ProcessFixpoint", %
              [ $p$, $where$ ] );
\)\kernttindent19 \quad\qquad fi;
\)\kernttindent20 \qquad fi;
\)\kernttindent21 \quad od;
\)\kernttindent22 end;
\)\kernttindent23 return PartitionBacktrack(
\)\kernttindent24 \qquad $G$,
\)\kernttindent25 \qquad $c$ -> $g$ ^ $c$ = $g$,
\)\kernttindent26 \qquad false,
\)\kernttindent27 \qquad $\calR$,
\)\kernttindent28 \qquad [ $\Pi_0$, $g$ ],
\)\kernttindent29 \qquad $L$, $R$ );

The list numbers below refer to the line numbers of the code above.

\beginlist%ordered

\item{1.}
$\Omega$ is the set on which $G$ acts and $\Pi_0$ is the first member  of
the decreasing sequence of partitions mentioned in "ref:Backtrack" in the
reference manual.  We  set  $\Pi_0=(\Omega)$,  which  is  constructed  as
`TrivialPartition( $\Omega$ )'), but we could have started with  a  finer
partition, e.g., into unions of $g$-cycles of the same length.

\item{2.}
This statement sets up the R-base in the variable $\calR$.

\item{3.} -- 21.
\enspace These lines define a function `$\calR$.nextLevel' which  is  called
whenever an additional member in the sequence $\Pi_0 \ge \Pi_1 \ge\ldots$
of partitions is needed. If $\Pi_i$ does  not  yet  contain  enough  base
points in one-point cells, {\GAP}  will  call  `$\calR$.nextLevel(  $\Pi_i$,
$\calR$ )', and this function will choose a new base point $a_{i+1}$, refine
$\Pi_i$ to $\Pi_{i+1}$ (thereby *changing* the first argument) and  store
all necessary information in~$\calR$.

\endlist
\beginlist%ordered{1}{5}

\item{5.}
This statement selects a new base point $a_{i+1}$, which is not yet in  a
one-point cell of $\Pi$ and still moved by the  stabilizer  $G_{a_1\ldots
a_i}$ of the earlier base points. If certain points  of  $\Omega$  should
are preferred as base point (e.g., because they belong to long cycles  of
$g$), a list of points starting with the most wanted ones, can  be  given
as an optional third argument to `NextRBasePoint' (actually, this is done
in the real code for `Centralizer').

\item{6.}
`Fixcells( $\Pi$ )' returns the list of  points  in  one-point  cells  of
$\Pi$ (ordered as the cells are ordered in $\Pi$).

\item{7.}
For every point $p\in fix$, if we know the image `$p$ ^ $g$' under  $c\in
C_G(e)$, we also know `( $p$ ^ $g$ ) ^ $c$ = ( $p$ ^ $c$  )  ^  $g$'.  We
therefore want to isolate these extra points in $\Pi$.

\endlist
\beginlist%ordered{1}{9}

\item{9.}
This statement puts point $q$ in a cell of its own, returning in  $where$
the number of the cell of $\Pi$ from which $q$  was  taken.  If  $q$  was
already the only point in its cell, `$where$ = false' instead.

\endlist
\beginlist%ordered{1}{12}

\item{12.}
This command does the necessary bookkeeping for the extra base point $q$:
It prescribes $q$ as next base in the stabilizer chain for  $G$  (needed,
e.g., in line~5) and  returns  `false'  if  $q$  was  already  fixed  the
stabilizer of the earlier base points (and `true' otherwise; this is  not
used here). Another call to `ProcessFixpoint' like  this  was  implicitly
made by the function `NextRBasePoint' to register the chosen base  point.
By contrast, the point $q$ was not chosen this way, so  `ProcessFixpoint'
must be called explicitly for~$q$.

\item{13.}
This statement registers the function  which  will  be  used  during  the
backtrack search to perform the corresponding refinements on the  ``image
partition'' $\Sigma_i$  (to  yield  the  refined  $\Sigma_{i+1}$).  After
choosing an image $b_{i+1}$ for the base  point  $a_{i+1}$,  {\GAP}  will
compute $\Sigma_i \wedge (\{b_{i+1}\},\Omega-\{b_{i+1}\})$ and store this
partition in `$\I$.partition', where $\I$ is a black box similar to $\calR$,
but corresponding to the current ``image  partition''  (hence  it  is  an
``R-image'' in analogy to the R-base). Then {\GAP} will call the function
`Refinements.Centralizer( $\calR$, $\I$, $\Pi$.cellno[ $p$ ],  $p$,  $where$
)',  with  the  then  current  values  of  $\calR$  and  $\I$,   but   where
`$\Pi$.cellno[ $p$ ]', $p$, $where$ still have the values  they  have  at
the time of this `AddRefinement' command. This function call will further
refine `$\I$.partition' to yield $\Sigma_{i+1}$ as it  is  programmed  in
the function `Refinements.Centralizer', which is  described  below.  (The
global variable `Refinements' is a record which contains  all  refinement
functions for all backtracking procedures.)

\item{14.} -- 19.
If the cell from which $q$ was taken out had only two points, we now have
an additional one-point cell. This condition is checked in line~13 and if
it is true, this extra fixpoint $p$ is taken  (line~15),  processed  like
$q$ before (line~16) and is then (line~17) passed to  another  refinement
function `Refinements.ProcessFixpoint( $\calR$, $\I$, $p$, $where$ )', which
is also described below.

\endlist
\beginlist%ordered{1}{22}

\item{23.} -- 29.
This command  starts  the  backtrack  search.  Its  result  will  be  the
centralizer as a subgroup of $G$. Its arguments are

\endlist
\beginlist%ordered{1}{24}
  \item{24.} the group we want to run through,
  \item{25.} the property we want to test, as a {\GAP} function,
  \item{26.} `false' if we are looking for a subgroup, `true' in the case
    of   a  representative  search    (when  the result   would    be one
    representative),
  \item{27.} the R-base,
  \item{28.} a list  of data, to be stored  in `$\I$.data', which has
    in position~1 the first member $\Sigma_0$  of the decreasing sequence
    of ``image partitions'' mentioned in "ref:Backtrack" in the
    reference manual. In the centralizer example, position~2 contains the
    element that is  to be centralized. In the  case of  a representative
    search,  i.e.,  a conjugacy test  `$g$  ^ $c$ ?= $h$', we
    would  have $h$   instead of  $g$   here, and   possibly a $\Sigma_0$
    different from $\Pi_0$ (e.g., a  partition into unions of  $h$-cycles
    of same length).
  \item{29.} two subgroups  $L\le  C_G(g)$  and  $R\le  C_G(h)$ known  in
    advance (we have $L=R$ in the centralizer case).
\endlist

\medskip
{\bsf Refinement  functions   for the  backtrack  search.}\quad  The last
subsection showed   how the refinement   process leading from  $\Pi_i$ to
$\Pi_{i+1}$  is coded in the  function  `$\calR$.nextLevel', this  has to be
executed once the  base point  $a_{i+1}$.  The analogous refinement  step
from $\Sigma_i$ to $\Sigma_{i+1}$ must be performed for each choice of an
image $b_{i+1}$ for  $a_{i+1}$, and it will  depend  on the corresponding
value of $\Sigma_i\wedge  (\{b_{i+1}\}, \Omega-\{b_{i+1}\})$. But  before
we  can continue  our centralizer example,  we  must,  for the interested
reader, document the record components of the other black box $\I$, as we
did above for the R-base black box $\calR$. Most of the components change as
{\GAP} walks up and down the levels of the search tree.
\beginitems
`data' &
    this will be mentioned below

`depth' &
    the level $i$ in the search tree of the current node $\Sigma_i$

`bimg' &
    a list of images of the points in `$\calR$.base'

`partition' &
    the partition $\Sigma_i$ of the current node

`level' &
    the stabilizer chain `$\calR$.lev[ $i$ ]' at the current level

`perm' &
    a permutation mapping `Fixcells(  $\Pi_i$ )' to `Fixcells( $\Sigma_i$
    )' (this implies mapping $(a_1,\ldots,a_i)$ to $(b_1,\ldots,b_i)$)

`level2', `perm2' &
    a  similar construction for    the second stabilizer chain,   `false'
    otherwise (and `true' if `$\calR$.level2 = true')
\enditems

As declared in    the above code  for  `Centralizer',  the refinement  is
performed   by   the function     `Refinement.Centralizer(   $\calR$,  $\I$,
$\Pi$.cellno[  $p$  ],  $p$,  $where$ )'.   The  functions in the  record
`Refinement' always   take two  additional   arguments  before  the  ones
specified  in  the `AddRefinement'  call (in  line~13 above),  namely the
R-base  $\calR$ and  the  current  value  $\I$  of the ``R-image''.   In our
example,  $p$   is a   fixpoint  of   $\Pi= \Pi_i   \wedge  (\{a_{i+1}\},
\Omega-\{a_{i+1}\})$ such that `$where$ = $\Pi$.cellno[ $p$ ^ $g$ ]'. The
`Refinement'   functions   must  return `false'    if   the refinement is
unsuccessful (e.g., because it  leads to $\Sigma_{i+1}$ having  different
cell   sizes from  $\Pi_{i+1}$)  and  `true'  otherwise.   Our particular
function looks like this.

\)\kernttindent 1 Refinements.Centralizer := function( %
                  $\calR$, $\I$, $cellno$, $p$, $where$ )
\)\kernttindent 2 local \ $\Sigma$,  $q$;
\)\kernttindent 3 \quad $\Sigma$ := $\I$.partition;
\)\kernttindent 4 \quad $q$ := FixpointCellNo( $\Sigma$, $cellno$ ) ^ %
                  $\I$.data[ 2 ];
\)\kernttindent 5 \quad return IsolatePoint( $\Sigma$, $q$ ) = $where$ %
                  and ProcessFixpoint( $\I$, $p$, $q$ );
\)\kernttindent 6 end;

The list numbers below refer to the line numbers of the code immediately
above.

\beginlist%ordered{1}{3}

\item{3.}
The current value of $\Sigma_i\wedge  (\{b_{i+1}\},  \Omega-\{b_{i+1}\})$
is always found in `$\I$.partition'.

\item{4.}
The image of the only point in cell number  `$cellno$  =  $\Pi_i$.cellno[
$p$ ]' in $\Sigma$ under `$g$ = $\I$.data[ 2 ]' is calculated.

\item{5.}
The function returns `true' only if the  image  $q$  has  the  same  cell
number in $\Sigma$ as $p$ had in $\Pi$ (i.e., $where$) and if $q$ can  be
prescribed as an  image  for  $p$  under  the  coset  of  the  stabilizer
$G_{a_1\ldots a_{i+1}}.c$ where $c\in  G$  is  an  (already  constructed)
element mapping the  earlier  base  points  $a_1,\ldots,a_{i+1}$  to  the
already chosen images  $b_1,\ldots,b_{i+1}$.  This  latter  condition  is
tested by `ProcessFixpoint( $\I$, $p$, $q$ )' which, if successful,  also
does the necessary bookkeeping in $\I$. In analogy to  the  remark  about
line~12 in the program above, the chosen image  $b_{i+1}$  for  the  base
point $a_{i+1}$ has already been processed  implicitly  by  the  function
`PartitionBacktrack', and this processing includes the construction of an
element  $c\in  G$  which  maps  `Fixcells(  $\Pi_i$  )'  to   `Fixcells(
$\Sigma_i$  )'  and  $a_{i+1}$  to  $b_{i+1}$.  By  contrast,  the  extra
fixpoints $p$ and $q$ in $\Pi_{i+1}$ and $\Sigma_{i+1}$ were  not  chosen
automatically, so they require an  explicit  call  of  `ProcessFixpoint',
which replaces the element $c$ by some $c'.c$ (with  $c'\in  G_{a_1\ldots
a_{i+1}}$) which in addition maps $p$ to $q$, or returns `false' if  this
is impossible.

\endlist

You should now be able to  guess what `Refinements.ProcessFixpoint( $\calR$,
$\I$, $p$, $where$   )' does: it  simply returns  `ProcessFixpoint( $\I$,
$p$, FixpointCellNo( $\I$.partition, $where$ ) )'.

\medskip
{\bsf  Summary.}\quad When you write  your  own backtrack functions using
the  partition technique,  you  have  to  supply  an R-base, including  a
component `nextLevel', and   the  functions in the   `Refinements' record
which  you need. Then  you can start  the backtrack by passing the R-base
and the additional data (for the  `data' component of the ``R-image'') to
`PartitionBacktrack'.

\medskip
{\bsf  Functions  for  meeting    ordered  partitions.}\quad A   kind  of
refinement that   occurs  in particular  in   the  normalizer calculation
involves computing  the  meet of $\Pi$  (cf.\ lines~6ff.\  above) with an
arbitrary other partition  $\Lambda$, not just  with one point. To do this
efficiently, {\GAP} uses the following two functions.

\>StratMeetPartition( $\calR$, $\Pi$, $\Lambda$ \[, $g$ \] )
\>MeetPartitionStrat( $\calR$, $\I$, {$\Lambda'$} \[, {$g'$} \], $strat$ )

\index{meet strategy}
Such a  `StratMeetPartition'   command would   typically appear in    the
function call `$\calR$.nextLevel(  $\Pi$, $\calR$ )'  (during the refinement of
$\Pi_i$  to  $\Pi_{i+1}$). This   command  replaces  $\Pi$  by $\Pi\wedge
\Lambda$ (thereby  *changing* the  second  argument) and returns a ``meet
strategy''  $strat$. This  is  (for  us) a  black   box which  serves two
purposes:  First, it allows {\GAP} to  calculate faster the corresponding
meet $\Sigma\wedge \Lambda'$,  which must then  appear in a `Refinements'
function  (during the refinement of  $\Sigma_i$ to $\Sigma_{i+1}$). It is
faster  to compute $\Sigma\wedge \Lambda'$ with  the ``meet strategy'' of
$\Pi\wedge \Lambda$ because  if the refinement  of $\Sigma$ is successful
at  all, the  intersection  of a  cell from   the left hand  side of  the
$\wedge$ sign  with a cell  from the right hand side  must  have the same
size   in both cases  (and  $strat$  records these   sizes, so  that only
non-empty intersections must  be calculated for $\Sigma\wedge \Lambda'$).
Second, if  there  is a discrepancy  between  the behaviour prescribed by
$strat$ and the behaviour observed when refining $\Sigma$, the refinement
can immediately be abandoned.

On  the  other hand, if you  only  want to meet   a  partition $\Pi$ with
$\Lambda$  for  a one-time  use, without recording   a strategy,  you can
simply type `StratMeetPartition( $\Pi$, $\Lambda$ )'  as in the following
example, which also demonstrates some other partition-related commands.

% \beginexample
% gap> P := Partition( [[1,2],[3,4,5],[6]] );;  Cells( P );
% [ [ 1, 2 ], [ 3, 4, 5 ], [ 6 ] ]
% gap> Q := OnPartitions( P, (1,3,6) );;  Cells( Q );  
% [ [ 3, 2 ], [ 6, 4, 5 ], [ 1 ] ] 
% gap> StratMeetPartition( P, Q ); 
% [  ]  # the ``meet strategy'' was not recorded, ignore this result
% gap> Cells( P );
% [ [ 1 ], [ 5, 4 ], [ 6 ], [ 2 ], [ 3 ] ]
% \endexample

% The preceding (original) example doesn't work because there is no
% function 'OnPartitions'. The following example works, but I don't
% know if it makes sense to have it here at all. (Note, in particular,
% that the function 'Partition' is undocumented.)  VF  14.10.02

\beginexample
gap> P := Partition( [[1,2],[3,4,5],[6]] );;  Cells( P );
[ [ 1, 2 ], [ 3, 4, 5 ], [ 6 ] ]
gap> Q := Partition( OnTuplesTuples( last, (1,3,6) ) );;  Cells( Q );
[ [ 3, 2 ], [ 6, 4, 5 ], [ 1 ] ]
gap> StratMeetPartition( P, Q );
[  ]
gap> # The ``meet strategy'' was not recorded, ignore this result.
gap> Cells( P );
[ [ 1 ], [ 5, 4 ], [ 6 ], [ 2 ], [ 3 ] ]
\endexample

You can even say  `StratMeetPartition( $\Pi$, $\Delta$ )'  where $\Delta$
is simple  a subset  of  $\Omega$, it   will then  be interpreted as  the
partition $(\Delta,\Omega-\Delta)$.

{\GAP} makes use   of  the advantages  of   a ``meet  strategy''  if  the
refinement   function  in `Refinements'  contains  a `MeetPartitionStrat'
command where   $strat$  is   the    ``meet  strategy''  calculated    by
`StratMeetPartition' before.  Such a command replaces `$\I$.partition' by
its meet with $\Lambda'$, again changing the argument $\I$. The necessary
reversal of these changes when backtracking from  a node (and prescribing
the next possible image  for a base point) is  automatically done by  the
function `PartitionBacktrack'.

In  all cases, an additional  argument $g$ means that the   meet is to be
taken  not with $\Lambda$,   but  instead with $\Lambda.{g^{-1}}$,  where
operation  on ordered partitions is  meant cellwise  (and setwise on each
cell). (Analogously for the primed arguments.)

\beginexample
gap> P := Partition( [[1,2],[3,4,5],[6]] );;
gap> StratMeetPartition( P, P, (1,6,3) );;  Cells( P );
[ [ 1 ], [ 5, 4 ], [ 6 ], [ 2 ], [ 3 ] ]
\endexample
Note that $P.(1,3,6) = Q$.

{\bsf Avoiding multiplication  of permutations.}\quad In the  description
of  the last subsections, the  backtrack  algorithm constructs an element
$c\in G$ mapping  the base points   to the prescribed images  and finally
tests the property in question for that element. During the construction,
$c$ is obtained as a product  of transversal elements from the stabilizer
chain for $G$,  and so multiplications  of permutations are required  for
every $c$  submitted to the test,  even if the  test fails (i.e.,  in our
centralizer example, if `$g$ ^ $c$ \<> $g$'). Even if the construction of
$c$ stops before images  for all base  points have been chosen, because a
refinement was unsuccessful,  several  multiplications will  already have
been performed by (explicit or implicit) calls of `ProcessFixpoint', and,
actually, the general   backtrack procedure implemented in  {\GAP} avoids
this.

For this purpose, {\GAP} does  not actually multiply the permutations but
rather stores  all the factors of the   product in a  list. Specifically,
instead of carrying out  the multiplication in $c\mapsto c'.c$  mentioned
in  the   comment  to  line~5 of  the   above  program   --- where $c'\in
G_{a_1\ldots  a_{i+1}}$ is a  product  of factorized inverse  transversal
elements, see "ref:Stabilizer chain records" in the reference manual  ---
{\GAP} appends the list of these factorized inverse transversal  elements
(giving $c'$) to the list of factors already collected for $c$. Here $c'$
is multiplied from the left and is itself  a  product  of  *inverses*  of
strong generators of $G$, but {\GAP} simply spares itself all the work of
inverting permutations and stores only  a  ``list  of  inverses'',  whose
product is then $(c'.c)^{-1}$ (which is the new value of  $c^{-1}$).  The
``list of inverses'' is extended this way whenever  `ProcessFixpoint'  is
called to improve~$c$.

The  product has to be multiplied  out only when  the property is finally
tested  for  the  element $c$. But  it  is  often possible  to  delay the
multiplication  even  further, namely  until after   the test, so  that no
multiplication is required in the case of  an unsuccessful test. Then the
test  itself  must be carried   out with the  factorized   version of the
element $c$.  For  this purpose,  `PartitionBacktrack' can  be passed its
second argument (the property  in question) in  a different way, not as a
single {\GAP} function, but as a list like in lines 2--4 of the following
alternative excerpt from the code for `Centralizer'.

\)\kernttindent 1 return PartitionBacktrack( $G$,
\)\kernttindent 2 \quad [ $g$, $g$,
\)\kernttindent 3 \qquad OnPoints,
\)\kernttindent 4 \qquad $c$ -> $c$!.lftObj = $c$!.rgtObj ],
\)\kernttindent 5 \quad false, $\calR$, [ $\Pi_0$, $g$ ], $L$, $R$ );

The test for $c$ to have the property in question  is of the form `$opr$(
$left$,  $c$  )  =  $right$' where  $opr$   is an  operation  function as
explained in "ref:External sets" in the reference manual. In other words,
$c$ passes the test if and only if it maps a ``left object'' to a ``right
object'' under  a certain operation. In  the centralizer example, we have
`$opr$ =  OnPoints' and $left = right  = g$, but  in a conjugacy test, we
would have $right = h$.

\beginlist%ordered{1}{2}

\item{2.}
Two first two entries (here $g$ and $g$) are the  values  of  $left$  and
$right$.

\item{3.}
The third entry (here `OnPoints') is the operation $opr$.

\item{4.}
The fourth entry is the test to be performed upon the mapped left  object
$left$ and preimage of the right object `$opr$( $right$, $c$^-1 )'.  Here
{\GAP} operates with the inverse of $c$ because this is  the  product  of
the permutations stored in the ``list  of  inverses''.  The  preimage  of
$right$ under $c$ is then calculated by mapping $right$ with the  factors
of $c^{-1}$ one by one, without the need to multiply these factors.  This
mapping  of  $right$  is  automatically  done  by  the  `ProcessFixpoint'
function whenever $c$ is extended, the current value of $right$ is always
stored in `$c$!.rgtObj'. When the test  given  by  the  fourth  entry  is
finally performed, the element $c$  has  two  components  `$c$!.lftObj  =
$left$' and `$c$!.rgtObj = $opr$( $right$, $c$^-1 )', which must be  used
to express the desired relation as a function of $c$. In our  centralizer
example, we simply have to test whether they are equal.

\endlist

\endgroup%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Stabilizer Chains for Automorphisms Acting on Enumerators}

This section describes a way of representing the automorphism group of a
group as permutation group, following \cite{Sims97}. The code however is
not yet included in the {\GAP} library.

In this section  we present an example in  which objects we  already know
(namely,  automorphisms  of   solvable  groups)   are  equipped  with the
permutation-like operations `^' and `/'  for action on positive integers.
To achieve this, we must  define a new  type of objects which behave like
permutations   but are  represented     as automorphisms  acting  on   an
enumerator.  Our  goal is to  generalize  the Schreier-Sims algorithm for
construction of a stabilizer chain to groups of such new automorphisms.

{\bsf  An operation domain for automorphisms.}\quad  The idea we describe
here is due  to C.~Sims. We consider  a group $A$  of  automorphisms of a
group $G$, given by generators,  and we would like  to know its order. Of
course we  could   follow the strategy  of  the   Schreier-Sims algorithm
(described  in "ref:Stabilizer chains"  in  the reference manual) for $A$
acting   on   $G$. This would    involve   a  call  of  `StabChainStrong(
EmptyStabChain( [   ],  One( $A$ ) ),   GroupGenerators(  $A$ ) )'  where
`StabChainStrong'  is a function as the  one described in the pseudo-code
below:

\){\kernttindent}StabChainStrong := function( $S$, $newgens$ )
\){\kernttindent}\quad{\rm Extend the Schreier tree of $S$ with $newgens$.}
\){\kernttindent}\quad for $sch$  in {\rm Schreier generators}  do
\){\kernttindent}\qquad if $sch \notin S$.stabilizer  then
\){\kernttindent}\qquad\quad StabChainStrong( $S$.stabilizer, [ $sch$ ] );
\){\kernttindent}\qquad fi;
\){\kernttindent}\quad od;
\){\kernttindent}end;

The membership test `$sch  \notin S$.stabilizer' can be performed because
the  stabilizer chain  of `$S$.stabilizer'  is   already correct at  that
moment. We  even know a base  in advance, namely  any  generating set for
$G$. Fix such  a generating set  $(g_1,\ldots,g_d)$ and observe that this
base  is  generally very   short compared  to   the degree $|G|$  of  the
operation. The problem with the Schreier-Sims algorithm, however, is then
that the length of the first  basic orbit $g_1.A$  would already have the
magnitude of $|G|$,  and the basic orbits at  deeper levels would  not be
much shorter. For the advantage of a short base  we pay the high price of
long basic  orbits, since the  product of  the  (few) basic orbit lengths
must  equal $|A|$.  Such  long  orbits  make the Schreier-Sims  algorithm
infeasible,   so we have to   look for a  longer base  with shorter basic
orbits.

Assume that   $G$ is solvable  and  choose  a  characteristic series with
elementary abelian factors. For the sake of  simplicity we assume that $N
\< G$ is an   elementary abelian characteristic subgroup  with elementary
abelian factor group $G/N$. Since $N$ is characteristic, $A$ also acts as
a group of automorphisms  on the factor  group $G/N$,  but of course  not
necessarily  faithfully. To retain  a faithful action,  we let $A$ act on
the   disjoint   union   $G/N$   with   $G$,   and   choose    as    base
$(g_1N,\ldots,g_dN,g_1,\ldots,g_d)$. Now the first $d$ basic  orbits  lie
inside $G/N$ and can have length at most $[G\mathbin:N]$. Since the  base
points $g_1N,\ldots,  g_dN$  form  a  generating  set  for  $G/N$,  their
iterated stabilizer $A^{(d+1)}$ acts trivially on the factor group $G/N$,
i.e., it leaves the cosets $g_iN$ invariant. Accordingly,  the  next  $d$
basic orbits lie inside $g_iN$ (for $i=1,\ldots,d$) and can  have  length
at most~$|N|$.

Generalizing this method to a characteristic series $G=N_0 > N_1 > \ldots
> N_l=\{1\}$ of length $l>2$, we  can always find  a base of length $l.d$
such that each  basic orbit is  contained in a  coset of a characteristic
factor, i.e. in a set of the form $g_iN_{j-1}/N_j$ (where $g_i$ is one of
the generators  of $G$ and $1\le j\le  l$). In particular, the  length of
the basic  orbits   is  bounded   by  the  size  of    the  corresponding
characteristic factors. To implement a Schreier-Sims algorithm for such a
base, we  must  be   able  to  let   automorphisms  act  on   cosets   of
characteristic  factors $g_iN_{j-1}/N_j$, for  varying  $i$  and $j$.  We
would    like to    translate each such     action  into  an  action   on
$\{1,\ldots,[N_{j-1}\mathbin: N_j]\}$, because then we need not enumerate
the operation domain
$$
   G/N_1 \mathbin{\dot\cup} G/N_2 \mathbin{\dot\cup} \ldots %
         \mathbin{\dot\cup} G/N_l 
$$
as a whole. Enumerating it  as a whole would result  in basic orbits like
$`orbit'\subseteq \{1001,\ldots,1100\}$  with a  `transversal' list whose
first 1000 entries would be unbound, but  still require 4~bytes of memory
each (see~"ref:Stabilizer chain records" in the reference manual).

Identifying   each  coset   $g_iN_{j-1}/N_j$ into   $\{1,\ldots, [N_{j-1}
\mathbin: N_j]\}$ of  course means that we have  to change the action  of
the automorphisms on     every  level of   the  stabilizer   chain.  Such
flexibility is not   possible with permutations  because their  effect on
positive  integers  is ``hardwired''  into them,  but  we can install new
operations for automorphisms.

{\bsf Enumerators for cosets of  characteristic factors.}\quad So far  we
have  not used the  fact that  the characteristic  factors are elementary
abelian, but we will do so from  here on. Our  first task is to implement
an enumerator (see "ref:AsList" and "ref:Enumerators"  in  the  reference
manual) for a coset of a characteristic factor in a solvable  group  $G$.
We assume that such a coset $gN/M$ is given by

\beginlist%ordered

\item{(1)}  a pcgs for  the group  $G$ (see  "ref:Pcgs" in the  reference
  manual), let `$n$ = Length( $pcgs$ )';

\item{(2)} a range `$range$ = [ $start$  .. $stop$ ]' indicating that `$N
  =  \langle pcgs$\{ [ $start$  .. $n$ ] \} $\rangle$'  and `$M = \langle
  pcgs$\{  [  $stop$ + 1   .. $n$ ]  \} $\rangle$',  i.e.,  the cosets of
  `$pcgs$\{ $range$ \}' form a base for the vector space $N/M$;

\item{(3)} the representative $g$.

\endlist

We   first  define a  new representation  for   such enumerators and then
construct them by simply putting these three pieces of data into a record
object. The  enumerator  should  behave as  a   list of  group   elements
(representing cosets modulo $M$),   consequently, its family will  be the
family of the $pcgs$ itself.
\begintt
IsCosetSolvableFactorEnumeratorRep := NewRepresentation
    ( "isCosetSolvableFactorEnumerator", IsEnumerator,
                                [ "pcgs", "range", "representative" ] );

EnumeratorCosetSolvableFactor := function( pcgs, range, g )
    return Objectify( NewKind( FamilyObj( pcgs ),
                   IsCosetSolvableFactorEnumeratorRep ),
                   rec( pcgs := pcgs,
                       range := range,
              representative := g ) );
end;
\endtt
The definition of the operations `Length', `\\[\\]' and `Position' is now
straightforward. The  code has sometimes  been  abbreviated and is  meant
``cum grano salis'',  e.g.,  the declaration of  the local  variables has
been left out.
\begintt
InstallMethod( Length, [ IsCosetSolvableFactorEnumeratorRep ],
    enum -> Product( RelativeOrdersPcgs( enum!.pcgs ){ enum!.range } ) );
\endtt

\begintt
InstallMethod( \[\], [ IsCosetSolvableFactorEnumeratorRep,
        IsPosRat and IsInt ],
    function( enum, pos )
    elm := ();
    pos := pos - 1;
    for i  in Reversed( enum!.range )  do
        p := RelativeOrderOfPcElement( enum!.pcgs, i );
        elm := enum!.pcgs[ i ] ^ ( pos mod p ) * elm;
        pos := QuoInt( pos, p );
    od;
    return enum!.representative * elm;
end );
\endtt

\begintt
InstallMethod( Position, [ IsCosetSolvableFactorEnumeratorRep,
        IsObject, IsZeroCyc ],
    function( enum, elm, zero )
    exp := ExponentsOfPcElement( enum!.pcgs,
                   LeftQuotient( enum!.representative, elm ) );
    pos := 0;
    for i  in enum!.range  do
        pos := pos * RelativeOrderOfPcElement( pcgs, i ) + exp[ i ];
    od;
    return pos + 1;
end );
\endtt

{\bsf  Making automorphisms act  on such enumerators.}\quad Our next task
is to make automorphisms of the  solvable group `$pcgs$!.group' act on `[
1 .. Length( $enum$ )  ]' for such an  enumerator $enum$. We achieve this
by  introducing a new  representation of automorphisms on enumerators and
by putting the enumerator together  with the automorphism into an  object
which behaves like  a permutation. Turning  an ordinary automorphism into
such  a special  automorphism requires  then   the construction of  a new
object which has the new kind. We provide an operation `PermOnEnumerator(
$model$, $aut$ )' which constructs such a new object having the same kind
as  $model$,  but representing the  automorphism  $aut$. So $aut$  can be
either an ordinary automorphism or one which already has an enumerator in
its kind, but perhaps  different from the one  we want (i.e. from the one
in $model$).
\begintt
IsPermOnEnumerator := NewCategory( "IsPermOnEnumerator",
    IsMultiplicativeElementWithInverse and IsPerm );
\endtt

\begintt
IsPermOnEnumeratorDefaultRep := NewRepresentation
    ( "IsPermOnEnumeratorDefaultRep",
      IsPermOnEnumerator and IsAttributeStoringRep,
      [ "perm" ] );

PermOnEnumerator := NewOperation( "PermOnEnumerator",
    [ IsEnumerator, IsObject ] );
\endtt

\begintt
InstallMethod( PermOnEnumerator,
        [ IsEnumerator, IsObject ],
    function( enum, a )
    SetFilterObj( a, IsMultiplicativeElementWithInverse );
    a := Objectify( NewKind( PermutationsOnEnumeratorsFamily,
                 IsPermOnEnumeratorDefaultRep ),
                 rec( perm := a ) );
    SetEnumerator( a, enum );
    return a;
end );
\endtt

\begintt
InstallMethod( PermOnEnumerator,
        [ IsEnumerator, IsPermOnEnumeratorDefaultRep ],
    function( enum, a )
    a := Objectify( TypeObj( a ), rec( perm := a!.perm ) );
    SetEnumerator( a, enum );
    return a;
end );
\endtt
Next we  have to install new  methods for the  operations which calculate
the  product of two automorphisms, because   this product must again have
the    right kind. We    also have to write  a    function which uses the
enumerators to apply such an automorphism to positive integers.
\begintt
InstallMethod( \*, IsIdenticalObj,
        [ IsPermOnEnumeratorDefaultRep, IsPermOnEnumeratorDefaultRep ],
    function( a, b )
    perm := a!.perm * b!.perm;
    SetIsBijective( perm, true );
    return PermOnEnumerator( Enumerator( a ), perm );
end );
\endtt

\begintt
InstallMethod( \^,
        [ IsPosRat and IsInt, IsPermOnEnumeratorDefaultRep ],
    function( p, a )
    return PositionCanonical( Enumerator( a ),
                   Enumerator( a )[ p ] ^ a!.perm );
end );
\endtt
How the corresponding  methods for `$p$ /  $aut$' and `$aut$  ^ $n$' look
like is obvious.

Now we  can  formulate  the recursive procedure   `StabChainStrong' which
extends  the stabilizer chain by adding  in new  generators $newgens$. We
content  ourselves again   with pseudo-code, emphasizing  only  the lines
which set the `EnumeratorDomainPermutation'. We assume that initially $S$
is a stabilizer chain for the trivial subgroup with a level for each pair
$(range,g)$ characterizing an enumerator  (as  described above). We  also
assume that  the `identity'  element at each  level already  has the kind
corresponding to that level.

\){\kernttindent}StabChainStrong := function( $S$, $newgens$ )
\){\kernttindent}\quad for $i$  in [ 1 .. Length( $newgens$ ) ]  do
\){\kernttindent}\qquad $newgens$[ $i$ ] := %
  AutomorphismOnEnumerator( $S$.identity, $newgens$[ $i$ ] );
\){\kernttindent}\quad od;
\){\kernttindent}\quad {\rm Extend the Schreier tree of $S$ with $newgens$.}
\){\kernttindent}\quad for $sch$  in {\rm Schreier generators}  do
\){\kernttindent}\qquad if $sch \notin S$.stabilizer  then
\){\kernttindent}\qquad\quad StabChainStrong( $S$.stabilizer, [ $sch$ ] );
\){\kernttindent}\qquad fi;
\){\kernttindent}\quad od;
\){\kernttindent}end;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E
% Local Variables:
% mode:               text
% mode:               outline-minor
% outline-regexp:     "\\\\Chapter\\|\\\\Section\\|\\\\stars"
% paragraph-start:    "\\\\begin\\|\\\\end\\|\\$\\$\\|.*%\\|^$"
% paragraph-separate: "\\\\begin\\|\\\\end\\|\\$\\$\\|.*%\\|^$"
% fill-column:        73
% End:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%