多項式の連立方程式を扱う魔術 −グレブナ一基底−丸山正樹
以下は，市民講演会で使ったOHP原稿にほんの少しだけ手を加えたものである．有†口な一般化が可能な個所が多々あるが，グレブナ一基底を「連立方程式を耶く」という札・さ真のみから椚説する利こ特化し．雰四気だけでも理研してもらうことを目指したものの故であると理研をして頂きたい．
まず次の方程式を考えてみよう．
lッ〜

lニ

ッん 2＋ニ＋

〃＋l

二ヱ

＋

〃＋ ＋∫∫〃2∫︷

最初の式から2番目の式を引いて国数分J押すると（∬一山（J‥＋〃−1）＝O

Jニ＝〃の叩は，エ2＋∬＋ヱ＝1と2∬＋ヱ2＝1を連立させて
ヱ4−4ヱ2＋4ェー1＝0
これを附いて．

ヱ＝1またはヱ＝−1士ヽ万∬＋〃＋1＝0の場合は，ヱ＝0となる．それぞれの場合に解を見つけるのは容易であろう．この邪法は方程式の形の昭殊性を仕っているので．一般化することは靴しい．例えば，方程式をlッ︶ニ

十〃＋γル＋∬＋〃十∬＋2′−−ノ＼−−し〃十ヱ2＝3としてみると，最初の式から2番口の式を引いても22∬−ズー〃＋〃＋1＝0となり，これは関数分椚できない．

「元の方程式からこのみについての方程式を導く一般的方法はあるか」という問いに対する椚答がYcsであるということを説明するのが，此の講演の口的である．後で説明する方法により，最初の方程式のヱについての解は
zG−4ェ1＋4ェ3−エ2＝ご2（ェー1）2（ヱ2十2ェーー1）＝0

多項式の連立方程式を扱う魔術【グレブナ一基底−（丸山正樹）の解であり，後に挙げた方程式の場合は

ヱ8−12ヱ6十4ヱ5＋45z4−16ェ3−68ヱ2十16z＋37＝0のノ解であることが分かる．
1．多項式の連立方程式

以1く」〝は有理数全体Q，実数全作軋 又は複素数全体Cのいずれかとする．文字（変数）ズ1，…，ズmを用意して〝［ズ1，…，ズれ］で〝に係

1l，．

Jl（ズ】，…，考l）＝0
ム（ズ1，．．，ノ㌦）＝0（1）ム（ズ1，・・，考l）＝0を考えよう．〟の元のれ′個の組（叫，‥．パ㌦）の全休を〝↑lとおく：〟m＝（（α1，…，αれ）l叫∈〝）（1）を附くとほ，仰の猥合V（ム，…，ム、）＝（（α1，・，αTl）∈〟mけ1（α慮，・，化m）＝…＝ム（α1，…，αm）＝0）を決めることである．
次の集合を考えよう．

〈J7，…，ふ〉＝†Jlタ】十…＋ふ動ー恥…，クγ∈呵ズ1，…，ズm］）〈．fl，…，ム〉の「仰の集合」をV（（ノtl，，ノ；・〉）＝（（ 1，，rlTl）∈打l」／申．1，．，∩，↑，．）＝0，∀ん∈（ん…，ム〉）と定義する．（ん…，ム）は〈ん…訪〉の部分鳩舎だからV（〈んノ1／申1，・，化，，）＝Jl（αh・，化 ）飢（勘，・，化71）＋‥＋ふ（化ト．＝∵イ㌦）ク丁車17．，∩↑l）＝0仇（α＝・↑（l ）＋…十0βr（α1，．，化丁と）＝0となるから，（（11，．・，化，−）∈V（け1，．．，．ん〉）となり．結局

V（（Jト，．ん〉）＝V（．fl，…，ふ）…，ム・〉）⊂

市民講演会講演となる．

定義 連立方程式
九1（ズ1，…， ズm）＝0ん2（ズト…，芳一）＝0／J′β（ズ1，…，考l）＝0が（1）と同価であるとは，くん…，．ん〉＝く／？′1，，板〉であるときに言う．

