Reverse Rearrangement Inequality

The reverse rearrangement inequality allows us to compare the product of sums of terms in an inequality. It has an uncanny resemblance to the famous rearrangement inequality, which is about the sum of product of terms, hence its namesake. It was first observed and explained by Daniel Liu.

Given two non-negative sequences $\{a_n\}$ and $\{b_n\}$ that are similarly ordered, we have

$$\prod_{k=1}^n(a_k+b_k)\le \prod_{k=1}^n (a_k+b_{\sigma(k)})\le \prod_{k=1}^n (a_k+b_{n-k+1}),$$

where $\sigma(1),\sigma(2),\ldots, \sigma(n)$ are permutations of $1,2,\ldots, n,$ respectively. $_\square$

A notable difference from the rearrangement inequality is that the variables are now required to be non-negative.

For non-negative integers $n$, prove that $$$$

$$n!\le \left(\dfrac{n+1}{2}\right)^n.$$

---

First, note that $$n!=1\cdot 2\cdot 3\cdots (n-1) \cdot n$$ and $$\left(\dfrac{n+1}{2}\right)^n=\left(\dfrac{n+1}{2}\right)\left(\dfrac{n+1}{2}\right)\cdots \left(\dfrac{n+1}{2}\right).$$ We have a product of terms on both sides, which suggests the reverse rearrangement inequality.

Recall that the minimum happens when the two sequences $\{a\}$ and $\{b\}$ are similarly ordered and the maximum happens when said sequences are oppositely ordered. We see that if two sequences are similarly ordered, their sum would be increasing, like the $n!$, and when they are oppositely ordered, they might pair each other up and give the same sum like $\frac{n+1}{2}$.

Indeed, if we let $a_k=b_k=\frac{k}{2}$, we get that $$(a_1+b_1)(a_2+b_2)\cdots (a_n+b_n)=1\cdot 2\cdots n=n!$$ and $$(a_1+b_n)(a_2+b_{n-1})\cdots (a_n+b_1)=\left(\dfrac{n+1}{2}\right)^n.$$

Thus, by reverse rearrangement, we have $$n!\le \left(\dfrac{n+1}{2}\right)^n$$ and we are done. $_\square$

Let $x, y, z$ be positive reals. Prove that $$$$

$$\left( \frac{ x}{y} + \frac{ y^2} { x} \right) \left( \frac{ y}{z} + \frac{ z^2} { y} \right) \left( \frac{ z}{x} + \frac{ x^2} { z} \right) \geq (x+1)(y+1)(z+1).$$

---

It is slightly hard to find similarly ordered sequences here. Let's simplify the inequality by clearing denominators. We want to show that

$$\left( x^2 + y^3\right) \left( y^2 + z^3 \right) \left( z^2 + x^3\right) \geq x^2 y^2 z^2 ( x+1)(y+1)( z+1).$$

Now, the similarly ordered sequences jump out at us. If $x\ge y\ge z,$ then we have the similarly ordered sequences $x^2\ge y^2\ge z^2$ and $x^3\ge y^3\ge z^3$, so we apply the theorem to obtain the following:

$$\begin{aligned} \left(x^2 + y^3\right) \left( y^2 + z^3 \right) \left( z^2 + x^3\right) & \geq \left(x^2 + x^3\right)\left(y^2+y^3\right)\left(z^2+z^3\right) \\ & = x^2 y^2z^2 (x+1)(y+1)(z+1). \ _\square \end{aligned}$$

Given that $x_1,x_2,\ldots, x_n\ge 1$ are reals, prove that

$$\left(x_1^2-x_1+x_2\right)\left(x_2^2-x_2+x_3\right)\cdots \left(x_n^2-x_n+x_1\right)\ge x_1^2x_2^2\cdots x_n^2.$$

---

WLOG, let $x_1\le x_2\le \cdots \le x_n.$ Now consider the substitution

