ニュートンの恒等式

ウィキペディア

ニュートンの恒等式

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/05/07 01:23 UTC 版)

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

定義

対称多項式による定式化

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

${\displaystyle p_{k}(x_{1},\dots ,x_{n})=\sum _{i=1}^{n}x_{i}^{k}=x_{1}^{k}+\dots +x_{n}^{k},}$

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

${\displaystyle {\begin{aligned}e_{0}(x_{1},\dots ,x_{n})&=1,\\e_{1}(x_{1},\dots ,x_{n})&=x_{1}+x_{2}+\dots +x_{n},\\e_{2}(x_{1},\dots ,x_{n})&=\textstyle \sum _{1\leq i<j\leq n}x_{i}x_{j},\\e_{n}(x_{1},\dots ,x_{n})&=x_{1}x_{2}\dotsb x_{n},\\e_{k}(x_{1},\dots ,x_{n})&=0,\quad {\text{for}}\ k>n.\\\end{aligned}}}$

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

${\displaystyle ke_{k}(x_{1},\dots ,x_{n})=\sum _{i=1}^{k}(-1)^{i-1}e_{k-i}(x_{1},\dots ,x_{n})p_{i}(x_{1},\dots ,x_{n})}$

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

また、

${\displaystyle 0=\sum _{i=k-n}^{k}(-1)^{i-1}e_{k-i}(x_{1},\dots ,x_{n})p_{i}(x_{1},\dots ,x_{n}),}$

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

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

${\displaystyle {\begin{aligned}e_{1}(x_{1},\dots ,x_{n})&=p_{1}(x_{1},\dots ,x_{n}),\\2e_{2}(x_{1},\dots ,x_{n})&=e_{1}(x_{1},\dots ,x_{n})p_{1}(x_{1},\dots ,x_{n})-p_{2}(x_{1},\dots ,x_{n}),\\3e_{3}(x_{1},\dots ,x_{n})&=e_{2}(x_{1},\dots ,x_{n})p_{1}(x_{1},\dots ,x_{n})-e_{1}(x_{1},\dots ,x_{n})p_{2}(x_{1},\dots ,x_{n})+p_{3}(x_{1},\dots ,x_{n}).\\\end{aligned}}}$

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

${\displaystyle {\begin{aligned}e_{1}&=p_{1},\\2e_{2}&=e_{1}p_{1}-p_{2}=p_{1}^{2}-p_{2},\\3e_{3}&=e_{2}p_{1}-e_{1}p_{2}+p_{3}={\tfrac {1}{2}}p_{1}^{3}-{\tfrac {3}{2}}p_{1}p_{2}+p_{3},\\4e_{4}&=e_{3}p_{1}-e_{2}p_{2}+e_{1}p_{3}-p_{4}={\tfrac {1}{6}}p_{1}^{4}-p_{1}^{2}p_{2}+{\tfrac {4}{3}}p_{1}p_{3}+{\tfrac {1}{2}}p_{2}^{2}-p_{4},\\\end{aligned}}}$

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

${\displaystyle {\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}p_{1}-2e_{2}=e_{1}^{2}-2e_{2},\\p_{3}&=e_{1}p_{2}-e_{2}p_{1}+3e_{3}=e_{1}^{3}-3e_{1}e_{2}+3e_{3},\\p_{4}&=e_{1}p_{3}-e_{2}p_{2}+e_{3}p_{1}-4e_{4}=e_{1}^{4}-4e_{1}^{2}e_{2}+4e_{1}e_{3}+2e_{2}^{2}-4e_{4},\\&{}\ \ \vdots \end{aligned}}}$

もなりたつ。一般に

${\displaystyle p_{k}(x_{1},\dots ,x_{n})=(-1)^{k-1}ke_{k}(x_{1},\dots ,x_{n})+\sum _{i=1}^{k-1}(-1)^{k-1+i}e_{k-i}(x_{1},\dots ,x_{n})p_{i}(x_{1},\dots ,x_{n})}$

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

${\displaystyle p_{k}(x_{1},\dots ,x_{n})=\sum _{i=k-n}^{k-1}(-1)^{k-1+i}e_{k-i}(x_{1},\dots ,x_{n})p_{i}(x_{1},\dots ,x_{n})}$

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

多項式の根への適用

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

