基及其初步應(yīng)用

1、基及其初步應(yīng)用引言基理論的形成,可以說是經(jīng)歷了幾十年的時(shí)間,最早可以追溯到1927年F·ironaka于1964年在研究奇性分解時(shí),引進(jìn)了多變元多項(xiàng)式的除法算法.在1965年,B.Buchberger使用除法算法系統(tǒng)地研究了域上多變元多項(xiàng)式環(huán)的理想生成元問題.他的基本思想是在單項(xiàng)式的集合中引入保持單項(xiàng)式的乘法運(yùn)算的全序,稱為項(xiàng)序,以保證多項(xiàng)式相除后所得多項(xiàng)式唯一,他引入了-多項(xiàng)式,使得對多項(xiàng)式環(huán)中的任一給定的理想,從它的一組生成元出發(fā),可計(jì)算得到一組特殊的生成元,即現(xiàn)在通常稱之的基. 基的概念是B.Buchberger于1965年在其博士論文中提出來的,為紀(jì)念其導(dǎo)師W.Groebne

2、r而將這種基稱之為基.利用基,許多關(guān)于理想的問題都得到了解決.因此它一出現(xiàn),受到許多領(lǐng)域的研究人員的重視,理論方面和應(yīng)用方面都得到了迅速發(fā)展.本文主要介紹有關(guān)基的一些基本內(nèi)容.一 基簡介（一） 預(yù)備知識設(shè)表示域上的多項(xiàng)式環(huán)中的全體項(xiàng)組成的集合.“”表示某一線序.（線序的定義見1）定義1 在中，如果線序滿足：（1）,1t;（2）對每個(gè),.則線序叫做上的單項(xiàng)式序.注 中單項(xiàng)式記為(,是元數(shù)組).我們約定變元上的序關(guān)系為. 下面給出幾種常用單項(xiàng)式序的例子：例1字典序，簡記為：lex.定義如下：在中，從左向右第一個(gè)非零分量為正數(shù).例如 按照字典序有： 例2 分次字典序，簡記為：grlex.定義如下：在

3、中，或者而從左向右第一個(gè)非零分量為正數(shù).例如 按照分次字典序有：， 例3 分次逆字典序，簡記為：grevlex.定義如下：在中，或者而中從右向左第一個(gè)非零分量為負(fù)數(shù).例如 按照分次逆字典序有：， 幾個(gè)符號說明：設(shè)，其中，I是有限集；表示中出現(xiàn)的所有的單項(xiàng)式的集合；表示中出現(xiàn)的所有項(xiàng)的集合；表示中的最大項(xiàng)，稱的首項(xiàng)；表示中的最大項(xiàng)，稱的首單項(xiàng)式；中的系數(shù)，稱首系數(shù).定義2 設(shè)是一個(gè)非空子集，如果：（1）;（2） ，有.則稱為一個(gè)多項(xiàng)式理想.若有有限個(gè)多項(xiàng)式，作，易證，是一多項(xiàng)式理想，稱為由生成的理想.定義3 在多項(xiàng)式環(huán)中,如果是由一組單項(xiàng)式生成的理想,則稱()是單項(xiàng)式理想.定義4 設(shè)是一個(gè)非零理

4、想，是一給定的單項(xiàng)式序，由生成的理想稱為的首項(xiàng)理想.（其中，）(二) 基的定義定義5 對于給定的單項(xiàng)式序，非零理想的有限子集，如果滿足：，則稱是的基.說明 根據(jù)定義，因?yàn)槭堑淖蛹?，易知因此，要證明是的基，只須證明中的每個(gè)單項(xiàng)式的首項(xiàng)可以被中的某一項(xiàng)整除.注意 與某個(gè)單項(xiàng)式序密切相關(guān)，即若是關(guān)于單項(xiàng)式序的基，但關(guān)于單項(xiàng)式序未必是基.下面給出Groebner基的幾個(gè)例子：例4 設(shè),單項(xiàng)式序?yàn)榉执巫值湫?則 是的基.證明 ,則或者它們顯然都可以被或整除.從而，是的基.例5 ，其中單項(xiàng)式序是grlex,則不是的基.證明 于是但即不是的基.說明 理想的基不唯一，例如在例4中，與都是的基.這是因?yàn)椋涸诘幕?/p>

