2014/03/05

Muirheadの不等式と具体例

分野: 不等式  レベル: 数学オリンピック

Muirheadの不等式:
各成分が非負で非増加な数列 $a=(a_1, a_2,\cdots , a_n), b=(b_1, b_2,\cdots, b_n)$ と,任意の非負実数 $x_1, x_2, \cdots, x_n$ に対して,$[a]\succeq [b]$ ならば
$\displaystyle\sum_{sym}\prod_{i=1}^nx_i^{a_i}\geq\displaystyle\sum_{sym}\prod_{i=1}^nx_i^{b_i}\\$
等号成立条件は,$a=b$ または, $x_1=x_2=\cdots=x_n$

この不等式は一見抽象的で意味不明ですが,具体的に書いてみればなんてことありません。要するに,「対称式ならベキが偏っている方が大きい」ということです。

$\displaystyle\sum_{sym}$ とか,$[a]\succeq[b]$ とかの記号の意味を説明しなくてはいけませんが,細かいことは後回しにしてとりあえずは具体例から入ってMuirheadの不等式の威力を実感してみてください。

Muirheadの不等式の具体例

$x ,y, z$ が非負のとき以下ように対称斉次な不等式を次々と生み出すことが出来ます!

・ $n=2, a=[2,0], b=[1,1]$ :
$x^2+y^2\geq 2xy$

・ $n=2, a=[4,0], b=[3,1]$ :
$x^4+y^4\geq x^3y+y^3x$

・ $n=3, a=[2,0,0], b=[1,1,0]$ :
$x^2+y^2+z^2\geq xy+yz+zx$

・ $n=3, a=[2,1,0], b=[1,1,1]$ :
$x^2y+xy^2+y^2z+yz^2+z^2x+zx^2\geq 6xyz$

・ $n=3, a=[2,0,0], b=[\tfrac{4}{3},\tfrac{1}{3},\tfrac{1}{3}]$ :
$x^2+y^2+z^2\geq x^{\tfrac{4}{3}}y^{\tfrac{1}{3}}z^{\tfrac{1}{3}}+x^{\tfrac{1}{3}}y^{\tfrac{4}{3}}z^{\tfrac{1}{3}}+x^{\tfrac{1}{3}}y^{\tfrac{1}{3}}z^{\tfrac{4}{3}}$

いずれの不等式も,相加相乗平均の不等式(場合によっては重み付き相加相乗平均の不等式)を用いて頑張れば示すことができますが,Muirheadの不等式を知っていると対称斉次の不等式証明問題の見通しが非常によくなります。
数学オリンピックでは「Muirheadの不等式より」と書いてよいでしょうが,大学入試の記述式問題では相加相乗平均の不等式を用いて証明した方が無難です。

以下ではMuirheadの不等式の意味を説明します。

Muirheadの不等式の意味1(和の記号)

$\displaystyle\sum_{sym}$ とは「文字を入れ替えて全組み合わせ足し合わせる」という意味です。足しあわせた結果は必ず対称式になります。

例えば3変数の場合,

$\displaystyle\sum_{sym}f(x,y,z)=f(x,y,z)+f(x,z,y)+f(y,x,z)+f(y,z,x)+f(z,x,y)+f(z,y,x)$
$\displaystyle\sum_{sym}x^2y=x^2y+x^2z+y^2x+y^2z+z^2x+z^2y$
$\displaystyle\sum_{sym}xy=xy+xz+yx+yz+zx+zy=2(xy+yz+zx)$
$\displaystyle\sum_{sym}xyz=xyz+xzy+yxz+yzx+zxy+zyx=6xyz$

最左辺から最右辺,及び最右辺から最左辺が一瞬でイメージできるように慣れましょう。

Muirheadの不等式の意味2(偏っている方が強い)

次に,$[a]\succeq[b]$ について説明します。 $a$ は $b$ よりも優数列である,”a majorizes b”などと言います。これは大雑把にいうと,$a$ の方が $b$ より偏っている,という意味を表します。

厳密な定義は以下の通りです:

項数が等しい非増加な数列 $a, b$ に対して $[a]\succeq[b]$ とは,
$\displaystyle\sum_{i=1}^{k}a_i\geq\sum_{i=1}^{k}b_i\:\:(k=1, 2, \cdots, n-1)$ かつ
$\displaystyle\sum_{i=1}^{n}a_i=\sum_{i=1}^{n}b_i$
が成立することを表す。

例えば $2\geq 1$ かつ $2+0=1+1$ なので,$[2,0]\succeq[1,1]$ です。

この記号を理解した上でもう一度上の具体例を確認してみてください!

Muirheadの不等式の証明の概略

証明の手順(概略)
1、 $[a]\succeq[b]$ なら二重確率行列 $P$ が存在して $b=Pa$ と書けることを示す。(有名な定理らしいです)
2、二重確率行列は置換行列の凸結合で表すことができる。(Birkhoff von Neumannの定理)
3、重み付き相加相乗平均の不等式を用いて計算する

厳密にやるには結構難しいみたいです。
Muirheadの不等式の厳密な証明はこちら(英語です)


Tag: 数学オリンピック突破のための有名不等式まとめ

分野: 不等式  レベル: 数学オリンピック