\documentstyle{article}
\input amssym.def
\input amssym.tex
\begin{document}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newenvironment{hypothesis}{\em Hypothesis $(\dagger):$}{}
\newcommand{\glz}[1]{\mbox{GL} (#1,{\bf Z})}
\newcommand{\trz}[1]{\mbox{Tr}_1(#1,{\bf Z})}
\title{Finding Matrix Representations for Polycyclic Groups}
\author{Eddie H. Lo \\ Department of Defense \\ Fort Meade, Maryland \\
ehlo@afterlife.ncsc.mil
\and
Gretchen Ostheimer \\ Mathematics Department \\ Tufts University \\
gostheim@emerald.tufts.edu}
\maketitle
In this report we describe an algorithm for finding faithful matrix
representations for polycyclic groups given by finite presentations.
Experiments show that these algorithms are
efficient enough to be useful in studying some
moderately complicated examples.
They also suggest that by considering variants
on the algorithm we can increase the complexity
of the groups under consideration and still
find a reasonably-sized
representation in a reasonable amount of time.
Further experiments are needed to better understand
which kinds of presentations can be represented practically
using our techniques.
By constructing representations for a collection
of free nilpotent groups,
we were able to obtain a theoretical result
concerning such representations.
\paragraph{Experiments.}
We performed a series of experiments
in which faithful matrix representations were constructed
from consistent polycyclic presentations.\footnote{Intuitively,
a consistent polycyclic presentation is one from which the
polycyclic structure of the group is easily gleaned.
For a more precise definition, see \cite{Sims}.
If a given finite presentation is known to define a polycyclic
group, a consistent polycyclic presentation can be found
using the polycyclic quotient algorithm described in \cite{Lo:jscpqa}.}
We used an algorithm (based on that described in \cite{GO:thesis})
which when given a consistent polycyclic presentation for a group
$G$ on generators
$x_1, x_2, \ldots, x_k$, finds an integer $n$
and $k$ matrices $g_1, g_2, \ldots, g_k$ in $\glz{n}$
such that the map from $G$ to $\glz{n}$
taking $x_i$ to $g_i$ defines an embedding.
The algorithm seems to be practical.
We expected most of the time would be used in
computing Gr\"obner bases; however,
and at no time did we experience unreasonable delays
while the Gr\"{o}bner basis calculations were performed.
In all cases, the matrices obtained have small entries
(at most two digits).
The degrees of the matrices vary depending on
the complexity of the group and the presentation
chosen for the group. Some results from experimentation
on the algorithm are given below.
For $n\ge1$, take $\trz{n}$ to be
the group of upper triangular matrices
over ${\bf Z}$ with ones on the diagonal. The group $\trz{n}$ is
torsion-free nilpotent. For fixed $n$,
a consistent polycylic presentation for $\trz{n}$ is easily obtained:
the generators consist of matrices with just a single $1$ off the diagonal
(and all other off-diagonal entries equal to $0$),
and the relations describe how those matrices act on each other by
conjugation.
From such a presentation, we can use our algorithm to
obtain an embedding of degree
$n$.
For the polycyclic group $L_1$ given by
\begin{eqnarray*}
L_1 = \langle a, b, c, d & | & b ^ a = c,
c^a = d^{-2} c^3 b^{-1}, d ^ a = d, \\
& & c^b = d^{-1}c, d^b = d, d^c = d \rangle,
\end{eqnarray*}
we obtained an embedding of degree 7.
For the polycyclic group $L_2$ given by
\begin{eqnarray*}
L_2 = \langle a_1,a_2,a_3,a_4,a_5 | & a_1a_2 = a_5a_2a_1,a_1a_3=a_3a_1,
a_1a_4=a_4a_1,a_1a_5=a_5a_1,\\
& a_2a_3=a_5a_4a_3^{-1}a_2,
a_2a_4=a_5a_2,a_2a_5=a_3a_2,\\
& a_3a_4=a_4a_3,a_3a_5=a_5a_3,
a_4a_5=a_5a_4\rangle,
\end{eqnarray*}
we obtained an embedding of degree 5.
For the polycyclic group $L_3$ given by
$$L_3 = \langle a,b,c \, | \, b^a = c^3b, c^a = c^{-1}, c^b = c^{-1}\rangle,$$
we obtained an embedding of degree 5.
Note that our algorithm is not fully implemented.
We stepped through the algorithm by hand
using as tools
the Gr\"{o}bner basis method for the integral group ring
of a polycyclic group as implemented in \cite{Lo:jscpqa}
and a Maple implementation of some simple algorithms for
working with the enveloping algebra of a matrix group.
Along the way, we used ad hoc methods to simplify the construction,
to reduce the amount of the computation and to
reduce the degree of the representation.
\paragraph{Free Nilpotent Groups.}
Let $F(k,c)$ denote the free nilpotent group of rank
$k$ and class $c$. For $F(2,1),F(2,2),F(2,3)$ and $F(2,4)$,
we constructed embeddings
using the algorithm described
in this report.
For each of these groups,
we found that
the degree of the embedding obtained was equal to
$1+k+k^2+\cdots+k^c$.
We went on to prove that our algorithm
will produce a representation for $F(k,c)$
of degree $1+k+k^2+\cdots+k^c$
for all $k$ and $c$.
The proof is based on results
in \cite{Hall:nilpgrps} and \cite{Passi}.
\paragraph{Methods.}
In Chapter 5 of \cite{Segal:book},
Segal proves the existence of an embedding of an abstract polycyclic group
$G$ into $\mbox{GL}(n,{\bf Z})$ for some $n$.
Our algorithm is based on this proof,
with some important differences (described in \cite{GO:thesis}).
Every polycyclic-by-finite $G$ contains a normal subgroup
$H$ of finite index in $G$ such that $H'$,
the commutator subgroup, is torsion-free nilpotent.
In order to find such an $H$,
we use the algorithm in \cite{Lo:finiteindex}
for enumerating the subgroups of finite index
in a polycyclic group,
the algorithm in \cite{Sims} for computing
the first commutator subgroup, and
the algorithm in \cite{GO:thesis}
for deciding whether or not a given group is torsion-free
nilpotent. Having found $H$ and $H'$,
we find an embedding for $H'$
by considering an action of $H'$ on its group ring.
We then use this embedding
to construct an embedding for $H$
as described in \cite{GO:thesis}.
Basically,
we pull the embedding for $H'$ up to an embedding for $H$
one cyclic factor at a time; at each stage,
when building an embedding for a subgroup
$K$ of $H$, we study the
action of $K$ on the group ring
of a suitably chosen subgroup of $K$.
For all calculations involving the group ring,
we rely on the Gr\"obner basis method
as described
in \cite{Lo:jscpqa}.
Finally, we use
the embedding for $H$ to construct
an embedding for $G$ (as described in \cite{GO:thesis}).
\sloppy
We rely on the following algorithms
in \cite{Sims}
for working with a polycyclic group $G$ given by a finite
presentation:
\begin{itemize}
\item finding a consistent polycyclic presentation for
a section of $G$.
\item testing membership in a subgroup of $G$,
\item finding the normal closure of a subgroup of $G$,
\item finding generating sets for the terms in the lower central
series of $G$.
\end{itemize}
\paragraph{Comparisons with earlier algorithms.}
In \cite{Segal:paper}, Segal establishes the decidability
of the representation problem for polycyclic groups;
however, no attempt is made to find a practical
algorithm to construct the embedding.
For example, at one point in the construction, he
relies on an algorithm in \cite{BCRS} to solve the following problem,
known as the {\em generalized conjugacy problem}:
\begin{itemize}
\item Let $G$ be a polycyclic-by-finite group given by a finite
presentation. Let $A$ and $B$ be subgroups of $G$
(given by finite generating sets). Decide whether or
not $A$ and $B$ are conjugate in $G$.
\end{itemize}
The algorithm for the generalized conjugacy problem relies on
the fact that in a polycyclic-by-finite group,
if $A$ and $B$ have conjugate images in every finite
quotient of $G$,
then $A$ and $B$ are conjugate in $G$.
Therefore, to decide whether or not $A$ and $B$
are conjugate in $G$, one can run two processes
simultaneously.
One process enumerates all the elements $g$ of $G$,
stopping if it finds that $A^g = B$,
and another process enumerates all the finite quotients $\overline{G}$
of $G$, stopping if it finds that $\overline{A}$ is not conjugate
to $\overline{B}$.
Eventually, one of the processes will stop --- at which
point the algorithm terminates.
This algorithm is unlikely to
be practical even for very simple examples.
\paragraph{Future Work.}
The algorithm described in this report is not fully
implemented.
Furthermore, the experiments performed so far do
not test the full capability of the algorithm.
For example, all of our examples were nilpotent-by-abelian:
we did not test the impact of finite extensions
(and we suspect that this is an area in which the
algorithm will have to be improved).
A more complete implementation and further experimentation
are needed to better understand the capability of the algorithm.
An ideal implementation platform would include implementations of the following
algorithms:
\begin{itemize}
\item a Gr\"obner basis algorithm
for integral group rings of polycyclic
groups as in \cite{Lo:jscpqa};
\item a low index subgroup algorithm for polycyclic groups as in
\cite{Lo:finiteindex};
\item an algorithm to decide
if a group is torsion-free nilpotent as in \cite{GO:thesis};
\item fundamental algorithms for working with polycyclic groups
given by finite presentations as in \cite{Sims};
\item basic algorithms for integer matrices, including
integer row Hermite normal form calculations.
\end{itemize}
\paragraph{Acknowledgements.}
This work has grown out of our doctoral dissertations,
directed by Charles Sims at Rutgers.
\bibliographystyle{plain}
\bibliography{overall}
\end{document}