5、中，多項(xiàng)式的首項(xiàng)系數(shù)不唯一確定，當(dāng)給定了的之后，在中添加中任意多項(xiàng)式所得的也是的基.另外，因?yàn)槔硐胫芯哂邢嗤醉?xiàng)的多項(xiàng)式有許多，它們可以構(gòu)成相同的首項(xiàng)理想，即使是極小基（極小基的定義在后面介紹），也不是唯一的.是不是每一個(gè)非零理想都有基呢？在定義中，也并沒要求是的生成元素組成的集合，但事實(shí)上，一定生成理想.下面的定理可幫我們回答上述兩個(gè)問題.定理1 固定一個(gè)單項(xiàng)式序，每一個(gè)非零理想都有基.更進(jìn)一步，.為證明此定理，我們先給出幾個(gè)定義和已證明過的命題.定義6 給定,模一步約化到，記為整除的某一項(xiàng)，且;設(shè)，如果存在一列指標(biāo)和一列多項(xiàng)式，使得，則稱模約化到，記為定義7 如果一個(gè)多項(xiàng)式模是不可約化的，

6、則稱是模的范式.對每個(gè)多項(xiàng)式都存在一個(gè)多項(xiàng)式使得其中，是模不可約化的，則稱是模的范式.其實(shí)，只有當(dāng)中的每一項(xiàng)都不能被整除時(shí)，模才是不可約化的.命題1 設(shè)是一個(gè)非零理想，則一定存在有限個(gè)多項(xiàng)式，使得.（證明見1）.命題2 假設(shè)是一個(gè)單項(xiàng)式理想,則一項(xiàng)當(dāng)且僅當(dāng)存在,使得.下面來證明定理1.證明 由命題1，是有限生成的，即存在的有限子集，使得，滿足基的定義，是的基.另外，設(shè)，模的范式設(shè)為，則 由范式性質(zhì)知，對每個(gè)不能整除如果，則由命題2，存在某個(gè),使得整除矛盾, 由于的任意性,.（三） 極小基前面提到了極小基的概念，這是一類特殊的基，我們來看一看極小基的一些有關(guān)性質(zhì).定義8 基稱為極小的，如果對于每

7、個(gè)，而且對于任何，都有不能整除.說明 定義8中提到的基，是指它是生成的理想的基.以后若提到中的非零多項(xiàng)式的有限集是基，都是指這一類型的基.下面我們給出一種求極小基的方法.定理2 設(shè)是理想的基，如果，則仍是的基.實(shí)際上，從任何一組基出發(fā)，不難得到極小基.若是基，那么對任何，若存在，就將從中拿掉，然后將剩下的每個(gè)用去除，便得到了極小基.例6 經(jīng)驗(yàn)證知是基.單項(xiàng)式序是“”.，仍是基，且是極小基.下面的定理告訴我們，的關(guān)于同一單項(xiàng)式序的極小基盡管不是唯一的，但有相同的元素個(gè)數(shù)，且適當(dāng)排序后，對應(yīng)多項(xiàng)式的首項(xiàng)相同，即：定理3 如果，是中理想的相對于同一單項(xiàng)式序的極小基，則，而且對.（如需要，可將和適當(dāng)?shù)?/p>

8、重新排序.（四）約化基前面說了，理想的基不唯一，為了討論基的唯一性，我們引入以下定義.定義9 設(shè)是理想的基，如果滿足：（1）;（2）對任意模是不可約化的. 則稱是的約化基.定理4 假設(shè)是的理想，對于給定的單項(xiàng)式，存在唯一的約化基.（證明見1）由此可見，對于每個(gè)單項(xiàng)式序都有唯一的約化基.現(xiàn)在有兩個(gè)問題，（1）的約化基是否是有限個(gè)呢？（2）是否有這樣一個(gè)的子集，它對于的每一個(gè)單項(xiàng)式序都是的基呢？事實(shí)上有：定理5 只有有限個(gè)約化基，而且一定存在子集，它對于的每一個(gè)單項(xiàng)式序都是基（證明見4）二 基的判定我們知道，每一個(gè)非零理想都有基，那么，什么樣的子集是的基呢？如何來判定是否是的基呢？下面我們給出幾種

