Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
You can get a rough upper bound with number theory by removing the factors of 2 and 3 from n factorial (as any desired subgroup has order dividing that factor). I am guessing the result will be dramtically smaller. Already for n=7 the answer is at most 35, and in fact is actually 7. Gerhard "Is Calculating From The Hip" Paseman, 2013.01.09 –  Gerhard Paseman Jan 10 '13 at 3:04
    
Upon reflection, I see that I am looking at subgroups without elements of orders 2 or 3, which may be different from what the poster desires. Gerhard "Is Reading From Hip Too" Paseman, 2013.01.09 –  Gerhard Paseman Jan 10 '13 at 3:08
    
Gerhard, no, it's about subgroups, it's about cyclic structures of the elements of orders 2 and 3. –  Dima Pasechnik Jan 10 '13 at 8:27
    
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. –  rishig Jan 11 '13 at 5:45
add comment

4 Answers

up vote 14 down vote accepted

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

share|improve this answer
    
oops, you're right. I somehow didn't think straight enough when I realized that the example in the question can be improved. :-) –  Dima Pasechnik Jan 10 '13 at 12:02
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
But the conclusion will be that, at least for large enough $n$, primitive groups will not be the largest groups with the required property. –  Derek Holt Jan 10 '13 at 11:48
    
Derek, of course you are right, as your citation of the Praeger-Saxl result makes clear. –  Nick Gill Jan 10 '13 at 13:15
add comment

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.

share|improve this answer
1  
It is known that the only primitive group on $n$ points containing a 2-cycle is $S_n$ and any primitive group containing a 3-cycle contains $A_n$. These are classical regults going back to Jordan. Thus any primitive group other than $A_n$ or $S_n$ has no 2-cycles or 3-cycles. There are very good upper bounds on the order of primitive group. The best is by Maroti which says that for such primitive groups one of the following holds: - G is a Mathieu group $M_n$ for $n=11,12,23,24$ -G is a subgroup of $S_m wr S_k$ with $n=m^k$, $m\geq 5$ and $k\geq 2$ -|G|\leq n^{1+\lfloor log_2(n)\rfloor}$ –  Michael Giudici Jan 10 '13 at 9:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.