ニュートンの恒等式のソースを表示

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

== 定義 ==
=== 対称多項式による定式化 ===
''x''<sub>1,</sub>...,''x''<sub>''n''</sub>を変数とし、 ''k'' ≥1について ''p<sub>k</sub>(x''<sub>1,</sub>...,''x''<sub>''n''</sub> )を '''''k''次のべき乗和:'''

: <math>p_k(x_1,\dots,x_n)=\sum_{i=1}^{n} x_i^k = x_1^k+\dots+x_n^k,</math>

''とする。そして、k'' ≥ 0 について e<sub>''k''</sub>''(x''<sub>1,</sub>...,''x''<sub>''n''</sub> )をk次の[[基本対称式]]とする。これは''k''個の相異なる変数の関の和である。

: <math>\begin{align}
 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_ix_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{align}</math>

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

: <math> 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)</math>

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

また、

: <math> 0 = \sum_{i=k-n}^{k} (-1)^{i-1} e_{k - i} (x_1, \dots, x_n) p_i(x_1, \dots, x_n),</math>

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

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

: <math>\begin{align}
  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{align}</math>

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

: <math>\begin{align}
  e_1 &= p_1,\\
 2e_2 &= e_1p_1-p_2 = p_1^2-p_2,\\
 3e_3 &= e_2p_1 - e_1p_2 + p_3 = \tfrac12 p_1^3-\tfrac32p_1p_2+p_3,\\
 4e_4 &= e_3p_1 - e_2p_2 + e_1p_3 - p_4 = \tfrac16p_1^4 - p_1^2p_2 + \tfrac43p_1p_3+\tfrac12p_2^2-p_4,\\
\end{align}</math>

これらの方程式により、e<sub>''i''</sub>をp<sub>''k''</sub>により表すことができる。また逆に

: <math>\begin{align}
 p_1 &= e_1,\\
 p_2 &= e_1p_1-2e_2 = e_1^2 - 2e_2,\\
 p_3 &= e_1p_2 - e_2p_1 + 3e_3 = e_1^3-3e_1e_2+3e_3,\\
 p_4 &= e_1p_3 - e_2p_2 + e_3p_1 - 4e_4 = e_1^4-4e_1^2e_2+4e_1e_3+2e_2^2-4e_4, \\
   & {}\ \ \vdots
\end{align}</math>

もなりたつ。一般に

: <math> 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)</math>

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

: <math> 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)</math>

が''k''&nbsp;>&nbsp;''n''&nbsp;≥&nbsp;1について成り立つ。

=== 多項式の根への適用 ===
''x<sub>i</sub>を''根を持つ多項式は、以下のように展開できる。

: <math> \prod_{i=1}^n \left( x - x_i \right) = \sum_{k=0}^n (-1)^{k} e_{k} x^{n-k},</math>

ここで、<math>e_k(x_1,\dots,x_n)</math> は上で定義された対称多項式である。根のべき和を考えると

: <math> p_k(x_1,\dots,x_n)= \sum_{i=1}^n x_i^k</math>

<math>x_1,\dots,x_n</math>を根に持つ多項式の係数はべき和により次のように表すことができる。

: <math>\begin{align}
 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{align}</math>

この方法で多項式を定式化すると、Delves や Lyness <ref name="Delves_Lyness_1967">{{Cite journal|last=Delves|first=L. M.|date=1967|title=A Numerical Method of Locating the Zeros of an Analytic Function|journal=Mathematics of Computation|volume=21|issue=100|pages=543–560|DOI=10.2307/2004999|JSTOR=2004999}}</ref>の方法により解析関数の零点を見つけるのに役立つ。

=== 行列の特性多項式への適用 ===
上記の[[行列|多項式が行列]]''Aの''[[固有多項式|特性多項式]]である場合（特に''A''が多項式の[[同伴行列]]である場合）、根 <math>x_i</math>は行列の[[固有値]]となる。また、任意の正の整数''k''に対して、行列 ''A''<sup>''k''</sup>は固有値 <math>x_i^k</math>を持ち、これらの和は''A''<sup>''k''</sup>の[[跡 (線型代数学)|トレース]]：

: <math>p_k = \operatorname{tr} ( A^k )\,.</math>

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

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

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

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

単項多項式 <math>\textstyle t^n+\sum_{k=1}^n (-1)^{k} a_k t^{n-k}</math> にこれを適用すれば、この多項式の根についての対称式''S''(''x''<sub>1</sub>,...,''x<sub>n</sub>'')は、係数を用いた多項式''P''(''a''<sub>1</sub>,...,''a<sub>n</sub>'')により表せることがわかる。このことは[[ガロア理論]]の一般的結果である。

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

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