9、判定方法.定理1 假設(shè)是由多項(xiàng)式生成的主理想，（主理想定義見5），則任何包含的的有限子集都是的基.證明 設(shè)是有限子集，令，且，）則，即可以整除，是的基。例1 設(shè)，則是的基。定理2 設(shè)是的有限子集，若對每個(gè)，模的范式是唯一的，那么是基。（證明見1）實(shí)際上，上述命題的逆命題也成立，即如果是基，則對于每個(gè)，模的范式是唯一的.定理3 設(shè)單項(xiàng)式序是，如果是中理想的基，則也是單項(xiàng)式理想的基.證明 設(shè)，則，要證是的基，只需證存在某個(gè)，使得是的基即，從而，也是單項(xiàng)式理想的基.例2 若是的基，則是的基.定理4 假設(shè)是一個(gè)有限集合，并且，如果任取，任取單項(xiàng)式，滿足，都有模的范式為0，則是基.定理4給出的判定是否是

10、基的方法，因?yàn)樗鼘γ繉M足的單項(xiàng)式都要進(jìn)行判定，這樣的過程需要無限多步.后來，又有人給出了一種改進(jìn)的方法.為介紹此方法，我們先介紹兩個(gè)定義.定義1 設(shè)是兩個(gè)非零多項(xiàng)式，如果則稱的最小公倍式.記作：.例3則.定義2 設(shè)為非零多項(xiàng)式，取定一單項(xiàng)式.記作，稱.例4 在上例中，計(jì)算得，于是，我們又得到下面的定理.定理5 設(shè)是的有限子集，并且，則是基的充分必要條件為模的范式為0.與定理4相比，我們的計(jì)算步驟大大簡化了，只需對S-多項(xiàng)式去判定即可.下面我們來看一道例題.例5 的單項(xiàng)式序?yàn)樽值湫?，令，求I基.解 令，有，模F約化為0，模F約化為0，模F約化為0，模F不可約化.令由上步可知，模約化為0。同理可

11、驗(yàn)證，模約化為0。由定理5可知，是理想的基。實(shí)際上，定理5也給出了一種計(jì)算基的方法，若對于，看是否能模約化為0。若能，則是基，若不能，方法是擴(kuò)充，在上添加-多項(xiàng)式的范式，得到，重復(fù)上述判定，直到得到基。由定理5。我們很容易得到下列推論：推論1 設(shè)是一個(gè)有限的單項(xiàng)式集合，則是基。證明 設(shè)，則= 模的范式為0，由定理5知，是基。下面我們介紹一個(gè)定義，定義3 設(shè)是一個(gè)有限子集，則，其中是單項(xiàng)式，對于，可能相同，并且，則上述表達(dá)式稱為對于的標(biāo)準(zhǔn)表示。例6，單項(xiàng)式序是分次字典序，則并且對于有標(biāo)準(zhǔn)表示。有了上述概念，我們再介紹一種基的判定方法。定理6 對于給定的單項(xiàng)式序,是有限集合，則是基如果對每個(gè)，對有

12、標(biāo)準(zhǔn)表示。（證明見1）如果我們把定義3中的條件改為，其中是一個(gè)項(xiàng)，則稱上述表示為對于的-表示。應(yīng)用-表示的定義，我們又有了一個(gè)基的判定方法。定理7 設(shè)是有限子集，并且，單項(xiàng)式序是，如果對于每個(gè)或者它對于有一個(gè)-表示，其中，則是基（證明見3）特別地，如果，則-表示就變成了標(biāo)準(zhǔn)表示。因此，上述定理可得到一種特殊情況推論2 設(shè)是有限子集，如果對每個(gè)或者對于有標(biāo)準(zhǔn)表示，則是基例7 ，令，單項(xiàng)式序是分次字典序，是基。定義7 設(shè)，如果,沒有公共的變元，則稱是不相交的項(xiàng)。此時(shí)，反之，如果有公共變元，則稱是相交的項(xiàng)。事實(shí)上，如果是不相交的項(xiàng)，則對于有標(biāo)準(zhǔn)表示（證明見1），由此，根據(jù)定理7及上述結(jié)論，我們有定理

13、8 ，單項(xiàng)式序是，則是基對每個(gè)，如果它們的首項(xiàng)相交則對于有標(biāo)準(zhǔn)表示。例8 ，設(shè)，單項(xiàng)式序是分次字典序。由定理8，只需對進(jìn)行判定，對有標(biāo)準(zhǔn)表示是基。定理8是比較容易理解的，事實(shí)上，若首項(xiàng)不相交，對于有標(biāo)準(zhǔn)表示，從而對也有標(biāo)準(zhǔn)表示。所以我們可以免去驗(yàn)證步驟。定理8的結(jié)論與定理7或推論2相比，我們只需驗(yàn)證首項(xiàng)相交的多項(xiàng)式對，看其是否對有標(biāo)準(zhǔn)表示，從而使問題大大簡化了。以上給出的是基的8種判斷方法，做題可靈活選擇。三 基的性質(zhì)在這部分里，我們著重介紹基所具有的幾點(diǎn)性質(zhì)。給定上的一個(gè)單項(xiàng)式序，是的一個(gè)理想，是的基，若設(shè)，則由基的定義可知，對則，其中。由于上式左邊只有一個(gè)項(xiàng)，從而右邊必只出現(xiàn)一項(xiàng)，能被某個(gè)

14、整除，由此得到第一個(gè)性質(zhì)。性質(zhì)1 各定上的一個(gè)單項(xiàng)式序，是的理想，是的基，則對能被某個(gè)整除（）。性質(zhì)2 若是的基，則對任意的多項(xiàng)式，模的范式為0，從而也是的基。證明 假設(shè)模的范式，則由范式性質(zhì)，是模不可約化的，設(shè)，則使得，由性質(zhì)1可知，可被某個(gè)整除，與模不可約化矛盾，從而，是的基。性質(zhì)3 若是的基，則對任意的多項(xiàng)式，設(shè)模的范式是，則由和唯一確定。（證明見8）四 基的算法有了基的定義，就要研究基的計(jì)算問題。實(shí)際上，在第二部分里，我們已經(jīng)初步討論了這個(gè)問題，通過擴(kuò)充的思想來計(jì)算基是比較繁瑣的，但這個(gè)過程通過計(jì)算機(jī)是可以實(shí)現(xiàn)的。1965年，在他的博士論文中研究了基的性質(zhì)，并給出了計(jì)算基的算法算法。算

15、法1 ，理想，則下列算法可求得的基。 說明：表示模的范式。這個(gè)算法的理論依據(jù)是第二部分定理5的結(jié)論，是不斷的擴(kuò)充，在中添加-多項(xiàng)式的范式。但是，對于不同的取的次序，算法會有不同的結(jié)果。另外，每個(gè)-多項(xiàng)式的范式不唯一，所以得到的基也不唯一，而且可能很大，包含很多不必要的多項(xiàng)式，雖然原則上該算法應(yīng)在有限步上停下來，但時(shí)間過長。計(jì)算機(jī)存儲小，實(shí)際上有時(shí)也是不能實(shí)現(xiàn)的。該算法可以通過軟件上機(jī)運(yùn)行。例1 使用軟件上機(jī)計(jì)算，求理想的基。執(zhí)行下列程序：；運(yùn)行程序后，得到的基為：其中，表示理想，表示單項(xiàng)式序。在第一部分我們知道，的約化基是唯一的。于是又有下列算法可求得的約化基。算法2 假設(shè)是基，則下列算法給出

16、了的約化基。 不整除 不整除 上述算法主要是根據(jù)約化基的定義。例2 使用軟件上機(jī)計(jì)算可得理想的約化基為 ：在第二部分介紹中，我們給出了基的幾種判定方法。根據(jù)這些方法，我們可以對基算法進(jìn)行了改進(jìn)。算法3 假設(shè)是多項(xiàng)式理想，則理想的基可由下列算法得到： 對算法3的原理闡述：先定義如下：對于。程序是這樣開始的：先讓等于，用來存放中所有元素下腳標(biāo)的兩兩組合，用來表示最后一個(gè)下腳標(biāo)，當(dāng)不是空集時(shí)，從里選擇一對，也即選擇了。這里當(dāng)且僅當(dāng)存在，使得，并且，此時(shí)容易證明對于有標(biāo)準(zhǔn)表示（證明見1）。因此這種情況我們不考察，相反，若，令為模的范式，如果范式不為0，就把擴(kuò)充為。以上是根據(jù)定理5的擴(kuò)充思想，然后再對其