上で示したように．連立方程式が同佃であれば，解の集合は一致する．
〈ん．，．ん〉が持つ性質を調べよう．

輔題 てJ．，一りは（．f］，…，ふ〉の任意の元で，クは〟［ズ1，…，方円］任意の元であるとする．この時，次のことが成り立つ．
（1）′u＋′りも（ん…，ム〉の元である．

（2）卯も（ん・‥，ふ〉の元である・
此の補題は次の定義の動機づけである．

定義 〝［ズ1，…，ズ71］の部分集合Jがイデアルであるとは．祁題の〈ん…，ム〉をJに置き撒えて（1），（2）が成立するときに言う．

上の補超から〈fl，・．，j；〉はイデアルであるが．次のHilbertの基底完埋によりイデアルはこのようなものしかない市が分かる．
定理Jをイデアルとすると．多項式ん．．，ム、が存在して，J＝げ】，…，ム〉となる．

定義 イデアルナについて，J＝〈Jト，ふ〉となる多項式ん．，ノ1をJの生成元と言う．

従って，多項式の連立方程式を考えることは，イデアルを考えることと同じことになり，連iリラ￣柱式を昭くことは「イデアルの生成元で附きやすいものを見つける」
ことに帰着する．連立力持式をイデアルと考えたとき，基本郁な問題として次のものがある：（1）．′を多項式，Jをイデアルとするとき，JがJの元であるかどうかを判定できるか，（2）ナノをイデアルとするとき，J＝ノであるかどうかを判定できるか，（3）イデアルの附きやすい生成元を見つけることができるか．
（3）は花々の‥■り責の侶票であり，ある多項式が考▲えている連立方程式系に含まれるかどうかが（1）である．連立力作ぺの同仰什を、川完するのが（2）である．

驚くべきことに，上記の問題全てについて，答えはYcsである．

多項式の連立方程式を扱う魔術グレブナ一基底（丸山正樹）

2．一変数の場合

柁＝1の場合に上の問題（1），（2），（3）を考えてみよう．一般の場合にどうすべきかについて，良い示唆を与えてくれる．以下この節ではズ1をズで表す．J∈呵∬］は

J＝α丁‖．ズTn＋αm＿トYTn「1＋・‥＋叫ズ＋化0α1∈〟，αTn≠0と書けるが，この時川・をJの次数と言い，（1cgJで表す．
Jを〟［ガ］の†0）でないイデアルとして，rJ＝111ill（degJIJ∈J＼（0））と置く．rJの定義とJがイデアルであることにより．Jの元タで（1egタ＝dであり．最高次の係数が1であるものが存在する：〟ニガイ＋わd−1Xrト1＋…＋わ0・Jの任意の元／を〃で割ることにより，
J＝ク／けγdegr＜rgまたはr＝0と書ける．γ＝J＋（一夕）九であり．．fと一夕が期こJの元であるから，イデアルの性質によりrもJの元であることが分かる．r≠0ならば，（legタ＜（gで（gの剛、乍＝こ反する．従って，r＝0であり，Jの全ての元がタで割り切れることが分かった．逆に．ガで割り切れる元が仝てJの元であることは明らかだから，J＝〈〝〉となる．−一方，吊㍍次の係数が1の多項式ガトク2について（ク1〉＝〈〃2〉ならば，ガ1＝叩2であり〟2＝わ．ヮ1であるから，2番目の式を1布［1の式に代人して，両辺をタ1で創ることにより1＝扉を得る．附こ．
化は〃の元となる．〃1と叩2の靖㍍次の係数を比忙して．化＝1が分かり，仇＝〟2となる．これにより】1二記のJに対する〝はJによって一意的に定まることになる．

