尹杰杰，王匯宇

(海南大學 信息科學技術(shù)學院，海南 ?？?570228)

可解多項式代數(shù)上的泛左Gr?bner基

尹杰杰，王匯宇

(海南大學 信息科學技術(shù)學院，海南 ?？?570228)

設(shè)I是可解多項式代數(shù)A=K[a1，…，an]的一個非零左理想，由可解多項式代數(shù)上的左Gr?bner基性質(zhì)，可知A中任何一個左理想對于一個單項式序的左Gr?bner基不一定滿足另一個單項式序.首先證明了在B上的任意2個單項式序1，2下，g={g1，g2，…，gt}是I在1下的左Gr?bner基，若LM(gi)=LM(gi)，1≤i≤t，那么g={g1，g2，…，gt}也是I在2下的左Gr?bner基；其次證明了I在A上的所有單項式序(可能無限個)下只有有限個約化左Gr?bner基；最后證明了A中的一個子集F，對于其上的任何一個單項式序，都是I的左Gr?bner基，子集F就是A的泛左Gr?bner基.

可解多項式； 單項式序； 左理想； 左Gr?bner基

Gr?bner基是Buchberger[1]在研究域上多變元多項式的理想生成元問題的博士論文中提出的，并以他的導師Gr?bner W 的名字命名.Gr?bner基理論最重要的貢獻是能計算且可求出來.自Buchberger創(chuàng)立交換多項式左理想的Gr?bner基理論及其算法以來，該方法對于解決交換與非交換數(shù)學領(lǐng)域的實際問題有著十分廣泛的應(yīng)用.如多項式左理想的Gr?bner基方法在判別多項式方程組解的存在性[2]，在解存在的情況下判別解的個數(shù)的有限性以及在求解過程中的有效性是眾所周知的事實.該方法已經(jīng)被國內(nèi)外數(shù)學工作者廣泛應(yīng)用.因此其一出現(xiàn)，不僅受到代數(shù)學界的重視，而且受到數(shù)學界、應(yīng)用數(shù)學界、計算機科學界和系統(tǒng)科學界等研究領(lǐng)域的重視，理論方面和應(yīng)用方面都得到了迅速的發(fā)展．由于實際問題規(guī)模的巨大，考慮到方程組的稀疏性，相應(yīng)地產(chǎn)生了可解多項式中的Gr?bner基的問題，對其進行研究，可以提高計算的效率.

本文給出了可解多項式代數(shù)A中的左Gr?bner基的性質(zhì)，得出了其中任何左理想對于一個單項式序的左Gr?bner基不一定滿足另一個單項式序，首先證明了在B上的任意2個單項式序1，2下，g={g1，g2，…，gt}是I在1下的左Gr?bner基，若LM(gi)=LM(gi)，1≤i≤t，那么g={g1，g2，…，gt}也是I在2下的左Gr?bner基；然后證明了I在A上的所有單項式序(可能無限個)下只有有限個約化左Gr?bner基；最后證明了A中的一個子集F，對于其任何一個單項式序，都是I的左Gr?bner基，子集F就是止的泛左Gr?bner基.

1 預備知識

本節(jié)簡單介紹有關(guān)可解多項式代數(shù)中左Gr?bner基的一些基本概念和結(jié)果，主要參考文獻[3-7]．

f的首單項式為LM(f)=aα(m)；

f的首項系數(shù)為LC(f)=λm；

f的首項為LT(f)=λmaα(m).

在計算代數(shù)中將B中元素稱為單項式，用小寫字母u，v，w，s，…來表示B中單項式．

定義1設(shè)有限生成K-代數(shù)A有一個PBWK-基B，是B上一個全序關(guān)系．若滿足以下條件

定義2設(shè)有限生成K-代數(shù)A有一個PBWK-基B，是B上一個單項式序．如果對于任意u=aα，v=aβB有uv=aαaβ=λα，βaα+β+fα，β，其中λα，βK*，fα，βA滿足LM(fα，β)

定義3設(shè)為B上一個單項式序，對于u，vB，如果存在wB，使得v=LM(uw)，則稱u左整除v，記為u│lv；如果存在wB，使得v=LM(uw)，則稱u右整除v，記為u│rv；如果存在w，sB，使得v=LM(wus)，則稱u整除v，記為u│v．

1)g是I的一個左Gr?bner基；

