基及其初步应用

1、基及其初步应用引言基理论的形成,可以说是经历了几十年的时间,最早可以追溯到1927年F·ironaka于1964年在研究奇性分解时,引进了多变元多项式的除法算法.在1965年,B.Buchberger使用除法算法系统地研究了域上多变元多项式环的理想生成元问题.他的基本思想是在单项式的集合中引入保持单项式的乘法运算的全序,称为项序,以保证多项式相除后所得多项式唯一,他引入了-多项式,使得对多项式环中的任一给定的理想,从它的一组生成元出发,可计算得到一组特殊的生成元,即现在通常称之的基. 基的概念是B.Buchberger于1965年在其博士论文中提出来的,为纪念其导师W.Groebne

2、r而将这种基称之为基.利用基,许多关于理想的问题都得到了解决.因此它一出现,受到许多领域的研究人员的重视,理论方面和应用方面都得到了迅速发展.本文主要介绍有关基的一些基本内容.一 基简介（一） 预备知识设表示域上的多项式环中的全体项组成的集合.“”表示某一线序.（线序的定义见1）定义1 在中，如果线序满足：（1）,1t;（2）对每个,.则线序叫做上的单项式序.注 中单项式记为(,是元数组).我们约定变元上的序关系为. 下面给出几种常用单项式序的例子：例1字典序，简记为：lex.定义如下：在中，从左向右第一个非零分量为正数.例如 按照字典序有： 例2 分次字典序，简记为：grlex.定义如下：在

3、中，或者而从左向右第一个非零分量为正数.例如 按照分次字典序有：， 例3 分次逆字典序，简记为：grevlex.定义如下：在中，或者而中从右向左第一个非零分量为负数.例如 按照分次逆字典序有：， 几个符号说明：设，其中，I是有限集；表示中出现的所有的单项式的集合；表示中出现的所有项的集合；表示中的最大项，称的首项；表示中的最大项，称的首单项式；中的系数，称首系数.定义2 设是一个非空子集，如果：（1）;（2） ，有.则称为一个多项式理想.若有有限个多项式，作，易证，是一多项式理想，称为由生成的理想.定义3 在多项式环中,如果是由一组单项式生成的理想,则称()是单项式理想.定义4 设是一个非零理

4、想，是一给定的单项式序，由生成的理想称为的首项理想.（其中，）(二) 基的定义定义5 对于给定的单项式序，非零理想的有限子集，如果满足：，则称是的基.说明 根据定义，因为是的子集，易知因此，要证明是的基，只须证明中的每个单项式的首项可以被中的某一项整除.注意 与某个单项式序密切相关，即若是关于单项式序的基，但关于单项式序未必是基.下面给出Groebner基的几个例子：例4 设,单项式序为分次字典序,则 是的基.证明 ,则或者它们显然都可以被或整除.从而，是的基.例5 ，其中单项式序是grlex,则不是的基.证明 于是但即不是的基.说明 理想的基不唯一，例如在例4中，与都是的基.这是因为：在的基

5、中，多项式的首项系数不唯一确定，当给定了的之后，在中添加中任意多项式所得的也是的基.另外，因为理想中具有相同首项的多项式有许多，它们可以构成相同的首项理想，即使是极小基（极小基的定义在后面介绍），也不是唯一的.是不是每一个非零理想都有基呢？在定义中，也并没要求是的生成元素组成的集合，但事实上，一定生成理想.下面的定理可帮我们回答上述两个问题.定理1 固定一个单项式序，每一个非零理想都有基.更进一步，.为证明此定理，我们先给出几个定义和已证明过的命题.定义6 给定,模一步约化到，记为整除的某一项，且;设，如果存在一列指标和一列多项式，使得，则称模约化到，记为定义7 如果一个多项式模是不可约化的，

