Processing math: 0%

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