定理Jを¶・変欽の多墳式環呵∬］のイデアルとすると．尼高次の係数が1である多項式〝が行在して，J＝〈〃〉となる．このタはJによって一意的にうこまる．
′＝（ん ，．ん〉のl甘．定川のヴは．行‥∵．差・の最大公約園丁であることは行捌こ分かる．在】がノ 1と．んの尼大公釣同丁であれば，Jト，．差・の最大公約因子と／？′1訪い‥Jの最大公約因子は一致する．従って，E11Cli（lの耳．
除法をr−−1l・叶繰り返すことにより，．ヴは仙丹に求まる．
前節の最後に挙げた【汀】越はト上記の揖■Hで附けたことになる．（1）はJをりで割って．割り切れるかどうかで判定できる．イデアルナ，ノに定理を適珊して，J＝〈ク1〉，J＝〈ク2〉とすると，J＝ノであるための必要十分条什は，仇＝仇となることである．（3）についてはク＝0の仰がJの解になる．

市民講演会講演

3．辞書式川軒iミと割り算
一変数の場合の眼り抜いで鎚になったアイデアは，多項式（正純には，単項式の）次数による大小関係と多項式の割り算であった．これらを多変数の場合にそのまま一般化することは出来ないが，才先々の目的に合う程度の一般化はある．

Z賢。で負でない整数m個の組の集合とする・すなわち，
Z芸0＝（（α1，…，αm）Jα1，・・， αmは負でない整数）
Z笠0の元α＝（α1，…，αγl）に対して蝉・項式ズα＝ズFl…方言−−を対応させることにより，Z；0と単項式全体の集合との問に1対1対応がつく（α＝（0，…，0）の転∴㍗＝1とする）・Z笠。の2元α＝（α1，…，αれ．），β＝（βト＝り且，．）に対してα＞β⇔王（1≦王≦れ一）が存在して，こニー■‥
βl，…，αト1＝β豆＿1かつα豆＞且と定義する．これでZ；。に順序が入るが．これを辞書式順序と言う・辞書式順
序は次の性質をj・わて1−る：（1）Z笠0の任意の2元α，βに対して，α＞β，α＝β，α＜βの何れかが成り立つ，（2）Z貰。の任意の部分集合に，この順序での剛、の元が存在する，（3）αうβならば，任意のZ笠。の元7について・α＋7＞β＋7となる．ここで，α＝（α1，…，α，l），7＝（71，…，7m）とするとき，α＋7＝（α1＋7】，…，α ＋7γl）と定義する．
この3′l堂質を打つ川即事は辞書式順序だけでなく，他にも沢山ある．実際，後述のグレブナ一基底の計糾こは「斉次逆辞書式」と呼ばれる順序を使う場合が多い．しかし，連立方程式を解くという場合には．辞書式順序の斉次逆辞書式順
序にはない牲牡l、〔しを仕うので，以下では，順序は辞書式であると仮定する．

Z笠0と里項式のγミ合との1対1対応を仕って，Z笠0の順序を単項式の購合 の順序と考える．この時，例えば（3）からズαがJ軒を割り切っていれば，α≦βであることが分かる．〟［ズ】，．，ズ，l］の元Jを／＝∑n。ズα〔1と諾いた帖，化α≠0であるαの凡桔1拭肝押で吊人のものを，Jの111tllti（1egI・CCと呼び．111ulti（1cg（f）で表す．Xn11．M（1eg（J）を1cadillglnOllOlnialと言い，LM（f）と書き，nJ7川仙1cg（／）を1ca〔lil−gCOCfficicntと言い，LC（f）で表す・

罷後に，LC（f）LM（f）を1ca〔1illgtCrlllと言い，LT（f）で表す．例えば．

／＝5刃耳拷3＋2ポ旦狂3−4ズ1一堵墨多項式の連立方程式を扱う魔肝グレブナ一基底−（丸山正樹）

ならば．

111tllti（lcg（J）＝（475，1）

LM（／）＝可東端
LC（／）＝5LT（／）＝5刃旦狂3である．

次に．多項式一′を多項式の集まり（ん．．，ム）で割ることを考える．一変数の場合，／をクで割ったとき．その余りの次数は（1cgタよりも′トさい．これを「LM（ク）が余りに現れるどの単項式も割り切らない」と理研して，一般の場合の割り符を次のように定義する．

