グレブナー基底を使った探索：演習問題と解答

lex では最初に \(x\) の指数を比べる。\(x^2z\) は \((2,0,1)\)、\(xy^5\) は \((1,5,0)\)。最初の指数で \(2>1\) なので \(x^2z>xy^5\)。

全次数はどちらも 3。差は \((2,0,1)-(1,2,0)=(1,-2,1)\)。最後に非零の成分は \(z\) 成分の \(1\)。grevlex ではこれが負の側が大きいので \(xy^2>x^2z\)。

\(x\) 指数が最大の項は \(3x^2y\)。したがって \(\mathrm{LT}(f)=3x^2y\)、\(\mathrm{LM}(f)=x^2y\)、\(\mathrm{LC}(f)=3\)。

\(x^2y\mid x^3y^4z\) は指数比較 \((2,1,0)\le(3,4,1)\) なので真。\(xy^5\mid x^3y^4z\) は \(5\le4\) が偽なので割らない。

\(\mathrm{LT}(p)=x^3\)、\(\mathrm{LT}(g)=x^2\)。係数単項式は \(x\)。よって \(p-xg=x^3+xy-x(x^2-y)=xy+xy=2xy\)。

\(x o y^2\) なので \(x^2 o y^4\)。さらに \(y^3 o1\) より \(y^4 o y\)。したがって \(p o y+y=2y\)。正規形は \(2y\)。

\(x o y^2\) より \(x^2-y o y^4-y\)。\(y^4 o y\) なので 0。正規形 0 だから属する。

\(\mathrm{LM}(f_1)=x^2\)、\(\mathrm{LM}(f_2)=xy\)、lcm は \(x^2y\)。したがって \(S=yf_1-xf_2=y(x^2-y)-x(xy-1)=x-y^2\)。

lcm\((x^2,x)=x^2\)。\(S=f_1-xg_3=(x^2-y)-x(x-y^2)=xy^2-y=y(xy-1)=yf_2\)。したがって 0 に簡約される。

lcm\((xy,x)=xy\)。\(S=f_2-y g_3=(xy-1)-y(x-y^2)=y^3-1\)。これは新規式として追加される。

2個だけなので唯一の S-ペアを見る。\(S(x-y^2,y^3-1)=y^3(x-y^2)-x(y^3-1)=x-y^5\)。\(x o y^2\) で \(y^2-y^5=y^2(1-y^3)\)、さらに \(y^3-1\) で 0。よって Buchberger 判定により GB。

両方 monic。\(x-y^2\) の非先頭項 \(y^2\) は \(y^3\) で割れない。\(y^3-1\) の非先頭項 1 は \(x\) でも \(y^3\) でも割れない。したがって被約。

消去定理より、\(G\cap K[y]=\{2y^2-1\}\) が \(I\cap K[y]\) の GB。

まず \(z^3+z-2=0\) を解く。次に各 \(z\) について \(y^2+yz+z^2+1=0\) を解く。最後に \(x=-y-z\) とする。

イデアル \(\langle x^2-a,x-b angle\)。\(x=b\) を代入して \(b^2-a=0\)。条件は \(a=b^2\)。GB は \(\{x-b,a-b^2\}\)。

\(2y^2-1=0\) より \(y=\pm1/\sqrt2\)。\(x=y\)。

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

解集合としては \(y=1\) だが重根である。平面曲線の交点では接触や重複度を示唆する。

節が偽になるのは \(x=0,y=1,z=0\)。したがって偽条件の指示積 \((1-x)y(1-z)\) を 0 にする。

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

Boolean 0/1 では \(x\oplus y=x+y-2xy\)。したがって \(z-(x+y-2xy)=0\) と Boolean 制約。

辺制約は \(x+y=1,y+z=1,x+z=1\)。最初二つから \(x=z\)。第三式で \(2x=1\)。Boolean 制約 \(x^2=x\) に \(x=1/2\) は反する。よって解なし。GB では \(1\) が出る。

\(z=0\) なら \((x,y,z)=(0,1,0)\)。\(z=1\) なら \((1,0,1)\)。

すべての解で \(y=1\)。また \(xz-x=x(z-1)=0\) なので、\(x=1\) なら \(z=1\)。

未処理の S-ペア集合。新しい基底元を追加すると、その基底元と既存基底元のペアが frontier に追加される。

GB による正規形は一意なので、同じ剰余類に属する状態は同じ正規形に落ちる。したがって重複探索を避ける canonical representation として使える。

直接の三角形化・消去には lex が適する。ただし計算が重い場合は grevlex で先に計算し、零次元なら順序変換を使う戦略もある。

どの生成元にも割られない単項式。\(1,x,y,y^2\)。

標準単項式が 4 個なので次元は 4。

新変数 \(t\) を入れて \(x^2-1=0,\ t(x-1)-1=0\)。これにより \(x=1\) は不可能になり、\(x=-1\) が残る。

\(g=0\) の解を勝手に消す可能性があるため。代数的には飽和 \(I:g^\infty\) や \(tg-1\) の導入で、割った枝が扱う解集合を明示する。

ラグランジアン \(L=x^2+y^2+\lambda(x+y-1)\)。方程式は \(2x+\lambda=0,2y+\lambda=0,x+y-1=0\)。

最初二式から \(x=y\)。制約より \(2x=1\)。したがって \(x=y=1/2\)、\(\lambda=-1\)。

前提 \(y=x^2\) の下で \(y^{\prime}=y+2x+1=x^2+2x+1=(x+1)^2=(x^{\prime})^2\)。多項式的には \(y^{\prime}-(x^{\prime})^2\) の正規形が 0。

複素数上では \(x=\pm i\) の 2 解。実数上では解なし。GB は係数体の代数閉包上の情報を主に与えるので、実解判定には追加手法が必要。

任意の先頭項の衝突は S-多項式に集約され、その全てが 0 に簡約されれば、任意のイデアル元の先頭項が \(\langle\mathrm{LT}(G) angle\) に捕捉されるから。

Dickson の補題、または多項式環が Noetherian である Hilbert 基底定理。先頭単項式イデアルの増大列が有限段で止まる。

S-多項式と簡約を繰り返すと中間係数が急激に大きくなることがある。計算時間・メモリ・式の可読性を悪化させるため、順序選択、モジュラー計算、F4/F5 などの工夫が重要になる。

lcm 条件や Buchberger の criteria により、正規形が 0 になることが事前に分かるペアを飛ばす。探索グラフでは枝刈りに相当する。

一つは one-hot 変数 \(x_{v,c}\) を使い、各頂点で \(\sum_c x_{v,c}-1=0\)、辺で \(x_{u,c}x_{v,c}=0\)。もう一つは三乗根変数 \(x_v^3-1=0\) と辺制約 \(x_u^2+x_ux_v+x_v^2=0\)。

制約から \(1=0\) が導かれるので解集合は空。探索木全体が根で閉じる、つまり全枝が矛盾することの代数的証明。

未知数をパラメータより大きく置く。例：lex \(x>y>a>b\)。すると \(G\cap K[a,b]\) にパラメータだけの条件が現れる。

単項式順序、入力多項式、各 S-ペア、各 S-多項式の正規形、新規基底元、0 簡約、最終 interreduce 結果、計算時間など。5つ以上挙げられていればよい。