割り算アルゴリズムとグレブナー基底
〜連立方程式でナンプレを解こう！〜

1. 1変数多項式の割り算

高校数学IIで学習する1変数多項式の割り算を復習する．まず1変数多項式の割り算の筆算の方法を見る．筆算は次の手順で行う：1変数多項式$f$を$g$で割る場合，

• $f$の最大次数が$g$の最大次数以上なら，$g$に足りない式を掛けて$f$から引くことで$f$の最大次数の項を打ち消し，ステップ(2)へ．

• 打ち消した後の式の最大次数が$g$の最大次数以上なら，その式に対してステップ(1)へ．小さければ筆算を終える．

実際，具体例で考えると次の計算を行う． $x^2+3x+5$を$x+1$で割ることを考える．すると筆算は以下のように書ける． \[ \] このとき，$x+2$が商，$3$が余りとなっている．よって数式 \[ x^2+3x+5=(x+1)(x+2)+3 \] が得られる． 実はこの表示を得ることが割り算の目的である．この筆算を元に1変数多項式の割り算を厳密に定義すると次の通りになる． 条件(1)の数式を得ることが割り算の目的であったが， 条件(2)は「これ以上割ることができない」を意味している． 筆算を使うことで$1$変数多項式の割り算は必ず答えを求めることができる．

2. 2変数多項式の割り算

次に変数をひとつ増やして，$x$と$y$の2変数多項式の割り算を考えてみよう． 1変数のときと同じように筆算してみると少し問題が起こる．実際，$x^3$を$x^2+y^2$で割る筆算を1変数多項式の場合と同様にしてみる． \[ \] $1$変数の場合，$x^2$や$x^3$のような次数が$2$や$3$の単項式はこれらしかない． しかし，$2$変数の場合$x^2$や$y^2$のように次数が同じだけど異なる単項式が存在する．その結果，この筆算のように，次数が最大の項をひとつ打ち消しても，次数が下がらず，筆算が終わらないことが起こる．この問題を解決するために，次数全体を比べるのではなく，それぞれの変数の次数ごとに大きさを比較して，すべての単項式に順番（大小）をつけることを考える． 単項式の大小関係を次のルールで決める．

• $x$の次数が大きい方の単項式が大きい．

• $x$の次数が同じであれば，$y$の次数が大きい方の単項式が大きい．

例えば，$1 \lt y \lt y^2 \lt x \lt x y^2 \lt x^2 \lt x^3y$のようになる． この大小関係を辞書式順序という．注意して欲しいのは$y^2 \lt x$のように全体の次数が大きかったとしても辞書式順序では小さくなる場合があることである．どれだけ次数が高くても，$x$の次数が小さければ小さくなるのである．多項式$f$の一番大きい項の単項式を先頭単項式といい，${\rm LM}(f)$と書くことにする． 例えば，$f=2x^3+x^2y+3xy^2-y^3+1$の辞書式順序で最大の項は$2x^3$なので，${\rm LM}(f)=x^3$である． さて，この辞書式順序を使って，筆算を次のように改良する． 2変数多項式$f$を$g$で割る場合，

• ${\rm LM}(f)$が${\rm LM}(g)$で割り切れるなら，$g$に足りない式を掛けて$f$から引くことで${\rm LM}(f)$を打ち消し，打ち消した後にできる式に対してステップ(1)に戻る．割り切れないならステップ(2)へ．

• ${\rm LM}(f)$の項を余りに移動させ，残った式が$0$でないならその式に対してステップ(1)に戻る．$0$だったら筆算を終える．

1変数の場合ステップ(1)では次数を下げていたが，2変数の場合，辞書式順序に関して大きさを下げている． それでは実際に具体例で考える． 辞書式順序に関して$x^3+x^2 y$を$x^2+y^2$で割ってみる． \[ \] すると \[ x^3+x^2y= (x+y) \times (x^2+y^2) +(-xy^2-y^3) \] なので，商$x+y$，余り$-xy^2-y^3$と考えることができる． この筆算を元に，2変数多項式の割り算を定義すると次の通りになる． 1変数の場合(2)の条件は次数が小さいことを意味しているので，この定義は1変数の場合と同じである．この条件(2)が「これ以上割ることができない」を意味している． 1変数の場合と同様で，筆算を使うことで$2$変数多項式の割り算は必ず答えを求めることができる．

3. $n$変数多項式の割り算

