グレブナー基底：詳細レポート

0. 全体像：グレブナー基底とは何か

グレブナー基底は、一言でいえば「多変数多項式イデアルに対する、割り算・消去・正規形計算を可能にする特殊な生成系」です。一変数多項式では Euclid の割り算により、剰余、最大公約因子、合同類などを明確に計算できます。多変数では単純な割り算が一意でなくなりますが、生成系をグレブナー基底に取り替えると、多くの点で一変数に近い計算体系が戻ってきます。

代数的な目的

多項式環 \(K[x_1,\dots,x_n]\) のイデアル \(I\) について、\(f\in I\) かどうか、\(K[x]/I\) の代表元は何か、イデアルがどのような初期項を持つかを計算したい。

幾何学的な目的

連立多項式方程式 \(f_1=\cdots=f_s=0\) の解集合を調べたい。特に変数を消去して、少数変数の方程式へ落としたい。

直観線形代数では、連立一次方程式を行基本変形して階段形にすると、解の構造が見えます。グレブナー基底は、非線形の多項式方程式に対する「階段形」の役割を果たします。ただし、多項式では項の順序を先に固定しないと「先頭」が決まらないため、単項式順序が理論全体の入口になります。

このレポートの読み方

グレブナー基底の中核は次の連鎖です。

\text{単項式順序} \Longrightarrow \text{先頭項} \Longrightarrow \text{多変数割り算} \Longrightarrow \text{S多項式} \Longrightarrow \text{Buchberger判定法} \Longrightarrow \text{グレブナー基底計算}.

順序を変えると同じイデアルでもグレブナー基底は変わります。特に辞書式順序は消去に強く、次数逆辞書式順序は実装上効率が良いことが多い、という実用上の使い分けがあります。

単項式順序の定義へ多変数割り算へ S多項式へ Buchbergerアルゴリズムへ消去定理へ計算ツールへ

1. 代数的準備

1.1 多項式環

係数体を \(K\) とします。典型例は \(\mathbb{Q}\), \(\mathbb{R}\), \(\mathbb{C}\), 有限体 \(\mathbb{F}_p\) です。変数 \(x_1,\dots,x_n\) による多項式全体は

K[x_1,\dots,x_n]

と書かれます。多項式は有限和

f=\sum_{\alpha\in\mathbb{N}^n} c_\alpha x^\alpha, \qquad x^\alpha=x_1^{\alpha_1}\cdots x_n^{\alpha_n}, \quad c_\alpha\in K

で表されます。ただし、実際に非零係数を持つ \(\alpha\) は有限個です。

定義：単項式・項・多項式の台

\(x^\alpha\) を単項式と呼びます。係数つきの \(c_\alpha x^\alpha\) を項と呼びます。多項式 \(f\) の非零項に現れる指数集合 \( \operatorname{supp}(f)=\{\alpha\in\mathbb{N}^n\mid c_\alpha\ne0\} \) を台と呼びます。

1.2 イデアル

部分集合 \(I\subset K[x_1, \dots,x_n]\) がイデアルであるとは、次を満たすことです。

f,g\in I \Rightarrow f+g\in I, \qquad f\in I,\\ h\in K[x_1,\dots,x_n] \Rightarrow hf\in I.

多項式 \(f_1, \dots,f_s\) によって生成されるイデアルは

\langle f_1, \dots,f_s\rangle =\left\{\sum_{i=1}^s h_i f_i\ \middle|\ h_i\in K[x_1, \dots,x_n]\right\}

です。グレブナー基底は、同じイデアルを生成する別の生成系 \(G=\{g_1, \dots,g_t\}\) で、先頭項に関して特別に良い性質を持つものです。

1.3 Noether 性

Hilbert の基底定理により、体上の多項式環 \(K[x_1, \dots,x_n]\) は Noether 環です。すなわち、任意のイデアルは有限生成です。グレブナー基底の存在は、より具体的には単項式イデアルの有限生成性、すなわち Dickson の補題に支えられます。

