最近、妹がグレブナー基底に興味を持ち始めたのだが。

第4話

『辞書式順序』

コーヒーの氷が溶けてカランと音を立てる。

俺はストローの屈折部分を真っ直ぐに伸ばした。

「辞書は、英語ならアルファベット順に、日本語なら五十音順に並んでいる。」

りんはテーブルの上にある英和辞書をペラペラとめくっている。

長い睫毛が、カフェの外から入る日光に反射してキラキラと輝いている。

「確かに言われてみればそうですよね。でもそれがどう単項式順序に関係するんですか？」

りんは眉をへの字にして俺を見つめる。

俺は慣れた口調で説明を始める。

「この辞書と同じように、単項式を並べてみるんだ。さっきみたいに x と y の単項式を考えよう。」

「分かりました。」

「まず、x の方が y より大きいとする。」

x>y

「はい。」

「そして、同じ変数で次数が高いものは大きいとする。例えば、」

x^4 > x^3

y^2 > y

「が成り立つとする。」

「自然な感じがしますね。」

「それじゃあ、これらを元にして"辞書的に"単項式を並べていこう。辞書では、"ant"と"apple"、どっちの方が先に載ってるかな？」

「えーと、"ant"ですかね？」

「正解。それはどうして？」

「んーと、まず、先頭は同じ"a"なので、次に二番目を見ると、"ant"は"n"、"apple"は"p"で、"n"より"p"の方が早いので、"ant"の方が先に出てくる、で合ってますか？」

「大正解。今のを紙にまとめようか。」

１番目：ant も apple も同じ a

２番目：ant は n 、apple は p 。n より p の方がアルファベット順が早い。

結論：ant の方が apple より先に辞書に載っている。

「…なんか、当たり前って感じですよね。数学じゃない気がします。」

「これと同じ考えを、xy^2 と xy の間で考えてみよう。まず、先頭、つまり、一番左を見る。何かな？」

「xy^2 も xy も両方 x ですね。」

「そうだね。では、次に２番目を見てみよう。」

「xy^2 は y^2 、xy は y ですね。」

「つまり？」

「y^2 の方が y より大きい……？

「もう一声！」

「xy^2 の方が xy より大きい……？」

「正解（エサクタ）！」

xy^2>xy

俺はスペイン語で正解を意味する語を叫んだ。

無反応のりんを尻目に俺は話を続ける。

「こんな感じで左から見てって大きい順に並べるのが辞書式順序なんだ。」

「なるほど。」

「正確な定義は次のようになる。」

***

定義（２変数の辞書式順序）

a_1, a_2, b_1, b_2 を0以上の整数とする。

単項式 x^{a_1}y^{a_2} と x^{b_1}y^{b_2} を考える。

このとき、順序>を

x^{a_1}y^{a_2} > x^{b_1}y^{b_2} ⇔ 「a_1>b_1」 または 「a_1=b_1 かつa_2>b_2」

で定義する。この順序のことを(x>yの)辞書式順序と呼ぶ。

***

「確か授業でもやりましたけど、『または』と『かつ』が入り組んでいて分かりづらいんですよね。」

「じゃあ、具体的な例で試してみようか。」

「はい！」

「次の単項式たちは、辞書式順序ではそれぞれどっちが大きいかな？」

***

第１問：xy と y^2

第２問：x^2y^2 とx^2y

第３問：xy^3 と x^2y

みんなもどっちが大きいか考えてみよう( ・∇・)！！

***

りんは問題の下にペンで可愛い顔文字を描いた。

みんなって誰だ。

「えーと、まず第１問は、x^{a_1}y^{a_2}=xy、x^{b_1}y^{b_2}=y^2 と見ると、a_1=1、a_2=1、b_1=0、b_2=2 ですよね。」

「うんそうだね。」

「だから、『a_1>b_1』を満たすので、x^{a_1}y^{a_2} > x^{b_1}y^{b_2}、つまり、」

xy > y^2

「ってことでいいですか？」

「その通り！」

「えへへ。」

「直感的には xy と y^2 のまず x の指数を比較して、xy の方が大きいからってことだね。この調子で第２問目いってみよう。」

