■因数分解の算法(その14)

 (その11)では,算術平均A(a^n)と幾何平均G(a^n)についてのフルヴィッツ・ムーアヘッドの等式

  n{A(a^n)−G(a^n)}

 =1/2(n−1)!{Σ(a1^(n-1)−a2^(n-1))(a1−a2)+Σ(a1^(n-2)−a2^(n-2))(a1−a2)a3+Σ(a1^(n-3)−a2^(n-3))(a1−a2)a3a4+・・・}

を紹介した.右辺はa1,a2,・・・,anを置換して得られる値の総和である.

 また,このことから算術平均と幾何平均の大小関係についての有名な不等式

  A(a^n)≧G(a^n)

の別証明が得られる.

  Σ(a1^(n-1)−a2^(n-1))(a1−a2)+Σ(a1^(n-2)−a2^(n-2))(a1−a2)a3+Σ(a1^(n-3)−a2^(n-3))(a1−a2)a3a4+・・・

 =ΣP1(a1−a2)^2+ΣP2(a1−a2)^2+ΣP3(a1−a2)^2+・・・

 =Σ(P1+P2+P3+・・・)(a1−a2)^2

 =ΣP0(a1−a2)^2≧0

 このように2次式の和の形ΣkP^2が出現するのだが,さらに,

  a1=x1^2,a2=x2^2,・・・

とおくと,

  (a1^(n-1)−a2^(n-1))(a1−a2)

 =(x1^2(n-1)−x2^2(n-1))(x1^2−x2^2)

 =(x1^2−x2^2)^2(x1^2(n-2)+x1^2(n-3)x2^2+・・・+x2^2(n-2))

となり,各項が(x1^2−x2^2)x1^(n-2)の平方の形の多項式となっていることがわかる.このことから,多項式P1,P2,・・・それ自体も平方の和となることが理解される.

 そのことを具体的に書いてみると

  (a^2+b^2)/2−ab=1/2(a−b)^2≧0

  (a^6+b^6+c^6)/3−a^2b^2c^2=1/6(a^2+b^2+c^2){(a^2−b^2)^2+(b^2−c^2)^2+(c^2−a^2)^2}≧0

である.右辺が平方式の和に書き直せるので非負になることは明らかであろう.今回のコラムでは(その11)を補足補完しておきたい.

===================================

【1】ヒルベルトの定理

 フルヴィッツ・ムーアヘッドの等式により,

  a1^n+a2^n+・・・+an^n−na1a2・・・an

を各項が非負値の和として表すことができることがわかっているが,特に2n次のとき,

  F=x1^2n+x2^2n+・・・+x2n^2n−2nx1x2・・・x2n

   =x1^2n+・・・+xn^2n−nx1^2・・・xn^2

   +xn+1^2n+・・・+x2n^2n−nxn+1^2・・・x2n^2

   +n(x1・・・xn−xn+1・・・x2n)^2

より,

  F=ΣPi^2≧0

を示すことができる.

 この定理は,

  a^4+b^4+c^4+d^4-4abcd

  a^6+b^6+c^6+d^6+e^6+f^6-6abcdef

が多項式の平方の和となることを保証するものである.たとえば,

  x^4+y^4+z^4+w^4−4xyzw

 =(x^2−y^2)^2+(z^2−w^2)^2+2(xy−zw)^2

は3個の多項式の平方の和である.

 また,

  x^6+y^6+z^6+u^6+v^6+w^6−6xyzuvw

 =1/2(x^2+y^2+z^2){(y^2−z^2)^2+(z^2−x^2)^2+(x^2−y^2)^2}+1/2(u^2+v^2+w^2){(v^2−w^2)^2+(w^2−u^2)^2+(u^2−v^2)^2}+3(xyz−uvw)^2

は19個の多項式の平方の和である.

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

 ヒルベルトは,多項式の不等式は必ず平方式の和として表されるという予想をたてた.そして,どのようなFがいくつかの多項式Piを用いて

  F=ΣPi^2≧0

