> < ^ From:

> < ^ Subject:

Dear GAP forum,

Dr. Keith Briggs asked:

Does anybody know an efficient method for listing all presentations

of a given group with a given number of generators?

Just to add to Joachim Neubueser's response to this, it is worth observing

that even for two-generator presentations of the trivial group, this

problem is impossible, or at least impossibly difficult, depending on

how you choose to interpret it. There are are infinitely many completely

unrelated presentations of this form, and it is a theoretically undecidable

problem whether or not a given presentation defines the trivial group.

If you mean 'list' in the recursively enumerate sense, then you could of

course theoretically set a Todd-Coxeter process with unbounded memory (if you

can afford such a machine!) going for each possible presentation, and it would

be guaranteed to complete eventually for all presentations of finite

groups.

A more interesting and tractable question might be to find all two

generator presentations of the trivial group with total relator length

at most n. It would be at least interesting to see how large you could

make n before it became impossible. I suspect you would get stuck

while n was still a single digit.

Derek Holt.

Miles-Receive-Header: reply

> < [top]