定義 多項式Jを多項式の集まり†ん・，．た）で割るとは「多項式化ト，化β，rでJ＝α1Jl＋…＋αβム＋γとなり，LM（Jl），…，LM（ム）のどれもがγに現れるどの単項式も割り切らないものを見つける」ことであるとする．
上記の割り算はいつでも可▲能であるが，叫，．，αβ，rは一意的に定まるとは閉らないことが，一変数とは本質lⅢこ違うところである．割り算が可能である
ことは．次の例で感じ11篭って貰いたい．
α1：∬＋〃
α2：1′り lり∵ −∬2〃＋∬〃2十〃2∵・′・／／・・′・￡〃2十∬十〃2
ご・り／・り∬＋〃2＋〃→ ∬〃2＋〃

りこ、・−−〃＋11→ ∬十〝0 → エ十〃十1市民講演会講演

上の計算の結果∬2〃＋∬〃2＋〃2＝（∬＋山（ァ〃−1）十1・（〃2−1）＋∬＋〃＋1となり．余りのγ＋〃＋1に硯れるどの単項式もLM（∬ダー1）＝ご〃でもLM（〃2−1）＝〝2でも割り切れない．また，∬〃−1と〃2−1の順序を変えて上と同じ計㌍をすると．
∬2y＋叩2＋y2＝（∬＋1）（〝2−1）＋∬（∬封−1）＋2∬＋1となり，余りの一意性さえも成り立たないことが分かる．
4．グレブナ一基底第1節に挙げた問題を脈く方法として．イデアルの良い生成元を見つけることを考えてみよう．一変数の場合は非常によい生成元が存在した．素朴に考えて，例えば尼も数の少ない生成元はどうだろうか．イデアルを扱った経験のある人ならば，それが凡そ使いものにならないものであることを却っている．
B．BtlClll）CI・gCI・は彼の学位論文で全く違った生成元を導入した（1965年）．
1970年代になってその有効性と重野「′仁が認識されるに及んで．Buchbergcrはこの生成元のことを，彼の指導教授の′捌こ因んでGl、（沌11er基底と名付けた．

第1節に挙げたHilbcI・tの基底定理を見直してみよう．（ムl入∈A）を，必ずしも有l猥とは限らない多項式の架合とする．

∑軌

仏t人∈A〉＝

仇は多項式，人五〈 有限和と置く，（ムl入∈A〉がイデアルであることは容易に分かる．従って．
Hilbcrtの≧掛民定】判こより，有限偶の多項式hl，，hsが存在して〈ムl入∈A〉＝（わ′］，…，板〉となる．各九jは仏l入∈A〉の元であるから，
rよ／？′慮＝∑恥左。，Å慮j∈Aj＝1と酋ける・イ1■辺に現れるムりを仕うと

仏lÅ∈A〉＝〈／？′】，，んβ〉⊂（ん．，ll≦J≦β，1≦j≦n〉⊂（ムtス∈A〉と成るが．これは仏lÅ∈A〉の有限個の生成元として（ムlス∈A）の中から取ることが■¶来ることを意味している．

→≠川てL／l

し− −−

カ一け

〃

さて．叫」Yl，・，ズ↑l］のイデアルナ≠（0）を取って，上の注意をイデアル〈LM（ハ〉＝（L九ノⅠ（／）け∈J〉に適【1してみよう．有限佃のJの元Jト（ハ〉二（LMげ1），…，LM（ム）〉となる．

多項式の連立方程式を扱う魔朴グレブナ一基底一（丸山正樹）

定義 〟［∬1，…，ズTl］のイデアルナ≠（0）について，〈LM（用二〈LM（Jl），・，L仙伏）〉と成るJの元の集合（ん…，ム）をJのグレブナ一基底と呼ぶ．