「はい！第２問目も同じように x^{a_1}y^{a_2}=x^2y^2、x^{b_1}y^{b_2}=x^2y と見て、a_1=2、a_2=2、b_1=2、b_2=1 とします。」

「うん。」

「今度は a_1=b_1 なので、次に a_2 と b_2 を比較します。a_2>b_2 ですので、『a_1=b_1 かつ a_2>b_2』が成り立ちます。よって、」

x^2y^2 > x^2y

「です！」

「大正解！ x の指数が同じだったから、y の指数で比較したってことだね。」

「えへへ。」

「それじゃあ、最後の第３問目はどうかな？」

「はい！同じように x^{a_1}y^{a_2}=xy^3、x^{b_1}y^{b_2}=x^2y とすると、a_1=1、a_2=3、b_1=2、b_2=1で、『a_1<b_1』なので、『a_1>b_1』と『a_1=b_1かつ a_2>b_2』のどちらも満たしません。よって、『xy^3 > x^2y』は成り立ちません。」

「その通り。じゃあ、逆に『xy^3 < x^2y』は成り立つかな？」

「えーと、逆に c_1=2、c_2=1、d_1=1、d_2=3 のように、x^{c_1}y^{c_2}=x^2y、x^{d_1}y^{d_2}=xy^3 として入れ替えて考えてみれば、『c_1>d_1』が成り立つので、『x^2y>xy^3』、つまり」

xy^3 < x^2y

「ってなりますか？」

「そうそう。なんだできてるじゃん。」

「はい。なんかできてました。」

答え：

第１問：xy > y^2

第２問：x^2y^2 > x^2y

第３問：xy^3 < x^2y

「やってみて分かったと思うけど、辞書式順序は左から順に指数を見ていって、大きさを比較していく順序だ。」

「考え方は自然というかシンプルでいいですよね。」

「そだねー。」

俺はカーリングの要領で水滴の付いたグラスを、右手から左手へと滑らせた。

りんは相変わらず黒糖ミルクラテを飲んでいる。

「それじゃあ、今から辞書式順序が単項式順序であることを示していこう。」

「あれ？辞書式順序＝単項式順序じゃないんですか？」

りんはカップに口を付けたまま首を傾げる。

口が淋しいのか彼女は何かよく食べている女の子だった。

「辞書式順序は単項式順序の一種であって、辞書式順序以外にも単項式順序はたくさんあるんだ。」

「あ、そうだったんですね。勘違いしてました。」

「辞書式順序が本当に単項式順序であることを今から確かめていこうと思う。」

「なるほど！」

俺はノートのページをめくり、単項式順序の部分を出した。

「おさらいすると、単項式順序の定義はこんな感じだったね。」

***

定義.（単項式順序）

> をn個の変数 x_1,...,x_n からなる単項式の間に定められた順序とする. ここで, 単項式 x_1^{a_1}…x_n^{a_n} を簡単に a=(a_1,...,a_n) として, x^a で表す. このとき, 次の３つの条件を満たすならば, >は単項式順序と呼ばれる.

1. >は全順序である.

2. 任意の単項式 x^a, x^b, x^c に対し、x^a>x^b ならば、x^a x^c > x^b x^c.

3. >は整列順序である.

***

「うへー。また難しいやつが……」

「大丈夫。さっき割り算で見たでしょ。」

「そんな昔のこともう忘れちゃいましたよ！」

昔のこと、か……

いやそんなに昔ではないが。

「と、とにかく、定義の条件をすべて満たすかどうか、１つずつ確認していこう。まず、１つ目。」

1. >は全順序である.

「えーと、全順序ってことはつまり、『並べられること』でしたっけ？」

「そうそう。」

「じゃあ、それを確認すればいいんですね？」

「簡単のために２変数の場合で考えよう。>を辞書式順序として、任意の２つの単項式 x^{a_1}y^{a_2} と x^{b_1}y^{b_2} が比較可能であることを証明しよう。すなわち、次の３つのうち、どれかが成り立つことを確認すれば良い。」

