対称式を一歩ずつ

$x_1, \ldots, x_n$ の多項式は、変数を置換しても変わらないとき対称であるといいます。$x_1^2 + x_2^2 + x_3^2$ や $x_1 x_2 x_3 - 1$ は対称ですが、$x_1^2 x_2$ は対称ではありません。$x_1$ と $x_2$ を入れ替えると $x_1 x_2^2$ になってしまうからです。対称式の基本定理によれば、体 $F$ 上では、すべての対称式はいくつかの基本的な対称式、すなわち基本対称式 $e_1, \ldots, e_n$ の多項式としてただ一通りに表せます。

$$\begin{aligned} \operatorname{Sym}[X_n] &= F[e_1, \ldots, e_n] \\ &\cong F[y_1, \ldots, y_n]. \end{aligned}$$

ここで $X_n$ は集合 $\{x_1, \ldots, x_n\}$、$\operatorname{Sym}[X_n]$ は $F$ に係数をもつ $X_n$ の対称式全体のなす環、$F[y_1, \ldots, y_n]$ は $n$ 個の新しい変数の多項式環です。等号はすべての対称式が $e_i$ の多項式であることを表し、各 $y_i$ を $e_i$ に送る同型は、その表し方がただ一通りであることを表しています。

通常の証明はアルゴリズムになっており、しかも短いものです。私は2022年に初めてこれをSageMath アーカイブのノートブックで実装しました。ここではブラウザ上で動きます。

基本対称式

変数の個数 $n \in \NN^+$ を固定します。次数 $d \geq 1$ の基本対称式は、相異なる $d$ 個の変数の積すべての和です。

$$e_d = \sum_{1 \leq i_1 < i_2 < \cdots < i_d \leq n} \underbrace{x_{i_1} \cdots x_{i_d}}_{d \text{ 個の因子}},$$

また $e_0 = 1$ とします。たとえば変数が3個のときは

$$\begin{aligned} e_1 &= x_1 + x_2 + x_3, \\ e_2 &= x_1 x_2 + x_1 x_3 + x_2 x_3, \\ e_3 &= x_1 x_2 x_3, \end{aligned}$$

であり、$d > n$ ではつねに $e_d = 0$ です。選べるだけの変数がないからです。

単項式の順序

このアルゴリズムでは、多項式のどの項が先頭に来るかを知る必要があります。単項式 $x_1^{\alpha_1} \cdots x_n^{\alpha_n}$ を、$\alpha = (\alpha_1, \ldots, \alpha_n) \in \NN^n$ として $x^\alpha$ と書き、単項式を次数付き辞書式順序（deglex）で並べます。まず全次数 $\alpha_1 + \cdots + \alpha_n$ で比較し、次数が同じ単項式どうしでは $x_1$ の指数で、次に $x_2$ の指数で、というように比較していきます。したがって $x_1^3 > x_1 x_2^2 > x_2^3 > x_1^2$ であり、一般に $x_1 > x_2 > \cdots > x_n$ です。0でない多項式の先頭項とは最大の単項式をもつ項のことで、その単項式を先頭単項式と呼びます。

deglex は単項式の単なる並べ方ではなく、単項式順序です。つまり単項式全体の上の全順序であって、次の性質を満たすものです。

1. 乗法と両立する：$x^\alpha < x^{\alpha'}$ ならば、すべての単項式 $x^\gamma$ について $x^\alpha x^\gamma < x^{\alpha'} x^\gamma$ が成り立つ。
2. 整列順序である：空でない単項式の集合はつねに最小元をもつ。同値な言い方をすれば、単項式の無限狭義減少列 $x^{\alpha^{(1)}} > x^{\alpha^{(2)}} > x^{\alpha^{(3)}} > \cdots$ は存在しない。

