Largest permutation group without 2-cycles or 3-cycles

2013-01-10T01:56:58Z

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)!$).

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)!$.

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

$\{(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$

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<1$.

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.

Comment by rishig

2013-01-11T05:45:48Z

Thanks everyone for your help and insight! The answers are exactly what I was looking for. I would "accept" several answers if I could, but it looks like mathoverflow only allows one accepted answer per question.

User rishig - MathOverflow

Largest permutation group without 2-cycles or 3-cycles

Comment by rishig