> < ^ From:

> < ^ Subject:

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]