Friday, February 19, 2016

The rearrangement inequality is everywhere

Recently, I've been talking with John Susice about some elementary Olympiad-style problems. I told him that in high school I was taught that virtually every inequality problem that appeared in this setting follows from the Rearrangement Inequality. This states that if $x_1\le \cdots\le x_n$ and $y_1\le \cdots\le y_n$ are real numbers, then the expression
$$x_1 y_{\sigma(1)}+\cdots+x_n y_{\sigma(n)}$$
for $\sigma$ a permutation on $[n]$ is maximized when $\sigma$ is the identity permutation and minimized when $\sigma$ is the reversing permutation. To me, this neatly isolates a useful and general principle that seems kind of obvious in hindsight.

The proof of the $n=2$ case of the inequality, which is all I'll need below, is just to expand $(x_2-x_1)(y_2-y_1)\ge 0$. This case also implies the AM-GM inequality (taking $x_1=y_1=\sqrt{a}$ and  $x_2=y_2=\sqrt{b}$).

Now sometime later, John told me an interesting problem about factoring numbers. He had a solution using a trick similar to Euler's product, but for me this was a chance to test my thesis about the rearrangement inequality:

Problem: Prove that every natural number $n$ has at least as many factors congruent to 1 (mod 4) as factors congruent to 3 (mod 4).

Solution: By induction. Clearly this holds for 1 and for primes. Now suppose $n$ is composite, so write $n=pq$ where $p,q<n$. For any integer $k$, let $r_k$ denote the number of factors it has which are congruent to 1 (mod 4) and $s_k$ the number of factors congruent to 3 (mod 4).

The product of two 1 (mod 4) numbers is still 1 (mod 4), and the product of two 3 (mod 4) numbers is 3 (mod 4). On the other hand, the product of a 1 (mod 4) and a 3 (mod 4) is a 3 (mod 4), and even factors can never be 1 or 3 (mod 4). This proves that $r_n=r_pr_q+s_ps_q$, which must be greater than or equal to $s_n=r_ps_q+r_qs_p$ by the rearrangement inequality!


No comments:

Post a Comment