稱為f與g的左S-元．

定理7設(shè)是B上給定的單項式序是g生成的A左理想，那么g={g1，…，gt}是I的關(guān)于的一個左Gr?bner基當且僅當對所有的gi≠gj，用g中的元素對S(gi，gj)g做除法后使得所有的S(gi，gj)都約化到零，即

Buchberger算法：

AlgorithmI：

Input：F={f1，…，fm}?K[a1，…，an]，其中fi≠0

Whileg≠? Do

S：=S-{S(f，g)}

Ifh≠0 Then

g：=g∪{h}

End

End

1) g是I的一個極小左Gr?bner基；

則稱g為I是A的一個約化左Gr?bner基.

定義10設(shè)I是A的一個非零左理想，是B上的一個單項式序.則在下I有唯一一個約化左Gr?bner基.

定義11設(shè)I是A=K[a1，…，an]的一個左理想，F(xiàn)是I的子集，若F對K[a1，…，an]上的每一個項序都是I的Gr?bner基，則稱F是I的泛Gr?bner基.

2 主要結(jié)論和證明

定理1設(shè)I是K[a1，a2，…，an]的一個左理想，1，2是B上的2個單項式序，g={g1，g2，，…，gt}是I在1下的左Gr?bner基，如果LM(gi)=LM(gi)，1≤i≤t，那么g={g1，g2，…，gt}也是I在2下的左Gr?bner基．

證明因為I是K[a1，a2，…，an]的一個左理想，1，2是B上的2個單項式序，g={g1，g2，…，gt}是I在1下的左Gr?bner基，所以?fI，在單項式序1下有

令LM(f)=aα(1)，且有在1下f模g約化為0，可知aα(i)I，1≤i≤m.

令LM(f)=aβ(1)=aα(r)，其中1≤r≤m．?gj，1≤j≤t，有LM(gj)│laα(r)，所以有LM(gj)│laα(r)，所以LM(gj)│laβ(1)，故有LM(gj)│lLM(f)，且可以得到在2下f模g約化為0．所以G也是I在2下的一個左Gr?bner基．

定理2設(shè)I是K[a1，a2，…，an)]的一個非零左理想，令T為B上所有(無限多個)單項式序的集合，對于每個單項式序T，令〈LM(I)〉為I上的首單項式生成的單項式左理想，g為I在下的既約左Gr?bner基.進而令L={〈LM(I)〉│T}，R={g│T}，有1)存在R到L的一一映射；2)L是一個有限集，R也是一個有限集.

證明1)I是K[a1，a2，…，an]的一個非零左理想，T為B上所有單項式序的集合.

L={〈LM(I)〉│T}，R={g│T}令

φ：R→L，g→〈LM(I)〉，

g是I在下的既約左Gr?bner基，〈LM(I)〉為I上的首單項式生成的單項式理想.

令g，gR，且g≠g，則〈LM(g)〉≠〈LM(g)〉，所以φ是單射.

綜上所述，R到L是一一映射.

2)假設(shè)L是一個無限集.L={〈(LM(I)〉│T}，從L中任意取出一個首項理想〈LM(I)〉，滿足該首項理想〈LM(I)〉的單項式序有無限個.

取T0?T，其中T0是滿足首項理想〈LM(I)〉的所有單項式序構(gòu)成的集合.顯然T0是一個有限集.

令g={f1，f2，…，fs}，設(shè)多項式fi有ki項，1≤i≤s，所以LM(fi)在不同的單項式序下最多有ki個不同的首項1≤i≤s，所以LM(g)在不同的單項式序下最多有kik2…ks個不同的LM(g).由此可知LM(g)不相同的單項式序最多也只有kik2…ks，是有限的.

又因為〈LM(g)〉是由LM(g)生成的左理想，故可知左理想〈LM(g)〉互不相同的單項式序也是有限的.

取無限集T1?T0，使得在T1中的所有項序下都有LM(f1)=m1；

取無限集T2?T1，使得在T2中的所有項序下都有LM(f2)=m2；

取無限集T3?T2，使得在T1中的所有項序下都有LM(f3)=m3；

?

取無限集Ts?Ts-1，使得在T1中的所有項序下都有LM(fs)=ms；因為Ts?Ts-1? … ?T3?T2?T1?T0，所以在無限集Ts的所有項序下都有LM(fi)=mi，1≤i≤s；

由定理1可知，在Ts的所有項序下，g都是I的左Gr?bner基.又因為〈LM(I)〉=〈m1，m2，…，ms〉，所以〈LM(I)〉是有限的，矛盾，故L是有限集.

又因為〈LM(I)〉=〈m1，m2，…，ms，ms+1，…，mr〉所以〈LM(I)〉是有限的，矛盾.

綜上所述，假設(shè)不成立，L為有限集.

由1)可知R到L是一一映射的，所以R也是一個有限集.得證.

