size of smallest generating set of a group

Question

Suppose I have a nice (e.g., word-hyperbolic? bi-automatic? automatic?) group and I want to know how big the smallest generating set is. Is that tractable (or, to put it more optimistically, what is the biggest class of groups for which it is tractable)? I am actually most interested in the question of whether there is a generating set of cardinality $2,$ but I suspect that is as hard as the general question.

EDIT What I really want to know is the answer for lattices (e.g., $SL(n, \mathbb{Z}),$) but that's probably not in any tractable class.

UPDATE It is, in fact, known that $SL(n, \mathbb{Z})$ itself is generated by $2$ elements (Hua+Reiner wrote down a generating set with three elements in 1949, as did M. Conder et al in 1992, for $SL(3, \mathbb{Z})$, but Stanton M. Trott did it with two generators in 1962). The generators are: $\begin{pmatrix} 1 & 0 & 0 & \dots & 0 \\ 1 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ . & . & . & \dots & .\\ 0 & 0 & 0 & \dots & 1 \end{pmatrix}$ and $\begin{pmatrix} 0 & 1 & 0 & \dots & 0\\ 0 & 0 & 1 & \dots & 0\\ . & . & . & \dots & .\\ 0 & 0 & 0 & \dots & 1\\ (-1)^n & 0 & 0 & \dots & 0 \end{pmatrix}$

Answer 1

I remember looking at this type of questions for finite groups and from complexity point of view. I recall it is believed (but still open) that $d(G)=2$ is a NP-complete problem even for a permutation group (given a generating set it is easy to verify that it generates the whole group, so the problem is in NP). I am not sure if this conjecture is formally stated anywhere (see here for an informal statement).

On the other hand, let me explain why it is obvious that the $d(G)=?\ 2$ problem is difficult. This has already been understood by Hall in this classical paper. Take for example $G=H^m$ where $H=A_n$ and $n!/8< m < n!/4.$ For $m=n!/8$ and $n$ large enough, $d(G)=2$, while for $m=n!/4$, $d(G)=3$. Computing where exactly the transition happens involves computing Möbius inversion of the whole subgroup lattice of $H$. This is, clearly, a Herculean task in practice if not in theory. Let me note that the probability that O(1) random elements generate $G$ goes to zero. Same story for $H=SL(2,p)$. See more here.

Answer 2

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

Update 1. $\mathrm{SL}_n(\mathbb R)$ the question is interesting.

Update 3. You may be interested in this paper They prove that the principal congruence subgroups of $\mathrm{SL}_n(\mathbb Z)$ have bounded number of generators but it is not true for all arithmeric subgroups of $\mathrm{SL}_n(\mathbb R)$.

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

Update 2. As HW noticed below, if we know that the group is hyperbolic, we can find its $\delta$.

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

Answer 3

The answer to this question is not know even in for virtually abelain groups $G$. It is well known that $d(\hat G) \leq d(G) \leq d(\hat G) +1$, where $d(G)$ is the minimal number of generators of $G$ and $d(\hat G)$ is the min number of generators for the profine completion. In this case $d(\hat G)$ is relatively easy to compute.

There are some examples where $d(G) = d(\hat G) +1$ but showing that $d(G) > d(\hat G)$ is nontrivial and uses that certain elements in the ideal class group if some ring of integers is nontrivial. It is plassible that the only obstructions for $d(G) = d(\hat G)$ (for virtually abelian $G$) are of this form, but this has not been made precise yet.

Of course if $d(G)=d(\hat G)$ one can write a stupid and slow algorithum to verrify that, but I am not awere of any alg which can show that $d(G) > d(\hat G)$.

Answer 4

There is no upper bound for finite index subgroups of $SL_n({\mathbb Z})$. That is, given any integer $k$, there exists a finite index subgroup of $SL_n({\mathbb Z})$ which needs at least $k$ generators. I do not know to whom this is originally due, but it is a remark of Rapinchuk that if you pull the centre of, say $SL_{2n}({\mathbb Z}/m {\mathbb Z})$ where $m$ is the product of $k$ distinct primes back to $SL_{2n}({\mathbb Z}) $, you get a finite index subgroup of $SL_{2n}({\mathbb Z})$ whose abelianisation has $({\mathbb Z}/2{\mathbb Z})^k$ as a quotient and hence is at least $k$ generated.

On the other hand, a finite index subgroup of $SL_n({\mathbb Z})$, contains a smaller finite index subgroup which is generated by 3 elements; this result is true for any higher rank non-uniform arithmetic group in a semi-simple linear group (and is due to Ritumoni Sarma and Venkataramana)