グレブナー基底を求める「まではやらない」連立方程式の変形

はじめに

ただ連立方程式を解くことが目的である場合の同値変形をまとめていきます。
用語や記号がほんの一部高校範囲外なので大学数学以上に設定してありますが、かといって大学数学レベルのことかと聞かれると微妙です。

同値変形$[0]$

式の消去のために、次に説明する同値変形$[1]$と合わせて暗黙的に使います。

同値変形$[1]$

$f\left(x_1,\ x_2,\ \ldots,\ x_m\right)$の単項式に$g\left(x_1,\ x_2,\ \ldots,\ x_m\right)\neq0$の先頭単項式$\mathrm{LM}\left(g\right)$の倍数$M\neq0$があるとき、$f$から$h=f-\dfrac{M}{\mathrm{LM}\left(g\right)}g$を得る操作を$g$による単項簡約といい、$f\underset{g}{\longrightarrow}h$と表すことにします。

これを使うことが多いです。

同値変形$[2]$

$f\left(x_1,\ x_2,\ \ldots,\ x_m\right)$の先頭単項式$\mathrm{LM}\left(f\right)$を先頭係数で割ったものを先頭項$\mathrm{LT}\left(f\right)$といいます。
項$T_1,\ T_2$の最小公倍数を$\mathrm{LCM}\left(T_1,\ T_2\right)$と表すことにします。
$f\left(x_1,\ x_2,\ \ldots,\ x_m\right)\neq0,\ g\left(x_1,\ x_2,\ \ldots,\ x_m\right)\neq0$について
$S\left(f,\ g\right)=\dfrac{\mathrm{LCM}\left(\mathrm{LT}\left(f\right),\ \mathrm{LT}\left(g\right)\right)}{\mathrm{LM}\left(f\right)}f-\dfrac{\mathrm{LCM}\left(\mathrm{LT}\left(f\right),\ \mathrm{LT}\left(g\right)\right)}{\mathrm{LM}\left(g\right)}g$
を$f,\ g$の$S$多項式といいます。

同値変形$[1]$で$1$変数の方程式が現れなかったときに使います。

例1

$$ \begin{eqnarray} \begin{cases} x^2+y+z=3 & \\ xy=1 & \\ yz=1 & \end{cases} \end{eqnarray} $$
を解いてみましょう。
まず移項によって右辺を0にします。最終的に$1$変数の方程式に落としこみたいため、$x>y>z$の辞書式順序で並べます。
$$ \begin{eqnarray} \begin{cases} x^2+y+z-3=0 & \\ xy-1=0 & \\ yz-1=0 & \end{cases} \end{eqnarray} $$
同値変形$[0],\ [1]$が使えないので、同値変形$[2]$を使います。
$S\left(xy-1,\ yz-1\right)$を求めます。
$xy$と$yz$の最小公倍数は$xyz$なので
$$ \begin{eqnarray} S\left(xy-1,\ yz-1\right)&=&z\left(xy-1\right)-x\left(yz-1\right)\\ &=&xyz-z-xyz+x\\ &=&x-z \end{eqnarray} $$
$x-z=0$を方程式に追加します。

$$ \begin{eqnarray} \begin{cases} x^2+y+z-3=0 & \\ xy-1=0 & \\ yz-1=0 & \\ x-z=0 & \end{cases} \end{eqnarray} $$
$$ \begin{eqnarray} \begin{cases} x^2+y+z-3=0 & \\ xy-1=0 & \\ x-z=0 & \\ yz-1=0 & \end{cases} \end{eqnarray} $$
先頭単項式が$x$である式が現れたので、同値変形$[1]$を使います。
$\left(xy-1\right)-y\left(x-z\right)=xy-1-xy+yz=yz-1$

$$ \begin{eqnarray} \begin{cases} x^2+y+z-3=0 & \\ yz-1=0 & \\ x-z=0 & \\ yz-1=0 & \end{cases} \end{eqnarray} $$
$$ \begin{eqnarray} \begin{cases} x^2+y+z-3=0 & \\ x-z=0 & \\ yz-1=0 & \\ yz-1=0 & \end{cases} \end{eqnarray} $$
同じ方程式が$2$つ現れたので、同値変形$[1]$からの同値変形$[0]$で消去します。