x^{a_1}y^{a_2} > x^{b_1}y^{b_2}

x^{a_1}y^{a_2} = x^{b_1}y^{b_2}

x^{a_1}y^{a_2} < x^{b_1}y^{b_2}

「うう…。大変そうですね…。」

「そんなことないさ。１個ずつ場合わけをすれば大丈夫。まず、どの場合分けが必要かな？」

「うーんと、『a_1>b_1』『a_1=b_1』『a_1<b_1』の３つですか？ 」

「その通りだね。ちなみになぜ？」

「えーと、辞書式順序はまず一番左の指数を比べますよね？だから、まず a_1 と b_1 どちらが大きいかで比べるのかなーって。」

「うんうん。いい筋だね。」

a_1>b_1の場合

a_1=b_1の場合

a_1<b_1の場合

「じゃあ、まず、a_1>b_1の場合にはどうなる？」

「えーと、辞書式順序の定義から、x^{a_1}y^{a_2} > x^{b_1}y^{b_2}になりますよね？」

a_1>b_1の場合 ⇨ x^{a_1}y^{a_2} > x^{b_1}y^{b_2}

a_1=b_1の場合

a_1<b_1の場合

「そうだね。」

「やった！」

「次にa_1=b_1の場合は？」

「a_1=b_1 の時は、えーと、a_2 と b_2の大きさを比べますよね？そして、a_2=b_2 だったら、x^{a_1}y^{a_2} > x^{b_1}y^{b_2}。逆に、a_2<b_2 だったら x^{a_1}y^{a_2} < x^{b_1}y^{b_2} ですか？」

a_1>b_1の場合 ⇨ x^{a_1}y^{a_2} > x^{b_1}y^{b_2}

a_1=b_1の場合

・a_2>b_2 ⇨ x^{a_1}y^{a_2} > x^{b_1}y^{b_2}

・a_2<b_2 ⇨ x^{a_1}y^{a_2} < x^{b_1}y^{b_2}

a_1<b_1の場合

「その通り！いい調子だね。ちなみに、a_2=b_2 だったら、『a_1=b_1かつa_2=b_2』だから、x^{a_1}y^{a_2} = x^{b_1}y^{b_2} となる。」

a_1>b_1の場合 ⇨ x^{a_1}y^{a_2} > x^{b_1}y^{b_2}

a_1=b_1の場合

・a_2>b_2 ⇨ x^{a_1}y^{a_2} > x^{b_1}y^{b_2}

・a_2<b_2 ⇨ x^{a_1}y^{a_2} < x^{b_1}y^{b_2}

・a_2=b_2 ⇨ x^{a_1}y^{a_2} = x^{b_1}y^{b_2}

a_1<b_1の場合

「確かにそうですね。」

「じゃあ、最後にa_1<b_1の時は？」

「えーと、その場合は、x^{a_1}y^{a_2} < x^{b_1}y^{b_2} になりますね。」

a_1>b_1の場合 ⇨ x^{a_1}y^{a_2} > x^{b_1}y^{b_2}

a_1=b_1の場合

・a_2>b_2 ⇨ x^{a_1}y^{a_2} > x^{b_1}y^{b_2}

・a_2<b_2 ⇨ x^{a_1}y^{a_2} < x^{b_1}y^{b_2}

・a_2=b_2 ⇨ x^{a_1}y^{a_2} = x^{b_1}y^{b_2}

a_1<b_1の場合 ⇨ x^{a_1}y^{a_2} < x^{b_1}y^{b_2}

「つまり、まとめるとどういうことになるかな？」

「んーと、x^{a_1}y^{a_2} > x^{b_1}y^{b_2}、x^{a_1}y^{a_2} = x^{b_1}y^{b_2}、x^{a_1}y^{a_2} < x^{b_1}y^{b_2} のうちの必ずどれかになるので、『大きさが比較できる』。すなわち、辞書式順序は『全順序』ってことですか？」

「大正解！！」

辞書式順序>が単項式順序であることを証明するための３つの条件

1. >は全順序である.←証明完了！

2. 任意の単項式 x^a, x^b, x^c に対し、x^a>x^b ならば、x^a x^c > x^b x^c.