6、则称是模的范式.对每个多项式都存在一个多项式使得其中，是模不可约化的，则称是模的范式.其实，只有当中的每一项都不能被整除时，模才是不可约化的.命题1 设是一个非零理想，则一定存在有限个多项式，使得.（证明见1）.命题2 假设是一个单项式理想,则一项当且仅当存在,使得.下面来证明定理1.证明 由命题1，是有限生成的，即存在的有限子集，使得，满足基的定义，是的基.另外，设，模的范式设为，则 由范式性质知，对每个不能整除如果，则由命题2，存在某个,使得整除矛盾, 由于的任意性,.（三） 极小基前面提到了极小基的概念，这是一类特殊的基，我们来看一看极小基的一些有关性质.定义8 基称为极小的，如果对于每

7、个，而且对于任何，都有不能整除.说明 定义8中提到的基，是指它是生成的理想的基.以后若提到中的非零多项式的有限集是基，都是指这一类型的基.下面我们给出一种求极小基的方法.定理2 设是理想的基，如果，则仍是的基.实际上，从任何一组基出发，不难得到极小基.若是基，那么对任何，若存在，就将从中拿掉，然后将剩下的每个用去除，便得到了极小基.例6 经验证知是基.单项式序是“”.，仍是基，且是极小基.下面的定理告诉我们，的关于同一单项式序的极小基尽管不是唯一的，但有相同的元素个数，且适当排序后，对应多项式的首项相同，即：定理3 如果，是中理想的相对于同一单项式序的极小基，则，而且对.（如需要，可将和适当的

8、重新排序.（四）约化基前面说了，理想的基不唯一，为了讨论基的唯一性，我们引入以下定义.定义9 设是理想的基，如果满足：（1）;（2）对任意模是不可约化的. 则称是的约化基.定理4 假设是的理想，对于给定的单项式，存在唯一的约化基.（证明见1）由此可见，对于每个单项式序都有唯一的约化基.现在有两个问题，（1）的约化基是否是有限个呢？（2）是否有这样一个的子集，它对于的每一个单项式序都是的基呢？事实上有：定理5 只有有限个约化基，而且一定存在子集，它对于的每一个单项式序都是基（证明见4）二 基的判定我们知道，每一个非零理想都有基，那么，什么样的子集是的基呢？如何来判定是否是的基呢？下面我们给出几种

9、判定方法.定理1 假设是由多项式生成的主理想，（主理想定义见5），则任何包含的的有限子集都是的基.证明 设是有限子集，令，且，）则，即可以整除，是的基。例1 设，则是的基。定理2 设是的有限子集，若对每个，模的范式是唯一的，那么是基。（证明见1）实际上，上述命题的逆命题也成立，即如果是基，则对于每个，模的范式是唯一的.定理3 设单项式序是，如果是中理想的基，则也是单项式理想的基.证明 设，则，要证是的基，只需证存在某个，使得是的基即，从而，也是单项式理想的基.例2 若是的基，则是的基.定理4 假设是一个有限集合，并且，如果任取，任取单项式，满足，都有模的范式为0，则是基.定理4给出的判定是否是

10、基的方法，因为它对每对满足的单项式都要进行判定，这样的过程需要无限多步.后来，又有人给出了一种改进的方法.为介绍此方法，我们先介绍两个定义.定义1 设是两个非零多项式，如果则称的最小公倍式.记作：.例3则.定义2 设为非零多项式，取定一单项式.记作，称.例4 在上例中，计算得，于是，我们又得到下面的定理.定理5 设是的有限子集，并且，则是基的充分必要条件为模的范式为0.与定理4相比，我们的计算步骤大大简化了，只需对S-多项式去判定即可.下面我们来看一道例题.例5 的单项式序为字典序，令，求I基.解 令，有，模F约化为0，模F约化为0，模F约化为0，模F不可约化.令由上步可知，模约化为0。同理可