1変数多項式の割り算を2変数多項式の割り算に拡張する場合は色々改善する点があったが，3変数 多項式の割り算は2変数多項式の割り算をそのまま拡張すればよい． 変数$x,y,z$の$3$変数多項式を考える． まず単項式の大小関係を次のルールで決める．

• $x$の次数が大きい方の単項式が大きい．

• $x$の次数が同じであれば，$y$の次数が大きい方の単項式が大きい．

• $x$と$y$のそれぞれの次数が同じであれば，$z$の次数が大きい方の単項式が大きい．

この大小関係も同様に辞書式順序という． 辞書式順序さえ定義できれば筆算アルゴリズムは同じステップで計算できる．割り算の定義も特に変える必要はない． さらに変数を$4$個，$5$個，$6$個とどんどん増やしても，辞書式順序さえ定義できれば筆算アルゴリズムと割り算は同じ定義で大丈夫である．つまり$n$個の変数$x_1,x_2,\ldots,x_n$の$n$変数多項式の割り算が定義できるのである．

4. 複数の多項式での割り算

さらに多項式の割り算を拡張していく．ここまではひとつの多項式で割ることを考えてきたが，複数の多項式で割ることも考えられる． 実際は次のように拡張する． この割り算を実行するために，筆算アルゴリズムを次のように改良する． 多項式$f$を$g_1,g_2,\ldots,g_s$で割る場合，

• ${\rm LM}(f)$が${\rm LM}(g_1)$で割り切れるなら，$g_1$に足りない式を掛けて$f$から引くことで${\rm LM}(f)$を打ち消し，打ち消した後にできる式に対してステップ(1)に戻る．割り切れないならステップ(2)へ．

• ${\rm LM}(f)$が${\rm LM}(g_2)$で割り切れるなら，$g_2$に足りない式を掛けて$f$から引くことで${\rm LM}(f)$を打ち消し，打ち消した後にできる式に対してステップ(1)に戻る．割り切れないならステップ(3)へ．

•   $\vdots$

• ${\rm LM}(f)$が${\rm LM}(g_s)$で割り切れるなら，$g_s$に足りない式を掛けて$f$から引くことで${\rm LM}(f)$を打ち消し，打ち消した後にできる式に対してステップ(1)に戻る．割り切れないならステップ(r)へ．

• ${\rm LM}(f)$の項をあまりに移動させ，残った式が$0$でないならその式に対してステップ(1)に戻る．$0$だったら筆算を終える．

つまり，ひとつの多項式で割る場合は${\rm LM}(g)$で${\rm LM}(f)$が割り切れるかどうかだけ見ていたが，複数の多項式で割る場合，それを${\rm LM}(g_1)$から順に判定していき，どれでも割り切れなかったときにはじめて余りに移動させるのである． この筆算を2変数の場合に試してみよう． $x^2+xy^2+y^2$を$xy-1$と$y^2-1$で割ってみると \[ \] となる． すると \[ f=(x+y) \cdot (xy-1) + 1 \cdot (y^2-1)+(x+y+1) \] となることがわかる．

5 割り算の連立方程式への応用

割り算アルゴリズムの連立方程式への応用を紹介する． 連立方程式を解く極意は，いくつかの式をうまく組み合わせて変数が少ない式を見つけることである． 例えば，連立方程式 \[ \begin{cases} f_1=xy+z^2-2=0 \\ f_2=x^2-yz=0\\ f_3=xz-y^2=0 \end{cases} \] を考えてみよう． 実は変数をうまく消せば \[ z^4-3z^2+2=0 \] が得られる． どうすればこの式を見つけることができるだろうか．おそらくかなり時間をかけても見つけることは難しいだろう．しかし，ブッフバーガーアルゴリズムという多項式の割り算に関するアルゴリズムを使えば見つけることができる．3つの多項式$f_1,f_2,f_3$に関するブッフバーガーアルゴリズムを簡単に説明する．

• $f_1,f_2,f_3$から適当に2つ選ぶ（例えば$f_1,f_2$）．

• 選んだ2つの多項式の先頭単項式を打ち消した式$f$を考える （${\rm LM}(f_1)=xy$と${\rm LM}(f_2)=x^2$だから$x^2y$（最小公倍元）に揃えて打ち消す，つまり$f=xf_1-y f_2$）．

• $f$を$f_1,f_2,f_3$で割った余りを$r$とする（$r=-2x+2y^2z$）．

• $r \neq 0$ならば$f_4=r$とし，ステップ(1)を$f_1,f_2,f_3,f_4$で始める（次は$f_1$と$f_4$を選ぶなど）．