3. >は整列順序である.

「とりあえず、これで１つ目の条件は証明できたね。」

「うへー。まだ１つ目なんですね。道のりは長い……」

りんはぐだーと脱力してテーブルに突っ伏す。

柔らかそうな白いほっぺが今にも落ちてしまいそうだ。

「一歩一歩、着実に進んで行けば大丈夫だよ。」

「頑張ります…」

「次は、２つ目。『掛けても大小は変わらない』ことを示そう。」

「また、２つの単項式 x^{a_1}y^{a_2} と x^{b_1}y^{b_2} を考える感じですか？」

「そう。そしてさらに、別の単項式 x^{c_1}y^{c_2} を考えよう。２つ目の条件を示すには、」

x^{a_1}y^{a_2} > x^{b_1}y^{b_2} ならば

x^{a_1}y^{a_2} x^{c_1}y^{c_2} > x^{b_1}y^{b_2} x^{c_1}y^{c_2}

「を証明できればいい。」

「あれ？でも単項式順序の定義の方だと、x^a, x^b, x^c になってますよね？」

「ああ。定義の方の対応だと、n=2 で、x_1=x、x_2=y、a=(a_1,a_2)、b=(b_1,b_2)、c=(c_1,c_2)という感じだね。」

「なるほど。」

「それじゃあ証明しよう。」

「えーと、あれ？何を示せばいいんですかね？」

「今導くべきことは、『ならば』の後にある結論『x^{a_1}y^{a_2} x^{c_1}y^{c_2} > x^{b_1}y^{b_2} x^{c_1}y^{c_2}』だね。その時に、仮定『x^{a_1}y^{a_2} > x^{b_1}y^{b_2} 』を使うんだ。ここで、x^{a_1}y^{a_2} x^{c_1}y^{c_2} を書き直すと」

x^{a_1}y^{a_2} x^{c_1}y^{c_2}=x^{a_1+c_1} y^{a_2+c_2}

「になる。」

「積と指数の関係からまあそうですね。」

「同様に、x^{b_1}y^{b_2} x^{c_1}y^{c_2} も書き直すと、」

x^{b_1}y^{b_2} x^{c_1}y^{c_2}=x^{b_1+c_1} y^{b_2+c_2}

「となる。つまり、示すべきことは」

x^{a_1}y^{a_2} > x^{b_1}y^{b_2} ならば

x^{a_1+c_1}y^{a_2+c_2} > x^{b_1+c_1}y^{b_2+c_2}

「ということだ。」

「なんだかさっきよりも分かりやすくなった気がします。」

「さらに結論部分を辞書式順序の定義に戻って書き直そう。定義から」

x^{a_1+c_1}y^{a_2+c_2} > x^{b_1+c_1}y^{b_2+c_2}

「はどういうことを意味するかな？」

「えーと、辞書式順序の定義が」

***

定義（２変数の辞書式順序）

a_1, a_2, b_1, b_2 を0以上の整数とする。

単項式 x^{a_1}y^{a_2} と x^{b_1}y^{b_2} を考える。

このとき、順序>を

x^{a_1}y^{a_2} > x^{b_1}y^{b_2} ⇔ 「a_1>b_1」 または 「a_1=b_1 かつa_2>b_2」

で定義する。この順序のことを(x>yの)辞書式順序と呼ぶ。

***

「だったので、」

x^{a_1+c_1}y^{a_2+c_2} > x^{b_1+c_1}y^{b_2+c_2}

⇔「a_1+c_1>b_1+c_1」または「a_1+c_1=b_1+c_1 かつ a_2+c_2>b_2+c_2」

「になりますか？」

「そうそう。」

「あれ？これって、c_1が消せますよね？ a_1+c_1>b_1+c_1は、両辺からc_1を決して、」

a_1>b_1

「になりますし、a_1+c_1=b_1+c_1 かつ a_2+c_2>b_2+c_2 は、c_1とc_2をそれぞれ引くと、」

a_1=b_1 かつ a_2>b_2

「ですよね？」

「そう！そうだね！いいよ！いいよ！」

