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

Case. 2

「……これって、四色じゃなくて、一般の n色でも考えられるのか？」

俺は、Case. 2 を選んだ。

すぐ n に一般化したがるのが、数学徒の性（さが）だ。

「無論。n 色の塗り分け判定も、グレブナー基底でできる。」

「おおー。」

「では。式を構成してみよう。」

そう言って南條は、ペンとレポート用紙を取り出した。

レポート用紙の中央を、ペンで縦に割るように線を引く。

「まず。四色問題の時の多項式には、x^4-1 があった。」

x^4-1=0

「これは。x は 1,-1,i,-i のどれかの値を取る、ということだった。もちろん、複素数体上で。」

「だから、それぞれの値に、４つの色を対応できたんだもんな。」

「適当。それでは、n 色の場合には、どのような多項式を与えれば、n 個の色を対応させられるだろう、か？」

「えーと…… x^n-1 か？」

「疑問。なぜ？」

「う……と、x^n-1 はn個の根を持っているからだろう。」

「不正確。正しくは、n 個の異なる根を持っている、から。」

「ん？何が違うんだ？」

思わず出た質問に、俺は、ちょっぴり後悔した。

南條がため息をついてこちらを見ていたからだ。

「愚問。x^4-1 の時に、４つの色とうまく対応づけられたのは、x^4-1 が４つの異なる解を持っていたから。もし、x^4-1 が重根を持っているとすると、x^4-1=0となるx というのは、４個より少なくなってしまい、４色に足りなくなってしまう。同様に、n色でも、n個の異なる解を持たなければいけない。」

「た、確かに……」

いくら、打ち解けたからといって、南條の鋭さは昔のままだ。

不用意に野暮なことを言うと、すぐ突っ込まれる。

「出題。それでは、x^n-1 が複素数で、ちょうど、n 個の根をもつことを証明して、くれなんし。」

「え、お、えーと……」

まずい。いや、出題されたこともまずいが、それよりも、語尾に「くれなんし」が付いた。くれなんしはやばい。

南條に変な攻撃スイッチが入ってなければいいのだが。

「えーと、なんて言うか、こう x^n-1 の根って、1のn乗根だから、ζ=e^{2πi/n} がその一つで、1,ζ,ζ^2,ζ^3,…,ζ^{n-1} は、どれも x^n-1=0 を満たす。そして、ζはn乗して初めて1になるから、これらは、すべて異なる根、つまり、x^n-1はn個の異なる根を持つ……これで……どうだ？」

「正解。」

「ほっ。」

「それでは。今から別の方法で証明しよう。」

「えっ。」

思わず、手元のコーヒーをこぼしそうになる。

南條は、その理由を次のように説明した。

「ある種。今の方法は、複素数の性質を利用した、解析的な証明、だ。そうではなく、代数的に、有限体でも使えるように証明したい、ずら。」

「どういうことだ？」

「微分。x^n-1 を微分してみよう。」

「ちょ、ちょっと、待ってくれ。今、代数的に証明したいっていったのに、微分って、思いっきり解析じゃないか。」

「愚問。微分といっても、代数的な微分、なのら。」

言葉の意味が分からず、頭の中で 微分!!! on ICE という、微分が滑りまくる映像が流れる。

呆れた南條がまたもや大きなため息をついて、話を始める。

「絶句。代数の授業でもやっただろう。いわゆる形式的な微分ってやつ、だ。」

「形式的な……あ！」

「そう。多項式の各項の指数部分を１減らし、また元の指数を係数にかける操作。それが、形式的な微分、ですぜ。」

「えーと、例えば、x^3 は微分すると、3x^2 ってことだよな。」

「適切。解析的には、微分は、極限を使って定義されるが、この形式的な微分は、多項式に対して定義されている。しかし、有理数係数多項式に関しては、普通の微分とまったく同じ、だ。」

ああ、確かに体論の授業でやった気がするな。

「では。有理数係数で、x^n-1を微分すると？」

「それは……x^nは、nx^{n-1}で、-1は消えるから、nx^{n-1} だな。」

「正解。ここで、nは１以上とすれば、x^n-1とnx^{n-1} の最大公約数は、１なので、よって、x^n-1は重根を持たない。証明終。」

「あれ！？終わった！？」

「Yes。何か疑問でも？」

「あ、え、えと、なんで、x^n-1とnx^{n-1}の最大公約数が１だと、重根を持たないんだっけ？」