$$ \begin{eqnarray} \begin{cases} x^2+y+z-3=0 & \\ x-z=0 & \\ yz-1=0 & \\ 0=0 & \end{cases} \end{eqnarray} $$
$$ \begin{eqnarray} \begin{cases} x^2+y+z-3=0 & \\ x-z=0 & \\ yz-1=0 & \end{cases} \end{eqnarray} $$
同値変形$[1]$をまた使います。
$\left(x^2+y+z-3\right)-x\left(x-z\right)=x^2+y+z-3-x^2+xz=xz+y+z-3$
$$ \begin{eqnarray} \begin{cases} xz+y+z-3=0 & \\ x-z=0 & \\ yz-1=0 & \end{cases} \end{eqnarray} $$
同値変形$[1]$をまた使います。
$\left(xz+y+z-3\right)-z\left(x-z\right)=xz+y+z-3-xz+z^2=y+z^2+z-3$
$$ \begin{eqnarray} \begin{cases} y+z^2+z-3=0 & \\ x-z=0 & \\ yz-1=0 & \end{cases} \end{eqnarray} $$
$$ \begin{eqnarray} \begin{cases} x-z=0 & \\ yz-1=0 & \\ y+z^2+z-3=0 & \end{cases} \end{eqnarray} $$
同値変形$[1]$をまた使います。
$\left(yz-1\right)-z\left(y+z^2+z-3\right)=yz-1-yz-z^3-z^2+3z=-z^3-z^2+3z-1$
$$ \begin{eqnarray} \begin{cases} x-z=0 & \\ -z^3-z^2+3z-1=0 & \\ y+z^2+z-3=0 & \end{cases} \end{eqnarray} $$
$$ \begin{eqnarray} \begin{cases} x-z=0 &\\ y+z^2+z-3=0 & \\ z^3+z^2-3z+1=0 & \end{cases} \end{eqnarray} $$
$\{x-z,\ y+z^2+z-3,\ z^3+z^2-3z+1\}$は$\langle x^2+y+z-3,\ xy-1,\ yz-1\rangle=\langle x-z,\ y+z^2+z-3,\ z^3+z^2-3z+1\rangle$の簡約グレブナー基底ですが、それを確認する必要はありません。
連立方程式を解くために同値変形をしてきたということが重要です。
$z^3+z^2-3z+1=0$を解きます。
明らかに$z=1$を解にもつので
$z^3+z^2-3z+1=\left(z-1\right)\left(z^2+2z-1\right)=\left(z-1\right)\left(z+1+\sqrt2\right)\left(z+1-\sqrt2\right)=0$より
$z=1,\ -1+\sqrt2,\ -1-\sqrt2$
$\left(1\right)z=1$の場合
$y+z^2+z-3=y+1^2+1-3=y-1=0$より$y=1$
$x-z=x-1=0$より$x=1$
$\left(2\right)z=-1+\sqrt2$の場合
$y+z^2+z-3=y+\left(-1+\sqrt2\right)^2+\left(-1+\sqrt2\right)-3=y-1-\sqrt2=0$より$y=1+\sqrt2$
$x-z=x+1-\sqrt2=0$より$x=-1+\sqrt2$
$\left(3\right)z=-1-\sqrt2$の場合
$y+z^2+z-3=y+\left(-1-\sqrt2\right)^2+\left(-1-\sqrt2\right)-3=y-1+\sqrt2=0$より$y=1-\sqrt2$
$x-z=x+1+\sqrt2=0$より$x=-1-\sqrt2$
よって
$$ \begin{eqnarray} \begin{cases} x^2+y+z=3 & \\ xy=1 & \\ yz=1 & \end{cases} \end{eqnarray} $$
の解は、$x=y=z=1$または$x=z=-1\pm\sqrt2,\ y=1\pm\sqrt2\ ($複号同順$)$です。