${\displaystyle \prod _{i=1}^{n}\left(x-x_{i}\right)=\sum _{k=0}^{n}(-1)^{k}e_{k}x^{n-k},}$

ここで、${\displaystyle e_{k}(x_{1},\dots ,x_{n})}$ は上で定義された対称多項式である。根のべき和を考えると

${\displaystyle p_{k}(x_{1},\dots ,x_{n})=\sum _{i=1}^{n}x_{i}^{k}}$

${\displaystyle x_{1},\dots ,x_{n}}$を根に持つ多項式の係数はべき和により次のように表すことができる。

${\displaystyle {\begin{aligned}e_{0}&=1,\\[4pt]-e_{1}&=-p_{1},\\[4pt]e_{2}&={\frac {1}{2}}(e_{1}p_{1}-p_{2}),\\[4pt]-e_{3}&=-{\frac {1}{3}}(e_{2}p_{1}-e_{1}p_{2}+p_{3}),\\[4pt]e_{4}&={\frac {1}{4}}(e_{3}p_{1}-e_{2}p_{2}+e_{1}p_{3}-p_{4}),\\&{}\ \ \vdots \end{aligned}}}$

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

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

上記の多項式が行列Aの特性多項式である場合（特にAが多項式の同伴行列である場合）、根 ${\displaystyle x_{i}}$は行列の固有値となる。また、任意の正の整数kに対して、行列 A^kは固有値 ${\displaystyle x_{i}^{k}}$を持ち、これらの和はA^kのトレース：

${\displaystyle p_{k}=\operatorname {tr} (A^{k})\,.}$

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

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

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

ガロア理論との関係

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

単項多項式 ${\displaystyle \textstyle t^{n}+\sum _{k=1}^{n}(-1)^{k}a_{k}t^{n-k}}$ にこれを適用すれば、この多項式の根についての対称式S(x₁,...,x_n)は、係数を用いた多項式P(a₁,...,a_n)により表せることがわかる。このことはガロア理論の一般的結果である。

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

関連する恒等式

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

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

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

${\displaystyle kh_{k}=\sum _{i=1}^{k}h_{k-i}p_{i},}$

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

${\displaystyle {\begin{aligned}h_{1}&=p_{1},\\2h_{2}&=h_{1}p_{1}+p_{2},\\3h_{3}&=h_{2}p_{1}+h_{1}p_{2}+p_{3}.\\\end{aligned}}}$

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

${\displaystyle \sum _{k=0}^{\infty }h_{k}(X_{1},\dots ,X_{n})t^{k}=\prod _{i=1}^{n}{\frac {1}{1-X_{i}t}}.}$

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

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

${\displaystyle {\begin{aligned}e_{1}&=p_{1},\\e_{2}&={\frac {1}{2}}p_{1}^{2}-{\frac {1}{2}}p_{2}&&={\frac {1}{2}}(p_{1}^{2}-p_{2}),\\e_{3}&={\frac {1}{6}}p_{1}^{3}-{\frac {1}{2}}p_{1}p_{2}+{\frac {1}{3}}p_{3}&&={\frac {1}{6}}(p_{1}^{3}-3p_{1}p_{2}+2p_{3}),\\e_{4}&={\frac {1}{24}}p_{1}^{4}-{\frac {1}{4}}p_{1}^{2}p_{2}+{\frac {1}{8}}p_{2}^{2}+{\frac {1}{3}}p_{1}p_{3}-{\frac {1}{4}}p_{4}&&={\frac {1}{24}}(p_{1}^{4}-6p_{1}^{2}p_{2}+3p_{2}^{2}+8p_{1}p_{3}-6p_{4}),\\&~~\vdots \\e_{n}&=(-1)^{n}\sum _{m_{1}+2m_{2}+\dots +nm_{n}=n \atop m_{1}\geq 0,\dots ,m_{n}\geq 0}\prod _{i=1}^{n}{\frac {(-p_{i})^{m_{i}}}{m_{i}!i^{m_{i}}}}\\\end{aligned}}}$

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

${\displaystyle e_{n}={\frac {(-1)^{n}}{n!}}B_{n}(-p_{1},-1!p_{2},-2!p_{3},\dots ,-(n-1)!p_{n}),}$

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

