# Factorial-inequalities

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

-
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 mathoverflow.net/questions/80998. If you haven't already, don't forget to read mathoverflow.net/howtoask. – 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

## 3 Answers

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

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

-
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

-
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