多変数連立代数方程式とグレブナー基底 #

概要 #

複数の多変数多項式を等号で結んで表される連立方程式 \[ f_1(X_1,\dots,X_n)=\cdots=f_s(X_1,\dots,X_n)=0 \] を考えます． ここではこれを多変数連立代数方程式と呼ぶことにします． 逆に，このページで単に連立方程式といえば，多変数連立代数方程式を指すこととします．

多変数連立代数方程式は，1次式であれば単なる線形方程式であり，1変数であれば4次までは解の公式が存在しますが，一般の場合の解の求め方は，それらに比べて明らかではありません．

[1], [2] は，この解法を考える上で重要な概念である グレブナー基底 の有名な入門書です． 本ページでは，この分野の概観を把握するため，[1] (それとほとんど目を通せていないですが [2] も) を読み流した際の記録として，多変数連立代数方程式とグレブナー基底についての概要をまとめます．

多変数連立代数方程式を解くという観点に絞り，この分野でどのような話題があるかを概観できるものとするため，証明や詳細な議論，重要であってもその周辺の話題の紹介は省略します． [1], [2] をご参照ください．

※2025/3/1: 余りの説明が誤っていたため修正しました¹．

多項式・イデアル・アフィン多様体 #

本節では主要な概念を定義します．

多項式 #

\(k\) を体として，係数を体 \(k\) にもつ多項式を考えます．

\(\mathbb{N}\) を0以上の整数全体，つまり \(\mathbb{N}=\{0,1,\dots\}\) とします． \(\alpha\in\mathbb{N}^n\) について， \(\alpha=(\alpha_i)_{i=1,2,\dots,n}\) と表すものとします．

有限個の \(\alpha\in\mathbb{N}^n\) を除き \(a_\alpha=0\) であるような \((a_{\alpha})_{\alpha\in\mathbb{N}^n}\) ( \(\forall\alpha\in\mathbb{N}^n\,(a_\alpha\in k)\) ) が存在し， \(n\) 個の 不定元 \(X_1,\dots,X_n\notin k\) を用いて \(f\) が \[ f=\sum_{(\alpha_1,\dots,\alpha_n)\in\mathbb{N}^n}a_{(\alpha_1,\dots,\alpha_n)}\prod_{i=1}^nX_i^{\alpha_i} \] と表せるとき，この \(f\) を 多項式 といいます． 項に現れる不定元を明示して \[ f(X_1,\dots,X_n)=\sum_{(\alpha_1,\dots,\alpha_n)\in\mathbb{N}^n}a_{(\alpha_1,\dots,\alpha_n)}\prod_{i=1}^nX_i^{\alpha_i} \] と書くこともあります．

後者の表記に関連し，例えば \(g\in k[X_1,\dots,X_n]\) について， \(\alpha_1\neq0\) ならば \(a_{(\alpha_1,\dots,\alpha_n)}=0\) であるとき， \(X_1\) は \(g\) の項に現れません． それを明示するために， \(g\) の代わりに \(g(X_2,\dots,X_n)\) と書くことがあります． 付随して，このような多項式全体の集合を \(k[X_2,\dots,X_n]\) と書くこともあります．

不定元が \(X_1,\dots,X_n\) である多項式全体の集合を \(k[X_1,\dots,X_n]\) と表します． この \(k[X_1,\dots,X_n]\) は単位的可換環をなします． この事実から， \(k[X_1,\dots,X_n]\) は 多項式環 と呼ばれます．

詳細は 前ページ をご参照ください． 前ページの記号でいうと， \(K\) を有限集合として， \(|K|=n\) である場合を考えていることになります． また， \(K\) が有限集合なら，前ページで \(\mathbb{N}^{(K)}\) としていたところは \(\mathbb{N}^n\) とできます．

いくつか関連する用語を定義します．

単項式 #

\(f[X_1,\dots,X_n]\) において， \((\alpha_i)_{i=1,2,\dots,n}\in\mathbb{N}^n\) のとき， \[ \prod_{i=1}^nX_i^{\alpha_i} \] を 単項式 といいます．