deglex はこの両方の性質をもちます。$x^\gamma$ を掛けると、$x^\alpha$ と $x^{\alpha'}$ の次数には同じ量が加わり、指数にも同じ値が加わるので、どちらの比較も変わりません。また、どの単項式についても、それより小さい単項式は有限個（次数がそれ以下のもの）しかないので、狭義減少列は必ずどこかで止まります。

1つ目の性質のおかげで、先頭項はうまく振る舞います。積の先頭項は先頭項の積です。$g$ の項と $h$ の項のそれ以外の積は、いずれも少なくとも一つはより小さい単項式を含んでおり、掛け算をしてもそれはより小さいままだからです。2つ目の性質は、アルゴリズムが停止することを保証してくれます。

もう一つ、対称式に特有の事実があります。対称式の先頭単項式の指数は非増加、すなわち $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_n$ です。$\alpha_i < \alpha_{i+1}$ となる $x^\alpha$ が現れたとすると、$x_i$ と $x_{i+1}$ を入れ替えることで、その多項式の別の単項式、しかもより大きなものが得られます。したがって $x^\alpha$ は先頭単項式ではなかったことになります。

先頭項を打ち消す

$f$ を先頭項が $c \, x^\alpha$ の対称式とします。証明のアイデアは、この項を基本対称式の積で取り除くことです。つまり、指数の有限列 $b = (b_1, \ldots, b_n) \in \NN^n$ で、

$$e^b = e_1^{b_1} e_2^{b_2} \cdots e_n^{b_n}$$

が同じ先頭単項式 $x^\alpha$ をもつものを見つけます。そうすれば $f - c \, e^b$ では2つの先頭項が打ち消し合います。

先頭項は掛け合わさるので、$e^b$ の先頭項 $\operatorname{lt}(e^b)$ は各因子の先頭項の積であり、$e_k$ の先頭項は係数 $1$ の $x_1 x_2 \cdots x_k$ です。変数 $x_i$ がそこに現れるのはちょうど $k \geq i$ のときなので、

$$\begin{aligned} \operatorname{lt}(e^b) &= \prod_{k=1}^{n} (x_1 x_2 \cdots x_k)^{b_k} \\ &= x_1^{b_1 + b_2 + \cdots + b_n} \, x_2^{b_2 + \cdots + b_n} \cdots x_n^{b_n}. \end{aligned}$$

となります。これが $x^\alpha$ になるには指数が一致しなければならず、$b$ は次の三角型の連立方程式の解でなければなりません。

$$\begin{aligned} \alpha_1 &= b_1 + b_2 + \cdots + b_n, \\ \alpha_2 &= b_2 + \cdots + b_n, \\ &\;\;\vdots \\ \alpha_n &= b_n. \end{aligned}$$

各式を一つ上の式から引くと $b_i = \alpha_i - \alpha_{i+1}$ が残り、最後の式からは $b_n = \alpha_n$ が得られます。したがって候補はちょうど一つであり、これを $\beta(\alpha)$ と呼ぶことにします。

$$\beta(\alpha)_i = \begin{cases} \alpha_i - \alpha_{i+1} & \text{（} 1 \leq i < n \text{ のとき）}, \\ \alpha_i & \text{（それ以外のとき）}. \end{cases}$$

これが負の成分をもたない有効な指数列になるのはちょうど $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_n$ のときであり、これは対称式の先頭単項式がつねに満たす条件です。たとえば $n = 3$ で先頭単項式が $x_1^3 x_2 x_3$ のとき、$\alpha = (3, 1, 1)$ から $\beta(\alpha) = (2, 0, 1)$ が得られます。実際、$e_1^2 e_3 = (x_1 + x_2 + x_3)^2 \, x_1 x_2 x_3$ の先頭単項式は $x_1^2 \cdot x_1 x_2 x_3 = x_1^3 x_2 x_3$ です。

アルゴリズム

対称式 $f$ が与えられたとき：

• $f$ が $0$ または定数なら、すでに $e_i$ の多項式になっているので、何もする必要はありません。
• そうでなければ、deglex での先頭項を $c \, x^\alpha$ とし、$b = \beta(\alpha)$ とします。このとき $f$ は、$c \, e^b$ と、$f - c \, e^b$（$e^b$ は $x_i$ について展開したもの）の $e_i$ による表示との和になります。後者はアルゴリズムをもう一度実行して求めます。

多項式 $f - c \, e^b$ は対称式の差なので依然として対称であり、その先頭単項式は $x^\alpha$ より小さくなります。2つの先頭項は打ち消し合い、$f$ と $c \, e^b$ のそれ以外の項はすべてより小さい単項式をもつからです。こうしてアルゴリズムを実行すると、先頭単項式が狭義に減少していく対称式の列 $f_0 = f, f_1, f_2, \ldots$ が得られます。deglex は整列順序なので、このような列が永遠に続くことはありません。有限回のステップの後に残るのは $0$ であり、途中で集めた項 $c \, e^b$ を足し合わせると $f$ になります。

この表示は一意でもあります。2つの多項式 $P, Q \in F[y_1, \ldots, y_n]$ について $f = P(e_1, \ldots, e_n) = Q(e_1, \ldots, e_n)$ だとしましょう。すると差 $R = P - Q$ は $R(e_1, \ldots, e_n) = 0$ を満たすので、ここから $R = 0$ が従うこと、すなわち変数に $e_i$ を代入して0になるような0でない多項式は存在しないこと（$e_i$ は代数的に独立である）を示せば十分です。

$$\begin{aligned} R &= \sum_{b \in S} c_b \, y^b, \\ R(e_1, \ldots, e_n) &= \sum_{b \in S} c_b \, e^b, \end{aligned}$$

と書きます。ここで $S \subset \NN^n$ は係数 $c_b$ が0でない指数からなる有限集合であり、$S$ は空でないと仮定します。各 $e^b$ の先頭項は係数 $1$ の $x^{\alpha(b)}$ で、$\alpha(b)_i = b_i + b_{i+1} + \cdots + b_n$ です。また $b$ は $\alpha(b)$ から $\beta(\alpha(b))$ として復元できるので、異なる $b$ は異なる $\alpha(b)$ を与えます。したがって、$b \in S$ に対する有限個の単項式 $x^{\alpha(b)}$ のなかには最大のもの $x^{\alpha(b^*)}$ があり、それを与える $b^* \in S$ はただ一つです。この単項式は $c_{b^*} e^{b^*}$ に係数 $c_{b^*}$ で現れます。他の $e^b$ は自身の先頭単項式 $x^{\alpha(b)}$ 以下の単項式しかもたず、$x^{\alpha(b)}$ は $x^{\alpha(b^*)}$ より小さいので、$x^{\alpha(b^*)}$ をまったく含みません。よって $R(e_1, \ldots, e_n)$ における $x^{\alpha(b^*)}$ の係数は $c_{b^*} \neq 0$ となり、$R(e_1, \ldots, e_n) = 0$ に反します。したがって $S$ は空であり、$R = 0$、つまり $P = Q$ です。

下の計算機は各ステップ、すなわち先頭項、$\alpha$ と $\beta(\alpha)$、そして残り $f_i$ を表示します。長い多項式を読みやすくするため、軌道ごとにまとめています。$m_\lambda$ は、指数が $\lambda$ の並べ替えになっている相異なる単項式の和です。たとえば $n = 3$ では

$$\begin{aligned} m_{(2,1)} = {} & x_1^2 x_2 + x_1^2 x_3 + x_1 x_2^2 \\ & + x_2^2 x_3 + x_1 x_3^2 + x_2 x_3^2. \end{aligned}$$

となります。多項式が対称であるのは、$\lambda_1 \geq \cdots \geq \lambda_n$ を満たす $m_\lambda$ の一次結合であるときに限ります。計算機はそれらを $x^\lambda$ の大きい順に並べるので、最初のものに先頭項が含まれます。計算機は計算もこの形で行います。積 $e^b$ を展開することはせず、軌道の係数に対して直接各 $e_j$ を掛けていきます。

多項式は対称でなければなりません。そうでない場合、アルゴリズムは正常に終了できません。もし終了したとすれば、その多項式は対称式の組み合わせであり、したがってそれ自身も対称であることになって、↯ です。Not symmetric の例を見ると、どこで破綻するかがわかります。遅かれ早かれ先頭項の指数が非増加の順に並ばなくなり、$\beta(\alpha)$ に負の成分が現れて、そのような先頭項をもつ $e_i$ の積は存在しなくなるのです。

べき和

べき和 $p_k = x_1^k + \cdots + x_n^k$ については、もっと直接的な方法としてニュートン・ジラールの恒等式 アーカイブがあります。これは $k \geq 1$ に対して、$p_k$ を $e_i$ とそれ以前のべき和で表すものです。

$$p_k = (-1)^{k+1} \Bigl( k \, e_k + \sum_{i=1}^{k-1} (-1)^i \, p_i \, e_{k-i} \Bigr),$$

ここで $i > n$ ではつねに $e_i = 0$ とします（また $x_i^0 = 1$ なので $p_0 = n$ です）。$p_1$、$p_2$ と順に、それぞれをそれ以前のものから $p_k$ まで計算していくと一つの表示が得られ、一般のアルゴリズムを $x_1^k + \cdots + x_n^k$ に適用するともう一つの表示が得られます。一意性からこの2つは同じ多項式でなければならず、実際その差は0になります。

判別式

今度は

$$f(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_0$$

が $\CC$ に根 $x_1, x_2, \ldots, x_n$ をもつとし、各根を重複度の回数だけ並べて $f(x) = (x - x_1) \cdots (x - x_n)$ となるようにします。$f$ の判別式とは積

$$\Delta(f) = \prod_{1 \leq i < j \leq n} (x_i - x_j)^2,$$

のことであり、これによって $f$ が重根をもつかどうかがわかります。

$$\exists \, i \neq j : x_i = x_j \iff \Delta(f) = 0.$$

$\Delta(f)$ が根の対称式であることは簡単に確かめられます。どの置換も互換の合成なので、2つの根 $x_i$ と $x_j$ を入れ替えても変わらないことを確かめれば十分です。

• どちらも含まない因子はそのままです。
• 一方だけを含む因子は、$(x_i - x_k)^2$ と $(x_j - x_k)^2$ のように2つずつ入れ替わります。底の符号が変わることはあっても、それは2乗によって消えます。
• 両方を含む因子は底の符号が変わり、$(x_i - x_j)^2$ は $(x_j - x_i)^2$ になりますが、2乗すれば変わりません。

したがって基本定理により、$\Delta(f)$ は根の基本対称式によってただ一通りに書けます。ところがこれらは、符号を除けば $f$ の係数にほかなりません。$(x - x_1) \cdots (x - x_n)$ を展開して $f$ と比較すると、$a_n = 1$ として $0 \leq i \leq n$ に対し

$$e_i(x_1, \ldots, x_n) = (-1)^i a_{n-i}$$

が成り立ちます。よって $\prod_{i<j} (x_i - x_j)^2$ に対してアルゴリズムを実行し、各 $e_i$ に $(-1)^i a_{n-i}$ を代入すれば、次数 $n$ のあらゆるモニック多項式の判別式を、根を知らなくても係数で表せます。$n = 2$ ではおなじみの $\Delta = a_1^2 - 4 a_0$ であり、$n = 3$ では

$$\begin{aligned} \Delta = {} & a_1^2 a_2^2 - 4 a_0 a_2^3 - 4 a_1^3 \\ & + 18 \, a_0 a_1 a_2 - 27 a_0^2, \end{aligned}$$

となります。これは $x^3 + p x + q$ に対しては $-4p^3 - 27q^2$ に帰着します。

最高次係数 $a_n$ が $1$ でない多項式は、モニック多項式 $f / a_n$ と同じ根をもちます。その判別式は通常 $a_n^{2n-2} \, \Delta(f / a_n)$ と定義されます。この因子によって判別式は $a_0, \ldots, a_n$ の整数係数多項式となり、それが0になるのはちょうど $\Delta(f / a_n)$ が0のときです。

下では、入力した多項式の次数に対応する公式をアルゴリズムで計算し、それをその多項式の係数で評価します。最初の例 $(x - 1)^2 (x + 2) = x^3 - 3x + 2$ は二重根をもつので、判別式は0です。2つ目の例 $(x - 1)(x + 1)(x + 3) = x^3 + 3x^2 - x - 3$ は相異なる3つの根をもち、判別式は0ではありません。