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



Rearrangement-style inequality with lots of terms and little evidence
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.


