0
$\begingroup$

Some notes before the question:

1- there are many questions in MSE asking about elements generating $S_n$ but they all involve more than one transposition to generate $S_n$ for example "$S_n$ is generated by elements of the form $(1k)$ [more than one element because $k$ varies] or "... generated by $ \{(1,2), (1,2,3,...,n) \} $".

2- By cyclic or generated by, considering the same meaning of generating a group by a single element and so called the cyclic group.

My question is : for which $i$ and $i$, $(i \ \ j)$ generated $S_n$, i.e. $S_n = \langle (i \ \ j) \rangle$ i.e. $S_n = {\{ (i \ \ j)^a | \text{fixed} \ i, j \ \text{and varying}\ a \ \in {\{1, \dots n}\} \ }\}$? And if the answer is no single transposition can generated $S_n$, is it possible with two transpositions and if so for what numbers i, j, k, m $S_n = \langle (i \ \ j), (k \ \ m) \rangle$ ?

I would appreciate any simple clear detailed explanation.

$\endgroup$
  • 2
    $\begingroup$ Any cyclic group is abelian, and very few $S_n$ are abelian. $\endgroup$ – Santiago Canez Mar 30 '16 at 16:33
  • $\begingroup$ A cyclic group is necessarily abelian, but $S_n$ is not except for $n<3$. $\endgroup$ – Captain Lama Mar 30 '16 at 16:33
  • 1
    $\begingroup$ Yes, two is possible : take $(12)$ and $(12\cdots n)$. $\endgroup$ – Captain Lama Mar 30 '16 at 16:35
  • 1
    $\begingroup$ I read "two generators", I forgot you wanted them to be transpositions. If you want that, then you need $n-1$ of them, for instance $(1i)$ for $1<i\leqslant n$. $\endgroup$ – Captain Lama Mar 30 '16 at 16:38
  • 2
    $\begingroup$ Clearly $2$ is not possible because all numbers need to appear in your transpositions if you want them to generate the whole group. $\endgroup$ – Captain Lama Mar 30 '16 at 16:38
1
$\begingroup$

As it was said in the comments (by Captain Lama and Santiago Canez), this is not possible if $n ≥ 3$ because the transpositions $(1 \; 2)$ and $(2 \; 3)$ do not commute. So $S_n$ is not abelian, and therefore it is not cyclic (i.e. it can't be generated by $1$ element). You only have $S_2 = \langle (1 \; 2) \rangle$.


For $n ≥ 5$, $S_n$ is not generated by $2$ transpositions: let $(a \; b)$ and $(c \; d)$ two of them, and let $x \in \{1,...,n\}$ with $x \not \in \{a,b,c,d\}$. Then $(a \; x)$ is not in the subgroup $G$ generated by $(a \; b)$ and $(c \; d)$, because every element of $G$ fixes $x$.

However, for $n=3$, you have $S_3 = \langle (1 \; 2), (1 \; 3) \rangle$.

$\endgroup$
  • $\begingroup$ (12⋯n) is not a transposition. $\endgroup$ – Liebe Mar 30 '16 at 16:36
  • $\begingroup$ Is writing $S_n = {\{ (i \ \ j)^{a_1} (k \ \ m)^{a_2} (i \ \ j)^{a_3} \dots | \text{fixed} \ i, j, k, m \ \text{and varying}\ a_i \ \in {\{1, \dots n}\} \ }\}$ possible? It has nothing to do with abelian since powers of same transpositions don't sum-up. $\endgroup$ – Liebe Mar 30 '16 at 16:39
  • $\begingroup$ @Liebe : you are right for the description of the subgroup generated by $(i \; j)$ and $(k \; m)$ (you can have $0≤a_i≤1$ here). The first part of my answer is about one generator, and this has something to do with abelian. But for two generators, this is indeed different. $\endgroup$ – Watson Mar 30 '16 at 16:44
  • $\begingroup$ Sorry one q. What is the least number of transpositions to generate $S_n$? It seems that in your example for n=5 if we bring a third transposition (i.e. incl. 1) so they may generate $S_n$ so the least number is 3? Thank you $\endgroup$ – Liebe Mar 30 '16 at 16:49
  • 1
    $\begingroup$ @Liebe The argument shows that no fewer that $n-1$ transpositions can generate $S_n$ and indeed, it is generated by either the $n-1$ transpositions containing some fixed element, or the $n-1$ transpositions exchanging some $i$ and $i+1$. $\endgroup$ – Tobias Kildetoft Mar 30 '16 at 17:19

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.