エレファント・ビジュアライザー調査記録

ビジュアルプログラミングで数式の変形を表すことを考えていくブロクです。

対称式の基本定理(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)も基本対称式の多項式となるということがわかります。

[証明終わり]