> < ^ Date: Wed, 17 Mar 1993 10:42:34 +0100
> < ^ From: Derek Holt <dfh@maths.warwick.ac.uk >
> < ^ Subject: Re: Infinite matrix groups

The problem as stated was to get the `first' 1000 or so elements of an
infinite matrix group rather than a random collection of elements.
Suppose the matrix group G is generated by g_1,...,g_n.
It seems to me that the natural way to do this is to start with the
free group F on generators x_1,...,x_n, and define the obvious
epimorphism phi from F to G. Now generate the first 1000 or so elements
of F, using the usual length-lexicographic ordering, and take the images
of these words under phi.

There are two problems. Firstly, there does not currently appear to be a GAP
function to spew out elements in a free group in order, although there probably
should be, and it would not be too hard to write. Secondly, if the matrix
group G has nontrivial relations, then the list of elements in G produced
will have some repetitions. If only about 1000 elements are needed, then it
would not be difficult to look for these repetitions directly (perhaps using
hash tables).

Better still, if one knows defining relations for G, then the Knuth-Bendix
procedure can be used to generate all relations in G systematically, and
then it is possible to produce repetition-free lists directly. Of course,
this is not yet possible in the GAP system, but the relevant software
does exist. We have used this technique to good advantage at Warwick in
connection with automatic groups. It has led to spectacular improvements
in efficiency in programs which draw pictures for analysts and topologists,
etc.

Derek Holt.


> < [top]