Necessary and Sufficient conditions for $(i \, j)$ and $(1 \, 2 \, \dotsc \, n)$ 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.

Solution 1:

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$.