> < ^ From:

> < ^ Subject:

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.

> < [top]