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?

  • $\begingroup$ 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. $\endgroup$ – Derek Holt May 16 '19 at 14:59
  • $\begingroup$ 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? $\endgroup$ – user44191 May 16 '19 at 16:37
  • $\begingroup$ 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. $\endgroup$ – user44191 May 16 '19 at 16:41
  • $\begingroup$ @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. $\endgroup$ – Derek Holt May 16 '19 at 16:44
  • $\begingroup$ @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. $\endgroup$ – user44191 May 16 '19 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)$.

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Hauke Reddmann May 17 '19 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.