# Does every finitely presentable group have a presentation that simultaneously minimizes the number of generators and number of relators?

This should probably be an easy question, but I don't know how to answer it: Suppose G is a finitely generated presentable group. Suppose a is the absolute minimum of the sizes of all generating sets for G and b is the absolute minimum of the number of relations over all presentations of G. Question: Is it necessary that G has a presentation that simultaneously has a generators and b relations?

The case b = 0 is just the fact that a free group cannot be generated by fewer elements than its free rank.

The problem could probably be interpreted in terms of CW-complexes (where the generators give rise to 1-cells and the relators give rise to 2-cells) but, because of my lack of familiarity with CW-complexes, I don't immediately see how to use these to solve the problem.

It also seems to be related to the notion of "deficiency" of a group, which is the (maximum possible over all presentations) difference #generators - #relations (under the opposite sign convention, the minimum possible difference #relations - #generators).

• As I remember, if a group $G$ has presentation with $k$ relations, then for any generating set with $n$ elements the number of relations is $\leq k+n$. May 19 '10 at 17:12
• I'd guess that the abelian case should be tractable. May 19 '10 at 17:19

A stronger question, is the deficiency of $G$ realized for a presentation with the minimal number of generators (rank($G$))? This question is asked in a paper of Rapaport, and proved to be true for nilpotent and 1-relator groups.

The question appears as Question 2, p. 2, of a book by Gruenberg. Lubotzky has answered the analogous question affirmatively in the category of profinite groups (Corollary 2.5). (Note though that this is in the category of profinite presentations, so it does not imply an affirmative answer even for finite groups).

• Thanks! That is very helpful and seems to answer my question (or rather, indicate what's known about the answer to the question). May 19 '10 at 22:55
• This paraphrasing isn't immediately equivalent to the original question: why couldn't there be a group with rank 4 and 6 relations which admits a presentation with 6 generators and 7 relations that realizes deficiency bound? May 19 '10 at 23:27
• Yes Victor, the condition is only sufficient. I changed the wording. May 20 '10 at 1:53
• I think the 1-relator group case is almost trivial: a group with a presentation with $n$ generators and 1 relator can only be generated by less than $n$ elements if it's free. Also, the link to the Gruenberg book seems to be wrong (I don't know what book you're linking to; Relation Modules?) May 20 '10 at 3:14
• Thanks Steve, I fixed the link. The 1-relator case is indeed trivial, but I was pointing out that it appears in the paper. May 20 '10 at 4:57

This is not an answer, but merely an observation that there can be no computable procedure to transform any given finite presentation into a presentation that is optimal in your sense. The reason is that the problem of determining if a finitely presented group is nontrivial is not computably decidable, but it is computably decidable from any optimal presentation, since the trivial group and only the trivial group has a=b=0.

So an affirmative answer cannot proceed by modifying the given presentation in some computable manner.

• Except for some classes of presentable groups which are decidable. May 19 '10 at 19:05
• In fact, something even stronger follows, namely that you can't algorithmically minimise the number of generators. (It's easy to check if a cyclic group is trivial!)
– HJRW
May 19 '10 at 19:37
• Yes, and you also can't computably minimize the number of relations, since it is easy to check if a free group is trivial. May 19 '10 at 19:55