Largest permutation group without 2-cycles or 3-cycles - MathOverflow

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.

Answer by Dima Pasechnik for Largest permutation group without 2-cycles or 3-cycles

2013-01-10T03:21:59Z

For small $n$ your construction is not optimal (e.g. for $n=6$ there is a group of size 120, isomorphic to $S_5$; $M_{12}$) is an example for $n=12$, the biggest exceptional $n$, it seems).

But for sufficiently large $n$, your construction is almost 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:

prove that this is the best possible with intransitive groups
same for imprimitive groups
for primitive groups, invoke O'Nan-Scott theorem (eventually, the classification of finite simple groups).

Perhaps there is a better way to deal with the last step, I don't know.

Answer by Derek Holt for Largest permutation group without 2-cycles or 3-cycles

2013-01-10T09:43:29Z

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 $\{\{1,2\}, \{3,4\},\ldots,\{2m-1,2m\}\}$ of ${1,2,\ldots,n}$. So $|W| = 2^mm!$.

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 $\{2i-1,2i\}$ 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.

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

Answer by Nick Gill for Largest permutation group without 2-cycles or 3-cycles

2013-01-10T10:15:57Z

This is really an comment to @Dima's answer, but it's a bit long...

There is a classical result of Jordan in permutation group theory that says the following:

If a primitive group $G$ [on a set of order $n$] contains a $p$-cycle, where $p < n - 3$ is prime, then $G$ is the alternating or symmetric group of degree $n$.

(See Wielandt's Finite permutation groups for a proof.)

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:

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

The quote comes from Permutation Groups and Normal Subgroups 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...

Answer by W Edwin Clark for Largest permutation group without 2-cycles or 3-cycles

2013-01-14T20:24:54Z

Two sequences motivated by this question made with a brute force GAP program:

https://oeis.org/A208232 and https://oeis.org/A208235

Someone may like to extend these sequences.