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

1. 数学は公式を使うだけの学問ではない

高校までの数学では，計算や公式を使うことが中心に見えるかもしれない． たとえば，方程式を解く，因数分解する，微分や積分を計算する，三角関数の公式を使う，といった内容である． もちろん，計算は数学にとって重要である． しかし，本来の数学は，決められた公式に数を代入するだけの学問ではない．

数学では，まず何を考えるのかをはっきりさせる． そのために「定義」を作り，その定義のもとでどのような法則が成り立つかを調べる． さらに，すでに知っている概念をより広い世界へ拡張し，新しい対象にも同じ考え方が通用するかを調べることも，大学数学の基本的な姿勢である．

たとえば，私たちは小学校で自然数の割り算を学んだ． 大学数学では，それを単なる計算方法として覚えるだけではなく，「割り算とは何をしているのか」を定義として捉え直す． そして，その定義をもとにして，自然数だけでなく，1変数多項式，多変数多項式，さらには複数の多項式による割り算へと考え方を広げていく．

このような「対象を数学の言葉に翻訳し，定義を作り，概念を拡張する」考え方は，情報科学においても重要である． プログラミングをするときにも，現実の問題をそのままコンピュータに渡すことはできない． まず，問題を数学的・論理的な形に整理する必要がある． 今回の講義では，その一例として，ナンプレを多項式の連立方程式に翻訳し，グレブナー基底という道具で扱う考え方を紹介する．

2. 割り算を定義する

ここからは，「割り算」という身近な概念を出発点にする． まず自然数の割り算を定義し，その後で同じ発想を多項式の世界へ拡張していく．

まず，小学校で学んだ自然数の割り算を思い出そう． たとえば，「$13$を$5$で割ると商$2$余り$3$」である． これは数式で \[ 13=2\times 5+3 \] と表すことができる． ここで余り$3$は割る数$5$より小さい． この「余りが割る数より小さい」という条件が，「これ以上割ることができない」という意味を持っている．

数学では，このように日常的に知っている計算も，条件を明確にして定義する． そして，その定義に対して次のようなことを考える．

• 答えはいつでも存在するか．
• 答えは一意的か．
• 答えを求める方法，つまりアルゴリズムはあるか．

自然数の割り算では，筆算によって商と余りを求めることができる． つまり，答えを見つけるアルゴリズムがある．

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

次に，割り算の考え方を自然数から多項式へ拡張する． ここで大切なのは，計算方法が似ているというだけではなく，「商と余りを作る」という定義の形が同じであるという点である．

高校数学では，1変数多項式の割り算を学ぶ． 自然数の割り算と同じように， \[ \text{割られるもの}=(\text{商})(\text{割るもの})+\text{余り} \] という形を目指す．

実際に，$x^2+3x+5$を$x+1$で割ってみる． 筆算は次のように行う．

このとき，商は$x+2$，余りは$3$である． したがって \[ x^2+3x+5=(x+1)(x+2)+3 \] が得られる．

ここでも大切なのは，「余りの次数が小さい」という条件である． これは自然数の割り算で「余りが割る数より小さい」と言っていたことに対応している． つまり，余りは「これ以上割れない部分」を表している．

4. 2変数多項式の割り算と辞書式順序

さらに概念を拡張して，$x$と$y$の2変数多項式を考える． 1変数でうまくいった定義をそのまま使いたいが，変数が増えると新しい問題が現れる． このように，概念を拡張するときには，何をそのまま残し，何を修正する必要があるかを考えることが重要である．

1変数のときと同じように割り算したいが，ここで問題が起こる． たとえば，$x^3$を$x^2+y^2$で割る筆算を1変数の場合と同じ気持ちで行うと，次のようになる．

1変数の場合，次数が大きい項を消すと次数が下がっていく． しかし2変数では，$x^2$と$y^2$のように同じ次数でも異なる単項式があり，次数だけを見ていると筆算がうまく終わらないことがある． そこで，単項式に順番をつける必要がある．

ここでは，変数に順番をつけて，その順に比べる方法を使う． たとえば，$x$を先に比べ，$x$の次数が同じなら$y$を比べることにする． このとき， \[ 1 < y < y^2 < x < xy < x^2 < x^3 \] のような順番になる． この順番を辞書式順序という． 辞書で単語を並べるとき，最初の文字から順に比べることに似ているためである．

たとえば，辞書式順序で$x$を先に比べると， \[ f=2x^3+x^2y+3xy^2-y^3+1 \] の先頭単項式は$\mathrm{LM}(f)=x^3$である．

この辞書式順序を使うと，2変数多項式でも筆算を定義できる． 考え方は次の通りである．

• 割られる多項式の先頭単項式を見る．
• それが割る多項式の先頭単項式で割り切れるなら，対応する項を打ち消す．
• 割り切れない項は余りに移す．
• これを繰り返す．

