ニュートンの恒等式
ニュートンの恒等式(Newton's identity)、ジラール-ニュートンの公式(Girard–Newton formula)は、べき乗和と基本対称式との関係を与える。この関係は、単行多項式Pの根が与えられたとき、それらのk乗の和が、根を明示的に求めなくても、Pの係数によって表されることを意味する。この恒等式は1666年にアイザック・ニュートンによって発見された。実際にはこの式はこれよりも前に、アルベルト・ジラールにより発見されている(1629)。この恒等式はガロア理論、不変式論、群論、組み合わせ論を含む数学の多くの分野での応用や、一般相対性理論を含む数学以外のさらなる応用をもつ。
x1,...,xnを変数とし、 k ≥1について pk(x1,...,xn )を k次のべき乗和:
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個の相異なる変数の関の和である。
\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}
このとき、ニュートンの恒等式は次のように述べることができる:
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 = \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について成り立つ
具体的には以下のようになる。
\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}
これらの等式は変数の数nに依存しない。(ただし、左辺が0になる位置は変数に依存する)
\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}
これらの方程式により、eiをpkにより表すことができる。また逆に
\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}
もなりたつ。一般に
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,\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を根を持つ多項式は、以下のように展開できる。
\prod_{i=1}^n \left( x - x_i \right) = \sum_{k=0}^n (-1)^{k} e_{k} x^{n-k},
ここで、e_k(x_1,\dots,x_n) は上で定義された対称多項式である。根のべき和を考えると
p_k(x_1,\dots,x_n)= \sum_{i=1}^n x_i^k
x_1,\dots,x_nを根に持つ多項式の係数はべき和により次のように表すことができる。
\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}
この方法で多項式を定式化すると、Delves や Lyness の方法により解析関数の零点を見つけるのに役立つ。
上記の多項式が行列Aの特性多項式である場合(特にAが多項式の同伴行列である場合)、根 x_iは行列の固有値となる。また、任意の正の整数kに対して、行列 Akは固有値 x_i^kを持ち、これらの和はAkのトレース:
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 のすべての置換について不変な多項式は基本対称式により表される。これは対称多項式の基本定理として知られている一般的な事実であり、ニュートンの恒等式はべき和対称多項式について明示的な関係を示しいる。
単項多項式 \textstyle t^n+\sum_{k=1}^n (-1)^{k} a_k t^{n-k} にこれを適用すれば、この多項式の根についての対称式S(x1,...,xn)は、係数を用いた多項式P(a1,...,an)により表せることがわかる。このことはガロア理論の一般的結果である。
ニュートンの恒等式は、基本対称多項式をべき和対称多項式で表現することを可能にする。これは、任意の対称多項式がべき和で表現できることを示している。
ニュートンの恒等式に関連する恒等式がいくつかある。
次数 k の単項式の和である完全斉次対称式 hkについても、ニュートン恒等式と同様に以下の恒等式が存在する。ニュートン恒等式とは異なり、マイナスの符号が現れない。
kh_k = \sum_{i=1}^kh_{k-i}p_i,
この式はすべてのn≥k≥1に対し成り立つ。ニュートンの公式とは異なり、左辺は大きなkに対して0にはならない。また、左辺には多くのゼロ項が含まれている。右側には、これまで以上にゼロ以外の項が含まれています。具体的には以下のようになる。
\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}
これらの関係は、以下のような母関数の恒等式の係数を比較することで確認できる。
\sum_{k=0}^\infty h_k(X_1, \dots, X_n)t^k = \prod_{i=1}^n\frac1{1 - X_it}.
前述のように、ニュートンの公式を使用して、べき和により基本対称多項式を再帰的に表現できる。
\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}
一般式は次のように簡単に表すことができる。
e_n = \frac{(-1)^n}{n!} B_{n}(- p_1, -1! p_2, - 2! p_3, \dots, - (n-1)! p_n ),
ここで、Bn は完全指数ベル多項式である。この式は、母関数の恒等式を与える。
\sum_{n=0}^\infty e_n \,X^n = \exp\left(\sum_{n=1}^\infty \frac{(-1)^{n+1}{n} p_n \,X^n \right).
この関係を単項多項式に適用すれば、係数を根のべき和で表すことができる。
完全斉次対称式についても同様の関係式を得ることができる。
\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}
この場合もベル多項式により以下のように表される。
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と表される。ここで
N=\prod_{i=1}^l(m_i!\,i^{m_i})
である。このN は、対応する巡回の種類と可換な置換の数を表す。
これは、次の帰納的ステップを検討することで証明できる。
\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}
ニュートンの恒等式から基本対象式によりべき和を表すことができる。
\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}
最初の4つの公式は、アルベールジラールによってニュートン以前の1629年に得られた。
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}.
通常のベル多項式により次のように簡単に表すことができる。
p_m = (-1)^m m \sum_{k=1}^m \frac{1}{k} \hat{B}_{m,k}(-e_1,\ldots,-e_{m-k+1}),
または母関数として表すことができる。
\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}
これはベル多項式の指数的母関数と類似している。
上式は、次の帰納法のステップを検討することで証明できる。
\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}
最後に、完全同次対称式によるべき和の表現を示す。
\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}
基本対称式の場合と比べ、ei のかわりにhiとなっており、各項の符号が異なっている。
一般式は次のとおりである。
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}
ニュートンの恒等式は、クラメルの法則を適用することで、行列式の形で表すことができる。以下に示すニュートンの恒等式:
\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}
について、p_1, -p_2, p_3, \ldots, (-1)^np_{n-1}を未知変数として、連立方程式を解く。これにより以下の表現が得られる。
\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}
p_nの代わりにe_nを解くと以下のようになる(Macdonald 1979,p.20):
\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}
ニュートンの恒等式は、初等代数で簡単に確認できる。
以下の式から、k変数のk番目のニュートンの公式を取得できる。
\prod_{i=1}^k (t - x_i) = \sum_{i=0}^k (-1)^{k-i} e_{k-i}(x_1,\ldots,x_k)t^i
ここで、xj に t を代入する。
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
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),
ここで i = 0 の項は、p0 の定義がないため、取り除かれている。この式は k 変数 k 番目のニュートンの恒等式を表している。
変数の数が n < k の場合は、k−n 個の変数をゼロとすることで得られる。また変数の数が n > k の場合、n 個の変数から k 個を選び、そのすべての組み合わせに対して k 変数 k 番目のニュートン恒等式を足し合わせることで得られる。
また別の導出は、形式的べき級数 R[t] を用いて得ることができる。ここで R はx1,..., xn を変数とする整数上の多項式環 Z[x1,..., xn] である。
\prod_{i=1}^n (t - x_i) = \sum_{k=0}^n (-1)^{k} a_k t^{n-k}
ここで t を1/t で置き換え、両辺に tn をかけることにより、負指数のべき乗を取り除く。
\prod_{i=1}^n (1- x_it) = \sum_{k=0}^n (-1)^{k} a_k t^k.
両辺を入れ替え、ai を基本対称式で表すことで以下の式を得る。
\sum_{k=0}^n (-1)^{k} e_k(x_1,\ldots,x_n) t^k=\prod_{i=1}^n (1- x_it).
両辺をt について形式的に微分し、t をかけることで、以下の式を得る。
\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}
ここで、右辺の多項式はまず有理関数に変形され、次に以下の公式により変形される。
\frac{X}{1 - X} = X + X^2 + X^3 + X^4 + X^5 + \cdots,
最後にt j の係数を比較することで以下の式が得られる。