${\displaystyle \sum _{n=0}^{\infty }e_{n}\,X^{n}=\exp \left(\sum _{n=1}^{\infty }{\frac {(-1)^{n+1}}{n}}p_{n}\,X^{n}\right).}$

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

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

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

${\displaystyle {\begin{aligned}h_{1}&=p_{1},\\h_{2}&={\frac {1}{2}}p_{1}^{2}+{\frac {1}{2}}p_{2}&&={\frac {1}{2}}(p_{1}^{2}+p_{2}),\\h_{3}&={\frac {1}{6}}p_{1}^{3}+{\frac {1}{2}}p_{1}p_{2}+{\frac {1}{3}}p_{3}&&={\frac {1}{6}}(p_{1}^{3}+3p_{1}p_{2}+2p_{3}),\\h_{4}&={\frac {1}{24}}p_{1}^{4}+{\frac {1}{4}}p_{1}^{2}p_{2}+{\frac {1}{8}}p_{2}^{2}+{\frac {1}{3}}p_{1}p_{3}+{\frac {1}{4}}p_{4}&&={\frac {1}{24}}(p_{1}^{4}+6p_{1}^{2}p_{2}+3p_{2}^{2}+8p_{1}p_{3}+6p_{4}),\\&~~\vdots \\h_{n}&=\sum _{m_{1}+2m_{2}+\dots +nm_{n}=n \atop m_{1}\geq 0,\dots ,m_{n}\geq 0}\prod _{i=1}^{n}{\frac {p_{i}^{m_{i}}}{m_{i}!i^{m_{i}}}}\\\end{aligned}}}$

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

${\displaystyle h_{n}={\frac {1}{n!}}B_{n}(p_{1},1!p_{2},2!p_{3},\dots ,(n-1)!p_{n}).}$

これらの式は、対称群の巡回指標多項式に対応する。単項式 p₁^m₁p₂^m₂...p_l^m_l に対応するh_k を表す式の係数は、k の置換のうち、m₁の固定点をもち、m₂ の長さ2の巡回をもち、...、m_l の長さ l の巡回をもつ置換のすべての置換に対する割合である。明示的にはこの係数は${\displaystyle 1/N}$と表される。ここで

${\displaystyle N=\prod _{i=1}^{l}(m_{i}!\,i^{m_{i}})}$

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

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

${\displaystyle {\begin{aligned}mf(m;m_{1},\ldots ,m_{n})&=f(m-1;m_{1}-1,\ldots ,m_{n})+\cdots +f(m-n;m_{1},\ldots ,m_{n}-1)\\m_{1}\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}+\cdots +nm_{n}\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}&=m\prod _{i=1}^{n}{\frac {1}{i^{m_{i}}m_{i}!}}\end{aligned}}}$

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

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

${\displaystyle {\begin{aligned}p_{1}&=e_{1},\\p_{2}&=e_{1}^{2}-2e_{2},\\p_{3}&=e_{1}^{3}-3e_{2}e_{1}+3e_{3},\\p_{4}&=e_{1}^{4}-4e_{2}e_{1}^{2}+4e_{3}e_{1}+2e_{2}^{2}-4e_{4},\\p_{5}&=e_{1}^{5}-5e_{2}e_{1}^{3}+5e_{3}e_{1}^{2}+5e_{2}^{2}e_{1}-5e_{4}e_{1}-5e_{3}e_{2}+5e_{5},\\p_{6}&=e_{1}^{6}-6e_{2}e_{1}^{4}+6e_{3}e_{1}^{3}+9e_{2}^{2}e_{1}^{2}-6e_{4}e_{1}^{2}-12e_{3}e_{2}e_{1}+6e_{5}e_{1}-2e_{2}^{3}+3e_{3}^{2}+6e_{4}e_{2}-6e_{6}.\end{aligned}}}$

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

${\displaystyle p_{m}=(-1)^{m}m\sum _{r_{1}+2r_{2}+\cdots +mr_{m}=m \atop r_{1}\geq 0,\ldots ,r_{m}\geq 0}{\frac {(r_{1}+r_{2}+\cdots +r_{m}-1)!}{r_{1}!r_{2}!\cdots r_{m}!}}\prod _{i=1}^{m}(-e_{i})^{r_{i}}.}$

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

${\displaystyle p_{m}=(-1)^{m}m\sum _{k=1}^{m}{\frac {1}{k}}{\hat {B}}_{m,k}(-e_{1},\ldots ,-e_{m-k+1}),}$

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

