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