Dickson の補題

\(\mathbb{N}^n\) の任意の部分集合 \(A\) に対し、有限個の元 \(\alpha^{(1)},\dots, \alpha^{(r)}\in A\) が存在して、任意の \(\alpha\in A\) はある \(i\) について \(\alpha^{(i)}\leq \alpha\) 成分ごと、すなわち \(\alpha-\alpha^{(i)}\in\mathbb{N}^n\) を満たします。

単項式で言えば、任意の単項式イデアルは有限個の単項式で生成されます。

Dickson の補題がなぜ重要か

Buchberger アルゴリズムでは、S多項式の剰余を新しい生成元として追加していきます。もしこの追加が無限に続くなら、先頭項イデアルが真に大きくなり続けます。しかし単項式イデアルには無限に真に増大し続ける列が存在しないため、アルゴリズムは停止します。

2. 単項式順序

グレブナー基底では、各多項式の「最大の項」を選ぶ必要があります。そのために単項式全体に順序を入れます。

定義：単項式順序

\(\mathbb{N}^n\) 上の全順序 \(\succ\) が単項式順序であるとは、次を満たすことです。

全順序： 任意の \(\alpha, \beta\in\mathbb{N}^n\) について、\(\alpha=\beta\), \(\alpha\succ\beta\), \(\beta\succ\alpha\) のいずれか一つが成り立つ。
乗法との両立： \(\alpha\succ\beta\) なら任意の \(\gamma\in\mathbb{N}^n\) に対して \(\alpha+ \gamma\succ\beta+ \gamma\)。単項式では \(x^\alpha\succ x^\beta\Rightarrow x^\gamma x^\alpha\succ x^\gamma x^\beta\)。
整列性： 任意の非空部分集合が最小元を持つ。これにより、割り算の過程で無限降下が起きない。

2.1 辞書式順序 lex

変数順序を \(x_1\succ x_2\succ\cdots\succ x_n\) とします。 \(\alpha=(\alpha_1, \dots, \alpha_n)\) と \(\beta=(\beta_1, \dots, \beta_n)\) に対して、左から見て最初に異なる成分が \(\alpha_i>\beta_i\) なら \(x^\alpha\succ_{\mathrm{lex}}x^\beta\) とします。

x^2y^0z^1 \succ_{\mathrm{lex}} xy^{100}z^{1000} \quad \text{because } 2>1 \text{ in the first coordinate.}

lex は変数消去に強い一方、実計算では中間式が大きくなりやすい傾向があります。

2.2 次数辞書式順序 grlex

まず総次数 \(|\alpha|=\alpha_1+\cdots+\alpha_n\) を比較し、総次数が大きい方を大きいとします。総次数が等しい場合は lex で比較します。

x^2 \prec_{\mathrm{grlex}} xy^2 \quad (2<3), \qquad x^2z \succ_{\mathrm{grlex}} xy^2 \quad (3=3, \text{ then lex}).

2.3 次数逆辞書式順序 grevlex

総次数を先に比較し、等しいときは右から左へ見て、最後に異なる成分が小さい方を大きいとします。これは最初は直観に反しますが、実装上は非常に重要な順序です。

x^\alpha\succ_{\mathrm{grevlex}}x^\beta \iff \begin{cases} |\alpha|>|\beta|, & \text{or}\\ |\alpha|=|\beta| \text{ and, for the largest } j \text{ with } \alpha_j\ne\beta_j, \alpha_j<\beta_j. \end{cases}

順序	特徴	主な用途
lex	最初の変数を最優先する。消去定理と相性が良い。	変数消去、三角形化、解の投影
grlex	次数を優先し、同次数で lex。	理論説明、次数付き構造
grevlex	次数を優先し、同次数で逆向きに比較。	高速な実計算の初期順序として頻用

注意単項式順序は「好きな順序」ではありません。乗法との両立と整列性が必須です。例えば単に指数ベクトルを実数値関数で評価して並べる場合、同点処理が全順序になっているか、負の重みで無限降下が起きないかを確認する必要があります。

