Gröbner基底

$q_1=\cdots=q_s=0$、$r=0$、$p=f$ から始め、$p\neq0$ の間、次の操作を繰り返す。

• $\operatorname{LT}(p)$ を割り切る $\operatorname{LT}(g_i)$ があれば、そのような最小の $i$ をとり、$m:=\operatorname{LT}(p)/\operatorname{LT}(g_i)$ として $q_i\leftarrow q_i+m$、$p\leftarrow p-mg_i$ とする。
• そのような $i$ がなければ $r\leftarrow r+\operatorname{LT}(p)$、$p\leftarrow p-\operatorname{LT}(p)$ とする。
  どちらの操作でも等式 $f=\sum_iq_ig_i+r+p$ は保たれる。前者では $mg_i$ の先頭項が $\operatorname{LT}(p)$ に等しい（単項式順序 の記事の補題「単項式順序の基本性質」の 3）ので、後者では先頭項を取り除くので、新しい $p$ は $0$ であるか先頭単項式が真に小さい。よって 単項式順序 の記事の命題「先頭単項式が下がる手続きの停止」により、有限回で $p=0$ となって止まり、$f=\sum_iq_ig_i+r$ を得る。
  $r$ に加えるのは $\operatorname{LT}(g_i)$ のどれでも割り切れない項だけなので 1 が成り立つ。$p$ の先頭単項式ははじめ $\operatorname{LM}(f)$ で、その後は真に下がり続けるので、$q_i$ に加える各 $m$ について $\operatorname{multideg}(mg_i)=\operatorname{multideg}(p)\le\operatorname{multideg}(f)$ であり、$r$ に加える項も $\operatorname{LM}(f)$ 以下である。$q_ig_i$ はこれらの $mg_i$ の和なので 2 が成り立つ。$\square$

1．$f\in I$ を $G$ で割り（thm-gb-division）、$f=\sum_iq_ig_i+r$ とする。$r=f-\sum_iq_ig_i\in I$ である。$r\neq0$ なら $\operatorname{LT}(r)\in\operatorname{LT}(I)=(\operatorname{LT}(g)\mid g\in G)$ であり、単項式順序 の記事の命題「単項式イデアル」の 1 により $\operatorname{LM}(r)$ はある $\operatorname{LT}(g_i)$ で割り切れる。これは余りの条件 1 に反する。よって $r=0$、$f\in(G)$ である。
2．$\operatorname{LT}(I)$ は単項式 $\operatorname{LM}(f)$（$f\in I$、$f\neq0$）で生成されるので、単項式順序 の記事の命題「単項式イデアル」の 2 により、有限個の $f_1,\dots,f_t\in I$ で $\operatorname{LT}(I)=(\operatorname{LM}(f_1),\dots,\operatorname{LM}(f_t))$ となる。$\{f_1,\dots,f_t\}$ が Gröbner 基底であり、1 により $I$ を生成する。$\square$

1．存在は thm-gb-division による。$G$ による余り $r$ のどの単項式も $\operatorname{LT}(g_i)$ のどれでも割り切れず、$\operatorname{LT}(I)$ は単項式イデアルなので、単項式順序 の記事の命題「単項式イデアル」の 1 により $\operatorname{LT}(I)$ に属さない。一意性：$f=h+r=h'+r'$ とすると $r-r'=h'-h\in I$ である。$r-r'\neq0$ なら $\operatorname{LM}(r-r')\in\operatorname{LT}(I)$ だが、$r-r'$ の単項式は $r$ か $r'$ の単項式なので $\operatorname{LT}(I)$ に属さない。よって $r=r'$ である。
2．$f\in I$ なら $f=f+0$ が 1 の表示なので、余りは $0$ である。逆は余りの定義から明らか。
3．1 により、$f$ の剰余類は標準単項式の $k$ 係数の和 $r$ の剰余類に等しいので、標準単項式の剰余類は $R/I$ を張る。標準単項式の $0$ でない $k$ 係数の和 $r$ が $I$ に属したとすると、$r=0+r=r+0$ が 1 の 2 通りの表示になり矛盾する。よって一次独立である。$\square$

$p'_i:=p_i/\operatorname{LC}(p_i)$、$a_i:=c_i\operatorname{LC}(p_i)$ とおくと $p=\sum_ia_ip'_i$ である。$x^\delta$ の係数を比べると $\sum_ia_i=0$ である。したがって
$$ p=a_1(p'_1-p'_2)+(a_1+a_2)(p'_2-p'_3)+\cdots+(a_1+\cdots+a_{m-1})(p'_{m-1}-p'_m)+(a_1+\cdots+a_m)p'_m $$
の最後の項は $0$ であり、主張が従う。$\square$

