Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
And such an H never contains the alternating group of degree N. –  Jack Schmidt Mar 22 '11 at 2:42
1  
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

2 Answers 2

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.

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

share|improve this answer
    
Thanks a lot Marty for pointing out the mistake in my "original proof". –  Hugo Chapdelaine Jul 10 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 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 at 0:01

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.