対称式の基本定理(1) - エレファント・コンピューティング調査報告

はてなダイアリーに対称式の基本定理について書いていたのですが、これもなぜか読みにくくなっているのでちょっと直して再び掲載していこうと思います。

文字を使った式

文字 $x$ を含む式の中で、加法、減法、乗法だけで書けるもの(たとえば $(3x-2)(x+3)$ のようなもの)は、

$\displaystyle \sum_{i=0}^{n}a_{i}x^{i}=a_{n}x^{n}+a_{n-1}x^{n-1}+ \ldots +a_{1}x+a_{0}$

という形にすることができます(たとえば $(3x-2)(x+3)$ のときは $(3x-2)(x+3)=3x^{2}+7x-6$ と書ける)。この

$\displaystyle \sum_{i=0}^{n}a_{i}x^{i}=a_{n}x^{n}+a_{n-1}x^{n-1}+ \ldots +a_{1}x+a_{0}$

という形の式を変数 $x$ の多項式といいます。多項式の和、積は多項式になります。多項式

$\displaystyle p(x) = \sum_{i=0}^{n}a_{i}x^{i}$

と

$\displaystyle q(x) = \sum_{i=0}^{m}b_{i}x^{i}$

の加法は、まず $n$ と $m$ の大きい方に合わせて $0$ を $a_{i}$ または $b_{i}$ として付け加えて( $n>m$ のときは $b_{m+1}=b_{m+2}= \ldots =b_{n}=0$ を付け加える)

$\displaystyle \left( \sum_{i=0}^{n}a_{i}x^{i} \right) +\left( \sum_{i=0}^{n}b_{i}x^{i} \right) = \sum_{i=0}^{n}\left( a_{i}+b_{i} \right) x^{i}$

となります。多項式 $p(x)$ と $q(x)$ の乗法は

$\displaystyle \left( \sum_{i=0}^{n}a_{i}x^{i} \right) \left( \sum_{j=0}^{m}b_{j}x^{j} \right) =\sum_{i=0}^{n} \sum_{j=0}^{m}a_{i}b_{j}x^{i+j}$

となります。

1変数の多項式

以上のことを考えて、環上の多項式を以下のように定義します。 $R$ を単位元をもつ可換環とします。

$\displaystyle \sum_{i=0}^{n}a_{i}x^{i}=a_{n}x^{n}+a_{n-1}x^{n-1}+ \ldots +a_{1}x+a_{0}$

( $a_{0},a_{1}, \ldots ,a_{n} \in R$ )という形の式を、 $R$ の元を係数とする変数(不定元ともいいます) $x$ の多項式といいます。多項式の加法、乗法は上に書いたように(文字を含む式の加法、乗法のように)定義することができます。この演算によって多項式全体の集合は単位元をもつ可換環となります。これを $R$ 上の変数 $x$ の多項式環といい、 $R[x]$ と書きます。

多変数の多項式

複数の変数に関する多項式も同様に定義することができます。変数 $x_{1},x_{2}, \ldots ,x_{n}$ の多項式とは、1変数の場合と同様に、文字 $x_{1},x_{2}, \ldots ,x_{n}$ から加法、減法、乗法によってできる式となります。多項式の加法、乗法を、やはり通常の加法、乗法のように定義することができ、この演算によって多項式全体の集合は単位元をもつ可換環となります。これを $R$ 上の変数 $x_{1},x_{2}, \ldots ,x_{n}$ の多項式環といい、 $R[x_{1},x_{2}, \ldots ,x_{n}]$ と書きます。

対称式

集合 $\{1,2, \ldots ,n\}$ からそれ自身への全単射の全体 $S_{n}$ は、写像の合成を演算として群になります。この $S_{n}$ を $n$ 次の対称群といいます。多項式 $f(x_{1},x_{2}, \ldots ,x_{n}) \in R[x_{1},x_{2}, \ldots ,x_{n}]$ が対称群 $S_{n}$ の任意の元 $\sigma$ に対して

$\displaystyle f(x_{\sigma (1)},x_{\sigma (2)}, \ldots ,x_{\sigma (n)})=f(x_{1},x_{2}, \ldots ,x_{n})$

を満たすとき、多項式 $f(x_{1},x_{2}, \ldots ,x_{n})$ を対称式といいます。

対称式の基本定理・証明1・3変数の場合

