【Gröbner基定义】
设多项式环 R = F [ x 1 , x 2 … x n ] R = F\left\lbrack x_{1},x_{2}\ldots x_{n} \right\rbrack R=F[x1,x2…xn]中的理想 I I I和某一单项序 < < <，当 I I I的有限子集 G G G满足 ⟨ l t ( G ) ⟩ = ⟨ l t ( I ) ⟩ \left\langle lt(G) \right\rangle = \left\langle lt(I) \right\rangle ⟨lt(G)⟩=⟨lt(I)⟩时，称 G G G为 I I I的Gröbner基。由于Gröbner基不是唯一的，全体Gröbner基记作
G B ( I ) = { G ∈ 2 I | ⟨ l t ( G ) ⟩ = ⟨ l t ( I ) ⟩ } GB(I) = \left\{ G \in 2^{I} \middle| \left\langle lt(G) \right\rangle = \left\langle lt(I) \right\rangle \right\} GB(I)={G∈2I ⟨lt(G)⟩=⟨lt(I)⟩}
其中 2 I 2^{I} 2I是集合 I I I的幂集。
【个人理解】
根据希尔伯特基定理，可以确定任何 F [ x 1 , x 2 … x n ] F\left\lbrack x_{1},x_{2}\ldots x_{n} \right\rbrack F[x1,x2…xn]上的理想 I I I都可以通过有限的多项式基生产，即 I = ⟨ g 1 , g 2 … g t ⟩ I = \left\langle g_{1},g_{2}\ldots g_{t} \right\rangle I=⟨g1,g2…gt⟩。但有一个问题比较棘手，如何 “通过有效算法” 判断某多项式是否属于该理想。Buchberger提出了Gröbner基的概念，然后通过带余除法解决了该问题。
【定理1】
设 G ∈ G B ( I ) G \in GB(I) G∈GB(I)，则对于任意 f ∈ R f \in R f∈R，存在唯一的 r ∈ R r \in R r∈R使得 f − r ∈ I f - r \in I f−r∈I，并且 r r r中无单项可被 l t ( G ) lt(G) lt(G)中元素整除，即不可被 G G G约化。
【个人理解】
该定理表明了Gröbner基的良好性质，与一般的整数除法然后取余数一样，余数的形式是唯一的，对于属于理想Gröbner基生成的理想 I I I的多项式 f f f其带余除法的 r r r一定为 0 0 0，也就是 f f f能被 G G G约化。
【 S \mathbf{S} S多项式定义】
对于非零多项式 g 、 h g、h g、h，设 α = deg g 、 β = deg h 、 x γ = l c m ( x α , x β ) \alpha = \deg g、\beta = \deg h、x^{\gamma} = lcm\left( x^{\alpha},x^{\beta} \right) α=degg、β=degh、xγ=lcm(xα,xβ)，定义 g 、 h g、h g、h的多项式为
S ( g , h ) = ( x γ l t ( g ) g − x γ l t ( h ) h ) ∈ F [ x 1 , x 2 … x n ] S(g,h) = \left( \frac{x^{\gamma}}{lt(g)}g - \frac{x^{\gamma}}{lt(h)}h \right) \in F\left\lbrack x_{1},x_{2}\ldots x_{n} \right\rbrack S(g,h)=(lt(g)xγg−lt(h)xγh)∈F[x1,x2…xn]
【引理1】
设 g 1 , g 2 … g s ∈ F [ x 1 , x 2 … x n ] 、 α 1 , α 2 … α s ∈ N n 、 c 1 , c 2 … c s ∈ F − { 0 } g_{1},g_{2}\ldots g_{s} \in F\left\lbrack x_{1},x_{2}\ldots x_{n} \right\rbrack 、\alpha_{1},\alpha_{2}\ldots\alpha_{s} \in \mathbb{N}^{n}、c_{1},c_{2}\ldots c_{s} \in F - \text{\{}0\} g1,g2…gs∈F[x1,x2…xn]、α1,α2…αs∈Nn、c1,c2…cs∈F−{0}
f = ∑ 1 ≤ i ≤ s c i x α i g i ∈ F [ x 1 , x 2 … x n ] f = \sum_{1 \leq i \leq s}^{}{c_{i}x^{\alpha_{i}}g_{i} \in F\left\lbrack x_{1},x_{2}\ldots x_{n} \right\rbrack} f=1≤i≤s∑cixαigi∈F[x1,x2…xn]
且有 δ ∈ N n \delta \in \mathbb{N}^{n} δ∈Nn使得 α i + deg g i = δ ( 1 ≤ i ≤ s ) 、 deg f < δ \alpha_{i} + \deg g_{i} = \delta\ (1 \leq i \leq s)、\deg f < \delta αi+deggi=δ (1≤i≤s)、degf<δ。该过程称为领项消去。
于是，那么 f f f也可表示为
f = ∑ 1 ≤ i < j ≤ s c i j x δ − γ i j S ( g i , g j ) f = \sum_{1 \leq i < j \leq s}^{}{c_{ij}x^{\delta - \gamma_{ij}}S\left( g_{i},g_{j} \right)} f=1≤i<j≤s∑cijxδ−γijS(gi,gj)
其中 x γ i j = l c m ( l t ( g i ) , l t ( g j ) ) x^{\gamma_{ij}} = lcm\left( lt\left( g_{i} \right),lt\left( g_{j} \right) \right) xγij=lcm(lt(gi),lt(gj))。
【证明思路】
利用数学归纳法，当 s = 2 s = 2 s=2时根据 S S S多项式定义，可知成立。
假定 s = k + 1 s = k + 1 s=k+1时成立，当 s = k + 1 s = k + 1 s=k+1时
f = ∑ 1 ≤ i ≤ k + 1 c i x α i g i = 1 k ∑ m = 1 k + 1 ∑ 1 ≤ i ≤ k i ≠ m c i x α i g i f = \sum_{1 \leq i \leq k + 1}^{}{c_{i}x^{\alpha_{i}}g_{i}} = \frac{1}{k}\sum_{m = 1}^{k + 1}{\sum_{\begin{array}{r} 1 \leq i \leq k \\ i \neq m \end{array}}^{}{c_{i}x^{\alpha_{i}}g_{i}}} f=1≤i≤k+1∑cixαigi=k1m=1∑k+11≤i≤ki=m∑cixαigi
其中 ∑ 1 ≤ i ≤ k i ≠ m c i x α i g i \sum_{\begin{array}{r} 1 \leq i \leq k \\ i \neq m \end{array}}^{}{c_{i}x^{\alpha_{i}}g_{i}} ∑1≤i≤ki=mcixαigi可以利用 s = k s = k s=k时的结论转换成 S S S多项式，然后在外层求和 ∑ m = 1 k + 1 ∗ \sum_{m = 1}^{k + 1}* ∑m=1k+1∗时再合并相同的 S S S多项式。之所以能够合并，是因为不论 m m m取多少 c i j x δ − γ i j S ( g i , g j ) c_{ij}x^{\delta - \gamma_{ij}}S\left( g_{i},g_{j} \right) cijxδ−γijS(gi,gj)的形式都是一致的。
【个人理解】
由于 deg S ( g i , g j ) < γ i j \deg{S\left( g_{i},g_{j} \right)} < \gamma_{ij} degS(gi,gj)<γij，所以 deg ( c i j x δ − γ i j S ( g i , g j ) ) < δ \deg\left( c_{ij}x^{\delta - \gamma_{ij}}S\left( g_{i},g_{j} \right) \right) < \delta deg(cijxδ−γijS(gi,gj))<δ。
引理表明， deg f < δ \deg f < \delta degf<δ时，表面可执行行领项消去操作；领项消去的过程一定也可以通过 S S S多项式方式计算求得。
另外，此时若 ( ∀ 1 ≤ i < j ≤ s ) ( S ( g i , g j ) r e m G = 0 ) (\forall 1 \leq i < j \leq s)\left( S\left( g_{i},g_{j} \right)\ rem\ G = 0 \right) (∀1≤i<j≤s)(S(gi,gj) rem G=0)，那么 S ( g i , g j ) S\left( g_{i},g_{j} \right) S(gi,gj)可由 G G G中的多项式线性组合，也就是 f \mathbf{f} f可重新表达为 G \mathbf{G} G中的多项式线性组合。此时，所有 deg ( c ∗ x ∗ g ∗ ) \deg\left( c_{*}x^{*}g_{*} \right) deg(c∗x∗g∗)被降低，也就是 deg ( c ∗ x ∗ g ∗ ) < δ \deg\left( c_{*}x^{*}g_{*} \right) < \delta deg(c∗x∗g∗)<δ。
【定理2】
G = { g 1 , g 2 … g s } ∈ G B ( G ) ⟺ ∀ ( 1 ≤ i < j ≤ s ) S ( g i , g j ) r e m G = 0 G = \left\{ g_{1},g_{2}\ldots g_{s} \right\} \in GB(G) \Longleftrightarrow \forall(1 \leq i < j \leq s)\ \ \ S\left( g_{i},g_{j} \right)\ rem\ G = 0 G={g1,g2…gs}∈GB(G)⟺∀(1≤i<j≤s) S(gi,gj) rem G=0
【证明】
易证 ⇒ \Rightarrow ⇒，下面证明 ⇐ \Leftarrow ⇐，即需要证明：若多项式 g ∈ ⟨ G ⟩ \mathbf{g \in}\left\langle \mathbf{G} \right\rangle g∈⟨G⟩，则 l t ( g ) ∈ ⟨ l t ( G ) ⟩ \mathbf{lt}\left( \mathbf{g} \right)\mathbf{\in}\left\langle \mathbf{lt}\left( \mathbf{G} \right) \right\rangle lt(g)∈⟨lt(G)⟩。
由 g ∈ ⟨ g 1 , g 2 … g s ⟩ g \in \left\langle g_{1},g_{2}\ldots g_{s} \right\rangle g∈⟨g1,g2…gs⟩得
g = ∑ 1 ≤ i ≤ s c i q i g i g = \sum_{1 \leq i \leq s}^{}{c_{i}q_{i}g_{i}} g=1≤i≤s∑ciqigi
令
f : = g f: = g f:=g
循环步骤：
考虑 f f f中的每一项，设
δ : = max ( deg q 1 g 1 , deg q 2 g 2 … deg q s g s ) \delta: = \max{(\deg{q_{1}g_{1}},\deg{q_{2}g_{2}}\ldots\deg{q_{s}g_{s}})} δ:=max(degq1g1,degq2g2…degqsgs)
f ∗ : = ∑ 1 ≤ i ≤ s deg ( q i g i ) = δ c i q i g i f^{*}: = \sum_{\begin{array}{r} 1 \leq i \leq s \\ \deg{\left( q_{i}g_{i} \right) = \delta} \end{array}}^{}{c_{i}q_{i}g_{i}} f∗:=1≤i≤sdeg(qigi)=δ∑ciqigi
若 deg f = δ \deg f = \delta degf=δ，则跳出循环步骤。
若 deg f < δ \deg f < \delta degf<δ。所以必能执行领项消去操作。根据引理1，可得 f f f能表示为
f ∗ = ∑ 1 ≤ i < j ≤ s c i j x δ − γ i j S ( g i , g j ) f^{*} = \sum_{1 \leq i < j \leq s}^{}{c_{ij}x^{\delta - \gamma_{ij}}S\left( g_{i},g_{j} \right)} f∗=1≤i<j≤s∑cijxδ−γijS(gi,gj)
因为 S ( g i , g j ) r e m G = 0 S\left( g_{i},g_{j} \right)\ rem\ G = 0 S(gi,gj) rem G=0，所以
f ∗ = f ∗ ∗ = ∑ 1 ≤ i ≤ s ∗ c i q i ∗ g i ∗ f^{*} = f^{**} = \sum_{1 \leq i \leq s^{*}}^{}{c_{i}q_{i}^{*}g_{i}^{*}} f∗=f∗∗=1≤i≤s∗∑ciqi∗gi∗
然后，进行如下赋值操作
f ≔ f − f ∗ + f ∗ ∗ f ≔ f - f^{*} + f^{**} f:=f−f∗+f∗∗
一轮循环步骤相当于对 f \mathbf{f} f的某部分 f ∗ \mathbf{f}^{\mathbf{*}} f∗进行了 S \mathbf{S} S多项式替换，即领项消去，每轮循环操作使得 deg ( q i g i ) \deg\left( q_{i}g_{i} \right) deg(qigi)都在下降。
重复进行循环步骤，直到无法再执行领项消去，此时必有 deg f = δ \deg f = \delta degf=δ，必然有 f r e m G = 0 f\ rem\ G = 0 f rem G=0，所以 l t ( f ) ∈ ⟨ l t ( ⟨ G ⟩ ) ⟩ lt(f) \in \left\langle lt\left( \left\langle G \right\rangle \right) \right\rangle lt(f)∈⟨lt(⟨G⟩)⟩。而 f = g f = g f=g，所以 l t ( g ) ∈ ⟨ l t ( G ) ⟩ lt(g) \in \left\langle lt(G) \right\rangle lt(g)∈⟨lt(G)⟩，从而 G = { g 1 , g 2 … g s } G = \left\{ g_{1},g_{2}\ldots g_{s} \right\} G={g1,g2…gs}是Gröbner基。
