Question on permutation

Question

I asked this question : Composition of permutation to generate all permutations earlier but I didn't phrase it well, here is my new question.

My question is a little bit different I'm looking for a set of permutation $\sigma_1$, ... $\sigma_p$ such that any composition (in this given order) $\sigma_1\circ\sigma_2\circ\cdots\circ\sigma_p\circ\sigma_1\circ\sigma_2\circ\cdots$ will generate all the permutation of a given list.

According to you answer I get that this sequence can be compose only of $\sigma_1=(1,2)$ and $\sigma_2=(1,2,...n)$, but this might not be optimal (because the sequence might be longer.)

Now my question is, what is the minimum sequence of $\sigma_1$ and $\sigma_p$ such that it generates all permutations of a set of $n$ element.

in my example with 1,2,3 above.

if I take $\sigma_1=(1,2)$ and $\sigma_2=(1,3)$

the sequence repeating sequence $\sigma_1\circ\sigma_2$ will generate all permutations :

id gives 1 2 3

$\sigma_1$ gives 2 1 3

$\sigma_1\circ\sigma_2$ gives 3 1 2

$\sigma_1\circ\sigma_2\circ\sigma_1$ gives 1 3 2

$\sigma_1\circ\sigma_2\circ\sigma_1\circ\sigma_2$ gives 2 3 1

$\sigma_1\circ\sigma_2\circ\sigma_1\circ\sigma_2\circ\sigma_1$ gives 3 2 1

---

I can phrase it this way :

Let $S_n$ be the symmetric group on $n$ elements. You are interested in subsets $\{a_0,a_1,\ldots,a_k,b\}$ where $a_0$ is the identity, such that for any $y∈S_n$, you can find $0≤j≤k$ and and natural number $M$ such that $y=bMaj$. And you want to find the minimum $k$. In other words, you are looking for the number of cosets in $S_n$ relative to the subgroup generated by $b$.

Thanks in advance.

Answer 1

If I understand you correctly, you are looking for elements $\sigma_1, \dots, \sigma_m$ of the symmetric group $S_n$ on $n$ elements such that the sequence $\sigma_1$, $\sigma_1\circ\sigma_2$, $\sigma_1\circ\sigma_2\circ\sigma_3, \dots, \sigma_1\circ\dots\circ\sigma_m$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\sigma_2, \dots, \sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1$, $\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\dots\circ\sigma_m\circ\sigma_1\circ\sigma_2, \dots$ lists every element of $S_n$ exactly once.

Defining $\tau := \sigma_1\circ\dots\circ\sigma_m$ this list can be written as $\tau^0\circ\sigma_1, \dots, \tau^0\circ\sigma_1\circ\dots\circ\sigma_{m-1}$, $\tau^1\circ\sigma_1, \dots, \tau^1\circ\sigma_1\circ\dots\circ\sigma_{m-1}$, $\tau^2\circ\sigma_1, \dots, \tau^2\circ\sigma_1\circ\dots\circ\sigma_{m-1}, \dots$.

Written like this, you see that if $\tau$ has the order $k$ (also called period), the sequence repeats itself after $\dots, \tau^{k-1}\circ\sigma_1\circ\dots\circ\sigma_{m-1}, \tau^k$. So if you pick an element $\tau$ whose order is maximal in $S_n$, you will get $m$ minimal, as you always have

$$m = \frac{|S_n|}{k} = \frac{n!}{k}.$$

Now pick elements $\tau_1, \dots, \tau_m$ from the different right cosets of the (cyclic) group $\langle \tau \rangle$ generated by $\tau$, where without loss of generality you may take $\tau_m = \tau$. Then define $\sigma_1 := \tau_1$ and $\sigma_i := \tau_{i-1}^{-1}\circ\tau_i$ for $i = 2,\dots, m$.

It is then not to hard to prove that this sequence $\sigma_1, \dots, \sigma_m$ fulfills your conditions and is as short as possible if the order of $\tau$ is chosen maximal among the elements of $S_n$. As lhf commented on my answer posted on your original question, the maximal possible order of elements of $S_n$ is given by Landau's function, which roughly grows like $\mathrm{e}^{\sqrt{n\log{n}}}$.