\documentclass[12pt]{article}
\usepackage{amssymb,amsmath}
\def\aut{{\rm Aut}}
\def\gl{{\rm GL}}
\def\calh{{\cal H}}
\def\cala{{\cal A}}
\def\calk{{\cal K}}
\def\calu{{\cal U}}
\def\calv{{\cal V}}
\def\Z{{\mathbb Z}}
\def\Q{{\mathbb Q}}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}
\begin{document}
\title{Three problems for the Oberwolfach meeting on\\
computational group theory}
\author{Charles~C. Sims\\
Mathematics Department\\
Rutgers University\\
\texttt{sims@math.rutgers.edu} }
\date{May 26, 1997}
\maketitle
In this note I want to discuss three problems which range from
relatively straight-forward to apparently quite challenging. In
summary, the problems are:
\begin{enumerate}
\item Determine the lattice of characteristic subgroups of the
restricted Burnside group $R(2,5)$.
\item Construct fast routines for computing products of elements
in the Burnside group $B(2,6)$.
\item Find an (efficient?) algorithm for deciding membership in
finitely generated rings of rational matrices.
\end{enumerate}
\section{Characteristic subgroups of $R(2,5)$}
The group $R(2,5)$ has order $5^{34}$. The order of the automorphism
group of $R(2,5)$ is
\[
|\gl(2,5)|\,5^{64} = 2^5\cdot3\cdot5^{65}.
\]
If $G$ is a two-generator group, then $|\aut(G)|$ is at most $|G|^2$.
Since
\[
\frac{|\aut(R(2,5))|}{|R(2,5)|^2} = 0.768,
\]
$\aut(R(2,5))$ is ``nearly as large as it could be''. Because
$R(2,5)$ has so many automorphisms, it is reasonable to expect that
$R(2,5)$ has very few characteristic subgroups.
I wrote a simple GAP program to look for characteristic subgroups of
$R(2,5)$. The program found 27 subgroups. The lattice formed by
these subgroups is pictured in a three-page attachment to this note.
Each subgroup other than $R(2,5)$ itself is described either as
$[i,j]$ or as $Z(i/j)$. In the first case the subgroup is the
commutator of the subgroups numbered $i$ and $j$. In the second case,
the subgroup is the inverse image in $R(2,5)$ of the center of the
quotient of subgroups $i$ and $j$. This permits each subgroup to be
constructed quickly and immediately demonstrated to be characteristic.
It is plausible that there are only 27 characteristic subgroups of
$R(2,5)$. The tools exist to decide this. For example, there are
algorithms based on the meataxe to find the complete lattice of
submodules of a finite dimensional module for a finite group over a
finite field. It would suffice to apply this algorithm to the action
of $\aut(R(2,5))$ on certain abelian quotients in the lattice of 27
subgroups.
\section{Computing in $B(2,6)$}
I am interested in determining the ``short relations'' which hold in
the finite groups $R(2,5)$ and $B(2,6)$. This means for each group
determining the balls of radius $r$ for $r$ as large as possible. The
ball of radius $r$ in a group $G$ relative to a generating set $X$ is
the set of all elements of $G$ which can be expressed by group words
over $X$ of length at most $r$. Computing large balls requires fast
multiplication in $G$ and efficient data structures.
Given a fixed polycyclic generating sequence for $R(2,5)$, there is a
natural identification of $R(2,5)$ with a 34-dimensional vector space
over GF(5). Any function from a vector space over a finite field to
another vector space over the same field is given by polynomials in
the coordinates. This means that multiplication in $R(2,5)$ can be
described by polynomials. Using a combination of GAP, Maple, and an
optimizing C compiler, I have produced C functions for multiplying in
$R(2,5)$ which seem to work quite well. The functions require a
substantial amount of memory.
Although $B(2,6)$ is smaller than $R(2,5)$, I can not at the moment
compute in $B(2,6)$ as fast as I can in $R(2,5)$. A nilpotent group
$G$ of exponent 6 is the direct product of its Sylow 2-subgroup and
its Sylow 3-subgroup. Multiplication in each Sylow group can be
described by polynomials (the Sylow 2-subgroup is abelian) and thus
multiplication in $G$ can be carried out rapidly. Unfortunately,
$B(2,6)$ is not nilpotent. There is a nilpotent normal subgroup $N$
in $B(2,6)$ of quite small index. Perhaps a fast way to compute in
$B(2,6)$ is to compute in $N$ using polynomials and store the products
of all pairs of coset representatives of $N$ and also the action of
these representatives on generators for $N$. Storing all of this
information would use a significant amount of memory.
This discussion suggests a general question which may or may not be
worth investigation:
\begin{itemize}
\item Do finite groups differ in essential ways in the efficiency of
their multiplication algorithms given limited memory?
\end{itemize}
As stated, this is an extremely vague question. Let me try to make it
more precise. Let $G$ be a finite group of order $n$, let $S$ be a
set of bit strings of fixed length ``not too much larger than'' $\log
n$, and let $f$ be a bijection from $G$ to $S$. A multiplication
algorithm $M$ for $G$ relative to $S$ and $f$ is an algorithm which
takes as inputs two elements $s$ and $t$ of $S$ and computes the
string
\[
f(f^{-1}(s)\bullet f^{-1}(t)),
\]
where $\bullet$ denotes multiplication in $G$.
For a given model of computation, there is a notion of the size of
$M$, the minimum length of a bit string needed to describe $M$ plus
the number of bits needed for data storage. (I am assuming our
computer is fixed independently of $G$, so that coding the
multiplication of $G$ into the hardware is not possible.) For
definiteness, I include in ``data'' any information built into the
algorithm initially and any intermediate results. If one wanted, this
could be restricted to just the initial data. Let $T(M)$ be the
maximum time or number of bit operations needed by $M$ for any
possible pair of strings $s$ and $t$.
For a positive number $r$, let $E_G(r)$ be the minimum of $T(M)$ over
all sets $S$, all bijections $f$, and all algorithms $M$ such that the
size of $M$ is at most $r$. If $r$ is big enough, then we can code
the entire multiplication table for $G$ into $M$. In this case
$E_G(r)$ will be $O(\log n)$. What is interesting is $E_G(r)$ when
$r$ is small, say less than $(\log n)^k$ for some fixed $k$.
If $G$ is the symmetric group of degree $m$, then $E_G(r)$ is bounded
by $O(\log n)$ for all $r$ bigger than about $3m\log m$. It seems
unlikely that products in arbitrary groups of comparable order can be
computed so efficiently.
Notice that I am not asking for an efficient construction of optimal
multiplication algorithms. This is almost certainly not possible.
\section{Rational matrix rings}
The algorithmic questions discussed here are not really
group-theoretic. They were motivated by the following observations.
Let $\Q$ be the field of rational numbers and let $S$ be a small finite
set of $n$-by-$n$ rational matrices. Set $A$ equal to the
$\Q$-algebra generated by $S$. It is obviously possible to find a
$\Q$-basis for $A$ and using this basis to decide membership in $A$,
although the size of the entries in the basis can be large enough that
the computation is in no sense trivial.
On the other hand, suppose the elements in $S$ are invertible and $n$
is at least 4. Then $\gl(n,\Q)$ contains subgroups isomorphic to the
direct product of two free groups of rank two. Determining membership
in finitely generated subgroups of such groups is undecidable. Thus
in general we can not decide membership in the subgroup $G$ of
$\gl(n,\Q)$ generated by $S$.
Let $R$ be the ring (with identity) generated by $S$. Deciding
membership in $R$ appears, at least initially, to be intermediate
between the membership problems for $A$ and $G$. Of course, deciding
membership in $R$ makes sense even when some of the elements of $S$
are singular.
A subring $R$ of $\Q$ is determined by the set of prime integers
invertible in $R$. Thus if $R$ is given by a finite set of
generators, we have only to find the distinct prime factors in the
denominators of the generators. We can describe $R$ as $\Z[1/d]$,
where $d$ is the product of these primes. Thus the ring membership
question is certainly decidable for $n=1$.
For $n>1$, things seem much harder. I initially attempted a Gr\"obner
basis solution, but the necessary Gr\"obner bases may not be finite.
Let me sketch briefly this approach and the problems that arise.
For an arbitrary ring $R$ and a finite set $X$ of indeterminates, let
$R[X]$ be the ring of polynomials with coefficients in $R$ in the
(commuting) variables in $X$ and let $R\langle X\rangle$ be the free
$R$-algebra generated by $X$, the algebra of ``polynomials'' where the
variables are not assumed to commute.
Let $T$ be the subring of $\Q$ generated by the entries in the
elements of $S$. As noted, we can determine $T$. Clearly $R$ is
contained in the $T$-algebra $U$ generated by $S$. Moreover, $U$ is
finitely generated as a $T$-module and we can decide membership in $U$.
Let $T= \Z[1/d]$, where $d$ is positive and square free, and let $u =
I_n/d$, where $I_n$ is the $n$-by-$n$ identity matrix.
Let $P$ be an $n$-by-$n$ matrix over $\Q$. If $P$ is not in $U$, then
$P$ is certainly not in $R$. If $P$ is in $U$, then we can obtain a
element $E$ in $\Z\langle S\rangle[u]$ which defines $P$. The question
is: does there exist an element $F$ in $\Z\langle S\rangle$ which
defines $P$?
Let $J$ be the kernel of the homomorphism from $\Z\langle S\rangle[u]$
to $U$. If we could find ideal generators for $J$, and if we could
produce a finite Gr\"obner basis for $J$ relative to the ordering of
the standard $\Z$-basis for $\Z\langle S\rangle[u]$ which is the wreath
product of the length-plus-lexicographic orderings on the free monoids
generated by $u$ and by $X$, then we could reduce $E$ with respect to
this Gr\"obner basis. Our matrix $P$ is in $R$ if and only if the
result of the reduction does not involve $u$. Unfortunately, it is
not clear that $J$ is finitely generated and even when it is, the
necessary Gr\"obner basis may not be finite.
There are many questions related to the membership problem for $R$.
These include:
\begin{itemize}
\item Find the ring of all scalar matrices in $R$.
\item Find the ring of all matrices in $R$ with integer entries.
\item Decide whether $R$ is finitely generated as an additive
abelian group.
\end{itemize}
The first problem seems doable and using techniques of Robert Beals so
does the third. Let $S_1$ be the set of matrices obtained by clearing
denominators in the elements of $S$. Then the ring generated by $S_1$
has finite index as an additive abelian group in the ring of all
integer matrices in $R$. It follows that if we can decide membership
in $R$ we can solve the second problem as well.
\end{document}