From: rusin@math.niu.edu (Dave Rusin)
Newsgroups: sci.math.research
Subject: Re: Rabin's theorem about trivial groups
Date: 12 Nov 1998 15:29:57 GMT

David Epstein  <dbae@maths.warwick.ac.uk> wrote:
>I would be grateful for a reference to the paper by Rabin in which he
>proves that there is no algorithm which has as input a finite
>presentation and output whether the group is trivial or not.

   Rabin, Michael O.
   Recursive unsolvability of group theoretic problems. 
   Ann. of Math. (2) 67 1958 172--194.
   Math Reviews 22 #1611 20.00 (02.00)

I would've responded directly to the poster except that this literature
search turned up another result relevant to a recent thread in sci.math:
that the isomorphism question, unsolveable in general, is solvable for
p-groups, and indeed a serviceable algorithm is described:

   O'Brien, E. A.(5-ANUM-MA)
   Isomorphism testing for $p$-groups. 
   J. Symbolic Comput. 17 (1994), no. 2, 131, 133--147.
   Math Reviews 95f:20040b 20D15 (20D45 20F28)

>Where is the most readable account?
Oh come on, this stuff's easy! :-)

dave
==============================================================================

From: Dave Rusin <rusin@math.niu.edu>
Date: Thu, 12 Nov 1998 21:11:34 -0600 (CST)
To: MANN@vms.huji.ac.il
Subject: Re:  c

I don't understand what Rips and Sela have proven, then. When you say
the isomorphism problem is soluble for hyperbolic groups, do you mean
that the groups are given as being generated by a finitely collection
of automorphisms of hyperbolic space? Must the relations among them be
explicitly given too? I assume the question of recognizing a finitely
presented group to be hyperbolic is unsolvable, then?

As you can tell I am not very well versed in this area. I appreciate the
times you have set me straight.

dave
==============================================================================

Date:     Fri,  13 Nov 98 16:44 +0200
From: MANN@vms.huji.ac.il
To: Dave Rusin <rusin@math.niu.edu>
Subject:  Re:  c

Dear Dave
I'm also not an expert in this area. I'll find out from Rips and Sela next
wek what is the exact formulation of their theorem. But it's already clear
that we're discussing two possibly different concepts. When I said "hyperbolic"
groups I should have said "Gromov hyperbolic" or "word hyperbolic". This class
of groups has several equivalent definitions, e.g. in reference to the metric
properties of its Cayley graph, and I believe that it's not known yet if they
are the same as the f.g. groups of automorphisms of hyperbolic space.
It's true that the Rips-Sela result implies that the problem of knowing whether
a given finite presentation defines a word hyperbolic group is insoluble.
Best wishes
Avinoam