# non transitive subgroups of the symmetric group

How to show that any non transitive subgroup of the symmetric group $S_n$ is up to conjugation contained in a Young subgroup $S_k\times S_{n-k}$?

Take $\mathbb Z_3$ the subgroup of $S_3$ generated by $(123)$. This is a non transitive subgroup of $S_3$, but it is contained in no $S_k\times S_{3-k}$ unless we take $k=0$ and in then what is $S_0$ ? And even if we identify $S_0\times S_{3-0}$ with $S_3$, then actually the statement is trivial as $S_3$ contains all its subgroups!!

• The subgroup generated by $(123)$ is transitive. For a non-transitive group, think about the orbits of $\{ 1, 2, ... n \}$ under the action of the group. – Qiaochu Yuan Jul 9 '11 at 14:35
• @ Qiaochu Yuan: but $\mathbb Z_3$ is non transitive in $S_4$ as no permutation can take 1 to 4. so how can we write $\mathbb Z_3$ in this case? is it to say that $\mathbb Z_3$ is contained in the young subgroup $S_3\times S_1\subset S_4$? – palio Jul 9 '11 at 15:22
• Well... yes. That's it. – Qiaochu Yuan Jul 9 '11 at 15:30
• @Geoff: your accounts have been merged. – Qiaochu Yuan Jul 9 '11 at 15:32

Suppose that $H\lt S_n$ is not transitive (that is, it does not act transitively on $\{1,2,\ldots,n\}$ under the usual action). The action of $H$ partitions $\{1,2,\ldots,n\}$ into orbits, and the action being nontransitive is exactly equivalent to the statement that this partition contains more than one equivalence class. In particular, there exist subsets $S$ and $T$ of $\{1,2,\ldots,n\}$ such that:
• $S\cup T=\{1,2,\ldots,n\}$;
• $S\cap T = \emptyset$;
• $S\neq\emptyset$ and $T\neq\emptyset$
• If $\mathscr{O}\subseteq \{1,2,\ldots,n\}$ is an orbit of $H$, then either $\mathscr{O}\subseteq S$ or $\mathscr{O}\subseteq T$.
For example, you can let $\mathscr{O}_1,\ldots,\mathscr{O}_k$ be the distinct orbits of $H$, and let $S=\mathscr{O}_1$ and $T=\mathscr{O}_2\cup\cdots\cup\mathscr{O}_k$. Since the action of $H$ is non transitive, $k\gt 1$, so $S$ and $T$ satisfy the four listed conditions.
In particular, $H$ acts on $S$ (by restriction) and $H$ acts on $T$ (by restriction); if we let $|S|=k$ and $|T|=n-k$, then we can find a $\tau\in S_n$ such that $S^{\tau}=\{1,2,\ldots,k\}$ and $T^{\tau} = \{k+1,\ldots,n\}$ (where $X^{\tau}=\left\{\tau(x)\mid x\in X\right\}$). Thus, $\tau H \tau^{-1}$ acts on $\{1,2,\ldots,k\}$ and separately on $\{k+1,\ldots,n\}$; these actions (via restriction) induce the desired embedding into $S_k\times S_{n-k}$.