代数方程组求解

一些基本概念
升列
基本列
特征列与解方程

一些概念与介绍
单项式理想及一些准备定理
Gröbner基及其性质
Buchberger算法及约化Gröbner基
Buchberger算法的两个改进
Gröbner基的应用
Gröbner基和特征值法解方程组

本章名为代数方程组的求解,所以我们将从求解代数方程组的角度来引出一系列概念和算法.根据我们从解线性方程组得到的经验,我们需要发展一套消元方法,以使将方程组化为类似于三角阵的形状,这样引出两种算法.一是吴文俊院士于上世纪七十年代为实现几何定理机器证明而提出的吴方法,它不仅能进行机器证明,同时特征列是一种三角列使得它也可以用于代数方程组的求解.另外一种是Gröbner基方法,它除了将多项式组化为三角形的基可用于解方程外,还有可以进行多项式理想的计算等诸多用处.

如果只从几何证明的角度,吴方法无疑比Gröbner基要高效很多,正是如此,吴方法在几何证明领域中在世界上都是十分有名的.然而,吴方法毕竟相当于一种不完全的约化,其除法用的是伪除法,因而在解方程、多项式理想计算等方面不如Gröbner基.

另外,由高等代数学我们知道还可以利用结式的计算来进行消元,这一过程及其理论本身比较简单,因此下面我们先从介绍结式消元法开始.

结式

我们所说的结式一般都是指Sylvester结式,利用结式进行消元基于我们以前提过的一个命题(见推论3),现在重述如下:

定理1 设 $R$ 是UFD,且有非零多项式 $f,g\in R[x]$ ,则 $\gcd(f,g)$ 非平凡当且仅当 $\mathrm{res}(f,g)=0$ .

现在我们考虑一个二元多项式方程组.设 $f,g\in\mathbb{C}[x,y]=\mathbb{C}[y][x]$ ,我们可以把它们看成 $\mathbb{C}[y]$ 上关于 $x$ 的一元多项式.那么利用上面的定理,我们有 $\gcd_x(f,g)$ 非平凡当且仅当 $\mathrm{res}_x(f,g)=0$ .现在我们要求它们的公共根,不妨设 $x_0$ 是其一根,则有 $(x-x_0)|\gcd_x(f,g)$ ,故有关于 $y$ 的方程 $\mathrm{res}_x(f,g)=0.$ 由此,我们实际上进行了消元,将方程组化为一个只关于 $y$ 的方程.

事实上,我们可以将这种消元方法推广到 $n$ 个变元的情形.设变元分别为 $x_1,x_2,\ldots,x_n$ ,则我们首先可以从 $n$ 个方程中取出 $(n-1)$ 对方程,两两用结式法消去 $x_1$ ,之后得到 $(n-1)$ 个关于 $x_2,\ldots,x_n$ 的方程,再将此过程递归做下去,最终可求出方程的解.

吴方法

一些基本概念

吴方法也称为特征列方法,这原本是由J. F. Ritt 在它的关于微分代数的工作中引入, 上个世纪70年代末,吴文俊在建立几何定理机器证明时大大发展了这一领域.它同Gröbner基类似,也是一种消元方法,在几何定理证明,代数方程求解等方面均有很重要的应用.关于吴方法,可以参考[1],[2],也可见吴文俊本人的著作[3]4.3节.

下面设 $k$ 是一特征为0的域, $k[X]=k[x_1,\ldots,x_n]=R$ ,并取字典序为 $x_1<x_2<\cdots<x_n$ .

定义1 对于单项式 $t\in M$ ,记 $t$ 中含 $x_i$ 最大的下标 $i$ 为 $p$ ,定义它的类 $\cl{t}=p$ .即 $\cl{t}=p=\max\{i:x_i|t\},$ 其中非0常数的类定义为0.

定义2 对于多项式 $f\in R$ ,定义其类为 $\cl{f}=\cl{\lt{f}}$ .

定义3 定义一种全序关系 $<\subset R\times R$ ,对于 $f,g\in R$ ,称 $f<g$ 如果下列条件之一满足:

$\cl{f}<\cl{g}$ ,
$\cl{f}=\cl{g}=p>0\wedge\deg_pf<\deg_pg$ .

若 $f\not<g\wedge g\not<f$ ,则称 $f\sim g$ (级别相同).

注1 若 $f<g$ ,则 $\lt{f}<\lt{g}$ .反之则不然,例如 $f=x_1x_2^2x_3$ , $g=x_1^2x_3$ 级别相同.

注2 这样的序不仅是全序,而且是良序.

定义4 设 $\cl{f}=p>0$ ,若 $\deg_pg<\deg_pf$ ,则称 $g$ 对 $f$ 是约化的（这里与我们在之前一章所说的约化的定义不大一样）,记为 $g\red{f}$ .

注3 若 $f<g$ ,则显然 $f\red{g}$ .但当 $f\red{g}$ 时,不一定有 $f<g$ .例如 $f=x_1x_3$ , $g=x_2$ .

下面记 $\cl{f}=p>0$ ,且 $f=f_0x_p^m+f_1x_p^{m-1}+\cdots+f_m,$ $g=g_0x_p^M+g_1x_p^{M-1}+\cdots+g_M,$ 首先

定义5 $f_0\in k[x_1,x_2,\ldots,x_{p-1},x_{p+1},\ldots,x_n]$ 称为 $f$ 的初式.

当 $g$ 相对 $f$ 不约化时,即 $M>m$ ,我们可由下面定义的伪除法将其约化.

定义6 $\exists s\in\mathbb{N}$ 使得 $f_0^sg=qf+r$ ,其中 $r\red{f}$ .

升列

我们引入一系列的定义.

定义7 多项式序列 $F=\{f_1,f_2,\ldots,f_r\}$ 称为升列(ascending set),若下列条件之一满足:

$r=1$ 且 $f_1\neq 0$ ,
$r>1$ ,且 $0<\cl{f_1}<\cl{f_2}<\cdots<\cl{f_r}$ ,且 $\forall j>i$ ,有 $f_j\red{f_i}$ .

由升列的定义我们知道升列的项数 $r$ 必然不大于未定元个数 $n$ .

定义8 升列称为矛盾列,如果升列只由一个非零常数组成.矛盾列构成的多项式方程组是无解的.

定义9 设 $F$ 是升列,对多项式 $g\in R$ ,若 $\forall f\in F$ 有 $g\red{f}$ ,则称 $g$ 相对于 $F$ 是约化的,记为 $g\red{F}$ .

定义10 定义升列上的偏序关系 $\prec$ ,对于两个升列 $F=\{f_1,\ldots,f_r\}$ , $G=\{g_1,\ldots,g_s\}$ ,称 $F\succ G$ ,若下列条件之一满足:

$\exists j\le\min(r,s)$ ,使得 $f_1\sim g_1,f_2\sim g_2,\ldots,f_{j-1}\sim g_{j-1},f_j>g_j,$
$s>r$ 且 $f_1\sim g_1,\ldots,f_r\sim g_r$ .

若 $F\not\prec G\wedge G\not\prec F$ ,则称二者级别相同,记为 $F\sim G$ .

注4 若 $F\sim G$ ,显然有 $r=s\wedge f_i\sim g_i(\forall i)$ .

下面的定理很重要,是特征列方法的基础.

定理2(Ritt引理) 设 $F_1,F_2,\ldots,F_q,\cdots$ 是不增升列的序列,即 $\forall q$ ,有 $F_{q+1}\prec F_q\vee F_{q+1}\sim F_q$ ,则 $\exists q'$ , $\forall q>q'$ ,有 $F_q\sim F_{q'}$ ,即有极小升列 $F_{q'}$ .

证明记 $r_q=\#F_q$ , $f_q\in F_q$ 是每个升列中第一个多项式,则 $f_1,f_2,\ldots,f_q,\cdots$ 是一个不增列.对于良序下的不增列我们显然有 $q_1\in\mathbb{N}$ 使得 $\forall q>q_1$ 时, $f_{q_1}\sim f_q$ .

我们再考虑 $q\ge q_1$ 时 $F_q$ 中第2个多项式构成的序列 $f_{q_1}^{(1)},\ldots,f_{q}^{(1)},\cdots$ 同样的分析给出 $q_2\in\mathbb{N}$ 使得 $q\ge q_2$ 时有 $f_{q}^{(1)}\sim f_{a_2}^{(1)}$ ,由于每个升列都有 $r_q\le n$ ,我们将这个过程继续下去总会终止,于是可找到 $q'\in\mathbb{N}$ ,使得 $q\ge q'$ 时, $r_q=r_{q'}$ 且 $F_q\sim F_{q'}$ . □

推论1 对于严格下降的升列序列,其必为有限的.

基本列

设 $A$ 是一有限非零多项式的集合,其中必含有升列,我们记从中选出的升列的全体集合为 $AS(A)$ .

定义11 若 $F\in AS(A)$ 是当中的一个极小元,则称 $F$ 是 $A$ 的基本列.(basic set)