3. 先頭項、先頭単項式、初期イデアル

単項式順序 \(\succ\) を固定します。非零多項式 \(f=\sum c_\alpha x^\alpha\) に対し、台の中で最大の指数を \(\alpha^*\) とします。

定義：先頭データ

\begin{aligned} \operatorname{LM}(f)&=x^{\alpha^*} &&\text{先頭単項式 leading monomial},\\ \operatorname{LC}(f)&=c_{\alpha^*} &&\text{先頭係数 leading coefficient},\\ \operatorname{LT}(f)&=c_{\alpha^*}x^{\alpha^*} &&\text{先頭項 leading term}. \end{aligned}

例えば \(K[x,y,z]\), 変数順序 \(x\succ y\succ z\) で

f=3x^2z+7xy^{10}-5y^3z^2+1

とすると、lex では \(\operatorname{LT}(f)=3x^2z\) ですが、grlex や grevlex では総次数の大きい \(7xy^{10}\) が先頭項になります。

3.1 初期イデアル

定義：初期イデアル

イデアル \(I\subset K[x_1, \dots,x_n]\) の初期イデアル、または先頭項イデアルを

\operatorname{in}_\succ(I) =\langle \operatorname{LT}(f)\mid f\in I, f\ne0\rangle

と定めます。係数を無視して \(\langle \operatorname{LM}(f)\mid f\in I\rangle\) と見ても、体上では本質的に同じ単項式イデアルです。

初期イデアルは単項式イデアルなので、構造がはるかに単純です。グレブナー基底とは、有限個の生成元の先頭項だけでイデアル全体の初期イデアルを生成できるような生成系です。

G=\{g_1, \dots,g_t\}\subset I \quad\text{が良い生成系であるとは} \quad \operatorname{in}(I)=\langle \operatorname{LT}(g_1), \dots, \operatorname{LT}(g_t)\rangle

4. 多変数多項式の割り算

一変数では \(f=qg+r\) かつ \(\deg r<\deg g\) が一意に決まります。多変数では「どの先頭項で割るか」「割れない項をいつ剰余へ送るか」に依存し、一般には一意ではありません。

多変数割り算アルゴリズム

入力：多項式 \(f\)、順序つきリスト \(F=(f_1, \dots,f_s)\)、単項式順序 \(\succ\)。
出力：商 \(q_1, \dots,q_s\) と剰余 \(r\) で \(f=q_1f_1+ \cdots+q_sf_s+r\) を満たすもの。

q_1 = ... = q_s = 0, r = 0, p = f
while p != 0:
    p の先頭項 LT(p) を見る
    ある i について LM(f_i) が LM(p) を割るなら、最初のその i を選ぶ
        m = LT(p) / LT(f_i)
        q_i = q_i + m
        p = p - m f_i
    どの i でも割れないなら
        r = r + LT(p)
        p = p - LT(p)

剰余 \(r\) の各項は、どの \(\operatorname{LT}(f_i)\) でも割れない単項式を持ちます。この性質自体は重要ですが、\(F\) が任意の生成系だと、同じ \(f\) でも \(F\) の順番や選び方によって剰余が変わります。

多変数割り算の非一意性生成系がグレブナー基底でないと、剰余はイデアル剰余として信用できません。特に、\(f\in\langle f_1, \dots,f_s\rangle\) であっても割り算の剰余が \(0\) にならないことがあります。

グレブナー基底による剰余の一意性

\(G\) が単項式順序 \(\succ\) に関するグレブナー基底なら、\(f\) を \(G\) で割った剰余は割り算の細部に依存せず一意です。この剰余を \(\operatorname{NF}_G(f)\) または \(\overline{f}^{G}\) と書き、正規形と呼びます。

この定理により、イデアル所属判定が可能になります。

f\in I=\langle G\rangle \quad\Longleftrightarrow\quad \operatorname{NF}_G(f)=0 \qquad (G\text{ がグレブナー基底}).

5. グレブナー基底の定義と同値条件