実際に，辞書式順序に関して$x^3+x^2y$を$x^2+y^2$で割ってみる．

したがって \[ x^3+x^2y=(x+y)(x^2+y^2)+(-xy^2-y^3) \] であり，商は$x+y$，余りは$-xy^2-y^3$である．

変数が3個以上の場合も同じである． たとえば変数$x,y,z$について，まず$x$を比べ，次に$y$を比べ，最後に$z$を比べる，というように変数の順番を決めると辞書式順序が定まる． この順序に関して先頭単項式を見ながら割り算を行う．

5. 複数の多項式で割る

ここまでで，1つの多項式で割ることは，多変数の場合にも拡張できた． 次は，割る多項式を1つから複数へ拡張する． これは連立方程式を扱うために自然な拡張である．

連立方程式を考えるときには，1つの式だけでなく複数の式が現れる． そのため，多項式を複数の多項式で割ることを考えたい． たとえば，ある多項式$f$を$g_1,g_2$で割るとは， \[ f=q_1g_1+q_2g_2+r \] という形に表すことである． ここで$r$は，$g_1,g_2$のどちらでもこれ以上割れない余りである．

実際に，辞書式順序で$x^2y+xy^2+y^2$を$xy-1$と$y^2-1$で割ってみる．

すると \[ f=(x+y)(xy-1)+1\cdot (y^2-1)+(x+y+1) \] となる．

しかし，複数の多項式で割ると，新しい問題が起こる． それは，割る順番によって余りが変わることがあるという問題である． 1つの多項式で割る場合には余りが一意的だったが，複数の多項式ではそうとは限らない．

実際に，割る順番で余りが変わる例を見てみよう．

この定義だけを見ると少し抽象的に感じるかもしれない． しかし，グレブナー基底は連立方程式を解くために非常に役立つ．

6. ブッフバーガーアルゴリズム

グレブナー基底は，ただの名前ではなく，実際に計算で作ることができる． そのための代表的な方法がブッフバーガーアルゴリズムである． ここでは雰囲気だけを紹介する．

多項式$f_1,f_2,\ldots,f_s$から始める． ブッフバーガーアルゴリズムでは，次の操作を繰り返す．

1. 多項式の中から2つを選ぶ．
2. その2つの先頭単項式が打ち消し合うような組み合わせを作る．
3. その組み合わせを，今持っている多項式たちで割る．
4. 余りが$0$でなければ，その余りを新しい多項式として追加する．
5. どの2つを選んでも余りが$0$になるまで続ける．

この操作は大変そうに見えるが，重要なのは機械的に実行できることである． つまり，手順さえ決めればコンピュータに計算させることができる． そして，このアルゴリズムが終了したときに得られる多項式の集まりがグレブナー基底になる．

この意味で，グレブナー基底は「よい性質を持つ多項式の集まり」であるだけでなく，具体的なアルゴリズムによって作れる対象である．

7. グレブナー基底と連立方程式

連立方程式を解くときの基本的な考え方は，いくつかの式をうまく組み合わせて，変数が少ない式を作ることである． たとえば，連立1次方程式では，式を足したり引いたりして1つの変数を消去する．

同じように，多項式の連立方程式でも，式をうまく組み合わせることで変数を消去したい． たとえば， \[ \begin{cases} f_1=xy+z^2-2=0,\\ f_2=x^2-yz=0,\\ f_3=xz-y^2=0 \end{cases} \] という連立方程式を考える． この式から，うまく変数$x,y$を消去すると， \[ z^4-3z^2+2=0 \] という$z$だけの式が得られる．

問題は，このような式をどうやって見つけるかである． 手計算で探すのはかなり難しい． しかし，$z$を最後に比べる辞書式順序に関するグレブナー基底を計算すると，このような$z$だけの式を見つけることができる．

たとえば，上の例では被約グレブナー基底を計算すると， \[ z^4-3z^2+2,\quad yz^2-y,\quad y^3+z^3-2z,\quad x-y^2z \] のような多項式が現れる． 最初の式が，欲しかった$z$だけの式である． このように，グレブナー基底は「連立方程式を解く」という問題を，「決まったアルゴリズムで多項式を計算する」という問題に変えてくれる．

もちろん，実際の計算は簡単ではない． しかし，Macaulay2 などのコンピュータ代数ソフトウェアを使うと，グレブナー基底を計算することができる． 抽象的な数学の定義が，コンピュータで計算するためのアルゴリズムにつながっているのである． この例の計算コードは こちら から確認できる．

8. ナンプレを連立方程式に翻訳する

最後に，ナンプレを連立方程式として表す考え方を紹介する． ここで重要なのは，ナンプレを「数字を書き込むパズル」としてではなく，多項式の連立方程式として翻訳することである．