定理3 $A$ 上的基本列存在,且能在有限步内构造出来.

证明我们只需给出构造性的证明即可.设 $A_1=A$ .

先取 $f_1$ 为 $A_1$ 中的某个最小元,若 $\cl{f_1}=0$ 则 $\{f_1\}$ 已是基本列.若 $\cl{f_1}>0$ ,记 $B_1=A_1\setminus\{f_1\}$ .若 $B_1$ 中元素对 $f_1$ 均未约化,则 $\{f_1\}$ 仍然是基本列,否则记 $B_1$ 中对 $f_1$ 约化的多项式全体为 $A_2$ .

$\forall f_2\in A_2$ ,显然有 $f_2\ge f_1$ .倘若 $f_2\sim f_1$ ,则与 $f_2\red{f_1}$ 矛盾.故 $f_2>f_1$ ,由于 $f_2\red{f_1}$ ,则只能 $\cl{f_2}>\cl{f_1}$ .

再取 $f_2$ 为 $A_2$ 中的某个最小元,若 $B_2=A_2\setminus\{f_2\}$ 中元素关于 $f_2$ 都未约化,则 $\{f_1,f_2\}$ 已是基本列,否则可以构造出 $A_3\cdots$

由于 $f_1,f_2,\cdots$ 的类是严格增加的,则上述过程必能有限步终止,得到基本列. □

鉴于基本列的存在性,我们记集合 $A$ 的全体基本列的集合为 $BS(A)$ .

定理4 $A$ 是非零多项式有限集, $F=\{f_1,\ldots,f_r\}\in BS(A)$ , $\cl{f_1}>0$ ,设 $g$ 是一非零多项式,且 $g\red{f_i}(\forall f_i\in F)$ ,设 $B=A\bigcup\{g\}$ ,则 $\exists G\in BS(B),G\prec F$ .

证明若 $\cl{g}=0$ ,则 $G=\{g\}$ 满足要求.

若 $\cl{g}=p>0$ ,则 $\exists s(1\le s\le r)$ 使得 $\cl{f_{s-1}}<p\le\cl{f_s}$ ,又由于 $g\red{f_s}$ ,则 $g<f_s$ ,故 $G=\{f_1,f_2,\ldots,f_{s-1},g\}$ 满足要求.

若 $\cl{g}>\cl{f_r}$ ,则 $G=\{f_1,\ldots,f_r,g\}$ 满足要求. □

特征列与解方程

定义12 若 $g$ 对升列 $F=\{f_1,\ldots,f_r\}$ 不是约化的,设 $I_i$ 为 $f_i\in F$ 的初式,则有带余除法: $I_r^{s_r}g=Q_rf_r+R_r,\quad R_r\red{f_r},$ $I_{r-1}^{s_{r-1}}R_r=Q_{r-1}f_{r-1}+R_{r-1},\quad R_{r-1}\red{f_{r-1}},$ $\cdots$ $I_1^{s_1}R_2=Q_1f_1+R_1,\quad R_1\red{f_1}.$ 显然 $R_1$ 对 $F$ 是约化的,我们称其为 $g$ 对 $F$ 的余式,记为 $g\rem F$ .

下面给出特征列的定义:

定义13 设 $P$ 为有限非零多项式集合,称升列 $C\in AS(P)$ 为其特征列(characteristic set),如果 $C\subset\idea{P}$ 且 $\forall p\in P$ 有 $p\rem C=0$ .

算法1(求特征列的算法)

输入:非零有限多项式集合 $P$ ,

输出: $P$ 的特征列 $F$ .

$P_1=P$ , $i=1$ ,
求出 $P_i$ 的一个基本列 $F_i\in BS(P_i)$ ,
将 $P_i\setminus F_i$ 中的多项式对 $F_i$ 求余式,其非零项构成集合 $R_i$ ,
若 $R_i\neq\emptyset$ ,令 $P_{i+1}=P_i\bigcup R_i$ , $i=i+1$ ,转2步,
输出 $F_i$ .

对于上面的算法过程,设其在 $i=m$ 时终止,我们很容易有如下断言: $V(P_1)=V(P_2)=\cdots=V(P_m).$

而对于算法的终止性,由定理4可知我们得到如下的递降基本列: $F_1\succ F_2\succ\cdots$ 由于Ritt引理,我们可以断言在某一步,例如 $i=m$ 时,算法会终止,即此时会得到 $R_i=\emptyset$ .

关于特征列和多项式零点的关系,有如下的定理:

定理5 设 $F=\{f_1,f_2,\ldots,f_r\}$ 为求得的基本列,且 $f_i$ 的初式为 $I_i$ , $J=I_1I_2\cdots I_r$ ,则 $V(P)=(V(F)\setminus V(J))\bigcup V(P,I_1)\bigcup V(P,I_2)\bigcup\cdots\bigcup V(P,I_r)$ .

证明由伪除法的定义,我们知道对于多项式 $p\in P$ ,由于 $p\red{F}$ ,则存在 $q_r,\ldots,q_1$ 使得 $I_r^{s_r}\cdots I_1^{s_1}p=q_rf_r+\cdots+q_1f_1,$ 由此等式显然可以看出右边任何一项都是左边的子集,因此右 $\subset$ 左.现在 $\forall a\in V(P)$ ,若 $a\in V(J)$ ,则必有某个 $i$ 使得 $a\in V(I_i)$ ,此时易知 $a\in V(P,I_i)$ ,若 $a\not\in V(J)$ ,则 $a\in V(F)\setminus V(J)$ ,因此有左 $\subset$ 右. □

注5 若 $F$ 是矛盾列,则有 $V(P)\subset V(F)=\emptyset$ .

定理6 对于有限非零多项式集合 $P$ ,存在一系列的特征列 $F_1,F_2,\cdots$ 使得 $V(P)=\bigcup[V(F_i)\setminus V(J_i)],$ 其中 $J_i$ 为 $F_i$ 中各多项式初式之积.

证明根据前面定理,我们已有分解 $V(P)=(V(F)\setminus V(J))\bigcup(\bigcup V(P,I_i)).$

首先我们证明若 $I_i\neq 0$ ,则 $I_i\red{P}$ .由于 $I_i$ 是特征列 $F$ 中 $f_i$ 的初式,则显然有 $I_i\red{F}$ .因此 $I_i\red{P}$ .

再用递归思想,对每个不为零的 $I_i$ ,分解 $V(P,I_i)$ ,若其特征列不是矛盾列,则可得到递减的特征列序列,由定理4可知其必有限终止, $V(P)$ 可化为本定理形式. □

Gröbner基

Gröbner基是Buchberger在1965年于其博士毕业论文中提出,最初是用来解决多项式方程组的问题.其后经过发展,它在多元多项式环的理想等问题上也有重要的应用.[4]一书对此有详细介绍,另外[5],[2]对此也有介绍.

一些概念与介绍

我们主要是为了处理多元多项式而引入了Gröbner基,因此我们先给出一些记号上的说明.

设 $F$ 为一域,以 $X$ 表示 $n$ 个不定元 $x_1,x_2,\ldots,x_n$ ,则记多项式环 $R=F[X]=F[x_1,x_2,\ldots,x_n]$ ,设有 $s$ 个多项式 $f_1,\ldots,f_s\in R$ ,由它们生成的理想记作 $I=\langle f_1,f_2,\ldots,f_s\rangle=\left\{\sum_{1\le i\le s}q_if_i|q_i\in R\right\}.$

定义14 对于上面的理想 $I$ ,定义其仿射簇(The variety of $I$ )为 $V(I)=\{a=(a_1,a_2,\ldots,a_n)\in F^n|f_i(a)=0,i=1,2,\ldots,s\}.$

显然我们有 $V(f_1,f_2,\ldots,f_s)=\bigcap_{i=1}^sV(f_i)$ ,且 $\forall f\in I(f(V(I))=0)$ .

采用上面的记号, $f_1,\ldots,f_s$ 显然是 $I$ 的基,我们知道,在一元多项式环中,由于其是主理想环,我们有 $\langle f_1,\ldots,f_s\rangle=\langle\gcd(f_1,\ldots,f_s)\rangle=\langle g\rangle,$ 且对于任何一个多项式 $f$ ,将其对 $g$ 作Euclid除法得到 $f=qg+r$ ,则 $f\in\langle g\rangle\Leftrightarrow r=0$ .但对于多元情形,这些良好的性质未必成立,比如 $\langle x,y\rangle\neq F[x,y]=\langle 1\rangle=\langle\gcd(x,y)\rangle.$

对于指标 $\alpha=(\alpha_1,\alpha_2,\ldots,\alpha_n)\in\mathbb{N}^n$ ,定义 $X^{\alpha}=x_1^{\alpha_1}x_2^{\alpha_2}\cdots x_n^{\alpha_n}$ ,称为单项式(Monomial),将全体单项式集合记作 $M\subset R$ .

我们可以定义 $M$ 中的一种良序 $<$ ,使其满足与加法的和谐性,即对任何三个指标 $\alpha$ , $\beta$ , $\gamma\in\mathbb{N}^n$ ,有 $\alpha<\beta\Rightarrow\alpha+\gamma<\beta+\gamma$ .下面给出几个序的例子:

例1 $M$ 上的字典序(Lexicographic order) ${<}_{lex}$ : $\alpha{<}_{lex}\beta\Leftrightarrow\alpha-\beta$ 左边第一非零分量为负. ◇

例2 $M$ 上的分级字典序(Graded lexicographic order) ${<}_{lex1}$ : $\alpha{<}_{lex1}\beta\Leftrightarrow\|\alpha\|<\|\beta\|\vee (\|\alpha\|=\|\beta\|\wedge\alpha{<}_{lex}\beta)$ ,其中 $\|\cdot\|$ 是1-范数. ◇

例3 $M$ 上的分级逆字典序(Graded reverse lexicographic order) ${<}_{lex2}$ : $\alpha{<}_{lex2}\beta\Leftrightarrow\|\alpha\|<\|\beta\|\vee (\|\alpha\|=\|\beta\|\wedge\alpha-\beta\text{最右非零分量为零})$ . ◇

我们一般取字典序即可,就以 $<$ 来表示,在该序下,我们可以定义多项式 $f$ 的领项 $\lt{f}$ ,领项系数 $\plc{f}$ 和领项单项式 $\lm{f}$ .一个多项式次数的定义为 $\deg f=\deg \lt{f}\in\mathbb{N}^n$ .有了这些概念,我们可以像在一元多项式环中那样做带余除法,下面给出 $R$ 中带余除法的算法:

算法2(带余除法)

输入: $f,f_1,f_2,\ldots,f_s\in R$ ,

输出: $q_1,q_2,\ldots,q_s,r\in R$ 使得 $f=q_1f_1+\cdots+q_sf_s+r$ 且 $r$ 中任何单项不被 $\lt{f_1},\ldots,\lt{f_s}$ 中任何一个整除,即不可再约化.

$r=0$ , $p=f$ , $q_i=0(i=1,\ldots,s)$ ,
当 $p\neq 0$ 时,循环做下面第3步,
若存在某个 $i$ 使 $\lt{f_i}|\lt{p}$ 则 $q_i=q_i+\frac{\lt{p}}{\lt{f_i}},\quad p=p-\frac{\lt{p}}{\lt{f_i}}f_i,$ 否则 $r=r+\lt{p}$ , $p=p-\lt{p}$ ,
输出 $q_1,q_2,\ldots,q_s,r$ .

例4 考虑 $f=x^2y+xy^2+y^2$ , $f_1=xy-1$ , $f_2=y^2-1$ . ◇

解用上面的算法计算除法,我们发现,第一步只可以用 $f_1$ 来约化,得到 $f=xf_1+(xy^2+x+y^2)$ ,第二步我们可以用 $f_1$ 或 $f_2$ 来约化,简单计算我们发现若这一步用 $f_1$ 来约化,得到结果 $f=(x+y)f_1+f_2+(x+y+1),$ 反之则得到 $f=xf_1+(x+1)f_2+(2x+1),$ 我们看到,约化的顺序不同会导致结果不同,这也是多元多项式环区别于一元多项式环的性质之一.

定义15 在算法2第3步中若选取满足领项能整除 $\lt{p}$ 的最小的指标 $i$ 对应的多项式进行约化,则定义此时得到的 $r$ 为余式 $f\rem (f_1,f_2,\ldots,f_s)=r$ .

由前面约化结果的不唯一性我们知道并不能用余式是否为零来判断一个多项式是否在所考察的理想中,为了解决种种在多元多项式环中出现的问题,我们需要引入Gröbner基.

单项式理想及一些准备定理

单项理想即是指由一些单项式生成的理想,若 $A$ 是 $N^n$ 的一个子集,定义 $\idea{x^A}=\idea{\{x^{\alpha}|\alpha\in A\}}$ .

引理1 $x^{\beta}\in I\Leftrightarrow\exists\alpha\in A(x^{\alpha}|x^{\beta})$ .

引理2 设 $I$ 是一个单项理想,以下三个命题是等价的:

(1) $f\in I$ ,

(2) $f$ 中每个单项都属于理想 $I$ ,

(3) $f$ 是 $I$ 中某些多项式的 $F$ -线性组合.

证明 (1) $\Rightarrow$ (2) 设 $I=\idea{x^A}$ ,则必有 $f=\sum_{\alpha\in A}q_{\alpha}x^{\alpha}$ ,其中 $q_{\alpha}$ 是多项式.由此可知 $f$ 中每个单项必可被某个 $x^{\alpha}$ 整除.

(2) $\Rightarrow$ (3)和(3) $\Rightarrow$ (1)均显然. □

由引理第二个等价条件得到:

推论2 两个单项理想 $I_1$ , $I_2$ 相等的充要条件是它们含有相同的单项式.

定理7(Dickson引理) $\forall A\subset\mathbb{N}^n,\exists$ 有限集 $B\subset A$ 使得 $\idea{x^A}=\idea{x^B}$ .

证明为了便于证明,我们引入 $\mathbb{N}^n$ 上的偏序 $\preccurlyeq$ 满足 $\alpha\preccurlyeq\beta\Leftrightarrow\forall i\in\{1,2,\ldots,n\}(\alpha_i\le\beta_i)$ .由是我们知道 $\alpha\preccurlyeq\beta\Leftrightarrow x^{\alpha}|x^{\beta}$ .

设 $B$ 为 $A$ 的极小元集合,即 $B=\{\beta\in A|\forall\alpha\in A(\alpha\not\prec\beta)\}$ .

于是 $\forall\alpha\in A,\exists\beta\in B(\beta\preccurlyeq\alpha)$ ,如若不然,首先 $\beta\neq\alpha\Rightarrow\alpha\not\in B$ ,即 $\alpha$ 非极小元,必存在 $\beta'\in B(\beta'\prec\alpha)$ ,矛盾.因此 $\forall\alpha\in A,\exists\beta\in B(x^{\beta}|x^{\alpha})$ ,即 $x^{\alpha}\in\idea{x^B}\Rightarrow\idea{x^A}\subset\idea{x^B}$ .又 $B\subset A\Rightarrow\idea{x^B}\subset\idea{x^A}$ ,因而 $\idea{x^A}=\idea{x^B}$ .

