Muirhead's Inequality

Before Muirhead's Inequality can be defined, it is first necessary to define another term.

Given two sequences of real numbers $\displaystyle A=a_1,a_2,\cdots,a_n$ and $\displaystyle B=b_1,b_2,\cdots,b_n$ , $A$ is said to majorize $B$ if and only if all of the following are true:

$\displaystyle a_1\geq b_1$

$\displaystyle a_1+a_2\geq b_1+b_2$

$\displaystyle \vdots$

$\displaystyle a_1+a_2+\cdots+a_{n-1}\geq b_1+b_2+\cdots+b_{n-1}$

$\displaystyle a_1+a_2+\cdots+a_n=b_1+b_2+\cdots+b_n$

With this out of the way, it is now possible to define Muirhead's Inequality.

Let $\displaystyle x_1,x_2,\cdots,x_n$ be a set of positive integers, and let $\displaystyle A=a_1,a_2,\cdots,a_n$ , and $\displaystyle B=b_1,b_2,\cdots,b_n$ be sets of positive real numbers (note that they all contain the same number of terms) such that $\displaystyle A$ majorizes $\displaystyle B$ . Then, using sigma notation, it is possible to say that

$\displaystyle \sum_{sym} {x_1}^{a_1}{x_2}^{a_2}\cdots {x_n}^{a_n}\geq \sum_{sym} {x_1}^{b_1}{x_2}^{b_2}\cdots {x_n}^{b_n}$

A concrete example will probably help to understand the inequality. Since the sequence $\displaystyle 5,1$ majorizes $\displaystyle 4,2$ , Muirhead's inequality tells us that, for any positive $\displaystyle x,y$ , we have

$\displaystyle x^5y^1+y^5x^1\geq x^4y^2+y^4x^2$

A common bruteforce technique with inequalities is to clear denominators, multiply everything out, and apply Muirhead's or Shur's. However, it is worth noting that any inequality that can be proved directly with Muirhead can also be proved using the Arithmetic Mean-Geometric Mean inequality. In fact, IMO gold medalist Thomas Mildorf says it is unwise to use Muirhead in an Olympiad solution; you should use an application of AM-GM instead.

As an example, here's how the above inequality can be proved using AM-GM:

$\displaystyle \frac{x^4+x^4+x^4+y^4}{4}\geq\sqrt[4]{x^{12}y^4}=x^3y$