（ん．，．f5）をJのグレブナ一基底として，Jの任意の元Jを此のム，．．，Jβで割ってみると
J＝α1Jl＋・‥十αβム＋γとなり．LM（Jl），．，LM（ム）のどれもがγ に硯れるどの単項式も割り切らない．r＝ノー（αL′1＋‥・＋αβム）はJの元であるから，LM（r）＝blLM（fl）＋‥・＋bsLM（ム）と書ける．もしr≠0ならば，b】，．．，bsのどれかは0でなく，LM（fl），．．，LM（fs）のどれかがLM（r）を割り切ることになり，rの性質に反する．放に，γ＝0となり，Jがくん…，ム〉に含まれることになる．

定理 イデアル∫のグレブナ一基底は．Jの生成元である．
グレブナ一基底は割り算に対して非′削こ良く振る舞う．

定理（プレ，，ん）をJのグレブナ一基底とする．町方1，…，弟l］任意の元ダに対して次の性質を持つJ，γが一志こ的に存在する：（1）タ＝．′＋γ，（2）ノ ∈J，（3）LMげ1），・・，LM（ム）のどれもがrに現れるどの単項式も割り切らない．

上の完理の〝を†ん…，Jβ）で割ってタ＝叫Jl＋…＋αβム＋rと書くと，J＝化げ1＋‥・十αβ，たとγが7日則こあるノ性質（1），（2），（3）を持つ．
従って，余りrが−一・悪的に決まることになる．

系（ん…，ム）をJのグレブナ」基底とする．多項式タがJの元である
ための必要￣l一分粂什は，†ん．，．た）でタを割ったときの余りが0に成ることである．

グレブナ一基底に一意性が撫いのは定義から明らかであろう．実際，（ん…，ム）がJのグレブナ一基底ならば，Jの任意の元Jについて，（ん．．，ム，J）もグレブナ一基底である．一意性をのためにグレブナ一基底に条件を付けよう．

定義 イデアルJ≠（0）のグレブナ一基底†ん…，ム）をJが被約であるとは（1）全てのノについて，LC（ノ1）＝1．
（2）全てのノについて，LM（ノち）はム（．ゾ≠ノ）に視れるどの単項式も割り切らない，

市民講演会講演時に言う．

次の定理は，それほど難しくなく証明できるが，驚くべき結果である．
定理 イデアルナ≠（0）に対して被約グレブナ一基底は必ず存在して，一意的である．

与えられたものから目的のものを導く手続きのことをa1goritlllllという．
BucllbergcI・のグレブナ一基底についての最大の貢献はBuchberger，sAlgorithm
イデアルが有限偶の生成元で与えられたとき，グレブナ一基底を決完する，有lリき回で終わり，かつ有効な（締単な場合にほ手計算でも可能であり．コンピュータを使えば，少し複紺でもそれほど時間のかからない）
a1g即itlllllが存在する．また，グレブナー韮威から披約グレブナ一基底を決定することも容易であるの発見であろう．

第1節の環後に挙げた問題（1），（2）はイデアルが有限個の生成元で与えられれば脈ける．実際，まず，Buchbcrgcr sAlgoritllmで協約グレブナ一基底を決定する．（1）については与えられた多項式を，このグレブナ一基底で割ってみて．割り切れるかどうかを見ればよい（上の系を参照）．（2）については，JとJの被約グレブナ一基底を比概して，それらが一致するかどうかによって判定できることになる（．上の最後の定理を参照）．

5．グレブナ一基底と多項式の逆立方程式
多項式環㌧打［ズ1，…，考，．］のイデアルナ＝〈恥…，タr〉を連立方程式と見なして，それを椚くことを考える．もう少し正純に言うと，一変数の方程式を附くことに帰着させる．
定義 ヨ望芳文Ⅲ・（1≦〃？′≦れ′−1）に対して，

んl＝〟［ズm＋ト・，ズn］nJと置き，？了トtllClilllillatiolli〔1calと呼ぶ．
次の結果がガ粁式を扱う基本定理である．

定理 C＝（ん・・，ム）をJのグレブナ一基底とする．
C汀1＝〟［ガm＋1，・，ズれ］∩（プ
はm−tllelilllillationi〔1calノー。のグレブナ一基底である．

