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 and that are similarly ordered, we have
where are permutations of respectively.
A notable difference from the rearrangement inequality is that the variables are now required to be non-negative.
For non-negative integers , prove that
First, note that and We have a product of terms on both sides, which suggests the reverse rearrangement inequality.
Recall that the minimum happens when the two sequences and 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 , and when they are oppositely ordered, they might pair each other up and give the same sum like .
Indeed, if we let , we get that and
Thus, by reverse rearrangement, we have and we are done.
Let be positive reals. Prove that
It is slightly hard to find similarly ordered sequences here. Let's simplify the inequality by clearing denominators. We want to show that
Now, the similarly ordered sequences jump out at us. If then we have the similarly ordered sequences and , so we apply the theorem to obtain the following:
Given that are reals, prove that
WLOG, let Now consider the substitution
for all . Note that as increases, also increases; thus and are similarly ordered. Also note that the condition that our variables must be non-negative is also satisfied, because
Using the reverse rearrangement inequality with the permutation , we get the inequality
This simplifies as
which is exactly what we wanted to prove.
Given that are non-negative reals such that , prove that
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 ; thus let's homogenize. The LHS is simple:
But wait a second: and so we have
Now let's homogenize the RHS:
implying our inequality turns into
Dividing both sides by , we get
Observe that we only have , , and terms on both sides of the inequality, which prompts us to substitute , , and . Then we just need to prove the inequality
This is perfect for reverse rearrangement now:
so we are done.
Here are some guidelines to help motivate you to try using RR:
- if there are multiple products on both sides of the inequality
- if there are permutations of the terms, especially the "shift-by-one" permutation
- if there is a way to simplify an expression through wishful thinking of terms canceling out
- 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.
The only permutation on 1 element is . The inequality is trivially true.
The non-trivial permutation on 2 elements is . We want to show that if and , then Expanding the terms, cancelling common terms, and shifting the terms to one side, we get This inequality is trivially true since both of the terms are non-negative.
Suppose that the statement is true for permutations on elements. Consider a permutation on elements.
If , then we can cancel from both sides of the inequality, and we now have a permutation on elements, and hence the inequality is true.
If , let . We have and , so from the induction hypothesis we have Now, consider the permutation on elements given by for and . Then, by the induction hypothesis, we have
Hence, combined with inequality , we get that
Therefore, the inequality is proven.
Note: We used the fact that the sequences are non-negative, because we multiplied the induction hypothesis by . In order for the sign to not change, we have to assume that 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) Let be a fixed positive number. Given positive reals , show that
2) Let be a decreasing, positive function. Let be a sequence of positive reals. Let be any permutation on elements. Show that