Hi. I would like to be able to do the following thing: I have a
presentation of a finite group G, and I would like to be able to know,
say, the 100 "shortest" ways of expressing a word in the generators
which represents the identity in G as a product of conjugates of
relators. Is this easy to do in GAP? If not, do you know of another
program which does this?

Tim Hsu

I think that is an extremely difficult problem, and I have never heard of
any kind of reasonable algorithmic approach to it. It is probably even
harder than Martin suggested in his reply, because one is not looking for
an expression of the trivial word as a product of relators, but as a product
of conjugates of relators.

In principal, the Knuth-Bendix algorithm, which systematically generates
consequences of the defining relations can be used to produce a machine
derivation of the triviality of any word in the generators which maps
onto the identity, and this could, theoretically, be used to express the
word as a product of conjugates of defining relators, but the result would
typically be a very long word indeed!

I know the question was about finite groups, but there are some theoretical
results of a more general nature that are related to this question. If
f(n) is the largest number of conjugates of defining relators that are
required to express any trivial word of length n, then f(n) is called
the isoperimetric function for the group (more precisely for the presentation).
For finite groups, f(n) will have a maximal value, but infinite hyperbolic
groups have a linear isoperimetric function, automatic groups have a
quadratic, nilpotent groups have a polynomial, etc.

Derek Holt.