=== 完全斉次対称式を使用した変形 ===
次数 ''k'' の[[単項式]]の和である完全斉次対称式 ''h<sub>k</sub>''についても、ニュートン恒等式と同様に以下の恒等式が存在する。ニュートン恒等式とは異なり、マイナスの符号が現れない。

: <math>kh_k = \sum_{i=1}^kh_{k-i}p_i,</math>

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

: <math>\begin{align}
  h_1 &= p_1,\\
 2h_2 &= h_1p_1 + p_2,\\
 3h_3 &= h_2p_1 + h_1p_2 + p_3.\\ 
\end{align}</math>

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

: <math>\sum_{k=0}^\infty h_k(X_1, \dots, X_n)t^k = \prod_{i=1}^n\frac1{1 - X_it}.</math>

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

: <math>\begin{align}
 e_1 &= p_1,\\
 e_2 &= \frac12p_1^2 - \frac12p_2 &&= \frac12 ( p_1^2 - p_2 ),\\
 e_3 &= \frac16p_1^3 - \frac12p_1 p_2 + \frac13p_3 &&= \frac{1}{6} ( p_1^3 - 3 p_1 p_2 + 2 p_3 ),\\
 e_4 &= \frac1{24}p_1^4 - \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 - \frac14p_4 
    &&= \frac1{24} ( p_1^4 - 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 - 6 p_4 ),\\
&~~\vdots\\
 e_n &= (-1)^n \sum_{m_1 + 2m_2 + \dots + nm_n = n \atop m_1 \ge 0, \dots, m_n \ge 0} \prod_{i=1}^n \frac{(-p_i)^{m_i}}{m_i ! i^{m_i}} \\
\end{align}</math>

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

: <math>e_n = \frac{(-1)^n}{n!} B_{n}(- p_1, -1! p_2, - 2! p_3, \dots, - (n-1)! p_n ), </math>

ここで、''B<sub>n</sub>'' は完全指数[[ベル多項式]]である。この式は、母関数の恒等式を与える。

: <math> \sum_{n=0}^\infty e_n \,X^n = \exp\left(\sum_{n=1}^\infty \frac{(-1)^{n+1}}{n} p_n \,X^n \right). </math>

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

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

: <math>\begin{align}
 h_1 &= p_1,\\
 h_2 &= \frac12p_1^2 + \frac12p_2 &&= \frac12 ( p_1^2 + p_2 ),\\
 h_3 &= \frac16p_1^3 + \frac12p_1 p_2 + \frac13p_3 &&= \frac{1}{6} ( p_1^3 + 3 p_1 p_2 + 2 p_3 ),\\
 h_4 &= \frac1{24}p_1^4 + \frac14p_1^2 p_2 + \frac18p_2^2 + \frac13p_1 p_3 + \frac14p_4 
    &&= \frac1{24} ( p_1^4 + 6 p_1^2 p_2 + 3 p_2^2 + 8 p_1 p_3 + 6 p_4 ),\\
&~~\vdots\\
 h_n &= \sum_{m_1 + 2m_2 + \dots + nm_n = n \atop m_1\ge 0, \dots, m_n\ge 0} \prod_{i=1}^n \frac{p_i^{m_i}}{m_i ! i^{m_i}}\\
\end{align}</math>

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

: <math>h_n = \frac{1}{n!} B_{n}(p_1, 1! p_2, 2! p_3, \dots, (n-1)! p_n ). </math>

これらの式は、[[対称群]]の巡回指標多項式に対応する。単項式 ''p''<sub>1</sub><sup>''m''<sub>1</sub></sup>''p''<sub>2</sub><sup>''m''<sub>2</sub></sup>...''p<sub>l</sub><sup>m<sub>l</sub></sup>'' に対応する''h<sub>k</sub>'' を表す式の係数は、''k'' の置換のうち、''m''<sub>1</sub>の固定点をもち、''m''<sub>2</sub> の長さ2の巡回をもち、...、''m<sub>l</sub>'' の長さ ''l'' の巡回をもつ置換のすべての置換に対する割合である。明示的にはこの係数は<math>1/N</math>と表される。ここで
:<math>N=\prod_{i=1}^l(m_i!\,i^{m_i})</math>
である。この''N'' は、対応する巡回の種類と可換な置換の数を表す。

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

: <math>\begin{align}
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{align}</math>

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

: <math>\begin{align}
 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_3e_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 - 6e_6.
\end{align}</math>