定義：グレブナー基底

単項式順序 \(\succ\) を固定し、\(I\subset K[x_1, \dots,x_n]\) をイデアルとします。有限集合 \(G=\{g_1, \dots,g_t\}\subset I\) が \(I\) のグレブナー基底であるとは、

\operatorname{in}_\succ(I)= \langle \operatorname{LT}_\succ(g_1), \dots, \operatorname{LT}_\succ(g_t)\rangle

が成り立つことです。通常はさらに \(I=\langle G\rangle\) も含めて述べますが、上式と \(G\subset I\) から、\(G\) は \(I\) を生成することが従います。

5.1 同値な見方

\(G=\{g_1, \dots,g_t\}\) が \(I\) のグレブナー基底であることは、以下と同値です。

任意の \(0\ne f\in I\) について、ある \(i\) が存在して \(\operatorname{LM}(g_i)\mid \operatorname{LM}(f)\)。
任意の \(f\) について、\(f\in I\) であることと \(G\) による剰余が \(0\) であることが同値。
\(K[x]/I\) の各剰余類が、\(\operatorname{in}(I)\) に含まれない単項式、すなわち標準単項式の線形結合で一意に表せる。

同値性の要点

\(\operatorname{in}(I)=\langle\operatorname{LT}(g_i)\rangle\) であるなら、任意の \(f\in I\) の先頭項は初期イデアルに属するので、ある \(\operatorname{LT}(g_i)\) で割れます。逆に、任意の \(f\in I\) の先頭単項式がどれかの \(\operatorname{LM}(g_i)\) で割れるなら、初期イデアルの生成元はすべて \(\operatorname{LT}(g_i)\) から出るため、初期イデアルの等式が成立します。

5.2 なぜ「基底」と呼ぶのか

線形代数の基底のように一次独立である、という意味ではありません。グレブナー基底はイデアルの生成系です。しかし、商空間 \(K[x]/I\) に対して、標準単項式が \(K\)-ベクトル空間としての基底を与えるため、線形代数的な基底とも深く関係します。

6. S多項式：先頭項の衝突を検出する道具

グレブナー基底でない理由は、多くの場合、生成元同士の組み合わせで先頭項が相殺され、より小さいが重要な新しい先頭項が現れることです。S多項式はこの相殺を体系的に検出します。

定義：S多項式

非零多項式 \(f,g\) に対して、 \(\operatorname{LT}(f)=a x^\alpha\), \(\operatorname{LT}(g)=b x^\beta\) とします。 \(x^\gamma=\operatorname{lcm}(x^\alpha,x^\beta) =x_1^{\max(\alpha_1, \beta_1)}\cdots x_n^{\max(\alpha_n, \beta_n)}\) とおくと、S多項式は

S(f,g) =\frac{x^\gamma}{\operatorname{LT}(f)}f -\frac{x^\gamma}{\operatorname{LT}(g)}g =\frac{x^\gamma}{a x^\alpha}f -\frac{x^\gamma}{b x^\beta}g.

係数まで含めて割るので、第一項と第二項の先頭項はいずれも \(x^\gamma\) となり、差を取ると相殺されます。つまり S多項式は「先頭項を消したときに何が残るか」を見るものです。

6.1 Buchberger 判定法

Buchberger 判定法

