Muirheadの不等式と具体例

Muirheadの不等式

各成分が非負で非増加な数列 a=(a1,a2,,an),b=(b1,b2,,bn)a=(a_1, a_2,\cdots , a_n), b=(b_1, b_2,\cdots, b_n) と,任意の非負実数 x1,x2,,xnx_1, x_2, \cdots, x_n に対して,[a][b][a]\succeq [b] ならば symi=1nxiaisymi=1nxibi \sum_{sym}\prod_{i=1}^nx_i^{a_i} \geq \sum_{sym}\prod_{i=1}^nx_i^{b_i} が成立する。等号成立条件は,a=ba=b または, x1=x2==xnx_1=x_2=\cdots=x_n である。

見た目は非常に複雑な不等式ですが,後述する具体的を見ればたいしたことはありません!

Muirheadの不等式の具体例

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

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

  • n=2,a=[2,0],b=[1,1]n=2, a=[2,0], b=[1,1] とすると
    x2+y22xyx^2+y^2\geq 2xy

  • n=2,a=[4,0],b=[3,1]n=2, a=[4,0], b=[3,1] とすると
    x4+y4x3y+y3xx^4+y^4\geq x^3y+y^3x

  • n=3,a=[2,0,0],b=[1,1,0]n=3, a=[2,0,0], b=[1,1,0] とすると
    x2+y2+z2xy+yz+zxx^2+y^2+z^2\geq xy+yz+zx

  • n=3,a=[2,1,0],b=[1,1,1]n=3, a=[2,1,0], b=[1,1,1] とすると
    x2y+xy2+y2z+yz2+z2x+zx26xyzx^2y+xy^2+y^2z+yz^2+z^2x+zx^2\geq 6xyz

  • n=3,a=[2,0,0],b=[43,13,13]n=3, a=[2,0,0], b=[\tfrac{4}{3},\tfrac{1}{3},\tfrac{1}{3}] とすると
    x2+y2+z2x43y13z13+x13y43z13+x13y13z43x^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の不等式の意味1(和の記号)

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

例えば,3変数の場合,

symf(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)\begin{aligned} &\sum_{\mathrm{sym}}f(x,y,z)\\ &\quad\quad=f(x,y,z)+f(x,z,y)+f(y,x,z)+f(y,z,x)+f(z,x,y)+f(z,y,x) \end{aligned}

です。

symx2y=x2y+x2z+y2x+y2z+z2x+z2y\displaystyle\sum_{\mathrm{sym}}x^2y=x^2y+x^2z+y^2x+y^2z+z^2x+z^2y

symxy=xy+xz+yx+yz+zx+zy=2(xy+yz+zx)\displaystyle\sum_{\mathrm{sym}}xy=xy+xz+yx+yz+zx+zy=2(xy+yz+zx)

symxyz=xyz+xzy+yxz+yzx+zxy+zyx=6xyz\displaystyle\sum_{\mathrm{sym}}xyz=xyz+xzy+yxz+yzx+zxy+zyx=6xyz

最左辺から最右辺,および最右辺から最左辺が素早くイメージできるように慣れましょう。

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

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

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

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

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

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

Muirheadの不等式の証明の概略

証明の手順(概略)

  1. [a][b][a]\succeq[b] なら二重確率行列 PP が存在して b=Pab=Pa と書けることを示す。(有名な定理らしいです)

  2. 二重確率行列は置換行列の凸結合で表すことができる。→バーコフ–フォン・ノイマンの定理

  3. 重み付き相加相乗平均の不等式を用いて計算する

厳密な証明は結構難しいようです。Muirheadの不等式の厳密な証明はこちら(英語です)

Muirheadの不等式と相加相乗平均の不等式

Muirheadの不等式から相加相乗平均の不等式を導けます!

n=3の場合の例

n=3,a=[1,0,0],b=[13,13,13]n=3,a=[1,0,0],b=\left[\dfrac{1}{3},\dfrac{1}{3},\dfrac{1}{3}\right] とすると, 2(x+y+z)6xyz32(x+y+z)\geq 6\sqrt[3]{xyz} つまり x+y+z3xyz3\dfrac{x+y+z}{3}\geq\sqrt[3]{xyz} である。

同様に,一般の nn に対しても a=[1,0,,0],b=[1n,1n,,1n]a=[1,0,\dots,0],b=\left[\dfrac{1}{n},\dfrac{1}{n},\dots,\dfrac{1}{n}\right] とすると相加相乗平均の不等式になります。

ただし,これを「相加相乗平均の不等式の証明」と呼ぶのは良くないです(Muirheadの不等式の証明には,相加相乗平均の不等式を使うので循環論法になります)。

要するに「対称式ならベキが偏っている方が大きい」ということです。

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