Suppose that $f$ is a convex function and $\{x_i\}_{i=1}^n$ and $\{y_i\}_{i=1}^n$ are real numbers such that $x_1\leq x_2\leq \dots \leq x_n$ and $y_1\leq y_2\leq \dots \leq y_n$. Let $\{u_i\}_{i=1}^n$ be any permutation of $y_i$'s. Then $$f(x_1+y_n)+f(x_2+y_{n-1})+\dots+f(x_n+y_1)\leq f(x_1+u_1)+f(x_2+u_{2})+\dots+f(x_n+u_n)\leq $$ $$\leq f(x_1+y_1)+f(x_2+y_2)+\dots+f(x_n+y_n).$$

In my book it is called as Generalized rearrangement inequality. I do know the regular rearrangement inequality and its proof.

I have no ideas how to prove the above inequality and how the regular one follows from it?

Would be very grateful for help!


1 Answer 1


One can proceed similarly as in the proof of the “regular” rearrangement inequality: If $\sigma$ is a permutation of $\{1, \ldots ,n\}$ and not the identity then there are indices $j < k$ such that exchanging $\sigma(j)$ and $\sigma(k)$ gives a new permutation $\tau$ with more fixed points than $\sigma$ and $$ \tag{*} \sum_{i=1}^n f(x_i + y_{\sigma(i)}) \le \sum_{i=1}^n f(x_i + y_{\tau(i)}) \, . $$ If $\tau$ is not the identity then this step can be repeated, and after finitely many steps one obtains $$ \sum_{i=1}^n f(x_i + y_{\sigma(i)}) \le \sum_{i=1}^n f(x_i + y_i) \, . $$

In the case of the “regular” rearrangement inequality one uses that for $a_1 \le a_2$ and $b_1 \le b_2$ $$ (a_2-a_1)(b_2-b_1) \ge 0 \implies a_1 b_2 + a_2 b_1 \le a_1 b_1 + a_2 b_2 \, . $$ In our case one can use the following to prove $(*)$:

If $f$ is a convex function and $a_1 \le a_2$ and $b_1 \le b_2$ then $$ f(a_1 + b_2) + f(a_2 + b_1) \le f(a_1 + b_1) + f(a_2 + b_2) \, . $$

This holds trivially if $a_1 =a_2$ or $b_1 = b_2$. In the case $a_1 < a_2$ and $b_1 < b_2$ it follows from adding the convexity conditions: $$ f(a_1 + b_2) \le \frac{a_2-a_1}{a_2+b_2-a_1-b_1} f(a_1 + b_1) + \frac{b_2 - b_1}{a_2+b_2-a_1-b_1} f(a_2 + b_2) \\ f(a_2 + b_1) \le \frac{b_2-b_1}{a_2+b_2-a_1-b_1} f(a_1 + b_1) + \frac{a_2 - a_1}{a_2+b_2-a_1-b_1} f(a_2 + b_2) $$

For positive sequences $u_1, \ldots, u_n$ and $v_1, \ldots, v_n$ the normal rearrangement inequality follows from the generalized one with $f(t)=e^t$ applied to $x_i = \log u_i$ and $y_i = \log v_i$, since then $$ f(x_i + y_{\sigma(i)}) = u_i \cdot v_{\sigma(i)} \ . $$

It is also a consequence of Karamata's inequality: Set $$ (a_1, a_2, \ldots , a_n) = (x_n + y_n, x_{n-1}+y_{n-1}, \ldots, x_1 + y_1) $$ and let $(b_1, b_2, \ldots , b_n)$ be a decreasing rearrangement of $$ (x_n + u_n, x_{n-1}+u_{n-1}, \ldots, x_1 + u_1) \, . $$ Then $$ (a_1,a_2,\ldots,a_n)\succ(b_1,b_2,\ldots,b_n) $$ so that $$ f(a_1)+f(a_2)+ \ldots +f(a_n) \ge f(b_1)+f(b_1)+ \ldots +f(b_n) $$ which is the desired conclusion.

  • $\begingroup$ You wrote that $f(a_1 + b_2) \le \frac{a_2-a_1}{a_2+b_2-a_1-b_1} f(a_1 + b_1) + \frac{b_2 - b_1}{a_2+b_2-a_1-b_1} f(a_2 + b_2)$ follows from convexity but it is not so obvious to me. If $\lambda=\frac{a_2-a_1}{a_2+b_2-a_1-b_1}$ and $\mu=\frac{b_2 - b_1}{a_2+b_2-a_1-b_1} $ then $\lambda,\mu>0$ and $\lambda+\mu=1$. Since $f$ is convex then $f(\lambda x+\mu y)\leq \lambda f(x)+\mu f(y)$. But I see that $\lambda x+\mu y$ is not equal to $a_1+b_2$. Or am I missing something? $\endgroup$
    – ZFR
    Oct 20, 2020 at 14:31
  • $\begingroup$ Would be grateful if you can explain my question, please. $\endgroup$
    – ZFR
    Oct 20, 2020 at 15:07
  • 1
    $\begingroup$ @ZFR: I used the convexity condition in the form $f(y) \le \frac{z-y}{z-x}f(x) + \frac{y-x}{z-x}f(z)$ with $x=a_1+b_1 < y=a_1+b_2 < z=a_2+b_2$. – You can also verify that $(a_2-a_1)(a_1+b_1)+(b_2-b_1)(a_2+b_2) = (a_1+b_2)(a_2+b_2-a_1-b_1)$ $\endgroup$
    – Martin R
    Oct 20, 2020 at 15:14
  • $\begingroup$ Yes your answer is really detailed and I understood everything! Thanks a lot for your help! But let me ask you one more question: You proved normal rearrangement inequality for positive sequences. But as far as I know it is true for arbitrary real sequences, right? $\endgroup$
    – ZFR
    Oct 24, 2020 at 10:34
  • $\begingroup$ @ZFR: Yes, the normal rearrangement inequality holds for arbitrary real numbers, but I am not sure if that can be proved using this generalized rearrangement inequality (one has to transform the product into a sum, which usually involves the logarithm). – However, there is another generalization which covers both the normal version (by choosing $f_i(x) = x y_i$) and also your version (by choosing $f_i(x) = f(x + y_i)$). $\endgroup$
    – Martin R
    Oct 24, 2020 at 11:02

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.