Karamataの不等式

Karamataの不等式
  • [a][b][a]\succeq [b] を満たす実数の列 a=(a1,a2,,an),b=(b1,b2,,bn)a=(a_1, a_2,\cdots , a_n), b=(b_1, b_2,\cdots, b_n)
  • f(x)f(x) は微分可能で凸

このとき, f(a1)+f(a2)++f(an)f(b1)+f(b2)++f(bn)f(a_1)+f(a_2)+\cdots +f(a_n)\geq f(b_1)+f(b_2)+\cdots +f(b_n) である。

Karamataの不等式の意味・応用例・証明を解説します。

Karamataの不等式の意味

まず,[a][b][a]\succeq [b] というのは 「2つの数列の全体の和が等しく,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 が成立することを表す。

この記号に不慣れな方はMuirheadの不等式と具体例を参考にしてください。

次に,ff が凸というのは様々な定義がありますが,「下に出っ張っている」というイメージです。凸関数について知らない方はイェンゼンの不等式の3通りの証明を参考にしてください。

以上を合わせると,Karamataの不等式は「凸関数においては,xx 座標が偏っている図形の重心の方がより上に来る」と解釈できます。 karamataの不等式のイメージ

例えば n=2n=2 の場合,図において青丸の方が赤丸より上にあるということを表しています。直感的にはイメージしやすいですね。

Karamataの不等式の応用例

1996年のアジア太平洋数学オリンピック(APMO)の問題です。ルートの和とシュワルツの不等式でも紹介した問題です。Ravi変換を用いるのが定石ですがKaramataの不等式を用いることでエレガントに証明します。

問題

a,b,ca,b,c が三角形の辺の長さのとき以下の不等式を証明せよ:

a+bc+b+ca+c+aba+b+c\sqrt{a+b-c}+\sqrt{b+c-a}+\sqrt{c+a-b} \leq \sqrt{a}+\sqrt{b}+\sqrt{c}

方針

f(A1)+f(A2)+f(A3)f(B1)+f(B2)+f(B3)f(A_1)+f(A_2)+f(A_3) \leq f(B_1)+f(B_2)+f(B_3) という形をしており,いかにもKaramataです。 x\sqrt{x} は上に凸な関数なので x-\sqrt{x} を考えることで強引に凸関数にします。

解答

対称式なので abca\geq b\geq c の場合を証明すればよい。

  • 簡単な計算により,
    (a+bc,c+ab,b+ca)(a,b,c)(a+b-c,c+a-b,b+c-a)\succeq (a,b,c)

  • f(x)=xf(x)=-\sqrt{x} とおくと f(x)=12xf'(x)=\dfrac{-1}{2\sqrt{x}} が増加関数なので f(x)f(x) は凸関数。

以上からKaramataの不等式が使える。

a+bcb+cac+ababc -\sqrt{a+b-c}-\sqrt{b+c-a}-\sqrt{c+a-b} \geq -\sqrt{a}-\sqrt{b}-\sqrt{c}

両辺を 1-1 倍して目標の式を得る。

Karamataの不等式のおもしろい応用例として,Popoviciu の不等式の証明もあります。

Karamataの不等式の証明

アーベルの総和公式を用います。→アーベルの総和公式とその解釈

証明

f(x)f(x) は凸関数なので,傾き ck=f(bk)f(ak)bkakc_k=\dfrac{f(b_k)-f(a_k)}{b_k-a_k} は減少数列となる(bk=akb_k=a_k の場合は微分係数 f(ak)f'(a_k)ckc_k とおく)。

すると,アーベルの総和公式が使えて,

k=1n(f(ak)f(bk))=k=1nck(akbk)=cn(AnBn)+k=1n1(ckck+1)(AkBk)0\begin{aligned} &\sum_{k=1}^n(f(a_k)-f(b_k))\\ &=\sum_{k=1}^nc_k(a_k-b_k)\\ &=c_n(A_n-B_n)+ \sum_{k=1}^{n-1} (c_k-c_{k+1}) (A_k-B_k)\geq 0 \end{aligned}

ただし,A,BA,B は数列 a,ba,b の部分和を表し,[a][b][a]\succeq [b] より AkBk0A_k-B_k\geq 0 であることを用いた。

Karamataはイェンゼンと同じく図形的にイメージしやすい不等式です。

Tag:各地の数オリの過去問