Difference between revisions of "Muirhead's Inequality"

(Example)
 
(14 intermediate revisions by 8 users not shown)
Line 1: Line 1:
'''Muirhead's Inequality''' states that if a sequence <math>A</math> [[Majorization|majorizes]] a sequence <math>B</math>, then given a set of positive integers <math>x_1,x_2,\cdots,x_n</math>:
+
'''Muirhead's Inequality''' states that if a sequence <math>A</math> [[Majorization|majorizes]] a sequence <math>B</math>, then given a set of positive reals <math>x_1,x_2,\cdots,x_n</math>:
 +
<cmath>\sum_{\text{sym}} {x_1}^{a_1}{x_2}^{a_2}\cdots {x_n}^{a_n}\geq \sum_{\text{sym}} {x_1}^{b_1}{x_2}^{b_2}\cdots {x_n}^{b_n}</cmath>
  
<math>\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}</math>
+
== Example ==
 +
The inequality is easier to understand given an example.  Since the sequence <math>(5,1)</math> majorizes <math>(4,2)</math> (as <math>5>4, 5+1=4+2</math>), Muirhead's inequality states that for any positive <math>x,y</math>,
  
=== Example ===
+
<math>x^5y^1+y^5x^1\geq x^4y^2+y^4x^2</math>.
  
The inequality is easier to understand given an example. Since the sequence <math>(5,1)</math> majorizes <math>(4,2)</math>, Muirhead's inequality states that for any positive <math>x,y</math>,
+
==Proof==
 +
We will first prove an important fact. If we have a sequence <math>C</math> such that <math>\sum_{i=1}^{n} c_i = 0</math>, then the following result holds:
 +
<cmath>\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\geq n!</cmath>
 +
for any positive reals <math>x_1, x_2, ..., x_n</math>.
  
<math>x^5y^1+y^5x^1\geq x^4y^2+y^4x^2</math>
+
Proof: By AM-GM, we know:
 +
<cmath>\frac{\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}}{n!}\geq \sqrt[n!]{\prod_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}}</cmath>
  
=== Usage on Olympiad Problems ===
+
However, expanding the right hand side, we see
 +
<cmath>\sqrt[n!]{\prod_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{cn}}=\sqrt[n!]{\prod_{i=1}^{n} x_i^{(n-1)!\left(c_1+c_2+\cdots +c_n\right)}}=1</cmath>
 +
or
 +
<cmath>\frac{\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}}{n!}\geq 1 \Rightarrow \sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\geq n!</cmath>
  
 +
We define our sequence <math>C</math> such that
 +
<cmath>c_i=a_i-b_i \hspace{1cm} \forall \hspace{2mm}1\leq i\leq n</cmath>
 +
 +
Note that
 +
<cmath>\sum_{i=1}^{n} c_i = \sum_{i=1}^{n} a_i-b_i=\sum_{i=1}^{n} a_i - \sum_{i=1}^{n} b_i=0</cmath>
 +
 +
Therefore, we get that
 +
