ニュートンの恒等式

提供: testwiki
2024年7月13日 (土) 15:18時点におけるimported>Anakabotによる版 (Bot作業依頼#Cite conferenceのbooktitle引数の移行)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

ニュートンの恒等式テンプレート:Lang-en-short)、ジラール-ニュートンの公式テンプレート:Lang-en-short)は、べき乗和と基本対称式との関係を与える。この関係は、単行多項式Pの根が与えられたとき、それらのk乗の和が、根を明示的に求めなくても、Pの係数によって表されることを意味する。この恒等式は1666年にアイザック・ニュートンによって発見された。実際にはこの式はこれよりも前に、アルベルト・ジラールにより発見されている(1629)。この恒等式はガロア理論、不変式論、群論組み合わせ論を含む数学の多くの分野での応用や、一般相対性理論を含む数学以外のさらなる応用をもつ。

定義

対称多項式による定式化

x1,...,xnを変数とし、 k ≥1について pk(x1,...,xn )を k次のべき乗和:

pk(x1,,xn)=i=1nxik=x1k++xnk,

とする。そして、k ≥ 0 について ek(x1,...,xn )をk次の基本対称式とする。これはk個の相異なる変数の関の和である。

e0(x1,,xn)=1,e1(x1,,xn)=x1+x2++xn,e2(x1,,xn)=1i<jnxixj,en(x1,,xn)=x1x2xn,ek(x1,,xn)=0,for k>n.

このとき、ニュートンの恒等式は次のように述べることができる:

kek(x1,,xn)=i=1k(1)i1eki(x1,,xn)pi(x1,,xn)

この式はすべての n ≥1とn≥K≥1について有効である。

また、

0=i=knk(1)i1eki(x1,,xn)pi(x1,,xn),

この式はすべてのk >> n ≥ 1について成り立つ

具体的には以下のようになる。

e1(x1,,xn)=p1(x1,,xn),2e2(x1,,xn)=e1(x1,,xn)p1(x1,,xn)p2(x1,,xn),3e3(x1,,xn)=e2(x1,,xn)p1(x1,,xn)e1(x1,,xn)p2(x1,,xn)+p3(x1,,xn).

これらの等式は変数の数nに依存しない。(ただし、左辺が0になる位置は変数に依存する)

e1=p1,2e2=e1p1p2=p12p2,3e3=e2p1e1p2+p3=12p1332p1p2+p3,4e4=e3p1e2p2+e1p3p4=16p14p12p2+43p1p3+12p22p4,

これらの方程式により、eiをpkにより表すことができる。また逆に

p1=e1,p2=e1p12e2=e122e2,p3=e1p2e2p1+3e3=e133e1e2+3e3,p4=e1p3e2p2+e3p14e4=e144e12e2+4e1e3+2e224e4,  

もなりたつ。一般に

pk(x1,,xn)=(1)k1kek(x1,,xn)+i=1k1(1)k1+ieki(x1,,xn)pi(x1,,xn)

がすべてのn≥1とn≥K≥1について成り立つ。

pk(x1,,xn)=i=knk1(1)k1+ieki(x1,,xn)pi(x1,,xn)

k > n ≥ 1について成り立つ。

多項式の根への適用

xi根を持つ多項式は、以下のように展開できる。

i=1n(xxi)=k=0n(1)kekxnk,

ここで、ek(x1,,xn) は上で定義された対称多項式である。根のべき和を考えると

pk(x1,,xn)=i=1nxik

x1,,xnを根に持つ多項式の係数はべき和により次のように表すことができる。

e0=1,e1=p1,e2=12(e1p1p2),e3=13(e2p1e1p2+p3),e4=14(e3p1e2p2+e1p3p4),  

この方法で多項式を定式化すると、Delves や Lyness [1]の方法により解析関数の零点を見つけるのに役立つ。

行列の特性多項式への適用

上記の多項式が行列Aの特性多項式である場合(特にAが多項式の同伴行列である場合)、根 xiは行列の固有値となる。また、任意の正の整数kに対して、行列 Akは固有値 xikを持ち、これらの和はAkトレース

pk=tr(Ak).

により表される。ニュートンの恒等式によりこれらから基本対称式が求まるため、Aの特性多項式の係数をAkのトレースを計算することにより求めることができる。

この計算では、行列のべき乗Akのトレースの計算と、ニュートンの恒等式を解く際に三角化された連立方程式を解く必要がある。これらの計算はどちらも複雑度クラスNCで実行できる。したがって、行列の特性多項式はNCで計算できる。ケイリー・ハミルトンの定理により、すべての行列はその特性多項式を満たし、単純な変換により、NCで余因子行列を見つけることができる。