• ステップ(1)からステップ(2)の操作をどの2つの多項式を選んでも$r=0$となるまで続ける．

このアルコリズムはかなり時間がかかるが，必ず有限回の操作でアルゴリズムが終了する． アルゴリズムが終了したときに追加した多項式を含めたすべての多項式$f_1,f_2,\ldots,f_s$をグレブナー基底と呼ぶ． そしてこのグレブナー基底の中から先ほどの変数$z$だけの式を見つけることができる．この結果を消去定理と呼ぶ． つまり，グレブナー基底を計算すれば答え，または簡単な式を見つけることができるのである． ただし，その計算量は膨大である．実際，上の$f_1,f_2,f_3$から \[ z^4-3z^2+2=0 \] を見つける場合，

• $f_1,f_2$から$f_4=-2x+2y^2z$を作る．

• $f_1,f_4$から$f_5=-2y^3z-2z^3+4$を作る．

• $f_3,f_4$から$f_6=-2y^2z^2+2y^2$を作る．

• $f_5,f_6$から$f_7=4y^3+4z^3-8z$を作る．

• $f_5,f_7$から$f_8=8z^4-24z^2+16$を作る．

この操作によってようやく欲しい式が見つかる． いつか必ず見つかるが，ペアの選び方によっては見つかるまでかなり時間がかかる場合がある． 手計算では大変だが，Macaulay2（リンク）と呼ばれるオンラインで使用できるソフトウェア（英文ページ）を使えばグレブナー基底は計算できる． ただし表示されるグレブナー基底は「余分」なものを取り除いた被約グレブナー基底というものである． 上の$f_1,f_2,f_3$に対して被約グレブナー基底を計算すると， \[ z^4-3z^2+2,yz^2-y,y^3+z^3-2z,x-y^2z \] となる（コードのリンク）．特に，この4つの多項式の連立方程式を解けば，元の連立方程式の解を求めることができる． また変数を増やすと，辞書式順序で見る最後の変数だけの式をグレブナー基底から見つけることができる．

6. ナンプレを連立方程式で解いてみる

最後に，グレブナー基底を使ってナンプレを解いてみる．ナンプレのルールを知らない人は，まず調べてみよう． ナンプレの各マス目に対し， $81$個の変数$x_i$を以下のように対応させる． そして多項式$F(x_j), G(x_i,x_j)$を次のように定義する． $ j = 1 , \dots, 81$ に対し，\[F(x_j) = (x_j-1)(x_j-2) \cdots (x_j-9) \] $1 \leq i \lt j \leq 81$に対し， \[G(x_i,x_j)=\frac{F(x_i)-F(x_j)}{(x_i-x_j)}\] また初期状態について，$i$のマス目に$a_i$という数字が入っていた場合， \[H(x_i)=x_i-a_i\] とする． 例として，以下のようなナンプレについて考えてみる． このナンプレにおける$H(x_i)$は， \[x_{2}-3,x_{5}-9,x_{7}-5,x_{11}-5,x_{12}-8,x_{13}-3,x_{14}-2,x_{17}-1,\] \[x_{19}-7,x_{24}-1,x_{26}-2,x_{28}-5,x_{33}-3,x_{35}-4,x_{38}-4,\] \[x_{39}-3,x_{40}-2,x_{41}-6,x_{44}-9,x_{48}-1,x_{51}-9,x_{53}-3,x_{57}-7,\] \[x_{59}-4,x_{61}-2,x_{62}-5,x_{65}-2,x_{68}-1,x_{70}-3,x_{72}-4,x_{76}-6,x_{79}-1\] となる． このとき，

• すべての$F(x_j)=0$，
• 同じ列，行，ブロックのどれかにいるすべての$i$と$j$に対する$G(x_i,x_j)=0$，
• すべての$H(x_i)=0$

からなる約1000個の連立方程式を解くとナンプレの答えがわかる． ナンプレは答えが一つしかないので，$x_i=a$という形の式が$81$個グレブナー基底に現れることになる． よってMacaulay2を使ってナンプレの答えを求めることができる．実際にこの例のコード（リンク）を載せておくので，コピー＆ペーストで確かめてみてほしい．なお，グレブナー基底はかなり計算がかかる（ほとんど終わらない）ので初期状態が少ないとだいたい解けなくなる．実用的ではないが，色々な方法で問題を解くのは数学の醍醐味のひとつである．