most recent 30 from http://mathoverflow.net 2013-05-20T05:29:07Z http://mathoverflow.net/feeds/question/59091 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/59091/looking-for-deterministic-criteria-to-generate-the-symmetric-group Hugo Chapdelaine 2011-03-21T18:12:01Z 2011-03-22T23:26:31Z

<p>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\}$.</p> <p>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.</p> <p>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$.</p> <p>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?</p> <p>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$?</p> <p>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.</p> <p>Q2: Do we have a good understanding of the tree of subgroups of $S_N$, especially the maximal subgroups? </p> <p>Q3: Is there some kind of probabilistic result that could be used in my context?</p>

http://mathoverflow.net/questions/59091/looking-for-deterministic-criteria-to-generate-the-symmetric-group/59100#59100 Hugo Chapdelaine 2011-03-21T20:02:26Z 2011-03-22T20:05:33Z

<p>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.</p>