$$\left\{\begin{array}{l} a_k=x_k\\ b_k=x_k^2-x_k \end{array}\right.$$

for all $k=1, \ldots, n$. Note that as $a_k$ increases, $b_k$ also increases; thus $\{a\}$ and $\{b\}$ are similarly ordered. Also note that the condition that our variables must be non-negative is also satisfied, because

$$x_k \ge 1\implies x_k^2-x_k \ge 0.$$

Using the reverse rearrangement inequality with the permutation $\big(\sigma(1),\sigma(2),\ldots, \sigma(n)\big)=(n,1,\ldots, n-1)$, we get the inequality

$$\begin{aligned} \prod_{cyc}(a_1+b_1)&\le \prod_{cyc}(a_2+b_1)\\ \prod_{cyc}(x_1+x_1^2-x_1)&\le \prod_{cyc}(x_2+x_1^2-x_1). \end{aligned}$$

This simplifies as

$$x_1^2x_2^2\cdots x_n^2\le \left(x_1^2-x_1+x_2\right)\left(x_2^2-x_2+x_3\right)\cdots \left(x_n^2-x_n+x_1\right),$$

which is exactly what we wanted to prove. $_\square$

Given that $x,y,z$ are non-negative reals such that $xy+yz+zx=1$, prove that $$$$

$$\big(x^2+y^2+2\big)\big(y^2+z^2+2\big)\big(z^2+x^2+2\big)\ge 8(x+y+z-xyz)^2.$$

---

The LHS looks great for some reverse rearrangement, but the RHS not so much. We only have the product of two terms (and a constant).

But first things first, we have a condition that $xy+yz+zx=1$; thus let's homogenize. The LHS is simple:

$$\prod_{cyc}\big(x^2+y^2+2\big)=\prod_{cyc}\big(x^2+y^2+2xy+2yz+2zx\big).$$

But wait a second: $x^2+xy+yz+zx=(x+y)(x+z)$ and $y^2+xy+yz+zx=(y+z)(y+x),$ so we have

$$\begin{aligned} \prod_{cyc}\big(x^2+y^2+2xy+2yz+2zx\big)&=\prod_{cyc}\big((x+y)(x+z)+(y+z)(y+x)\big)\\ &=\prod_{cyc}(x+y)(x+y+2z).\end{aligned}$$

Now let's homogenize the RHS:

$$\begin{aligned} 8(xyz-x-y-z)^2&=8\big(xyz-(xy+yz+zx)(x+y+z)\big)\\ &= 8\left(xyz-\big(3xyz+x^2y+x^2z+y^2x+y^2z+z^2x+z^2y\big)\right)^2\\ &=8\big(x^2y+x^2z+y^2x+y^2z+z^2x+z^2y+2xyz\big)^2\\ &= 8\big((x+y)(y+z)(z+x)\big)^2, \end{aligned}$$

implying our inequality turns into

$$\prod_{cyc}(x+y)(x+y+2z)\ge 8\big((x+y)(y+z)(z+x)\big)^2.$$

Dividing both sides by $(x+y)(y+z)(z+x)$, we get

$$\prod_{cyc}(x+y+2z)\ge 8(x+y)(y+z)(z+x).$$

Observe that we only have $x+y$, $y+z$, and $z+x$ terms on both sides of the inequality, which prompts us to substitute $a=x+y$, $b=x+z$, and $c=y+z$. Then we just need to prove the inequality

$$\prod_{cyc}(b+c)\ge 8abc.$$

This is perfect for reverse rearrangement now:

$$\prod_{cyc}(a+c)\ge \prod_{cyc}(a+a)=(2a)(2b)(2c)=8abc,$$

so we are done. $_\square$

Here are some guidelines to help motivate you to try using RR:

1. if there are multiple products on both sides of the inequality
2. if there are permutations of the terms, especially the "shift-by-one" permutation
3. if there is a way to simplify an expression through wishful thinking of terms canceling out
4. if the sum of all of the terms on both sides of the inequality are the same.

We will provide a proof for the lower bound using induction.

Base case: $n=1$
The only permutation on 1 element is $\sigma(1) = 1$. The inequality is trivially true.

Base case: $n = 2$
The non-trivial permutation on 2 elements is $\sigma(1) = 2, \sigma(2) = 1$. We want to show that if $0 \leq a_1 \leq a_2$ and $0 \leq b_1 \leq b_2$, then $$(a_1 + b_1) ( a_2 + b_2) \leq (a_1 + b_2) ( a_2 + b_1).$$ Expanding the terms, cancelling common terms, and shifting the terms to one side, we get $$0 \leq a_1 b_1 + a_2b_2 - a_1 b_2 - a-2 b_1 = (a_2-a_1)(b_2-b_1).$$ This inequality is trivially true since both of the terms are non-negative.

Induction step:
Suppose that the statement is true for permutations on $k$ elements. Consider $\sigma$ a permutation on $k+1$ elements.

If $\sigma(k+1) = k+1$, then we can cancel $(a_{k+1} + b_{k+1} )$ from both sides of the inequality, and we now have a permutation on $k$ elements, and hence the inequality is true.

If $\sigma(k+1) = j \neq k+1$, let $\sigma(i) = k+1$. We have $a_i \leq a_{k+1}$ and $b_j \leq b_{k+1}$, so from the induction hypothesis we have $$( a_i + b_j)(a_{k+1}+b_{k+1} ) \leq (a_i + b_{k+1} ) ( a_{k+1} + b_{j } ). \qquad (*)$$ Now, consider the permutation $\sigma^*$ on $k$ elements given by $\sigma^*(x) = \sigma(x)$ for $x \neq i$ and $\sigma^* (i) = j$. Then, by the induction hypothesis, we have $$(a_1 + b_1 ) \times \cdots \times ( a_k + b_k ) \leq (a_1 + b_{\sigma^*(1) } ) \times \cdots\times (a_i + b_j) \times \cdots \times ( a_k + b_{\sigma^*(k) } ).$$

Hence, combined with inequality $(*)$, we get that $$\begin{aligned} & (a_1 + b_1 ) \times \cdots \times ( a_k + b_k ) \times (a_{k+1} + b_{k+1}) \\ \leq & (a_1 + b_{\sigma^*(1) } ) \times \cdots\times (a_i + b_j) \times \cdots \times ( a_k + b_{\sigma^*(k) } ) \times (a_{k+1} + b_{k+1}) \\ \leq & (a_1 + b_{\sigma^*(1)} ) \times \cdots\times (a_i + b_{k+1}) \times \cdots \times ( a_k + b_{\sigma^*(k) } ) \times (a_{k+1} + b_{j}) \\ = & (a_1 + b_{\sigma(1)} ) \times \cdots\times (a_i + b_{\sigma(i) }) \times \cdots \times ( a_k + b_{\sigma (k) } ) \times (a_{k+1} + b_{\sigma(k+1)}). \end{aligned}$$

Therefore, the inequality is proven. $_\square$

Note: We used the fact that the sequences are non-negative, because we multiplied the induction hypothesis by $a_{k+1} + b_{k+1}$. In order for the sign to not change, we have to assume that $a_{k+1} + b_{k+1}$ is positive.

The proof of the upper bound is similar and left to the reader.

For a more detailed analysis of this inequality, download Daniel's paper here.

1. If $f(x)$ is a decreasing non-negative function, then

$$\prod \left( a_k + f( a_k ) \right) \geq \prod \left ( a _ k + f ( a_{\sigma(k)} \right)$$

1. If $f(x)$ is a decreasing non-negative function, then

$$\prod \left( a_k f(a_k) + 1 \right) \leq \prod \left( a_k f(a_{\sigma(k) } ) + 1 \right)$$

In each case, the inequality flips for an increasing non-negative function.

1) Let $k$ be a fixed positive number. Given positive reals $\{ b_i \}_{i=1}^n$, show that

$$( b_1 ^2 + k) ( b_2 ^2 + k ) \ldots ( b_n^2 + k) \geq ( b_1 b_2 + k ) ( b_2b_3 + k ) \ldots ( b_n b_1 + k ) .$$

2) Let $f(x)$ be a decreasing, positive function. Let $\{ a_i \} _{i=1} ^ n$ be a sequence of positive reals. Let $\sigma$ be any permutation on $n$ elements. Show that

$$\prod_{k=1}^n \big( a_k + f( a_k) \big) \geq \prod_{k=1}^n \left( a_k + f\big( a_{\sigma(k)} \big) \right) .$$

• Rearrangement Inequality

• Holders Inequality