Muirhead's Inequality

More spread-out exponents give bigger symmetric sums: if a b then [ a] ≥ [ b].

The idea

Theorem (Muirhead's inequality).

Let $\mathbf{a} = (a_1 \ge \cdots \ge a_n)$ and $\mathbf{b} = (b_1 \ge \cdots \ge b_n)$ be exponent tuples with $\mathbf{a} \succ \mathbf{b}$, and let $x_1, \dots, x_n$ be positive reals. Write $[\mathbf{a}] \;=\; \sum_{\text{sym}} x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n}$ for the sum of this monomial over all $n!$ orderings of the variables. Then $[\mathbf{a}] \ge [\mathbf{b}]$, and when $\mathbf{a} \neq \mathbf{b}$, equality holds if and only if $x_1 = \cdots = x_n$.

The hypothesis $\mathbf{a} \succ \mathbf{b}$ says that $\mathbf{a}$ majorizes $\mathbf{b}$: the two tuples have the same total, and for every $k$ the first $k$ entries of $\mathbf{a}$ sum to at least as much as the first $k$ entries of $\mathbf{b}$. Plotted against $k$, the running sums $A_k = a_1 + \cdots + a_k$ stay on or above $B_k = b_1 + \cdots + b_k$ and meet them at $k = n$. At a fixed total, $\mathbf{a}$ is the more concentrated tuple and $\mathbf{b}$ the more even one, so the inequality says that concentrating the exponents enlarges the symmetric sum.

The theorem reduces a symmetric inequality in $n$ positive variables to a comparison of two exponent tuples: we check the partial sums of $\mathbf{a}$ against those of $\mathbf{b}$, and the $x_i$ never enter the argument.

Ways to work on it

• Walkthrough. Learn when one symmetric sum dominates another and derive AM-GM as a special case.
• Practice. Check majorization between random exponent triples.
• Hardest. Decide which competition inequalities follow from Muirhead and which do not.

Not sure where to start? Take the ten-question placement test.