# Efficient presentations for finite groups

A finitely presented group which has more generators than relations has an infinite abelianization and so is an infinite group. Therefore, for a finite group, all presentations must have at least as many relations as generators. A presentation for a finite group is called efficient if the number of generators equals the number of relations.

I know the following examples of efficient presentations for finite groups with $2$ generators:

$< x,y | x^{2} = y^{2} = (xy)^{n}>$, for any $n \geq 2$, which is a group of order $4n^{2}-4n$ in which $xy$ has order $2n^{2}-2n$ and conjugating through $x$ or $y$ sends $xy$ to $(xy)^{2n-1}$. (When $n=2$, this is the quaternion group of order $8$.)

$< x,y | x^{3} = y^{3} = (xy)^{2}>$, which is a double cover of $A_{4}$ isomorphic to $SL(2,3)$. This group is isomorphic to the group of quaternion units, together with $\pm \frac{1}{2} \pm \frac{i}{2} \pm \frac{j}{2} \pm \frac{k}{2}$.

$< x,y | x^{4} = y^{3} = (xy)^{2}>$, which is a double cover of $S_{4}$ not isomorphic to $GL(2,3)$. This is isomorphic to the preceding group, together with every quaternion of the form $\pm \frac{u}{\sqrt{2}} \pm \frac{v}{\sqrt{2}}$, where $u$ and $v$ are two distinct elements of the set $\{ 1, i, j, k \}$.

$< x,y | x^{5} = y^{3} = (xy)^{2}>$, which is a double cover of $A_{5}$ isomorphic to $SL(2,5)$. This is isomorphic to the group of unit quaternions representing $SL(2,3)$ as above, together with a set of icosians explicitly described in Conway and Sloane's SPLAG, which I am too lazy to describe here.

All of these groups have a central element of order $2$, and except for the members of the infinite family that have $n$ being odd, a subgroup isomorphic to the quaternion group of order $8$.

How does this generalize to larger numbers of generators, or, at least, what are some examples of efficient presentations of finite groups using $3$ generators? (I need not explain why I know all examples of efficiently presented groups with a single generator.) Is there a group analogous to the quaternion group of order $8$ for each number of generators? Is there a group analogous to $SU(2)$, which has subgroups isomorphic to the smallest member of the infinite family and all three exceptional examples? Is the center of a nontrivial finite group possessing an efficient presentation always nontrivial? (And what is a good reference for discussing this?)

-
And the obvious omitted question: Are there other examples using 2 generators? –  DavidLHarden Mar 29 '11 at 4:09
Just a remark (which you probably know): the groups $G = \langle X \mid R \rangle$ you're after, have trivial Schur multiplier, since in general the Schur multiplier is generated by (at most) $|R| - |X|$ elements. –  Tom De Medts Mar 29 '11 at 7:58
@David - As one example, see the presentation of the "covering group of $M_{22}$" given in the paper "Short balanced presentations of perfect groups" by Havas and Ramsay. –  Sam Nead Mar 29 '11 at 16:14

You asked about the center of a group with an efficient presentation: the relation of "central" to "efficient presentation" is probably strongest in the Schur multiplier. In particular, a perfect group can only have an efficient presentation if its Schur multiplier is trivial (so it is the universal perfect central extension of its inner automorphism group). If the inner automorphism group has a non-trivial Schur multiplier, then the perfect group with an efficient presentation must have a non-trivial center.

However, many perfect groups have trivial Schur multipliers and centers. For instance, the Mathieu group M11 has an efficient presentation on two generators with two relations, and of course has a trivial center.

Efficient presentations are somewhat poorly named (balanced might be better) since they are typically awful for computational group theory. However, people have taken them as a challenge, and so you can find scores of papers dealing with efficient presentations of (covering groups of) finite simple groups. One paper with nice tables is:

Campbell, Colin M.; Havas, George; Ramsay, Colin; Robertson, Edmund F. Nice efficient presentations for all small simple groups and their covers. LMS J. Comput. Math. 7 (2004), 266–283. MR2118175 Online version.

Note that efficient is sometimes defined in terms of the rank of the Schur multiplier. So be careful that your usage may contradict some of the papers (which give "efficient" presentations for groups with non-trivial Schur multiplier; they are allowed to use one extra relation per independent generator of the Schur multiplier).

A related concept is an asymptotic version that seeks to describe how complicated presentations of finite simple groups get. In fact it seems they are very, very simple:

Guralnick, R. M.; Kantor, W. M.; Kassabov, M.; Lubotzky, A. Presentations of finite simple groups: a quantitative approach. J. Amer. Math. Soc. 21 (2008), no. 3, 711–774. MR2393425 DOI:10.1090/S0894-0347-08-00590-0

where it is shown that there is an absolute constant C so that a total C generators and relations is needed to define a presentation of a finite quasi-simple group, and indeed the total word length of the relations is bounded by C*(log(n)+log(q)) where n is the rank of the BN-pair and q is the size of the field of definition (and alternating and sporadic groups just get less than C). They left out the case of Ree groups (the characteristic 3 kind), but probably it will be taken care of at some point.

If you want to explore these things in GAP, part of the documentation for GAP is dedicated to this problem:

http://www.gap-system.org/Doc/Examples/balanced.html

-

Groups like SL(2,p) are also efficent

-

Perhaps you would like Coxeter and Moser's book "Generators and relations for discrete groups".

Edit - it just clicked in my head that your notion of efficient presentation is identical to that of a balanced presentation. These appear in a central way in the statement of the Andrews-Curtis Conjecture (ACC): can any balanced presentation of the trivial group be transformed into the trivial presentation of the trivial group using only the four AC-moves and their inverses?

The AC-moves are

1. (invert) replace a relation $r_i$ by $r_i^{-1}$
2. (handle slide) replace $r_i$ by $r_i r_j$ where $i \neq j$
3. (conjugate) replace $r_i$ by $w r_i w^{-1}$ where $w$ is any word in the generators
4. (stabilize) add a new generator $x_{n+1}$ and a new relator $r_{n+1} = x_{n+1}$.

The unstabilized ACC does not permit us to use the fourth move. These statements of the ACC are copied out of Rolfsen's talk "The Poincaré Conjecture and its cousins" -- the slides give a nice discussion and further references.

Anyway, there is a lot of literature on this --the ACC is thought to be very tough. So there is no good theory for balanced presentations of the trivial group. I'm not sure that you can hope for a good theory of balanced presentations of non-trivial groups. I'll certainly read the other answers to this question!

Now, to answer your first question: using stabilization you can take a given balanced presentation and crank up the number of generators and relations as much as you want.

I'll end with one more remark. The groups you list above are fundamental groups of three-dimensional space forms. That they have balanced presentations with two generators is a consequence of the fact that all such space forms have Heegaard splittings of genus at most two.

-

Suppose $G$ is a finite $p$-group and $d$ is its minimal number of generators. If $G=\left< X | R \right>$, where $|X|=d$ and $|R|=r$, then $r \geq d^2/4$. So if $d>4$ you certainly cannot have an efficient presentation. (If you increase the number of generators, you will need also to increase the number of relations by at least the same amount).

I think this could somehow be applied to any finite group. However, you need to be more careful as you have to to talk about pro-$p$ presentations. So I have to think about it.

Edit: Thinking about it a bit more, I cannot see how to extend this to any finite group. Also, like Sam I think these are called balance presentations.

Edit2: I forgot to mention that the inequality above is the Golod-Shafarevich inequality or at least a specifc case of it.

-