> < ^ Date: Thu, 06 Nov 2003 15:22:46 +0000
< ^ From: Derek Holt <dfh@maths.warwick.ac.uk >
^ Subject: Follow-up to old message

Dear GAP Forum

Readers might be interested to know that the old posting of mine below,
which was accidentally re-circulated to the GAP Forum yesterday, elicited a
response from george Havas.

Derek Holt.

On Fri, 4 Feb 2000, Derek Holt wrote:

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.
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.

Well, a paper which appeared this year:

TITLE: Short balanced presentations of perfect groups
AUTHORS: George Havas and Colin Ramsay
CITATION: Groups St Andrews 2001 in Oxford, London Mathematical Society
Lecture Note Series 304, Cambridge University Press (2003) 238-243

solves this problem for n up to 17. I am sure I can solve it up to at
least n = 20, and if pressed somewhat higher.


George Havas http://www.itee.uq.edu.au/~havas
ARC Centre for Complex Systems
School of Information Technology and Electrical Engineering
The University of Queensland, Queensland 4072 AUSTRALIA

> < [top]