MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $n>15$ be an integer. Suppose also $n=\sum_{i=1}^n ic_i$, where $c_i$ are non-negative integers. Assume further that $c_1<4$.

Is the following inequality true? $$\frac{n!}{\prod_{i=1}^{n}i^{c_i}\prod_{i=1}^{n}c_i!}>n(n-1)(n-2)(n-3)$$.

Motivation: The left hand side of the inequality is the size of the conjugacy class of a permutation $\sigma$ with cycle decomposition $n=\sum_{i=1}^n ic_i$, i.e., $\sigma$ is the product of $c_1$ cycles of length $1$, $c_2$ cycles of length $2$,.... We have encountered the question in studying a group $G$ of order $|A_n|=n!/2$ having the same multiset of conjugacy class sizes as the alternating group $A_n$ of degree $n$. We are trying to show that any non-trivial normal subgroup of $G$ is actually the whole $G$, that is, $G$ is simple. Why $n>15$, this is maybe more technical; but let me say that the problem for less than $n\leq 15$ hase been solved. We did not chech if the inequality valid or not for $n\leq 15$.

share|cite|improve this question
What if $k=1$ and $c_1=n$? – Andreas Blass Dec 24 '11 at 18:13
@Andreas: Thanks. I forgot to stay that $c_1<4$. – Alireza Abdollahi Dec 24 '11 at 18:19
Hi Alireza: This might be a very interesting mathematical question — I don't have the expertise to judge. But as written it reads a bit like an olympiad exercise, and so I wouldn't be surprised if it were closed as "too localized". You could improve it a lot by giving some motivation and background, the way you did e.g. in your (as far as I know, unrelated) question If you haven't already, don't forget to read – Theo Johnson-Freyd Dec 24 '11 at 18:40
Is't the number you are looking at the number of permutations in $S_n$ whose (disjoint) cycle structure has $c_i$ cycles of size $i$? Also, since you allow the $c_i$ to be zero, you might as well take $k =n,$ I think. – Geoff Robinson Dec 24 '11 at 18:57
@Theo: Thanks. As far as I know, this is not an olympiad exercise. Please if it is tell me. The left hand side of the inequality is the size of the conjugacy class of a permutation $\sigma$ with cycle decomposition $n=\sum_{i=1}^k i c_i$, i.e., $\sigma$ is the product of $c_1$ cycles of length $1$, $c_2$ cycles of length $2$, .... We have encountered the question in studying a group $G$ of size $n!/2$ having the same conjugacy class sizes as the alternation group $A_n$ of degree $n$. We are trying to show that a certain normal subgroup is actually whole of $G$. – Alireza Abdollahi Dec 24 '11 at 18:59
up vote 1 down vote accepted

Note that for integers $i > 2$ and. $h > 0$, and except for the case $(i,h) = (3,1)$, one has $i^h(h!) < 2^{\lfloor ih/2 \rfloor}(\lfloor ih/2 \rfloor !)$. We can account for the exception and bound from above the denominator of the left hand side of the posted inequality by $(3)2^{(n - c_1)/2}(((n - c_1)/2)!)(c_1!) \leq (3)2^{(n - c_1)/2}(((n + c_1)/2)!)$. This latter term is increasing in $c_1$, and for large $n$ one can have $c_1 \leq n - 10$ and still be less than $(n - 4)!$. One can use this to show the inequality of the post is satisfied for $n > 15$ and $c_1 < 4$; likely the inequality holds for more $n$ and more $c_1$.

BEGIN EDIT 2012.01.05 I decided to add some detail to the post.

Letting $f(i)=i^{c_i}(c_i)!$, we can rearrange the poster's inequality to $$(n - 4)!  \gt \prod_{1 \le i \le n}f(i)$$, and ask for which values of $n, i,$ and $c_i$ the inequality holds.  Given $c_i$, let $g(i) = 2^{\lfloor ic_i/2 \rfloor} (\lfloor ic_i /2 \rfloor)! $ for $i \gt 1$ and $g(1) = f(1)$.  Now, when $i = 3$ and $c_i = 1$ we have $f(3) \lt 2g(3)$, and for other pairs $(i,c_i)$ with $i \gt 2$ and $c_i \gt 0$ one has $f(i) \le g(i)$, so one can have the original inequality follow from $$(n-4)! \gt 2\prod_{1 \le i \le n} g(i) $$.   However, the product of the $g(i)$ is itself bounded from above by $h=2(c_1)! 2^{(n - c_1)/2} {\lceil(n - c_1)/2\rceil}!$.  When $c_1 \le 4$ and $n \ge 15$,  $2h$ is less than $(n-4)!$.  