<cmath>\sum_{\text{sym}}\left({x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\right) -n!\geq 0</cmath>
 +
 +
We multiply this by <math>\sum_{\text{sym}} \prod_{i=1}^{n}x_i^{b_i}</math> to get:
 +
<cmath>\left(\sum_{\text{sym}} \prod_{i=1}^{n}x_i^{b_i}\right)\left(\sum_{\text{sym}}\left({x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}-1\right)\right)=\sum_{\text{sym}} \prod_{i=1}^{n} x_i^{b_i+c_i}-\prod_{i=1}^{n} x_i^{b_i}\geq 0</cmath>
 +
 +
Since <math>b_i+c_i=b_i+a_i-b_i=a_i</math>, we get
 +
<cmath>\sum_{\text{sym}} \prod_{i=1}^{n} x_i^{a_i}-\prod_{i=1}^{n} x_i^{b_i}\geq 0</cmath>
 +
or
 +
<cmath>\sum_{\text{sym}} {x_1}^{a_1}{x_2}^{a_2}\cdots {x_n}^{a_n}\geq \sum_{\text{sym}} {x_1}^{b_1}{x_2}^{b_2}\cdots {x_n}^{b_n}</cmath>
 +
 +
== Usage on Olympiad Problems ==
 
A common [[Brute forcing|bruteforce]] technique with inequalities is to clear denominators, multiply everything out, and apply Muirhead's or [[Schur's Inequality|Schur'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 | Arithmetic Mean-Geometric Mean]] inequality.  In fact, [[International Mathematics Olympiad | IMO]] gold medalist [[Thomas Mildorf]] says it is unwise to use Muirhead in an Olympiad solution; one should use an application of AM-GM instead.  Thus, it is suggested that Muirhead be used only to verify that an inequality ''can'' be proved with AM-GM before demonstrating the full AM-GM proof.
 
A common [[Brute forcing|bruteforce]] technique with inequalities is to clear denominators, multiply everything out, and apply Muirhead's or [[Schur's Inequality|Schur'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 | Arithmetic Mean-Geometric Mean]] inequality.  In fact, [[International Mathematics Olympiad | IMO]] gold medalist [[Thomas Mildorf]] says it is unwise to use Muirhead in an Olympiad solution; one should use an application of AM-GM instead.  Thus, it is suggested that Muirhead be used only to verify that an inequality ''can'' be proved with AM-GM before demonstrating the full AM-GM proof.
  
Line 21: Line 48:
 
Adding these,
 
Adding these,
  
<math>x^4+y^4\geq x^3y+xy^3</math>
+
<math>x^4+y^4\geq x^3y+xy^3</math>.
  
 
Multiplying both sides by <math>xy</math> (as both <math>x</math> and <math>y</math> are positive),
 
Multiplying both sides by <math>xy</math> (as both <math>x</math> and <math>y</math> are positive),
Line 30: Line 57:
  
 
[[Category:Inequality]]
 
[[Category:Inequality]]
[[Category:Number Theory]]
+
[[Category:Theorems]]

Latest revision as of 01:14, 4 January 2020

Muirhead's Inequality states that if a sequence $A$ majorizes a sequence $B$, then given a set of positive reals $x_1,x_2,\cdots,x_n$: \[\sum_{\text{sym}} {x_1}^{a_1}{x_2}^{a_2}\cdots {x_n}^{a_n}\geq \sum_{\text{sym}} {x_1}^{b_1}{x_2}^{b_2}\cdots {x_n}^{b_n}\]

Example

The inequality is easier to understand given an example. Since the sequence $(5,1)$ majorizes $(4,2)$ (as $5>4, 5+1=4+2$), Muirhead's inequality states that for any positive $x,y$,

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

Proof

We will first prove an important fact. If we have a sequence $C$ such that $\sum_{i=1}^{n} c_i = 0$, then the following result holds: \[\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\geq n!\] for any positive reals $x_1, x_2, ..., x_n$.

Proof: By AM-GM, we know: \[\frac{\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}}{n!}\geq \sqrt[n!]{\prod_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}}\]

However, expanding the right hand side, we see \[\sqrt[n!]{\prod_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{cn}}=\sqrt[n!]{\prod_{i=1}^{n} x_i^{(n-1)!\left(c_1+c_2+\cdots +c_n\right)}}=1\] or \[\frac{\sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}}{n!}\geq 1 \Rightarrow \sum_{\text{sym}}{x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\geq n!\]

We define our sequence $C$ such that \[c_i=a_i-b_i \hspace{1cm} \forall \hspace{2mm}1\leq i\leq n\]

Note that \[\sum_{i=1}^{n} c_i = \sum_{i=1}^{n} a_i-b_i=\sum_{i=1}^{n} a_i - \sum_{i=1}^{n} b_i=0\]

Therefore, we get that \[\sum_{\text{sym}}\left({x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}\right) -n!\geq 0\]

We multiply this by $\sum_{\text{sym}} \prod_{i=1}^{n}x_i^{b_i}$ to get: \[\left(\sum_{\text{sym}} \prod_{i=1}^{n}x_i^{b_i}\right)\left(\sum_{\text{sym}}\left({x_1}^{c_1}{x_2}^{c_2}\cdots {x_n}^{c_n}-1\right)\right)=\sum_{\text{sym}} \prod_{i=1}^{n} x_i^{b_i+c_i}-\prod_{i=1}^{n} x_i^{b_i}\geq 0\]

Since $b_i+c_i=b_i+a_i-b_i=a_i$, we get \[\sum_{\text{sym}} \prod_{i=1}^{n} x_i^{a_i}-\prod_{i=1}^{n} x_i^{b_i}\geq 0\] or \[\sum_{\text{sym}} {x_1}^{a_1}{x_2}^{a_2}\cdots {x_n}^{a_n}\geq \sum_{\text{sym}} {x_1}^{b_1}{x_2}^{b_2}\cdots {x_n}^{b_n}\]

Usage on Olympiad Problems

A common bruteforce technique with inequalities is to clear denominators, multiply everything out, and apply Muirhead's or Schur'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; one should use an application of AM-GM instead. Thus, it is suggested that Muirhead be used only to verify that an inequality can be proved with AM-GM before demonstrating the full AM-GM proof.

As an example, the above inequality can be proved using AM-GM as follows:

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

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

Adding these,

$x^4+y^4\geq x^3y+xy^3$.

Multiplying both sides by $xy$ (as both $x$ and $y$ are positive),

$x^5y+xy^5\geq x^4y^2+x^2y^4$

as desired.

Invalid username
Login to AoPS