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.

  • $\begingroup$ 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. $\endgroup$ – Eric Stucky Oct 5 '13 at 0:48
  • $\begingroup$ @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? $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ It is not clear to me right away that the permutations that are respectful mod $g$ do not generate all of $S_n$. $\endgroup$ – tylerc0816 Oct 5 '13 at 12:48
  • $\begingroup$ @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. $\endgroup$ – Ewan Delanoy Oct 5 '13 at 12:54
  • $\begingroup$ What are $a$ and $b$? They don't seem to be introduced in the question or in your answer. $\endgroup$ – joriki Mar 28 at 6:29
  • $\begingroup$ @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) $\endgroup$ – Ewan Delanoy Mar 28 at 8:00
  • $\begingroup$ @joriki By the way, this question looks like a duplicate of math.stackexchange.com/questions/64848/… $\endgroup$ – Ewan Delanoy Mar 28 at 8:02

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.