17、他的多項(xiàng)式對進(jìn)行判斷，直到得到基為止。事實(shí)上，基算法的計(jì)算非常復(fù)雜。由于在基的計(jì)算過程中，需要生成大量的中間多項(xiàng)式，即使我們輸入的多項(xiàng)式的系數(shù)是非常小的整數(shù)，基中的多項(xiàng)式的系數(shù)也可以是非常復(fù)雜的有理數(shù)。因此，計(jì)算一個(gè)理想的基，需要花費(fèi)很大的時(shí)間和大量的存儲空間。五 基的初步應(yīng)用在符號計(jì)算領(lǐng)域，基方法占有著十分重要的地位。它的應(yīng)用領(lǐng)域包括代數(shù)方程組的求解，多項(xiàng)式在代數(shù)擴(kuò)域和代數(shù)函數(shù)域中的因子分解，素理想檢驗(yàn)，代數(shù)流形分解等。在此，我僅舉幾個(gè)簡單的例子來說明這一點(diǎn)。一 基在多項(xiàng)式方程組求解中的應(yīng)用我們考查這樣的方程組：，為域上的多項(xiàng)式方程組。1. 多項(xiàng)式方程組的解的存在性問題?？疾橛稍摲匠探M的多項(xiàng)

18、式生成的理想，計(jì)算該理想的基。事實(shí)上，有下述定理：定理1 設(shè),為的基。則方程組有解的充要條件為：。（證明見3）例1 確定多項(xiàng)式方程組是否有解？解 考查理想，字典序?yàn)?，上機(jī)計(jì)算可得的基為上述方程組有解以前我們并未接觸過如何判斷一個(gè)多元高次方程組是否有解,通過本文的介紹我們可以發(fā)現(xiàn), 基方法在這方面有很大的優(yōu)勢,只需運(yùn)行一個(gè)簡單的程序即可.2 多項(xiàng)式方程組解的有限性問題如果一個(gè)方程組有解，有多少解？如何來求解呢？我們可以通過多項(xiàng)式生成理想的基來解決這一問題。定理2 設(shè)為的基（關(guān)于任何單項(xiàng)式序的）則方程組，在系數(shù)域的代數(shù)閉包（定義參見3）中僅有有限多解的充要條件為：對每個(gè)，存在非負(fù)整數(shù)及，使得（證明

19、見3）例2 我們討論下列方程組，單項(xiàng)式序是字典序,且解 考查理想的基為：方程組有解，其中都出現(xiàn)在某些多項(xiàng)式的首項(xiàng)當(dāng)中，方程組僅有有限多個(gè)解。3 .多項(xiàng)式方程組的求解方法設(shè)中一方程組。（字典序?yàn)椋┰O(shè)的基為，我們把中的多項(xiàng)式進(jìn)行排序。由定理2可知，存在且及，使得。又單項(xiàng)式序?yàn)樽值湫?，可知中僅含變元。依此類推僅含變元與。令我們可解出，把代入可解出。這樣下去，多項(xiàng)式方程組就可解了。例3 討論方程組的解的情況解 考查理想，單項(xiàng)式序?yàn)樽值湫?。?jì)算得的基為方程組有解。又都出現(xiàn)在某些多項(xiàng)式的首項(xiàng)當(dāng)中，方程組僅有有限多個(gè)解。在中僅含變元，于是令得，把所有的值代入與中，得方程組的解為: 如果我們用以前學(xué)過的方法解

20、決此方程組,就要采用代入消元法,比較起解一個(gè)一元二次方程來說是比較麻煩的.同樣對于有無限解的情況，用基方法一樣可以解決。例4 討論方程組的解的情況。解 (1) 高斯消元法,我們需對增廣矩陣作初等行變換,有=系數(shù)矩陣設(shè)為,所以,秩()=秩()=(未知元個(gè)數(shù)),所以方成組有無數(shù)解.由最末矩陣可得(2) 基法在環(huán)中，令，而取字典序?yàn)?。考查理想得的一個(gè)基為：方程組有解。不是所有的都存在非負(fù)整數(shù)及使得 即沒出現(xiàn)在某些多項(xiàng)式的首項(xiàng)當(dāng)中，方程組有無限解。但我們求得的基仍能幫我們解此方程組.由便可直接得出方成組的解.由此可見, 基方法在解線性方程組中,表現(xiàn)了很大的優(yōu)越性,它只需很簡單的程序便可解決問題,而以前用消元法解線性方程組,要對增廣矩陣作行的變換,并不是一件十分容易的事情.例5 討論方程組的解的情況。解 在環(huán)中，令而取字典序?yàn)椤啊笨疾槔硐肷蠙C(jī)計(jì)算得的基為，由定理1知，方程組無解。由此可見，基方法在解決多項(xiàng)式方程組中是一個(gè)十分簡潔有效的方法。所有的多項(xiàng)式方程組都可以由它判別是否有