\(G=\{g_1, \dots,g_t\}\) をイデアル \(I=\langle G\rangle\) の有限生成系とします。単項式順序 \(\succ\) を固定します。このとき、\(G\) が \(I\) のグレブナー基底であるための必要十分条件は、すべての組 \(i

\operatorname{NF}_G(S(g_i,g_j))=0

が成り立つことです。

証明の構造

必要性は比較的直接的です。\(G\) がグレブナー基底なら、\(S(g_i,g_j)\in I\) ですから、グレブナー基底による正規形は \(0\) です。

十分性の核心は、任意の \(f\in I\) を \(f=\sum h_i g_i\) と表したとき、右辺の各 \(h_i g_i\) の先頭単項式の最大値をできるだけ小さくする表現を選ぶことです。もし最大の先頭単項式が右辺で相殺されて \(\operatorname{LT}(f)\) より大きいものが消えているなら、その相殺は本質的に S多項式の組み合わせで説明できます。S多項式がすべて \(G\) で \(0\) に簡約されるという仮定により、その表現を最大単項式の小さい表現へ置き換えられます。これは最小性に反します。したがって相殺後の \(\operatorname{LT}(f)\) はある \(\operatorname{LT}(g_i)\) で割れ、グレブナー基底の同値条件が成立します。

S の意味 S は syzygy, subtraction, special のように説明されることがありますが、本質は「二つの先頭項の最小公倍単項式まで持ち上げて先頭項を相殺する」ことです。

7. Buchberger アルゴリズム

Buchberger 判定法は、そのままアルゴリズムになります。生成系がグレブナー基底でなければ、どこかの S多項式の剰余が非零になります。その剰余を新しい生成元として追加します。

Buchberger アルゴリズム

G = {f_1, ..., f_s}
すべてのペア (g_i, g_j) を候補集合 P に入れる
while P が空でない:
    P から 1 つのペア (g_i, g_j) を取り出す
    S = S(g_i, g_j)
    r = S を G で割った剰余
    if r != 0:
        G = G ∪ {r}
        新しい r と既存の各 g とのペアを P に追加する
return G

7.1 停止性

非零剰余 \(r\) を追加すると、通常は

\langle \operatorname{LT}(G)\rangle \subsetneq \langle \operatorname{LT}(G\cup\{r\})\rangle

となります。もし等号なら \(\operatorname{LT}(r)\) は既存の先頭項で割れるため、割り算で \(r\) の先頭項は残らないはずだからです。したがって非零剰余の追加は初期イデアルを真に増大させます。単項式イデアルは無限に真に増大し続けられないので、有限回で停止します。

7.2 ペア削減基準

ナイーブに全ペアを処理すると非常に高コストです。Buchberger の古典的な改良には次のような基準があります。

基準	内容	直観
積基準	\(\gcd(\operatorname{LM}(f),\operatorname{LM}(g))=1\) なら、多くの場合 \(S(f,g)\) は自明に \(0\) へ簡約される。	先頭単項式が互いに素なら、相殺の干渉が少ない。
連鎖基準	別の生成元 \(h\) が \(f,g\) の lcm の間に入り、既に関連ペアが処理済みなら、\(f,g\) のペアを省略できることがある。	相殺情報が他のペアから導かれる。
正規形計算の戦略	どの割る多項式を選ぶか、先にどの項を消すか、基底をどの順で並べるかで速度が変わる。	同じ数学でも中間式の大きさが大きく変わる。

7.3 実務上の典型戦略

実際の計算機代数システムでは、grevlex で高速にグレブナー基底を求め、その後 FGLM アルゴリズムなどで lex へ順序変換する、といった戦略が用いられることがあります。特に零次元イデアルではこの方針が有効です。

8. 簡約グレブナー基底と一意性

グレブナー基底は一意ではありません。例えば任意の生成元に同じイデアル内の冗長な多項式を追加してもグレブナー基底であり続ける場合があります。そこで標準形として簡約グレブナー基底を考えます。

定義：最小・簡約グレブナー基底

グレブナー基底 \(G\) が最小であるとは、各 \(g\in G\) がモニック、つまり \(\operatorname{LC}(g)=1\) であり、かつどの \(g\in G\) についても \(\operatorname{LM}(g)\) が他の \(h\in G\setminus\{g\}\) の \(\operatorname{LM}(h)\) で割れないことです。

さらに簡約であるとは、各 \(g\in G\) の先頭項以外の項が、他の \(h\in G\setminus\{g\}\) の先頭単項式で割れないことです。

簡約グレブナー基底の一意性

体 \(K\)、多項式環 \(K[x_1, \dots,x_n]\)、イデアル \(I\)、単項式順序 \(\succ\) を固定すると、\(I\) の簡約グレブナー基底は一意に定まります。

一意性の理由

グレブナー基底が決める初期イデアル \(\operatorname{in}(I)\) はイデアル \(I\) と順序 \(\succ\) だけで決まります。最小単項式生成元も単項式イデアルにより一意に決まります。各先頭単項式に対応する多項式は、同じ先頭単項式を持つモニックな元を標準単項式だけで補正したものとして一意になるため、簡約グレブナー基底全体も一意です。

この一意性により、グレブナー基底はイデアルの「正規化された表現」として使えます。二つのイデアルが等しいかどうかは、同じ順序で簡約グレブナー基底を計算して比較すれば判定できます。

9. 消去定理と連立方程式の求解

グレブナー基底の最重要応用の一つが変数消去です。変数順序を \(x_1\succ x_2\succ\cdots\succ x_n\) とした lex 順序では、先頭側の変数を消す情報が基底の中に現れます。

消去定理

\(I\subset K[x_1, \dots,x_n]\) とし、lex 順序 \(x_1\succ x_2\succ\cdots\succ x_n\) に関するグレブナー基底を \(G\) とします。 \(k=0, 1, \dots,n-1\) に対し、

I_k=I\cap K[x_{k+1}, \dots,x_n]

を第 \(k\) 消去イデアルとすると、

G_k=G\cap K[x_{k+1}, \dots,x_n]

は \(I_k\) のグレブナー基底です。

9.1 方程式求解の流れ

零次元の連立方程式、すなわち有限個の解を持つ系では、lex グレブナー基底が三角形に近い形を与えることがあります。

\begin{cases} g_n(x_n)=0,\\ g_{n-1}(x_{n-1},x_n)=0,\\ \cdots,\\ g_1(x_1, \dots,x_n)=0. \end{cases}

まず一変数方程式 \(g_n(x_n)=0\) を解き、その解を上へ代入していくことで候補解を求めます。ただし重複根、代数閉包、飽和、根の拡張可能性などに注意が必要です。

9.2 陰関数化・パラメータ消去

例えばパラメータ表示 \(x=t^2, y=t^3\) の像の方程式を求めるには、

I=\langle x-t^2, y-t^3\rangle\subset K[t,x,y]

を考え、\(t\) を最初に置く lex 順序で \(I\cap K[x,y]\) を求めます。結果として \(y^2-x^3=0\) が現れます。

なぜ消去できるのか

lex 順序では、\(x_1, \dots,x_k\) を含む単項式は、それらを含まない単項式より大きくなりやすいです。\(I\cap K[x_{k+1}, \dots,x_n]\) の多項式を割り算するとき、剰余がこの小さい変数だけの環に留まるため、グレブナー基底の中の同じ小さい変数だけの部分で消去イデアルが生成されます。

10. 標準単項式、Hilbert 関数、商環

初期イデアル \(\operatorname{in}(I)\) は単項式イデアルです。その補集合にある単項式は、商環 \(K[x]/I\) の標準的な代表元になります。

定義：標準単項式

単項式 \(x^\alpha\) が標準単項式であるとは、 \(x^\alpha\notin \operatorname{in}(I)\)、つまりどの初期イデアル生成単項式にも割られないことです。

標準単項式の基底性

\(G\) を \(I\) のグレブナー基底とします。標準単項式全体の剰余類は、商環 \(K[x]/I\) を \(K\)-ベクトル空間と見たときの基底をなします。

標準単項式が有限個なら、商環は有限次元であり、代数閉体上では多様体が零次元であることと深く関係します。重複度を込めた解の個数は \(\dim_K K[x]/I\) で測られます。

10.1 Hilbert 関数

斉次イデアルに対し、次数 \(d\) 成分の次元 \(H_I(d)=\dim_K (K[x]/I)_d\) を Hilbert 関数と呼びます。グレブナー基底を使うと、\(I\) の Hilbert 関数は \(\operatorname{in}(I)\) の Hilbert 関数と一致します。単項式イデアルの Hilbert 関数は組合せ的に数えられるため、次元や次数を計算できます。

11. 幾何学的意味：多様体とイデアル

代数閉体 \(K\) 上で、多項式集合 \(S\subset K[x_1, \dots,x_n]\) の零点集合を

V(S)=\{a\in K^n\mid f(a)=0\text{ for all }f\in S\}

と書きます。\(V(S)\) は \(\langle S\rangle\) のみに依存します。グレブナー基底はイデアルを変えないので、零点集合も変えません。しかし、計算しやすい生成系に変換します。

11.1 Nullstellensatz との接点

Hilbert の零点定理は、代数閉体上で幾何学的対象 \(V(I)\) と根基イデアル \(\sqrt{I}\) の対応を与えます。グレブナー基底はこの対応の計算面を支えます。例えば、\(1\in I\) かどうかは \(G=\{1\}\) になるか、または正規形で判定でき、これは方程式系が解を持たないことを意味します。

11.2 射影と閉包

消去イデアル \(I\cap K[x_{k+1}, \dots,x_n]\) は、\(V(I)\) を後半の座標へ射影した像の Zariski 閉包を記述します。実数解集合の通常位相の射影とは異なる場合があるため、幾何的解釈では体と位相に注意が必要です。

12. 実装・高度な話題

12.1 係数膨張

有理数係数で Buchberger アルゴリズムを実行すると、中間係数の分子・分母が急速に大きくなることがあります。これを係数膨張と呼びます。対策として、整数係数の内容を取り除く、有限体で計算して中国剰余で復元する、モジュラー計算を行うなどの方法があります。

12.2 F4 / F5 の考え方

現代的なグレブナー基底計算では、多数の S多項式の簡約を個別に行うのではなく、線形代数の行列簡約としてまとめて処理する手法が重要です。F4 はこの行列化の代表例です。F5 はさらにシグネチャを用い、不要な零簡約を避ける設計です。

12.3 順序変換

同じイデアルでも単項式順序を変えるとグレブナー基底が変わります。計算が速い順序でまず基底を求め、その後目的に合う順序へ変換する方法があります。零次元イデアルに対する FGLM アルゴリズムはその代表です。

12.4 重み順序とトロピカル幾何

重みベクトル \(w\in\mathbb{R}^n\) によって \(w\cdot\alpha\) を比較する初期形式も重要です。同点を単項式順序で解消すれば単項式順序が得られます。重み初期イデアルの変化は Gröbner fan やトロピカル多様体と関係します。

12.5 非可換・微分作用素への拡張

グレブナー基底の思想は、可換多項式環だけでなく、非可換代数、自由代数、Weyl 代数、微分作用素環にも拡張されます。ただし、単項式順序、停止性、S多項式に対応する臨界対の扱いはそれぞれの代数構造に合わせて変わります。

13. 手計算例

13.1 例：\(I=\langle x^2-y, xy-1\rangle\subset \mathbb{Q}[x,y]\)

lex 順序 \(x\succ y\) を使います。

f_1=x^2-y, \qquad f_2=xy-1.

先頭単項式は \(\operatorname{LM}(f_1)=x^2\), \(\operatorname{LM}(f_2)=xy\) です。最小公倍単項式は \(x^2y\) なので、

\[ S(f_1,f_2)=y f_1-x f_2 =y(x^2-y)-x(xy-1) =x-y^2. \]

\(x-y^2\) は \(f_1,f_2\) では簡約されないので、 \(f_3=x-y^2\) を追加します。

次に

\[ S(f_1,f_3)=f_1-xf_3 =(x^2-y)-x(x-y^2)=xy^2-y =y(xy-1) \]

なので \(f_2\) で \(0\) に簡約されます。また

\[ S(f_2,f_3)=f_2-yf_3 =(xy-1)-y(x-y^2)=y^3-1. \]

これを \(f_4=y^3-1\) として追加します。最終的に簡約グレブナー基底は

\{x-y^2, y^3-1\}

です。これにより、方程式系はまず \(y^3=1\) を解き、その後 \(x=y^2\) と戻せばよいことがわかります。

13.2 例：陰関数化

パラメータ表示 \(x=t^2, y=t^3\) の曲線を考えます。

I=\langle x-t^2, y-t^3\rangle\subset K[t,x,y].

lex 順序 \(t\succ x\succ y\) で消去すると、\(I\cap K[x,y]\) は

\langle y^2-x^3\rangle

で生成されます。したがって像の Zariski 閉包は半立方放物線 \(y^2=x^3\) です。

13.3 例：所属判定

\(G=\{x-y^2, y^3-1\}\) とし、\(f=x^2y-y\) が \(I\) に属するか判定します。

x\equiv y^2 \pmod{I} \quad\Rightarrow\quad x^2y-y\equiv y^4y-y=y^5-y=y(y^4-1).

\(y^3\equiv1\) なので \(y^5-y\equiv y^2-y\) です。これは一般に \(0\) ではないため、\(f\notin I\) です。正確にはグレブナー基底で割った正規形が \(y^2-y\) になります。

14. よくある誤解と注意点

誤解 1：生成系なら何でも割り算に使える生成系で割れることと、イデアルに属することは同じではありません。グレブナー基底でない生成系では、\(f\in I\) でも剰余が非零になることがあります。

誤解 2：グレブナー基底はイデアルだけで決まる単項式順序を固定しなければ決まりません。lex, grlex, grevlex で結果は変わります。簡約グレブナー基底が一意なのは、イデアルと単項式順序の両方を固定した場合です。

誤解 3：「基底」なので最小個数の生成元であるグレブナー基底は線形代数の基底とは異なります。冗長な元を含むこともあります。簡約グレブナー基底は標準的ですが、生成元数がイデアル生成元数として最小とは限りません。

誤解 4：lex が常に最良 lex は消去に強いものの、計算量が大きくなりやすいです。実計算では grevlex で計算してから順序変換する方が速い場合があります。

実用上のチェックリスト

係数体を明確にする。\(\mathbb{Q}\) か、有限体か、代数拡大か。
変数順序を明確にする。特に lex では変数の並びが結論を大きく変える。
目的を明確にする。所属判定、消去、解の個数、陰関数化、最適化など。
計算結果が巨大になる可能性を見積もる。高次数・多変数では急激に難しくなる。
得られた基底が簡約されているか確認する。比較や保存には簡約基底が便利。

15. 対話ツール

以下の計算器は教育用の小規模ツールです。係数は整数または有理数、変数は x,y,z を想定しています。入力例：x^2 - y, x*y - 1, 1/2*x^2 - y*z。大きな問題や本格的な計算には専用の計算機代数システムを使ってください。

15.1 単項式順序比較

順序

単項式 A の指数

単項式 B の指数

15.2 S多項式を計算

順序

\(f\)

\(g\)

15.3 多変数割り算・正規形

順序

割られる多項式

割る多項式リスト
1行に1個

15.4 Buchberger アルゴリズム

順序

生成元
1行に1個

最大ペア処理数

16. 用語集

用語	意味
単項式順序	単項式を比較する全順序。乗法と両立し、整列性を持つ。
先頭項 \(\operatorname{LT}(f)\)	固定した単項式順序で最大の項。
初期イデアル \(\operatorname{in}(I)\)	イデアル内の全多項式の先頭項で生成される単項式イデアル。
グレブナー基底	自分たちの先頭項で初期イデアル全体を生成するイデアル生成系。
S多項式	二つの多項式の先頭項を最小公倍単項式まで持ち上げて相殺した多項式。
Buchberger 判定法	全 S多項式が基底で 0 に簡約されることと、グレブナー基底であることの同値性。
正規形	グレブナー基底で割った一意な剰余。
標準単項式	初期イデアルに入らない単項式。商環のベクトル空間基底になる。
消去イデアル	一部の変数を含まない多項式だけを取り出したイデアル。