Cが被約であれば，C 1もそうである．従って，第2節の結果を使えば．
Cが被釣であれば，Cれ＿1は空集合であるか，唯一つの元から成る．
上の定理をガ粁式を附くという視点から眺めてみよう．GmはJの部分集合であるから，V（J）⊂V（CTn）である・従って．（呵，．．，αn）がJの耶ならば，（化m十＝‥・，町，．）はん．の耶である．このことを理昭した上で考えれば．方程式を附く手拭きは以下の通りである．

多項式の連立方程式を扱う魔朴グレブナけ基底一（丸山正樹）（i）Jの披約グレブナ一基底Cを決定する．
（ii）Cn→1が空集合でなければ．その折の一つ∩ノア1を取る．Cγl−1が空集合ならば「†一丁，．は何でも良い．

（iii）〝
mる．

注意（1）CTト2＼Cれ＿1＝†プレ・諭）とする．烏（1≦才≦f）を方円＿1の多項式として整班してム＝4れ（考と）耳禁1＋4れ＿1し㌦）碓γ−＋‥・＋4。（芳一）と書こう，Cれ．−1の脈化mを取ると，4岬（化n）＝A2m．2（化γl）＝‥・＝4勒（αm）＝0であるか，．ハ（ガm＿1，∩・71），…諭（考ト1，α，l）が正の次数の共通因子を持つ．

l，…，ムは考巨］について正の次数の（2）C↑，．＿1が空集合ならば，（1）のJ共通因子を持つ．
例 最初に挙げた方程式のイデアル（∬2十y十エー1，∬十〃2十エー1，∬十y＋ヱ2−1〉の被約グレブナ一基底は（エ十〟十ヱ2−1，〃ヱ2十ヮ4＿ヤ22〃2−y−ヱ2十ヱ，ヱ6−4ェ4十4ヱ3−ヱ2）であり，2番口の連立ガ和式のイデアル
2〈㌔＋〃＋エー1，ズ＋〃＋エー2，ご＋〃＋ヱ2−3〉の被約グレブナ一基底は,li4（∬十一5ヱ＋2ヱ3・13ヱ2−4エー，、り．り〃−＋5ご1−2ェ3−12ヱ2＋4ヱ＋，、】「㌔−12ヱG＋4㌔十45ヱ」−16ヱ3−68ヱ2十16ヱ十37）である．
最後に，グレブナ一基底の計算に仕える，パソコン上のソフトの例を挙げておく．

（1）市販のソフトでは．MatllenlaticaとMaplcがある．これらのソフト
上での，多項式についての画数，命令の多くが．グレブナ一基底の計算を基礎にしている．

市民講演会講演（2）富士通のグループが開発したAsirは上記の市販ソフトに比べると格段に速いパッケージである．MathcmaticaやMapleで何十分もかかる計算が，数秒ですむこともある．公開されているソフトであって，elldeavor．fujitsu．co．jp（164．71．131）
から，ftpで人手できる．UNIX版，DOS版，Willdows版，MacilltOSll版があるが，最後のMacilltOSh版は68Ⅰく用で，PPC用は解いようである．
（3）ドイツのⅠくaiserslatltCrn大学の計算機代数のグループが開発しているSillgulal・というソフトがある．これは特異点の計算に特化したパッケージであるが．グレブナ一基底の強力な計算力を持っている．上記のAsirとは違った計算機で試行したので，単純比較ほJIl来ないが，数倍速い場合もあるようである．これも公開されていて，http：／／www．mathelllatik・ulli−kl．derzca／Sillgular／からダウンロード出来る．UNIX版，DOS版，Macintosh版があるが，Ma・CilltOSll版にはMPWが必要である．最近，VerSioll−uPされた．
（4）上記のほかPARI，MuPad，Macaulayなど多くのソフトがあるが，く使った経験が無いか，最新版は知らないものなので，無責任なことは言わないことにする．上記（2），（3）のソフトのマニュアルなどで，人手方法を見つけることは，それほど即しく細い．
（まるやま まさき，京都大学大学院理学研究科）