「呆気。一般に、多項式 f(x) を f(x)=f_1^{e_1} f_2^{e_2}...f_d^{e_d} と因数分解してみる。ここで、f_1,...,f_d は互いに異なる既約多項式で、e_1,...,e_d はその指数、だ。」

「多項式の、既約分解ってことだな。」

「ここで。f(x)をxで微分してみ、ヨーソロー。」

ヨーソロー！

残念ながらサンシャインでは、俺はヨハネ推しのリトルデーモンなので、ヨーソローとは気軽に返すことはできない。

ヨーソローより、よーしこーだからだ。

まあ、それはともかく、f(x) を微分してみた。

f'(x)=e_1 f_1^{e_1-1} f_2^{e_2} ...f_d^{e_d} + e_2 f_1^{e_1} f_2^{e_2-1} ...f_d^{e_d} + ... + e_d f_1^{e_1} f_2^{e_2} ...f_d^{e_d-1}

「えーと、積の微分法則から、積のうち (f_i^e_i) を微分したやつの和となる。つまり、f_i^{e_i}の指数を１減らして、e_i を 係数としてかけたやつ、e_i f_1^{e_1}...f_i^{e_i-1}...f_d^{e_d} の和が、f の微分だ。」

「適正。それでは、f の微分をキレイにまとめる、と？」

「うーんと、f_1^{e_1-1}...f_d^{e_d-1}で括れるから、」

f’(x)=e_1 f_1^{e_1-1} f_2^{e_2} ...f_d^{e_d} + e_2 f_1^{e_1} f_2^{e_2-1} ...f_d^{e_d} + ... + e_d f_1^{e_1} f_2^{e_2} ...f_d^{e_d-1}

　　=f_1^{e_1-1}...f_d^{e_d-1} (e_1 f_2...f_d + e_2 f_1 f_3 ... f_d + ... + e_d f_1 f_2 ... f_{d-1})

「てな感じで、分解できる。」

「では。f と f’ の最大公約数 gcd は、なんぴょろ？」

「さっき、 f’を括った結果から、f_1^{e_1-1}...f_d^{e_d-1} だな。」

「つまり。f と f’ の最大公約数は、既約因子の指数が１ずつ減ったものが出てくる。これは、すなわち、f が無平方、すなわち、e_1=...=e_d=1 の時、f と f’の最大公約数は、f_1^{e_1-1}...f_d^{e_d-1}=f_1^0...f_d^0=1 となる。」

「そうか、逆に、gcd が１となっている時は、f が無平方、つまり、f は異なる解を持っているのか。」

「まとめ。話をまとめると、微分と最大公約数を調べれば、異なる根を持つかを判定できる。これは、有理数だけではなく、有限体にも活用できるメソッドだ、キュピコン。」

キュピコンの意味は分からないが、とりあえず、有限体には関係ないことは分かる。

あと、南條には似合わない語尾であることも分かる。

「結論。有理数係数で、x^n-1 と nx^{n-1} の gcd は 1 だった。故に、n色の塗り分け判定は、x^n-1 という多項式を使うことで、４色と同じように判定できる。問題は、有限体でも同じように、x^n-1 が使えるかどうか、だ。」

「ん？それだと、使えない場合があるのか？」

「例示。２元体 F_2 で４色問題を考えてみる、ジョン。さて、x^4-1 は異なる４つの根を持つか？」

「……あ！持たないのか！」

「要求。その、理由は？」

「標数が２の場合、偶数は０となってしまい、(x^4-1)=(x-1)^4 となってしまうからだ。これだと、x^4-1 は 1 しか根を持たない。」

「正解。すなわち、有限体では、必ずしも、x^n-1 はn個の異なる根を持つとは限らない。では逆に、どのような場合に、x^n-1 は異なる根を持つだろうか。」

「……もしかして、標数 p が n を割らない場合か？」

「鋭し。さっきの微分と gcd を使って、実際に示してみる、ンだ。」

よし、やってみようと、俺はペンを取った。

まず、一般に、さっきのように、多項式を

f(x)=f_1^{e_1} f_2^{e_2}...f_d^{e_d}

と書く。これを微分すると、

f’(x)=e_1 f_1^{e_1-1} f_2^{e_2} ...f_d^{e_d} + e_2 f_1^{e_1} f_2^{e_2-1} ...f_d^{e_d} + ... + e_d f_1^{e_1} f_2^{e_2} ...f_d^{e_d-1}

となる。問題は、有理数の場合と違って、有限体 F_p で考えているという点だ。

有限体 F_p では、p の倍数は、すべて０になってしまう。

もし、指数 e_1,...,e_n のうちに p の倍数が存在すれば、例えば、e_i が p の倍数なら、e_i=0 で、

e_i f_1^{e_1}... f_2^{e_i} ...f_d^{e_d} = 0

となってしまう。

そうすると、計算する時に都合が悪い。

そうだ、そういう e_i はあらかじめ、一箇所に集めておこう。

e_i=0 mod p となるような、f_i^e_i たちを集めて、

h と置くことにする。

番号を振り直せば、f は、

f=h*f_1^{e_1}... f_2^{e_i} ...f_d^{e_k}

とかける。

この状態で、f を微分すれば、h の微分が０になるところを除けば、有理数の場合と同じだから、

f’(x)=h*(e_1 f_1^{e_1-1} f_2^{e_2} ...f_d^{e_d} + e_2 f_1^{e_1} f_2^{e_2-1} ...f_d^{e_d} + ... + e_k f_1^{e_1} f_2^{e_2} ...f_d^{e_k-1})

となる。したがって、f=h*f_1^{e_1}... f_2^{e_i} ...f_d^{e_k} だったから、f と fの微分の最大公約数は、

gcd(f,f’)=h*f_1^{e_1-1}...f_k^{e_k-1}

だ。もし、f が無平方（e_i がすべて1)の時、e_i-1=0 となるから、

gcd(f,f’)=h*f_1^{e_1-1}...f_k^{e_k-1}=h

となる。くそ h が邪魔だ。

h め。微分で０になりやがって。許さんぞ。

……いや待てよ。

h は微分して０になるんだから、指数は p の倍数じゃないか？

例えば、x^p の微分は、p x^{p-1} = 0 となる。

そうか、よって、f がもともと、無平方だったら、h はそもそも１だ。

つまり、

gcd(f,f’)=h*f_1^{e_1-1}...f_k^{e_k-1}=h=1

だ！逆に、gcd(f,f’)=1 の時、f は無平方になるから、これで、有理数と同じように、次の命題が示せた。

deg(f)=n の時、

f が相異なる根を持つ（重根を持たない）　⇔ gcd(f,f’)=1

「以上のことから、素数 p を n を割り切らないものとすると、x^n-1 の微分は、nx^{n-1}≠0 だから、最大公約数は、１。したがって、今示した命題から、x^n-1はF_p でも異なる根を持つ。つまり、n 色の塗り分け可能かは、n を割らない有限体F_p でも、グレブナー基底で判定できるってことだ！！！」

俺は、南條の反応を伺う。

この問題に正解できたら、１０００万円だ。

南條は、手の平に角砂糖の塔を作って静止している。

ファイナルアンサー。

俺は、心の中でそう答えて、南條が動き出すのをじっと待つ。

「回答。多少荒いところもあるが、方向性としてはいいだ、ろう。ただ、異なるn個の解を持つというのは、有理数では複素数上で、有限体ではその代数的閉体で持つ、ということだ。有理数体、有限体のような基礎体は完全体だから、無平方という性質は、代数的閉体に拡張しても成立する。」

完全体と聞いて、フ○ーザ様しか浮かばなかったが、とりあえず及第点をもらえたようだ。

それに、変な語尾が付かなくなったことから、どうやら少しは満足してもらえたらしい。

さぁ！それでは、導来対策に移りますよ！南條さん！ドドリアさん！

「ふご。」

「………………え？」

俺はとても嫌な予感がしたが、おそるおそる目の前の南條を確認する。

寝てる。

それも、鼻息を立てて、ぐっすりと。

どうやら、俺が、F_p の時の gcd(f,f’) の時、待ちくたびれて、すでに睡魔が来ていたらしい。

こうなるなら、何か計算させとけばよかった。

「んーむにゅむにゅ……射有限群……完全不連結コンパクトハウスドルフ位相群……むにゃむにゃ……」

一体、どんな夢を見てるんだ。

というか何で、夢の中で数学してるんだ。

ラマヌジャンかよ。

ああ、こんなことになるなら、あの時、Case. 1を選択しておけばよかった。

おそらく、具体的なグレブナー基底の計算になったはずだから、南條が眠ることもなかったはずだ。

お冷の氷がすっかり溶けて、カランと音がなる。

こうして、終わらない寝息とともに、長い夜は更けていくのであった。