4
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ What if $k=1$ and $c_1=n$? $\endgroup$ Dec 24, 2011 at 18:13
  • $\begingroup$ @Andreas: Thanks. I forgot to stay that $c_1<4$. $\endgroup$ Dec 24, 2011 at 18:19
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 24, 2011 at 18:40
  • $\begingroup$ 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. $\endgroup$ Dec 24, 2011 at 18:57
  • 1
    $\begingroup$ @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$. $\endgroup$ Dec 24, 2011 at 18:59

3 Answers 3

1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ @Gerhard: your tex is scrozzled... $\endgroup$
    – Igor Rivin
    Dec 26, 2011 at 21:03
  • $\begingroup$ 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 $\endgroup$ Dec 26, 2011 at 21:32
  • $\begingroup$ 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 $\endgroup$ Dec 26, 2011 at 22:04
2
$\begingroup$

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

$\endgroup$
3
  • 5
    $\begingroup$ Whoever down voted this, why? $\endgroup$
    – Igor Rivin
    Dec 25, 2011 at 15:54
  • $\begingroup$ But 4+3+2+2+1+1+1=14<15 so for Alireza's problem this, without bookkeeping, is sufficient, no? $\endgroup$
    – Will Sawin
    Dec 25, 2011 at 20:34
  • $\begingroup$ @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. $\endgroup$
    – Igor Rivin
    Dec 25, 2011 at 21:00
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Dec 24, 2011 at 20:01
  • $\begingroup$ @Gerhard. Thanks. I have now put the motivation with the question in the same place. $\endgroup$ Dec 25, 2011 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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