整数分拆

设非负整数数列 $\mathit{\lambda }:=({\lambda }_1,{\lambda }_2,\dots )$ 只有有限项非零且（不严格）单调递减．定义长度 $\mathcal{L}(\mathit{\lambda })$ 为其非零项元素个数；定义 $\mathcal{S}(\mathit{\lambda })$ 为其非零项元素之和．此时称 $\mathit{\lambda }$ 是整数 $\mathcal{S}(\mathit{\lambda })$ 的一个长度为 $\mathcal{L}(\mathit{\lambda })$ 的分拆．

由于分拆只有有限项非零，对大于等于 $\mathcal{L}(\mathit{\lambda })$ 的非负整数 $k$，我们也常省略从第 $k+1$ 项开始的全为 $0$ 的项，将 $\mathit{\lambda }$ 直接记为长度为 $k$ 的非负整数数组 $({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_k)$．

Ferrers diagram 和 Young diagram 是图示分拆的常见方法．

通过沿主对角线翻转分拆的 Ferrers diagram 或 Young diagram，可以定义分拆的转置．分拆 $\lambda$ 的转置记为 ${\lambda }^{\mathrm{T}}$．转置后分拆的长度变为原分拆的首项，而首项变为原分拆的长度．

单项对称多项式

设 $n$ 是正整数，$K$ 是一个域．记 $\mathit{x}:=(x_1,\dots ,x_n)$．设 $\mathit{\lambda }:=({\lambda }_1,{\lambda }_2,\dots {\lambda }_n)$ 是长度不超过 $n$ 的一个分拆．

定义 $n$ 元多项式环 $K[\mathit{x}]$ 上的关于分拆 $\mathit{\lambda }$ 的单项对称多项式（monomial symmetric polynomial）$m_{\mathit{\lambda }}(\mathit{x})$ 为各项系数为 $1$ 的含有单项式 ${\mathit{x}}^{\mathit{\lambda }}:=x_1^{{\lambda }_1}{x}_2^{{\lambda }_2}\dots x_n^{{\lambda }_n}$ 的项数最少的对称多项式．

• $m_{(2,1,0)}(x_1,x_2,x_3)=x_1^2{x}_2+x_1^2{x}_3+x_1{x}_2^2+x_1{x}_3^2+x_2^2{x}_3+x_2{x}_3^2$
• $m_{(2,2,1)}(x_1,x_2,x_3)=x_1^2{x}_2^2{x}_3+x_1^2{x}_2{x}_3^2+x_1{x}_2^2{x}_3^2$

易见 $m_{\mathit{\lambda }}(\mathit{x})$ 是次数为 $\mathcal{S}(\mathit{\lambda })$ 的齐次（homogeneous）多项式．全体单项对称多项式构成 $n$ 元对称多项式环 ${\mathrm{\Lambda }}_n\subset K[\mathit{x}]$ 作为 $K$ 上线性空间的一组基底．

单项对称多项式

Exercise 1 对一给定的长度不超过 $n$ 的分拆 $\lambda :=({\lambda }_1,{\lambda }_2,\dots {\lambda }_n)$，$n$ 元单项对称多项式 $m_{\lambda }(\mathit{x})$ 共有多少项？

在计数时根据分拆中重复项的分布情况进行消序．

Exercise 2 $n$ 元 $d$ 次单项对称多项式共有多少种可能的构型？设 ${\mathrm{\Lambda }}_n^{(d)}\subset {\mathrm{\Lambda }}_n$ 由全体至多 $d$ 次的 $n$ 元对称多项式构成，其作为 $K$ 上线性空间的维数是多少？

该问题等价于求满足 $\mathcal{S}(\mathit{\lambda })=d$，$\mathcal{L}(\mathit{\lambda })\le n$ 的所有可能分拆 $\mathit{\lambda }$ 的数量，也即“将 $d$ 个无标号球放入 $n$ 个可空置的无标号盒”的可行方案数．

基本对称多项式

$n$ 元多项式环 $K[\mathit{x}]$ 上的 $n$ 个基本对称多项式（elementary symmetric polynomial）定义为 $$e_k(x_1,\dots ,x_n):=\sum _{1\le i_1<i_2\cdots <i_k\le n}{x}_{i_1}{x}_{i_2}\dots x_{i_k},k=1,2,\dots ,n$$ 使用单项对称多项式的记号，也可记为 $$e_k(\mathit{x}):=m_{{\mathit{\lambda }}_k}(\mathit{x})$$ 其中分拆 ${\mathit{\lambda }}_k:=(1,\dots ,1,0,\dots )$ 的前 $k$ 项为 $1$，其余项皆为 $0$．

设分拆 $\mathit{\lambda }:=({\lambda }_1,{\lambda }_2,\dots )$ 满足 ${\lambda }_i\le n,\mathrm{\forall }i\in {\mathbb{N}}_{+}$．我们记 $e_{\mathit{\lambda }}(\mathit{x}):=e_{{\lambda }_1}(\mathit{x})e_{{\lambda }_2}(\mathit{x})\dots e_{{\lambda }_{\mathcal{L}(\mathit{\lambda })}}(\mathit{x})$．

基本对称多项式

Theorem 1 (对称多项式基本定理) 设 $f(\mathit{x})$ 是域 $K$ 上的 $n$ 元对称多项式，则存在唯一的 $g(\mathit{x})\in K[\mathit{x}]$，使得 $$f(\mathit{x})=g(e_1(\mathit{x}),\dots ,e_n(\mathit{x}))$$

该定理对交换环上的对称多项式仍然成立．这意味着若 $f$ 是整系数对称多项式，则 $g$ 也是整系数多项式．

在定理的存在性证明中，为消去首项对应的单项对称多项式 $m_{\mathit{\lambda }}(\mathit{x})$，我们构造的若干个基本对称多项式的乘积恰为 ${\mathit{e}}_{{\mathit{\lambda }}^{\mathrm{T}}}$．

考察全体满足 ${\lambda }_i\le n,\mathrm{\forall }i\in {\mathbb{N}}_{+}$ 的分拆 $\mathit{\lambda }$ 对应的 $e_{\mathit{\lambda }}(\mathit{x})$，它们构成了 $n$ 元对称多项式环 ${\mathrm{\Lambda }}_n$ 作为 $K$ 上线性空间的另一组基底．

幂和对称多项式

$n$ 元多项式环 $K[\mathit{x}]$ 上的幂和对称多项式（power sum symmetric polynomial）定义为 $$p_k(x_1,\dots ,x_n):=x_1^k+x_2^k+\cdots +x_n^k,k\in \mathbb{N}$$ 使用单项对称多项式的记号，也可记为 $$p_k(\mathit{x}):=m_{(k,0,0,\dots )}$$ 特别的，$p_0(\mathit{x})=n$．

Theorem 2 设 $\mathbb{Q}\subset K\subset \mathbb{C}$ 是数域，设 $f(\mathit{x})$ 是域 $K$ 上的 $n$ 元对称多项式，则存在唯一的 $g(\mathit{x})\in K[\mathit{x}]$，使得 $f(\mathit{x})=g(p_1(\mathit{x}),\dots ,p_n(\mathit{x}))$．

一般地，结论对特征为 $0$ 的域 $K$ 也成立．

幂和对称多项式

以下定理递推地给出了幂和对称多项式 $p_1,\dots ,p_n$ 与基本对称多项式 $e_1,\dots ,e_n$ 间的关系．Theorem 2 的存在性部分可由这一定理给出．

Theorem 3 (Newton’s Identities) $$\begin{array}{rlrl}{p}_k& =\sum _{i=1}^{k-1}(-1{)}^{i-1}{e}_i{p}_{k-i}+(-1{)}^{k-1}k{e}_k& k& =1,2,\dots ,n\\ p_k& =\sum _{i=1}^n(-1{)}^{i-1}{e}_i{p}_{k-i}& k& >n\\ k{e}_k& =\sum _{i=1}^k(-1{)}^{i-1}{p}_i{e}_{k-i}& k& =1,2,\dots ,n\\ 0& =\sum _{i=1}^n(-1{)}^{i-1}{p}_i{e}_{k-i}& k& >n\end{array}$$

其它基底

完全齐次对称多项式（Complete homogeneous symmetric polynomials）、Schur 多项式……

本节主要参考 [1]–[4]．

Vieta’s formulas

Theorem 4 (Vieta’s formulas) 设数域 $K\subset \mathbb{C}$ 上 $n$ 次首一多项式（monic polynomial） $$A(x):=x^n+a_{n-1}{x}^{n-1}+\cdots +a_0=(x-c_1)(x-c_2)\dots (x-c_n)$$ 其 $n$ 个复根分别为 $\mathit{c}:=(c_1,c_2,\dots ,c_n)$，则 $A(x)$ 的系数可由关于根的 $n$ 个 $n$ 元基本对称多项式表示 $$a_{n-k}=e_k(-\mathit{c})=(-1{)}^k\sum _{1\le i_1<\cdots <i_k\le n}{c}_{i_1}{c}_{i_2}\dots c_{i_k}$$ 其中 $k=1,2,\dots ,n$．特别的 $$\begin{array}{rl}{a}_0& =e_n(-\mathit{c})=(-1{)}^n{c}_1{c}_2\dots c_n\\ a_{n-1}& =e_1(-\mathit{c})=-(c_1+c_2+\cdots +c_n)\end{array}$$

Vieta 定理与对称多项式基本定理

• 即使尚未获知多项式 $n$ 个复根 $c_1,\dots ,c_n$ 的具体取值，我们也能通过已知的多项式系数 $a_0,\dots ,a_{n-1}$ 获知 $n$ 个 $n$ 元基本对称多项式在根处的取值．

• 对称多项式基本定理指出，任何对称多项式都可被（唯一）表示为关于 $n$ 个基本对称多项式的一个多项式．

• 仅需知晓多项式的系数，就可获得任意给定对称多项式在根处的取值．

• 目标：构造一个（数域 $K\subset \mathbb{C}$ 上的）$n$ 元对称多项式，使得能通过代入求值的方式，快速检测 $n$ 个复数是否两两不同．

Vandermonde 行列式

考察作为（数域 $K\subset \mathbb{C}$ 上）$n$ 元多项式的 Vandermonde 行列式 $$\begin{array}{rl}detV& :=det{\left(\begin{array}{c}{x}_j^{i-1}\end{array}\right)}_{i=1,j=1}^{n,n}\\ & =det\left(\begin{array}{cccc}1& 1& \dots & 1\\ x_1& x_2& \dots & x_n\\ ⋮& ⋮& \ddots & ⋮\\ x_1^{n-1}& x_2^{n-1}& \dots & x_n^{n-1}\end{array}\right)=\prod _{1\le i<j\le n}(x_j-x_i)\end{array}$$ 它是否可用于判定重根？它是对称多项式吗？

Remark. $detV$ 是一个斜对称多项式．事实上，$detV$ 与所有对称多项式的乘积构成了全体斜对称多项式（alternating polynomials）．

判别式

设（数域 $K\subset \mathbb{C}$ 上的）$n$ 元对称多项式 $$D(x_1,\dots ,x_n):=(detV{)}^2=\prod _{1\le i<j\le n}(x_j-x_i{)}^2$$ 称其为（数域 $K$ 上）一元 $n$ 次首一多项式的判别式（Discriminant）．当代入的 $\mathit{x}:=(x_1,\dots ,x_n)\subset \mathbb{C}$ 互不相同时，$D(\mathit{x})\ne 0$；否则 $D(\mathit{x})=0$．

根据对称多项式基本定理，存在唯一数域 $K$ 上的 $n$ 元多项式 $d$，使得 $d(e_1(\mathit{x}),\dots ,e_n(\mathit{x}))=D(\mathit{x})$．

Proposition 1 数域 $K\subset \mathbb{C}$ 上的 $n$ 次首一多项式 $f(x):=x^n+a_{n-1}{x}^{n-1}+\cdots +a_0$ 在复数域中有重根的充分必要条件是 $d(a_{n-1},\dots ,a_0)=0$．

这是因为 $f(x)$ 的 $n$ 个复根 $\mathit{c}:=(c_1,\dots ,c_n)$ 满足 $$D(-\mathit{c})=d(e_1(-\mathit{c}),\dots ,e_n(-\mathit{c}))=d(a_{n-1},\dots ,a_0)$$

判别式

Exercise 3 写出数域 $K\subset \mathbb{C}$ 上一元二次多项式 $x^2+bx+c$ 的判别式．

对次数更高的方程，直接使用消首项方法求解判别式 $D(\mathit{x})$ 在基本对称多项式下的表示 $d(e_1,\dots ,e_n)$ 将变得相当繁琐．下面利用判别式与 Vandermonde 行列式的关系得到另一种分解方法．

另一分解方法

$$\begin{array}{rl}D(\mathit{x})& =(detV{)}^2=det(V{V}^T)\\ & =det(\left(\begin{array}{cccc}1& 1& \dots & 1\\ x_1& x_2& \dots & x_n\\ ⋮& ⋮& \ddots & ⋮\\ x_1^{n-1}& x_2^{n-1}& \dots & x_n^{n-1}\end{array}\right)\left(\begin{array}{cccc}1& x_1& \dots & x_1^{n-1}\\ 1& x_2& \dots & x_2^{n-1}\\ ⋮& ⋮& \ddots & ⋮\\ 1& x_n& \dots & x_n^{n-1}\end{array}\right))\\ & =det\left(\begin{array}{cccc}n& p_1(\mathit{x})& \dots & p_{n-1}(\mathit{x})\\ p_1(\mathit{x})& p_2(\mathit{x})& \dots & p_n(\mathit{x})\\ ⋮& ⋮& \ddots & ⋮\\ p_{n-1}(\mathit{x})& p_n(\mathit{x})& \dots & p_{2n-2}(\mathit{x})\end{array}\right)=det{\left(\begin{array}{c}{p}_{i+j-2}(\mathit{x})\end{array}\right)}_{i=1,j=1}^{n,n}\end{array}$$ 而由 Newton’s Identities，幂和对称多项式 $p_k(\mathit{x})$ 可较容易地递推分解为基本对称多项式的多项式组合，故我们找到了分解 $D(\mathit{x})$ 的一种更易操作的方法．

另一分解方法

Exercise 4 写出数域 $K\subset \mathbb{C}$ 上不完全三次多项式 $x^3+bx+c$ 的判别式．

本节主要参考 [5]–[8]．