# 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$ where $N$ is even and $n=\frac{N}{2}$. We let $H$ act on $T$ in the following way: We divide $T$ in $n$ disjoint blocks of size $2$. We let $S_n$ permute the $n$ blocks without swapping the pair in each block, and we let $\mathbf{F}_2^n$ permute (resp. acts like the identity) the two elements in the i-th block if the i-th coordinate of an element $\sigma\in \mathbf{F}_2^n$ is $\overline{1}$ (resp. $\overline{0}$). It thus follows that $H$ acts transitively (but imprimitively) on $T$.

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.

-
@Marty comment below is true. There is a gap in the proof above. Implicitely implied in the proof above was the belief that the semi-direct product $S_{2}^{n}\rtimes S_n$ had no cycle of length $>n$. This is (in retrospect) clearly false. – Hugo Chapdelaine Jul 10 '15 at 22:08

Embarrassingly, the posting below contains another incomplete proof, as was pointed out by Hugo Chapdelaine. I am working on a new (third) version, but after two wrong proofs, I want to hold off for a while on posting it until it is written up carefully and checked. What I am trying to prove is this:

THEOREM: Let $H$ be a transitive subgroup of $S_N$, and suppose $M \triangleleft H$ and $H/M \cong S_n$, where $N/2 \le n < N$ and $5 < n$. Then $n = N/2$ and either $M = 1$ or all orbits of $M$ have size $2$.

Unfortunately, the proof in the original version of this post had a gap that I do not see how to repair. The following weaker result seems to be true, however.

THEOREM. Let $H \subseteq S_N$ and assume that $M \triangleleft H$ and $H/M \cong S_n$, where $n \ge N/2$. Then either $M$ is an elementary abelian $2$-group and $n = N/2$ and $H$ is transitive, or else there exists $K \subseteq H$ such that $H = MK$ and $M \cap K = 1$. In particular, $K \cong S_n$.

Proof. Induct on $N$. Let $S$ be a point stabilizer in $S_N$. Write $u = |H:(H \cap S)|$, so $u \le N$ with equality only if $H$ is transitive. Write $v = |M:(M \cap S)|$, so $v = |M(H \cap S):(H \cap S)|$, and this divides $u$. Also, $u/v = |H:M(H \cap S)|$ is the index of a subgroup of $H/M \cong S_n$, so this index is either $1$ or at least $n$.

Suppose $u/v = 1$. Then $M(H \cap S) = H$, and so $(H \cap S)/(M \cap S) \cong H/M \cong S_n$. Also, $S \cong S_{N-1}$ and $(N-1)/2 < n$, so the inductive hypothesis applies with $H \cap S$ in place of $H$ and $M \cap S$ in place of $M$. Since $n$ is not $(N-1)/2$, there exists $K \subseteq H \cap S$ such that $K \cap (M \cap S) = 1$ and $H \cap S = (M \cap S)K$. Then $K \cap M = 1$ and $H = M(H \cap S) = M(M \cap S)K = MK$ as required.

We can assume now that for every choice of point stabilizer $S$ we have $u/v \ne 1$. Then $N/v \ge u/v \ge n \ge N/2$, and thus $v \le 2$. Thus all orbits of $M$ have size $1$ or $2$, so $M$ is an elementary abelian 2-group. If we always have $v = 1$, then $M = 1$ and we can take $K = H$. We can thus assume that $v = 2$ for some choice of $S$. Then $N/2 \ge u/2 = u/v \ge n \ge N/2$ and we have equality. Thus $n = N/2$ and $u = N$, and the latter equality shows that $H$ is transitive. QED

In the case where $H = MK$ and $M \cap K = 1$, we have $K \cong S_n$, so we can ask what copies $K$ of $S_n$ are contained in $S_N$ if $n \ge N/2$. If $n > 5$, It seems that the only possibility is that $K$ is the stabilizer of $N - n$ points. This can be proved using the fact that $S_n$ has no proper subgroup of index less than or equal to $2n$ except for point stabilizers. (At least I think that is a fact.)

-
Thanks a lot Marty for pointing out the mistake in my "original proof". – Hugo Chapdelaine Jul 10 '15 at 22:19
Dear Marty, I just read the proof of your theorem which looks good. I'm confused though about one point. The group $S_n$ admits a subgroup of index $2$ namely $A_n$. It is true though that if $e:=[S_n:H]>2$ then $e≥n$. Moreover, it is true that $A_n$ has the property which you used in your proof namely that if $e:=[A_n:H]>1$ then $e≥n$. – Hugo Chapdelaine Jul 11 '15 at 14:17
@Hugo You are right, of course. I need to think some more about how A_n fits into my proof. – Marty Isaacs Jul 12 '15 at 0:01