An inequality for rearrangement-style sums

Question

The following is a holdover from my math contest days that I never got around to solve.

We will use the notation $\left[ k\right] $ for the set $\left\{ 1,2,\ldots,k\right\} $ whenever $k$ is a nonnegative integer.

Let me first state my question in its general form, which is sadly not very inviting. I recommend taking a look at the particular cases $p=2$ (proven) and $p=3$ (open) stated further below (as Theorem 1 and Conjecture 2, respectively). The $p=2$ case also comes with motivation.

Question. Let $n$ and $p$ be two nonnegative integers. For each $i\in\left[ n\right] $ and $j\in\left[ p\right] $, let $a_{i,j}$ be a nonnegative real. For each $k\in\left[ n\right] $, let \begin{align} m_{k}=\max\left\{ \prod_{j=1}^{p}a_{u_{j},j}\ \mid\ \left( u_{1} ,u_{2},\ldots,u_{p}\right) \in\left[ n\right] ^{p};\ \max\left\{ u_{1},u_{2},\ldots,u_{p}\right\} =k\right\} . \end{align} Also, let $\sigma_{1},\sigma_{2},\ldots,\sigma_{p}$ be $p$ permutations of $\left[ n\right] $. Prove or disprove that \begin{align} \sum_{k=1}^{n}\prod_{j=1}^{p}a_{\sigma_{j}\left( k\right) ,j}\leq\sum _{k=1}^{n}m_{k}. \end{align}

This is easy to see for $n = 2$; I also have proven this for $p = 2$. Experiments with Sage seem to suggest that the $n = 3$ and $p = 3$ case is also true.

One simple observation about the question is that if $\sigma$ is any permutation of $\left[p\right]$, then replacing $\sigma_1, \sigma_2, \ldots, \sigma_p$ by $\sigma_1 \circ \sigma, \sigma_2 \circ \sigma, \ldots, \sigma_p \circ \sigma$ leaves the left hand side unchanged. Thus, we can WLOG assume that $\sigma_1 = \operatorname{id}$. This reduces the number of permutations involved to $p-1$.

The case $p = 2$: When $p = 2$, the question thus takes the following form (where we rename $a_{i,1}, a_{i,2}, \sigma_2$ as $a_i, b_i, \sigma$, respectively):

Theorem 1. Let $a_1, a_2, \ldots, a_n$ be $n$ nonnegative reals.

Let $b_1, b_2, \ldots, b_n$ be $n$ nonnegative reals.

For every $k\in\left[n\right]$, let $m_{k}=\max\left( \left\{ a_{1}b_{k},a_{2}b_{k},\ldots,a_{k}b_{k}\right\} \cup\left\{ a_{k}b_{1}% ,a_{k}b_{2},\ldots,a_{k}b_{k}\right\} \right) $.

Let $\sigma$ be a permutation of $\left[n\right]$.

Then, \begin{align} a_{1}b_{\sigma\left( 1\right) }+a_{2}b_{\sigma\left( 2\right) } +\cdots+a_{n}b_{\sigma\left( n\right) }\leq m_1 + m_2 + \cdots + m_n. \end{align}

This was problem O222 in Mathematical Reflections (my proof). I originally came up with it when trying to prove an inequality from Ahlswede/Blinovsky (see my proof for details); but it also easily yields the classical rearrangement inequality. (In a sense, Theorem 1 relates to the Ahlswede/Blinovsky result as Chebyshev does to rearrangement.)

Note that the rearrangement inequality shows that the left hand side of the inequality in Theorem 1 is maximized (for fixed $n$, $a_i$ and $b_i$) when $\sigma$ has the property that the tuples $\left(a_1, a_2, \ldots, a_n\right)$ and $\left(b_{\sigma\left(1\right)}, b_{\sigma\left(2\right)}, \ldots, b_{\sigma\left(n\right)}\right)$ are equally sorted (i.e., we have $\left(a_i - a_j\right) \left(b_{\sigma\left(i\right)} - b_{\sigma\left(j\right)}\right) \geq 0$ for all $i$ and $j$). This observation did not end up useful in my proof of Theorem 1.

The case $p = 3$: To give some intuition for the Question above, let me state its $p = 3$ case as a conjecture (renaming $a_{i,1}, a_{i,2}, a_{i,3}, \sigma_2, \sigma_3$ as $a_i, b_i, c_i, \sigma, \tau$ and setting $\sigma_1 = \operatorname{id}$ as before):

Conjecture 2. Let $a_1, a_2, \ldots, a_n$ be $n$ nonnegative reals.

Let $b_1, b_2, \ldots, b_n$ be $n$ nonnegative reals.

Let $c_1, c_2, \ldots, c_n$ be $n$ nonnegative reals.

For every $k\in\left[n\right]$, let $m_{k}=\max\left\{ a_{i}b_{j}c_{\ell}\ \mid\ \max\left\{ i,j,\ell\right\} =k\right\} $.

Let $\sigma$ and $\tau$ be two permutations of $\left[n\right]$.

Prove or disprove that \begin{align} a_{1}b_{\sigma\left( 1\right) }c_{\tau\left( 1\right) }+a_{2} b_{\sigma\left( 2\right) }c_{\tau\left( 2\right) }+\cdots+a_{n} b_{\sigma\left( n\right) }c_{\tau\left( n\right) }\leq m_{1}+m_{2} +\cdots+m_{n}. \end{align}

I believe that we can again use some sort of rearrangement inequality to maximize the left hand side of this inequality, but I don't expect this to be useful (nor am I fully sure about it -- most treatments of rearrangement inequality for more than two tuples run into combinatorial troubles around the concept of "equally sorted" and equality cases).

Answer 1

Let me prove it for $p=3$ (only because the notations look more friendly.) The maximum of left hand side is realized when the arrays $(a_i),(b_{\sigma(i)}),(c_{\tau(i)})$ are equally sorted, so let us assume that it is the case.

I claim that not only the sum, but the $s$-th largest summand of RHS (clarification: first largest means maximal) is not less than the $s$-th largest summand in LHS, for any $s=1,2,\dots,n$. Denote by $\alpha, \beta, \gamma$ the $s$-th largest elements of the arrays $a, b, c$ respectively. Choose minimal indices $i, j, k$ respectively for which $a_i\geqslant \alpha$, $b_j\geqslant \beta$, $c_k\geqslant \gamma$. Without loss of generality $k=\max(i, j, k) $. Choose any $r$ such that $c_r\geqslant \gamma$. We have $r\geqslant k\geqslant \max(i,j)$, therefore $m_r\geqslant a_i b_j c_r\geqslant \alpha \beta \gamma$. We get at least $s$ such values of $r$, thus $s$-th largest $m$ is not less than $\alpha \beta\gamma$, as desired.