$G$ が Gröbner 基底なら、$S(g_i,g_j)\in I$ なので thm-gb-normal-form の 2 により余りは $0$ である。
逆を示す。$0$ でない $f\in I$ をとり、$\operatorname{LT}(f)\in(\operatorname{LT}(g_1),\dots,\operatorname{LT}(g_s))$ を示せばよい。$f=\sum_ih_ig_i$ という表示は多数あり、各表示について $\delta:=\max\{\operatorname{multideg}(h_ig_i)\mid h_ig_i\neq0\}$ を考える。単項式順序は整列順序なので、$\delta$ が最小になる表示を選べる。$\operatorname{multideg}(f)\le\delta$ である。
$\operatorname{multideg}(f)< \delta$ と仮定して矛盾を導く。$T:=\{i\mid\operatorname{multideg}(h_ig_i)=\delta\}$ とし、$\operatorname{LT}(h_i)=c_ix^{\alpha(i)}$ と書くと
$$ f=\sum_{i\in T}c_ix^{\alpha(i)}g_i+\Bigl(\sum_{i\in T}(h_i-\operatorname{LT}(h_i))g_i+\sum_{i\notin T}h_ig_i\Bigr) $$
である。括弧の中の各項の多重次数は $\delta$ より小さく、$f$ もそうなので、$p:=\sum_{i\in T}c_ix^{\alpha(i)}g_i$ も $0$ であるか多重次数 $< \delta$ をもつ。$p_i:=x^{\alpha(i)}g_i$（$i\in T$）はすべて多重次数 $\delta$ をもつので、lem-gb-cancel により $p$ は $p_j/\operatorname{LC}(p_j)-p_l/\operatorname{LC}(p_l)$（$j,l\in T$）の一次結合である。$x^{\gamma}$ を $\operatorname{LM}(g_j)$ と $\operatorname{LM}(g_l)$ の最小公倍元とすると、$x^\delta$ はこの両方で割り切れるので $x^\gamma$ で割り切れ、
$$ \frac{p_j}{\operatorname{LC}(p_j)}-\frac{p_l}{\operatorname{LC}(p_l)}=\frac{x^\delta}{\operatorname{LT}(g_j)}g_j-\frac{x^\delta}{\operatorname{LT}(g_l)}g_l=x^{\delta-\gamma}S(g_j,g_l) $$
である。仮定より $S(g_j,g_l)$ の余りは $0$ なので、thm-gb-division の 2 から $S(g_j,g_l)=\sum_ia_ig_i$、$\operatorname{multideg}(a_ig_i)\le\operatorname{multideg}(S(g_j,g_l))< \gamma$ と書ける（S 多項式が $0$ なら全部 $a_i=0$ とする）。$x^{\delta-\gamma}$ を掛けると、各項の多重次数は $< \delta$ になる。
以上をまとめると $p$ は多重次数 $< \delta$ の項 $b_ig_i$ の和であり、$f=\sum_i(b_i+h'_i)g_i$（$h'_i$ は括弧の中の係数）は各項の多重次数が $< \delta$ の表示になる。これは $\delta$ の最小性に反する。よって $\operatorname{multideg}(f)=\delta$ であり、$x^\delta$ の係数を比べると
$$ \operatorname{LT}(f)=\sum_{i\in T}\operatorname{LT}(h_i)\operatorname{LT}(g_i)\in(\operatorname{LT}(g_1),\dots,\operatorname{LT}(g_s)) $$
である。$\square$

要点：加える $r$ の先頭項は $G$ のどの先頭項でも割り切れないので、単項式イデアル $(\operatorname{LT}(g)\mid g\in G)$ は操作のたびに真に大きくなる。単項式イデアルの真の増大列は無限に続かないので止まり、止まった $G$ は Buchberger の判定法を満たす。

要点：$\operatorname{LT}(I)$ の極小な単項式 $m$ ごとに、$m$ からその余りを引いた $m-\bar m$ を集めると被約 Gröbner 基底になる。2 つの被約 Gröbner 基底の同じ先頭単項式をもつ元の差は、$\operatorname{LT}(I)$ に属さない単項式だけからなる $I$ の元なので $0$ である。

$G_i\subset I_i$ である。$0$ でない $f\in I_i$ をとる。$\operatorname{LT}(f)\in\operatorname{LT}(I)$ なので、単項式順序 の記事の命題「単項式イデアル」の 1 により、ある $g\in G$ の $\operatorname{LM}(g)$ が $\operatorname{LM}(f)$ を割り切る。$\operatorname{LM}(f)$ には $x_1,\dots,x_i$ が現れないので $\operatorname{LM}(g)$ にも現れず、単項式順序 の記事の命題「消去の性質と次数の性質」の 1 により $g\in k[x_{i+1},\dots,x_n]$、すなわち $g\in G_i$ である。$k[x_{i+1},\dots,x_n]$ の辞書式順序は $k[x_1,\dots,x_n]$ の辞書式順序の制限なので、先頭項は同じであり、$\operatorname{LT}(I_i)$ は $G_i$ の先頭項で生成される。$I_i\neq0$ なら $\operatorname{LT}(I_i)\neq0$ なので $G_i\neq\emptyset$ である。$\square$