「つまり、」

x^{a_1+c_1}y^{a_2+c_2} > x^{b_1+c_1}y^{b_2+c_2}

⇔「a_1+c_1>b_1+c_1」または「a_1+c_1=b_1+c_1 かつ a_2+c_2>b_2+c_2」

⇔「a_1>c_1」または「a_1=b_1 かつ a_2>b_2」

「という風に変形できる？」

「いいよ！もっと！もっと！」

「最後のって、結局、辞書式順序の定義から、x^{a_1}y^{a_2} > x^{b_1}y^{b_2} っていうことですね。」

x^{a_1+c_1}y^{a_2+c_2} > x^{b_1+c_1}y^{b_2+c_2}

⇔「a_1+c_1>b_1+c_1」または「a_1+c_1=b_1+c_1 かつ a_2+c_2>b_2+c_2」

⇔「a_1>c_1」または「a_1=b_1 かつ a_2>b_2」

⇔ x^{a_1}y^{a_2} > x^{b_1}y^{b_2}

「もう一声！」

「つまり、この変形を逆からたどれば、」

x^{a_1}y^{a_2} > x^{b_1}y^{b_2} ならば

x^{a_1+c_1}y^{a_2+c_2} > x^{b_1+c_1}y^{b_2+c_2}

「が成り立ちます！」

「お見事！」

俺は、拍手でりんを祝福する。

りんは鼻を高くして喜んでいる。

「なんだか調子が出てきたみたいだね。」

「はい。なんとなく辞書式順序が分かったような気がしてきました。」

「これで、２つ目の条件、『掛けても順序は変わらない』が証明できた。」

辞書式順序>が単項式順序であることを証明するための３つの条件

1. >は全順序である.←証明完了！

2. 任意の単項式 x^a, x^b, x^c に対し、x^a>x^b ならば、x^a x^c > x^b x^c.←証明完了！

3. >は整列順序である.

「いよいよラスボスですね。」

「ラスボス、三番目の条件は整列順序、すなわち『小さくしていくと、いつかは止まる』だ。ここで、e_1,e_2,e_3, ..., f_1,f_2,f_3,...を0以上の整数として、単項式の列」

x^{e_1}y^{f_1} > x^{e_2}y^{f_2} > x^{e_3}y^{f_3} > …

「を考えよう。これはどんどん小さくなる列だ。今から示すことは、この列がいつかは止まること、すなわち、ある自然数mがあって、」

x^{e_m}y^{f_m}=x^{e_(m+1)}y^{f_(m+1)}=x^{e_(m+2)}y^{f_(m+2)}=…

「というなることだ。」

「m番目以降は、小さくならずにイコールが続くってことですね。」

「That's right. その通り。じゃあ、証明していこう。」

「あれ？『That's right』と『その通り』って同じ意味ですよね？」

「ごほん。まず、辞書式順序でどんどん小さくなっているとき、xとyの指数の大きさはどうなっているだろうか？」

「えーと、減ってる……？」

「それはどうして？」

りんはペンを鼻の上に乗せて、しばし黙考する。

リップが塗られた唇が赤く輝いている。

「えーと、辞書式順序の定義から、『x^{e_1}y^{f_1} > x^{e_2}y^{f_2}』という式から言えることは、『e_1>e_2』または『e_1=e_2 かつ f_1>f_2』ですよね？」

「うん。」

「…つまり、x^{e_2}y^{f_2} では、xの指数 e_2 と yの指数 f_2 のどちらかは絶対にx^{e_1}y^{f_1} のものより小さくなっているんです。

「ほほう？」

「同じように、x^{e_2}y^{f_2} > x^{e_3}y^{f_3} から、x^{e_3}y^{f_3}では、xの指数 e_3 と yの指数 f_3 のどちらかは x^{e_2}y^{f_2} のより小さくなってて…」

「その通りだね。それはつまり、言い換えると…」

「ちょっと待ってください！」

その時、俺はりんに口を押さえられた。

冷たい手の感触が顔に伝わる。

「もう少しで分かりそうなので、ここはノーヒントでもいいですか？」

「え、あ、うん。」

