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$
$\endgroup$
7
asked May 16, 2019 at 13:46
-
$\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 HoltCommented May 16, 2019 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$– user44191Commented May 16, 2019 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$– user44191Commented May 16, 2019 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 HoltCommented May 16, 2019 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$– user44191Commented May 16, 2019 at 19:08
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
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)$.
answered May 16, 2019 at 14:46
$\begingroup$
$\endgroup$
1
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.
answered May 17, 2019 at 10:10
-
$\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$ Commented May 17, 2019 at 11:04