グレブナ基底候補がグレブナ基底となる条件

ここでは, change of ordering の場合には, trace lifting の場合に必要だったグレブナ 基底テストとメンバシップテストが不必要になることを示す. F ⊂Z[X]とする.

仮定 11.12 有理数体上と有限体上の計算が異らないよう次の仮定をおく.

1. 不必要対の検出基準は頭項のみで行う.

2. 正規形計算において, 正規化に用いる元 (reducer) の選択は, 正規化される多項 式の項および reducerの頭項の集合にのみ依存する.

定義 11.13 (compatibileな素数)素数 pが F に関し compatible とは, φ_p(Id(F)∩Z[X])(=φ_p(Id(F)∩Z_(p)[X])) =Id(φ_p(F))

なること.

定義 11.14 素数 p が (F, <) に関して strongly compatible とはp が F に関して compatibleで

E_<(Id(F)) =E_<(Id(φ_p(F)) なること.

定義 11.15 (permissibleな素数)素数pが(F, <)についてpermissibleとは各f ∈F に対しp6 |hc_<(f)なること.

定義 11.16 f ∈Q[X] が pに関し stable とはf ∈Z_(p)[X]なること.

定義 11.17 (modular グレブナ基底の逆像) G⊂ Id(F)∩Z[X] が F の < に関する p-compatible なグレブナ基底候補とはp が (G, <) について permissibleで φ_p(G)が Id(φ_p(F))の < に関するグレブナ基底なるときをいう.

注意 11.18 compatibility は order に独立な概念である.

補題 11.19 G ⊂ Z[X], p を (G, <) について permissible な素数, f ∈ Z[X] とする.

このとき仮定11.12 のもとで

NF(φp(f), φp(G)) =φp(NF(f, G)).

[証明]NF(f, G)は次の recurrence で計算される.

f₀ ←f, f_i ←f_i−1−α_it_ig_ki

ここで, α_i ∈Q, t_i : a term, g_ki ∈G. すると, p が (G, <) に対して permissible より αi ∈Z(p). よって 全てのi に対し fi ∈Z(p)[X] で, この recurrence にφp を適用して 次を得る.

φ_p(f_i) = φ_p(f_i−1)−φ_p(α_i)t_iφ_p(g_ki).

もしφp(αi)6= 0 ならばφp(fi−1)6= 0 で,

φ_p(f_i)←φ_p(f_i−1)−φ_p(α_i)t_iφ_p(g_ki)

は φp(G) による頭項消去である. もしφp(αi) = 0 ならば φp(fi) =φp(fi−1) で {φ_p(f_i)|i= 0 orφ_p(α_i)6= 0}

11.2. MODULAR CHANGE OF ORDERING 127 なる列はNF(φ_p(f), φ_p(G)) の計算に対応する. もしφ_p(f_i) = 0 なる i が存在すれば 像は途中で切れるが

NF(φ_p(f), φ_p(G)) =φ_p(NF(f, G)) = 0 だから主張が成立する. 2

定理 11.20 G ⊂ Id(F)∩Z[X] を Id(F) の < に関するグレブナ基底とする. もし p が (G, <) に関して permissible かつφp(G) ⊂ Id(φp(F)) ならば p は F に関して compatible である. 更に, φp(G) は Id(φp(F)) のグレブナ基底でp は (F, <) につい て strongly compatibleである.

[証明]h ∈Id(F)∩Z[X]とする. GがId(F)のグレブナ基底だから,NF(h, G) = 0よ りh=^P_g∈Ga_gg と書ける. ここでa_g ∈Q[X]. 更にpが (G, <)についてpermissible より, a_g は p について stable で, 仮定φ_p(g)∈Id(φ_d(F))より

φ_p(h) = ^X

g∈G

φ_p(a_g)φ_p(g).

よってφp(h)∈Id(φp(F)). 故にφp(Id(F)∩Z[X])⊂Id(φp(F)).

逆にh∈Id(φ_p(F)) は

h= ^X

f∈F

a_fφ_p(f)

と書ける. ここでa_f ∈GF(p)[X]. すると,φ_p(a_f) = a_f なるa_f を選んでh=^P_f∈F a_ff とおけばφp(h) =h. これから φp(Id(F)∩Z[X]) = Id(φp(F)).

最後に φ(G) が Id(φ_p(F)) のグレブナ基底となることを示す. 上で述べたことから, h∈ Id(φ_p(F)) に対し, h∈ Id(F)∩Z[X] が存在して h =φ_p(h). すると, 補題 11.19 より

NF(h, φ_p(G)) = φ_p(NF(h, G)) = 0.

従って, φ_p(G) は Id(φ_p(F)) のグレブナ基底. strong compatibility は E_<(Id(F)) が E_<(G) で生成されることから分かる. 2

この定理で, φp(G)⊂Id(φp(F)) はId(φp(F)) のグレブナ基底によりチェックできる.

よって, p の compatibility のチェックは有理数体上, 有限体上の任意の order でのグ レブナ基底を計算することで行うことができる. もし, 入力が既にある order でのグ レブナ基底ならcompatibility のチェックは極めて簡単である.

系 11.21 G ⊂Z[X] が < に関する Id(G) のグレブナ基底とする. もし p が (G, <) に対しpermissible ならばφ_p(G) は Id(φ_p(G))のグレブナ基底でp は (G, <) に対し strongly compatible.

次の定理は, グレブナ基底候補が実際にグレブナ基底になるための十分条件を与える.

すなわち,我々が求めるものである.

定理 11.22 pが F について compatibleで Gが <に関して p-compatibleなグレブ ナ基底候補ならば,G は < に関する Id(F) のグレブナ基底である.

[証明]全ての f ∈Id(F) が < に関して G により 0 に正規化されることを示せばよ い. f は G について被約としてよい. もし f 6= 0 ならば, 適当な有理数をかけて, f ∈Id(F)\{0}がG について被約で f の係数の整数 GCD (cont(f) と書く) が 1に 等しい, としてよい. するとφ_p(f)6= 0. さもなくばcont(f) は因子pを持つことにな る. p は F につき compatibleだから φ_p(f)∈Id(φ_p(F)). するとφ_p(f) は <に関し, φ_p(G)により 0に正規化されなければならない. しかし f は G について被約だから φ_p(G) の頭項の集合は G のそれと等しい. よってφ_p(f) は φ_p(G) について被約とな り, φ_p(f) = 0. これは矛盾. 2

次の定理は前定理の精密化である. すなわち,昇順に計算された部分的なp-compatible なグレブナ基底候補が実際にグレブナ基底の一部となっていることを保証する. これ は, 途中までの結果を再利用できるという点で有用である. また, 後で述べるよう に, グレブナ基底のある特定の元, 例えば, 順序最小の元のみを求めたい, あるいは

elimination後の結果のみを求めたい場合にも有用である.

定理 11.23 pがF についてcompatibleとする. G⊂GF(p)[X], G=GB_<(Id(φ_p(F)) としg₁ <· · ·< g_s なる g_i によりG={g₁,· · ·, g_s} と書く. 更に,ある正数 t≤sに対 し, g_i ∈Id(F)∩Z_(p)[X] (1≤ i≤t) が存在してφ_p(g_i) =g_i かつ g_i は {g₁,· · ·, g_i−1} について被約とする. このとき, g₁,· · ·, g_t は GB_<(Id(F)) の最初の t 個の元に一致 する.

証明略(帰納法による.)

以上述べたことにより, 次のような一般的な change of orderingアルゴリズムが得ら れる.

Procedure 11.24 candidate(F, p, <)

11.2. MODULAR CHANGE OF ORDERING 129 Input : F ⊂Z[X]

素数p order<

Output : F の p-compatible なグレブナ基底候補またば nil (各 F に対し, nil を返す pの個数は有限個でなければならない.)

アルゴリズム 11.25 (compatibility checkによるテストの省略) gr¨obner by change-of-ordering(F, <)

Input : F ⊂Z[X], order <

Output : Id(F)の < に関するグレブナ基底G

G0 ←F の, あるorder <0 に関するグレブナ基底; G0 ⊂Z[X]

again:

p←(G₀, <₀)に関して permissible な未使用の素数 G← candidate(G₀,p,<)

IfG =nil goto again:

else returnG

candidate() においては, p-compatible なグレブナ基底候補を返す任意のアルゴリズ

ムが使用可能である. これまで述べたものでは,

• tl guess()

• 斉次化 + tl guess() + 非斉次化

• candidate by linear algebra()

が適合する. これらのうち, 前者 2 つについては明らかだが, 最後のものについては 検証を要する. これについて次節で述べる.