User rishig - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T22:17:10Z http://mathoverflow.net/feeds/user/30530 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 Comment by rishig rishig 2013-01-11T05:45:48Z 2013-01-11T05:45:48Z Thanks everyone for your help and insight! The answers are exactly what I was looking for. I would &quot;accept&quot; several answers if I could, but it looks like mathoverflow only allows one accepted answer per question.