\(f\in k[X_1,\dots,X_n]\) が，有限個の \(\alpha\in\mathbb{N}^n\) を除き \(a_\alpha=0\) であるような \((a_{\alpha})_{\alpha\in\mathbb{N}^n}\) によって \[ f=\sum_{(\alpha_1,\dots,\alpha_n)\in\mathbb{N}^n}a_{(\alpha_1,\dots,\alpha_n)}\prod_{i=1}^nX_i^{\alpha_i} \] と表されているとき， \[ \left.\left\{\prod_{i=1}^nX_i^{\alpha_i}\,\right|\,a_{(\alpha_1,\dots,\alpha_n)}\neq0\right\} \] の元を 多項式 \(f\) の単項式 と呼ぶことがあります．

全次数 #

\(\alpha\in\mathbb{N}^n\) に対し， \[ |\alpha|=\sum_{i=1}^n\alpha_i \] とします．

\(f\in k[X_1,\dots,X_n]\) が，有限個の \(\alpha\in\mathbb{N}^n\) を除き， \(a_\alpha=0\) であるような \((a_{\alpha})_{\alpha\in\mathbb{N}^n}\) によって \[ f=\sum_{(\alpha_1,\dots,\alpha_n)\in\mathbb{N}^n}a_{(\alpha_1,\dots,\alpha_n)}\prod_{i=1}^nX_i^{\alpha_i} \] と表されているとします． \(f\neq0\) ならば， \[ \deg f=\max\{|\alpha|\mid\alpha\in\mathbb{N}^n\wedge a_\alpha\neq0\} \] を \(f\) の 全次数 といいます．

イデアル #

\(f[X_1,\dots,X_n]\) の部分集合 \(I\) が， \[ \begin{aligned} &0\in I,\\ &\forall f,g\in I\,(f+g\in I),\\ &\forall f\in I\,\forall h\in k[X_1,\dots,X_n]\,(hf\in I) \end{aligned} \] であるとき， \(I\) は イデアル であるといいます．

イデアルは，多項式環以外でも定義される一般的な概念ですが，本ページでイデアルといえば，多項式環のイデアルを指すこととします．

\(k[X_1,\dots,X_n]\) に対するイデアル \(I\) は， \(\mathbb{Z}\) に対する \(n\mathbb{Z}=\{nx\mid x\in\mathbb{Z}\}\) を想像しておけばよいです．

\(f_1,\dots,f_s\in k[X_1,X_2,\dots,X_n]\) について， \(\langle f_1,\dots,f_s\rangle\) を， \[ \langle f_1,\dots,f_s\rangle=\left.\left\{\sum_{i=1}^sh_if_i\,\right|\,h_1,\dots,h_s\in k[X_1,\dots,X_n]\right\} \] と定めると， \(\langle f_1,\dots,f_s\rangle\) はイデアルになります． この \(\langle f_1,\dots,f_s\rangle\) を \(f_1,\dots,f_s\) により 生成されるイデアル といいます．

逆に，イデアル \(I\) に対して， \(f_1,\dots,f_s\in k[X_1,\dots,X_n]\) が存在し， \(I=\langle f_1,\dots,f_s\rangle\) となることが知られています（ヒルベルトの基底定理）． この \(f_1,\dots,f_s\) を \(I\) の 基底 といいます．

アフィン多様体 #

\(f_1,\dots,f_s\in k[X_1,\dots,X_n]\) に対し， \[ \bm{V}(f_1,\dots,f_s)=\{a\in k^n\mid \forall i\in\{1,2,\dots,s\}\,(f_i(a)=0)\} \] を \(f_1,\dots,f_s\) により定義される アフィン多様体 といいます． ただし， \(f_i(a)\,(i=1,2,\dots,s)\) は， \(f_i\) に \(a=(a_1,\dots,a_n)\in k^n\) を代入したときの値を表します． \(\bm{V}(f_1,\dots,f_s)\) は連立方程式 \[ f_i(a)=0,\quad i=1,2,\dots,s \] の解全体の集合です．