例2

さらに極端な例です。
$$ \begin{eqnarray} \begin{cases} a^2s+b^2s=25 & \\ a^2s+\left(1-b\right)^2s=49 & \\ \left(1-a\right)^2s+b^2s=1 & \end{cases} \end{eqnarray} $$
を解いてみましょう。
ちなみにこの方程式で1963年の名古屋大学の入試の図形問題を補助線を引かずに解けます。
まず移項によって右辺を0にし、$a>b>s$の辞書式順序で並べます。

$$ \begin{eqnarray} \begin{cases} a^2s+b^2s-25=0 & \\ a^2s+b^2s-2bs+s-49=0 & \\ a^2s-2as+b^2s+s-1=0 & \end{cases} \end{eqnarray} $$
同値変形$[1]$をひたすら使っていきます。
$\left(a^2s-2as+b^2s+s-1\right)-\left(a^2s+b^2s-25\right)=-2as+s+24$より
$$ \begin{eqnarray} \begin{cases} a^2s+b^2s-25=0 & \\ a^2s+b^2s-2bs+s-49=0 & \\ as-\dfrac{1}{2}s-12=0 & \end{cases} \end{eqnarray} $$
$\left(a^2s+b^2s-2bs+s-49\right)-\left(a^2s+b^2s-25\right)=-2bs+s-24$より
$$ \begin{eqnarray} \begin{cases} a^2s+b^2s-25=0 & \\ bs-\dfrac{1}{2}s+12=0 & \\ as-\dfrac{1}{2}s-12=0 & \end{cases} \end{eqnarray} $$
$$ \begin{eqnarray} \begin{cases} a^2s+b^2s-25=0 & \\ as-\dfrac{1}{2}s-12=0 & \\ bs-\dfrac{1}{2}s+12=0 & \end{cases} \end{eqnarray} $$
$\left(a^2s+b^2s-25\right)-b\left(bs-\dfrac{1}{2}s+12\right)=a^2s+\dfrac{1}{2}bs-12b-25$より
$$ \begin{eqnarray} \begin{cases} a^2s+\dfrac{1}{2}bs-12b-25=0 & \\ as-\dfrac{1}{2}s-12=0 & \\ bs-\dfrac{1}{2}s+12=0 & \end{cases} \end{eqnarray} $$
$\left(a^2s+\dfrac{1}{2}bs-12b-25\right)-\dfrac{1}{2}\left(bs-\dfrac{1}{2}s+12\right)=a^2s-12b+\dfrac{1}{4}s-31$より
$$ \begin{eqnarray} \begin{cases} a^2s-12b+\dfrac{1}{4}s-31=0 & \\ as-\dfrac{1}{2}s-12=0 & \\ bs-\dfrac{1}{2}s+12=0 & \end{cases} \end{eqnarray} $$
$\left(a^2s-12b+\dfrac{1}{4}s-31\right)-a\left(as-\dfrac{1}{2}s-12\right)=\dfrac{1}{2}as+12a-12b+\dfrac{1}{4}s-31$より
$$ \begin{eqnarray} \begin{cases} as+24a-24b+\dfrac{1}{2}s-62=0 & \\ as-\dfrac{1}{2}s-12=0 & \\ bs-\dfrac{1}{2}s+12=0 & \end{cases} \end{eqnarray} $$
$\left(as+24a-24b+\dfrac{1}{2}s-62\right)-\left(as-\dfrac{1}{2}s-12\right)=24a-24b+s-50$より
$$ \begin{eqnarray} \begin{cases} a-b+\dfrac{1}{24}s-\dfrac{25}{12}=0 & \\ as-\dfrac{1}{2}s-12=0 & \\ bs-\dfrac{1}{2}s+12=0 & \end{cases} \end{eqnarray} $$
$\left(as-\dfrac{1}{2}s-12\right)-s\left(a-b+\dfrac{1}{24}s-\dfrac{25}{12}\right)=bs-\dfrac{1}{24}s^2+\dfrac{19}{12}s-12$より
$$ \begin{eqnarray} \begin{cases} a-b+\dfrac{1}{24}s-\dfrac{25}{12}=0 & \\ bs-\dfrac{1}{24}s^2+\dfrac{19}{12}s-12=0 & \\ bs-\dfrac{1}{2}s+12=0 & \end{cases} \end{eqnarray} $$
$\left(bs-\dfrac{1}{24}s^2+\dfrac{19}{12}s-12\right)-\left(bs-\dfrac{1}{2}s+12\right)=-\dfrac{1}{24}s^2+\dfrac{25}{12}s-24$より
$$ \begin{eqnarray} \begin{cases} a-b+\dfrac{1}{24}s-\dfrac{25}{12}=0 & \\ s^2-50s+576=0 & \\ bs-\dfrac{1}{2}s+12=0 & \end{cases} \end{eqnarray} $$
$$ \begin{eqnarray} \begin{cases} a-b+\dfrac{1}{24}s-\dfrac{25}{12}=0 & \\ bs-\dfrac{1}{2}s+12=0 & \\ s^2-50s+576=0 & \end{cases} \end{eqnarray} $$