${\displaystyle {\begin{aligned}\sum _{k=1}^{\infty }(-1)^{k-1}p_{k}{\frac {t^{k}}{k}}&=\ln \left(1+e_{1}t+e_{2}t^{2}+e_{3}t^{3}+\cdots \right)\\&=e_{1}t-{\frac {1}{2}}\left(e_{1}^{2}-2e_{2}\right)t^{2}+{\frac {1}{3}}\left(e_{1}^{3}-3e_{1}e_{2}+3e_{3}\right)t^{3}+\cdots ,\end{aligned}}}$

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

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

${\displaystyle {\begin{aligned}f(m;\;r_{1},\ldots ,r_{n})={}&f(m-1;\;r_{1}-1,\cdots ,r_{n})+\cdots +f(m-n;\;r_{1},\ldots ,r_{n}-1)\\[8pt]={}&{\frac {1}{(r_{1}-1)!\cdots r_{n}!}}(m-1)(r_{1}+\cdots +r_{n}-2)!+\cdots \\&\cdots +{\frac {1}{r_{1}!\cdots (r_{n}-1)!}}(m-n)(r_{1}+\cdots +r_{n}-2)!\\[8pt]={}&{\frac {1}{r_{1}!\cdots r_{n}!}}\left[r_{1}(m-1)+\cdots +r_{n}(m-n)\right]\left[r_{1}+\cdots +r_{n}-2\right]!\\[8pt]={}&{\frac {1}{r_{1}!\cdots r_{n}!}}\left[m(r_{1}+\cdots +r_{n})-m\right]\left[r_{1}+\cdots +r_{n}-2\right]!\\[8pt]={}&{\frac {m(r_{1}+\cdots +r_{n}-1)!}{r_{1}!\cdots r_{n}!}}\end{aligned}}}$

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

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

${\displaystyle {\begin{aligned}p_{1}&=+h_{1},\\p_{2}&=-h_{1}^{2}+2h_{2},\\p_{3}&=+h_{1}^{3}-3h_{2}h_{1}+3h_{3},\\p_{4}&=-h_{1}^{4}+4h_{2}h_{1}^{2}-4h_{3}h_{1}-2h_{2}^{2}+4h_{4},\\p_{5}&=+h_{1}^{5}-5h_{2}h_{1}^{3}+5h_{2}^{2}h_{1}+5h_{3}h_{1}^{2}-5h_{3}h_{2}-5h_{4}h_{1}+5h_{5},\\p_{6}&=-h_{1}^{6}+6h_{2}h_{1}^{4}-9h_{2}^{2}h_{1}^{2}-6h_{3}h_{1}^{3}+2h_{2}^{3}+12h_{3}h_{2}h_{1}+6h_{4}h_{1}^{2}-3h_{3}^{2}-6h_{4}h_{2}-6h_{1}h_{5}+6h_{6},\\\end{aligned}}}$

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

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

${\displaystyle p_{m}=-\sum _{r_{1}+2r_{2}+\cdots +mr_{m}=m \atop r_{1}\geq 0,\ldots ,r_{m}\geq 0}{\frac {m(r_{1}+r_{2}+\cdots +r_{m}-1)!}{r_{1}!r_{2}!\cdots r_{m}!}}\prod _{i=1}^{m}(-h_{i})^{r_{i}}}$

行列式による表現

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

${\displaystyle {\begin{aligned}e_{1}&=1p_{1},\\2e_{2}&=e_{1}p_{1}-1p_{2},\\3e_{3}&=e_{2}p_{1}-e_{1}p_{2}+1p_{3},\\&\,\,\,\vdots \\ne_{n}&=e_{n-1}p_{1}-e_{n-2}p_{2}+\cdots +(-1)^{n}e_{1}p_{n-1}+(-1)^{n-1}p_{n}\\\end{aligned}}}$

について、${\displaystyle p_{1},-p_{2},p_{3},\ldots ,(-1)^{n}p_{n-1}}$を未知変数として、連立方程式を解く。これにより以下の表現が得られる。

