ブッフベルガーアルゴリズムの証明

グレブナー基底大好きbot @groebner_basis

【ブッフベルガーアルゴリズムの証明①】 今日は、水曜日に紹介した「ブッフベルガーアルゴリズムの証明」をするぶなよっ！ アルゴリズムについては、togetter.com/li/895861 を見てほしいぶなっ！

グレブナー基底大好きbot @groebner_basis

【ブッフベルガーアルゴリズムの証明②】 今回は、二つのことを証明するぶなっ！ ひとつは、アルゴリズムでちゃんとグレブナー基底が出来ていること「正当性」ぶなで、もうひとつは、アルゴリズムが無限ループせずに有限回で終わること「停止性」ぶなっ！それでは、アルゴリズムの復習からぶなっ！

グレブナー基底大好きbot @groebner_basis

【証明③】 【アルゴリズム】 入力：多項式の集合F={f_1,…,f_s} 出力：<F>のグレブナー基底 G:=F P:={ {f_i,f_ j} | f_i ≠ f_ j in G} while P≠Ø 　{f_i,f_ j} in P を一つ選ぶ

グレブナー基底大好きbot @groebner_basis

【証明④】 　P:=P - {f_i,f_ j} 　h:=S(f_i,f_ j) (mod G) 　if(h≠0) 　　P:=P⋃{ {u,h} | u in G} 　　G:=G⋃{h} 　end if end while return G だったぶなね！

グレブナー基底大好きbot @groebner_basis

【証明⑤】 それでは、まず「正当性」を証明するぶなっ！ （正当性の証明） 分かりやすいように、Gの初期値をG_0, Pの初期値をP_0とするぶな！また、n回目のwhileループの後のG,Pをそれぞれ、G_n,P_nで表すぶなっ！

グレブナー基底大好きbot @groebner_basis

【証明⑥】 また、 H_n:={ {f_i,f_ j} | f_i ≠ f_ j in G_n} とするぶな！つまりH_nは、G_nの多項式のすべてのペアの集合ぶなっ！ まず、すべてのnについて、 <F>=<G_n> が成り立っていることを示すぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑦】 帰納法で示すぶな。 n=0 の時、G_0=Fぶなから、もちろん成り立っているぶな。 そして、<G_n>=<F>が成り立っていると仮定するぶな。 n+1回目のループでは、G_nは変わらないか、h=S(f_i,f_ j) (mod G_n)が足されるぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑧】 よって、G_{n+1}=G_n または、G_{n+1}=G_n ⋃ {h} ぶな。ここで、f_i,f_ j in G_nから、hはG_nの元ぶな。したがって、いずれにしろ<G_{n+1}>=<G_n>=<F>が成り立っているぶな。つまり、常にG_nは<F>の基底ぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑨】 次に、すべてのnについて、 H_n - P_n に含まれる多項式の組{f_i,f_ j}に対し、 S(f_i,f_ j)=0 (mod G_n) が成り立つことを示すぶな。 これも帰納法で示すぶな。 n=0の時、H_0=P_0で、 H_0 - P_0 =∅ ぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑩】 よって、n=0のとき成立しているぶな。 次に、nで成立しているとするぶな。 n+1回目のループで、P_n から{f_i,f_ j}を取り除いたとするぶな。 このループの後半は、h=S(f_i,f_ j) (mod G_n)の値によって２つのケースがあるぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑪】 [h=0 mod(G_n)のとき] これはifの条件を満たさないので、G_{n+1}=G_nとなるぶな。 よって、 H_{n+1} - P_{n+1} =H_n - (P_n - {f_i,f_ j}) =(H_n - P_n)⋃{f_i,f_ j} となるぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑫】 帰納法の仮定から、H_n - P_n の多項式の組のS多項式は0 (mod G_{n+1})で、S(f_i,f_ j)=0 (mod G_{n+1}) から、この場合、n+1の時も成立してるぶな。 次に、h≠0(mod (G_n))のケースを考えるぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑬】 [h≠0 (mod G_n)の時] ifの条件を満たすので、 P_{n+1}=P_n ⋃ { {u,h} | u ∈ G_n} G_{n+1}=G_n ⋃ {h} H_{n+1}={ {f_i, f_ j} | f_i≠f_ j ∈ G_{n+1}} となるぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑭】 よって、 H_{n+1} - P_{n+1} =(H_n - P_n) ⋃ {f_i, f_ j} が成り立つぶな。 なぜなら、P_nからまず{f_i, f_j}を引いていることと、H_{n+1}とP_{n+1}に新しく加わった組は同じものから言えるぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑮】 ここで帰納法の仮定から、H_n - P_n の多項式の組にS多項式は0 (mod G_{n+1})で、{f_i, f_ j}のS多項式S(f_i,f_ j)は0 (mod G_{n+1}) になってるぶな。（そのS多項式のG_nでの余りがG_{n+1}の元だからぶな）

