1. グラフで見ると何が見えるか
グレブナー基底による探索は、式変形を「計算」として見るだけでなく、状態空間の探索として見ると理解が一段深くなります。ノードは多項式、単項式、基底、S-ペア、部分問題、解候補を表し、エッジは「割る」「S-多項式を作る」「消去する」「分岐する」「正規形を取る」といった遷移を表します。
単項式の探索空間
単項式全体は整除関係で半順序集合になります。先頭イデアル \(\langle \mathrm{LT}(G)\rangle\) は上に閉じた領域で、そこから外れた単項式が標準単項式です。
簡約の探索空間
多項式割り算は、先頭単項式を単項式順序で小さくしていく有向非巡回グラフ上の移動です。停止性は「毎回真に小さくなる」ことから来ます。
Buchberger 法の探索空間
候補基底のノードから S-ペアが生まれ、正規形が 0 でなければ新しい基底ノードが追加されます。探索 frontier は「未処理 S-ペア」の集合です。
解空間の探索
lex 順序の三角形化、Boolean 制約、消去イデアルにより、探索問題を順に低次元化・分岐・検証できます。
2. DOT + d3-graphviz インタラクティブ図鑑
下のセレクタで図を切り替えると、DOT ソースを d3-graphviz が SVG として描画します。DOT は編集できるので、ノードやエッジを追加しながら探索構造の変化を観察できます。
DOT ソース
CDN が読み込めない環境では SVG は表示されません。その場合でも DOT ソースを Graphviz 対応ビューアに貼れば同じ図を確認できます。
3. 視覚文法：グレブナー探索を図に落とす規則
3.1 多項式をノードにする場合
多項式ノードには、少なくとも次の情報を載せます。
| 表示情報 | 意味 | 探索上の役割 |
|---|---|---|
| \(f\) | 多項式そのもの | 制約、または書換規則の本体 |
| \(\mathrm{LT}(f)\) | 先頭項 | どの単項式を消せるかを決める |
| \(\mathrm{LM}(f)\) | 先頭単項式 | 整除判定、S-ペアの lcm に使う |
| 次数 | 全次数や重み次数 | 探索コストの見積もりに使う |
| 由来 | 入力式か、S-ペアから得た式か | 証明トレース、不要式削除、デバッグに使う |
たとえば \(G=\{g_1,g_2\}\) のとき、\(\mathrm{LT}(g_i)\mid \mathrm{LT}(p)\) なら \(p\) は \(g_i\) によって一歩簡約できます。図では「現在の多項式」から「簡約後の多項式」へ矢印を引き、ラベルに使用した \(g_i\) と係数単項式を記します。
3.2 S-ペアをノードにする場合
\(f_i,f_j\) の S-多項式は
\[ S(f_i,f_j)=\frac{\mathrm{lcm}(\mathrm{LM}(f_i),\mathrm{LM}(f_j))}{\mathrm{LT}(f_i)}f_i- \frac{\mathrm{lcm}(\mathrm{LM}(f_i),\mathrm{LM}(f_j))}{\mathrm{LT}(f_j)}f_j. \]これは「先頭項をそろえて打ち消す」ための局所的な衝突解消です。探索図では、二つの基底ノードから S-ペアノードへ入り、正規形 \(\mathrm{NF}(S\mid G)\) が 0 なら剪定、0 でなければ新ノードを生成します。
4. 単項式整除 DAG と先頭イデアル
\(K[x,y]\) の単項式を \(x^a y^b\) と書くと、\(x^a y^b\mid x^c y^d\) は \(a\le c, b\le d\) と同値です。したがって、単項式全体は格子状の DAG になります。
有限個の先頭単項式 \(M=\{x^2,xy,y^3\}\) が与えられると、先頭イデアルは
\[ \langle M\rangle=\{m: x^2\mid m\text{ または }xy\mid m\text{ または }y^3\mid m\} \]です。これは DAG 上で上に閉じた領域です。補集合は標準単項式
\[ \mathcal{N}=\{1,x,y,y^2\} \]で、剰余環 \(K[x,y]/\langle x^2,xy,y^3\rangle\) のベクトル空間基底になります。
5. 簡約は「減少する道」を探すこと
固定した単項式順序 \(>\) に対して、\(p\to p-cm g\) という簡約ステップでは、\(cm\mathrm{LT}(g)=\mathrm{LT}(p)\) となるように選びます。このとき新しい多項式の先頭単項式は必ず古い先頭単項式より小さいので、無限に続くことはありません。
ただし、割る多項式の選び方により途中経路は変わります。グレブナー基底で割る場合には、最終的な正規形が一意になります。グレブナー基底でない集合で割ると、割る順番によって剰余が変わることがあります。これは探索アルゴリズムの再現性・枝刈り精度に直結します。
| 集合 | 剰余の一意性 | 探索での扱い |
|---|---|---|
| 任意の生成集合 \(F\) | 一般には一意でない | 途中結果の順序依存性に注意する |
| グレブナー基底 \(G\) | 一意 | 正規形を状態の canonical representation として使える |
| 被約グレブナー基底 | 一意かつ基底自体も正規化 | 比較、キャッシュ、同型判定に向く |
6. Buchberger 法のグラフ拡張
入力
\[ f_1=x^2-y,\qquad f_2=xy-1 \]を lex 順序 \(x>y\) で考えます。最初の S-多項式は
\[ S(f_1,f_2)=y f_1-x f_2=x-y^2. \]これが 0 に簡約されないので、\(g_3=x-y^2\) を追加します。次に
\[ S(f_2,g_3)=f_2-y g_3=y^3-1 \]も 0 に簡約されないので \(g_4=y^3-1\) を追加します。一方、\(S(f_1,g_3)\) は既存基底で 0 に簡約されます。最終的に被約グレブナー基底は
\[ G=\{x-y^2,\ y^3-1\} \]です。この一連の流れを図にすると、「衝突から新規制約が生まれ、余分な入力式が後で吸収される」構造が見えます。
手動ステップビューア
7. 消去と三角形化をグラフで読む
lex 順序 \(x>y>z\) のグレブナー基底は、しばしば上流変数を消去した三角形の形を作ります。たとえば
\[ I=\langle x+y+z,\\ xy+yz+zx-1,\\ xyz-2\rangle \]の lex グレブナー基底は
\[ G=\{x+y+z, \ y^2+yz+z^2+1, \ z^3+z-2\}. \]探索手順は、まず \(z^3+z-2=0\) を解き、次に \(y^2+yz+z^2+1=0\) を解き、最後に \(x=-y-z\) を代入する、という逆向き代入になります。
グラフでは、全変数空間から \(z\)-軸への射影、次に \((y,z)\) 平面への持ち上げ、最後に \((x,y,z)\) 空間への持ち上げとして描けます。
8. Boolean 探索と枝刈り
Boolean 変数 \(x_i\in\{0,1\}\) は多項式制約
\[ x_i^2-x_i=0 \]で表せます。節 \((a\lor b\lor \lnot c)\) は
\[ (1-a)(1-b)c=0 \]と表せます。全制約のグレブナー基底が \(\{1\}\) なら充足不能です。\(1\notin I\) なら解候補を lex 順序や標準単項式の構造から抽出できます。
グラフ探索では、変数代入の木を作り、各ノードで制約の正規形を見ます。途中で \(1\) が出れば枝を閉じます。これは SAT ソルバに似ていますが、代数的には「部分代入でイデアルを拡大し、その簡約で矛盾を検出する」操作です。
| 論理条件 | 多項式 | 意味 |
|---|---|---|
| \(x\) は Boolean | \(x^2-x=0\) | \(x=0\) または \(1\) |
| \(x\land y=z\) | \(z-xy=0\) | AND ゲート |
| \(x\oplus y=z\) | \(z-(x+y-2xy)=0\) | XOR ゲート |
| \(x\ne y\) | \(x+y-1=0\) | 2 色グラフ彩色の辺制約 |
9. 探索設計パターン
frontier を明示する
Buchberger 法では未処理 S-ペア、Boolean 探索では未確定代入、消去では未解決の低変数多項式が frontier です。
canonical state に落とす
状態を正規形で保存すれば、同じ状態を二度探索することを避けられます。これはグラフ探索の visited set と同じ発想です。
先頭イデアルで覆う
先頭単項式が増えるほど、探索空間の覆われる領域が大きくなります。標準単項式が減ることは情報が増えたことを意味します。
消去順序を目的に合わせる
解く対象が \(z\) だけなら \(x,y\) を先に消す順序を選びます。探索の目的が違えば良い順序も変わります。