${\displaystyle {\begin{aligned}p_{n}={}&{\begin{vmatrix}1&0&\cdots &&e_{1}\\e_{1}&1&0&\cdots &2e_{2}\\e_{2}&e_{1}&1&&3e_{3}\\\vdots &&\ddots &\ddots &\vdots \\e_{n-1}&\cdots &e_{2}&e_{1}&ne_{n}\end{vmatrix}}{\begin{vmatrix}1&0&\cdots &\\e_{1}&1&0&\cdots \\e_{2}&e_{1}&1&\\\vdots &&\ddots &\ddots \\e_{n-1}&\cdots &e_{2}&e_{1}&(-1)^{n-1}\end{vmatrix}}^{-1}\\[7pt]={(-1)^{n-1}}&{\begin{vmatrix}1&0&\cdots &&e_{1}\\e_{1}&1&0&\cdots &2e_{2}\\e_{2}&e_{1}&1&&3e_{3}\\\vdots &&\ddots &\ddots &\vdots \\e_{n-1}&\cdots &e_{2}&e_{1}&ne_{n}\end{vmatrix}}\\[7pt]={}&{\begin{vmatrix}e_{1}&1&0&\cdots \\2e_{2}&e_{1}&1&0&\cdots \\3e_{3}&e_{2}&e_{1}&1\\\vdots &&&\ddots &\ddots \\ne_{n}&e_{n-1}&\cdots &&e_{1}\end{vmatrix}}.\end{aligned}}}$

${\displaystyle p_{n}}$の代わりに${\displaystyle e_{n}}$を解くと以下のようになる（Macdonald 1979,p.20）：

${\displaystyle {\begin{aligned}e_{n}={\frac {1}{n!}}&{\begin{vmatrix}p_{1}&1&0&\cdots \\p_{2}&p_{1}&2&0&\cdots \\\vdots &&\ddots &\ddots \\p_{n-1}&p_{n-2}&\cdots &p_{1}&n-1\\p_{n}&p_{n-1}&\cdots &p_{2}&p_{1}\end{vmatrix}}\\[7pt]p_{n}=(-1)^{n-1}&{\begin{vmatrix}h_{1}&1&0&\cdots \\2h_{2}&h_{1}&1&0&\cdots \\3h_{3}&h_{2}&h_{1}&1\\\vdots &&&\ddots &\ddots \\nh_{n}&h_{n-1}&\cdots &&h_{1}\end{vmatrix}}\\[7pt]h_{n}={\frac {1}{n!}}&{\begin{vmatrix}p_{1}&-1&0&\cdots \\p_{2}&p_{1}&-2&0&\cdots \\\vdots &&\ddots &\ddots \\p_{n-1}&p_{n-2}&\cdots &p_{1}&1-n\\p_{n}&p_{n-1}&\cdots &p_{2}&p_{1}\end{vmatrix}}.\end{aligned}}}$

恒等式の導出

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

n = k の場合による導出

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

${\displaystyle \prod _{i=1}^{k}(t-x_{i})=\sum _{i=0}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k})t^{i}}$

ここで、x_j に t を代入する。

${\displaystyle 0=\sum _{i=0}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k}){x_{j}}^{i}\quad {\text{for }}1\leq j\leq k}$

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

${\displaystyle 0=(-1)^{k}ke_{k}(x_{1},\ldots ,x_{k})+\sum _{i=1}^{k}(-1)^{k-i}e_{k-i}(x_{1},\ldots ,x_{k})p_{i}(x_{1},\ldots ,x_{k}),}$

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

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

係数の比較

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

基本的な関係

${\displaystyle \prod _{i=1}^{n}(t-x_{i})=\sum _{k=0}^{n}(-1)^{k}a_{k}t^{n-k}}$

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

${\displaystyle \prod _{i=1}^{n}(1-x_{i}t)=\sum _{k=0}^{n}(-1)^{k}a_{k}t^{k}.}$

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

${\displaystyle \sum _{k=0}^{n}(-1)^{k}e_{k}(x_{1},\ldots ,x_{n})t^{k}=\prod _{i=1}^{n}(1-x_{i}t).}$

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

