# Generators for permutation groups

Consider (e.g.) the full permutation group $$G=S_6$$. A valid set of generators and equations for $$G$$ is $$r^6=m^2=(rm)^5=1$$. I say this system has width $$3$$ (because there are $$3$$ equations), length $$10$$ (because there are $$10$$ generators in $$(rm)^5$$ - arguably, $$m$$ as a mirror causes no "load" in which case the length would be $$6$$) and height $$6$$ (for the exponent $$6$$).
What is the generator set with minimum height or length or width or (best) everything at the same time? How do I find it in the general case?

• I don't understand what you are asking. The group defined by the presentation $\langle r,m \mid r^6=m^2=(rm)^5=1 \rangle$ is not $S_6$; it is an infinite group. – Derek Holt May 16 at 14:59
• Width and length both seem relatively simple to define in terms of a presentation, but height doesn't - what if the presentation was $rrrrrr = mm = rmrmrmrmrm = 1$? Or $rrmmrrrr = mm = rmrmrmrmrm = 1$ How would you get $6$ out of that? – user44191 May 16 at 16:37
• Additionally, given any finite presentation, you can find a presentation of "length" $2$ (but with high width and many generators). So trying to get a "(best) everything at the same time" doesn't work; you will have to specify some single thing you want to minimize. – user44191 May 16 at 16:41
• @user44191 Both you and Francesco Polizzi in his answer are talking about presentations, but there is no mention of presentations in the question, and the example given is not a presentation for $S_6$, so I am not at all sure that the question is about presentations. – Derek Holt May 16 at 16:44
• @DerekHolt "set of generators and equations" seems like a description of a presentation to me. I was focusing more on the (partial) definitions than the specific group, as they seem to be applicable to any presentation. – user44191 May 16 at 19:08

There is a well-known Coxeter presentation of $$S_n$$ having height $$3$$.

Regarding presentations with short width and length (again, in the general case) you can have a look at the paper

Bray, J. N.; Conder, M. D. E.; Leedham-Green, C. R.; O’Brien, E. A.: Short presentations for alternating and symmetric groups, Trans. Am. Math. Soc. 363, No. 6, 3277-3285 (2011), ZBL1223.20023.

For instance, the authors show hot to construct a presentation in two generators having width $$O(\log n)$$ and length $$O(\log^2 n)$$.

This is an answer to your question in your comment rather than to the original question. With a bit of computer experimentation, I found that $$S_6 \cong \langle m,r | r^6=m^2=(rm)^5 = (mr^2mr^{-2})^2 = (mrmr^{-1})^3 = 1 \rangle.$$ You can reduce that to three relations, by combining the first two, and the final two to give

$$S_6 \cong \langle m,r | r^6=m^2,\ (rm)^5 = 1,\ (mr^2mr^{-2})^2 = (mrmr^{-1})^3 \rangle.$$

Since the Schur Multiplier of $$S_6$$ is nontrivial (it has order 2), every presentation must have at least pone more relation than generator, so you cannot define $$S_6$$ with two relations.

• Converting to the Coxeter presentation, I got the same result (but didn't know which of the additional equations are needed - THX!). I guess my "technique" I used to get a matrix 5-dim irrep of S6 automagically fulfilled the other equations, thus my error. – Hauke Reddmann May 17 at 11:04