では、「対称式の基本定理」の証明を書こうと思いますが、これはけっこうめんどうなので、まず3変数の場合からやってみます。

基本対称式

$n$ 変数の多項式

$s_{k}=\displaystyle \sum_{1 \le i_{1} < i_{2} < \ldots < i_{k} \le n}^{}x_{i_{1}}x_{i_{2}} \ldots x_{i_{k}}$

は対称式となります( $k=1,2, \ldots ,n$ )。これらの対称式を基本対称式といいます。 $n=2$ のときは $x_{1}+x_{2}$ と $x_{1}x_{2}$ が基本対称式となります。 $n=3$ のときは $x_{1}+x_{2}+x_{3}$ と $x_{1}x_{2}+x_{2}x_{3}+x_{3}x_{1}$ と $x_{1}x_{2}x_{3}$ が基本対称式となります。

対称式の基本定理

[定理]

対称式は基本対称式の多項式となります。これを3変数( $x,y,z$ )の場合について証明します。この場合基本対称式は $x+y+z, xy+yz+zx, xyz$ となります。

[証明]

$f(x,y,z)$ を対称式とします。 $f(x,y,z)$ は $kx^{a}y^{b}z^{c}$ という形の式の和の形で書くことができます。この $kx^{a}y^{b}z^{c}$ という形の式を単項式といいます。 $f(x,y,z)$ の中に(和の成分として)含まれている単項式を項ということにします。

例

この証明は、実際に対称式を基本対称式の多項式で表す方法を示しています。
$f(x,y,z)=(x-y)^2(y-z)^2(z-x)^2$
を基本対称式
$a=x+y+z, b=xy+yz+zx, c=xyz$
の多項式で書いてみます。

第1段階

$\begin{eqnarray*} f(x,y,z) & = & - 6x^2y^2z^2 + 2x^3y^2z + x^4y^2 + 2x^2yz^3 + 2x^3yz^2 - 2x^4yz \\ & & + x^2z^4 - 2x^3z^3 + x^4z^2 + 2xy^3z^2 + 2x^2y^3z - 2x^3y^3 \\ & & + 2xy^2z^3 - 2xyz^4 + y^4z^2 - 2xy^4z + x^2y^4 - 2y^3z^3 + y^2z^4 \end{eqnarray*}$
に含まれる項の中で、定理の証明で述べた順序に関して最大の項は
$x^4y^2$
となります。
$\begin{eqnarray*} & & a^{4-2}b^2 = a^2b^2 \\ & = & x^4y^2 + 2x^4yz + 8x^3y^2z + x^4z^2 + 8x^3yz^2 + 15x^2y^2z^2 \\ & & + 2x^3y^3 + 8x^2y^3z + 8xy^3z^2 + 2x^3z^3 + 8x^2yz^3 + 8xy^2z^3 \\ & & + x^2y^4 + 2xy^4z + y^4z^2 + 2y^3z^3 + x^2z^4 + 2xyz^4 + y^2z^4 \end{eqnarray*}$
によって変形する(両辺の差をとる)と
$\begin{eqnarray*} f(x,y,z) & = & - 21x^2y^2z^2 - 6x^3y^2z - 6x^2yz^3 - 6x^3yz^2 - 4x^4yz - 4x^3z^3 \\ & & - 6xy^3z^2 - 6x^2y^3z - 4x^3y^3 - 6xy^2z^3 - 4xyz^4 - 4xy^4z \\ & & - 4y^3z^3 + a^2b^2 \end{eqnarray*}$
となります。

第2段階

$\begin{eqnarray*} f(x,y,z) & = & - 21x^2y^2z^2 - 6x^3y^2z - 6x^2yz^3 - 6x^3yz^2 - 4x^4yz - 4x^3z^3 \\ & & - 6xy^3z^2 - 6x^2y^3z - 4x^3y^3 - 6xy^2z^3 - 4xyz^4 - 4xy^4z \\ & & - 4y^3z^3 + a^2b^2 \end{eqnarray*}$
に含まれる項の中で、定理の証明で述べた順序に関して最大の項は
$- 4x^4yz$
となります。
$\begin{eqnarray*} & & -4a^{4-1}b^{1-1}c = -4a^3c \\ & = & - 4x^4yz - 12x^3y^2z - 12x^3yz^2 - 12x^2y^3z - 24x^2y^2z^2 - 12x^2yz^3 \\ & & - 4xy^4z - 12xy^3z^2 - 12xy^2z^3 - 4xyz^4 \end{eqnarray*}$
によって変形する(両辺の差をとる)と
$\begin{eqnarray*} f(x,y,z) & = & 3x^2y^2z^2 + 6x^3y^2z + 6x^2yz^3 + 6x^3yz^2 - 4x^3z^3 + 6xy^3z^2 \\ & & + 6x^2y^3z - 4x^3y^3 + 6xy^2z^3 - 4y^3z^3 + a^2b^2 - 4a^3c \end{eqnarray*}$
となります。

