1
$\begingroup$

Let $S=\{(1,2),(1,2,\ldots,n),(1,n,,n-1,\ldots,2)\}$ be a subset of the symmetric group $S_n$. Let $a=(1,2),b=(1,2,\ldots,n),c=(1,n,n-1\ldots,2)$ be the elements of $S$. My question is, since $S$ is a generating set of $S_n$, what are the distinct shortest words in the set $S$ that enunciate all the elements of $S_n$. That is, how do we describe one set of distinct words which give rise to all the elements of $S_n$; or, I want one set of $n!$ minimal words(with exponents of each letter being positive) which give the elements of $S_n$.

Since the word problem on finite groups is solvable, I think there would be a way to enunciate all such elements. Since only $a,b$ are sufficient to generate the whole group, so I was thinking along the lines of $a, ba,b^2a,\ldots,b^{n-1}a=ca,ab,ab^2,\ldots ab^{n-1}=ac,aba,abab,abab^2,\ldots,abab^{n-1}=abac\ldots$. Is there a right way to enunciate such words? Thanks beforehand.

Improve this question
$\endgroup$
17
  • 1
    $\begingroup$ Just think about the cycle decomposition of elements of $S_n$. Moreover, you do not need $c$, i.e. $\{a,b\}$ generates. $\endgroup$
    – Ryan Budney
    Commented May 27, 2022 at 8:20
  • 2
    $\begingroup$ Each element of $S_n$ can be expressed in infinitely many different ways as a word in the generators. So you need to be more precise in what you are asking. You could ask for a shortest word representing each element (which is still not unique), or you might prefer something with a more concise description. $\endgroup$
    – Derek Holt
    Commented May 27, 2022 at 8:23
  • 2
    $\begingroup$ @vidyarthi could you edit your question to make it more clear? for the moment "how do we describe all those distinct combinations which give rise to all the elements of $S_n$" is too general, and the thread of comments is not the right place to amend a question. $\endgroup$
    – YCor
    Commented May 27, 2022 at 8:31
  • 2
    $\begingroup$ After doing a few computer experiments in $S_6$, I am doubtful whether there is a concise description of a set of shortest words for the group elements. For a example, a shortest word for $(2,6,3,4,5)$ is $bab^{-1}ababab^{-1}a$, and a shortest word for $(2,6,4,3)$ is $b^2ab^{-2}ab^{-1}$. The finite state automaton that accepts the set of shortlex least words has $162$ states. $\endgroup$
    – Derek Holt
    Commented May 27, 2022 at 8:47
  • 2
    $\begingroup$ If you were prepared to change generating set to the $n-1$ elements $(1,2),(2,3),(3,4),\ldots,(n-1,n)$ each of order two there is a very good geometric theory of word length with respect to these generators. The thing to search for is finite Coxeter groups: the symmetric group $S_n$ with these generators is the Coxeter group of type $A_{n-1}$. For example, there is a unique element of $S_n$ that has maximal length with respect to these generators (although there are many words of that length that represent it). The geometry behind this is that the antipodal point on a sphere is unique. $\endgroup$
    – IJL
    Commented May 27, 2022 at 13:20

1 Answer 1

Reset to default
3
$\begingroup$

The diameter of the Cayley graph of $S_n$ with respect to $a=(1,2)$, $b=(1,2,\dots,n)$, and $c=b^{-1}=(n,n-1,n-2,\dots,1)$ is not known.

See the sequence A186783 on OEIS.

This paper may be of interest (it gives an algorithm for producing the "flip" permutation $(1,n)(2,n-1),(3,n-2),\dots$ in $O(n^2)$ steps.

Improve this answer
$\endgroup$

You must log in to answer this question.

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