27
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – Ievgen Bondarenko
    Commented May 19, 2010 at 17:12
  • $\begingroup$ I'd guess that the abelian case should be tractable. $\endgroup$
    – Noah Snyder
    Commented May 19, 2010 at 17:19

2 Answers 2

Reset to default
17
$\begingroup$

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.

Addendum:

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

Improve this answer
$\endgroup$
13
  • $\begingroup$ Thanks! That is very helpful and seems to answer my question (or rather, indicate what's known about the answer to the question). $\endgroup$
    – Vipul Naik
    Commented May 19, 2010 at 22:55
  • 1
    $\begingroup$ 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? $\endgroup$
    – Victor Protsak
    Commented May 19, 2010 at 23:27
  • $\begingroup$ Yes Victor, the condition is only sufficient. I changed the wording. $\endgroup$
    – Ian Agol
    Commented May 20, 2010 at 1:53
  • $\begingroup$ 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?) $\endgroup$
    – Steve D
    Commented May 20, 2010 at 3:14
  • $\begingroup$ Thanks Steve, I fixed the link. The 1-relator case is indeed trivial, but I was pointing out that it appears in the paper. $\endgroup$
    – Ian Agol
    Commented May 20, 2010 at 4:57
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Except for some classes of presentable groups which are decidable. $\endgroup$
    – ogerard
    Commented May 19, 2010 at 19:05
  • $\begingroup$ 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!) $\endgroup$
    – HJRW
    Commented May 19, 2010 at 19:37
  • $\begingroup$ Yes, and you also can't computably minimize the number of relations, since it is easy to check if a free group is trivial. $\endgroup$
    – Joel David Hamkins
    Commented May 19, 2010 at 19:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .