グレブナー基底を使った探索：大量の具体例集

\(x+y-3=0,\ x-y-1=0\) を解く。

\(I=\langle x+y-3, x-y-1\rangle\subset K[x,y]\)、lex \(x>y\)。

\(G=\{x-2,\ y-1\}\)。

解は \((x,y)=(2,1)\)。線形系ではグレブナー基底計算は Gaussian elimination と同じ構造を持つ。

探索としては、先頭変数 \(x\) を含む式を作り、最後に \(y\) を固定する三角形化である。

\(y=x^2\) と \(y=2x-1\) の交点を求める。

\(I=\langle y-x^2,\ y-2x+1\rangle\)、lex \(x>y\)。

\(G=\{2x-y-1,\ (y-1)^2\}\)。

\(y=1\)、\(x=1\)。重根なので接している。

単に点を求めるだけでなく、\((y-1)^2\) が出ることで重複度も見える。

単位円 \(x^2+y^2=1\) と直線 \(x=y\) の交点。

\(I=\langle x^2+y^2-1,\ x-y\rangle\)、lex \(x>y\)。

\(G=\{x-y,\ 2y^2-1\}\)。

\(y=\pm 1/\sqrt2\)、\(x=y\)。

まず \(y\) だけの方程式に落とし、次に \(x\) を復元する。

\(x^2+y^2=1\) と \((x-1)^2+y^2=1\) の交点。

\(I=\langle x^2+y^2-1,(x-1)^2+y^2-1\rangle\)、lex \(x>y\)。

\(G=\{2x-1,\ 4y^2-3\}\)。

\(x=1/2\)、\(y=\pm\sqrt3/2\)。

二式を引くと \(2x-1=0\) が出る。その後に \(y\) が残る。GB はこの消去を体系化する。

\(x^2+2y^2=1\) と \(x+y=0\) の交点。

\(I=\langle x^2+2y^2-1,x+y\rangle\)、lex \(x>y\)。

\(G=\{x+y,\ 3y^2-1\}\)。

\(y=\pm1/\sqrt3\)、\(x=-y\)。

線形制約で \(x\) を消去し、1変数二次方程式へ落とす。

\(x^2-y=0,\ xy-1=0\)。

\(I=\langle x^2-y,xy-1\rangle\)、lex \(x>y\)。

\(G=\{x-y^2,\ y^3-1\}\)。

\(y^3=1\)、\(x=y^2\)。複素数上では 3 点。

Buchberger 法の S-ペアから \(x-y^2\)、さらに \(y^3-1\) が生まれる典型例。

\(x+y+z=0,\ xy+yz+zx=0,\ xyz=1\)。

\(I=\langle x+y+z,xy+yz+zx,xyz-1\rangle\)、lex \(x>y>z\)。

\(G=\{x+y+z,\ y^2+yz+z^2,\ z^3-1\}\)。

まず \(z^3=1\) を解き、次に \(y\)、最後に \(x\) を復元する。

対称式で書かれた制約が三角形化され、解探索の順序が明示される。

\(x+y+z=0,\ xy+yz+zx=1,\ xyz=2\)。

\(I=\langle x+y+z,xy+yz+zx-1,xyz-2\rangle\)、lex \(x>y>z\)。

\(G=\{x+y+z,\ y^2+yz+z^2+1,\ z^3+z-2\}\)。

\(z\) は \(z^3+z-2=0\) の根。各 \(z\) に対し \(y\) は二次方程式、\(x=-y-z\)。

探索木の根が \(z\) の候補、次の階層が \(y\)、葉が \(x\) になる。

\(I=\langle x^2-y,xy-1\rangle\) に \(h=x-y^2\) が属するか。

上の例と同じ GB \(G=\{x-y^2,y^3-1\}\) で \(h\) を割る。

\(\mathrm{NF}(h\mid G)=0\)。

\(h\in I\)。実際 \(h=S(x^2-y,xy-1)\)。

探索で得た新規式は、もとの制約から導かれる隠れ制約である。

\(I=\langle x+y,y+z\rangle\) に \(x+z\) は属するか。

lex \(x>y>z\) で \(G=\{x-z, y+z\}\)。

\(x+z\) を割ると \(2z\) が残る。

標数 0 では \(x+z otin I\)。ただし \(x-z\in I\)、\(y+z\in I\)。

正規形が 0 でないことは、イデアル所属探索の反証になる。

単位円 \(x^2+y^2=1\) と直線 \(y=ax\) の交点を \(x\) で表す。

\(I=\langle x^2+y^2-1,y-ax\rangle\)、変数順序 \(y>x\)、\(a\) は係数扱い。

\(G=\{y-ax,\ (a^2+1)x^2-1\}\)。

\(x=\pm 1/\sqrt{a^2+1}\)、\(y=ax\)。

消去順序を \(y>x\) にしたことで、\(x\) だけの条件が直接現れる。

\(x^2=a\) と \(x=b\) が同時に成り立つ条件。

\(I=\langle x^2-a,x-b\rangle\)、lex \(x>a>b\)。

\(G=\{x-b,\ a-b^2\}\)。

存在条件は \(a=b^2\)。そのとき \(x=b\)。

未知数 \(x\) を消去すると、パラメータ空間内の実現可能領域が出る。

\(x+y=1\) 上で \(x^2+y^2\) を最小化する。

ラグランジュ条件 \(2x+\lambda=0, 2y+\lambda=0, x+y-1=0\)。

lex \(x>y>\lambda\) で \(G=\{2x-1,2y-1,\lambda+1\}\)。

最小点は \((1/2,1/2)\)。

多項式最適化では、KKT 条件を解く探索に GB を使える。大域最適性は別途確認が必要。

点 \((a,b)\) に最も近い単位円上の点候補を求める。

\(F=(x-a)^2+(y-b)^2\)、制約 \(x^2+y^2=1\)。KKT は \(2(x-a)+2\lambda x=0, 2(y-b)+2\lambda y=0, x^2+y^2-1=0\)。

消去により \((\lambda+1)^2-a^2-b^2=0\) が現れる。

\((a,b) e(0,0)\) なら候補は \((x,y)=\pm(a,b)/\sqrt{a^2+b^2}\)。最近点は同方向の方。

ラグランジュ乗数を消去すると、幾何的条件が代数方程式として出る。

\(I=\langle x^2-y,xy-1\rangle\) を異なる順序で見る。

lex \(x>y\) と grevlex \(x>y\)。

lex: \(\{x-y^2,y^3-1\}\)。grevlex: \(\{x^2-y,xy-1,-x+y^2\}\)。

lex は消去に強く、grevlex は計算が軽くなりやすい。

探索目的が「解を三角形化する」なら lex、「まず基底を速く作る」なら grevlex が候補。

\(z=x\land y\) を多項式で表す。

\(x^2-x,y^2-y,z^2-z,z-xy\)。

lex \(x>y>z\) で \(\{x^2-x, xy-z, xz-z, y^2-y, yz-z, z^2-z\}\)。

Boolean 性と \(z=xy\) が正規形に反映される。

論理回路を多項式制約に変換すると、回路探索を代数的に行える。

\(z=x\oplus y\)。

\(z-(x+y-2xy)=0\) と Boolean 制約。

lex \(x>y>z\) で \(\{x+2yz-y-z, y^2-y, z^2-z\}\)。

\(x=y+z-2yz\) として復元できる。

XOR は線形に見えるが、有理数上の Boolean 多項式では積項が現れる。

節 \((x\lor y)\land(\lnot x\lor z)\land(y\lor\lnot z)\)。

\((1-x)(1-y)=0,\ x(1-z)=0,\ (1-y)z=0\) と Boolean 制約。

lex \(x>y>z\) で \(\{x^2-x, xz-x, y-1, z^2-z\}\)。

必ず \(y=1\)。\(z\in\{0,1\}\)、\(z=0\) なら \(x=0\)、\(z=1\) なら \(x\in\{0,1\}\)。

GB が強制リテラル \(y=1\) を発見している。

3頂点パス \(1-2-3\) を2色で塗る。

Boolean 制約と辺制約 \(x_1+x_2-1=0, x_2+x_3-1=0\)。

\(G=\{x_1-x_3, x_2+x_3-1, x_3^2-x_3\}\)。

\(x_3\) を自由に選ぶと \(x_1=x_3\)、\(x_2=1-x_3\)。2通り。

GB が「同じ側の頂点は同色」という構造を抽出する。

三角形 \(K_3\) を2色で塗れるか。

Boolean 制約と \(x_i+x_j-1=0\) を全辺に置く。

\(G=\{1\}\)。

解なし。

探索木を展開しなくても、代数的矛盾 \(1\in I\) が得られる。

三角形を3色で塗る。

各頂点変数を 1 の三乗根にし、辺 \((i,j)\) に \(x_i^2+x_ix_j+x_j^2=0\) を置く。

lex で \(\{x_1+x_2+x_3, x_2^2+x_2x_3+x_3^2, x_3^3-1\}\)。

3! 通りの本質的彩色が表現される。

根の符号化を使うと one-hot 変数より少ない変数で彩色を表せる。

完全グラフ \(K_4\) を3色で塗れるか。

三乗根符号化で各頂点 \(x_i^3-1=0\)、各辺 \(x_i^2+x_ix_j+x_j^2=0\)。

全制約のグレブナー基底は \(\{1\}\)。

3色では塗れない。

彩色不能性がイデアル全体の単位元生成として検出される。

4×4 盤に互いに攻撃しない 4 個の queen を置く。

変数 \(q_{ij}\in\{0,1\}\)。各行・列に \(\sum_j q_{ij}-1=0,\sum_i q_{ij}-1=0\)。各斜めペアに \(q_{ij}q_{kl}=0\)。

完全な GB は大きいが、lex 順序では最後の変数から順に解候補を列挙できる。

4-Queens には 2 解がある。