最初の4つの公式は、アルベールジラールによってニュートン以前の1629年に得られた。<ref>{{Cite book|last=Tignol|first=Jean-Pierre|title=Galois' theory of algebraic equations|url=https://archive.org/details/galoistheoryalge00tign|date=2004|publisher=World Scientific|location=River Edge, NJ|isbn=981-02-4541-6|pages=[https://archive.org/details/galoistheoryalge00tign/page/n50 37]–38|edition=Reprinted}}</ref>

: <math>p_m = (-1)^m m \sum_{r_1 + 2r_2 + \cdots + mr_m = m \atop r_1\ge 0, \ldots, r_m\ge 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}.</math>

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

: <math>p_m = (-1)^m m \sum_{k=1}^m \frac{1}{k} \hat{B}_{m,k}(-e_1,\ldots,-e_{m-k+1}),</math>

または[[母関数]]として<ref>{{MathWorld|title=Symmetric Polynomial}}</ref>表すことができる。

: <math>
\begin{align}
\sum_{k=1}^{\infty} (-1)^{k-1} p_k \frac{t^k}{k} & = \ln\left(1+e_1t+e_2t^2+e_3t^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_1e_2+3e_3\right) t^3 + \cdots, 
\end{align} 
</math>

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

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

: <math>\begin{align}
 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{align}</math>

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

: <math>\begin{align}
 p_1 &= + h_1,\\
 p_2 &= - h_1^2 + 2 h_2,\\
 p_3 &= + h_1^3 - 3 h_2 h_1 + 3 h_3,\\
 p_4 &= - h_1^4 + 4 h_2 h_1^2 - 4 h_3 h_1 - 2 h_2^2 + 4 h_4,\\
 p_5 &= + h_1^5 - 5 h_2 h_1^3 + 5 h_2^2 h_1 + 5 h_3 h_1^2 - 5 h_3h_2 - 5 h_4 h_1 + 5 h_5,\\
 p_6 &= - h_1^6 + 6 h_2 h_1^4 - 9 h_2^2 h_1^2 - 6 h_3 h_1^3 + 2 h_2^3 + 12 h_3 h_2 h_1 + 6 h_4 h_1^2 - 3 h_3^2 - 6 h_4 h_2 - 6 h_1 h_5 + 6h_6,\\
\end{align}</math>

基本対称式の場合と比べ、''e<sub>i</sub>'' のかわりに''h<sub>i</sub>''となっており、各項の符号が異なっている。

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

: <math>p_m = -\sum_{r_1 + 2r_2 + \cdots + mr_m = m \atop r_1\ge 0, \ldots, r_m \ge 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}</math>

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

: <math>\begin{align}
  e_1 &= 1p_1,\\
 2e_2 &= e_1p_1 - 1p_2,\\
 3e_3 &= e_2p_1 - e_1p_2 + 1p_3,\\
    & \,\,\,\vdots \\
 ne_n &= e_{n-1}p_1 - e_{n-2} p_2 + \cdots + (-1)^ne_1p_{n - 1} + (-1)^{n - 1}p_n\\
\end{align}</math>

について、<math>p_1, -p_2, p_3, \ldots, (-1)^np_{n-1}</math>を未知変数として、連立方程式を解く。これにより以下の表現が得られる。

: <math>\begin{align}
 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{align}</math>

<math>p_n</math>の代わりに<math>e_n</math>を解くと以下のようになる（Macdonald 1979,p.20）：

: <math>\begin{align}
 e_n = \frac1{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 = \frac1{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{align}</math>

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

=== ''n'' = ''k'' の場合による導出 ===
以下の式から、k変数のk番目のニュートンの公式を取得できる。

: <math> \prod_{i=1}^k (t - x_i) = \sum_{i=0}^k (-1)^{k-i} e_{k-i}(x_1,\ldots,x_k)t^i</math>

ここで、''x<sub>j</sub>'' に ''t'' を代入する。

: <math>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</math>

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

: <math>0= (-1)^kke_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),</math>

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

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

=== 係数の比較 ===
また別の導出は、[[形式的冪級数|形式的べき級数]] ''R[t]'' を用いて得ることができる。ここで ''R'' は''x''<sub>1</sub>,..., ''x<sub>n</sub>'' を変数とする整数上の多項式環 '''Z'''[''x''<sub>1</sub>,..., ''x<sub>n</sub>''] である。

基本的な関係

: <math>\prod_{i=1}^n (t - x_i) = \sum_{k=0}^n (-1)^{k} a_k t^{n-k}</math>

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

: <math>\prod_{i=1}^n (1- x_it) = \sum_{k=0}^n (-1)^{k} a_k t^k.</math>

両辺を入れ替え、''a<sub>i</sub>'' を基本対称式で表すことで以下の式を得る。

: <math>\sum_{k=0}^n (-1)^{k} e_k(x_1,\ldots,x_n) t^k=\prod_{i=1}^n (1- x_it).</math>

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

: <math>\begin{align}
 \sum_{k=0}^n (-1)^{k}k e_k(x_1,\ldots,x_n) t^k 
  &=   t \sum_{i=1}^n \left[(-x_i) \prod\nolimits_{j \neq i}(1 - x_jt)\right]\\
  &= -\left(\sum_{i=1}^n \frac{x_it}{1 - x_it}\right) \prod\nolimits_{j=1}^n (1 - x_jt)\\
  &= -\left[\sum_{i=1}^n \sum_{j=1}^\infty(x_it)^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{align}</math>

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

: <math>\frac{X}{1 - X} = X + X^2 + X^3 + X^4 + X^5 + \cdots,</math>

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

: <math>(-1)^{k}k e_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),</math>

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

== 参照 ==
* [[対称式]]

== 参考文献 ==


* {{Cite book|last=Tignol, Jean-Pierre|title=Galois' theory of algebraic equations|location=Singapore|publisher=World Scientific|year=2001|isbn=978-981-02-4541-2}}
* {{Cite book|last=Bergeron, F.|last2=Labelle, G.|last3=Leroux, P.|title=Combinatorial species and tree-like structures|location=Cambridge|publisher=[[Cambridge University Press]]|year=1998|isbn=978-0-521-57323-8|url=https://archive.org/details/combinatorialspe0000berg}}
* {{Cite book|last=Cameron, Peter J.|author-link=Peter Cameron (mathematician)|title=Permutation Groups|url=https://archive.org/details/permutationgroup0000came|location=Cambridge|publisher=Cambridge University Press|year=1999|isbn=978-0-521-65378-7}}
* {{Cite book|last=Cox, David|author-link=David A. Cox|last2=Little, John|last3=O'Shea, Donal|title=Ideals, Varieties, and Algorithms|location=New York|publisher=Springer-Verlag|year=1992|isbn=978-0-387-97847-5}}
* {{Cite conference|last=Eppstein, D.|author-link=David Eppstein|last2=Goodrich, M. T.|author2-link=Michael T. Goodrich|title=Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible Bloom filters|book-title=[[Workshop on Algorithms and Data Structures|Algorithms and Data Structures, 10th International Workshop, WADS 2007]]|pages=637–648|publisher=Springer-Verlag, Lecture Notes in Computer Science 4619|year=2007|bibcode=2007arXiv0704.3313E}}
* {{Cite book|last=Littlewood, D. E.|title=The theory of group characters and matrix representations of groups|publisher=Oxford University Press|location=Oxford|year=1950|isbn=0-8218-4067-3|nopp=true|page=viii+310}}
* {{Cite book|last=Macdonald, I. G.|title=Symmetric functions and Hall polynomials|series=Oxford Mathematical Monographs|publisher=The Clarendon Press, Oxford University Press|location=Oxford|year=1979|isbn=0-19-853530-9|nopp=true|page=viii+180|mr=553598}}
* {{Cite book|last=Macdonald, I. G.|title=Symmetric functions and Hall polynomials|edition=Second|series=Oxford Mathematical Monographs|publisher=Oxford Science Publications. The Clarendon Press, Oxford University Press|location=New York|year=1995|isbn=0-19-853489-2|page=x+475|mr=1354144}}
* {{Cite journal|last=Mead, D.G.|year=1992|title=Newton's Identities|journal=The American Mathematical Monthly|volume=99|issue=8|pages=749–751|publisher=Mathematical Association of America|DOI=10.2307/2324242|JSTOR=2324242}}
* {{Cite book|last=Stanley, Richard P.|author-link=Richard P. Stanley|title=Enumerative Combinatorics, Vol. 2|publisher=Cambridge University Press|year=1999|isbn=0-521-56069-1|id=(hardback). (paperback)}}
* {{Cite book|last=Sturmfels, Bernd|author-link=Bernd Sturmfels|title=Algorithms in Invariant Theory|location=New York|publisher=Springer-Verlag|year=1992|isbn=978-0-387-82445-1}}
* {{Cite book|last=Tucker|first=Alan|author-link=Alan Tucker|title=Applied Combinatorics|url=https://archive.org/details/appliedcombinato00tuck|edition=5/e|location=New York|publisher=Wiley|year=1980|isbn=978-0-471-73507-6}}

* MathWorldの[http://mathworld.wolfram.com/Newton-GirardFormulas.html Newton–Girard式]
* 数学雑誌における[https://www.jstor.org/stable/2690982 ニュートンのアイデンティティの行列証明]
* [http://stellar.mit.edu/S/course/6/sp10/6.256/courseMaterial/topics/topic2/lectureNotes/lecture-05/lecture-05.pdf 実根数への応用]
* [https://www.math.rutgers.edu/~zeilberg/mamarimY/Zeilberger_y1984_p319.pdf DoronZeilbergerによるニュートンのアイデンティティの組み合わせ]論的証明

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}} 

{{DEFAULTSORT:にゆうとんのこうとうしき}}
[[Category:ガロア理論]]
[[Category:代数的組合せ論]]
[[Category:恒等式]]
[[Category:線型代数学]]
[[Category:不変式論]]
[[Category:群論]]
[[Category:アイザック・ニュートン]]
[[Category:数学に関する記事]]