\documentstyle{article}
\input amssym.def
\input amssym.tex
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newenvironment{hypothesis}{\em Hypothesis $(\dagger):$}{}
\newenvironment{proof}{{\em Proof.}}{$\Box$}
\newenvironment{proofy}{}{$\Box$}
\newcommand{\glq}[1]{\mbox{GL} (#1,{\bf Q})}
\newcommand{\glz}[1]{\mbox{GL} (#1,{\bf Z})}
\newcommand{\glv}[1]{\mbox{GL} (#1)}
\newcommand{\trq}[1]{\mbox{Tr}_1(#1,{\bf Q})}
\newcommand{\trz}[1]{\mbox{Tr}_1(#1,{\bf Z})}
\newcommand{\q}[1]{{\bf Q}^{#1}}
\newcommand{\z}[1]{{\bf Z}^{#1}}
\newcommand{\choo}[2]{\left( \begin{array}{c} #1 \\ #2 \end{array} \right)}
\title{Algorithms for Polycyclic Matrix Groups}
\author{Gretchen Ostheimer\\
        Math Department\\
        Tufts University\\
        gostheim@emerald.tufts.edu}
\begin{document}
\maketitle

\begin{abstract}
This is a report on work in progress concerning
practical algorithms for studying infinite matrix groups.
I restrict my attention to polycyclic-by-finite 
groups as this is the setting in which (most of)
the interesting questions are actually decidable.
I have developed 
algorithms for testing membership, finding presentations, and
computing normal closures and  kernels of homomorphisms.
For some of these algorithms I have completed experiments which 
show that they are efficient enough to be
useful in studying some moderately 
complicated examples; for others I have heuristic
arguments that the algorithms are practical.
\end{abstract}

\paragraph{Results and Motivation.}
In developing an algorithmic theory for infinite
matrix groups, it is natural to consider the 
class of polycyclic-by-finite groups.\footnote{Recall 
that a group is polycyclic if and only
if it is solvable and all of its subgroups
are finitely generated.}
While most problems concerning 
matrix groups (such as membership and orbit)
are undecidable in general, 
they are decidable for the class of polycyclic-by-finite groups
\cite{BCRS}.

Let $G$ be a polycyclic subgroup of 
$\glq{n}$ given by a finite generating set 
$ \{ g_1, g_2, \ldots, g_k \} $ of matrices.
I have developed algorithms for the following 
problems concerning $G$.  
\begin{itemize}
\item{Membership.} 
Given a matrix $x$ in $\glq{n}$,
decide whether or not $x$ is an element of $G$.
\item{Normal Closure.}
Given a finite set of generators for a subgroup $H$ of $G$,
find a finite set of generators for the normal closure of 
$H$ in $G$.
\item{Polycyclic Generating Sequence.}
Find a polycyclic generating sequence for $G$.
(Polycyclic groups are characterized by the fact 
that they can be generated by a sequence of 
elements $s_1,s_2,\ldots,s_r$ with the property
that if $S_i = \langle s_i, s_{i+1}, \ldots s_r \rangle$,
then $S_{i+1} \triangleleft S_{i}$ for all $i$.
Such sequences are called polycyclic generating
sequences; they are desirable because then each element
in $G$ can be written as $s_1^{a_1} s_2^{a_2} \cdots s_r^{a_r}$
for some $a_1, a_2, \ldots, a_r \in {\bf Z}$.)
\end{itemize}
The following two algorithms allow us to study 
a homomorphism $\theta$ from $G$ to $\glq{m}$ for some $m$.
We assume that we are given 
matrices $h_1,h_2,\ldots, h_k$ in $\glq{m}$
such that the map $\theta$ taking $g_i$ to $h_i$
is a homomorphism.
(In practice, $\theta$ will arise naturally by considering
the action of $G$ on an invariant subspace or quotient
of $\q{n}$.)
\begin{itemize}
\item{Kernel.}
Find a finite set of generators for the kernel of $\theta$.
\item{Pullback.}
Given a matrix $h$ in $\theta(G)$,
find a $g$ in $G$ such that $\theta(g) = h$.
\end{itemize}
For the following two algorithms I assume that 
the given generators for $G$ form a polycyclic
generating sequence.
\begin{itemize}
\item{Constructive Membership.}
Given a matrix $x$ in $\glq{n}$,
decide whether or not $x$ is an element of $G$,
and, if so, write $x$ as a product of the
given generators for $G$.
\item{Presentations.}
Find a presentation for $G$ in terms of the given generators.
\end{itemize}

The emphasis of my research is on practical algorithms.
By a ``practical algorithm'' I mean
one which is efficient enough to answer 
an interesting question in a reasonable amount of time
with current technology.
While polynomial-time algorithms do exist
for some problems concerning nilpotent groups
\cite{Beals:nilfin}, it is unlikely
that they exist for polycyclic groups:
the growth rate
of a nilpotent group is
polynomial, whereas the growth rate of a polycyclic
group which is not nilpotent is exponential.
(See \cite{Milnor} and \cite{Wolf}.)

\paragraph{Related Work.}
For the case when $G$ is a solvable matrix group over
a finite field,
algorithms for these problems are
given in \cite{Luks}.
These algorithms run in 
polynomial-time (under certain assumptions about the
primes that appear in the order of $G$).
It would be interesting to explore their practicality.

For the case when $G$ is infinite but nilpotent-by-finite,
a probabilistic 
algorithm for constructive membership testing
in nilpotent-by-finite groups is given in 
\cite{Beals:nilfin}.
This algorithm runs in Las Vegas polynomial time.
In general, however, nilpotent groups are easier to
work with algorithmically than polycyclic 
groups.  For example, 
while the conjugacy problem
for finitely presented nilpotent groups has a very simple
and practical solution \cite{Sims},
there is no known practical algorithm for 
this problem that works for general finitely presented 
polycyclic groups.

An important survey of decidability results 
concerning polycyclic-by-finite matrix groups
can be found in \cite{BCRS}.
It is easy to show that 
the decidability of each of the problems listed above
follows easily from the results in \cite{BCRS};
however, many their algorithms 
are not practical \cite{GO:thesis}.
Consider for example, the algorithm in \cite{BCRS}
to find a presentation for a polycyclic subgroup $G$
of $\glz{n}$.
An important special case is when $G$ is triangularizable
over the complex numbers.  
The algorithm in \cite{BCRS} enumerates all number
fields $K$ and all of the bases for $K^n$
until it finds a field $K$ and a basis for $K^n$
with respect to which all of the matrices in $G$
are upper triangular.
The degree of $K$ could be as large as $n!$.
It will be impractical to compute in $K$, let alone to 
search blindly for $K$ and for a basis for $K^n$
of the desired form.
In \cite{GO:thesis} I give a structure theorem
for triangularizable groups that allows us
to avoid this.

\paragraph{Future work}
An interesting anomaly was discovered during experimentation.
Unitriangular groups (subgroups of $\trz{n}$) are 
an important special case of polycyclic groups.
I anticipated that such groups would lend themselves easily
to practical algorithms --- after all, they are torsion-free
nilpotent, and there are polynomial-time algorithms for working with
such groups \cite{Beals:nilfin}.
Furthermore, $\trz{n}$ has a natural polycyclic presentation,
and we can easily adapt the techniques in \cite{Sims}
for working with such groups.
This involves generalizing existing row Hermite normal
form algorithms (for
studying finitely generated free abelian groups).
When this was done,
however, I found that the efficiency of the algorithms
was not as good as expected;
indeed, the most time-consuming step
was in the computation of a certain unitriangular
subgroup.
This is an area that warrants further research.
One approach might be to see whether the improvements
to Hermite normal form calculations as described in \cite{Havas1}
and \cite{Havas2}
could be adapted to this context.

Most of the algorithms described here have not been implemented.
For triangularizable matrix groups, algorithms for testing 
membership and for finding a polycyclic generating sequence
were partially implemented, and experiments were done to 
illustrate the practicality of the algorithm.  Further implementation
and experimentation are needed to determine the kinds of
polycyclic groups 
for which these algorithms are really practical.
Ideally, an implementation platform would include 
some primitives for working with finitely generated abelian 
groups, number fields and matrix groups over finite
fields.

\paragraph{Acknowledgements.}  This work grew out of my
Ph.D.\ thesis, directed by Charles Sims at Rutgers.

%Gretch: 
%I need to check with George before mentionning his stuff.

\bibliographystyle{plain}
\bibliography{overall}
\end{document}

