# Necessary and Sufficient conditions to generate $S_n$

I have a homework question that asks

"Find necessary and sufficient conditions on $1 \leq i < j \leq n$ so that $(i \, j)$ and $(1 \, 2 \, \dotsc \, n)$ generate $S_n$."

Here is what I have done so far. Call $c = (1 \, 2 \, \dotsc \, n)$. I made the observation that $$\overbrace{c c \dotsb c}^{n - j + 1} (i \, j) \overbrace{c^{-1} c^{-1} \dotsb c^{-1}}^{n - j + 1} = (1 + i - j + n \, 1).$$ Thus, $\langle (i \, j), c \rangle = \langle (1 \, i - j + n + 1), c \rangle$, so it suffices to look at $\langle (1 \, k), c \rangle$ for positive integers $2 \leq k \leq n$. I've checked that, for the value $k=2$, $\langle (1 \, 2), c \rangle = S_n$. This immediately implies $\langle (1 \, n), c \rangle = S_n$. I suspect that no other values of $k$ will work, but am not sure how to prove it.

-
Observe $(1,2,\dots,n)^p(a,b)(n,n-1,\dots,1)^p = (p+a,p+b)$ where the sum is mod $n$. Try $n=5$ and $n=8$ for some other values of $k$ and you will find some additional values that work; the pattern isn't too tricky. But I'm not sure how to say why no others work. – Eric Stucky Oct 5 '13 at 0:48
@EricStucky According to math.stackexchange.com/questions/64848/… , $(a, b)$ and $(1, 2, \dotsc, n)$ generate $S_n$ if and only if $\text{gcd}(|a-b|,n) = 1$. I'm working on trying to prove this now. Ideas? – tylerc0816 Oct 5 '13 at 0:58

Suppose that $gcd(|b-a|,n)=g>1$. Say that a permutation $\sigma$ of $[n]=\lbrace 1,2,\ldots ,n\rbrace$ is respectful modulo $g$ if

$$i \equiv j ({\sf mod}\ g) \Leftrightarrow \sigma(i) \equiv \sigma(j) ({\sf mod}\ g)$$ It is easy to see that the set of permutations that are respectful modulo $g$ is a strict subgroup of $S_n$, which will obviously contain your two elements.

Conversely, suppose $gcd(|b-a|,n)=1$. It will be convenient to view the base set as $\frac{\mathbb Z}{n{\mathbb Z}}$ rather than $[n]$. Denote by $H$ the subgroup generated by your two elements and let $$T=\bigg\lbrace t\in \frac{\mathbb Z}{n{\mathbb Z}} \bigg| (1,1+t) \in H \bigg\rbrace$$

As explained in the OP, we have $(i,i+t)=c^i(1,1+t)c^{-i}$ so when $t\in H$ one deduces $(i,i+t)\in H$ for any $i$. So $T$ is in fact equal to $$T'=\bigg\lbrace t\in \frac{\mathbb Z}{n{\mathbb Z}} \bigg| (i,i+t) \in H \ \text{for every } \ i \in\frac{\mathbb Z}{n{\mathbb Z}} \bigg\rbrace$$

But it is clear that $T'$ is a subgroup of $\frac{\mathbb Z}{n{\mathbb Z}}$ by construction. Since it contains an element that is coprime with $n$, it is the whole of $\frac{\mathbb Z}{n{\mathbb Z}}$. Then the generated subgroup contains all transpositions and is therefore equal to the whole of $S_n$.

-
It is not clear to me right away that the permutations that are respectful mod $g$ do not generate all of $S_n$. – tylerc0816 Oct 5 '13 at 12:48
@tylerc0816 Since they form a subgroup, it suffices to show that not every permutation in $S_n$ is respectful. Any permutation $\sigma$ with $\sigma(1)=1$, $\sigma(g+1)=g$ will do. – Ewan Delanoy Oct 5 '13 at 12:54