\(I\subseteq k[X_1,\dots,X_n]\) をイデアルとするとき， \[ \bm{V}(I)=\{a\in k^n\mid \forall f\in I\,(f(a)=0)\} \] とします． これは，一般には無限個の方程式 \(f=0\,(\forall f\in I)\) の共通解全体の集合です．

\(I\subseteq k[X_1,\dots,X_n]\) をイデアルとするとき， \(I=\langle f_1,\dots,f_s\rangle\) となる \(f_1,\dots,f_s\in k[X_1,\dots,X_n]\) が存在しますが，このとき \[ \bm{V}(\langle f_1,\dots,f_s\rangle)=\bm{V}(f_1,\dots,f_s) \] であることが知られています． つまり，無限個の方程式の共通解が，有限個の方程式の共通解に一致するということです．

また，これは特に \(\langle f_1,\dots,f_s\rangle=\langle g_1,\dots,g_t\rangle\) ならば， \[ \bm{V}(f_1,\dots,f_s)=\bm{V}(g_1,\dots,g_t) \] であることも示しています．

一般に，連立方程式 \(f_1=0,\dots,f_s=0\) が解きづらければ，それと等価な解きやすい方程式 \(g_1=0,\dots,g_t=0\) を解けばよいのですが，その方法として， \(f_1,\dots,f_s\) が生成するイデアル \(I=\langle f_1,\dots,f_s\rangle\) を考え，連立方程式が解きやすい \(I\) の基底 \(g_1,\dots,g_t\) を見つけてもよい，ということになります．

単項式順序 #

多項式の先頭項やアルゴリズムを述べるため，多項式の項の順序について考えます．

1変数の多項式 \(a_nX^n+a_{n-1}X^{n-1}+\cdots+a_1X+a_0\) や，1次の多変数多項式 \(a_1X_1+a_2X_2+\cdots+a_nX_n\) では，多項式の項の順序は（一意に決まらずとも）自然に考えられます．

つまり，前者であれば \[ X^n>X^{n-1}>\cdots>X>1 \] という順序を考え，後者であれば \[ X_1>X_2>\cdots>X_n \] という順序を考え，この順に項を並べるのが自然と考えられます．

一方で，一般の \(n\) 次の多変数多項式の場合，その順序は自然に決まりません． 全次数をもとに並べることにしても，例えば， \(X^2Y^2,X^3Y,XY^3\) の序列は直感的に明らかではありません．

多項式の項の順序を考えるため，単項式のどのような順序が定義できるかを考えます．

単項式全体の集合は \[ \left.\left\{\prod_{i=1}^nX_i^{\alpha_i}\,\right|\,(\alpha_1,\dots,\alpha_n)\in\mathbb{N}^n\right\} \] と書けますが，この順序を考えることは， \(\mathbb{N}^n\) 上の順序を考えることと同じことになります．

順序 #

まず，一般の集合に対する 順序 の定義を説明します．

集合 \(A\) に対し， \(R\subseteq A^2\) を 関係 といいます． \((a,b)\in R\) であることを \(aRb\) と表すとき， \[ \begin{aligned} &\forall a\in A\,(aRa),\\ &\forall a,b,c\in A\,(aRb\wedge bRc\implies aRc),\\ &\forall a,b\in A\,(aRb\wedge bRa\implies a=b),\\ \end{aligned} \] を満たすとき， \(R\) は 半順序 であるといい， \[ \begin{aligned} &\forall a\in A\,(aRa),\\ &\forall a,b,c\in A\,(aRb\wedge bRc\implies aRc),\\ &\forall a,b\in A\,(aRb\wedge bRa\implies a=b),\\ &\forall a,b\in A\,(aRb\vee bRa),\\ \end{aligned} \] を満たすとき， \(R\) は 全順序 であるといいます． このとき， \(aRb\) は \(a\le b\) と書くことがふつうです． また， \(a\le b\wedge a\neq b\) であることを \(a< b\) と表します．

順序とは半順序（または全順序）を表す言葉です．

任意の \(S\subseteq A\) に対し， \(S\neq\emptyset\) ならば，ある \(\alpha\in S\) が存在して任意の \(\beta\in S\) に対して \(\alpha\le\beta\) が成り立つとき， \(\le\) は 整列順序 であるといいます．

本ページでは，関係 \(< \) に対して \(a\le b\) を \(a< b\vee a=b\) であることとして， \(\le\) が全順序ならば， \(<\) は全順序であるということにします．

単項式順序 #

単項式に対する順序を具体的に定義します． この順序は， \(\mathbb{N}^n\) の順序に多項式環の代数構造と両立するための性質を追加で要求したものです．

\(\mathbb{N}^n\) 上の順序 \(>\) が，

1. \(>\) は \(\mathbb{N}^n\) の全順序である．
2. \(\forall\alpha,\beta,\gamma\in\mathbb{N}^n\,(\alpha>\beta\implies \alpha+\gamma>\beta+\gamma)\) .
3. \(>\) は \(\mathbb{N}^n\) の整列順序である．

を満たすとき， \(>\) は 単項式順序 であるといいます．

代表的な単項式順序に以下のものがあります．

• \(\alpha,\beta\in\mathbb{N}^n\) に対し， \(j=\min\{i\mid\alpha_i\neq\beta_i\}\) において \(\alpha_j>\beta_j\) であるとき \(\alpha>_{\mathrm{lex}}\beta\) とする（辞書式順序，lex 順序）．
• \(\alpha,\beta\in\mathbb{N}^n\) に対し， \(|\alpha|>|\beta|\) または \(|\alpha|=|\beta|\wedge\alpha>_{\mathrm{lex}}\beta\) となるとき， \(\alpha>_{\mathrm{grlex}}\beta\) とする（次数付き辞書式順序，grlex 順序）．
• \(\alpha,\beta\in\mathbb{N}^n\) に対し， \(|\alpha|>|\beta|\) または \(|\alpha|=|\beta|\wedge(j=\max\{i\mid \alpha_i\neq\beta_i\}\implies \alpha_j<\beta_j)\) となるとき， \(\alpha>_{\mathrm{grevlex}}\beta\) とする（次数付き逆辞書式順序，grevlex 順序）．

これら順序に優劣はなく，それぞれの性質から，目的にあわせて使い分けられています．

単項式順序に関連する定義 #

単項式順序 \(>\) を固定し， \(\mathbb{N}^n\) の部分集合上の \(\max\) はこの順序の意味でとることとします． つまり， \(A\subseteq\mathbb{N}^n\) について，固定した単項式順序 \(> \) に対して， \(\alpha\ge \beta\) を \(\alpha>\beta\vee\alpha=\beta\) と定め， \(\gamma=\max A\) であるとは， \(\alpha\in A\,(\gamma\ge\alpha)\) であることと定めます．

\(X=(X_1,\dots,X_n)\in k[X_1,\dots,X_n]^n\) , \(\alpha\in\mathbb{N}^n\) に対し， \[ X^{\alpha}=\prod_{i=1}^nX_i^{\alpha_i} \] と表すことにします．

\(f\in k[X_1,\dots,X_n]\) が，有限個の \(\alpha\in\mathbb{N}^n\) を除き \(a_\alpha=0\) であるような \((a_{\alpha})_{\alpha\in\mathbb{N}^n}\) によって \[ f=\sum_{(\alpha_1,\dots,\alpha_n)\in\mathbb{N}^n}a_{(\alpha_1,\dots,\alpha_n)}\prod_{i=1}^nX_i^{\alpha_i}=\sum_{\alpha\in\mathbb{N}^n}a_{\alpha}X^{\alpha} \] と表されているとします． このとき， \[ \begin{aligned} &\mathrm{multideg}\,f=\max\{\alpha\in\mathbb{N}^n\mid a_{\alpha}\neq0\},\\ &\mathrm{LC}(f)=a_{\mathrm{multideg}\,f}\in k,\\ &\mathrm{LM}(f)=X^{\mathrm{multideg}\,f}\in k[X_1,\dots,X_n],\\ &\mathrm{LT}(f)=\mathrm{LC}(f)\mathrm{LM}(f) \end{aligned} \] と定めます．

特に \(\mathrm{multideg}\,f\) を \(f\) の 多重次数， \(\mathrm{LT}(f)\) を \(f\) の 先頭項 といいます．

これで，多変数多項式に対しても項の順序を考えることができ，先頭項という概念を導入できました．

多変数多項式の割り算と余り #

\(f\in k[X_1,\dots,X_n]\) に対して， \(f_1,\dots,f_s,h_1,\dots,h_s,r\in k[X_1,\dots,X_n]\) を用いて \(f=h_1f_1+\cdots+h_sf_s+r\) と書けて， \(r=0\) であれば， \(f\in\langle f_1,\dots,f_s\rangle\) とわかります（正確にいえばこれは十分条件で必要条件ではありません）．

1変数多項式 \(f\in k[X]\) に対し， \(g\in k[X]\) を零でない多項式とすると， \(f=qg+r\) , \(r=0\) または \(\deg r<\deg g\) なる \(q,r\in k[X]\) が存在することが知られていて， \(r\) は， \(f\) を \(h\) で割った 余り と呼ばれています．

それを拡張し， \(f,f_1,\dots,f_s\in k[X_1,\dots,X_n]\) に対し， \(f\) を \((f_1,\dots,f_s)\) で割った余り という概念が作れないかを考えます．

\(k[X_1,\dots,X_n]\) の単項式順序を固定します． \(F=(f_1,\dots,f_s)\in k[X_1,\dots,X_n]^s\) とします． このとき， \(q_1,\dots,q_s,r\in k[X_1,\dots,X_n]\) が存在し，以下が成り立つことが知られています¹．

1. \(f=q_1f_1+\cdots+q_sf_s+r\) .
2. \(r\) は \(r=0\) であるか，そうでなければ \[ r=\sum_{\alpha\in\mathbb{N}^n}b_\alpha X^{\alpha} \] のとき， \(b_\alpha\not=0\) なる \(X^\alpha\) は \(\mathrm{LT}(f_1),\dots,\mathrm{LT}(f_s)\) のいずれでも割り切れない．
3. \(i=1,2,\dots,s\) について \(q_if_i\neq0\) ならば \(\mathrm{multideg}\,f\ge\mathrm{multideg}\,q_if_i\) が成り立つ．

この \(r\) は， \(f\) を \(F\) で割った 余り と呼ばれ， \(\bar{f}^F\) と表されます．

\(F=(f_1,\dots,f_s)\) の多項式の順番を入れ替えた多項式列を \(F^\sigma=(f_{\sigma(1)},f_{\sigma(2)},\dots,f_{\sigma(s)})\) と書くと，一般には， \(\bar{f}^F\neq\bar{f}^{F^\sigma}\) であることが知られています． \(q_i\,(i=1,2,\dots,s)\) に関しても同様です．

\(f\in k[X_1,\dots,X_n]\) に対して， \(f_1,\dots,f_s,h_1,\dots,h_s,r\in k[X_1,\dots,X_n]\) を用いて \(f=h_1f_1+\cdots+h_sf_s+r\) と書けて \(r\neq0\) であったとしても， \(f_1,\dots,f_s\) の順番を入れ替えると，余りが0になる場合があるので， \(r=\bar{f}^F=0\) であることは \(f\in\langle f_1,\dots,f_s\rangle\) であることの十分条件であっても必要条件ではない，ということになります．

グレブナー基底 #

\(I\) を \(k[X_1,\dots,X_n]\) の \(\{0\}\) でないイデアルとします． \(k[X_1,\dots,X_n]\) の単項式順序を固定します． ここで，イデアルに属する多項式の先頭項だけに注目したような概念として， \[ \begin{aligned} &\mathrm{LT}(I)=\{\mathrm{LT}(f)\mid f\in I-\{0\}\},\\ &\langle \mathrm{LT}(I)\rangle=\langle f\mid f\in\mathrm{LT}(I)\rangle \end{aligned} \] というものを定義します．

\(G=\{g_1,\dots,g_t\}\subseteq k[X_1,\dots,X_n]\) が \[ \langle\mathrm{LT}(g_1),\dots,\mathrm{LT}(g_t)\rangle=\langle\mathrm{LT}(I)\rangle \] を満たすとき， \(G\) は \(I\) の グレブナー基底 といいます． また， \(\langle\emptyset\rangle=\{0\}\) として， \(\emptyset\) は \(\{0\}\) のグレブナー基底であるとします． これまでの \(\langle f_1,\dots,f_s\rangle=I\) に対し，先頭項だけに注目したような定義といえます．

すべてのイデアル \(I\subseteq k[X_1,\dots,X_n]\) はグレブナー基底をもちます． また，グレブナー基底は \(I\) の基底であり， \(\bar{f}^G\) は \(G=(g_1,\dots,g_t)\) の順序を入れ替えても変わりません（一方で \(q_i\,(i=1,2,\dots,s)\) は変わります）． 一般の多項式列 \(F=(f_1,\dots,f_s)\) の場合は，多項式の順番を変えると余りが変わってしまいますが，グレブナー基底の場合は，余りに関しては順番を気にしなくてよい，ということです． また，これによって， \(G\) が \(I\) のグレブナー基底ならば， \(f\in I\) であることと \(\bar{f}^G=0\) であることが同値になります．

次に， \(G\subseteq k[X_1,\dots,X_n]\) がイデアル \(I\subseteq k[X_1,\dots,X_n]\) のグレブナー基底であるかを判定する方法があることを説明します．

\(f,g\in k[X_1,\dots,X_n]\) を零でない多項式とします． \(\mathrm{multideg}\,f=\alpha,\mathrm{multideg}\,g=\beta\) とし， \(\gamma_i=\max\{\alpha_i,\beta_i\}\,(i=1,2,\dots,n),\gamma=(\gamma_1,\dots,\gamma_n)\) とします． このとき， \[ S(f,g)=\frac{X^\gamma}{\mathrm{LT}(f)}\cdot f-\frac{X^\gamma}{\mathrm{LT}(g)}\cdot g \] を， \(f,g\) の \(S\) 多項式 といいます． この多項式は， \(f,g\) の先頭項を打ち消すように作られた多項式です．

イデアル \(I\subseteq k[X_1,\dots,X_n]\) の適当な基底 \(f_1,\dots,f_s\) はグレブナー基底になるとは限らないのですが，これはなぜかというと， \(S\) 多項式のように先頭項を打ち消してつくった多項式の先頭項が \(f_1,\dots,f_s\) の先頭項たちの線形結合で作れない場合， \(\langle\mathrm{LT}(f_1),\dots,\mathrm{LT}(f_s)\rangle\) より \(\langle\mathrm{LT}(I)\rangle\) が大きくなってしまうことがあるためです． このため， \(S\) 多項式というものを定義して，イデアル \(I\subseteq k[X_1,\dots,X_n]\) の基底がグレブナー基底であるかを解析しようということです．

実際， \(S\) 多項式を使うと， \(G\subseteq k[X_1,\dots,X_n]\) がイデアル \(I\subseteq k[X_1,\dots,X_n]\) のグレブナー基底であるかが判定できます． 具体的には， \(G=\{g_1,\dots,g_t\}\) のすべての \(i\neq j\) となる添字について， \(\overline{S(g_i,g_j)}^G=0\) であることと， \(G\) が \(I\) のグレブナー基底であることは同値です（ブッフバーガーの判定条件）．

