Largest permutation group without 2-cycles or 3-cycles - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T05:13:50Z http://mathoverflow.net/feeds/question/118494 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/118494/largest-permutation-group-without-2-cycles-or-3-cycles Largest permutation group without 2-cycles or 3-cycles rishig 2013-01-10T01:56:58Z 2013-01-28T03:11:23Z <p>The largest permutation group without 2-cycles is $A_n$, which has size $n!/2$. I think the largest permutation group without 2-cycles or 3-cycles is much smaller, but I can't figure out if it should be polynomially smaller (eg. of size $n!/n^3$), or more dramatically smaller (eg. of size $(.5n)!$). </p> <p>The largest group I could come up with is $\{\phi(x_1,\dots,x_{n/2}) \circ \phi(x_{n/2+1},\dots,x_n) | \phi \in S_{n/2}\}$, which has size $(.5n)!$.</p> <hr> <p>EDIT: Posting this here since the answers below pointed me in the right direction, but ended up conjecturing something that was not quite correct. The group </p> <p>$\{(g_1, g_2, \dots, g_{d-1}\!,\ g_1g_2\cdots g_{d-1}\!)\ |\ g_i \in S_{n/d}\} \le S_{n/d}^d \le S_n$</p> <p>has no 2-cycles or 3-cycles, and has $(n/d)!^{d-1}$ elements. When $d = \log n$, this is $n!/n^{\Theta(n\log\log(n)/\log(n))}$, which is smaller than $n!/poly(n)$ but larger than $(cn)!$ for any $c&lt;1$. </p> <p>You can do a little bit better by using a wreath product instead of a direct product, and by tweaking $d$, but I think this is more or less optimal.</p> http://mathoverflow.net/questions/118494/largest-permutation-group-without-2-cycles-or-3-cycles/118498#118498 Answer by Dima Pasechnik for Largest permutation group without 2-cycles or 3-cycles Dima Pasechnik 2013-01-10T03:21:59Z 2013-01-10T03:31:09Z <p>For small $n$ your construction is not optimal (e.g. for $n=6$ there is a group of size 120, isomorphic to $S_5$; <a href="http://en.wikipedia.org/wiki/Mathieu_group" rel="nofollow">$M_{12}$</a>) is an example for $n=12$, the biggest exceptional $n$, it seems). </p> <p>But for sufficiently large $n$, your construction is <i>almost</i> optimal; you can still add an extra 2 to the order of your group. Namely, add the permutation $(1,n/2+1)(2,n/2+2)\dots (n/2,n)$. A way to prove that this becomes optimal (for sufficiently large $n$) might go as follows:</p> <ul> <li>prove that this is the best possible with intransitive groups</li> <li>same for imprimitive groups</li> <li>for primitive groups, invoke <a href="http://www.maths.qmul.ac.uk/~raw/talks_files/ONStalk.pdf" rel="nofollow">O'Nan-Scott theorem</a> (eventually, the classification of finite simple groups).</li> </ul> <p>Perhaps there is a better way to deal with the last step, I don't know.</p> http://mathoverflow.net/questions/118494/largest-permutation-group-without-2-cycles-or-3-cycles/118513#118513 Answer by Derek Holt for Largest permutation group without 2-cycles or 3-cycles Derek Holt 2013-01-10T09:43:29Z 2013-01-10T09:43:29Z <p>I can do a bit better! For even $n=2m$ there is a subgroup of order $2^{m-1}m!$ with no 2-cycles or 3-cycles. Let $W$ be the wreath product of a cyclic group of order 2 with $S_m$. In other words, $W$ is the subgroup of $S_n$ that preserves the partition <code>$\{\{1,2\}, \{3,4\},\ldots,\{2m-1,2m\}\}$</code> of ${1,2,\ldots,n}$. So $|W| = 2^mm!$.</p> <p>Then $W$ has no 3-cycles, but it does have the 2-cycles $(1,2),(3,4),$ etc. Now $W$ is a semidirect product $B \rtimes S_m$, where $B$ is the base group of the wreath product, which is the subgroup of order $2^m$ that fixes each of the pairs <code>$\{2i-1,2i\}$</code> in the partition. The subgroup $C$ of $B$ consisting of the even permutations in $B$ has order $2^{m-1}$ and has no 2-cycles, and it is normal in $W$, so $G := C \rtimes S_m$ has no 3-cycles and no 2-cycles.</p> <p>I would guess that this is the best you can do for large $n$, and I am sure that this could be proved using the methods suggested by Dima Pasechnik. The intransitive and imprimitive maximal subgroups of $S_n$ are respectively direct and wreath products of symmetric groups, so their structure is well understood. The primitive maximal subgroups are comparatively small. There is an old result (of Praeger and Saxl I think) that says they have order at most $4^n$, and many more recent more accurate results, but $4^n$ is already asymptotically smaller than $|G|$.</p> http://mathoverflow.net/questions/118494/largest-permutation-group-without-2-cycles-or-3-cycles/118517#118517 Answer by Nick Gill for Largest permutation group without 2-cycles or 3-cycles Nick Gill 2013-01-10T10:15:57Z 2013-01-10T10:15:57Z <p>This is really an comment to @Dima's answer, but it's a bit long...</p> <p>There is a classical result of Jordan in permutation group theory that says the following:</p> <blockquote> <p>If a primitive group $G$ [on a set of order $n$] contains a $p$-cycle, where $p &lt; n - 3$ is prime, then $G$ is the alternating or symmetric group of degree $n$.</p> </blockquote> <p>(See Wielandt's <em>Finite permutation groups</em> for a proof.)</p> <p>So any primitive group will satisfy the requirements of the OP. There are LOTS of papers written about the maximal orders of primitive groups, so you should investigate these. The starting point is classical work of W.A. Manning, but once the Classification of Finite Simple Groups was completed, much stronger results were possible. Here is a relevant quote:</p> <blockquote> <p>"It is now known that the largest [primitive] groups [on a set of order $n$ occur for $n$ of the form $c(c − 1)/2$ and are $S_c$ and $A_c$ acting on the unordered pairs from a set of size $c$."</p> </blockquote> <p>The quote comes from <em>Permutation Groups and Normal Subgroups</em> by Cheryl Praeger. So you can work out from this what the upper bound for the order of a primitive group containing neither 2-cycles nor 3-cycles. Which leaves the intransitive and imprimitive ones...</p> http://mathoverflow.net/questions/118494/largest-permutation-group-without-2-cycles-or-3-cycles/118919#118919 Answer by W Edwin Clark for Largest permutation group without 2-cycles or 3-cycles W Edwin Clark 2013-01-14T20:24:54Z 2013-01-14T20:24:54Z <p>Two sequences motivated by this question made with a brute force GAP program:</p> <p><a href="https://oeis.org/A208232" rel="nofollow">https://oeis.org/A208232</a> and <a href="https://oeis.org/A208235" rel="nofollow">https://oeis.org/A208235</a></p> <p>Someone may like to extend these sequences.</p>