整数分拆

设非负整数数列 $\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$ 上线性空间的一组基底．

单项对称多项式

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

该问题等价于求满足 $\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})$．

基本对称多项式

该定理对交换环上的对称多项式仍然成立．这意味着若 $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$．

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

幂和对称多项式

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

其它基底

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

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

Vieta’s formulas

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}$$ 它是否可用于判定重根？它是对称多项式吗？

判别式

设（数域 $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})$．

这是因为 $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)$$

判别式

对次数更高的方程，直接使用消首项方法求解判别式 $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})$ 的一种更易操作的方法．

另一分解方法

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