# An inequality for rearrangement-style sums

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

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.
• I am not sure why you can WLOG assume the tuples to be equally sorted. Replacing $b_i$ by $b_{\sigma\left(i\right)}$ changes the RHS, too! Feb 23 '19 at 19:14
• @darijgrinberg I mean that the permutations on the left are chosen so that $(a_i),(b_{\sigma(i)}),(c_{\tau(i)})$ are equally sorted. Feb 23 '19 at 19:47
• Thanks. Any chance you could detail the argument for $m_r \geq \alpha\beta\gamma$ ? Feb 23 '19 at 20:55
• @darijgrinberg $m_r\geqslant a_i b_j c_r\geqslant \alpha \beta \gamma$, no? Feb 23 '19 at 21:53