在之前的博客文章中我介绍了一些多项式代数的基本概念,在这篇文章中我们将介绍Gröbner基的基本理论和计算Gröbner基的Buchberger算法;
Gröbner基的概念来源于B.Buchberger的博士论文.考虑最简单的情形, K \mathcal{K} K为域, K [ x ] \mathcal{K}[\boldsymbol{x}] K[x]是一元多项式环. J \mathcal{J} J为 K [ x ] \mathcal{K}[\boldsymbol{x}] K[x]上的理想,理想 J \mathcal{J} J中存在次数极小的多项式,因为 J \mathcal{J} J中多项式的次数构成 N N N(非负整数)的一个子集.设 A ( x ) ∈ J A(x) \in \mathcal{J} A(x)∈J是次数极小多项式,则对任意 B ( x ) ∈ J B(x) \in \mathcal{J} B(x)∈J,有 Q , R ∈ K [ X ] Q,R \in K[X] Q,R∈K[X],使得 B = Q A + R B = QA + R B=QA+R,其中 d e g ( R ) < d e g ( A ) deg(R) < deg(A) deg(R)<deg(A),必有 R = 0 R = 0 R=0,否则与 A ( x ) A(x) A(x)是次数极小的多项式矛盾.由上述分析可知, J = ⟨ A ⟩ \mathcal{J} = \langle A \rangle J=⟨A⟩,即 A A A是 J \mathcal{J} J的理想基, J \mathcal{J} J中的任何多项式都可以被 A A A约化到 0 0 0,具有这种性质的理想基称为Gröbner基.
利用上一部分提到的Dickson引理我们可以证明如下的Hilbert 基定理,并进而证明理想的升链条件;
♡ \heartsuit ♡定理2.2(Hilbert 基定理): 每个多项式理想 J ⊆ K [ x ] \mathcal{J} \subseteq \mathcal{K}[\boldsymbol{x}] J⊆K[x] 都是有限生成的,即存在 H 1 , ⋯ , H s ∈ J H_{1}, \cdots, H_{s} \in \mathcal{J} H1,⋯,Hs∈J,使得 J = ⟨ H 1 , ⋯ , H s ⟩ \mathcal{J}=\left\langle H_{1}, \cdots, H_{s}\right\rangle J=⟨H1,⋯,Hs⟩;下面的理想的升链条件常用于证明算法的终止性;
♡ \heartsuit ♡定理2.3(理想的升链条件): 设 J 1 ⊂ J 2 ⊂ ⋯ ⊆ K [ x ] \mathcal{J}_{1} \subset \mathcal{J}_{2} \subset \cdots \subseteq \mathcal{K}[x] J1⊂J2⊂⋯⊆K[x] 为理想升链,则存在正整数 N N N,使得对任意 i > N i>N i>N 都有 J i = J N \mathcal{J}_{i}=\mathcal{J}_{N} Ji=JN(即不存在无限递增的理想升链);
♡ \heartsuit ♡定理2.4: 给定项序,下列条件是等价的:
i) G \mathbb{G} G是 K [ x ] \mathcal{K}[\boldsymbol{x}] K[x] 中的 Gröbner 基; ii) 对任意非零多项式 F ∈ ⟨ G ⟩ F \in\langle\mathbb{G}\rangle F∈⟨G⟩,nform ( F , G ) = 0 (F, \mathbb{G})=0 (F,G)=0 iii) 对 K [ x ] \mathcal{K}[\boldsymbol{x}] K[x] 中的所有多项式 F 1 F_{1} F1 和 F 2 F_{2} F2:
F 1 − F 2 ∈ ⟨ G ⟩ ⟺ nform ( F 1 , G ) = nform ( F 2 , G ) F_{1}-F_{2} \in\langle\mathbb{G}\rangle \Longleftrightarrow \operatorname{nform}(F_{1}, \mathbb{G})=\operatorname{nform}(F_{2}, \mathbb{G}) F1−F2∈⟨G⟩⟺nform(F1,G)=nform(F2,G)
iv) 每个非零多项式 F ∈ ⟨ G ⟩ F \in\langle\mathbb{G}\rangle F∈⟨G⟩ 对 G \mathbb{G} G 都是可约的 v) 对每个非零多项式 F ∈ ⟨ G ⟩ F \in\langle\mathbb{G}\rangle F∈⟨G⟩,存在多项式 G ∈ G G \in \mathbb{G} G∈G 使 lt ( G ) ∣ lt ( F ) \operatorname{lt}(G) \mid \operatorname{lt}(F) lt(G)∣lt(F) vi) 对所有多项式 F ∈ K [ x ] F \in \mathcal{K}[\boldsymbol{x}] F∈K[x],
F ∈ ⟨ G ⟩ ⟺ F = ∑ G ∈ G H G G F \in\langle\mathbb{G}\rangle \Longleftrightarrow F=\sum_{G \in \mathbb{G}} H_{G} G F∈⟨G⟩⟺F=∑G∈GHGG, 而 lt ( F ) = max G ∈ G lt ( H G ) ⋅ lt ( G ) \operatorname{lt}(F)=\max _{G \in \mathbb{G}} \operatorname{lt}\left(H_{G}\right) \cdot \operatorname{lt}(G) lt(F)=maxG∈Glt(HG)⋅lt(G)
vii) ⟨ { l t ( G ) ∣ G ∈ G } ⟩ = ⟨ { lt ( F ) ∣ F ∈ ⟨ G ⟩ } ⟩ \langle\{\mathrm{lt}(G) \mid G \in \mathbb{G}\}\rangle=\langle\{\operatorname{lt}(F) \mid F \in\langle\mathbb{G}\rangle\}\rangle ⟨{lt(G)∣G∈G}⟩=⟨{lt(F)∣F∈⟨G⟩}⟩
我们将 x 1 , ⋯ , x i x_{1}, \cdots, x_{i} x1,⋯,xi 简记为 x i x_{i} xi.Gröbner 基的下述消元性质有若干应用.
♡ \heartsuit ♡定理2.5: 设 G 为 K [ x ] \mathcal{K}[\boldsymbol{x}] K[x] 中关于变元序 x 1 ≺ ⋯ ≺ x n x_{1} \prec \cdots \prec x_{n} x1≺⋯≺xn 所确定的纯字典项序的Gröbner基,那么对任意 1 ⩽ i ⩽ n 1 \leqslant i \leqslant n 1⩽i⩽n都有⟨ G ⟩ ∩ K [ x i ] = ⟨ G ∩ K [ x i ] ⟩ \langle\mathbb{G}\rangle \cap \mathcal{K}\left[\boldsymbol{x}_{i}\right]=\left\langle\mathbb{G} \cap \mathcal{K}\left[\boldsymbol{x}_{i}\right]\right\rangle ⟨G⟩∩K[xi]=⟨G∩K[xi]⟩
式中右边的理想是在 K [ x i ] \mathcal{K}\left[\boldsymbol{x}_{i}\right] K[xi] 中生成的.
对于计算Gröbner基,可以用Buchberger算法:
△ \triangle △定义2.6: K [ x ] \mathcal{K}[x] K[x] 中两个非零多项式 F F F和 G G G 的S多项式定义为spol ( F , G ) : = lc ( G ) ⋅ μ ⋅ F − lc ( F ) ⋅ ν ⋅ G \operatorname{spol}(F, G):=\operatorname{lc}(G) \cdot \mu \cdot F-\operatorname{lc}(F) \cdot \nu \cdot G spol(F,G):=lc(G)⋅μ⋅F−lc(F)⋅ν⋅G
式中 μ \mu μ 和 ν \nu ν 是使得 lt ( F ) ⋅ μ = lt ( G ) ⋅ ν = lcm ( lt ( F ) , lt ( G ) ) \operatorname{lt}(F) \cdot \mu=\operatorname{lt}(G) \cdot \nu=\operatorname{lcm}(\operatorname{lt}(F), \operatorname{lt}(G)) lt(F)⋅μ=lt(G)⋅ν=lcm(lt(F),lt(G)) 成立的项.
⋆ \star ⋆例2.7: 对例1.10中的多项式 P 1 P_{1} P1和 P 2 P_{2} P2,我们有:spol ( P 1 , P 2 ) = lc ( P 2 ) ⋅ μ 1 ⋅ P 1 − lc ( P 1 ) ⋅ μ 2 ⋅ P 2 = 2 x 1 x 3 x 4 + 2 x 3 x 4 − 5 x 1 2 x 2 x 4 − 2 x 1 x 2 x 4 + 5 x 1 2 x 2 x 3 \begin{aligned} \operatorname{spol}\left(P_{1}, P_{2}\right) &=\operatorname{lc}\left(P_{2}\right) \cdot \mu_{1} \cdot P_{1}-\operatorname{lc}\left(P_{1}\right) \cdot \mu_{2} \cdot P_{2} \\ &=2 x_{1} x_{3} x_{4}+2 x_{3} x_{4}-5 x_{1}^{2} x_{2} x_{4}-2 x_{1} x_{2} x_{4}+5 x_{1}^{2} x_{2} x_{3} \end{aligned} spol(P1,P2)=lc(P2)⋅μ1⋅P1−lc(P1)⋅μ2⋅P2=2x1x3x4+2x3x4−5x12x2x4−2x1x2x4+5x12x2x3
其中 μ 1 = x 4 , μ 2 = x 1 \mu_{1}=x_{4}, \mu_{2}=x_{1} μ1=x4,μ2=x1;
♡ \heartsuit ♡定理2.8: 多项式组 G ⊂ K [ x ] G \subset \mathcal{K}[x] G⊂K[x]是Gröbner基当且仅当: nform ( spol ( F , G ) , G ) = 0 (\operatorname{spol}(F, G), \mathbb{G})=0 (spol(F,G),G)=0 对所有 F , G ∈ G F, G \in \mathbb{G} F,G∈G 成立.定理2.8给出了 Gröbner 基的一个算法特征:多项式组 P \mathbb{P} P是否为Gröbner基可以通过考虑有限多对 P \mathbb{P} P中的多项式的S多项式来加以检验. 基干定理2.8我们可以将Buchberger算法描述如下.
□ \Box □算法2.9(GroBas): G : = GroBas ( P \mathbb{G}:= \operatorname{GroBas}(\mathbb{P} G:=GroBas(P). 任给非空有限多项式组 P ⊂ K [ x ] P \subset \mathcal{K}[\boldsymbol{x}] P⊂K[x], 本算法计算 P \mathbb{P} P的Gröbner基 G \mathbb{G} G. G1. 命 G : = P , Θ : = { { F , G } ∣ F ≠ G , F , G ∈ P } \mathbb{G}:=\mathbb{P}, \Theta:=\{\{F, G\} \mid F \neq G, F, G \in \mathbb{P}\} G:=P,Θ:={{F,G}∣F=G,F,G∈P} G2. 重复下列步骤直至 Θ = ∅ : \Theta=\varnothing: Θ=∅: G2.1. 设 { F , G } \{F, G\} {F,G} 为 Θ \Theta Θ 中的元素,且命 Θ : = Θ \ { { F , G } } \Theta:=\Theta \backslash\{\{F, G\}\} Θ:=Θ\{{F,G}} G2.2. 计算 R : = nform ( spol ( F , G ) , G ) R:=\operatorname{nform}(\operatorname{spol}(F, G), \mathbb{G}) R:=nform(spol(F,G),G) G2.3. 若 R ≠ 0 R \neq 0 R=0,则命Θ : = Θ ∪ { { R , G } ∣ G ∈ G } , G : = G ∪ { R } \Theta:=\Theta \cup\{\{R, G\} \mid G \in \mathbb{G}\}, \mathbb{G}:=\mathbb{G} \cup\{R\} Θ:=Θ∪{{R,G}∣G∈G},G:=G∪{R}
⋆ \star ⋆例2.10: 考虑环 k [ x , y ] k[x, y] k[x,y]具有grlex项序,并且令 I = ⟨ f 1 , f 2 ⟩ = I=\langle f_{1}, f_{2}\rangle= I=⟨f1,f2⟩= ( x 3 − 2 x y , x 2 y − 2 y 2 + x ) \left(x^{3}-2 x y, x^{2} y-2 y^{2}+x\right) (x3−2xy,x2y−2y2+x). 可以断言 { f 1 , f 2 } \left\{f_{1}, f_{2}\right\} {f1,f2}并非 I I I的Gröbner基,这是由于 LT ( S ( f 1 , f 2 ) ) = − x 2 ∉ ⟨ LT ( f 1 ) , LT ( f 2 ) ⟩ \operatorname{LT}\left(S\left(f_{1}, f_{2}\right)\right)=-x^{2} \notin\left\langle\operatorname{LT}\left(f_{1}\right), \operatorname{LT}\left(f_{2}\right)\right\rangle LT(S(f1,f2))=−x2∈/⟨LT(f1),LT(f2)⟩;对给定的多项式组 P \mathbb{P} P, 其 Gröbner 基不是惟一的. 譬如,对任意 F ∈ ⟨ G ⟩ F \in\langle\mathbb{G}\rangle F∈⟨G⟩, 如果 G \mathbb{G} G是 Gröbner 基，那么 G ∪ { F } \mathbb{G} \cup\{F\} G∪{F}也是Gröbner 基. 算法 GroBas 的输出通常太大,它包含很多冗余的多项式.
另一方面,Gröbner基的性质说明,重要的是它的首项理想.所有满足 ⟨ lt ( ⟨ P ⟩ ) ⟩ = ⟨ l t ( G ) ⟩ \langle\operatorname{lt}(\langle\mathbb{P}\rangle)\rangle=\langle\mathrm{lt}(\mathbb{G})\rangle ⟨lt(⟨P⟩)⟩=⟨lt(G)⟩的 G \mathbb{G} G都是 P \mathbb{P} P的Gröbner基.对 x α ∈ lt ( G ) , ⟨ P ⟩ \boldsymbol{x}^{\alpha} \in \operatorname{lt}(\mathbb{G}),\langle\mathbb{P}\rangle xα∈lt(G),⟨P⟩ 中首项是 x α \boldsymbol{x}^{\alpha} xα的多项式可以有很多,不同的选择也可以导致不同的Gröbner基;
所以我们引进了约化Grobner基,来保证给定的多项式组可以求得其唯一的约化Gröbner基.
△ \triangle △定义2.11: 称 Gröbner基 G \mathbb{G} G为约化Gröbner基,如果每个多项式 G ∈ G G \in \mathbb{G} G∈G都是首一的,且对 G / { G } \mathbb{G}/ \{G\} G/{G}是约化的.
♡ \heartsuit ♡定理2.12: 设 J \mathcal{J} J 为 K [ x ] \mathcal{K}[\boldsymbol{x}] K[x] 中的理想. 对给定项序, J \mathcal{J} J有惟一的约化Gröbner基.
我们可以将约化Buchberger算法描述如下.
□ \Box □算法2.13(RedGroBas): G ∗ : = RedGroBas ( G ) \mathbb{G}^{*}:=\operatorname{RedGroBas}(\mathbb{G}) G∗:=RedGroBas(G).给定 Gröbner 基 G ⊂ K [ x ] \mathbb{G} \subset \mathcal{K}[\boldsymbol{x}] G⊂K[x], 本算法计算 G \mathbb{G} G的约化Gröbner基 G ∗ \mathbb{G}^{*} G∗. R1. 命 P : = G , G ∗ : = ∅ \mathbb{P}:=\mathbb{G}, \mathbb{G}^{*}:=\varnothing P:=G,G∗:=∅ R2. 重复下列步骤直至 P = ∅ \mathbb{P}=\varnothing P=∅ : R2.1. 选取多项式 G ∈ P , G \in \mathbb{P}, G∈P, 且命 P : = P \ { G } . \mathbb{P}:=\mathbb{P} \backslash\{G\} . P:=P\{G}. R2.2. 若 lt ( P ) ∤ lt ( G ) \operatorname{lt}(P) \nmid \operatorname{lt}(G) lt(P)∤lt(G) 对所有 P ∈ P ∪ G ∗ P \in \mathbb{P} \cup \mathbb{G}^{*} P∈P∪G∗ 成立, 则命 G ∗ : = G ∗ ∪ { G } . \mathbb{G}^{*}:=\mathbb{G}^{*} \cup\{G\} . G∗:=G∗∪{G}. R3. 重复下列步骤直至 G ∗ \mathbb{G}^{*} G∗约化 : R3.1. 选取对 G ∗ \ { G } \mathbb{G}^{*} \backslash\{G\} G∗\{G} 可约的 G ∈ G ∗ G \in \mathbb{G}^{*} G∈G∗,且命 G ∗ : = G ∗ \ { G } \mathbb{G}^{*}:=\mathbb{G}^{*} \backslash\{G\} G∗:=G∗\{G}. R3.2. 计算 R : = R:= R:= nform ( G , G ∗ ) \left(G, \mathbb{G}^{*}\right) (G,G∗).若 R ≠ 0 , R \neq 0, R=0, 则命 G ∗ : = G ∗ ∪ { R } \mathbb{G}^{*}:=\mathbb{G}^{*} \cup\{R\} G∗:=G∗∪{R} R4. 命 G ∗ : = { G / lc ( G ) ∣ G ∈ G ∗ } \mathbb{G}^{*}:=\left\{G / \operatorname{lc}(G) \mid G \in \mathbb{G}^{*}\right\} G∗:={G/lc(G)∣G∈G∗}.
⋆ \star ⋆例2.14: 仍然考虑例2.10中的设定,那么计算得到: Gröbner基: { f 1 , f 2 , f 3 , f 4 , f 5 } = { x 3 − 2 x y , x 2 y − 2 y 2 + x , − x 2 , − 2 x y , − 2 y 2 + x } \left\{f_{1}, f_{2}, f_{3}, f_{4}, f_{5}\right\}=\left\{x^{3}-2 x y, x^{2} y-2 y^{2}+x,-x^{2},-2 x y,-2 y^{2}+x\right\} {f1,f2,f3,f4,f5}={x3−2xy,x2y−2y2+x,−x2,−2xy,−2y2+x}; 约化的Gröbner基: { x 2 , x y , y 2 − x 2 } \left\{x^{2}, x y, y^{2}-\frac{x}{2}\right\} {x2,xy,y2−2x};
(本节完)
A Tutorial on Gröbner Bases With Applications in Signals and Systems <<多项式代数>>王东明/牟晨琪(2011)ISBN: 9787040316988 Ideals, Varieties, and Algorithms (4th ed.) [Cox, Little & O’Shea 2015-06-14] 介绍一下Grobner基的概念和应用？谢谢[知乎问题回答:来自"匿名用户"]