グレブナー基底大好きbot @groebner_basis

【証明⑯】 よって、このケースでもn+1で成立するぶな。 したがって、すべてのnについて H_n - P_n の元のS多項式は0 (mod G_n)であることが言えたぶな。 これで正当性の証明の準備ができたぶな。 仮に、このアルゴリズムで、G_nが出力されたとするぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑰】 最初示したことから、G_nは<F>の基底ぶな。 また、アルゴリズムが終了したということは、whileループから脱出したということなので、P_n=∅がいえるぶな。 よって、H_n-P_n=H_nのS多項式はすべて0 (mod G_n)ぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑱】 ここで、H_nはG_ｎの多項式のすべての組を表していて、グレブナー基底の判定法 togetter.com/li/893456 の条件を満たすぶなから、G_nは<F>のグレブナー基底であることが示せたぶな。（正当性の証明終わり）

グレブナー基底大好きbot @groebner_basis

【証明⑲】 これで、「アルゴリズムが止まれば、グレブナー基底が出る」ことが分かったぶなけど、本当に有限回のループで終了してくれるかどうかはまだ分かってないぶな。 よって、次にこれを示すぶな。

グレブナー基底大好きbot @groebner_basis

【証明⑳】 （停止性の証明） 明らかにG_n⊂G_{n+1}ぶななので、 先頭項による単項式イデアルの上昇列 <LT(G_0)> ⊂ <LT(G_1)> ⊂ <LT(G_2)> ⊂… が作れるぶな。 ここで、これらすべての和集合 G=⋃<LT(G_n)> を考えるぶな。

グレブナー基底大好きbot @groebner_basis

【証明㉑】 実は、このGも単項式イデアルになっているぶな（読者への演習問題にするぶな）。 ここで、ディクソンの補題 togetter.com/li/889789 から、 G=<g_1,…g_t> と書けるぶな。 各g_iについて g_i∈G=⋃<LT(G_n)> が成り立つぶな

グレブナー基底大好きbot @groebner_basis

【証明㉒】 よって、あるn_iが存在して、 g_i ∈ <LT(G_{n_i})> となるぶな。 このようなn_iの中で最大のものをNとすると、 上昇列の包含関係から、 g_1,…g_t ∈ <LT(G_N)> が成り立つぶな。

グレブナー基底大好きbot @groebner_basis

【証明㉓】 したがって、 G=<g_1,…,g_t> ⊂ <LT(G_N)> ⊂ G ぶなから、 G=<LT(G_N)> で、つまり、 <LT(G_N)>=<LT(G_{N+1})>=<LT(G_{N+2})>=… が成り立っているぶな。

グレブナー基底大好きbot @groebner_basis

【証明㉔】 これは、N+1回目以降のループでは、P_{N+1}は増えないことを意味しているぶな。 実際、P_{N+1}に元が追加されるのは、h≠0 (mod G_N)の時で、この時、<LT(G_{N+1})>も同時に増えるので、これはあり得ないぶな。

グレブナー基底大好きbot @groebner_basis

【証明㉕】 各whileループの最初にP_nから元を一つ抜いているので、N+1以降は、P_nの元の個数は１個ずつ減っていくぶな。したがって、いつかは０個、つまりP_n=∅になり、whileループから抜けるぶな。 よって、このアルゴリズムは必ずいつかは止まることが証明できたぶな。