まず，ナンプレの各マスに変数を対応させる． たとえば，左上から順に \[ x_1,x_2,\ldots,x_{81} \] という変数を置く． それぞれの変数は，そのマスに入る数字を表す．

まず，各マスには$1$から$9$のどれかが入る． これは，多項式 \[ F(x)=(x-1)(x-2)\cdots(x-9) \] を使って \[ F(x_i)=0 \] と表せる． なぜなら，$F(x)$は$x=1,2,\ldots,9$のときだけ$0$になるからである．

次に，同じ行，同じ列，同じ$3\times 3$ブロックにある2つのマスには，同じ数字が入ってはいけない． この条件も，多項式を使って表すことができる． ここでは詳しい理由には立ち入らないが，たとえば \[ G(x_i,x_j)=\frac{F(x_i)-F(x_j)}{x_i-x_j} \] という多項式を考えるとよい． 同じ行・列・ブロックにある2つのマス$x_i,x_j$に対して，この$G(x_i,x_j)$から作られる方程式を入れることで，「同じ数字を使ってはいけない」という条件を多項式の言葉で表すことができる． この講義では，細かい仕組みよりも，ナンプレのルールをこのような多項式の式へ翻訳できる，という点を見てほしい．

さらに，最初から数字が入っているマスについては，その数字と等しいという条件を入れる． たとえば，$i$番目のマスに$5$が入っているなら， \[ x_i-5=0 \] を加える．

たとえば，次のようなナンプレを考える．

このナンプレを解くには，次の3種類の方程式をすべて集めればよい．

• 各マスに$1$から$9$のどれかが入ることを表す方程式$F(x_i)=0$．
• 同じ行・列・ブロックにある2つのマスに同じ数字が入らないことを表す，$G(x_i,x_j)$から作られる方程式．
• 最初から入っている数字を固定する方程式$x_i-a_i=0$．

このようにして，ナンプレのルールをすべて多項式の連立方程式に翻訳することができる． できあがる式は非常に多いが，考え方は単純である． この連立方程式に対してグレブナー基底を計算すれば，ナンプレの答えを求めることができる． 答えが一意的なナンプレでは，最終的に \[ x_i=a \] という形の式が各マスに対して現れる． これは「$i$番目のマスには$a$が入る」という意味である． この例のコードは こちら から確認できる．

9. 方程式に翻訳するという考え方

ここまで，ナンプレを多項式の連立方程式に翻訳する話を見た． このように，何かの対象を方程式で表すことは，実は高校数学でもすでに行っている．

たとえば，高校数学では軌跡の方程式を学ぶ． 円や直線などの図形を，点の集まりとして見るだけでなく， \[ x^2+y^2=1 \] のような方程式で表すのである． これは，図形を「式」に翻訳していると考えることができる．

図形を方程式に翻訳すると，視覚的な情報に頼らずに扱うことができる． 図を描かなくても計算できるし，複雑な図形も式として扱える． さらに，4次元以上の図形のように目に見えない対象も，方程式を使えば考えることができる．

ナンプレの場合も同じである． そのままでは，ナンプレは数字を書き込むパズルである． しかし，各マスを変数にし，ルールを多項式で表すと， \[ \text{ナンプレ} \quad\longrightarrow\quad \text{多項式の連立方程式} \] に翻訳できる．

この考え方は，情報科学やプログラミングでも重要である． 現実の問題をそのままコンピュータに渡すことはできない． まず，数学的・論理的な形に翻訳し，計算できる形にする必要がある． 今回の講義で見たグレブナー基底は，その一例である．

10. まとめ

今回見たことをまとめよう．

• 数学では，まず対象を定義し，その定義のもとで何が成り立つかを考える．
• すでに知っている概念を，より広い世界へ拡張することも大学数学の基本的な考え方である．
• 自然数の割り算も，多項式の割り算も，「商」と「余り」を定義することで理解できる．
• 多変数多項式では，辞書式順序を使って先頭単項式を決めることで割り算ができる．
• 複数の多項式で割ると余りが順番に依存することがある．
• グレブナー基底は，余りを一意的にし，連立方程式を機械的に扱うための道具である．
• ブッフバーガーアルゴリズムにより，グレブナー基底は機械的に作ることができる．
• ナンプレのような問題も，多項式の連立方程式に翻訳できる．
• 図形やパズルを方程式に翻訳すると，グレブナー基底のような数学の道具を使える．

公式を覚えて計算するだけでなく，身近な概念を定義として捉え直し，それをより広い対象へ拡張する． さらに，図形やパズルのような対象を数学の言葉に翻訳し，定義とアルゴリズムによって扱える形にする． これが大学数学の大きな魅力の一つであり，情報科学にもつながる考え方である．