「ちょうど1つ」と「同時配置禁止」を多項式にすると、exact cover 型探索になる。

集合 \(U=\{1,2,3\}\)、候補 \(A=\{1,2\}, B=\{2,3\}, C=\{3\}, D=\{1\}\) で exact cover を探す。

Boolean 変数 \(a,b,c,d\)。要素ごとに \(a+d-1=0, a+b-1=0, b+c-1=0\)。

線形部分だけで \(b=1-a, d=1-a, c=a\)。Boolean より \(a\in\{0,1\}\)。

\(a=1\) なら \(A,C\)、\(a=0\) なら \(B,D\)。

線形等式で大きく枝刈りし、Boolean 制約で残りを確定する。

\(f=0\) かつ \(g\ne0\) を代数的に扱う。

新変数 \(t\) を導入して \(tg-1=0\) を追加する。つまり \(I+\langle tg-1\rangle\)。

例：\(x^2-1=0, x\ne1\) は \(x^2-1,t(x-1)-1\) から \(x+1=0\) が得られる。

\(x=-1\) だけが残る。

探索で「この枝では \(g=0\) を禁止する」という条件を多項式だけで表現できる。

\(x+y+1=0, xy=0\) を \(\mathbb F_2\) で解く。

Boolean 制約は \(x^2-x,y^2-y\) だが、\(\mathbb F_2\) では \(-=+\)。

\(x+y+1=0\) より \((x,y)=(0,1),(1,0)\)。\(xy=0\) は両方を許す。

2 解。

係数体が変わると同じ式でも意味が変わる。SAT/符号理論では体の選択が重要。

\(H e=s\) を \(\mathbb F_2\) で解く。

各ビット \(e_i^2-e_i=0\) と線形方程式。

線形方程式だけなら GB は行基本変形後の形に一致する。重み最小性を加えるには追加の探索基準が必要。

誤り候補の空間を代数的に列挙できる。

GB は syndrome 制約の解空間を正規形で表し、重み条件は別の目的関数探索として扱う。

リンク長 \(l_1,l_2\)、角度の cos/sin を使って手先 \((X,Y)\) を表す。

\(c_i^2+s_i^2-1=0\)、\(X=l_1c_1+l_2(c_1c_2-s_1s_2)\)、\(Y=l_1s_1+l_2(s_1c_2+c_1s_2)\)。

\(c_2\) について消去すると \(c_2=(X^2+Y^2-l_1^2-l_2^2)/(2l_1l_2)\) が現れる。

\(|c_2|\le1\) が実解条件になる。

消去は幾何的な到達可能条件を抽出する。

更新 \(x^{\prime}=x+1, y^{\prime}=y+2x+1\) が \(y=x^2\) を保つか。

\(x^{\prime}-x-1=0, y^{\prime}-y-2x-1=0, y-x^2=0\)。不変式候補は \(y^{\prime}-(x^{\prime})^2\)。

候補を制約で割ると正規形 0。

\(y=x^2\) なら更新後も \(y^{\prime}=(x^{\prime})^2\)。

到達可能状態をイデアルで表し、候補不変量の所属判定を行う。

重み 2 と 3 の組合せで同じ総和を表す関係を見つける。

写像 \(u\mapsto t^2, v\mapsto t^3\)。核は \(u^3-v^2\)。

\(I_A=\langle u^3-v^2\rangle\)。

3 個の 2 重みと 2 個の 3 重みは同じ総和 6 を表す。

整数計画やマルコフ基底探索の最小例。単項式間の同値関係を binomial で表す。

行列 \(\begin{pmatrix}a&b\\c&d\end{pmatrix}\) の rank が 1 以下である条件。

全 2×2 小行列式、つまり \(ad-bc=0\)。

一つの多項式 \(ad-bc\) が基底。

rank 制約は determinantal ideal として扱える。

低ランク探索、代数統計、行列補完の入口になる。

\(I=\langle x^2\rangle\) と \(J=\langle x\rangle\) の違い。

どちらも集合としての零点は \(x=0\)。

GB はそれぞれ \(\{x^2\}\)、\(\{x\}\)。

零点集合だけなら同じだが、重複度や剰余環は違う。\(\sqrt I=J\)。

探索で「解の場所」だけを見るのか、「重複度を含む構造」も見るのかを区別する必要がある。

\(x^2+1=0\) を考える。

\(I=\langle x^2+1\rangle\subset\mathbb Q[x]\)。

\(G=\{x^2+1\}\)。

複素数上は2解、実数上は解なし。GB だけでは実解存在性を完全には判定しない。

実閉体上の探索では CAD、実根分離、実根基などの道具と組み合わせる。

grevlex で計算した GB を lex に変換したい。

零次元イデアルで標準単項式の有限基底を使う。

例 \(\langle x^2-y,xy-1\rangle\) は grevlex から lex \(\{x-y^2,y^3-1\}\) へ変換できる。

直接 lex が重いとき、まず計算しやすい順序で解いてから変換する。

探索のコスト最適化パターン。目的は lex でも、途中順序は別でよい。