Return to Revisions

@Igor: If I remember correctly, for lattices in $\mathrm{SL}_n(\mathbb R)$, $n\ge 2$, the answer is 2 (perhaps somebody can correct me here). So the algorithm is easy. I think the proof involves arithmeticity of these lattices. For hyperbolic groups there exists a result of Arzhantseva-Olshanskii (Arzhantseva, G. N.; Olʹshanskiĭ, A. Yu. Generality of the class of groups in which subgroups with a lesser number of generators are free. Mat. Zametki 59 (1996), no. 4, 489--496) that generically hyperbolic groups given by $n$ generators and a number of relations are $n$-generated. Thus if you have a random presentation with $n$ generators, it gives a group which cannot be generated by fewer elements. I do not think there is a known algorithm that outputs the smallest number of generators given a presentation plus the additional information that the group is hyperbolic (CAT(0), etc.). But if in addition to hyperbolicity you also know the $\delta$ (hyperbolicity constant), then the algorithm should exist simply because you should not search too far for the generators: every generating set should consist (up to conjugacy) of relatively short elements. The proof may follow from a paper by Arzhantseva (or Kapovich-Weidmann) Arzhantseva, Goulnara N., A dichotomy for finitely generated subgroups of word hyperbolic groups. Topological and asymptotic aspects of group theory, 1–10, Contemp. Math., 394, Amer. Math. Soc., Providence, RI, 2006 (resp. Kapovich, Ilya; Weidmann, Richard Nielsen methods and groups acting on hyperbolic spaces. Geom. Dedicata 98 (2003), 95–121. )