下面我们证明 $B$ 是有限集.对于一元 $n=1$ 的情况,由于 $\preccurlyeq$ 是全序,则 $B$ 是单元集,命题显然成立.下面假设命题对于 $n-1$ 的情况也是成立的,命 $A^*=\{(\alpha_1,\alpha_2,\ldots,\alpha_{n-1}\in\mathbb{N}^{n-1}|\exists\alpha_n\in\mathbb{N},(\alpha_1,\ldots,\alpha_n)\in A\},$ 则 $A^*$ 的极小元集 $B^*$ 是有限集. $\forall\beta^*=(\beta_1,\ldots,\beta_{n-1})\in B^*$ ,我们可取 $b_{\beta^*}\in\mathbb{N}$ 使得 $(\beta^*,b_{\beta^*})\in A$ ,由于 $B^*$ 的有限性,我们可取最大值 $b=\max\{b_{\beta^*}|\beta^*\in B^*\}.$ 于是 $\forall\alpha\in A$ , $\exists\beta^*\in B^*$ 使得 $\beta^*\preccurlyeq(\alpha_1,\ldots,\alpha_{n-1})$ ,假设 $\alpha_n>b$ ,则 $(\beta^*,b_{\beta^*})\preccurlyeq(\beta^*,b)<\alpha,$ 即 $\alpha$ 不是极小元.因此 $A$ 中任一极小元 $\alpha$ 必满足 $\alpha_n\le b$ ,那么 $\#B\le (\#B^*)\times(b+1)$ 是有限的.由归纳法,本定理得证. □

引理3 $I$ 是 $R$ 中任一理想,若 $G\subset I$ 是有限集且 $\idea{\lt{G}}=\idea{\lt{I}}$ ,则 $\idea{G}=I$ .

证明设 $G={g_1,\ldots,g_t}$ ,则 $\forall f\in I$ ,由带余除法可得到 $f=q_1g_1+\cdots+q_tg_t+r,$ 其中 $r$ 不可再被 $G$ 约化.而由于 $r=f-q_1g_1-\cdots-q_tg_t\in I$ ,于是 $\lt{r}\in\lt{I}\Rightarrow\lt{r}\in\idea{\lt{G}}$ ,即 $r$ 中每个单项都在 $\idea{\lt{G}}$ 中,因此 $r=0$ ,则 $f\in\idea{G}\Rightarrow\idea{G}=I$ . □

由于任何单项理想均可有限生成,我们有下面的:

定理8(Hilbert基定理) $R$ 中任何理想 $I$ 均可有限生成.

推论3(理想升链定理) 设 $R$ 中有一理想升链 $I_1\subset I_2\subset\cdots\subset I_n\subset\cdots$ ,则存在 $n\in\mathbb{N}(\forall m>n,I_m=I_n)$ .

这可由 $I=\bigcup_{i=1}^{\infty}I_i$ 是有限生成的得到.满足这样条件的环也叫诺特环(Noetherian Domain).

Gröbner基及其性质

现在引入Gröbner基的定义:

定义16 设有多项式环 $R$ 中的理想 $I$ 和某一单项序 $<$ , $I$ 的有限子集 $G$ 当满足 $\idea{\lt{G}}=\idea{\lt{I}}$ 时,称为 $I$ 的Groenber基.

我们记理想 $I$ 的全体Gröbner基为 $GB(I)$ ,即 $GB(I)=\{G\in 2^{I}|G\text{是}I\text{的Groenber基}\}.$ Gröbner基的存在性是由Hilbert基定理和引理3保证的,它有如下的性质:

定理9 设 $G\in GB(I)$ ,则 $\exists !r\in R$ 使得 $f-r\in I$ 且 $r$ 中无单项可被 $\lt{G}$ 中元素整除,即不可被 $G$ 约化.

当考察的 $G$ 是Gröbner基时,我们也记 $f\rem G=\overline{f}^G$ 或 $\overline{f}$ .

证明存在性由带余除法算法得到,对于唯一性,可令 $f=h_1+r_1=h_2+r_2$ ,其中 $r_1$ , $r_2$ 分别是两种不同途径约化的结果.则 $r_1-r_2=h_2-h_1\in I\Rightarrow \lt{r_1-r_2}$ 可被 $\lt{G}$ 中元素整除.由 $r_1,r_2$ 的定义可知 $r_1-r-2=0$ . □

推论4 $f\in I\Leftrightarrow r=\overline{f}=f\rem G=0$ .

构造理想的Gröbner基需要一种称为S-多项式的概念,下面简要讨论之.

定义17 对于非零多项式 $g,h$ ,设 $\alpha=\deg g$ , $\beta=\deg h$ , $x^{\gamma}=\mathrm{lcm}(x^{\alpha},x^{\beta})$ ,即 $\gamma=(\max(\alpha_1,\beta_1),\ldots,\max(\alpha_n,\beta_n))$ ,则定义 $g,h$ 的S-多项式为 $S(g,h)=\left(\frac{x^{\gamma}}{\lt{g}}g-\frac{x^{\gamma}}{\lt{h}}h\right)\in R.$

引理4 设 $g_1,\ldots,g_s\in R$ , $\alpha_1,\ldots,\alpha_s\in\mathbb{N}^n$ , $c_1,\ldots,c_s\in F\setminus\{0\}$ , $f=\sum_{1\le i\le s}c_ix^{\alpha_i}g_i\in R,$ 且有 $\delta\in\mathbb{N}^n$ 使 $\alpha_i+\deg g_i=\delta(1\le i\le s)$ , $\deg f<\delta$ ,即这些多项式的和最高领项消去(Leading term cancellation).

令 $x^{\gamma_{ij}}=\mathrm{lcm}(\lm{g_i},\lm{g_j})$ ,则存在 $c_{ij}\in F$ 使得 $x^{\gamma_{ij}}|x^{\delta}$ 且 $f=\sum_{1\le i<j\le s}c_{ij}x^{\delta-\gamma_{ij}}S(g_i,g_j),$ 且 $\deg x^{\delta-\gamma_{ij}}S(g_i,g_j)<\delta,(1\le i<j\le s)$ .

证明可假定 $\plc{g_i}=1$ ,否则可将其归并入 $c_i$ 中而使定理条件形式仍不变,于是 $\lt{g_i}=\lm{g_i}=x^{\deg g_i}$ .由于 $x^{\delta}=x^{\alpha_i}\lm{g_i}=x^{\alpha_j}\lm{g_j}$ ,则有 $x^{\gamma_{ij}}|x^{\delta}$ .

由于 $S(g_i,g_j)=\frac{x^{\gamma_{ij}}}{\lt{g_i}}g_i-\frac{x^{\gamma_{ij}}}{\lt{g_j}}g_j,$ 首项消去告诉我们 $\deg S(g_i,g_j)<\gamma_{ij}$ ,因此 $\deg x^{\delta-\gamma_{ij}}S(g_i,g_j)\prec\delta$ .

不妨设 $s\ge 2$ , 则 $\begin{align*} g&=f-c_1x^{\delta-\gamma_{ij}}S(g_1,g_2)\\ &=c_1x^{\alpha_1}g_1+c_2x^{\alpha_2}g_2+\sum_{3\le i\le s}c_ix^{\alpha_i}g_i-c_1x^{\delta-\gamma_{12}}\left(\frac{x^{\gamma_{12}}}{\lt{g_1}}g_1-\frac{x^{\gamma_{12}}}{\lt{g_2}}g_2\right)\\ &=c_1(x^{\alpha_1}-x^{\delta-\deg g_1})g_1+(c_2x^{\alpha_2}+c_1x^{\delta-\deg g_2})g_2+\sum_{3\le i\le s}c_ix^{\alpha_i}g_i\\ &=(c_1+c_2)x^{\alpha_2}g_2+\sum_{3\le i\le s}c_ix^{\alpha_i}g_i, \end{align*}$ 显然 $\deg g<\delta$ ,由此时 $g$ 的形式和归纳法,我们可以证明 $f$ 可以表成定理中的形式. □

下面的定理给出了判别Gröbner基的一个充要条件:

定理10 $G=\{g_1,\ldots,g_s\}\in GB(I)\Leftrightarrow\forall(1\le i<j\le s),S(g_i,g_j)\rem G=0$ .

证明 $\Rightarrow$ . $S(g_i,g_j)\in I=\idea{G}\Rightarrow\overline{S(g_i,g_j)}=0$ .

$\Leftarrow$ .令 $f\in I\setminus\{0\}$ ,由定义需证明 $\lt{f}\in\idea{\lt{G}}$ 即可.

不妨设 $f=\sum_{1\le i\le s}q_ig_i$ , $\delta=\max\{\deg(q_ig_i)|1\le i\le s\}$ ,则显然 $\deg f\le\delta$ .倘若等号不成立,即 $\deg f<\delta$ ,定义 $f^*=\sum_{1\le i\le s,\deg(q_ig_i)=\delta}\lt{q_i}g_i,$ 它显然满足引理6的条件,可写为 $S(g_i,g_j)$ 的线性组合,因而其在 $G$ 下约化为零.由带余除法,存在 $q_i^*$ 使得 $f^*=\sum_{1\le i\le s}q_i^*g_i$ 且 $\max\{\deg(q_i^*g_i)|1\le i\le s\}\le\deg f^*<\delta$ .由 $f^*$ 的定义可知 $f-f^*=\sum_{1\le i\le s}q_i^{**}g_i$ , $\max\{\deg(q_i^{**}g_i)|1\le i\le s\}<\delta$ .于是 $f$ 也可以表示成 $f=\sum_{1\le i\le s}q_ig_i,\quad\max\{\deg(q_ig_i)|1\le i\le s\}<\delta,$ 这与 $\delta$ 的定义矛盾,故 $\deg f=\delta$ ,即 $\exists i$ 使 $\deg f=\deg(q_ig_i)$ ,因此 $\lt{f}=\sum_{1\le i\le s,\deg(q_ig_i)=\delta}\lt{q_i}\lt{g_i}\in\idea{\lt{G}}.$

证毕. □

Buchberger算法及约化Gröbner基

Buchberger提出了Gröbner基的概念并给出了计算它的方法,即下面的Buchberger算法:

算法3(Buchberger算法)

输入: $f_1,\ldots,f_s\in R$ ,

输出: $I=\idea{f_1,\ldots,f_s}$ 的一个Groenber基 $G$ .

$G=\{f_1,\ldots,f_s\}$ ,
循环作后面所有步骤,
$S=\emptyset$ ,将 $G$ 中元素编号为 $G=\{g_1,\ldots,g_t\}$ ,
对于所有的序对 $(i,j),1\le i<j\le t$ 做: $r=S(g_i,g_j)\rem G$ ,若 $r\neq 0$ 则 $S=S\bigcup\{r\}$ ,
若 $S=\emptyset$ 则输出 $G$ ,否则 $G=G\bigcup S$ .

证明(算法有效性) 我们只需证明该算法循环是可以终止的,因为终止时由定理10可知 $G$ 即是Gröbner基.因为每步循环之后我们都可以得到一个新的集合 $G$ ,我们给它们编上号,记为 $G_1\subset G_2\subset\cdots$ ,显然 $\idea{\lt{G_1}}\subset\idea{\lt{G_2}}\subset\cdots,$ 由理想升链定理, $\exists n\in\mathbb{N}$ 使得 $\forall m>n$ 有 $\idea{\lt{G_n}}=\idea{\lt{G_m}}$ ,此时 $\forall g,h\in G_n$ ,令 $r=S(g,h)\rem G_n$ ,则显然 $r=0\vee r\in G_{n+1}$ ,于是 $\lt{r}\in\idea{\lt{G_{n+1}}}=\idea{\lt{G_n}}$ ,由 $r$ 是多项式对 $G_n$ 的约化结果知道 $r=0$ ,于是算法终止. □

多项式理想的Gröbner基并不是唯一的,而且在上面的算法中 $G$ 的规模的增长是十分迅速的,因此我们要对Gröbner基作一定的优化,下面我们一步一步对其进行约化化简.

引理5 设 $G\in GB(I)$ , $g\in G$ 且 $\lt{g}\in\idea{\lt{G\setminus\{g\}}}$ ,则 $G\setminus\{g\}\in GB(I)$ .

证明 $\lt{g}\in\idea{\lt{G\setminus\{g\}}}\Rightarrow\idea{\lt{G\setminus\{g\}}}=\idea{\lt{G}}=\idea{\lt{I}}\Rightarrow G\setminus\{g\}\in GB(I)$ . □

定义18 设 $G\in GB(I)$ ,且 $\forall g\in G$ ,有 $\plc{g}=1\wedge\lt{g}\not\in\idea{\lt{G\setminus\{g\}}}$ ,则称 $G$ 是 $I$ 的极小Gröbner基(Minimal Gröbner bases),并简记为 $G\in MGB(I)$ .

定义19 设 $G\in MGB(I)$ ,若对于 $g\in G$ , $g$ 不可再被 $G\setminus\{g\}$ 约化,即 $g$ 中任何一单项均不在理想 $\idea{\lt{G\setminus\{g\}}}$ 中,则称 $g$ 关于 $G$ 是约化的.若 $\forall g\in G$ , $g$ 关于 $G$ 都是约化的,则称 $G$ 是约化Gröbner基(Reduced Gröbner bases),并简记为 $G\in RGB(I)$ (或由下面的唯一性可记为 $G=RGB(I)$ ).

定理11 每个多项式理想 $I$ 都有唯一的约化Gröbner基.

证明存在性.由引理5可将 $G$ 化为 $I$ 的极小Gröbner基,设此时 $G=\{g_1,g_2,\ldots,g_s\}$ ,然后对 $1\le i\le s$ 归纳地做 $h_i=g_i\rem\{h_1,\ldots,h_{i-1},g_{i+1},\ldots,g_s\}$ .由极小Gröbner基的条件知道 $\lt{h_i}=\lt{g_i},(1\le i\le s)$ .于是由 $h_i$ 相对于 $\{h_1,\ldots,h_{i-1},g_{i+1},\ldots,g_s\}$ 约化可知其相对于 $G_s=\{h_1,\ldots,h_s\}$ 也是约化的.

唯一性.设 $G,G^*$ 均是 $I$ 的约化Gröbner基,则 $\forall g\in\lt{G}\subset\idea{\lt{G}}=\idea{\lt{G^*}}$ , $\exists g^*\in G^*$ 使 $\lt{g^*}|\lt{g}$ ,同样地, $\exists g^{**}\in G$ 使 $\lt{g^{**}}|\lt{g^*}$ ,因此 $\lt{g^{**}}|\lt{g}$ ,由于约化Gröbner基也是极小Gröbner基,我们知道 $\lt{g}=\lt{g^{**}}=\lt{g^*}\in\lt{G^*}\Rightarrow\lt{G}\subset\lt{G^*}$ ，再由对称可证 $\lt{G}=\lt{G^*}$ .

$\forall g\in G$ ,取 $g^*\in G^*$ 使得 $\lt{g}=\lt{g^*}$ .由于 $G,G^*$ 约化,则 $g-g^*\in I$ 中任一单项式均不能被 $\lt{G\setminus\{g\}}=\lt{G^*\setminus\{g^*\}}$ 中元素约化.于是 $g-g^*=g-g^*\rem G=0\Rightarrow g=g^*\in G^*\Rightarrow G\subset G^*\Rightarrow G=G^*$ . □

Buchberger算法的两个改进

Buchberger算法复杂性膨胀得很厉害,因而需要对其作一定的优化.[4]3.3节提出了两种改进的方法.首先从算法3本身可以看到它比较啰嗦,实际上是采用下面的算法:

算法4(Buchberger算法)

输入输出同算法3,

$G=\{f_1,\ldots,f_s\}$ , $H=\{\{i,j\}|i\neq j\wedge 1\le i,j\le s\}$ ,
当 $H\neq\emptyset$ 时循环做后面两步,
任取 $h=\{i,j\}\in H$ , $H=H\setminus \{h\}$ , $r=S(f_i,f_j)\rem G$ ,
若 $r\neq 0$ 则 $f_{s+1}=r$ , $H=H\bigcup\{\{i,s+1\}|1\le i\le s\}$ , $G=G\bigcup\{f_{s+1}\}$ , $s=s+1$ ,
输出 $G$ .

注6 设 $E=\{f_1,\ldots,f_s\}$ ,如果我们要得到矩阵 $M$ 使得 $G=EM$ ,首先令 $M_s=I_{s\times s}$ ,然后在上面算法每次第4步判断成功后,设带余除法给出 $r=S(f_i,f_j)\rem G=S(f_i,f_j)-q_1f_1-\cdots-q_sf_s$ ,设 $S(f_i,f_j)=\sum_{1\le k\le s}S_kf_k$ ,其中 $S_i=x^{\gamma_{ij}}/\lt{g_i}$ , $S_j=-x^{\gamma_{ij}}/\lt{g_j}$ ,其余的 $S_k=0$ .则由 $(f_1,\ldots,f_s,r)=(f_1,\ldots,f_s)\begin{pmatrix}1 & & & &S_1-q_1\\ &1 & & &S_2-q_2\\ & &\ddots & &\vdots\\ & & &1 &S_s-q_s \end{pmatrix}=(f_1,\ldots,f_s)Q_s,$ 可知有迭代 $M_{s+1}=M_sQ_s$ ,输出最后的 $M=M_s$ 即可.

注7 产生极小Gröbner基时只要从 $M$ 中去掉相应的列,而对于约化过程,同样由带余除法得到 $q_1,\ldots,q_s$ ,乘以相应的迭代矩阵.

第一个改进

引理6 设有多项式 $f_1,\ldots,f_s$ 和 $d$ , $I=\idea{f_1,\ldots,f_s}$ , $J=\idea{f_1d,\ldots,f_sd}$ ,则 $\{f_1,\ldots,f_s\}\in GB(I)\Leftrightarrow \{f_1d,\ldots,f_sd\}\in GB(J)$ .

此引理由Gröbner基的定义 $\idea{\lt{G}}=\idea{\lt{I}}$ 可证.

引理7 设有非零多项式 $f,g$ , $I=\idea{f,g}$ , $d=\gcd(f,g)$ ,则下面两个条件等价:

(1) $\lm{f/d}$ 与 $\lm{g/d}$ 互素,

(2) $S(f,g)\rem\{f,g\}=0$ ,即 $\{f,g\}\in GB(I)$ .

证明 (1) $\Rightarrow$ (2).先设 $d=\gcd(f,g)=1$ ,且 $f=aX+f'$ , $g=bY+g'$ ,其中 $\plc{f}=a,\lm{f}=X,\lc{g}=b,\lm{g}=Y$ , $f'$ , $g'$ 是余下的部分,于是 $X=\frac{f-f'}{a},\quad Y=\frac{g-g'}{b}.$

(I)若 $f'=g'=0$ ,则 $S(f,g)=0$ ,

(II)若 $f'=0,g'\neq 0$ ,由 $\gcd(\lm{f},\lm{g})=1$ 得 $S(f,g)=\frac{1}{a}Yf-\frac{1}{b}Xg=\frac{1}{ab}(g-g')f-\frac{1}{ab}fg=-\frac{1}{ab}g'f,$ 若它能被 $g$ 约化,则由 $\lm{g}|\lm{g'f}\wedge\gcd(\lm{g},\lm{f})=1$ 知 $\lm{g}|\lm{g'}$ ,这与 $\deg g'<\deg g\wedge g'\neq 0$ 矛盾.

(III)若 $f'\neq 0,g'$ $=0$ ,这与情形(II)类似.

(IV)若 $f'\neq 0\wedge g'\neq 0$ ,此时经过计算可知 $S(f,g)=\frac{1}{ab}(f'g-g'f),$ 我们断言 $\lm{f'g}\neq\lm{g'f}$ .假设二者相等,则 $\lm{f'}\lm{g}=\lm{g'}\lm{f}$ ,由于 $\lm{f}$ 和 $\lm{g}$ 互素,我们得到 $\lm{f}|\lm{f'}$ ,矛盾.不妨设此时 $\lm{f'g}>\lm{g'f}$ ,则第一步仅可通过 $g$ 约化,其结果为 $S(f,g)\rightarrow\frac{1}{ab}[(f'-\lt{f'})g-g'f],$ 对于相反的情形如法炮制,得到第一步的约化结果仍然可进行同样的讨论,只需将其中的 $f'-\lt{f'}$ 看作 $f'$ 即可.于是这样的约化过程可一直继续,直至约化为0.

综上,我们在 $d=1$ 的情况下证明了(1) $\Rightarrow$ (2).当 $d\neq 1$ 时,我们有 $\gcd(f/d,g/d)=1$ ,于是 $S(f/d,g/d)\rem\{f/d,g/d\}=0$ ,即 $\{f/d,g/d\}$ 是Gröbner基,由引理6可知 $\{f,g\}$ 也是Gröbner基,命题得证.

(2) $\Rightarrow$ (1).(I)首先我们仍然设 $d=\gcd(f,g)=1$ ,取单项式 $D,X,Y\in M$ 满足 $\lm{f}=DX,\quad\lm{g}=DY,\quad \gcd(X,Y)=1,$ 于是 $S(f,g)=\frac{Y}{\plc{f}}f-\frac{X}{\plc{g}}g$ ,由假设 $\{f,g\}$ 是Gröbner基,我们进行带余除法可以得到多项式 $u,v$ 使得 $S(f,g)=uf+vg$ ,且 $\lm{uf},\lm{vg}\le\lm{S(f,g)}$ .整理之可得 $\left(\frac{X}{\plc{g}}+v\right)g=\left(\frac{Y}{\plc{f}}-u\right)f,$ 因此 $g|(Y/\plc{f}-u)$ ,又 $\lm{u}DX=\lm{uf}\le\lm{S(f,g)}<\lm{Yf}=\lm{Xg}=DXY\Rightarrow\lm{u}<Y,$ 则 $g|(Y/\plc{f}-u)\Rightarrow DY|Y\Rightarrow D=1$ ,亦即 $\lm{f}$ , $\lm{g}$ 互素.

(II)当 $d\neq 1$ 时,则 $\gcd(f/d,g/d)=1$ ,于是由 $\{f,g\}$ 是Gröbner基可知 $\{f/d,g/d\}$ 是Gröbner基,因而 $\lm{f/d}$ , $\lm{g/d}$ 互素. □

定理12 $S(f,g)\rem\{f,g\}=0$ 的一个充分条件是: $\gcd(\lm{f},\lm{g})=1$ .

注8 只需注意到 $\gcd(\lm{f},\lm{g})=1\Rightarrow\gcd(f,g)=1$ .

我们可以由此得到Buchberger算法的第一个修正,在计算S-多项式并约化之前由 $\lm{f},\lm{g}$ 是否互素来决定是否要计算.

第二个改进

定义20 对于多项式 $f_1,\ldots,f_s$ ,设 $f=(f_1,\ldots,f_s)\in R^s$ ,定义 $\mathrm{Syz}(E)=\{h=(h_1,\ldots,h_s)\in R^s|h\cdot f=0\}$ .

定理13 设 $c_1,\ldots,c_s\in F\setminus\{0\}$ , $X_1,\ldots,X_s\in M$ , $X_{ij}=\mathrm{lcm}(X_i,X_j)$ ,则 $\mathrm{Syz}(c_1X_1,\ldots,c_sX_s)$ 由 $\{\tau_{ij}=\frac{X_{ij}}{c_iX_i}e_i-\frac{X_{ij}}{c_jX_j}e_j\in R^s|1\le i<j\le s\}$ 生成,其中 $e_i,e_j$ 为 $R^s$ 中的自然基矢.

证明首先易验证 $\idea{\tau_{ij}}\subset\mathrm{Syz}(c_1X_1,\ldots,c_sX_s)$ .现在假设 $h=(h_1,\ldots,h_s)\in\mathrm{Syz}(c_1X_1,\ldots,c_sX_s)$ ,于是有 $h_1c_1X_1+\cdots+h_sc_sX_s=0.$ 考虑任一单项式 $X\in M$ ,则在上式中含 $X$ 的同类项合并之后为 $0$ ,因此我们可只考虑这些项,将其分离出来.可设 $h_i=c_i'X_i'$ ,其中 $c_i'=0$ 或 $X_i'X_i=X$ ,设 $c_{i_1}',\ldots,c_{i_t}'$ 是 $c_i'$ 中不为零的系数重新编号,于是有 $c_1'c_1+\cdots+c_s'c_s=c_{i_1}'c_{i_1}+\cdots+c_{i_t}'c_{i_t}=0$ ,则 $\begin{align*} h=&(h_1,\ldots,h_s)=c_{i_1}'X_{i_1}'e_{i_1}+\cdots+c_{i_t}'X_{i_t}'e_{i_t}\\ &=c_{i_1}'c_{i_1}\frac{X}{c_{i_1}X_{i_1}}e_{i_1}+\cdots+c_{i_t}'c_{i_t}\frac{X}{c_{i_t}X_{i_t}}e_{i_t}\\ &=c_{i_1}'c_{i_1}\frac{X}{X_{i_1i_2}}(\frac{X_{i_1i_2}}{c_{i_1}X_{i_1}}e_{i_1}-\frac{X_{i_1i_2}}{c_{i_2}X_{i_2}}e_{i_2})\\ &+(c_{i_1}'c_{i_1}+c_{i_2}'c_{i_2})\frac{X}{X_{i_2i_3}}(\frac{X_{i_2i_3}}{c_{i_2}X_{i_2}}e_{i_2}-\frac{X_{i_2i_3}}{C_{i_3}X_{i_3}}e_{i_3})+\cdots\\ &+(c_{i_1}'c_{i_1}+\cdots+c_{i_{t-1}}'c_{i_{t-1}})\frac{X}{X_{i_{t-1}i_t}}(\frac{X_{i_{t-1}i_t}}{c_{i_{t-1}}X_{i_{t-1}}}e_{i_{t-1}}-\frac{X_{i_{t-1}i_t}}{c_{i_t}X_{i_t}}e_{i_t})\\ &+(c_{i_1}'c_{i_1}+\cdots+c_{i_t}'c_{i_t})\frac{X}{c_{i_t}X_{i_t}}e_{i_t}. \end{align*}$

注意到上式最后一项为零,得证. □

定理14 设 $G=\{g_1,\ldots,g_s\}$ , $B\{\tau_{ij}|1\le i<j\le s\}$ 是 $\mathrm{Syz}(\lt{g_1},\ldots,\lt{g_s})$ 的生成元集,则 $G\in GB(\idea{G})\Leftrightarrow\forall h=(h_1,\ldots,h_s)\in B(h_1g_1+\cdots+h_sg_s\rem G=0)$ .

证明注意到 $\tau_{ij}\cdot(g_1,\ldots,g_s)=S(g_i,g_j)$ ,则命题显然. □

引理8 记 $X_{ij}=\mathrm{lcm}(X_i,X_j)$ , $X_{ijl}=\mathrm{lcm}(X_i,X_j,X_l)$ ,则 $\frac{X_{ijl}}{X_{ij}}\tau_{ij}+\frac{X_{ijl}}{X_{jl}}\tau_{jl}+\frac{X_{ijl}}{X_{li}}\tau_{li}=0,$ 若 $X_l|X_{ij}$ ,则 $\tau_{ij}$ 在 $\tau_{jl}$ 和 $t_{li}$ 生成的 $R^s$ 的子模中.

注9 等式可以由 $\tau_{ij}$ 的定义式直接验证,对于第二个断言利用 $X_l|X_{ij}$ 时 $X_{ijl}=X_{ij}$ 代入等式直接得.

推论5 设 $B\subset\{\tau_{ij}|1\le i<j\le s\}$ 是 $\mathrm{Syz}(c_1X_1,\ldots,x_sX_s)$ 的生成元集,若 $\exists i,j,l$ 使 $\tau_{ij},\tau_{jl},\tau_{li}\in B$ ,且 $X_l|X_{ij}$ ,则 $B\setminus\{\tau_{ij}\}$ 也是 $\mathrm{Syz}(c_1X_1,\ldots,c_sX_s)$ 的生成元集.

由此推论我们可以得到Buchberger算法的第二个改进,即某些S-多项式可能是其它两个S-多项式的线性组合,可以不予计算.这一步,能够显著提高Buchberger算法的效率.

改进后的算法

算法5(改进Buchberger算法)

输入:多项式 $f_1,\ldots,f_s$ ,

输出:理想 $\idea{f_1,\ldots,f_s}$ 的Gröbner基 $G$ .

$G=\{f_1,\ldots,f_s\}$ , $C=\emptyset$ , $NC=\{\{1,2\}\}$ , $i=2$ ,
当 $i<s$ 时,循环做: $NC=NC\bigcup\{\{j,i+1\}|1\le j\le i\}$ , $NC=\mathrm{crit}(NC,C,i+1)$ , $i=i+1$ ,
当 $NC\neq\emptyset$ 时,循环做后面所有步骤,否则输出 $G$ 退出,
任选 $\{i,j\}\in NC$ ,令 $NC=NC\setminus\{\{i,j\}\}$ , $C=C\bigcup\{\{i,j\}\}$ ,
若 $\gcd(\lm{f_i},\lm{f_j})\neq 1$ ,则做下面6、7步,
$r=S(f_i,f_j)\rem G$ ,
若 $r\neq 0$ 则 $f_{s+1}=r,G=G\bigcup\{f_{s+1}\}$ , $s=s+1$ , $NC=NC\bigcup\{\{i,s\}|1\le i\le s-1\}$ , $NC=\mathrm{crit}(NC,C,s)$ .

上面算法中 $\mathrm{crit}$ 函数是第二个改进判别法,由下面算法给出,其中的 $X_i=\lm{f_i}$ :

算法6(crit函数)

$\mathrm{crit}(NC,C,s)$ ,输出简化后的 $NC$ .

$l=1$ ,
当 $l<s$ 时循环做下面3-7步,否则转8步,
若 $\{l,s\}\in NC$ 则令 $i=1$ 并做下面4-6步,否则转7步,
当 $i<s$ 时循环做下面5,6步,否则转7步,
若 $\{i,l\}\in NC\bigcup\wedge \{i,s\}\in NC$ 则看 $X_l|\mathrm{lcm}(X_i,X_s)$ 是否成立,是则令 $NC=NC\setminus\{\{i,s\}\}$ ,
$i=i+1$ ,
$l=l+1$ ,
$i=1$ ,
若 $i<s$ 则做下面10-14步,否则转15步,
若 $\{i,s\}\in NC$ 则令 $j=i+1$ 并做下面11-13步,否则转14步,
当 $j<s$ 时做下面12,13步,否则转14步,
若 $\{j,s\}\in NC\wedge\{i,j\}\in NC$ 则看 $X_s|\mathrm{lcm}(X_i,X_j)$ 是否成立,是则令 $NC=NC\setminus\{\{i,j\}\}$ ,
$j=j+1$ ,
$i=i+1$ ,
输出 $NC$ .

Gröbner基的应用

一些简单的应用

现在我们可以回到本章开头所提出的一些关于多元多项式理想的问题上来了.我们要解决的第一个问题是对于任何一个多项式 $f$ ,如何判断它在不在一个已知的理想 $I=\idea{f_1,\ldots,f_s}$ 中,以及找出多项式 $v_1,\ldots,v_s$ 使得 $f=v_1f_1+\cdots+v_sf_s$ .

首先我们根据前面生成Gröbner基的算法,不仅得到了约化的Gröbner基 $G=\{g_1,\ldots,g_t\}$ ,而且可以得到变换矩阵 $M_{t\times s}$ 使得 $(g_1,\ldots,g_t)=(f_1,\ldots,f_s)M$ .我们利用除法算法可以得到多项式 $u_1,\ldots,u_t$ 满足 $f=u_1g_1+\cdots+u_tg_t$ ,于是由 $f=(g_1,\ldots,g_t) \begin{pmatrix}u_1\\ \vdots\\ u_t\end{pmatrix}=(f_1,\ldots,f_s)M\begin{pmatrix}u_1\\ \vdots\\ u_t\end{pmatrix}$ 知 $(v_1,\ldots,v_s)^T=M(u_1,\ldots,u_t)^T$ .

对于两个多项式理想是否相等的判定,也可由它们唯一的约化Gröbner基来进行.而在商环 $R/I$ 中的算术需要用到代表元,我们也可取为 $\overline{f}=f\rem G$ .下面定理给出了商环 $R/I$ 的一组基.

定理15 $\mathcal{B}=\{\overline{g}|g\in M\wedge g\not\in\idea{\lt{G}}\}$ 是 $R/I$ 在 $F$ 上的一组基.

$R/I$ 中的求逆问题.设 $f\in R/I$ ,我们既已知道了该环的基,则可设 $f^{-1}$ 为 $\mathcal{B}$ 的元素的线性组合来求解,这比较复杂.我们设 $g$ 是 $f$ 的逆,注意到 $fg-1\in I\Leftrightarrow 1\in\idea{I,f}\Leftrightarrow\idea{I,f}=R,$ 则我们可以求 $\idea{I,f}$ 的Gröbner基,看1是否在其中来确定是否存在逆.再求出 $1$ 在 $\idea{I,f}$ 中的线性表示,即 $1=v_1f_1+\cdots+v_sf_s+gf$ , $g$ 即是 $f$ 在 $R/I$ 中的逆.

Hilbert零点定理(Hilbert Nullstellensatz)及Gröbner基在解方程中的应用

现在考虑 $F$ 的某个扩域 $k\supset F(\vee k=F)$ .

定义21 $V_k(I)=\{a\in k^n|\forall f\in I(f(a)=0)\}$ .

对于 $F^n$ 中子集 $V$ ,定义理想 $I(V)=\{f\in R|f(V)=0\}$ .

定理16(弱Hilbert零点定理) $I\subset R$ , $k$ 是 $F$ 的代数闭域,则 $V_k(I)=\emptyset\Leftrightarrow I=R=F[x]$ .

定义22 定义多项式理想 $I$ 的根理想(radical)为 $\sqrt{I}=\{f\in R|\exists e\in\mathbb{N}(f^e\in I)\}$ .

显然有 $\forall k\supset F$ , $V_k(I)=V_k(\sqrt{I})$ .

定理17(强Hilbert零点定理) $I(V_k(I))=\sqrt{I}$ .

推论6 $V_k(I)=V_k(J)\Leftrightarrow\sqrt{I}=\sqrt{J}$ .

注10 强、弱Hilbert零点定理的证明见有关代数几何的书,如[6]及其中译本[7].

定理18 设 $G=\{g_1,\ldots,g_t\}\in GB(I)$ ,下面三个命题等价:

(1) $V_k(I)$ 是有限集,

(2) $\forall i\in\{1,\ldots,n\}$ , $\exists v_i\in\mathbb{N},j\in\{1,\ldots,t\}$ 使得 $\lm{g_j}=x_i^{v_i}$ ,

(3) $R/I$ 有限维.

当上面任何一个条件满足时,我们也称理想 $I$ 是零维理想(zero-dimensional).

证明 (1) $\Rightarrow$ (2).若 $V_k(I)=\emptyset$ 则 $1\in G$ ,无须证明.下面假设 $V_k(I)\neq\emptyset$ ,取某个 $i\in\{1,\ldots,n\}$ ,对于 $l=\#V_k(I)$ ,取 $a_{im}(m=1,2,\ldots,l)$ 为 $V_k(I)$ 中点的第 $i$ 个分量,取非零多项式 $f_m\in F[x_i]\subset F[x]$ 使得 $f_m(a_{im})=0$ ,令 $f=f_1\cdots f_l\in F[x_i]\subset F[x]$ ,则 $f\in I(V_k(I))=\sqrt{I}$ ,于是 $\exists e\in\mathbb{N}$ 使得 $f^e\in I$ ,则 $\lm{f^e}$ 是 $x_i$ 的幂, $G$ 中有元素 $g_j$ 满足 $g_j=x_i^{v_i}$ 为 $x_i$ 的幂.

(2) $\Rightarrow$ (3).对于 $R/I$ 的基 $\prod_{1\le i\le n}x_i^{\alpha_i}$ ,一定满足 $\alpha_i<v_i$ ,维数不超过 $\prod_{1\le i\le n}v_i$ ,因此它是有限维的.

(3) $\Rightarrow$ (1).考虑多项式集合 $\{\overline{x_i^j}|j\in\mathbb{N}\}$ ,由于在 $R/I$ 中维数有限,则它们一定线性相关,即存在 $m\in\mathbb{N}$ 使得 $\sum_{0\le j\le m}c_j\overline{x_i^j}=0$ ,亦即 $\sum_{0\le j\le m}c_jx_i^j\in I$ ,该多形式在 $F[x_i]$ 中零点有限,至多为 $m$ 个,不妨设其零点集为 $V_i$ ,于是 $V_k(I)\subset\prod_{1\le i\le n}V_i$ 是有限集. □

推论7 设 $I$ 是零维理想, $G=\{g_1,\ldots,g_t\}=RGB(I)$ ,规定的字典序为 $x_1<x_2<\cdots<x_n$ ,则 $t\ge n$ ,并可将 $g_1,\ldots,g_t\in G$ 重新编号使得 $g_i(1\le i\le n)$ 只含 $x_1,x_2,\ldots,x_i$ 且 $\lm{g_i}$ 为 $x_i$ 的幂.

例5 考虑由 $f_1=x^2+y^2+z^2-1,f_2=x+y+z,f_3=x^2-2x+y^2-2y+z^2+2z$ 生成的理想的Gröbner基. ◇

解由Buchberger算法可得其Gröbner基为 $G=\{g_1,g_2,g_3\}=\{16x^2-4x-7,4x+4y-1,4z+1\}.$

显然, $V(I)$ 是一有限集,此基的形式正如推论所说,由此我们可以由第一个一元多项式方程解出其根,代入第二个方程解出第二个变元,依次迭代下去即可解出所有的根.

方程组解的结构的一些讨论

现在为了方便起见,将所讨论的域限定为复数域 $\mathbb{C}$ ,由上一小节所讨论的内容,我们很容易推广到如下结论:

定理19 $I$ 是零维理想当且仅当 $\forall i\in\{1,\ldots,n\}$ ,消元理想 $I\bigcap\mathbb{C}[x]\neq\{0\}$ .

证明 $(\Rightarrow)$ 显然.我们只要选取相应的字典序 $x_i<x_1<\cdots<x_{i-1}<x_{i+1}<\cdots<x_n$ 即可.

$(\Leftarrow)$ .当消元理想是非平凡理想时,其是一元多项式环 $\mathbb{C}[x_i]$ 上的理想,因而是一个主理想,可设其由 $f_i$ 生成, $f_i$ 首一且 $\deg f_i=m_i$ ,则对任何单项序有 $x_i^{m_i}\in\idea{\lt{I}}=\idea{\lt{G}}$ .由此易得 $R/I$ 是 $\mathbb{C}$ 上有限维线性空间. □

注11 $f_i$ 可由满足 $\sum_{j=0}^{m_i}c_j\overline{x_i}^j=\overline{0}$ 的极小多项式得到.

定义23 记 $p_{red}$ 为多项式 $p$ 的无平方部分,即 $p_{red}:=p/\gcd(p,p')$ .

定理20 当 $p$ 是一元多项式时,有 $\sqrt{\idea{p}}=\idea{p_{red}}$ .

证明首先由 $V(p)=V(p_{red})\Rightarrow\sqrt{\idea{p}}=I(V(p_{red}))=\sqrt{\idea{p_{red}}}$ .而显然有 $\sqrt{\idea{p_{red}}}=\idea{p_{red}}$ . □

[8]P46给出了如下定理:

定理21 设 $I\subset\mathbb{C}[x_1,x_2,\ldots,x_n]$ 是一多项式理想,则有 $\sqrt{I}=I+\idea{p_{1,red},p_{2,red},\ldots,p_{n,red}},$ 其中 $p_i$ 是消元理想 $I\bigcap\mathbb{C}[x_i]$ 的唯一首一生成元,且 $p_{i,red}$ 是 $p_i$ 的无平方部分.

证明设上面等式右边的理想为 $J$ ,先证其为一根理想.我们先将诸 $p_i$ (记 $n_i=\deg p_i$ )进行 $\mathbb{C}$ 上的因子分解,得到 $p_{i,red}=\prod_{1\le j\le n_i}(x_i-a_{ij}),$ 其中由无平方部分的性质可知 $a_{i1},a_{i2},\ldots,a_{in_i}$ 互不相同.由 $p_{1,red}\in J$ 可得 $J=J+\idea{p_{1,red}}=\bigcap_{1\le j\le n_1}(J+\idea{x_1-a_{1j}}),$ 同样地对于其它 $p_{i,red}$ 可得 $J=\bigcap_{1\le j_i\le n_i,1\le i\le n}(J+\idea{x_1-a_{1j_1},x_2-a_{2j_2},\ldots,x_n-a_{nj_n}}).$ 对于每一项, $\idea{x_1-a_{1j_1},\ldots,x_n-a_{nj_n}}$ 都是极大理想,因而 $J$ 是有限个极大理想的交集,即有限个根理想的交集,仍然是根理想.

由 $J$ 的定义显然有 $I\subset J$ ,又由于 $J$ 的零点全在 $V(I)$ 中,于是 $I\subset J\subset\sqrt{I}$ ,取根理想有 $\sqrt{I}=\sqrt{J}=J$ . □

下面我们给出一个有用的引理:

引理9 设 $S=\{p_1,p_2,\ldots,p_m\}\subset\mathbb{C}^n$ 是 $m$ 个互不相同的点的集合,则存在多项式组 $g_i\in\mathbb{C}[x_1,\ldots,x_n](1\le i\le m)$ ,使得 $g_i(p_j)=\delta_{ij}$ .

证明回忆一元多项式情形下的Lagrange插值的构造方法,我们可以类似地构造.首先考虑 $p_1,p_2$ 两个点,两个点肯定有某个分量不同,不妨设 $p_{1,k}\neq p_{2,k}$ ,则定义 $g_{1,2}=\frac{x_k-p_{2,k}}{p_{1,k}-p_{2,k}},$ 其满足 $g_{1,2}(p_1)=1$ , $g_{1,2}(p_2)=0$ ,同样作出 $g_{1,j}(2\le j\le m)$ 后,取 $g_1=g_{1,2}g_{1,3}\cdots g_{1,m}$ 即可.

对于 $g_i(2\le i\le m)$ 可类似构造. □

下面的定理给出了方程组根的个数的估计([8]P47).

定理22 $I$ 是 $\mathbb{C}[X]$ 中的零维理想, $A=R/I$ ,则 $\dim A\ge\#V(I)$ ,取等号当且仅当 $I=\sqrt{I}$ .

证明设 $V(I)=\{p_1,\ldots,p_m\}$ ,其中 $m=\#V(I)$ ,考虑线性映射: $\delta\subset\mathbb{C}[X]/I\times\mathbb{C}^m:\overline{f}\mapsto(\overline{f}(p_1),\ldots,\overline{f}(p_m)).$

根据引理9设 $g_1,\ldots,g_m$ 满足 $g_i(p_j)=\delta_{ij}$ ,则 $\overline{g_i}(p_j)=\delta_{ij}$ .由于 $\forall(\lambda_1,\ldots,\lambda_m)\in\mathbb{C}^m$ , $\exists f=\sum_{1\le i\le m}\lambda_ig_i$ ,使得 $\delta(\overline{f})=(\lambda_1,\ldots,\lambda_m)$ ,因此 $\delta$ 是满射.于是 $\dim A\ge\dim\mathbb{C}^m=m=\#V(I)$ .

对于第二个等价条件,先设 $I=\sqrt{I}$ ,令 $\overline{f}\in\ker\delta$ ,则 $f(V(I))=0\Rightarrow f\in I(V(I))=\sqrt{I}=I\Rightarrow\overline{f}=0$ ,从而 $\delta$ 是单射,因而是同构, $\dim A=m$ .

若 $\dim A=m$ ,首先 $I\subset\sqrt{I}$ , $\forall f\in\sqrt{I}=I(V(I))$ ,有 $f(V(I))=0$ ,则 $\delta(\overline{f})=(0,\ldots,0)\Rightarrow\overline{f}\in\ker\delta\Rightarrow f\in I\Rightarrow I=\sqrt{I}$ . □

Gröbner基和特征值法解方程组

在用Gröbner基理论将方程组化为三角形列后,采用一步步迭代来算会引入累积误差,[8]2.4节给出了一种方法,用于求解的任何一个分量,同时也给出了求消元理想 $I\bigcap\mathbb{C}[x_i]$ 的首一生成元的快速方法.设 $A=R/I$ ,首先我们定义

定义24 线性映射 $m_f\subset A\times A$ 使得 $m_f(\overline{g})=\overline{f}\overline{g}$ ,显然 $m_f=0\Leftrightarrow\overline{f}=0$ .以后 $m_f$ 既指线性映射,也可指其在 $A$ 的某组基上的矩阵表示.

很显然可以验证这样定义的线性映射具有一定的和谐性,即 $\forall h(t)\in\mathbb{C}[t]$ ,有 $m_{h(f)}=h(m_f)$ .只需逐一验证 $m_{f+g}=m_f+m_g$ , $m_{fg}=m_fm_g$ 即可.

下面的定理给出了求解的方法:

定理23 设 $h_f$ 是 $m_f$ 的极小多项式, $\forall\lambda\in\mathbb{C}$ , $I$ 是一零维理想,则下面三个命题是等价的:

$h_f(\lambda)=0$ ,
$\lambda$ 是 $m_f$ 的特征值,
$f$ 在 $V(I)$ 上取得值 $\lambda$ ,即 $\lambda\in f(V(I))$ .

证明由高等代数知识知道1和2等价是显然的.

$2\Rightarrow 3$ .不妨设 $\lambda\not\in f(V(I))$ ,由特征值的定义知 $\exists \overline{z}\in A\setminus\{0\}$ ,使得特征方程 $\overline{f-\lambda}\overline{z}=0$ 成立.令 $V(I)=\{p_1,\ldots,p_m\}$ ,则 $f(p_i)\neq\lambda(\forall p_i\in V(I))$ .令 $g=f-\lambda$ ,有 $g(p_i)\neq 0$ ,设 $g_i(1\le i\le m)$ 满足 $g_i(p_j)=\delta_{ij}$ ,定义 $g'=\sum_{i=1}^m\frac{1}{g(p_i)}g_i,$ 则 $g'(p_i)g(p_i)=1\Rightarrow 1-g'g\in I(V(I))=\sqrt{I}\Rightarrow\exists l\in\mathbb{N}((1-g'g)^l\in I)$ .将其作二项式展开,可得 $g''$ 满足 $1-g''g\in I$ ,即 $\overline{g''}\overline{g}=1$ ,故 $\overline{f-\lambda}\overline{z}=0\Rightarrow \overline{g''}\overline{g}\overline{z}=0=\overline{z},$ 矛盾.