11、验证，模约化为0。由定理5可知，是理想的基。实际上，定理5也给出了一种计算基的方法，若对于，看是否能模约化为0。若能，则是基，若不能，方法是扩充，在上添加-多项式的范式，得到，重复上述判定，直到得到基。由定理5。我们很容易得到下列推论：推论1 设是一个有限的单项式集合，则是基。证明 设，则= 模的范式为0，由定理5知，是基。下面我们介绍一个定义，定义3 设是一个有限子集，则，其中是单项式，对于，可能相同，并且，则上述表达式称为对于的标准表示。例6，单项式序是分次字典序，则并且对于有标准表示。有了上述概念，我们再介绍一种基的判定方法。定理6 对于给定的单项式序,是有限集合，则是基如果对每个，对有

12、标准表示。（证明见1）如果我们把定义3中的条件改为，其中是一个项，则称上述表示为对于的-表示。应用-表示的定义，我们又有了一个基的判定方法。定理7 设是有限子集，并且，单项式序是，如果对于每个或者它对于有一个-表示，其中，则是基（证明见3）特别地，如果，则-表示就变成了标准表示。因此，上述定理可得到一种特殊情况推论2 设是有限子集，如果对每个或者对于有标准表示，则是基例7 ，令，单项式序是分次字典序，是基。定义7 设，如果,没有公共的变元，则称是不相交的项。此时，反之，如果有公共变元，则称是相交的项。事实上，如果是不相交的项，则对于有标准表示（证明见1），由此，根据定理7及上述结论，我们有定理

13、8 ，单项式序是，则是基对每个，如果它们的首项相交则对于有标准表示。例8 ，设，单项式序是分次字典序。由定理8，只需对进行判定，对有标准表示是基。定理8是比较容易理解的，事实上，若首项不相交，对于有标准表示，从而对也有标准表示。所以我们可以免去验证步骤。定理8的结论与定理7或推论2相比，我们只需验证首项相交的多项式对，看其是否对有标准表示，从而使问题大大简化了。以上给出的是基的8种判断方法，做题可灵活选择。三 基的性质在这部分里，我们着重介绍基所具有的几点性质。给定上的一个单项式序，是的一个理想，是的基，若设，则由基的定义可知，对则，其中。由于上式左边只有一个项，从而右边必只出现一项，能被某个

14、整除，由此得到第一个性质。性质1 各定上的一个单项式序，是的理想，是的基，则对能被某个整除（）。性质2 若是的基，则对任意的多项式，模的范式为0，从而也是的基。证明 假设模的范式，则由范式性质，是模不可约化的，设，则使得，由性质1可知，可被某个整除，与模不可约化矛盾，从而，是的基。性质3 若是的基，则对任意的多项式，设模的范式是，则由和唯一确定。（证明见8）四 基的算法有了基的定义，就要研究基的计算问题。实际上，在第二部分里，我们已经初步讨论了这个问题，通过扩充的思想来计算基是比较繁琐的，但这个过程通过计算机是可以实现的。1965年，在他的博士论文中研究了基的性质，并给出了计算基的算法算法。算

15、法1 ，理想，则下列算法可求得的基。 说明：表示模的范式。这个算法的理论依据是第二部分定理5的结论，是不断的扩充，在中添加-多项式的范式。但是，对于不同的取的次序，算法会有不同的结果。另外，每个-多项式的范式不唯一，所以得到的基也不唯一，而且可能很大，包含很多不必要的多项式，虽然原则上该算法应在有限步上停下来，但时间过长。计算机存储小，实际上有时也是不能实现的。该算法可以通过软件上机运行。例1 使用软件上机计算，求理想的基。执行下列程序：；运行程序后，得到的基为：其中，表示理想，表示单项式序。在第一部分我们知道，的约化基是唯一的。于是又有下列算法可求得的约化基。算法2 假设是基，则下列算法给出

16、了的约化基。 不整除 不整除 上述算法主要是根据约化基的定义。例2 使用软件上机计算可得理想的约化基为 ：在第二部分介绍中，我们给出了基的几种判定方法。根据这些方法，我们可以对基算法进行了改进。算法3 假设是多项式理想，则理想的基可由下列算法得到： 对算法3的原理阐述：先定义如下：对于。程序是这样开始的：先让等于，用来存放中所有元素下脚标的两两组合，用来表示最后一个下脚标，当不是空集时，从里选择一对，也即选择了。这里当且仅当存在，使得，并且，此时容易证明对于有标准表示（证明见1）。因此这种情况我们不考察，相反，若，令为模的范式，如果范式不为0，就把扩充为。以上是根据定理5的扩充思想，然后再对其

17、他的多项式对进行判断，直到得到基为止。事实上，基算法的计算非常复杂。由于在基的计算过程中，需要生成大量的中间多项式，即使我们输入的多项式的系数是非常小的整数，基中的多项式的系数也可以是非常复杂的有理数。因此，计算一个理想的基，需要花费很大的时间和大量的存储空间。五 基的初步应用在符号计算领域，基方法占有着十分重要的地位。它的应用领域包括代数方程组的求解，多项式在代数扩域和代数函数域中的因子分解，素理想检验，代数流形分解等。在此，我仅举几个简单的例子来说明这一点。一 基在多项式方程组求解中的应用我们考查这样的方程组：，为域上的多项式方程组。1. 多项式方程组的解的存在性问题。考查由该方程组的多项

18、式生成的理想，计算该理想的基。事实上，有下述定理：定理1 设,为的基。则方程组有解的充要条件为：。（证明见3）例1 确定多项式方程组是否有解？解 考查理想，字典序为，上机计算可得的基为上述方程组有解以前我们并未接触过如何判断一个多元高次方程组是否有解,通过本文的介绍我们可以发现, 基方法在这方面有很大的优势,只需运行一个简单的程序即可.2 多项式方程组解的有限性问题如果一个方程组有解，有多少解？如何来求解呢？我们可以通过多项式生成理想的基来解决这一问题。定理2 设为的基（关于任何单项式序的）则方程组，在系数域的代数闭包（定义参见3）中仅有有限多解的充要条件为：对每个，存在非负整数及，使得（证明

19、见3）例2 我们讨论下列方程组，单项式序是字典序,且解 考查理想的基为：方程组有解，其中都出现在某些多项式的首项当中，方程组仅有有限多个解。3 .多项式方程组的求解方法设中一方程组。（字典序为）设的基为，我们把中的多项式进行排序。由定理2可知，存在且及，使得。又单项式序为字典序，可知中仅含变元。依此类推仅含变元与。令我们可解出，把代入可解出。这样下去，多项式方程组就可解了。例3 讨论方程组的解的情况解 考查理想，单项式序为字典序。计算得的基为方程组有解。又都出现在某些多项式的首项当中，方程组仅有有限多个解。在中仅含变元，于是令得，把所有的值代入与中，得方程组的解为: 如果我们用以前学过的方法解

20、决此方程组,就要采用代入消元法,比较起解一个一元二次方程来说是比较麻烦的.同样对于有无限解的情况，用基方法一样可以解决。例4 讨论方程组的解的情况。解 (1) 高斯消元法,我们需对增广矩阵作初等行变换,有=系数矩阵设为,所以,秩()=秩()=(未知元个数),所以方成组有无数解.由最末矩阵可得(2) 基法在环中，令，而取字典序为。考查理想得的一个基为：方程组有解。不是所有的都存在非负整数及使得 即没出现在某些多项式的首项当中，方程组有无限解。但我们求得的基仍能帮我们解此方程组.由便可直接得出方成组的解.由此可见, 基方法在解线性方程组中,表现了很大的优越性,它只需很简单的程序便可解决问题,而以前用消元法解线性方程组,要对增广矩阵作行的变换,并不是一件十分容易的事情.例5 讨论方程组的解的情况。解 在环中，令而取字典序为“”考查理想上机计算得的基为，由定理1知，方程组无解。由此可见，基方法在解决多项式方程组中是一个十分简洁有效的方法。所有的多项式方程组都可以由它判别是否有