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