割り算アルゴリズムとグレブナー基底
〜連立方程式でナンプレを解こう！〜（ロング版）
1. 自然数の割り算
小学生の頃学習した割り算を思い出すと，例えば，$5 \div 2$は商$2$余り$1$であった．他にも$13 \div 5$は商$2$余り$3$である．算数では具体例を使って割り算や商，余りを説明していたが，数学的に厳密に定義できるだろうか．ただし，ここで考えたいのは，$5 \div 2= 2.5$のように小数点以下まで考える割り算ではなく，余りも考慮した自然数の中だけの割り算である．さて，割り算の見方を変えると，「$5 \div 2$は商$2$余り$1$」からは数式 \[ 5= 2 \times 2 +1 \] が得られ， 「$13 \div 5$は商$2$余り$3$」からは \[ 13=2 \times 5 +3 \] が得られる．ここで「余り」がいつでも割る数より小さいことに注意する． これは「これ以上割れない」ということを意味する． このような表示を与えることを「割り算」と定義することで，数式を使って「割り算」を説明することができる．つまり，割り算の厳密な定義は以下の通りである：定義
自然数$a$を$b$で割るとは，負ではない整数$q$と$r$で条件
自然数の割り算は筆算すれば必ず答え（商と余り）を求めることができたことを思い出そう．これは割り算の答えがいつでも存在することを意味する．さらに，そのときの答えはひとつしかなかったことを思い出そう．つまり，次の事実が成り立つ．
-
$a=q \times b +r$である，
-
$r$は$b$より小さい
命題
自然数$a$を自然数$b$で割ったときの余りと商は必ず存在し，その答えはひとつしかない．
数学では定義も大事だが，その定義に対して
- 答えの存在
- 答えの一意性（ひとつしかないこと）
- 答えを見つける方法（アルゴリズム）
2. 1変数多項式の割り算
数や文字についての掛け算だけで作られた式を単項式という． 例えば，$2$や$-3x$，$x^2y$などである．単項式に対して- 掛けられている文字の個数を次数，
- 文字を取り除いた数を係数
- 足された各単項式のことをその多項式の項，
- 各項のうちで最も大きい次数を，その多項式の次数
-
$f$の最大次数が$g$の最大次数以上なら，$g$に足りない式を掛けて$f$から引くことで$f$の最大次数の項を打ち消し，ステップ(2)へ．
-
打ち消した後の式の最大次数が$g$の最大次数以上なら，その式に対してステップ(1)へ．小さければ筆算を終える．
定義
1変数多項式$f$を（$0$ではない）1変数多項式$g$で割るとは，1変数多項式$q$と$r$で条件
自然数の割り算では余りの条件は「割る数より小さい」であった．これは「これ以上割ることができない」を意味している．1変数多項式の割り算の場合，この条件が(2)の「余り$r$の次数は割る多項式$g$より次数が小さい」となる．
筆算を使うことで$1$変数多項式の割り算は必ず答えを求めることができる．特に，その答えはひとつしかない．つまり，自然数の割り算と同様に次の事実が成り立つ．
- (1) $f=q \times g + r$である，
- (2) $r$の次数は$g$の次数より小さい，
命題
1変数多項式$f$を（$0$ではない）1変数多項式$g$で割ったときの余りと商は必ず存在し，その答えは一意的である．
よって1変数多項式の割り算も
- 答えの存在
- 答えの一意性（ひとつしかないこと）
- 答えを見つける方法（アルゴリズム）
3. 2変数多項式の割り算
それでは変数をひとつ増やして，$x$と$y$の2変数多項式の割り算を考えてみよう． 1変数のときと同じように筆算してみると少し問題が起こる．実際，$x^3$を$x^2+y^2$で割る筆算を1変数多項式の場合と同様にしてみる． \[ \]
-
$x$の次数が大きい方の単項式が大きい．
-
$x$の次数が同じであれば，$y$の次数が大きい方の単項式が大きい．
-
${\rm LM}(f)$が${\rm LM}(g)$で割り切れるなら，$g$に足りない式を掛けて$f$から引くことで${\rm LM}(f)$を打ち消し，打ち消した後にできる式に対してステップ(1)に戻る．割り切れないならステップ(2)へ．
-
${\rm LM}(f)$の項を余りに移動させ，残った式が$0$でないならその式に対してステップ(1)に戻る．$0$だったら筆算を終える．
定義
辞書式順序に関して2変数多項式$f$を（$0$ではない）2変数多項式$g$で割るとは，2変数多項式$q$と$r$で条件
1変数の場合(2)の条件は次数が小さいことを意味しているので，この定義は1変数の場合と同じである．この条件(2)が「これ以上割ることができない」を意味している．
1変数の場合と同様で，筆算を使うことで$2$変数多項式の割り算は必ず答えを求めることができる．特に，その答えはひとつしかない．つまり，次の事実が成り立つ．
- (1) $f=q \times g + r$である，
- (2) $r$の各項は${\rm LM}(g)$で割り切れない，
命題
2変数多項式$f$を（$0$ではない）2変数多項式$g$で割ったときの余りと商は必ず存在し，その答えは一意的である．
よって2変数多項式の割り算も
- 答えの存在
- 答えの一意性（ひとつしかないこと）
- 答えを見つける方法（アルゴリズム）
4. $n$変数多項式の割り算
1変数多項式の割り算を2変数多項式の割り算に拡張する場合は色々改善する点があったが，3変数 多項式の割り算は2変数多項式の割り算をそのまま拡張すればよい． 変数$x,y,z$の$3$変数多項式を考える． まず単項式の大小関係を次のルールで決める．-
$x$の次数が大きい方の単項式が大きい．
-
$x$の次数が同じであれば，$y$の次数が大きい方の単項式が大きい．
-
$x$と$y$のそれぞれの次数が同じであれば，$z$の次数が大きい方の単項式が大きい．
$x_1$の次数が大きい方の単項式が大きい．
$x_1$の次数が同じであれば，$x_2$の次数が大きい方の単項式が大きい．
$x_1$と$x_2$のそれぞれの次数が同じであれば，$x_3$の次数が大きい方の単項式が大きい．
- $\vdots$
$x_1,x_2,\ldots,x_{n-1}$のそれぞれの次数が同じであれば，$x_n$の次数が大き方の単項式が大きい．
定義
辞書式順序に関して$n$変数多項式$f$を（$0$ではない）$n$変数多項式$g$で割るとは，$n$変数多項式$q$と$r$で条件
さらに，筆算から次の事実が成り立つ．
$f=q \times g + r$である，
$r$の各項は${\rm LM}(g)$で割り切れない，
定義
$n$変数多項式$f$を（$0$ではない）$n$変数多項式$g$で割ったときの余りと商は必ず存在し，その答えは一意的である．
よって一般にどんな多項式に対しても，その割り算の
- 答えの存在
- 答えの一意性（ひとつしかないこと）
- 答えを見つける方法（アルゴリズム）
5. 複数の多項式での割り算
さらに多項式の割り算を拡張していく．ここまではひとつの多項式で割ることを考えてきたが，複数の多項式で割ることも考えられる． 実際は次のように拡張する．定義
多項式$f$を複数の（$0$ではない多項式）$g_1,g_2,\ldots,g_s$で割るとは，多項式$q_1,q_2,\ldots,q_s$と$r$で条件
この割り算を実行するために，筆算アルゴリズムを次のように改良する．
多項式$f$を$g_1,g_2,\ldots,g_s$で割る場合，
- (1) $f = q_1g_1+q_2 g_2 +\cdots + q_s g_s +r$である，
- (2) $r$の各項は${\rm LM}(g_1), {\rm LM}(g_2),\ldots, {\rm LM}(g_s)$のいずれでも割り切れない，
- (3)（おまじない）$q_i$が$0$でないならば，${\rm LM}(f)$は辞書式順序に関して${\rm LM}(q_i g_i)$以上である．
${\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$だったら筆算を終える．
- 答えの存在
- 答えを見つける方法（アルゴリズム）
定義
ゼロではない多項式の集まり$g_1,g_2,\ldots,g_s$がグレブナー基底であるとは，どんな多項式$f$を$g_1,g_2,\ldots,g_s$で割っても，割る順番によらずに$f$の多項式の余りが一意的になるときにいう．
上の例だと$xy-1$と$y^2-1$はグレブナー基底ではない．しかし，この式に$x-y$という式を追加することで，グレブナー基底にすることができる．つまりどんな多項式$f$を3つの多項式$xy-1$と$y^2-1$と$x-y$で割っても，割る順番に関わらず余りは一意的である．
実は，多項式の集合はいくつか多項式を追加することでいつでもグレブナー基底にすることができる．
次の節で，このグレブナー基底の作り方と，グレブナー基底の連立方程式への応用を紹介する．
6. 割り算の連立方程式への応用
多項式$f_1,f_2,\ldots,f_s$があったとき，ブッフバーガーアルゴリズムという計算でグレブナー基底を作ることができる．具体的に \[ f_1=xy+z^2-2, f_2=x^2-yz, f_3=xz-y^2 \] という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,\ldots,f_s$からブッフバーガーアルゴリズムをはじめ，アルゴリズムが終了したときのすべての多項式が$f_1,f_2,\ldots,f_s,f_{s+1},\ldots,f_t$だったとき，この多項式の集まりはグレブナー基底となっている．
この方法で作ったグレブナー基底は連立方程式に応用できる．
連立方程式を解く極意は，いくつかの式をうまく組み合わせて変数が少ない式を見つけることである．
例えば，連立方程式
\[
\begin{cases}
2x +3y=3 \\
3x+2y=2
\end{cases}
\]
の場合，一つ目の式に$3$を掛けて，二つ目の式に$2$を掛けて両辺を引くと$x$が消えて$5y=5$という式が得られる．
よって$y=1$となり一つ目の式に代入することで$x=0$がわかる．
では連立方程式
\[
\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$変数$x,y,z$の連立方程式を式変形して$z$だけの式が作れるならば，そのような式はグレブナー基底から見つけられる．
- グレブナー基底の中に$z$だけの式がないのなら，どう式変形しても$z$だけの式を作ることはできない．
- 連立方程式の解が$(x,y,z)=(a,b,c)$の1個しかない場合は$x-a,y-b,z-c$という形の式が必ずグレブナー基底に現れる．
-
$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$を作る．
7. ナンプレを連立方程式で解いてみる
最後に，グレブナー基底を使ってナンプレを解いてみる．ナンプレのルールを知らない人は，まず調べてみよう． ナンプレの各マス目に対し， $81$個の変数$x_i$を以下のように対応させる．
- すべての$F(x_j)=0$，
- 同じ列，行，ブロックのどれかにいるすべての$i$と$j$に対する$G(x_i,x_j)=0$，
- すべての$H(x_i)=0$