因為R={g│T}，且R是一個有限集，所以可知I只有有限多個約化左Gr?bner基.

定理3左理想I一定存在子集F，對于A的每一個單項式序都是I的左Gr?bner基[7].

證明由定理2，可設(shè)(G1，1)={g11，g12，…，g1k1}，(G2，2)={g21，g22，…，g2k2}，(G3，3)={g31，g32，…，g3k3}，…，(Gs，s)={gs1，gs2，…，gsks}分別是I關(guān)于單項式序1，2，3，…，s的約化左Gr?bner基，故對任何單項式序，I的約化左Gr?bner基一定重合于G1，G2，…，Gs之中的一個.令F={g11，g12，…，g1k1，…，gs1，gs2，…，gsks}，則可知對任何單項式序，F(xiàn)都是I的約化左Gr?bner基.得證.

此時可知F就是I的泛左Gr?bner基.

3 實驗舉例

設(shè)I=〈xy-x，x-y2〉?Q[x，y]，找出I的泛左Gr?bner基，只需要找出I的全部有限個約化左Gr?bner基.只要根據(jù)Buchberger算法，對一切可能的項序求出I的既約左Gr?bner基，其泛左Gr?bner基即可求出為F={x-y2，xy-x，y3-y2，x2-x}.

[1]BuchbergerB.EinAlgorithmuszumAuffindenderBasiselementedesRestklassenringesnacheinemnulldimensionalenpolynomideal[D].Innsbruck：Universityoflnnsbruck，1965．

[2] 熊雪瑋，趙志琴.圖的k-獨立集與Gr?bner基求解[J]．工程數(shù)學學報，2012，29(5)：696-702．

[3]AdamsW，LoustaunausP.AnintroductiontoGr?bnerbases[M]．Washington,DC：AmericanMathematicalSociety，1994．

[4] 劉木蘭．Gr?bner基理論及其應(yīng)用[M]．北京：科學出版社，2000.

[5]LiH，WuY.Filtered-gradedtransferofGr?bnerbasiscomputationinsolvablepolynomialalgebras[J].Corem．Alg．2000，28(1)：15-32．

[6]LiH.NoncommutativeGr?bnerbasesandFiltered-GradedTransfer[M].Berlin:Springer-Verlag，2002．

[7] 安立奎， 韓麗艷．半群代數(shù)K[A]中的泛Gr?bner基的研究[J]．渤海大學學報(自然科學版)，2005，26(4)：331-332．

Universal Left Gr?bner Bases on Solvable Polynomial Algebra

Yin Jiejie，Wang Huiyu

(Department of Information and Technology College, Hainan University, Haikou 570228, China)

In the report, let I be a nonzero left ideal of a solvable polynomial algebraA=K[a1，…，an], based on the property of left Gr?bher of the solvable polynonlial algebra，we know that a len Gr?bner bases with respect to one monomial ordering might not be a left Gr?bner bases with respect to another monomial ordering．First, it was proved that1，2，B，g={g1，g2，…,gt}, is the left Gr?bher bases ofIwith respect to1, if LM(gi)=LM(gi), 1≤i≤t, theng={g1,g2, …,gt} is also the left Gr?bher bases ofIwith respect to2; Second, it was proved that there are only finitely many possible reduced left Gr?bner bases for a given left ideal; Last, a subset ofA,f, is a left Gr?bner bases with respect to every ordering, and which is called a universal left Gr?bner bases ofA.

solvable polynomial algebra; monomial ordering; left ideal; left Gr?bner bases

2015-05-11

尹杰杰(1990-)，男，廣東韶關(guān)人，2012級碩士研究生，研究方向：計算代數(shù)，E-mail：15120644019@163．com

1004-1729(2015)04-0305-05

O 157.5

A DOl：10.15886/j.cnki.hdxbzkb.2015.0054