計算を効率的な形式に再配置すると、ファデーエフ・ルベリエアルゴリズム(1840)が得られる。これの高速並列実装は、L. Csanky(1976)により得られた。この方式の欠点は、整数による除算が必要なことである。したがって、群の標数は0である必要がある。

ガロア理論との関係

与えられたn、k=1,...,n について初等対称多項式 ek(x1,...,xn) はxi に関する対象式の代数的基底を形成する。xi のすべての置換について不変な多項式は基本対称式により表される。これは対称多項式の基本定理として知られている一般的な事実であり、ニュートンの恒等式はべき和対称多項式について明示的な関係を示しいる。

単項多項式 tn+k=1n(1)kaktnk にこれを適用すれば、この多項式の根についての対称式S(x1,...,xn)は、係数を用いた多項式P(a1,...,an)により表せることがわかる。このことはガロア理論の一般的結果である。

ニュートンの恒等式は、基本対称多項式をべき和対称多項式で表現することを可能にする。これは、任意の対称多項式がべき和で表現できることを示している。

関連する恒等式

ニュートンの恒等式に関連する恒等式がいくつかある。

完全斉次対称式を使用した変形

次数 k単項式の和である完全斉次対称式 hkについても、ニュートン恒等式と同様に以下の恒等式が存在する。ニュートン恒等式とは異なり、マイナスの符号が現れない。

khk=i=1khkipi,

この式はすべてのn≥k≥1に対し成り立つ。ニュートンの公式とは異なり、左辺は大きなkに対して0にはならない。また、左辺には多くのゼロ項が含まれている。右側には、これまで以上にゼロ以外の項が含まれています。具体的には以下のようになる。

h1=p1,2h2=h1p1+p2,3h3=h2p1+h1p2+p3.

これらの関係は、以下のような母関数の恒等式の係数を比較することで確認できる。

k=0hk(X1,,Xn)tk=i=1n11Xit.

べき和による基本対称多項式を表現

前述のように、ニュートンの公式を使用して、べき和により基本対称多項式を再帰的に表現できる。

e1=p1,e2=12p1212p2=12(p12p2),e3=16p1312p1p2+13p3=16(p133p1p2+2p3),e4=124p1414p12p2+18p22+13p1p314p4=124(p146p12p2+3p22+8p1p36p4),en=(1)nm1+2m2++nmn=nm10,,mn0i=1n(pi)mimi!imi

一般式は次のように簡単に表すことができる。

en=(1)nn!Bn(p1,1!p2,2!p3,,(n1)!pn),

ここで、Bn は完全指数ベル多項式である。この式は、母関数の恒等式を与える。

n=0enXn=exp(n=1(1)n+1npnXn).

この関係を単項多項式に適用すれば、係数を根のべき和で表すことができる。

べき和による完全同次対称式の表現

完全斉次対称式についても同様の関係式を得ることができる。

h1=p1,h2=12p12+12p2=12(p12+p2),h3=16p13+12p1p2+13p3=16(p13+3p1p2+2p3),h4=124p14+14p12p2+18p22+13p1p3+14p4=124(p14+6p12p2+3p22+8p1p3+6p4),hn=m1+2m2++nmn=nm10,,mn0i=1npimimi!imi

この場合もベル多項式により以下のように表される。

hn=1n!Bn(p1,1!p2,2!p3,,(n1)!pn).

これらの式は、対称群の巡回指標多項式に対応する。単項式 p1m1p2m2...plml に対応するhk を表す式の係数は、k の置換のうち、m1の固定点をもち、m2 の長さ2の巡回をもち、...、ml の長さ l の巡回をもつ置換のすべての置換に対する割合である。明示的にはこの係数は1/Nと表される。ここで

N=i=1l(mi!imi)

である。このN は、対応する巡回の種類と可換な置換の数を表す。

これは、次の帰納的ステップを検討することで証明できる。

mf(m;m1,,mn)=f(m1;m11,,mn)++f(mn;m1,,mn1)m1i=1n1imimi!++nmni=1n1imimi!=mi=1n1imimi!

基本対称多項式によるべき和の表現

ニュートンの恒等式から基本対象式によりべき和を表すことができる。

p1=e1,p2=e122e2,p3=e133e2e1+3e3,p4=e144e2e12+4e3e1+2e224e4,p5=e155e2e13+5e3e12+5e22e15e4e15e3e2+5e5,p6=e166e2e14+6e3e13+9e22e126e4e1212e3e2e1+6e5e12e23+3e32+6e4e26e6.

最初の4つの公式は、アルベールジラールによってニュートン以前の1629年に得られた。[2]

pm=(1)mmr1+2r2++mrm=mr10,,rm0(r1+r2++rm1)!r1!r2!rm!i=1m(ei)ri.

通常のベル多項式により次のように簡単に表すことができる。

pm=(1)mmk=1m1kB^m,k(e1,,emk+1),

または母関数として[3]表すことができる。