俺はしどろもどろになりながら、りんに従う。

りんは、真剣にノートにペンを走らせている。

「…………どっちかは小さくなるってことは……………………」

その姿に俺は少し反省をしていた。

人に数学を教える時、ついつい全部を教えてしまう気分になる。

教えるという行為はある種、優越感というか全能感というか気持ちがいい。

でも、それは必ずしも教わる側のためになるとは限らない。

一番大事なのは、教わる側が自分で考えるということなのだから。

「あ！分かりました！」

りんが元気な声で俺の方を向く。

自信たっぷりな笑顔を浮かべている。

「おほん。じゃあ、りんさん。君の証明を発表してもらってもいいかな？」

「はい！まず、x^{e_1}y^{f_1} > x^{e_2}y^{f_2} なので、『e_1>e_2』または『e_1=e_2 かつ f_1>f_2』が成り立ちます。仮に、『e_1>e_2』としましょう。」

「ほほう？」

「すると、次に x^{e_2}y^{f_2} > x^{e_3}y^{f_3} なので、『e_2>e_3』または『e_2=e_3 かつ f_2>f_3』ですが、ここでも『e_2>e_3』とします。」

「ふむふむ。」

「するとどうでしょう？」

e_1>e_2>e_3>…

「という列が考えられます。しかし、e_1,e_2,e_3,...は0以上の整数なので、0より小さい整数になることはあり得ません。つまり、いつかはあるkで」

e_k=e_(k+1)=e_(k+2)=…

「という感じで小さくならなくなってしまうのです。」

「うん。」

「この時、x^{e_k}y^{f_k}>x^{e_(k+1)}y^{f_(k+1)} だとすると、『e_k>e_(k+1)』または『e_k=e_(k+1) かつ f_k>f_(k+1)』です。今、e_k=e_(k+1)なので、注目すべきは後半部分ですね。つまり、f_k>f_(k+1)なんです。」

「ほほう。」

「さっきと同じようにして、」

f_k>f_(k+1)>f_(k+2)>…

「という列ができます！しかし！f_1,f_2,f_3,...も0以上の整数なので、いつかはあるmで」

f_m=f_(m+1)=f_(m+2)=…

「で小さくならなくなってしまうのです。この時、m≧kから」

e_m=e_(m+1)=e_(m+2)=…

「でもあるので、すなわち、」

x^{e_m}y^{f_m}=x^{e_(m+1)}y^{f_(m+1)}=x^{e_(m+2)}y^{f_(m+2)}=…

「が成立します！これで、辞書式順序>が整列順序であることが証明できました！」

りんはキラキラした目で数式を眺めている。

俺はアイスコーヒーを飲み干した。

「Great だね。まあ、少し言葉足らずのところもあるけど、よく証明できている。りん、成長したね。」

「えへへ。」

頭を撫でようかとも思ったが、ふと気づき、それは諦めた。

俺は話を続ける。

「これで、辞書式順序の３つ目の条件も証明できた。」

辞書式順序>が単項式順序であることを証明するための３つの条件

1. >は全順序である.←証明完了！

2. 任意の単項式 x^a, x^b, x^c に対し、x^a>x^b ならば、x^a x^c > x^b x^c.←証明完了！

3. >は整列順序である.←証明完了！

「つまり、辞書式順序が単項式順序であることが証明できた。」

「やりましたね！」

「この辞書式順序というのは、グレブナー基底を使って連立方程式を解く時にやくに立つんだ。」

「へー。すごいですね。」

「それじゃあ、単項式順序の例もやったことだし、グレブナー基底の定義をしていこうか。」

「ようやくですね！」

りんは嬉しそうにこっちを向いている。

好きな女の子と数学をする。こんな幸せなことはない。

でも、幸せな時間というものは、砂時計のようなもので、どんどん減っていって、いつかは止まってしまう。

花柄のスカートに、ロングのブーツ、白のニットに、ハーフアップされた綺麗な髪。

今日、彼女が喫茶店に現れた時、その姿に俺は驚いていた。

それもそのはずだ。だって、

りんはもうこの世にいないのだから。