# Looking for deterministic criteria to generate the symmetric group?

So let $S_N$ be the symmetric group of degree $N$. We think of it as a permutation group via its natural action on the set $T=\{1,2,\ldots,N\}$.

Say that $H\leq S_N$ is a subgroup which acts transitively on $T$. However, I DONT'T WANT to assume necessarily that $H$ is primitive (that is the whole point of my question). Assume furthermore that there is an onto group homomorphism $$f:H\rightarrow S_n$$ where $n=\lfloor{N/2}\rfloor$. In fact, as was pointed out by Schmidt, the existence of this onto group homomorphism implies that $H$ is imprimitive.

In general, one cannot rule out the existence of such an $H$. For example one could have $H=S_n\ltimes\mathbf{F}_2^n$ when $N$ is even and $n=\frac{N}{2}$. Here, $S_n$ acts in the natural way by permutation on the coordinates of $\mathbf{F}_2^n$. Note that by construction, $H$ acts transitively on $T$ and it admits an onto group homomorphism on $S_n$.

Furthermore, suppose that I can produce " a lot of elements " in $H$ which contain a cycle of length $r$ in their cycle presentations (their writing as a product of disjoint cycles of $T$) for $r>n$. Then may I conclude that such an $H$ does not exist?

Q1: Is there some kind of results that would allow me to conclude that $H\supseteq A_N$, so that this would contradict the imprimitivity and therefore rule out the existence of such an $H$?

For example here is one key result which is good to know: if $H$ is assumed to be primitive and contains a cycle of length $\ell$ with $2\leq \ell\leq N-7$ ($\ell$ not necessarily prime) then combining classical results on permutation group theory one may show that $H\supseteq A_N$. However, since in my setting $H$ is imprimitive I cannot apply this result.

Q2: Do we have a good understanding of the tree of subgroups of $S_N$, especially the maximal subgroups?

Q3: Is there some kind of probabilistic result that could be used in my context?

-
Be careful that the subgroup H you are talking about exists. There is no onto group homomorphism from the symmetric group on 2n points to the symmetric group on n points unless n=1 or n=2. In particular, unless n=1 or n=2, H never contains the alternating group of degree N=2n. –  Jack Schmidt Mar 21 '11 at 20:56
Well take $H=S_n\rtimes\mathbf{F}_2^n$ with $N=2n$, this certainly have an onto group homomorphism to $S_n$. –  Hugo Chapdelaine Mar 21 '11 at 22:09
change $\rtimes$ by $\ltimes$ –  Hugo Chapdelaine Mar 21 '11 at 22:10
And such an H never contains the alternating group of degree N. –  Jack Schmidt Mar 22 '11 at 2:42
Looks good. Your solution looks good. The maximal subgroups of symmetric groups are a little bit complicated, but for the most part are well-understood. Let me know if you want an answer about the subgroups of symmetric groups or maximal subgroups of symmetric groups, but I think you've got what you need. –  Jack Schmidt Mar 22 '11 at 23:18

Well I think I have more or less an answer to my question. I have shown that the set of all maximal imprimitive transitive subgroups $H\leq S_N$ is of the form $$S_{N/r}^{r}\rtimes S_r$$ for $r|N$ and where $S_r$ acts by permutation on the coordinates of $S_{N/r}^r$. So since I have an onto group homomorphism $$f:H\rightarrow S_n$$ I must conclude that $H\subseteq S_{2}^{n}\rtimes S_n$ and that $H\supseteq S_n$. Finally, since I can produce an element $\tau\in H$ that has a cycle of length larger than $n$ which appears in its cycle presentation I may conclude that $H$ is not contained in any maximal transitive imprimitive subgroups of $S_N$ and therefore by maximality this implies that $H=S_N$. But this is absurd since it contradicts the imprimitivity of $H$. Therefore such an $H$ does not exist.