と表されるかという問題の証明を試みたのであるが,基本的には正しいものの当初予想されたような完全な完全な形での成立は不可能であることがわかった.

 最終的には,Fの次数を2nとし,変数の数をmとした場合,

  (1)m=2,nは任意

  (2)mは任意,2n=2

  (3)m=3,2n=4

は実数係数2次形式の和で表されるが,これ以外のものについては表されないものが存在するという結論である.

===================================

【2】ムーアヘッド平均(算術平均と幾何平均の一般化)

 たとえば,算術平均・幾何平均の不等式

  (a^3+b^3+c^3)/3≧abc

の左辺も右辺も

  (a^xb^yc^z+a^xb^zc^y+a^yb^zc^x+a^yb^xc^z+a^zb^xc^y+a^zb^yc^x)/6

の特別な場合になっていることに気づかされるであろう.

 x≧y≧z≧0として(x,y,z)を指標と呼ぶことにするが,左辺は指標(x,y,z)=(3,0,0),右辺は指標(x,y,z)=(1,1,1)である.また,いずれにおいてもx+y+z=3という条件が満たされている.

 不等式

  (a^3+b^3+c^3)/3≧abc

  M(3,0,0)≧M(1,1,1)

と書くことにするが,M(x,y,z)をムーアヘッド平均と呼ぶことにする.ムーアヘッド平均は算術平均と幾何平均の一般化である.

 次に

  M(2,1,0)=(a^2b+a^2c+ac^2+ab^2+b^2c+bc^2)/6

について考えてみるが,実は

  M(3,0,0)≧M(2,1,0)≧M(1,1,1)

が成立する.そして,このことから

  M(3,0,0)≧M(1,1,1)

よりも

  M(3,0,0)≧M(2,1,0),

  M(2,1,0)≧M(1,1,1)

の方が本質的な性質であることがわかる.

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

 さらに

  M(x,y,z)≧M(u,v,w)

が成り立つための必要十分条件は,指標

  (x,y,z)>(u,v,w)

が成り立つことである(ム−アヘッドの定理).

 指標(x,y,z)>(u,v,w)の意味については次節で説明することにするが,ムーアヘッド平均に関する不等式は,算術平均・幾何平均の不等式の一般化であり,対応する指標に関する不等式に帰着されるのである.(ム−アヘッドの定理の条件の必要性の証明はわかるが,十分性の証明は込み入っている).

===================================

【3】分割とムーアヘッドの定理

 非負整数の非増加列,すなわち,

  λ=(λ1,λ2,・・・,λn)

  λ1≧λ2≧・・・≧λn>0

なる整数列を分割(partition)という.

 ここでは

  λ1≧λ2≧・・・≧λn≧0,n=3

の場合を扱うことになるので注意してほしい.(≧−1とすることができれば調和平均も扱えるのだが,・・・)

 分割はλ=(λ1,λ2,・・・,λn)でパラメトライズされるわけであるが,分割λに対して

  |λ|=Σλi

を分割λのサイズ,λiが零でないiの総数をl(λ)と書いて分割λの長さという.前節の例でいえばx+y+z=3が分割のサイズである.

 変数の数が3の場合,サイズ1の分割の集合は

  S1={(1,0,0)}

サイズ2の分割の集合は

  S2={(2,0,0),(1,1,0)}

サイズ3の分割の集合は

  S3={(3,0,0),(2,1,0),(1,1,1)}

である.

 分割の集合を求めるのは難しいことではなく,たとえば,変数の数が3の場合,サイズ6の分割の集合は

  S6={(6,0,0),(5,1,0),(4,2,0),(4,1,1),(3,3,0),(3,2,1),(2,2,2)}

サイズ7の分割の集合は

  S7={(7,0,0),(6,1,0),(5,2,0),(5,1,1),(4,3,0),(4,2,1),(3,3,1),(3,2,2)}

