Factorial-inequalities - MathOverflow

Factorial-inequalities

2011-12-24T17:51:45Z

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

Answer by Igor Rivin for Factorial-inequalities

2011-12-24T19:41:32Z

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

Answer by Gerhard Paseman for Factorial-inequalities

2011-12-24T19:55:11Z

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

Answer by Gerhard Paseman for Factorial-inequalities

2011-12-26T20:04:59Z

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