對稱多項式與牛頓恆等式
對稱多項式
Vieta 公式
Vieta 公式給出了多項式方程根與係數的關係, 而不必實際地把這些根求出來, 由於高次多項式方程的求解一般而言非常困難, 該公式極大地簡化了對多項式方程的研究.
由代數基本定理知, 一個 $n$ 次多項式方程在複數域上必有 $n$ 個根 (含重根), 所以任何一個 $n$ 次首一多項式 $f(x)=x^n+\sum_{i=1}^{n}a_i x^{n-i}$ 必能表示為如下形式:
$$f(x)=(x-x_1)(x-x_2)\cdots(x-x_n)$$
直接展開比較係數即得
$$
\begin{cases}
a_1 = (-1)\sum_{i=1}^n x_i \\
a_2 = (-1)^2\sum_{i<j} x_i\thinspace x_j \\
\cdots\cdots \\
a_k = (-1)^k\sum_{i_1<\cdots<i_k} x_{i_1}x_{i_2}\cdots x_{i_k} \\
\cdots\cdots \\
a_n = (-1)^n x_1 x_2\cdots x_n
\end{cases}
$$
我們得到 $n$ 個關於 $x_1,\cdots,x_n$ 的多項式, 分別記作
$$
\begin{cases}
s_1 = \sum_{i=1}^n x_i \\
s_2 = \sum_{i<j} x_i\thinspace x_j \\
\cdots\cdots \\
s_k = \sum_{i_1<\cdots<i_k} x_{i_1}x_{i_2}\cdots x_{i_k} \\
\cdots\cdots \\
s_n = x_1 x_2\cdots x_n
\end{cases}
$$
注意到 $s_k(x_1,\cdots,x_n)$ 在 $(x_1,\cdots,x_n)$ 的任意置換下保持不變, 即
$$s_k(x_1,x_2,\cdots,x_n)=s_k\left(x_{\sigma(1)},x_{\sigma(2)},\cdots,x_{\sigma(n)}\right)$$
恆成立, 其中 $\sigma\in S_n$ 是 $(1,\cdots,n)$ 的任一置換.
因此, 我們稱多項式 $s_k$ 為 $n$ 元初等對稱多項式 (elementary symmetric polynomial).
對稱多項式
一般地, 設 $A$ 為整環, $n$ 元多項式 $f\in A\left[x_1,\cdots,x_n\right]$, 若對任意 $\sigma\in S_n$ 都有
$$f(x_1,x_2,\cdots,x_n) = f\left(x_{\sigma(1)},x_{\sigma(2)},\cdots,x_{\sigma(n)}\right)$$
則稱 $f$ 為對稱多項式.
對 $f\in A\left[x_1,\cdots,x_n\right]$ 和 $\sigma\in S_n$, 令
$$(\sigma\circ f)(x_1,x_2,\cdots,x_n) = f\left(x_{\sigma(1)},x_{\sigma(2)},\cdots,x_{\sigma(n)}\right)$$
則 $\sum_{\sigma\in S_n}\sigma\circ f$ 和 $\prod_{\sigma\in S_n}\sigma\circ f$ 都是對稱多項式, 又
$$
\begin{align*}
\sigma\circ (fg) &= (\sigma\circ f)(\sigma\circ g) \\
\sigma\circ (f+g) &= \sigma\circ f+\sigma\circ g
\end{align*}
$$
所以 $A$ 上的全體 $n$ 元對稱多項式構成多項式環 $R=A\left[x_1,\cdots,x_n\right]$ 的一個子環. 進而, 對任意 $F\in A\left[y_1,\cdots,y_m\right]$ 和對稱多項式 $f_1,\cdots,f_m\in R$, $F(f_1,\cdots,f_m)$ 是 $R$ 中的對稱多項式.
對稱多項式基本定理
對稱多項式基本定理是說, 整環 $A$ 上的對稱多項式必可唯一表成初等對稱多項式的多項式, 即任意對稱多項式 $f\in A\left[x_1,\cdots,x_n\right]$, 必存在 $g\in A\left[y_1,\cdots,y_m\right]$ 使得
$$f(x_1,x_2,\cdots,x_n) = g(s_{i_1},s_{i_2},\cdots,s_{i_m})$$
其中 $s_{i_1},\cdots,s_{i_m}$ ($0\leq i_1<\cdots<i_m\leq n$) 為 $m$ 個 $n$ 元初等對稱多項式.
證明即給出表示法. 首先容易看出, 任意對稱多項式可以表為若干齊次對稱多項式之和, 故只需分別處理齊次部分即可. 設 $f(x_1,\cdots,x_n)$ 為齊次對稱多項式, 我們為它的每一項 $a_{i}x_1^{l_{i,1}}x_2^{l_{i,2}}\cdots x_n^{l_{i,n}}$ 指派一個有序多元組 $L_i=(l_{i,1},\cdots,l_{i,n})$, 定義字典序如下:
- 若 $l_{i,1}<l_{j,1}$, 則 $L_i<L_j$,
- 若 $l_{i,1}=l_{j,1}$, $\cdots$, $l_{i,k}=l_{j,k}$, $l_{i,k+1}<l_{j,k+1}$, 則 $L_i<L_j$.
按字典序由大到小排列 $f$ 的項, 那麼其首項 $a_1 x_1^{l_1}x_2^{l_2}\cdots x_n^{l_n}$ 必滿足 $l_1\geq\cdots\geq l_n\geq 0$, 否則由對稱性立即能推出矛盾. 令 $\varphi_1=a_1 s_1^{l_1-l_2}s_2^{l_2-l_3}\cdots s_n^{l_n}$, 則 $\varphi_1$ 的首項恰為
$$a_1 x_1^{l_1-l_2}(x_1x_2)^{l_2-l_3}\cdots(x_1\cdots x_n)^{l_n}=a_1 x_1^{l_1}x_2^{l_2}\cdots x_n^{l_n}$$
而 $\varphi_1$ 的其餘項按字典序均小於該項. 因此, $g_1=f-\varphi_1$ 是一個有更 “小” 首項的對稱多項式 (對稱多項式之和仍為對稱多項式), 並且 $g_1$ 顯然是齊次的.
這樣做下去便得到一串多項式 $g_1,g_2,\cdots$, 由每個 $g_i$ 的對稱性知, 其首項中 $x_1$ 的次數必不為 $0$ (除非 $g_i=0$), 由於 $L_1$ 逐次減小, 在有限次操作後, 必然有 $l_{1,1}=1$. 又因為 $l_{1,1}\geq\cdots\geq l_{1,n}\geq 0$, 不妨假設 $g_m$ 的首項為 $a_1’x_1\cdots x_r$, 其中 $r\leq n$, 由齊次性和對稱性可知, $g_m=a_1’\sum_{i_1<\cdots<i_r} x_{i_1}x_{i_2}\cdots x_{i_r}$, 而這正是 $a_1’ s_r$, 只需再減一次就能得到 $0$. 把上述過程逆回去就得到要求的關於 $s$ 的多項式.
Newton 恆等式
接下來引入一類特殊的對稱多項式 $p_k(x_1,\cdots,x_n)=\sum_{i=1}^n x_i$, 稱之為 $k$ 次等冪和. Newton 恆等式給出了等冪和 $p$ 與基本對稱多項式 $s$ 的關係.
規定 $s_0=1$, $s_m=0$ $(m>n)$, 則
$$ks_k + \sum_{i=1}^k(-1)^i p_is_{k-i} = 0$$
特別地, 當 $k>n$ 時,
$$\sum_{i=k-n}^k(-1)^i p_is_{k-i} = 0$$
下面提供兩種證明.
第一種證明
(聽說這是 Kostrikin 的證法. )
令 $f(x)=\prod_{i=1}^n(x-x_i)=\sum_{i=1}^n(-1)^i s_i x^{n-i}$, 兩邊對數求導得
$$\frac{f’(x)}{f(x)} = \sum_{i=1}^n \frac{1}{x-x_i}$$
把 $1/(x-x_i)$ 展開為冪級數
$$\frac{1}{x-x_i} = \frac{1}{x}\sum_{j=0}^{\infty}\left(\frac{x_i}{x}\right)^j$$
所以
$$\text{RHS} = \frac{1}{x}\sum_{i=1}^n\sum_{j=0}^{\infty}\frac{x_i^j}{x^j} = \frac{1}{x}\sum_{j=0}^{\infty}\frac{p_j}{x^j}$$
即
$$xf’(x) = \sum_{i=1}^n(-1)^i is_i x^{n-i} = \left(\sum_{i=1}^n(-1)^i s_i x^{n-i}\right)\left(\sum_{j=0}^{\infty}\frac{p_j}{x^j}\right)$$
當 $k\leq n$ 時, 比較 $n-k$ 次項係數即得
$$(-1)^k ks_k = \sum_{i=0}^{k-1} (-1)^i p_{k-i} s_i$$
當 $k>n$ 時, 左側負次冪項係數為 $0$, 所以
$$0 = \sum_{i=k-n}^k (-1)^i p_{k-i} s_i$$
(右式仍為 $n-k$ 次項係數和) $\square$
第二種證明
下面是一種非常巧妙的組合證明, 由 Doron Zeilberger 發表於1984年.
考慮由有序對 $(A,j^l)$ 構成的集合 $\mathscr{A}(n,k)$, 其中
- $A$ 是 $\lbrace 1,\cdots,n\rbrace$ 的子集,
- $j\in\lbrace 1,\cdots,n\rbrace$,
- $|A|+l=k$, 其中 $|A|$ 表示 $A$ 中元素個數,
- $l\geq 0$, 若 $l=0$ 則 $j\in A$.
定義 $(A,j^l)$ 的權重 $w(A,j^l)$ 為 $w(A,j^l)=(-1)^{|A|}(\prod_{a\in A}x_a)x_j^l$. 那麼顯然,
$$\sum_{(A,j^l)\in\mathscr{A}}w(A,j^l) = \sum_{i=0}^{k-1} (-1)^i p_{k-i} s_i + (-1)^k ks_k$$
在右側和式中令 $i=|A|<k$, $k-i=l$.
故只需證明所有權重的和為 $0$ 即可. 為此, 我們定義映射 $T:\mathscr{A}\to\mathscr{A}$ 如下:
$$
T(A,j^l)=\begin{cases}
(A\setminus\lbrace j\rbrace,j^{l+1}), &j\in A \\
(A\cup\lbrace j\rbrace,j^{l-1}), &j\not\in A
\end{cases}
$$
於是有 $w(A,j^l)=-w(T(A,j^l))$, 且 $T\circ T=\text{id}_{\mathscr{A}}$. 因此 $T$ 為雙射, $w(A,j^l)$ 和 $w(T(A,j^l))$ 可配成互相抵消的對, 所以權重的總和為 $0$. $\square$
這種證法也暗示了 Newton 恆等式在本質上是容斥原理的一種特殊形式.
應用
通過 Newton 恆等式, 我們可以遞歸地用 $p$ 表示出 $s_k$
$$s_k=\frac{1}{k}\sum_{i=1}^k (-1)^{i-1}p_i s_{k-1}$$
前文已經證明, $A$ 上的任意對稱多項式可以表示為 $s$ 的多項式, 進而, 它們都能表示為 $p$ 的多項式. 因此, $k$ 次等冪和 ($k=1,\cdots,n$) 之集生成了 $n$ 元對稱多項式環. 但需注意一點, 任何整係數對稱多項式表示為 $s$ 的多項式, 其係數仍是整數 (從構造過程可以看出), 而 $s_k$ 關於 $p$ 的多項式表示則不一定是整係數的.
進一步地, 我們可以用行列式來求出 $s$ 與 $p$ 的顯式表達式. 根據 Newton 恆等式列出如下方程組:
$$
\begin{cases}
s_1 - p_1 = 0 \\
2s_2 - p_1s_1 + p_2 = 0 \\
3s_3 - p_1s_2 +p_2s_1 - p_3 =0 \\
\cdots\cdots \\
ks_k - p_1s_{k-1} + \cdots + (-1)^k p_k = 0
\end{cases}
$$
把 $p_1,\cdots,p_k$ 看作 $k$ 個未知數, 用 Cramer 法則解方程組
$$
\begin{pmatrix}
-1&0&0&\cdots&0\\
-s_1&1&0&\cdots&0\\
-s_2&s_1&-1&\cdots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
-s_{k-1}&s_{k-2}&-s_{k-3}&\cdots&(-1)^k
\end{pmatrix}
\begin{pmatrix}p_1\\p_2\\p_3\\\vdots\\p_k\end{pmatrix}
= \begin{pmatrix}-s_1\\-2s_2\\-3s_3\\\vdots\\-ks_k\end{pmatrix}
$$
得到
$$
\begin{align}
p_k &= \left.\begin{vmatrix}
-1&0&\cdots&-s_1\\
-s_1&1&\cdots&-2s_2\\
\vdots&\vdots&\ddots&\vdots\\
-s_{k-1}&s_{k-2}&\cdots&-ks_k
\end{vmatrix} \middle/
\begin{vmatrix}
-1&0&\cdots&0\\
-s_1&1&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
-s_{k-1}&s_{k-2}&\cdots&(-1)^k
\end{vmatrix}\right. \\
&= (-1)^{k-1} \begin{vmatrix}
1&0&\cdots&s_1\\
s_1&1&\cdots&2s_2\\
\vdots&\vdots&\ddots&\vdots\\
s_{k-1}&s_{k-2}&\cdots&ks_k
\end{vmatrix} \\
&= \begin{vmatrix}
s_1&1&0&0&\cdots&0\\
2s_2&s_1&1&0&\cdots&0\\
3s_3&s_2&s_1&1&\cdots&0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
(k-1)s_{k-1}&s_{k-2}&s_{k-3}&s_{k-4}&\cdots&1\\
ks_k&s_{k-1}&s_{k-2}&s_{k-3}&\cdots&s_1
\end{vmatrix}
\end{align}
$$
反過來把 $s_1,\cdots,s_k$ 看作未知數, 解方程組
$$
\begin{pmatrix}
1&0&0&\cdots&0\\
p_1&-2&0&\cdots&0\\
p_2&-p_1&3&\cdots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
p_{k-1}&-p_{k-2}&p_{k-3}&\cdots&(-1)^{k-1}k
\end{pmatrix}
\begin{pmatrix}s_1\\s_2\\s_3\\\vdots\\s_k\end{pmatrix}
= \begin{pmatrix}p_1\\p_2\\p_3\\\vdots\\p_k\end{pmatrix}
$$
得到
$$
\begin{align}
s_k &= (-1)^{k-1}\left.\begin{vmatrix}
1&0&\cdots&p_1\\
p_1&2&\cdots&p_2\\
\vdots&\vdots&\ddots&\vdots\\
p_{k-1}&p_{k-2}&\cdots&p_k
\end{vmatrix} \middle/
\begin{vmatrix}
1&0&\cdots&0\\
p_1&2&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
p_{k-1}&p_{k-2}&\cdots&k
\end{vmatrix}\right. \\
&= \frac{1}{k!} \begin{vmatrix}
p_1&1&0&0&\cdots&0\\
p_2&p_1&2&0&\cdots&0\\
p_3&p_2&p_1&3&\cdots&0\\
\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\
p_{k-1}&p_{k-2}&p_{k-3}&p_{k-4}&\cdots&k-1\\
p_k&p_{k-1}&p_{k-2}&p_{k-3}&\cdots&p_1
\end{vmatrix}
\end{align}
$$
例如當 $k=3$ 時, 據此很容易就能求出
$$
s_3 = \frac{1}{6}\begin{vmatrix}
p_1&1&0\\
p_2&p_1&2\\
p_3&p_2&p_1
\end{vmatrix}
= \frac{1}{6}(p_1^3-3p_1p_2+2p_3)
$$
計算判別式
$n$ 次多項式 $f(x)=x^n+\sum_{i=1}^{n}a_i x^{n-i}$ 有重根的判別式 $D_f$ 定義為
$$
D_f = \prod_{i<j}(x_i-x_j)^2 = \begin{vmatrix}
1&1&\cdots&1\\
x_1&x_2&\cdots&x_n\\
x_1^2&x_2^2&\cdots&x_n^2\\
\vdots&\vdots&\ddots&\vdots\\
x_1^{n-1}&x_2^{n-1}&\cdots&x_n^{n-1}
\end{vmatrix}^2
$$
其中,
$$
V = \begin{vmatrix}
1&1&\cdots&1\\
x_1&x_2&\cdots&x_n\\
x_1^2&x_2^2&\cdots&x_n^2\\
\vdots&\vdots&\ddots&\vdots\\
x_1^{n-1}&x_2^{n-1}&\cdots&x_n^{n-1}
\end{vmatrix} = \prod_{i<j}(x_i-x_j)
$$
是一個 Vandermonde 行列式. 之所以要取平方, 是因為平方後成為一個對稱多項式, 更容易計算. 顯然, $f$ 有重根當且僅當 $D_f=0$.
根據 Vandermonde 行列式的性質, 我們有
$$
D_f = \det(V\cdot V^T) = \det\begin{pmatrix}
n&p_1&p_2&\cdots&p_{n-1}\\
p_1&p_2&p_3&\cdots&p_n\\
p_2&p_3&p_4&\cdots&p_{n+1}\\
\vdots&\vdots&\vdots&\ddots&\vdots\\
p_{n-1}&p_{n}&p_{n+1}&\cdots&p_{2n-2}
\end{pmatrix}
$$
上文已給出 $p_k$ 關於 $s$ 的表達式, 又由 Vieta 公式 $s_k=(-1)^k a_k$, 代入上式即可得到 $D_f$ 關於係數的表達式.
若多項式有 $n$ 個實根…
首先來看實係數二次方程 $a_0 x^2+a_1 x+a_2=0$, 假設該方程有兩個非 $0$ 實根且 $a_1=0$, 則必有 $a_0 a_2<0$. 那麼, 對 $n$ 次多項式方程是否有類似的結論成立?
——這是前不久我的一個同學遇到的面試題. 結論並不難猜, 若 $n$ 次實係數多項式 $f(x)=\sum_{i=0}^{n}a_i x^{n-i}=0$ 有 $n$ 個非 $0$ 實根且 $a_k=0$ ($k<n$), 則必有 $a_{k-1}a_{k+1}<0$, 問題在於該如何證明. 如果 $n$ 個實根都為正數, 那麼證明是很容易的, 只需直接計算 $s_{k-1}s_{k+1}-s_k^2$ 就能看出該值恆小於 $0$; 而對於一般情況, 我想了半個下午無果, 所以就去網上找答案了 (懶了).
最後在 Hardy et al. 的名著《不等式》中找到了這個結論. 事實上, 書中證明的是一個更強的不等式, 但很容易從中推導出我們所需的結論. (書裡說這是 Newton 的結果, 但我沒有找到原始出處. )
記 $\sum!F(a_1,\cdots,a_n)=\sum_{\sigma\in S_n}F\left(a_{\sigma(1)},\cdots,a_{\sigma(n)}\right)$ 為對 $a$ 進行任意置換形成的 $n!$ 個項的和 (即對稱和). 令
$$\left[\alpha_1,\cdots,\alpha_n\right] = \frac{1}{n!}\sum!F(a_1^{\alpha_1},\cdots,a_n^{\alpha_n})$$
為 $n$ 個不同 $a_i$ 的若干次冪相乘形成的 $n!$ 項的算術平均, 它在 $\alpha$ 的任意置換下保持不變, 故稱為對稱平均.
設 $x_1,\cdots,x_n$ 是 $n$ 個非 $0$ 實數, 則
$$s_k = \frac{1}{k!(n-k)!}\sum!x_1\cdots x_k$$
其中 $k!(n-k)!$ 為等價的項被計數的次數 (也就是組合數的分母). 令
$$d_k = \frac{k!(n-k)!}{n!}s_k = [\underbrace{1,\cdots,1}_{k},0,\cdots,0]$$
規定 $d_0=s_0=1$. 下面就來證明 $d_{k-1}d_{k+1}<d_k^2$.
令
$$
\begin{align}
f(x,y) &= (x-x_1 y)(x-x_2 y)\cdots(x-x_n y)\\
&= d_0 x^n+\binom{n}{1}d_1 x^{n-1}y+\binom{n}{2}d_2 x^{n-2}y^2+\cdots+d_n y^n
\end{align}
$$
對其多次微分得到導出方程
$$d_{k-1}x^2 + 2d_k xy + d_{k+1}y^2 = 0$$
由於 $x_i\not=0$, $x/y=0$ 不是原方程的根. 因此, $x/y=0$ 不是導出方程的重根, 所以任意兩個相鄰的 $d$ 不同時為 $0$, 故導出方程不是恆等方程. 根據廣義 Rolle 定理, 導出方程必有兩個實根. 於是有
$$d_{k-1}d_{k+1}\leq d_k^2$$
等號成立, 當且僅當所有 $x_i$ 均相等.
進而,
$$
\begin{align}
s_{k-1}s_{k+1} &= \frac{n!}{(k-1)!(n-k+1)!}d_{k-1}\cdot\frac{n!}{(k+1)!(n-k-1)!}d_{k+1}\\
&= \frac{k}{k+1}\cdot\frac{n-k}{n-k+1}\cdot\left(\frac{k!(n-k)!}{n!}\right)^2 d_{k-1}d_{k+1}\\
&< \left(\frac{k!(n-k)!}{n!}\right)^2 d_{k-1}d_{k+1}\\
&\leq \left(\frac{k!(n-k)!}{n!}\right)^2 d_k^2 = s_k^2
\end{align}
$$
特別地, 當 $s_k=0$ 時, $s_{k-1}s_{k+1}<0$. $\square$
這樣, 原問題大致就解決了. 唯一留下的一個小瑕疵是所有實根都非 $0$ 這個條件, 書中說要求非 $0$ 是為了簡化取等條件的討論, 如果進一步推廣該結論, 應該可以把這個條件去掉. 另外, 這裡得到的僅僅是 $n$ 次多項式有 $n$ 個非 $0$ 實根的必要條件, 而不是充分條件, 是否能找到一個充分條件甚至充要條件? 這些問題就留待以後思考了.