Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.