第3段階

$\begin{eqnarray*} f(x,y,z) & = & 3x^2y^2z^2 + 6x^3y^2z + 6x^2yz^3 + 6x^3yz^2 - 4x^3z^3 + 6xy^3z^2 \\ & & + 6x^2y^3z - 4x^3y^3 + 6xy^2z^3 - 4y^3z^3 + a^2b^2 - 4a^3c \end{eqnarray*}$
に含まれる項の中で、定理の証明で述べた順序に関して最大の項は
$- 4x^3y^3$
となります。
$\begin{eqnarray*} & & -4a^{3-3}b^{3-0}c^0 = -4b^3 \\ & = & - 4x^3y^3 - 12x^3y^2z - 12x^2y^3z - 12x^3yz^2 - 24x^2y^2z^2 - 12xy^3z^2 \\ & & - 4x^3z^3 - 12x^2yz^3 - 12xy^2z^3 - 4y^3z^3 \end{eqnarray*}$
によって変形する(両辺の差をとる)と
$\begin{eqnarray*} f(x,y,z) & = & 27x^2y^2z^2 + 18x^3y^2z + 18x^2yz^3 + 18x^3yz^2 + 18xy^3z^2 \\ & & + 18x^2y^3z + 18xy^2z^3 + a^2b^2 - 4a^3c - 4b^3 \end{eqnarray*}$
となります。

第4段階

$\begin{eqnarray*} f(x,y,z) & = & 27x^2y^2z^2 + 18x^3y^2z + 18x^2yz^3 + 18x^3yz^2 + 18xy^3z^2 \\ & & + 18x^2y^3z + 18xy^2z^3 + a^2b^2 - 4a^3c - 4b^3 \end{eqnarray*}$
に含まれる項の中で、定理の証明で述べた順序に関して最大の項は
$18x^3y^2z$
となります。
$\begin{eqnarray*} & & 18a^{3-1}b^{2-1}c = 18abc \\ & = & 18x^3y^2z + 18x^3yz^2 + 54x^2y^2z^2 + 18x^2y^3z + 18xy^3z^2 + 18x^2yz^3 + 18xy^2z^3 \end{eqnarray*}$
によって変形する(両辺の差をとる)と
$f(x,y,z) = - 27x^2y^2z^2 + a^2b^2 - 4a^3c - 4b^3 + 18abc$
となります。

第5段階

$f(x,y,z) = - 27x^2y^2z^2 + a^2b^2 - 4a^3c - 4b^3 + 18abc$
に含まれる項の中で、定理の証明で述べた順序に関して最大の項は
$- 27x^2y^2z^2$
となります。
$-27a^{2-2}b^{2-2}c^2 = -27c^2 = - 27x^2y^2z^2$
によって変形する(両辺の差をとる)と
$f(x,y,z) = a^2b^2 - 4a^3c - 4b^3 + 18abc - 27c^2$
となります。
これで $x,y,z$ を含む項はなくなって、 $f(x,y,z)$ は基本対称式の多項式として表すことができました。

[証明の続き]

$f(x,y,z)$ の中に $kx^{a}y^{b}z^{c}$ と $lx^{a}y^{b}z^{c}$ という項があるとすると、これらの項をまとめて $(k+l)x^{a}y^{b}z^{c}$ とすることができます。よって $f(x,y,z)$ に含まれる項 $kx^{a}y^{b}z^{c}$ は $a$ 、 $b$ 、 $c$ のどれかが異なるようにすることができます。多項式 $f(x,y,z)$ をこの形に書き直したときの $f(x,y,z)$ に含まれる項全体の集合を $T(f(x,y,z))$ とします。