k=1(1)k1pktkk=ln(1+e1t+e2t2+e3t3+)=e1t12(e122e2)t2+13(e133e1e2+3e3)t3+,

これはベル多項式の指数的母関数と類似している。

上式は、次の帰納法のステップを検討することで証明できる。

f(m;r1,,rn)=f(m1;r11,,rn)++f(mn;r1,,rn1)=1(r11)!rn!(m1)(r1++rn2)!++1r1!(rn1)!(mn)(r1++rn2)!=1r1!rn![r1(m1)++rn(mn)][r1++rn2]!=1r1!rn![m(r1++rn)m][r1++rn2]!=m(r1++rn1)!r1!rn!

完全同次対称式によるべき和の表現

最後に、完全同次対称式によるべき和の表現を示す。

p1=+h1,p2=h12+2h2,p3=+h133h2h1+3h3,p4=h14+4h2h124h3h12h22+4h4,p5=+h155h2h13+5h22h1+5h3h125h3h25h4h1+5h5,p6=h16+6h2h149h22h126h3h13+2h23+12h3h2h1+6h4h123h326h4h26h1h5+6h6,

基本対称式の場合と比べ、ei のかわりにhiとなっており、各項の符号が異なっている。

一般式は次のとおりである。

pm=r1+2r2++mrm=mr10,,rm0m(r1+r2++rm1)!r1!r2!rm!i=1m(hi)ri

行列式による表現

ニュートンの恒等式は、クラメルの法則を適用することで、行列式の形で表すことができる。以下に示すニュートンの恒等式:

e1=1p1,2e2=e1p11p2,3e3=e2p1e1p2+1p3,nen=en1p1en2p2++(1)ne1pn1+(1)n1pn

について、p1,p2,p3,,(1)npn1を未知変数として、連立方程式を解く。これにより以下の表現が得られる。

pn=|10e1e1102e2e2e113e3en1e2e1nen||10e110e2e11en1e2e1(1)n1|1=(1)n1|10e1e1102e2e2e113e3en1e2e1nen|=|e1102e2e1103e3e2e11nenen1e1|.

pnの代わりにenを解くと以下のようになる(Macdonald 1979,p.20):

en=1n!|p110p2p120pn1pn2p1n1pnpn1p2p1|pn=(1)n1|h1102h2h1103h3h2h11nhnhn1h1|hn=1n!|p110p2p120pn1pn2p11npnpn1p2p1|.

恒等式の導出

ニュートンの恒等式は、初等代数で簡単に確認できる。

n = k の場合による導出

以下の式から、k変数のk番目のニュートンの公式を取得できる。

i=1k(txi)=i=0k(1)kieki(x1,,xk)ti

ここで、xjt を代入する。

0=i=0k(1)kieki(x1,,xk)xjifor 1jk

これをすべてのjについて合計すると

0=(1)kkek(x1,,xk)+i=1k(1)kieki(x1,,xk)pi(x1,,xk),

ここで i = 0 の項は、p0 の定義がないため、取り除かれている。この式は k 変数 k 番目のニュートンの恒等式を表している。

変数の数が n < k の場合は、kn 個の変数をゼロとすることで得られる。また変数の数が n > k の場合、n 個の変数から k 個を選び、そのすべての組み合わせに対して k 変数 k 番目のニュートン恒等式を足し合わせることで得られる。

係数の比較

また別の導出は、形式的べき級数 R[t] を用いて得ることができる。ここで Rx1,..., xn を変数とする整数上の多項式環 Z[x1,..., xn] である。

基本的な関係

i=1n(txi)=k=0n(1)kaktnk

ここで t を1/t で置き換え、両辺に tn をかけることにより、負指数のべき乗を取り除く。

i=1n(1xit)=k=0n(1)kaktk.

両辺を入れ替え、ai を基本対称式で表すことで以下の式を得る。

k=0n(1)kek(x1,,xn)tk=i=1n(1xit).

両辺をt について形式的に微分し、t をかけることで、以下の式を得る。

k=0n(1)kkek(x1,,xn)tk=ti=1n[(xi)ji(1xjt)]=(i=1nxit1xit)j=1n(1xjt)=[i=1nj=1(xit)j][=0n(1)e(x1,,xn)t]=[j=1pj(x1,,xn)tj][=0n(1)1e(x1,,xn)t],

ここで、右辺の多項式はまず有理関数に変形され、次に以下の公式により変形される。

X1X=X+X2+X3+X4+X5+,

最後にt j の係数を比較することで以下の式が得られる。

(1)kkek(x1,,xn)=j=1k(1)kj1pj(x1,,xn)ekj(x1,,xn),

k 番目のニュートンの恒等式を与える。

参照

参考文献

脚注

テンプレート:脚注ヘルプ テンプレート:Reflist