On the difficulty of presenting finitely presentable groups
Martin R. Bridson and Henry Wilton
To appear in Groups, Geometry and Dynamics (special volume for Fritz Grunewald)
We exhibit classes of groups in which the word problem is uniformly solvable
but in which there is no algorithm that can compute finite presentations for
finitely presentable subgroups. Direct products of hyperbolic groups, groups
of integer matrices, and right-angled Coxeter groups form such classes. We
discuss related classes of groups in which there {\em{does}} exist an algorithm
to compute finite presentations for finitely presentable subgroups. We also
construct a finitely presented group that has a polynomial Dehn function but
in which there is no algorithm to compute the first Betti number of its finitely
presentable subgroups.
24 pages, no figures.