Inequality involving factorials

Question

I'm doing my PhD about some topological constructions for Right-angled Artin groups. While trying to prove a lemma about word lengths in this kind of groups, I arrived to this inequality involving factorials: $$ a!+(n-a-1)!+b!+(n-b-1)!\geq (a-c)!+(n-a+c-1)!+(b-c)!+(n-b+c-1)! $$ where $A,B\subset L$, $n=|L|$ is the cardinal of the set and $a=|A|,b=|B|, c=|A\cap B|\neq 0$. I've been a couple of days thinking about it, but the only thing that occurs to me is trying to prove $$ a!-(a-c)!\geq (n-a+c-1)!-(n-a-1)! $$ but I don't really know how to simplify any expression in there. It's been a while since the last time I worked with factorials and combinatorics. Do you think the inequality will hold? Do you have any idea about how could I start working on it? Thank you very much!

Answer 1

The inequality is equivalent to the inequality $a+b-c \ge n-1$, or in other words $|A \cup B| \ge n-1$. I've checked this experimentally for all $n \le 10$, and for $n>10$, we can prove that it continues to hold.

The intuition is that in a sum of factorials, the largest factorial will dominate, unless all the factorials are small. So we deal with the small cases by asking Mathematica to do it, and we deal with the other cases by comparing the largest term on each side.

Case 1. Suppose $a+b-c > n-1$; in particular, $a+b \ge n$. Let's suppose without loss of generality that $a \ge b$; then $a \ge n/2$. We have:

• $a > a-c$, since $c>0$;
• $a > b-c$, since $a\ge b$ and $c>0$;
• $a > n-b+c-1$, by the case;
• $a > n-a+c-1$, by the case and since $a \ge b$.

Then just the $a!$ term on the left is greater than each term on the right individually, so they are each at most $(a-1)!$. Because $a \ge n/2 > 5$, we know that $a! > 4(a-1)!$, and just the $a!$ on the left exceeds all the terms on the right.

Case 2. Suppose $a + b - c = n-1$. Then the left and right terms can be paired up into four equal pairs:

• $a! = (n-b+c-1)!$
• $(n-a-1)! = (b-c)!$
• $b! = (n-a+c-1)!$
• $(n-b-1)! = (a-c)!$

In this case, both sides of the inequality are equal.

Case 3. Suppose $a+b-c < n-1$. Again, without loss of generality suppose that $a \ge b$. Then we expect $(n-b+c-1)!$ on the right to dominate all four terms on the left. We have:

• $n-b+c-1 > n-b-1$, since $c>0$;
• $n-b+c-1 > n-a-1$, since $c>0$ and $a \ge b$;
• $n-b+c-1 > a$, by the case;
• $n-b+c-1 > b$, by the case and since $a \ge b$.

But why should $n-b+c-1$ be large? Well, $b-c = |B-A|$, so $n-b+c = n-|B-A|$. Because $a \ge b$, we have $|A-B| \ge |B-A|$, and these are disjoint, so in particular, $|B-A| \le n/2$. Therefore $n-b+c \ge n/2$, so $n-b+c-1 \ge n/2 - 1 > 4$. This is enough to see that four factorials less than $(n-b+c-1)!$ add up to less than $(n-b+c-1)!$, so the right-hand side wins.