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$
    – RFZ
    Oct 20, 2020 at 14:31
  • $\begingroup$ Would be grateful if you can explain my question, please. $\endgroup$
    – RFZ
    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$
    – RFZ
    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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .