数学ガール グレブナー基底

第6章 グレブナー基底

今は放課後。ここは図書室。5人で集まって数学の話をしている。

「強正優美問題を、違う解き方で解こうと思う」ミルカさんが話を切り出す。

「全部調べなくてもいいのかにゃ」とユーリ。

「この問題を、''連立方程式''にする」ミルカが答える。

「連立方程式って、2x+y=3,x-y=4みたいなのですよね？」テトラが尋ねる。

「そう。ただし、この場合はもっと複雑だけど。日本語の文章を方程式にするには、まず何をする？」ミルカは僕を指差す。

「求めたいものを、文字で置きます」僕が答える。

「この問題で求めたいものは何？」テトラを指す。

「この条件を同時に満たすことができるかどうか、ですよね」

「これらの条件を同時に満たすものを何と言う？」ユーリを指す。

「えっと・・・解？」

「そう。この問題は、これらの条件の''解''を求めることになる。この場合、解は〈強くて、正しくなくて、優しくて、美しい〉のような形になる。この場合、条件4を満たさないからこれは会ではないが」

「強い、正しい、優しい、美しいの4変数の連立方程式ってことですね！」テトラが答える。

「その通り。ここでは、〈強い〉をs,〈正しい〉をt,〈優しい〉をk,〈美しい〉をbで表すことにして、肯定を0、否定を1とする。すなわち、〈強くて、正しくなくて、優しくて、美しい〉は(s,t,k,b)=(0,1,0,0)と表される」

「肯定が0で否定が1？普通は逆じゃないですか」と僕が質問する。

「これは、便宜上そうしただけであって、本来はどっちでもいい。ただ、こうした方が後が楽になる」ミルカが答える。

「変数を作っても、〈か〉が表せないにゃ」とユーリ。

「掛け算」とミルカ。

「「掛け算？」」僕とテトラが同時に聞きかえす。

「''真偽値表''を書くとわかりやすい。例えば、〈強いか正しい〉で考える」

ミルカさんはそういうと、白板に表を書き始めた。

強い　正しい　s　t　強いか正しい　s*t

真　　 真　　0　0　　　真　　　　0

真　　 偽　　0　1　　　真　　　　0

偽　　 真　　1　0　　　真　　　　0

偽　　 偽　　1　1　　　偽　　　　1

「真が0、偽が1のとき、〈か〉は掛け算で表される」

テトラちゃんは表の一行一行を確認している。

「確かに、掛け算になっています」とテトラ。

「次に、〈ではない〉を作る」

「〈ではない〉は、0のとき1、1のとき0になるような計算を作ればいいですね」と僕が答える。

「そう。これは、元の変数をxとして1-xで表される」とミルカが答える。

「1-0=1,1-1=0だから確かに否定されてるにゃ」とユーリ。

「これで、準備はそろった。これらの条件を文字で表していこう。まず、最初の条件の〈強いか、正しいか、美しい〉は、s*t*b=0で表される」

「右辺の=0はどういう意味ですか？」僕が尋ねる。

「〈強いか、正しいか、美しい〉が真、すなわちこの条件が成り立つことを示している」

「なるほど」

「次の条件は、〈優しいか、正しいか、美しくない〉だ。〈美しくない〉は1-bだから、この条件はk*t*(1-b)=0と書き換えられる」

「残りは、私にやらせてください！」とテトラちゃんが大きな目を輝かせて言う。

「わかった」ミルカさんは持っていたマジックをテトラちゃんに渡す。

しばらくして、式が出来上がった。

s*t*b=0

k*t*(1-b)=0

(1-s)*k*b=0

(1-s)*(1-k)*t=0

(1-k)*(1-t)*b=0

(1-s)*(1-t)*(1-b)=0

s*(1-k)*(1-b)=0

s*k*(1-t)=0

「式は出来たけど、この方程式、どうやって解くのかにゃ」とユーリ。

「''グレブナー基底''」とミルカ。

「「グレブナー基底？」」僕とテトラは聞き返す。

「グレブナー基底を使うと、連立方程式が簡単に解ける。リサ」ミルカはリサを指差す。

「計算済み」

リサは僕たちに画面を見せる。そこには、こう書かれていた。

nd_gr([s*t*b,k*t*(1-b),(1-s)*k*b,(1-s)*(1-k)*t,(1-k)*(1-t)*b,(1-s)*(1-t)*(1-b),s*(1-k)*(1-b),s*k*(1-t)],[s,t,b,k],0,0);

[1]

「これは何？」僕が尋ねる。

「nd_grは入力、1は出力」リサがハスキーボイスで答える。

「グレブナー基底として[1]が出てきた。これは、連立方程式に解がないという意味」ミルカが補足する。

「つまり、強正優美問題に解はないということですね！」とテトラちゃん。

「そういうこと」ミルカが返す。

「解けない場合は[1]だけど、解ける場合はどうなるんですか？」と僕が尋ねる。

「もっと簡単な連立方程式が返ってくる。リサ、具体例」

「計算済み」リサが画面を見せる。

nd_gr([2*x+y-3,x-y-4],[x,y],0,0);

[-3*x+7,-3*y+5]

「これは、2x+y-3=0,x-y-4=0という連立方程式が、-3x+7=0,-3y+5=0という同値な連立方程式に置き換えられたことを示している」とミルカが付け加える。

「だったら、グレブナー基底を使えばどんな連立方程式でも簡単に解けるということですね！」とテトラ。

「そうとは限らない。場合によっては、グレブナー基底は非常に長くなる」

ミルカはそう言うと、白板に連立方程式を書き始めた。

「リサ、これのグレブナー基底」

「計算中」

リサが高速タイプで連立方程式を入力する。

nd_gr([2*x^3+y^3+z-1,x^2*y+y^2-y*z+6,z^3+x*y+x^3-2],[x,y,z],0,2);

１分ほどして、結果が表示された。

[-8*z^27+12*z^25+156*z^24-6*z^23-72*z^22-1305*z^21-189*z^20+51*z^19+3670*z^18+2355*z^17+3035*z^16-7422*z^15-9945*z^14+21585*z^13+18348*z^12-1329*z^11-198274*z^10-288571*z^9+76272*z^8+672150*z^7+1613039*z^6-39696*z^5+363024*z^4-2979584*z^3+673200*z^2-3307392*z-8532864,-43260932113387534317552541215970299824711524493341693291007181312*y-103117870101800641685737881651011224703174696402986917557912*z^26+24175362175115505857358624358506974090802833308028436256888*z^25+167919825821473411700345036896924948678125834086973693701036*z^24+1956404289235749990787169595703071897862916079016988383751384*z^23-529610440679130008628519171273092680925095666393297837709306*z^22-909427746057147303585642867041841383859034567033508623502774*z^21-16226060471228240638569411798299391956415995641928259676989397*z^20+663517898857770269573197814919978042050115269568131745992186*z^19-826688934567925480762534139146285840546272940410098084794445*z^18+46166055544338218088806347176997952815481898539167729978145195*z^17+25402680692888156214638791946634341603207118058056252590084382*z^16+52948809323339394952211891901650613933368461472685309199234311*z^15-126082540327853647996379178315825099176001851456852002089973333*z^14-126627154283970695676215556518319698636702571836696453668650294*z^13+298182451572802837617762425592703249226185005338354627976435949*z^12+324930847189084966434332467672465332183773409961594545436110939*z^11-6136510979887340654440916343580072971314867261757420722467030*z^10-2573622749509648109753191315623495102102462112783632600383991292*z^9-2331901900607127841959130322959652499355273522631397674417140045*z^8+989709873917354475913629327467593112961251931140946725661852417*z^7+7940996552900399271972888278741382760183018162951362296862329401*z^6+15376205771029283009231704819632118252399760485888926732414866756*z^5-847069076330657642340645167228501856497270230509025809009317984*z^4+7359159438419743589606089346220410053258620879052070494638152320*z^3-32502667215230128024611979497701125138386629734572992175089793840*z^2+7489956711989506044695205227593354788350773119169320324608315520*z-45850212482791070527409787296572409166412318669138597046257243776,16222849542520325369082202955988862434266821685003134984127692992*x-18053557098809746639410723335614727346495279245380261505952*z^26+1266457299226227879546496676887876011009029741369931979984*z^25-11866275676880564033996708407770762178777322177609635905240*z^24+334657061740235583484820687469018694158887585647638796424432*z^23+2303475360451552351055084374991959771979428621007764189908*z^22+571579874260287757289707047952572722011784185197089802214012*z^21-2978885884683466711328503086166658406204417070240157354626170*z^20-347187084254918698169660751632432894220010438907420762163304*z^19-5108155718646451798350114389498246093402972405738304990995313*z^18+10534903305624499494208528896463967171673544744539566276000350*z^17+4491198537308928573427626703512275082340024935495071388611023*z^16+16514754739484139018063856431378477826284763995559483362450851*z^15-38643475314173484014240420673563064162329705871093954489685442*z^14-23620967381554386705930091147988848037238453170725166874980957*z^13+37129796426328167680256558131259778062502728464498982215656587*z^12+1553398972928683276799496438000311544976618905589860924688502*z^11+175314951913228035791795173754397612547752335952342874585621489*z^10-311787005181382046395143733576732462815592702212889107596602805*z^9-495279909388983658960769627341226166153988885659973884728845172*z^8-744855691263799256621896547841845601563460508987262965506829580*z^7+781906420947345342393627102209564811234545182569901450629566939*z^6+3142175302390237421670660749378100045498944442690746293545749831*z^5+1448429606174217407822209545067135385081161902305369342074323171*z^4+3048533664200590126050379198994823366590740298339274842489877676*z^3-13641979392307142581337497169155635165501250042408428954838636068*z^2+7750426838128343113601954577734742202265179525606875446905454112*z-7279138457071940119148384277703432083632978468920625358317254752]

「ふぁっ！？」と僕。

「きゃあああああああああああ！！！」テトラが叫ぶ。

「ぶにゃああああああああああ！！！」ユーリも叫ぶ。

ミルカとリサは無言。

周りの人たちが一斉に僕たちの方を見る。僕たちがグレブナー基底を見て叫んでいるなんて誰も思っていないだろう。

僕たちの興奮が収まってから、ミルカが口を開いた。

「入力は３変数の３次式だが、グレブナー基底にはzの27次式が出てきた」

「つまり、何でも解けるってわけじゃないんですね」とテトラ。

「場合によっては、これより長くなることもある。インターネット上には２万字のグレブナー基底が載っているサイトがあるらしい」

「２万字・・・」僕とユーリは驚いて後に続く言葉が出てこなかった。

「下校時間です」

長いグレブナー基底に驚いた僕たちを、水谷女史が現実世界へと引き戻した。