ニュートンの恒等式

ニュートンの恒等式（英: Newton's identity）、ジラール-ニュートンの公式（英: Girard–Newton formula）は、べき乗和と基本対称式との関係を与える。この関係は、単行多項式Pの根が与えられたとき、それらのk乗の和が、根を明示的に求めなくても、Pの係数によって表されることを意味する。この恒等式は1666年にアイザック・ニュートンによって発見された。実際にはこの式はこれよりも前に、アルベルト・ジラールにより発見されている（1629）。この恒等式はガロア理論、不変式論、群論、組み合わせ論を含む数学の多くの分野での応用や、一般相対性理論を含む数学以外のさらなる応用をもつ。 x1,...,xnを変数とし、 k ≥1について pk(x1,...,xn )を k次のべき乗和: p k ( x 1 , … , x n ) = ∑ i = 1 n x i k = x 1 k + ⋯ + 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 について ek(x1,...,xn )をk次の基本対称式とする。これはk個の相異なる変数の関の和である。 e 0 ( x 1 , … , x n ) = 1 , e 1 ( x 1 , … , x n ) = x 1 + x 2 + ⋯ + x n , e 2 ( x 1 , … , x n ) = ∑ 1 ≤ i < j ≤ n x i x j , e n ( x 1 , … , x n ) = x 1 x 2 ⋯ x n , e k ( x 1 , … , x n ) = 0 , for   k > n . {\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}}} このとき、ニュートンの恒等式は次のように述べることができる： k e k ( x 1 , … , x n ) = ∑ i = 1 k ( − 1 ) i − 1 e k − i ( x 1 , … , x n ) p i ( x 1 , … , x n ) {\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について有効である。 また、 0 = ∑ i = k − n k ( − 1 ) i − 1 e k − i ( x 1 , … , x n ) p i ( x 1 , … , x n ) , {\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について成り立つ 具体的には以下のようになる。 e 1 ( x 1 , … , x n ) = p 1 ( x 1 , … , x n ) , 2 e 2 ( x 1 , … , x n ) = e 1 ( x 1 , … , x n ) p 1 ( x 1 , … , x n ) − p 2 ( x 1 , … , x n ) , 3 e 3 ( x 1 , … , x n ) = e 2 ( x 1 , … , x n ) p 1 ( x 1 , … , x n ) − e 1 ( x 1 , … , x n ) p 2 ( x 1 , … , x n ) + p 3 ( x 1 , … , x n ) . {\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になる位置は変数に依存する） e 1 = p 1 , 2 e 2 = e 1 p 1 − p 2 = p 1 2 − p 2 , 3 e 3 = e 2 p 1 − e 1 p 2 + p 3 = 1 2 p 1 3 − 3 2 p 1 p 2 + p 3 , 4 e 4 = e 3 p 1 − e 2 p 2 + e 1 p 3 − p 4 = 1 6 p 1 4 − p 1 2 p 2 + 4 3 p 1 p 3 + 1 2 p 2 2 − p 4 , {\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}}} これらの方程式により、eiをpkにより表すことができる。また逆に p 1 = e 1 , p 2 = e 1 p 1 − 2 e 2 = e 1 2 − 2 e 2 , p 3 = e 1 p 2 − e 2 p 1 + 3 e 3 = e 1 3 − 3 e 1 e 2 + 3 e 3 , p 4 = e 1 p 3 − e 2 p 2 + e 3 p 1 − 4 e 4 = e 1 4 − 4 e 1 2 e 2 + 4 e 1 e 3 + 2 e 2 2 − 4 e 4 ,     ⋮ {\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}}} もなりたつ。一般に p k ( x 1 , … , x n ) = ( − 1 ) k − 1 k e k ( x 1 , … , x n ) + ∑ i = 1 k − 1 ( − 1 ) k − 1 + i e k − i ( x 1 , … , x n ) p i ( x 1 , … , x n ) {\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について成り立つ。 p k ( x 1 , … , x n ) = ∑ i = k − n k − 1 ( − 1 ) k − 1 + i e k − i ( x 1 , … , x n ) p i ( x 1 , … , x n ) {\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について成り立つ。 xiを根を持つ多項式は、以下のように展開できる。 ∏ i = 1 n ( x − x i ) = ∑ k = 0 n ( − 1 ) k e k x n − k , {\displaystyle \prod _{i=1}^{n}\left(x-x_{i}\right)=\sum _{k=0}^{n}(-1)^{k}e_{k}x^{n-k},} ここで、 e k ( x 1 , … , x n ) {\displaystyle e_{k}(x_{1},\dots ,x_{n})} は上で定義された対称多項式である。根のべき和を考えると p k ( x 1 , … , x n ) = ∑ i = 1 n x i k {\displaystyle p_{k}(x_{1},\dots ,x_{n})=\sum _{i=1}^{n}x_{i}^{k}} x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}} を根に持つ多項式の係数はべき和により次のように表すことができる。 e 0 = 1 , − e 1 = − p 1 , e 2 = 1 2 ( e 1 p 1 − p 2 ) , − e 3 = − 1 3 ( e 2 p 1 − e 1 p 2 + p 3 ) , e 4 = 1 4 ( e 3 p 1 − e 2 p 2 + e 1 p 3 − p 4 ) ,     ⋮ {\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 の方法により解析関数の零点を見つけるのに役立つ。 上記の多項式が行列Aの特性多項式である場合（特にAが多項式の同伴行列である場合）、根 x i {\displaystyle x_{i}} は行列の固有値となる。また、任意の正の整数kに対して、行列 Akは固有値 x i k {\displaystyle x_{i}^{k}} を持ち、これらの和はAkのトレース： p k = tr ⁡ ( A k ) . {\displaystyle p_{k}=\operatorname {tr} (A^{k})\,.} により表される。ニュートンの恒等式によりこれらから基本対称式が求まるため、Aの特性多項式の係数をAkのトレースを計算することにより求めることができる。 この計算では、行列のべき乗Akのトレースの計算と、ニュートンの恒等式を解く際に三角化された連立方程式を解く必要がある。これらの計算はどちらも複雑度クラスNCで実行できる。したがって、行列の特性多項式はNCで計算できる。ケイリー・ハミルトンの定理により、すべての行列はその特性多項式を満たし、単純な変換により、NCで余因子行列を見つけることができる。 計算を効率的な形式に再配置すると、ファデーエフ・ルベリエアルゴリズム（1840）が得られる。これの高速並列実装は、L. Csanky（1976）により得られた。この方式の欠点は、整数による除算が必要なことである。したがって、群の標数は0である必要がある。 与えられたn、k=1,...,n について初等対称多項式 ek(x1,...,xn) はxi に関する対象式の代数的基底を形成する。xi のすべての置換について不変な多項式は基本対称式により表される。これは対称多項式の基本定理として知られている一般的な事実であり、ニュートンの恒等式はべき和対称多項式について明示的な関係を示しいる。 単項多項式 t n + ∑ k = 1 n ( − 1 ) k a k t n − k {\displaystyle \textstyle t^{n}+\sum _{k=1}^{n}(-1)^{k}a_{k}t^{n-k}} にこれを適用すれば、この多項式の根についての対称式S(x1,...,xn)は、係数を用いた多項式P(a1,...,an)により表せることがわかる。このことはガロア理論の一般的結果である。 ニュートンの恒等式は、基本対称多項式をべき和対称多項式で表現することを可能にする。これは、任意の対称多項式がべき和で表現できることを示している。 ニュートンの恒等式に関連する恒等式がいくつかある。 次数 k の単項式の和である完全斉次対称式 hkについても、ニュートン恒等式と同様に以下の恒等式が存在する。ニュートン恒等式とは異なり、マイナスの符号が現れない。 k h k = ∑ i = 1 k h k − i p i , {\displaystyle kh_{k}=\sum _{i=1}^{k}h_{k-i}p_{i},} この式はすべてのn≥k≥1に対し成り立つ。ニュートンの公式とは異なり、左辺は大きなkに対して０にはならない。また、左辺には多くのゼロ項が含まれている。右側には、これまで以上にゼロ以外の項が含まれています。具体的には以下のようになる。 h 1 = p 1 , 2 h 2 = h 1 p 1 + p 2 , 3 h 3 = h 2 p 1 + h 1 p 2 + p 3 . {\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}}} これらの関係は、以下のような母関数の恒等式の係数を比較することで確認できる。 ∑ k = 0 ∞ h k ( X 1 , … , X n ) t k = ∏ i = 1 n 1 1 − X i t . {\displaystyle \sum _{k=0}^{\infty }h_{k}(X_{1},\dots ,X_{n})t^{k}=\prod _{i=1}^{n}{\frac {1}{1-X_{i}t}}.} 前述のように、ニュートンの公式を使用して、べき和により基本対称多項式を再帰的に表現できる。 e 1 = p 1 , e 2 = 1 2 p 1 2 − 1 2 p 2 = 1 2 ( p 1 2 − p 2 ) , e 3 = 1 6 p 1 3 − 1 2 p 1 p 2 + 1 3 p 3 = 1 6 ( p 1 3 − 3 p 1 p 2 + 2 p 3 ) , e 4 = 1 24 p 1 4 − 1 4 p 1 2 p 2 + 1 8 p 2 2 + 1 3 p 1 p 3 − 1 4 p 4 = 1 24 ( p 1 4 − 6 p 1 2 p 2 + 3 p 2 2 + 8 p 1 p 3 − 6 p 4 ) ,     ⋮ e n = ( − 1 ) n ∑ m 1 + 2 m 2 + ⋯ + n m n = n m 1 ≥ 0 , … , m n ≥ 0 ∏ i = 1 n ( − p i ) m i m i ! i m i {\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}}} 一般式は次のように簡単に表すことができる。 e n = ( − 1 ) n n ! B n ( − p 1 , − 1 ! p 2 , − 2 ! p 3 , … , − ( n − 1 ) ! p n ) , {\displaystyle e_{n}={\frac {(-1)^{n}}{n!}}B_{n}(-p_{1},-1!p_{2},-2!p_{3},\dots ,-(n-1)!p_{n}),} ここで、Bn は完全指数ベル多項式である。この式は、母関数の恒等式を与える。 ∑ n = 0 ∞ e n X n = exp ⁡ ( ∑ n = 1 ∞ ( − 1 ) n + 1 n p n X 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).} この関係を単項多項式に適用すれば、係数を根のべき和で表すことができる。 完全斉次対称式についても同様の関係式を得ることができる。 h 1 = p 1 , h 2 = 1 2 p 1 2 + 1 2 p 2 = 1 2 ( p 1 2 + p 2 ) , h 3 = 1 6 p 1 3 + 1 2 p 1 p 2 + 1 3 p 3 = 1 6 ( p 1 3 + 3 p 1 p 2 + 2 p 3 ) , h 4 = 1 24 p 1 4 + 1 4 p 1 2 p 2 + 1 8 p 2 2 + 1 3 p 1 p 3 + 1 4 p 4 = 1 24 ( p 1 4 + 6 p 1 2 p 2 + 3 p 2 2 + 8 p 1 p 3 + 6 p 4 ) ,     ⋮ h n = ∑ m 1 + 2 m 2 + ⋯ + n m n = n m 1 ≥ 0 , … , m n ≥ 0 ∏ i = 1 n p i m i m i ! i m i {\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}}} この場合もベル多項式により以下のように表される。 h n = 1 n ! B n ( p 1 , 1 ! p 2 , 2 ! p 3 , … , ( n − 1 ) ! p n ) . {\displaystyle h_{n}={\frac {1}{n!}}B_{n}(p_{1},1!p_{2},2!p_{3},\dots ,(n-1)!p_{n}).} これらの式は、対称群の巡回指標多項式に対応する。単項式 p1m1p2m2...plml に対応するhk を表す式の係数は、k の置換のうち、m1の固定点をもち、m2 の長さ2の巡回をもち、...、ml の長さ l の巡回をもつ置換のすべての置換に対する割合である。明示的にはこの係数は 1 / N {\displaystyle 1/N} と表される。ここで N = ∏ i = 1 l ( m i ! i m i ) {\displaystyle N=\prod _{i=1}^{l}(m_{i}!\,i^{m_{i}})} である。このN は、対応する巡回の種類と可換な置換の数を表す。 これは、次の帰納的ステップを検討することで証明できる。 m f ( m ; m 1 , … , m n ) = f ( m − 1 ; m 1 − 1 , … , m n ) + ⋯ + f ( m − n ; m 1 , … , m n − 1 ) m 1 ∏ i = 1 n 1 i m i m i ! + ⋯ + n m n ∏ i = 1 n 1 i m i m i ! = m ∏ i = 1 n 1 i m i m i ! {\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}}} ニュートンの恒等式から基本対象式によりべき和を表すことができる。 p 1 = e 1 , p 2 = e 1 2 − 2 e 2 , p 3 = e 1 3 − 3 e 2 e 1 + 3 e 3 , p 4 = e 1 4 − 4 e 2 e 1 2 + 4 e 3 e 1 + 2 e 2 2 − 4 e 4 , p 5 = e 1 5 − 5 e 2 e 1 3 + 5 e 3 e 1 2 + 5 e 2 2 e 1 − 5 e 4 e 1 − 5 e 3 e 2 + 5 e 5 , p 6 = e 1 6 − 6 e 2 e 1 4 + 6 e 3 e 1 3 + 9 e 2 2 e 1 2 − 6 e 4 e 1 2 − 12 e 3 e 2 e 1 + 6 e 5 e 1 − 2 e 2 3 + 3 e 3 2 + 6 e 4 e 2 − 6 e 6 . {\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年に得られた。 p m = ( − 1 ) m m ∑ r 1 + 2 r 2 + ⋯ + m r m = m r 1 ≥ 0 , … , r m ≥ 0 ( r 1 + r 2 + ⋯ + r m − 1 ) ! r 1 ! r 2 ! ⋯ r m ! ∏ i = 1 m ( − e i ) r i . {\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}}.} 通常のベル多項式により次のように簡単に表すことができる。 p m = ( − 1 ) m m ∑ k = 1 m 1 k B