# size of smallest generating set of a group

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}$

-
You mean, sacrificing a goat and dancing around a campfire is better than an algorithm? If not, what do you mean? I am somewhat confused... –  Igor Rivin Sep 26 '11 at 13:35
Sacrificing a goat would be more effective than running some algorithms in combinatorial group theory :) –  Andy Putman Sep 26 '11 at 14:21
@quid : Algorithms in combinatorial group theory often have absurdly long run times. For instance, to solve the word problem for residually finite groups, you have one computer enumerating all finite groups and all possible homomorphisms to those finite groups and one computer systematically enumerating relations in the group. Eventually one of these computers will win (the first one showing that a word in the generators is nontrivial, the second one showing that the word is a relation), but the mind boggles trying to estimate the runtime... –  Andy Putman Sep 26 '11 at 15:45
@quid: in addition, what Richard really meant, i think, is that in some cases there are heuristics for UNDECIDABLE problems which work reasonably well in practice (Todd-Coxeter is the poster child for this) –  Igor Rivin Sep 26 '11 at 15:49
Kapovich and Weidmann proved that the rank is computable for Kleinian groups. front.math.ucdavis.edu/0407.5438 Their method should apply more generally to hyperbolic groups which are locally quasi-convex. –  Ian Agol Sep 27 '11 at 4:58

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.

-
In addition, there is the following cute fact of Neumann + Neumann: Every countable group is a subgroup of a $2$-generator subgroup, see Galvin, Fred(1-KS) Embedding countable groups in 2-generator groups. Amer. Math. Monthly 100 (1993), no. 6, 578–580. 20F05 for a one page proof. –  Igor Rivin Sep 28 '11 at 11:07

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

-
You need more than $2$ generators for lattices in $SL_n(\mathbb{R})$. The abelianizations of the level $p$ congruence subgroups of $SL_n(\mathbb{Z})$ have rank $n^2-1$ (see the paper "On the homology and cohomology of congruence subgroups" by Lee-Szczarba), so you need at least $n^2-1$ generators to generate them. –  Andy Putman Sep 27 '11 at 2:15
@Andy: Thanks! Is $n^2-1$ the upper bound for all the lattices in $SL_n$? I will correct the answer. –  Mark Sapir Sep 27 '11 at 2:52
I'm not sure what the correct upper bound should be, and would be very interested in knowing the answer. –  Andy Putman Sep 27 '11 at 3:28
Mark - Papazoglou's algorithm will find a constant $\delta$ given a presentation of a word-hyperbolic group. –  HJRW Sep 27 '11 at 7:48
@HW: You are right of course, one just needs to check if $\delta=1, 2,...$. –  Mark Sapir Sep 27 '11 at 9:23

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

-

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)

-
This is stated (complete with proof very similar to what you give) in the paper of Venkataramana and Soifer (without attribution to Rapinchuk. They also give estimates for principal congruence subgroups (for which the number IS bounded by some function of $n$ only) –  Igor Rivin Jul 16 '12 at 14:08