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$.)
 A: 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.
A: 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 :(.
A: 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.


*

*Generate two random vectors $a$ and $b$, sort them in descending order

*Generate all the even permutations on $n$ letters and all the odd ones

*Compute the products.

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