# Rearrangement-style inequality with lots of terms and little evidence

This is another of the problems I designed for contests but wasn't able to solve on my own for years. Maybe AoPS is a better place for it, but let me try it here.

[UPDATE: I have streamlined the exposition after zeb's wonderful proof of my conjectures. Everything stated below as a "conjecture" is true. Note that some comments, as well as fedja's and Suvrit's answers below, refer to an older version of these conjectures, which was false.]

Let $n\in\mathbb N$ be $\geq 2$, and let $a_1$, $a_2$, ..., $a_n$ and $b_1$, $b_2$, ..., $b_n$ be nonnegative reals such that $a_1\geq a_2\geq ...\geq a_n$ and $b_1\geq b_2\geq ...\geq b_n$. Let $A_n$ denote the $n$-th alternating group, and $S_n$ denote the $n$-th symmetric group. We use the symbol $-$ for set-theoretical complement (since the backslash means something else in group theory).

Product-sum conjecture. Then,

$\left(-1\right)^{\binom{n}{2}}\left(\prod\limits_{\pi\in A_n} \left(\sum\limits_{k=1}^n a_kb_{\pi\left(k\right)}\right) - \prod\limits_{\pi\in S_n - A_n} \left(\sum\limits_{k=1}^n a_kb_{\pi\left(k\right)}\right) \right) \leq 0$.

Sum-maximum conjecture. We have

$\left(-1\right)^{\binom{n}{2}}\left(\sum\limits_{\pi\in A_n} \max\left\lbrace a_k + b_{\pi\left(k\right)} \mid k\in\left\lbrace 1,2,...,n\right\rbrace \right\rbrace - \sum\limits_{\pi\in S_n - A_n} \max\left\lbrace a_k + b_{\pi\left(k\right)} \mid k\in\left\lbrace 1,2,...,n\right\rbrace \right\rbrace \right) \leq 0$.

zeb has proven both of these conjectures (I am still interested in an analysis-free proof, but rather convinced that zeb's is the natural one). Here are some easy observations:

• If the Product-sum conjecture holds, then so does the Sum-maximum one, by the standard "tropical geometry" trick (replace $a_k$ by $x^{a_k}$, replace $b_k$ by $x^{b_k}$, and watch the asymptotics of the sides while $x$ goes to $\infty$).

• Both conjectures hold for $n\leq 3$ for very simple reasons.

• By the same argument as in the proof of Cauchy's and Vandermonde's determinants, the difference $\prod\limits_{\pi\in A_n} \left(\sum\limits_{k=1}^n a_kb_{\pi\left(k\right)}\right) - \prod\limits_{\pi\in S_n - A_n} \left(\sum\limits_{k=1}^n a_kb_{\pi\left(k\right)}\right)$ is divisible (as a polynomial) by $\prod\limits_{1\leq i < j\leq n}\left(a_i-a_j\right) \prod\limits_{1\leq i < j\leq n}\left(b_i-b_j\right)$. The question is whether the quotient has the same sign as $\left(-1\right)^{\binom{n}{2}}$. I wouldn't be surprised if it is even a polynomial with all coefficients having that same sign, and maybe even Schur-positive times $\left(-1\right)^{\binom{n}{2}}$, whatever this means for symmetric polynomials in two sets of indeterminates. (For $n\leq 3$, this quotient is $1$.)

• It seems that my "counterexample" was suffering some numerical bug, leading to the correct conclusion, but with the wrong argument! – Suvrit Jan 7 '12 at 22:04
• but now, I have updated my answer, which includes a counterexample to your new reversed inequality (for $n=6$ though). – Suvrit Jan 7 '12 at 23:10
• And now it seems that the $\geq$ sign rules again for $n=6$... – darij grinberg Jan 7 '12 at 23:13
• Update: after some more experimentation, it seems that $L\ge R$ holds for $2,3,6,7,10,...$, while $L \le R$ holds for $4,5,8,9,...$---do you think we can safely conjecture from this a "skip by 2" pattern for this alternating behavior of the inequalities? – Suvrit Jan 8 '12 at 14:48
• For n=4, my computer says that the Product-Sum difference divided by the two Vandermonde determinants is an irreducible degree 12 polynomial, all of the coefficients of which are positive. – zeb Jan 16 '12 at 23:13

Ok, I have a functional generalization of your Product-Sum conjecture using a very simple method.

Let $f:\mathbb{R}\rightarrow \mathbb{R}$ be any function with a nonnegative $\binom{n}{2}$th derivative. I claim that we have the following functional inequality:

$\sum_{\pi\in S_n} (-1)^{\sigma(\pi)}f(\sum_i a_ib_{\pi(i)}) \ge 0$.

Plugging in $f(x) = -(-1)^{\binom{n}{2}}\log(x)$, we see that your inequality holds as long as $\sum_i a_ib_{n+1-i} \ge 0$.

To prove the functional inequality, it clearly suffices to prove it in the case that the $b_i$s are all distinct positive integers, so assume from now on that this is the case. Let $x_i = e^{a_i}$. Note first that in the special case in which $f(x) = e^x$, we get that

$\sum_{\pi\in S_n} (-1)^{\sigma(\pi)}\prod_ix_i^{b_{\pi(i)}} = \det((x_i^{b_j})_{i,j})$

which is $\prod_{i\lt j}(x_i-x_j)$ times the Schur polynomial $s_{(b_1-n+1,...,b_n)}(x_1,...,x_n)$, and as is well known Schur polynomials have all of their coefficients nonnegative. For every monomial $x^m = \prod_i x_i^{m_i}$, let $c_m$ be its coefficient in the Schur polynomial $s_{(b_1-n+1,...,b_n)}(x_1,...,x_n)$.

Next, let $S_a$ be the shift operator - i.e., let $S_a(f)(x) = f(x+a)$. Then it is easy to check that we have

$\sum_{\pi\in S_n} (-1)^{\sigma(\pi)}f(\sum_i a_ib_{\pi(i)}) =\sum_mc_m(\prod_{i\lt j}(S_{a_i}-S_{a_j}))(f)(\sum_ia_im_i)$,

which is nonnegative since we have $(\prod_{i\lt j}(S_{a_i}-S_{a_j}))(f)(x) \ge 0$ for any $x$ and any function $f$ with nonnegative $\binom{n}{2}$th derivative.

• Glad you made this work. – Gjergji Zaimi Jan 21 '12 at 1:35
• Ah!! I finally see what you are doing when you say "it is easy to check that we have [...]": you are applying the polynomial identity $\sum_{\pi\in S_n} (-1)^{\sigma(\pi)}\prod_ix_i^{b_{\pi(i)}} = \det((x_i^{b_j})_{i,j})$ to $x_i=S_{a_i}$, using the fact that the algebra generated by the shift operators is commutative. But how do you know at the end that $(\prod_{i\lt j}(S_{a_i}-S_{a_j}))(f)(x) \ge 0$ for any $x$ and any function $f$ with nonnegative $\binom{n}{2}$th derivative? I vaguely remember a formula giving the finite difference quotient of a function as an integral ... – darij grinberg Jan 26 '12 at 14:13
• ... of its $n$-th derivative over a simplex, and I suspect this to be something alike, but I can't quite solidify this into a proof. – darij grinberg Jan 26 '12 at 14:13
• Ah, I see this too now. We write $S_{a_i}-S_{a_j}$ formally as $\int_{a_i}^{a_j} DS_t dt$, where $D$ is the differentiation operator. Since the $D$ commutes with the $S_t$'s, we get $\prod_{i\lt j}(S_{a_i}-S_{a_j}) = D^{\binom{n}{2}}\cdot\left(\text{integral of }S_{\text{something}}\text{ over a rectangular box}\right)$. – darij grinberg Jan 26 '12 at 14:30
• Beautiful proof! – darij grinberg Jan 26 '12 at 14:30

The first one is certainly false as stated even for $n=4$. Indeed, let's choose $a_j=1+t\alpha_j$, $b_j=1+t\beta_j$ where $t$ is very small and $\sum_j\alpha_j=\sum_j\beta_j=0$. Let $S(\pi)=\sum_j\alpha_j\beta_{\pi(j)}$. Then we are basically looking at $\sum_\pi(-1)^{\sigma(\pi)}\log(1+tS(\pi))$. (I lost the square and the factor of $n$ but they change nothing). Decomposing $\log$ into power series, we see that we need to look at the power sums $\sum_\pi(-1)^{\sigma(\pi)}S(\pi)^m$. They are polynomials of degree $2m$ divisible by that "double Vandermond" product you mentioned, so the first non-zero sum corresponds to $m=6$ and it turns out to be positive, which, together with the fact that the even powers have negative coefficients, shows that the inequality fails for small enough $t$. To see that the sum is positive note that it is proportional to the double Vandermond product, so all one needs is to determine the sign of the constant on any particular pair of vectors. It turns out to be positive (stupid computation using some equally stupid program).

This calls for further investigation but I have no time right away :(.

• Sorry for not noticing it earlier, but yes... the original conjectures are wrong for $n=4$. The new question is whether they are true with reverse inequality sign for $n\geq 4$, or the sign is indefinite. – darij grinberg Jan 7 '12 at 20:23
• Change the sign back to $\geq$ for $n=6$ (I think). At least this is what the examples seem to show; there is always a chance that the inequality would be wrong even with $\geq$. I have no idea what causes these sign turbulences; to be honest they don't give me much hope for the conjectures to hold. But I wouldn't be surprised if at least the $n$'s up to some bound yield definite true inequalities, Shapiro-like. The AoPS people would probably have some fun crunching them with SOS... – darij grinberg Jan 7 '12 at 23:22
• Then post on AoPS :) Actually I like it more there: the discussion format there is much more convenient and posting graphs is easier (I surmise we'll need a few). At this point I would try to prove the power sum inequality, which should be always $\ge$... – fedja Jan 7 '12 at 23:44
• I'll post it on AoPS tomorrow (sorry, too tired right now) - but now that we know it fails for $n=7$, it is probably not prone to reasonable approaches. I'm still interested in the tropical version, though. I'll put that on AoPS, too. – darij grinberg Jan 8 '12 at 2:12
• BTW, I assume your $\left(-1\right)^{\sigma\left(\pi\right)}$ should be a $\left(-1\right)^{\pi}$. – darij grinberg Jan 8 '12 at 17:19

Summary + Update: Sorry, I again made errors due to floating point (cheap excuse: I computed this rather late yest night).

For $n=4,5$ the reversed inequality seems to hold, for $n=6,7$ the original inequality seems to hold.

Countx for $n=7$ that breaks lhs $\le$ rhs: $a=(67, 63, 60, 44, 37, 22, 13)$ and $b=(97, 75, 71, 65, 33, 32, 31)$.

So it seems that a much more careful assessment is needed for this amazing inequality!

Older Update Thanks to fedja and darij in catching my error! The mistake was in using Matlab, whence numerical errors led me to present a wrong "counterexample" but with the correct conclusion. Fixed now.

Using $n=6$, it seems that even the reverse "product-sum" conjecture is false; try $a=(10,7,5,4,3,0)$ and $b=(8,6,5,3,2,0)$.

However, for $n=4$ or $n=5$, it seems that the reversed conjecture might be true.

The first conjecture is false. I guess then, the second one must be false too.

A random-search reveals that for $a = (5,3,2,0)$ and $b=(5,4,3,2)$ the difference lhs - rhs is $\approx -3.84 \times 10^{13}$.

Just to make sure I got it right. Here's what I did.

1. Generate two random vectors $a$ and $b$, sort them in descending order
2. Generate all the even permutations on $n$ letters and all the odd ones
3. Compute the products.
• I can't believe anything with $a$ having two equal elements can be a counterexample to any of the two questions... – darij grinberg Jan 7 '12 at 19:08
• Anyway, you are right in that random-search is a good idea. I have managed to define the LHS and RHS in a reasonable way (induction...) feasible for computation (still not symbolic) and found that in all the numeric cases for $n=4$ and $n=5$ that came into my mind, the product-sum conjecture actually holds WITH THE REVERSE SIGN. This is absolutely strange. – darij grinberg Jan 7 '12 at 19:29
• If two $a_j$ coincide, you should get $0$, so something is wrong. – fedja Jan 7 '12 at 20:05
• This is fascinating. Not only have I checked your counterexample to the reverse inequality for $n=6$; also all my other cases suggest that for $n=6$ the inequality again holds with an $\geq$ sign. What the heck is going on? – darij grinberg Jan 7 '12 at 23:11
• As Kronecker was writing that "God made the integers; all else is the work of man", Satan was busy inventing floats. – darij grinberg Jan 8 '12 at 16:01

An interesting observation:

Let's copy fedja's notation $S(\pi) = \sum_i a_ib_{\pi(i)}$. Suppose it really was the case that for every $n$, we had that the ratio between $(-1)^{n \choose 2}(\prod_{\pi\in A_n} S(\pi) - \prod_{\pi\not\in A_n} S(\pi))$ and the double Vandermonde had all coefficients nonpositive.

Let $D_a = \sum_i \frac{\partial}{\partial a_i}$. Then since $D_a(a_i-a_j) = D_a(b_i-b_j) = 0$ for any $i,j$, we see that for any $k$,

$(-1)^{n \choose 2}\frac{D_a^k(\prod_{\pi\in A_n} S(\pi) - \prod_{\pi\not\in A_n} S(\pi))}{\prod_{i\lt j}(a_i-a_j)(b_i-b_j)}$

is also a polynomial with all of its coefficients nonpositive, and thus $(-1)^{n \choose 2}D_a^k(\prod_{\pi\in A_n} S(\pi) - \prod_{\pi\not\in A_n} S(\pi))$ is always nonpositive as well.

Next, note that $D_a S(\pi) = \sum_i b_i$ for each $\pi$, so $D_a^k\prod_{\pi\in A_n} S(\pi)$ is just $(\sum_i b_i)^kk!$ times the $(|A_n|-k)$th elementary symmetric polynomial of the $S(\pi)$s for $\pi \in A$, and similarly for $D_a^k\prod_{\pi\not\in A_n} S(\pi)$. Thus, in this case, we would also have the inequality

$(-1)^{n\choose 2}(\sum_{\{\pi_1, ..., \pi_k\}\subseteq A_n}\prod_{i=1}^k S(\pi_i) - \sum_{\{\pi_1, ..., \pi_k\}\subseteq S_n-A_n}\prod_{i=1}^k S(\pi_i)) \le 0$.

This suggests that we might be able to prove all of these inequalities by induction on $n, k$: if we know it holds for $n, k-1$, then to prove it for $n,k$ it suffices to check the inequality when $a_n = 0$ (or even when both $a_n$ and $b_n$ are $0$). Unfortunately there does not seem to be any nice simplification from setting $a_n = 0$...

Edit: the following is false. (see my comment below) The Sum-maximum conjecture is easily proved by Fedja's observation. Put $S_a:=\frac1n\sum a_k$ and for big $N$, define $a_k^':=1+\frac{a_k-S_a}N$, similarly for $S_b$ and $b_k^'$. According to Fedja, the Product-sum conjecture holds for $a_k^'$ and $b_k^'$, and this implies the Sum-maximum conjecture for $a_k^'$ and $b_k^'$. Now we can replace $a_k^'$ and $b_k^'$ by $a_k$ and $b_k$ because the linear transformations don't change anything for the difference of the two sums.

Too bad we can't say the same for the Product-sum conjecture as well.

• Well, it seemed too easy... The "tropical" trick needs the first conjecture to be valid not only in a neighborhood of 1, because $x$ is sent to $\infty$. So the flaw is that I thought the second conjecture is implied by the first [i]for the same $a_k,b_k$[/i], but this is not the case. :( – Wolfgang Jan 14 '12 at 11:02