${\displaystyle {\begin{aligned}\sum _{k=0}^{n}(-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})t^{k}&=t\sum _{i=1}^{n}\left[(-x_{i})\prod \nolimits _{j\neq i}(1-x_{j}t)\right]\\&=-\left(\sum _{i=1}^{n}{\frac {x_{i}t}{1-x_{i}t}}\right)\prod \nolimits _{j=1}^{n}(1-x_{j}t)\\&=-\left[\sum _{i=1}^{n}\sum _{j=1}^{\infty }(x_{i}t)^{j}\right]\left[\sum _{\ell =0}^{n}(-1)^{\ell }e_{\ell }(x_{1},\ldots ,x_{n})t^{\ell }\right]\\&=\left[\sum _{j=1}^{\infty }p_{j}(x_{1},\ldots ,x_{n})t^{j}\right]\left[\sum _{\ell =0}^{n}(-1)^{\ell -1}e_{\ell }(x_{1},\ldots ,x_{n})t^{\ell }\right],\\\end{aligned}}}$

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

${\displaystyle {\frac {X}{1-X}}=X+X^{2}+X^{3}+X^{4}+X^{5}+\cdots ,}$

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

${\displaystyle (-1)^{k}ke_{k}(x_{1},\ldots ,x_{n})=\sum _{j=1}^{k}(-1)^{k-j-1}p_{j}(x_{1},\ldots ,x_{n})e_{k-j}(x_{1},\ldots ,x_{n}),}$

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

参照

• 対称式

参考文献

• Tignol, Jean-Pierre (2001). Galois' theory of algebraic equations. Singapore: World Scientific. ISBN 978-981-02-4541-2 
• Bergeron, F.; Labelle, G.; Leroux, P. (1998). Combinatorial species and tree-like structures. Cambridge: Cambridge University Press. ISBN 978-0-521-57323-8. https://archive.org/details/combinatorialspe0000berg 
• Cameron, Peter J. (1999). Permutation Groups. Cambridge: Cambridge University Press. ISBN 978-0-521-65378-7. https://archive.org/details/permutationgroup0000came 
• Cox, David; Little, John; O'Shea, Donal (1992). Ideals, Varieties, and Algorithms. New York: Springer-Verlag. ISBN 978-0-387-97847-5 
• Eppstein, D.; Goodrich, M. T. (2007). "Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters". Algorithms and Data Structures, 10th International Workshop, WADS 2007. Springer-Verlag, Lecture Notes in Computer Science 4619. pp. 637–648. Bibcode:2007arXiv0704.3313E。
• Littlewood, D. E. (1950). The theory of group characters and matrix representations of groups. Oxford: Oxford University Press. viii+310. ISBN 0-8218-4067-3 
• Macdonald, I. G. (1979). Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. Oxford: The Clarendon Press, Oxford University Press. viii+180. ISBN 0-19-853530-9. MR553598 
• Macdonald, I. G. (1995). Symmetric functions and Hall polynomials. Oxford Mathematical Monographs (Second ed.). New York: Oxford Science Publications. The Clarendon Press, Oxford University Press. p. x+475. ISBN 0-19-853489-2. MR1354144 
• Mead, D.G. (1992). “Newton's Identities”. The American Mathematical Monthly (Mathematical Association of America) 99 (8): 749–751. doi:10.2307/2324242. JSTOR 2324242. 
• Stanley, Richard P. (1999). Enumerative Combinatorics, Vol. 2. Cambridge University Press. ISBN 0-521-56069-1. (hardback). (paperback) 
• Sturmfels, Bernd (1992). Algorithms in Invariant Theory. New York: Springer-Verlag. ISBN 978-0-387-82445-1 
• Tucker, Alan (1980). Applied Combinatorics (5/e ed.). New York: Wiley. ISBN 978-0-471-73507-6. https://archive.org/details/appliedcombinato00tuck 

• MathWorldのNewton–Girard式
• 数学雑誌におけるニュートンのアイデンティティの行列証明
• 実根数への応用
• DoronZeilbergerによるニュートンのアイデンティティの組み合わせ論的証明

脚注

[脚注の使い方]

1. ^ Delves, L. M. (1967). “A Numerical Method of Locating the Zeros of an Analytic Function”. Mathematics of Computation 21 (100): 543–560. doi:10.2307/2004999. JSTOR 2004999. 
2. ^ Tignol, Jean-Pierre (2004). Galois' theory of algebraic equations (Reprinted ed.). River Edge, NJ: World Scientific. pp. 37–38. ISBN 981-02-4541-6. https://archive.org/details/galoistheoryalge00tign 
3. ^ Weisstein, Eric W. "Symmetric Polynomial". MathWorld (英語).