\documentclass[11pt]{amsart}
\usepackage{palatcm,fullpage,latexsym}
\title{Algorithms for permutation groups based on
Homomorphisms,\\
Some thoughts}
\author{Alexander Hulpke}
\address{St. Andrews, May 1997}
\email{ahulpke@dcs.st-and.ac.uk}
\begin{document}
\maketitle
\pagestyle{empty}
\thispagestyle{empty}
\section{Motivation}

There are very efficient algorithms for solvable groups, using (special)
pc-systems. These algorithms are applicable also to solvable permutation
groups, the concept of a {\em polycyclic generating system} ({\sf PCGS}) in
{\sf GAP4} actually permits to use the same code.

Permutation group algorithms have seen much improval over the last years.
But while elementary objects like centralizers or normalizers can be computed
satisfactory, more complex objects like conjugacy classes or complements
are still diffcult.

If a solvable normal subgroup exists, the algorithms for solvable groups can
be utilized again, provided the problem has been solved in the factor group. 

We can compute a composition series for permutation groups quickly. From
this we can derive a normal series with elementary factors (or even a chief
series).

The matrix group recognition project also produces algorithms that can be
used to compute a composition series for matrix groups. 

It would be desirable for such groups to use the homomorphism approach
that has proven to be very effective for groups with a pc presentation.
To extend this to the general case, one only has
to develop methods to deal with elementary nonabelian factors. Probably
information from the Classification can come handy here.

(Apologies for not citing anything in this section. This would have doubled
this drafts size.)

As an example, I will outline an algorithm to compute conjugacy classes (that
was motivated by shortcomings in the existing algorithms).
This is still work in progress.

\section{Conjugacy Classes}

It is sufficient to consider a nonabelian step.

Let $N\lhd G$ be an elementary nonabelian subgroup. Assume the classes of
$G/N$ are known. Let $C=C_G(N)$. Then (as $N$ is elementary nonabelian)
$C\cap N=\langle 1\rangle$. Thus $G$ is a subdirect product of $G/N$
with $G/C$. We can identify $F:=G/C$ with a subgroup of 
Aut$(N)\le \mbox{Aut}(T)\wr S_d$. Via this supergroup, we obtain a small
degree permutation representation for $F$. Thus we can analyze $F$ as
an imprimitive permutation group.

There is a homomorphism $\psi\colon F\to S_d$ (the action on the
components). Let $M=\ker\psi$. Then $M$ is an iterated subdirect product.

I will describe how to compute the classes of a subdirect product. This
shows how to get the classes of $G$ from those of $G/N$ and $F$. We will get
the classes of $F$ from the classes of $M$ (subdirect product), taking care
of the component permutation by $F$ and the classes outside $M$.

\subsection{Subdirect product}
The classes of a direct product are simply a ``cartesian product'' of the
constituents classes. If we have a subdirect product of $A$ and $B$, we have
to be a bit
more careful. Assume it has elements of the form $g=(a,b)$. Then $g$ can be
conjugate to make $a$ a class representative, but then $b$ can only be
assumed to be a
representative under the action of the centralizer $\hat C$ of $a$ on the
second component. Such representatives can be computed by conjugating class
representatives $b$ of $B$ with representatives of the double cosets
${C_B(b)}{\setminus}{B}{/}{(\hat C}^{(B-\mbox{part})})$.

As the subdirect product contains a large direct product,
$\hat C^{(B-\mbox{part})}$ usually is very close to $B$.

We construct representatives in this iterated way and remove all
representatives that are not contained in the subdirect product.

\subsection{Component permutation}
Now let $M\le F$ be an iterated subdirect product of $A$ with component
permutation action by $F\psi$. Assign ``colours'' to the classes of $A$,
according of how
they may fuse under this permutation action (this can be seen from
$(\mbox{Stab}_{F\psi}(1))\psi^{-1}$).

Each element of $M$ is a tuple $(a_1,\ldots,a_d)$. We can assign a ``colour
bar'' to this tuple. The permutation action of $F\psi$ permutes the colours.

We may assume that the colour bars of class representatives are ``minimal''.

Initially, construct all minimal colour bars, using a combinatorial
algorithm. This tells
\begin{itemize}
\item[-] whether to accept a full representative $(a_1,\ldots,a_d)$,
\item[-] which colours/classes can be added to a partial representative
$(a_1,\ldots,a_i)$ ($i<d$).
\item[-] which of the obtained representatives may fuse: They have to have
the same colour bar and fusion takes place in the bar stabilizer.
\end{itemize}

\subsection{Outer classes of $F$}
Experiments and heuristics show that there are relatively few classes
outside $M$, but that some of them can be very small. Thus we cannot use a
simple random search.

The idea in the solvable case ({\sc M. Mecky}, {\sc J. Neub\"user})
is to compute the classes of $Q=F\psi$ first
and for a representative $r$ in $F$ of a representative of each $Q$-class
to look at the action of $Z=(C_Q(r\psi))\psi^{-1}$ on $rM$ via
$(rm)^z=r[r,z]m^z$.

We cannot act on $M$ which is too big, but if we replace $Z$ by $M$, the
action decomposes into components:
\[
(rm)^z=r([r,z]_1m_1^{z_1},\ldots,[r,z]_dm_d^{z_d}).
\]
We then can act component-wise and obtain representatives inductively.

If even one component is too large to act on, one can try to compose the
classes from $C_F(r)$-classes. If $r$ is chosen suitably, this groups is
almost a diagonal and thus fairly large. This case still needs attention.

\subsection{Closing remarks}
I have a rudimentary implementation in {\sf GAP4}, but it is too early to
compare runtimes.

The algorithm nowhere uses that the group is a permutation group, it only
requires certain basic computations (like composition series) to be
feasible.

A related algorithm, using only one -- non-elementary -- nonabelian step and
relying on a random search outside a direct product, has been proposed
recently by {\sc J. Cannon} and {\sc B. Souvignier}

Thank you very much for reading through this draft.

\end{document}