さらに，多変数多項式の余りは有限回の手続きで求まり，ブッフバーガーの判定条件を用いると，与えられたイデアル \(I=\langle f_1,\dots,f_s\rangle\subseteq k[X_1,\dots,X_n]\) のグレブナー基底も有限回の手続きで求まることが知られています（ブッフバーガーのアルゴリズム）．

簡単にいうと，すべて \(\overline{S(g_i,g_j)}^G=0\) となればよいため，ひとまずは仮に \(G=\{f_1,\dots,f_t\}\subseteq I\) としてはじめて， \(r=\overline{S(g_i,g_j)}^G\neq0\) である \(r\in I\) が見つかったら，それをグレブナー基底候補 \(G\) に加えることを続けていく方法です． この操作でグレブナー基底が求まること，さらにその手続きが有限回で終わることが示せます．

さらに，イデアル \(I\) のグレブナー基底 \(G\) が \[ \forall p\in G\,(\mathrm{LC}(p)=1) \] であり，すべての \(p\in G\) について， \(p\) のどの単項式も \(\langle\mathrm{LT}(G-\{p\})\rangle\) に含まれないとき， \(G\) は 被約グレブナー基底 と呼ばれ， \(\{0\}\) でないイデアル \(I\) は与えられた単項式順序に対して被約グレブナー基底をもち，ただひとつに定まることがいえます． 被約グレブナー基底も，有限回の手続きで求めることができます．

消去定理 #

\(f_1,\dots,f_s\in k[X_1,\dots,X_n]\) とします． イデアル \(I=\langle f_1,\dots,f_s\rangle\) に対して， \(I_l=I\cap k[X_{l+1},\dots,X_n]\) はイデアルであり，これを \(l\) 次の 消去イデアル といいます．

ただし， \(k[X_{l+1},\dots,X_n]\subseteq k[X_1,\dots,X_n]\) とは， \(f\in k[X_1,\dots,X_n]\) を 有限個の \(\alpha\in\mathbb{N}^n\) を除き \(a_\alpha=0\) であるような \((a_{\alpha})_{\alpha\in\mathbb{N}^n}\) によって \[ f=\sum_{\alpha\in\mathbb{N}^n}a_\alpha X^\alpha \] と表すとき， \((\alpha_1,\dots,\alpha_l)\neq0\) ならば \(a_{(\alpha_1,\dots,\alpha_n)}=0\) であるもの全体の集合とします．

\(l\) 次の消去イデアル \(I_l\) の元には \(X_1,\dots,X_l\) が現れません． このことより，連立方程式 \(f_1=\cdots=f_s=0\) から \(X_1,\dots,X_l\) を消去することは， \(I\) の \(l\) 次の消去イデアル \(I_l\) の基底を求めることに相当するといえます．

では，消去イデアルとその基底をどのように求めればよいかですが，適切な単項式順序をとれば，グレブナー基底でただちに求まります． 具体的には， \(I\subseteq k[X_1,\dots,X_n]\) をイデアルとして， \(G\) が \(I\) の lex 順序 \(X_1>X_2>\cdots>X_n\) に関するグレブナー基底ならば， \(0\le l\le n\) に対し， \(G_l=G\cap k[X_{l+1},\dots,X_n]\) は \(l\) 次の消去イデアル \(I_l\) のグレブナー基底になることが知られています（消去定理）．

つまり，lex 順序に関するグレブナー基底を用いると，連立方程式から変数を消去して，変数の少ない方程式から順に解を求めることで，もとの連立方程式を解くことができると考えられます．

拡張定理 #

厳密にいえば，前節の方法で消去ができたとしても，その 部分解 が常にもとの解の一部になるとは限りません． それが実現できる条件を述べたのが 拡張定理 です． 前節の消去定理とこの拡張定理を合わせると，グレブナー基底を用いて，消去法 で多変数連立代数方程式が解ける仕組みや解けるための条件が理解できます．