$\sigma$ を集合 $\{x,y,z\}$ の置換(集合 $\{x,y,z\}$ からそれ自身への全単射)とすると、単項式 $kx^{a}y^{b}z^{c}$ に単項式 $k\sigma (x)^{a}\sigma (y)^{b}\sigma (z)^{c}$ を対応させる写像を定義することができます。この(単項式全体の集合からそれ自身への)写像も $\sigma$ と書くことにします。このような写像を $x,y,z$ の置換ということにします。

$T(f(x,y,z))$ の元 $kx^{a}y^{b}z^{c}$ をとります。 $\sigma$ を $x,y,z$ の置換とすると、 $f(x,y,z)$ は対称式なので $\sigma (kx^{a}y^{b}z^{c})$ も $T(f(x,y,z))$ の元となります。 $kx^{a}y^{b}z^{c}$ に対して、 $x,y,z$ のすべての置換 $\sigma$ によってできる $\sigma (kx^{a}y^{b}z^{c})$ (の中の異なるもの)全体の集合を $S(kx^{a}y^{b}z^{c})$ とすると、 $S(kx^{a}y^{b}z^{c})$ は $T(f(x,y,z))$ に含まれます。

単項式全体の集合に以下のように順序 $\ge$ を定義します。単項式 $kx^{a}y^{b}z^{c}$ と $lx^{a'}y^{b'}z^{c'}$ は、 $a>a'$ 、または $a=a'$ かつ $b>b'$ 、または $a=a'$ かつ $b=b'$ かつ $c \ge c'$ であるときに $kx^{a}y^{b}z^{c} \ge lx^{a'}y^{b'}z^{c'}$ であるとします。この順序 $\ge$ は全順序となります。 $a>a'$ 、または $a=a'$ かつ $b>b'$ 、または $a=a'$ かつ $b=b'$ かつ $c>c'$ であるときに $kx^{a}y^{b}z^{c}>lx^{a'}y^{b'}z^{c'}$ と書くことにします。

$T(f(x,y,z))$ は空ではないとし、順序 $\ge$ に関して最大となる $T(f(x,y,z))$ の元 $kx^{a}y^{b}z^{c}$ をとります。
$T(k(x+y+z)^{a-b}(xy+yz+zx)^{b-c}(xyz)^{c})$
の中で $x$ の次数が最大の元は
$T(kx^{a-b}(xy+zx)^{b-c}(xyz)^{c})$
の元となります。この中で $y$ の次数が最大の元は
$kx^{a-b}(xy)^{b-c}(xyz)^{c}=kx^{a}y^{b}z^{c}$
となります。よって $T(k(x+y+z)^{a-b}(xy+yz+zx)^{b-c}(xyz)^{c})$ は $S(kx^{a}y^{b}z^{c})$ を含み、
$T(k(x+y+z)^{a-b}(xy+yz+zx)^{b-c}(xyz)^{c})-S(kx^{a}y^{b}z^{c})$
の中で順序 $\ge$ に関して最大となる元を $t$ とすると $kx^{a}y^{b}z^{c}>t$ となります。

よって
$f_{1}(x,y,z)=f(x,y,z)-k(x+y+z)^{a-b}(xy+yz+zx)^{b-c}(xyz)^{c}$
とおくと順序 $\ge$ に関する $T(f_{1}(x,y,z))$ の最大元 $t$ は $kx^{a}y^{b}z^{c}>t$ となります。ここで、もし $f_{1}(x,y,z)$ が基本対称式の多項式であるとすると、 $f(x,y,z)$ も基本対称式の多項式となります。よって、 $f_{1}(x,y,z)$ が基本対称式の多項式であることを証明すればよいということになります。

$f(x,y,z)$ から $f_{1}(x,y,z)$ を作ったのと同じ方法で、 $f_{1}(x,y,z)$ から $f_{2}(x,y,z)$ 、 $f_{2}(x,y,z)$ から $f_{3}(x,y,z)$ 、と順に作っていくと、どこかの $f_{r}(x,y,z)$ で $f_{r}(x,y,z)=0$ となるか、または順序 $\ge$ に関して最大となる元の $x$ の次数は $0$ となります。すなわち $f_{r}(x,y,z)$ は定数となるので、基本対称式の多項式となります。したがって元の $f(x,y,z)$ も基本対称式の多項式となるということがわかります。

[証明終わり]