サイズ8の分割の集合は

  S8={(8,0,0),(7,1,0),(6,2,0),(6,1,1),(5,3,0),(5,2,1),(4,4,0),(4,3,1),(4,2,2),(3,3,2)}

となる.

 次に,分割の集合に自然な順序を定義したい.λ≧μとは

  |λ|=|μ|

かつすべてのiに対して

  λ1+・・・+λi≧μ1+・・・+μi

が成り立つこととする(i=1〜n).

 すると

  (2)>(1^2)

  (3)>(21)>(1^3)

  (4)>(31)>(2^2)>(21^2)>(1^4)

  (5)>(41)>(32)>(31^2)>(2^21)>(21^3)>(1^5)

  (6)>(51)>(42)>(41^2)>(321)>(31^3)>(2^21^2)>(21^4)>(1^6)

   >(3^2)> >(2^3)>

となって|λ|≦5の場合には全順序(辞書式順序)であるが,|λ|≧6の場合は半順序となることが理解される.(λ1≧λ2≧・・・≧λn≧0として,(λ1,λ2,・・・,λn)のことを(λ1λ2・・・λn),(1111)のことを(1^4)と表している.)

 3変数の場合に限ると,

  (2)>(1^2)

  (3)>(21)>(1^3)

  (4)>(31)>(2^2)>(21^2)

  (5)>(41)>(32)>(31^2)>(2^21)

  (6)>(51)>(42)>(41^2)>(321)>(2^3)

   >(3^2)>

となって,指標(4,1,1)と(3,3,0)の間には大小関係がないということになる.

 3変数6次多項式

  a^4bc+abc^4+ab^4c

  a^3b^3+a^3c^3+b^3c^3

については大小関係が成立しないものが存在するのである.

===================================

【4】モノミアル対称多項式(基本対称式の一般化)

 分割λに対応する単項対称多項式(モノミアル対称多項式)を

  mλ(x)=Σx1^α1x2^α2・・・xn^αn

により定義する.ただし,この和はλ=(λ1,λ2,・・・,λn)の入れ替えで生じる単項式すべてを動くものとする.すなわち,単項対称多項式は単項式x1^α1・・・xn^αnの線形結合をとって得られる対称化多項式である.

 |λ|=3,n=3とすれば

  m(3)(x)=x1^3+x2^3+x3^3

  m(21)(x)=x1^2x2+x1^2x3+x2^2x1+x2^2x3+x3^2x1+x3^2x2

  m(1^3)(x)=x1x2x3

 また,ベキ和対称関数をr次のベキ和

  pr=Σx^r=m(r)(x)

と分割λ=(λ1,λ2,・・・)に対して

  pλ=pλ1pλ2・・・=Πpλi

と定義すると,n=3の場合,

  p(3)(x)=x1^3+x2^3+x3^3

  p(21)(x)=(x1^2+x2^2+x3^2)(x1+x2+x3)

  p(1^3)(x)=(x1+x2+x3)^3

のようになる.

 さらに,ヤング図形の縦1列に対応する場合がr次の基本対称式

  er(x)=σr=m(1^r)

ヤング図形の横1列に対応する場合がr次の完全(同次)対称多項式

  hr(x)=Σmλ(x)   |λ|=r

であるが,eλ(x),hλ(x)についてもベキ和対称多項式の場合と同様に定義する.

===================================

【補】凸関数の応用

 上に凸な関数では,不等式

  φ((a1+a2+・・・+an)/n)≧(φ(a1)+φ(a2)+・・・+φ(an))/n

が成立する.このことからφ(x)=logxとおくと,算術平均・幾何平均の不等式は容易に証明される.

 また,不等式

  f(x)=exp(x)-x-1≧0

  g(x)=x^n-nx+(n-1)≧0

などを使っても算術平均・幾何平均の不等式を示すことができる.

===================================