例えば，1次の消去イデアルを考えて， \((a_2,\dots,a_n)\in\bm{V}(I_1)\) が求まったとします． この 部分解 をもとの方程式の完全な解に 拡張 するには， \(I=\langle g_1,\dots,g_t\rangle\) に対して， \[ \begin{aligned} &g_1(X_1,a_2,\dots,a_n)=0,\\ &g_2(X_1,a_2,\dots,a_n)=0,\\ &\cdots\\ &g_t(X_1,a_2,\dots,a_n)=0 \end{aligned} \] を満たす \(X_1=a_1\) を求めればよいですが，この共通解が常に存在するとは限らない という点が問題になります．

どのようなときに，そのような共通解が取れるかを述べたのが 拡張定理 です．

\(k\) を体とします． すべての定数でない多項式 \(f\in k[X]\) について \(f(a)=0\) を満たす \(a\in k\) が存在するとき， \(k\) は 代数的閉体 であるといいます．

拡張定理は次のとおりです． \(k\) を代数的閉体とします． イデアル \(I=\langle f_1,\dots,f_s\rangle\subseteq k[X_1,\dots,X_n]\) を考え， \(I_1\) を \(I\) の1次の消去イデアルとします． \(i=1,2,\dots,s\) に対して， \[ f_i=c_i(X_2,\dots,X_n)X_1^{N_i}+g_i(X_1,\dots,X_N) \] と表します． ただし， \(g_i\) は \(X_1\) の次数が \(N_i\) 未満であるような多項式です． ここで， \(N_i\ge 0\) で \(c_i\in k[X_2,\dots,X_n]\) は零でない多項式とします． 部分解 \((a_2,\dots,a_n)\in\bm{V}(I_1)\) があると仮定します． このとき， \((a_2,\dots,a_n)\notin\bm{V}(c_1,\dots,c_s)\) ならば \(a_1\in k\) が存在して \((a_1,\dots,a_n)\in\bm{V}(I)\) となります（拡張定理）．

ここでポイントとなる条件は \((a_2,\dots,a_n)\notin\bm{V}(c_1,\dots,c_s)\) という部分です． \((a_2,\dots,a_n)\in\bm{V}(c_1,\dots,c_s)\) ならば， \(i=1,2,\dots,s\) について \(c_i(a_2,\dots,a_n)=0\) なので，これは \((X_2,\dots,X_n)\) を \((a_2,\dots,a_n)\) に置き換えて得られる \(f_i(X_1,a_2,\dots,a_n)\in k[X_1]\,(i=1,2,\dots,s)\) において，拡張しようとしたら先頭係数が同時に消えてしまう場合 を意味します．

つまり，拡張定理は，拡張しようとしたら先頭係数が同時に消えてしまう場合に限っては，拡張がうまくいかないかもしれない ということを示しています． そうでない場合は部分解を拡張して，もとの方程式の解が得られるということになります．

まとめ #

本ページでは，[1] (それとほとんど目を通せていませんが [2] も) を読み流した際の記録として，多変数連立代数方程式とグレブナー基底についての概要をまとめました．

本ページではブッフバーガーのアルゴリズムの内容は述べていませんが，オリジナルの方法に対して，効率的に計算する方法が研究されており，例えば F4アルゴリズム，F5アルゴリズム というものが知られています [2]．

また，多変数連立代数方程式を解くという点だけに着目しましたが，グレブナー基底にまつわる話題はこれだけではありません． 詳細は [1], [2] をご参照ください．

参考文献 #

[1] D. A. Cox, J. Little, D. O’Shea（大杉英史，土屋昭善訳），グレブナー基底と代数多様体入門上 原書4版 イデアル・多様体・アルゴリズム，丸善出版，東京，2023.
[2] D. A. Cox, J. Little, D. O’Shea（大杉英史，土屋昭善訳），グレブナー基底と代数多様体入門下 原書4版 イデアル・多様体・アルゴリズム，丸善出版，東京，2023.