同値変形$[1]$だけで$a,b,s$の方程式と$b,s$の方程式と$s$の方程式がそれぞれ現れました。
$$ \begin{eqnarray} S\left(bs-\dfrac{1}{2}s+12,\ s^2-50s+576\right)&=&s\left(bs-\dfrac{1}{2}s+12\right)-b\left(s^2-50s+576\right)\\ &=&50bs-576b-\dfrac{1}{2}s^2+12s\\ &\underset{bs-\frac{1}{2}s+12}{\longrightarrow}&-576b-\dfrac{1}{2}s^2+37s-600\\ &\underset{s^2-50s+576}{\longrightarrow}&-576b+12s-312\\ \end{eqnarray} $$
より、実は$\{a-b+\dfrac{1}{24}s-\dfrac{25}{12},\ bs-\dfrac{1}{2}s+12,\ s^2-50s+576\}$は$\langle a^2s+b^2s-25,\ a^2s+b^2s-2bs+s-49,\ a^2s-2as+b^2s+s-1\rangle=\langle a-b+\dfrac{1}{24}s-\dfrac{25}{12},\ bs-\dfrac{1}{2}s+12,\ s^2-50s+576\rangle$のグレブナー基底ではありません。
しかし、ここまで連立方程式を解くという目的のもと同値変形をしてきたので、このまま解いて問題ありません。
$s^2-50s+576=0$を解くと
$s^2-50s+576=(s-32)(s-18)=0$より$s=32,\ 18$です。
$\left(1\right)s=32$の場合
$bs-\dfrac{1}{2}s+12=32b-16+12=32b-4=0$より$b=\dfrac{1}{8}$
$a-b+\dfrac{1}{24}s-\dfrac{25}{12}=a-\dfrac{1}{8}+\dfrac{32}{24}-\dfrac{25}{12}=a-\dfrac{21}{24}=a-\dfrac{7}{8}=0$より$a=\dfrac{7}{8}$
$\left(2\right)s=18$の場合
$bs-\dfrac{1}{2}s+12=18b-9+12=18b+3=0$より$b=-\dfrac{1}{6}$
$a-b+\dfrac{1}{24}s-\dfrac{25}{12}=a+\dfrac{1}{6}+\dfrac{18}{24}-\dfrac{25}{12}=a-\dfrac{28}{24}=a-\dfrac{7}{6}=0$より$a=\dfrac{7}{6}$
よって
$$ \begin{eqnarray} \begin{cases} a^2s+b^2s=25 & \\ a^2s+\left(1-b\right)^2s=49 & \\ \left(1-a\right)^2s+b^2s=1 & \end{cases} \end{eqnarray} $$
の解は、$a=\dfrac{7}{8},\ b=\dfrac{1}{8},\ s=32$または$a=\dfrac{7}{6},\ b=-\dfrac{1}{6},\ s=18$です。