It is clear that the original inequality implies $c_1 \lt n-4$, and that there is no solution for $n \lt 8$.  For $n=8$, the product of the $f(i)$ has to be less than $24$, so $c_1 \lt 4$. For $n= 8,9,10,11$ it is routine to find restrictions on $c_1$ that will permit solutions of the inequality. From another direction,  if $c_1 = n-5$ then case-by-case examination gives that $f(i) = 1$ for $ i \gt 5$ and $f(2)f(3)f(4)f(5)$ is at most $8$, so that $n > 12$ for the original inequality to hold.  When $c_1 = n - 6$, a similar analysis requires $n > 11$, and for larger values of $n - c_1$ the inequality holds for all the remaining meaningful cases. END EDIT 2012.01.05

Gerhard "Ask Me About System Design" Paseman, 2011.12.26

share|cite|improve this answer
@Gerhard: your tex is scrozzled... – Igor Rivin Dec 26 '11 at 21:03
On my display, the major problem is that I don't know the TeX for/floor(ih/2). Everything else renders properly for me. Gerhard "Also Needs TeX For Ceiling" Paseman, 2011.12.26 – Gerhard Paseman Dec 26 '11 at 21:32
I hope the TeX is no longer scroozled. Also, using the tighter bound allows me to show the inequality for n > 11 and c_1 < n-5. Gerhard "Ask Me About System Design" Paseman, 2011.12.26 – Gerhard Paseman Dec 26 '11 at 22:04

I might be misunderstanding the question, but for $n$ large enough (I am too lazy to compute the exact bounds, but $15$ seems the right ballpark), the interpretation as the number of conjugacy classes tells you that the conjugacy class for which the inequality fails can have no five-cycles (since the number of five-cycles in $n(n-1)(n-2)(n-3)(n-4)/5,$ which is bigger than the right hand side for $n>9$), at most one four- and three- cycle, and at most two two-cycles (and we know it has at most three fixed points).But in fact, it cannot have BOTH a four and a three cycle, or indeed a four- and a two-cycle, so it seems that this is a simple bookkeeping exercise...

share|cite|improve this answer
Whoever down voted this, why? – Igor Rivin Dec 25 '11 at 15:54
But 4+3+2+2+1+1+1=14<15 so for Alireza's problem this, without bookkeeping, is sufficient, no? – Will Sawin Dec 25 '11 at 20:34
@Will: Not exactly. The point is that the number of five-cycles is $n(n-1)(n-2)(n-3)(n-4)/5$, which is greater than his bound for $n>9.$ So we assume that there are no five cycles.$ The number of four-cycles$ is $(n(n-1)(n-2)(n-3)/4,$ which gives us a factor of $4$ to play with, so if $(n-4)(n-5)/2$ is at least $4$ we can have another transposition, otherwise we can have only a four-cycle, etc. The bookkeeping is keeping track of the small constants we divide by ($5, 4, 2$) above. I agree this is not rocket science, which is why I left this to the reader. – Igor Rivin Dec 25 '11 at 21:00

The function $C_l(i) =_{\text{def }} i^{l/i}\Gamma(1 + l/i)$ for large enough $l$ decreases as $i$ increases past 3. This says to me that the values of $i$ to be concerned with in general are at most $4$. For $n > 15$, this should break down into few enough cases to prove that the inequality does hold, or at least holds in all but finitely many cases, even if $c_1$ is allowed to be less than $n/2$.

Gerhard "Not Ready For The Details" Paseman, 2011.12.24

share|cite|improve this answer
Also, I would want to see more motivation in the question proper before I call this an acceptable question for MathOverflow. I encourage the poster to move any such motivation out of the comments and into the question itself. Gerhard "Ask Me About System Design" Paseman, 2011.12.24 – Gerhard Paseman Dec 24 '11 at 20:01
@Gerhard. Thanks. I have now put the motivation with the question in the same place. – Alireza Abdollahi Dec 25 '11 at 3:30

Your Answer


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.