6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – darij grinberg Feb 23 at 19:14
  • $\begingroup$ @darijgrinberg I mean that the permutations on the left are chosen so that $(a_i),(b_{\sigma(i)}),(c_{\tau(i)})$ are equally sorted. $\endgroup$ – Fedor Petrov Feb 23 at 19:47
  • $\begingroup$ Thanks. Any chance you could detail the argument for $m_r \geq \alpha\beta\gamma$ ? $\endgroup$ – darij grinberg Feb 23 at 20:55
  • $\begingroup$ @darijgrinberg $m_r\geqslant a_i b_j c_r\geqslant \alpha \beta \gamma$, no? $\endgroup$ – Fedor Petrov Feb 23 at 21:53
  • 1
    $\begingroup$ Thank you! And, for future readers' sake: You are using the rearrangement inequality for multiple sequences in your first paragraph. $\endgroup$ – darij grinberg Feb 24 at 2:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.