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

• 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
• What are $a$ and $b$? They don't seem to be introduced in the question or in your answer. – joriki Mar 28 at 6:29
• @joriki Hmm, that was so long ago ... it seems my $(a,b)$ is the asker's $(i,j)$. It is strange no-one noticed it at the time, and I generally make an effort to stick to the OP's notation when possible. Perhaps I took the $(a,b)$ notation from the asker's comment (and linked question) – Ewan Delanoy Mar 28 at 8:00
• @joriki By the way, this question looks like a duplicate of math.stackexchange.com/questions/64848/… – Ewan Delanoy Mar 28 at 8:02