（基础数学专业论文）多项式复合与grobner基的性质与计算研究.pdf

j - 暂 = 多项式复合与g r 6 b n e r 基的性质与计算研究 摘要 本文研究多项式复合与g r 6 b n e r 基的性质与计算。 设k 陋l ，z 2 ，z n 是域k 上关于变量z 1 ，z 2 ，z n 的多元多项式环， e = ( p 1 ，如，如) 是一个有序多项式组，多项式，( z 1 ，z 2 ，z n ) 关于e 的复 合是多项式，( p 1 ，p 2 ，) ，记为厂oe 设f 是k k l ，z 2 ，z 凡】的一个非零子 集，规定f 。e = 厂oel ，f ) 我们说子集g 是一个g r 6 b n e r 基，如果g 是由g 生成理想i d e a l ( g ) 的g r 6 b n e r 基，说多项式复合e 与g r 6 b n e r 基的计 算可交换，如果对任意g r 6 b n e r 基g ，goe 仍是g r 6 b n e r 基，说多项式复合e 与项序 相容，如果删g ，p g 令p ol t ( e ) gol t ( e ) 首先，我们给出h o o nh o n g 关于多项式复合下g r 6 b n e r 基性质的经典定理 的新证明，该证明相比简洁得多，且方法新颖、技巧性强接着讨论多项式复合 下泛g r 6 b n e r 基、单项式g r 6 b n e r 基、齐次g r 6 b n e r 基、r 齐次g r 6 b n e r 基的 性质与计算，分别得到了多项式复合与泛g r 6 b n n 基、单项式g r 6 b n e r 基、齐 次g r 挑n e r 基、r 一齐次g r 6 b n e r 基、入g r 6 b n e r 基的计算可交换的等价条件 我们的结果克服了以前研究多项式复合只与整体g r 6 b n e r 基相关的单一性，丰 富了研究多项式复合与g r 6 b n e r 基的研究内容，尤其是首次对多项式复合下某 类g r 6 b n e r 基的性质展开研究，这是一个较大的突破。 接下来我们研究多项式复合e 与项序 的相容性、齐次相容性、r 一齐次相 容性，给出了具体的算法( 判定方法) ，这样，我们既解决了h o o nh o n g 于1 9 9 8 年提出的开问题，又把抽象的代数条件具体化，使之更便于判别与应用接着我 们研究多项式复合运算的性质，并对几类常见的项序给出了多项式复合的具体形 式 最后，我们研究微分算子环( 代数) 、c l i 怕r d 与g r a s s m a n n 代数的g r 6 b n e r 基及理想的成员问题，得到了一些有趣的结果我们能更好地运用外微分系统的 技术研究在物理中提出的偏微分方程系统的性质，尤其是明确给出了微分算子代 数中某些左理想的g r 6 b n e r 基，为研究某些微分方程组提供了一种新方法。我们 也刻划了双斜多项式的双边理想的成员问题 i -。 簟 ，i飞liiiiiiii卜kiil 博士学位论文 关键词：多项式环；项序；g r 6 b n e r 基；多项式复合；微分算子环；c l i 舫r d 与g r a s s m a n n 代数；双斜多项式环 1 、j 心 j 童 多项式复合与g r 6 b n e r 基的性质与计算研究 a b s t r a c t t h i sp a p e rs t u d i e sp r o p e r t i e sa n dc o n l p u t a t i o nf b rc o m p o s i t i o na n dg r 6 b n e r b a s e s l e tk z 1 ，z 2 ，z 捌b eap o l y n o m i a lr i n gi nt h ev a r i a b l e sz 1 ，z 2 ，o t l w i t hc o e 伍c i e n tf r o m6 e l dk ，e = ( 口1 ，p 2 ，) b eal i s to f 礼p o l y n i m i a l si n k z 1 ，z 2 ，z n 】c o m p o s i t i o no f ，( z 1 ，z 2 ，z 几) b yei s 厂( 口1 ，臼2 ，如) ，d e n o t e sb y ，oe l e tfb ean o n z e r os e to fp o l y n o m i a li nj r z 1 ，z 2 ，z n 】，、v e d e 6 n e ：foe = ，oe i ，f ) w bs a yas u b s e tg ag r 6 b n e ri fgi sg r o e b n e r b a s i so fi d e a l ( g ) g e n e r a t e db yg ，s a yag r 6 b n e rb a s i sc o m p u t a t i o nc o m m u t i n g w i t hc o m p o s i t i o nb yei fg oo i sg r 6 b n e rb a s i sf o ra n yg r 6 b n e rb a s i s ，s a yat e r m o r d e r i n gb e i n gc o m p a t i b l ew i t hc o m p o s i t i o ni f 、口勿崎，g ，p 口= 争p o l t ( e ) g o l t ( e ) f i r s t l y ，w eg i v ean e wp r o o fo fh o n g sc l a s s i c a lt h e o r e m ，t h ep r o o fi ss i m p l e ， a n dn e wm e t h o d a f t e rt h a t ，ed i s c u s sp r o p e r t i e sa n dc o m p u t a t i o n sf b ru n i v e r s a l g r 6 b n e rb a s e s 、m o n o m i a lg r 6 b n e rb a s e s 、 h o m o g e n e o u sg r 6 b n e rb a s e s 、 r h o m o g e n e o u sg r 6 b n e rb a s e su n d e rc o m p o s i t i o n w 色g e te q u i v a l e n tc o n d i t i o n s o fm o n o m i a lg r 6 b n e rb a s i s 、 h o m o g e n e o u sg 墒b n e rb a s i s 、r _ h o m o g e n e o u s g r 6 b n e rb a s i sc o m p u t a t i o n sc o m m u t i n gw i t hc o m p o s i t i o nb ye 0 u rr e s u l t s o v e r c o m ef o r m e r l ys i n 9 1 es t u d i n gc o m p o s i t i o na n dg r 6 b n e rb a s i s o n ee n r i c h c o n t e n ts t u d i n gc o m p o s i t i o na n dg r 6 b n e r b a s i s e a s p e c i a l l y ，w et a k et h el e a di n s t u d i n gs o m eg r 6 b n e rb a s e su n d e rc o m p o s i t i o n ，t h i si sab i g g e rb r e a c h s e c o n d l y r es t u d yc o m p a t i b i l i t i e so fc o m p o s i t i o na n dt e r mo r d e r i n g 、 h o m o g e n e o u sc o m p a t i b i l i t yo fc o m p o s i t i o na n dt e r mo r d e r i n g 、r - h o m o g e n e o u s c o m p a t i b i l i t y a n dg i v ec o n c r e t ea l g o r i t h m o u d g i n gm e t h o d ) i nt h i sw a 孔w er e s o l v e dh o n g so p e np r o b l e m ( 1 9 9 8 ) ，a n dm a d ea b s t r c ta l g e b r i cc o n d i t i o nm o r e c l e a r ，i ti sf a v o u r a b l et oju d g m e n ta n da p p l i c a t i o n a f t e rt h a t ，w es t u d yo p e r a t i o no fc o m p o s i t i o n ，a n dg i v ec o n c r e t ef o r m so fc o m p o s i t i o nf o rs o m ec o m m o n i i i ， 博士学位论文 t e r mo r d e r i n g s f i n a l l y ，w es t u d yg r 6 b n e rb a s e sa n dm e m b e r s h i pp r o b l e m so fi d e a lf b rw e y l a l g e b r a 、 c l i 肋r da n dg r a s s m a n na l g e b r a ，a n dg e ts o m ei n t e r e s t i n gr e s u l t s e a s p e c i a l l y ，w eg e tc l e a r l yg r 6 b n e rb a s e so fs o m e1 e f ti d e a li nw e y l a l g e b r a ，p r o v i d en e wm e t h o df b rs t u d i n gs o m ed i n e r e n t i a le q u a t i o ns y s t e m s w ed e p i c tt h e m e m e r l d s h i pp r o b l e mo ft w o s i d ei d e a lt - 0 rb i n o m i a lp o l y n o m i a lr i n g s k e yw o r d s ：p o l y n o m i a lr i n g ；t e r mo r d e r i n g ；g r 6 b n e rb a s i s ；c o m p o s i t i o n ； w e y l 一a l g e b r a ；c l i 仃o r da n dg r a s s m m a na l g e b r a ；b i n o m i a ls k e wp o l y n o m i a lr i n g i v 弋e o f o 多项式复合与g r 6 b n e r 基的性质与计算研究 第一章绪论 随着社会信息化进程的加快，特别是计算机、互联网的迅速发展，代数与符 号计算的研究受到了科学工作者的高度重视，它的研究已渗透到计算代数、代数 几何、微分方程、概率统计、数值分析、编码、密码、多维系统理论等诸多领域 g r 6 b n e r 基的理论与方法在代数与符号计算中起着关键作用，例如运用g r 曲n e r 基解大型代数方程组 7 6 】、 2 2 】，g r 6 b n e r 基在法国卫星6 0 0 m b 中的应用 2 1 g r 6 b n e r 基的研究吸引了越来越多的数学与工程计算等领域科学工作者，它的研 究具有十分重要的意义。近四十年来，以多变多项式求解算法研究为核心的代数 与符号计算理论与技术得到了快速的发展。1 9 6 5 年，b b u c h b e r g e r 使用符号 算法系统地研究了域上多变多项式环的理想生成元问题，提出了g r 6 b n e r 基的 概念 5 ，通过计算g r 6 b n e r 基，代数理想成员的判断及数学中许多抽象的问题 可得到较好的认识和解决 s c h w a r t z 研究了g r 6 b n e r 基的稳定性 6 3 】，接着 r o b b i a n o 研究了g r 6 b n e r 基的元素个数与次数的上界【5 7 】1 9 8 8 年g i a n n i 运 用g r 6 b n e r 基研究了理想的准素分解 6 4 ，同年，k a n d r i 研究了欧氏环上多 元多项式环的g r 6 b n e r 基，接着他们研究了可解代数( 非交换) 的g r 洮n e r 基 5 0 1 9 9 2 年，m 6 l e r 利用合冲给出了g r 6 b n e r 基计算的一个新方法 6 0 】， 同年，f i t z p a t r i c k 运用g r 6 b n e r 基较好的解决了数值逼近中的一些问题 2 2 。 1 9 9 6 年，h o n g 研究多项式复合下g r 6 b n e r 基的性质与计算，1 9 9 8 年得到了一 个经典结论：多项式复合e 与g r 6 b n e r 基的计算可交换当且仅当复合e 既与项 序相容又与非整除性相容【3 9 】。接着，g u t i e r r e z 也得到了一个相应结果：复合 e 与既约g r 6 b n e r 基的计算交换当且仅当复合e 与项序相容且e 是单排列的 【3 2 】上述两个结果为研究复合下的g r 6 b n e r 基奠定了很好的基础，尤其是研究 变量替换后g r 6 b n e r 基的变化及简化g r 6 b n e r 的计算起着关键性的作用。 下面简单叙述与本文直接相关的几个问题的研究现状，并结合介绍本文的主 要工作。 一1 一 博士学位论文 一、多项式复合与g r 6 e b n e r 基的关系 多项式复合是多项式代数的一种常见运算，g r 6 b n e r 基是代数与符号计算研 究的核心问题之一，由于应用的广泛性，近几十年来已形成了一套系统的g r 6 b n e r 基的理论与方法1 9 9 8 年，h o o nh o n g 3 9 关于多项式复合与g r 6 b n e r 基得到 了下列经典结论：， h o n g 定理多项式复合e 与g r 孙n e r 基的计算可交换当且仅当0 既与 项序 是相容的又与非整除性是相容的 这里，多项式复合e 与g r 6 b n e r 基的计算可交换是指对任意g r 6 b n e r 基g ， g 。e 仍是g r 6 b n e r 基；多项式复合e 与项序 相容是指：对任意项p ，g 号 p o l t ( e ) g o l t ( e ) ；e 与非整除性相容是指：对任意项p ，口，p t g 号p 。1 t ( e ) 十g o l t ( e ) 同年，g u t i e r r z e 等人 3 3 】得到了下述结论： g u t i e r r z e 定理多项式复合e 与既约g r 6 b n e r 基的计算可交换当且仅当 e 既与项序 是相容的且e 是单排列的 以后几年，在这方面一直未有好结果h o n g 定理的证明非常复杂、冗长， 而且它们只考虑了多项式复合与整体g r 6 b n e r 基的关系，但在实际问题中，我们 经常碰到多项式复合与某类g r 6 b n e r 基的关系本文第二章给出了h o n g 定理 的新证明，它有很强的技巧性，且证明过程相当简洁，为这方面的研究提供了一 种新的方法进而，我们分别讨论多项式复合与泛g r 6 b n e r 基、单项式g r 6 b n e r 基、齐次g r 6 b n e r 基、f 一齐次g r 6 b n e r 基、a g r 6 b n e r 基的关系并给出了相 应的等价条件尤其是r 一齐次g r 6 b n e r 基非常具有广泛性，它的研究结果涵盖 了这方面以前的许多结果，为研究多项式复合与g r 6 b n e r 基的关系开辟了一条 新的途径 二、多项式复合与项序的相容性 我们知道，多项式复合与g r 6 b n e r 基的计算可交换的一个重要条件是多项 式复合与项序相容从h o o n 定理看到，上面多项式复合与项序相容是抽象的， 很难判断1 9 9 8 年，h o n g 提出了一个开问题：给出判断多项式复合与项序相 容的具体算法本章在第三章通过将项序用矩阵表示这一新方法，经过详细论证 一9 一 多项式复合与g r 6 b n e r 基的性质与计算研究 给出上面判断的切实可行的方法，这一判断方法可通过算法程序实现，该方法简 单且具有可操作性 在研究多项式复合与齐次g r 6 b n e r 基、r 一齐次g r 6 b n e r 基的计算可交换的 等价条件时，我们也将面临多项式复合与项序齐次相容、i 、齐次相容等问题我 们将通过详细论证给出上面判断的具体算法，该算法不再是纯抽象的，具有可操 作性 三、非交换代数的g r 曲n e r 基 1 9 9 8 年，b e r g m a n 首先提出了非交换代数的g r 6 b n e r 基的理论，1 9 9 0 年， 、v e i s p f e n n i n g 等人研究了可解代数的非交换g r 6 b n e r 基，1 9 9 4 年，刘金旺研究 了微分算子环( 非交换代数) 单边理想的g r 6 b n e r 基1 9 9 5 年，d a v i d 等人研 究了c l i 肋r d 与g r a l s s m a n n 代数单边理想的g r 6 b n e r 基2 0 0 3 年，刘金旺等 人研究了双斜多项式环( 可解代数) 双边理想的g r 6 b n e r 基及成员问题，解决了 g a t e v a 等人于1 9 9 6 年提出的相应开问题关于微分算子环的g r 6 b n e r 理论已有 的结论很少，本文第四章继续研究该问题，并得到了一些有趣的结果，使得某些 单边理想的g r 6 b n e r 基易于计算关于c l i 助r d 与g r a s s m a n i i 代数( 非交换) 只 有单边理想g r 6 b n e r 基的一些结果，本文第四章研究该代数双边理想的g r 6 b n e r 基；证明了双边理想g r 6 b n e r 基的存在性并给出了具体算法，从而解决了该代数 双边理想的成员问题接着我们讨论非交换代数( 四元素除环上n 元多项式环) 中多项式复合与g r 曲n e r 基的性质与计算问题 一3 一 i r 一 u 多项式复合与g r 6 b n e r 基的性质与计算研究 第二章多项式复合与g r 6 b n e r 基 2 1 预备知识 设刚z 1 ，z 2 ，z n 】是域k 上关于变量z 1 ，2 2 ，z 礼的多项式环【5 6 】 令是非负整数集合，n 是一个给定的正整数，z 1 ，z 2 ，z n 表示环r 上的n 个变元令集合 丁m = z 芋1 z 呈2 z “fq i ，i = 1 ，2 ，n ) ， 即t m 是n 个变元z 1 ，z 2 ，z n 的幂积的集合我们记z ? 1 z 呈2 z n = x a ， 其中x = ( z 1 ，z 2 ，z n ) ，q = ( q 1 ，a 2 ，乜n ) n 对于t m 中的任何两个元 素x 。= z 宇1 z 呈2 z n 和x 卢= z 2 1 2 2 2 z 争，定义它们的乘法为： x q x 卢= x a x 卢= z 宇1 + 尻z ；2 w 2 z 竺n + 风，或者由环r k l ，z 2 ，z n 】中的乘法得到上式， 易见，t m 是一个幺半群 ：， 。 所谓盯是集合t m 上的一个全序( t o t do 耐e r ) ，是指对任意给定的t m 中的 两个元素x q 和x 卢，下面的三个关系之一必须成立，而且只有一个成立： x q 盯x 卢，x a = x p ，x 卢 盯x q 如果无须特别标注盯，上式可简记为 x q x 卢，x q = x 卢，x p 仃1 ( 2 ) 对任何x a ，x 卢，x 1 丁m ，如果x 口 盯x 卢，则x q x 7 盯x 卢x ，y 一5 一 博士学位论文 首先任意选定集合t m 上的一个项序盯，由于仃已选定，我们总将相对盯 的小于关系 通常将t m 上的项序也称为环 a = r p ，z n 上的项序当然要事先给定基环兄对于多项式环4 中的任 意一个非零多项式厂，相当于给定的环4 上的项序 x a 。 x 卧定义 l t ( ，) = x ，即l t ( ，) 表示，的首项幂积； l c ( 厂) = n ，即l c ( 厂) 表示厂的首项系数； 1 m ( ，) = o - xq 1 ，即l t ( ，) 表示- 厂的首项； 1 m ( o ) = 1 c ( o ) = 1 t ( o ) = o ； s u p p ( ，) = x 。t mic ( ，z n ) o ) ，为在厂中出现的幂积的集合， l o g ( x d ) = a ，为幂积x n 的幂指数 例1 t m 上相对z 1 z 2 z n 的字典序( 1 e x i c o g r a p h i c a lo r d e r ) ，简 记为l e x ，定义如下： 对于a = ( q 1 ，a n ) ，p = ( 卢1 ，尾) n ，则 x q l e xx 卢兮存在o 尼n 一1 ，使得= 岛，歹= o ，1 ，忌，和 口七+ 1 凤+ 1 ( 约定乜o = 阮) 若n = 2 ，则 1 z 2 z ； z ； z 1 z l z 2 z l z ； 的次数字典序( d e g r e el e x i c o g r a p h i c a l o r d e r ) ，简记为d e 9 1 e x ，定义如下： 对于q = ( q 1 ，a n ) ，卢= ( 卢1 ，风) n ，则 x 。 d e l e xx 卢 。 有序典字按或和 屈厥 1 1 9 1 1 9 # 卢 = x n k 一 弋 n 拉 n 仁 n x ，i_-_-。，、l_-ll 多项式复合与g r 6 b n e r 基的性质与计算研究 若n = 2 ，则 1 z 2 z 1 z ； z l z 2 z ； z ； z l z ； z ；z 2 z n 的次数反字典序( d e g r e er e v e r j e 1 e x i c o g r a p h i c a lo r d e r ) ，简记为d e g r e v l e x ，定义如下： 对于a = ( a 1 ，q n ) ，卢= ( p 1 ，风) ，贝4 x a 屈 注对于n = 2 ，d e g l e x 和d e g r e v l e x 给出相同的序，但对礼 2 ，则给出不 同的序例如n = 3 ，相对z 1 z 2 z 3 ，有 z ；z 2 2 3 d e g l e xz l z ；，z ；。2 z ； ：d e l e xz l z i z 3 ， 和 z i z 2 2 3 d e g r e v l e xz l z ；，z ；z 2 z ；+ d e g r e l e xz l z ；z 3 9冀99q t 以上三种序是最常用的当然t m 上可有许多种项序，但从序分类定理来 看，字典序是最基本的在后面可以看到，g r 孙n e r 基的计算是依赖于序的选取 的，序选的好，可以使一些问题的计算变得简单 我们讲述求域上多项式环中理想的g r 6 b n e r 基的b u c h b e r g e r 算法所依赖的 除法算法，i 整个这节，始终设a = k b ，z n 】为域审上n 变元多项式环，盯为任意 给定的环a 上一个项序，并将 盯简记为 的首项幂积 ，关于项序 的首系数 ，关于项序 的首式，即，l m ( ，) = l c ( 埘t ( ，) f o r ，o ，1 m ( o ) = o k p ，z n 的非空有限子集 集合 l t ( ) i 日) 由g 生成的理想 厂与夕的最大公因式 p 与g 的最小公倍式 一9 一 动力曲 ， )p，7 9 m，寥 g 玑 山国、魄叫叫 k m薹|i斗_蝴即删刚岫 博士学位论文 e 一个有序多项式组( 口1 ，如) ，o 吼k b l ，z n 1 t ( e )有序多项式组( 1 t ( p ) ，l t ( 以) ) 1 m ( e )有序多项式组( 1 m ( 口1 ) ，l m ( ) ) s ( ，口) 厂与夕的s 一多项式，即，堕业器皆必厂一堕雩铲夕 本章，我们固定一个项序 ，称g = 9 1 ，9 2 ，玑) 是理想，的g r 6 b n e r 基，如果对任意非零厂j ，存在i ，1si s 使得l t ( 吼) il t ( ，) 我们说，g 是 一个g r 曲n e r 基是指g 是i d e a l ( g ) 关于项序 的一个g r 6 b n e r 基 定义1 7 多项式复合e 与g r 6 b n e r 基的计算可交换如果对任意g r 曲n e r 基g ，g 。e 仍是g r 6 b n e r 基 定义1 8 多项式复合e 与项序 是相容的，如果对所有项p 与g ，有 p g p ol t ( e ) gol t ( e ) 定义1 9 多项式复合e 与非整除性是相容的如果对所有项p 与g ，有 p 十g 今p 。f t ( e ) 十口of t ( e ) 参看 3 9 】，我们容易得到下列引理 引理1 1 0 ( 1 )( ，9 ) oe = 厂oe 夕。e ( 2 )( ，+ 夕) oe = 厂oe + 夕oe ( 3 )l m ( p oe ) = po1 m ( e ) ( 4 )l t oe ) = po 1 t ( e ) 引理1 1 1 设 ( a ) 多项式复合e 与项序 是相容的； ( b ) 对任意多项式，有 ( a ) l m ( ，oe ) = l m ( ，) ol m ( e ) ( b ) 1 t ( 厂oe ) = 1 t ( 厂) ol t ( e ) 一1n 一 多项式复合与g r 6 b n e r 基的性质与计算研究 那么( a ) ( b ) 引理1 1 2 设 ( a ) 多项式复合o 与非整除性是相容的； ( b ) l t ( e ) 是排列幂的，即，l t ( e ) = ( z ：，z 笔，z 象) ，这里丌是( 1 ，2 ，扎1 的一个排列，且入1 ，入2 ，a n 0 那么( a ) 令( b ) 引理1 1 3 设 ( a ) l t ( e ) 是排列幂的，即，l t ( e ) = ( z ：，z 笔，z 麓) ，7 r 是( 1 ，2 ，礼) 的一个排列，a 1 ，a 2 ，a n 0 ； ( b ) 州gl c m ( p 。1 t ( e ) ，qol t ( e ) ) = 1 c m ( p ，q ) 。l t ( e ) 那么( a ) ( b ) 我们看到，l t ( e ) 是排列幂的当且仅当1 t ( ，l t ( 巳) 是互素的，且l t ( 1 ， 这里i j ，i ，歹= 1 ，2 ，扎 引理1 1 4 下列( a ) 与( b ) 是等价的： ( a ) g = 夕l ，夕2 ，吼) 是g r 6 b n e r 基； ( b ) 对任意仇与纺g ，i j ，存在 l ， 2 ，也使得 ( a ) s ( 9 i ，缈) = 1 9 1 + 2 9 2 + + 危t 夕t ( b ) 对每一七，= o 或l t ( ) f t ) 相容也与非整除性相容 那么( a ) 号( b ) 一1 1 博士学位论文 2 2h o n g 定理的新证明 在 3 9 】，h o n g 定理的证明非常复杂、冗长，本节我们使用新方法给出h o n g 定理的证明，它是简洁清楚的，并且该方法在代数与符号计算中有很好的运用 充分性假设 9 1 ，夕2 ，仇) 是一个g r 6 b n e r 基；设1 i jst 由引理 1 1 4 ，存在h 1 ，h 2 ，也使得 v 尼，允后= o ，或1 t ( 七鲰) 1 c m ( 1 t ( 夕i ) ，l t ( 缈) ) 令 a = l c m ( 1 m ( 吼) ，l m ( 9 i ) ) l m ( 仇) ，殇= l c m ( 1 m ( 吼) ，1 m ( 劬) ) l m ( 缈) ； 由引理1 1 0 ，1 1 1 ，1 1 2 ，1 1 3 ；有 1 c m ( 1 t ( 9 i 。e ) ，l m ( 坊。e ) ) l m ( 阢。e ) = l c m ( 1 m ( 仇) ol m ( e ) ，l m ( 仇) o1 m ( e ) ) l m ( 俄) oi m ( e ) = 1 c m ( 1 m ( 仇) ，l m ( 劬) ) ol m ( e ) l m ( 仇) 。l m ( e ) = ( 1 c m ( 1 m ( 吼) ，l m ( 劬) ) l m ( 吼) ) ol m ( e ) = 仇。l m ( e ) 同理，1 c m ( f m 慨。e ) ，l m ( 乃oe ) ) 1 m ( 易oe ) = 功ol m ( e ) 显然 s _ l g t ，9 0 = 仇g t p j g j 且 t s ( 仇，缈) oe = ( 肌仇一岛卯) 。e = oe 纵oe 惫= l p ioe = p i 。l m ( e ) + 吼，l m ( 吼) 魏ol m ( e ) ， 聊oe = 乃ol m ( e ) + 劬，l m ( 劬) 鳓ol m ( e ) s ( 9 i 。e ，缈。e ) = 纯ol m ( o ) 9 ioe 一功。f m ( e ) 。e = ( 仇。e 一吼) 仇oe 一( 功。e 一劬) 跏。e 一1 2 一 七9七 h 。随 = 鲂b s 多项式复合与g r 6 b n e r 基的性质与计算研究 = 鼽。e 仇。e 一办oe 卯oe + 劬缈。e 一吼阢oe = i 吼一功劬) oe + 劬劬oo 一吼阢。e = s ( 劬，卯) 。e + 劬功oe 一吼仇oe = ：1 。e 肌oe + 劬劬oe 一吼玑6e 显然，v 七 1 t ( 七。e 玑o e ) = l t ( 饥鲰) o l t ( e ) l c m ( 1 t ( 仇) ，l t ( 劬) o l t ( o ) ) = l c m ( 1 t ( 肌o e ) ，l t ( 劬o e ) ) 且 l t ( 劬缈oe ) = l t ( ) l t ( 缈。e ) 乃。l t ( e ) ( 协) l t ( e ) = ( 乃l t ( 缈) ) ol t ( e ) = l c m ( 1 t ( 仇) ，1 t ( 吼) ) 。1 t ( o ) = l c m ( 1 t ( 夕ioe ) ，l t ( 缈oe ) ) 同理，l t ( 吼仇oe ) 1 我们分以下几步证明 1 v i j ，晚十 假设易= 吼 因为 z i ，+ 1 ) 是g r 6 b n e r 基，那么 吼，岛+ 1 也是 g r 6 b n e r 基，显然， 仇，仇九+ 1 ) = 仇，如+ 1 ) 不是g r 曲n e r 基矛盾： 2 v i j ，l t ( 和l t ( 易) 是互素的 设d = 夕c d ( 仇，巳) ，以= d 。彰，巳= d 。嘭；或= z 仇( 彰) + 玩，够= 2 m ( 够) + 吩，这 里f m ( ) o 如果p g ，那么p 口 因此pol t ( e ) gol t ( e ) 4 v p v g ，p g 今p 。l t ( ) 口ol t ( e ) 假设p 。l t ( o ) pol t ( e ) = 1 t oe ) ，l t oe + g oo ) = l t ( g 。e ) l t ( p 。e ) 矛盾因此， pof 亡( e ) qo1 t ( e ) ，多项式复合e 与项序 是相容的 我们知道，多项式复合e 与非整除性相容是容易判断的，我们在第三章将 给出多项式复合e 与项序相容的判别方法通过上面h o n g 定理的简单证明，我 们对h o n g 定理有了更好的理解下面我们讨论多项式复合与一些特殊g r 6 b n e r 基的关系，它们在代数与符号计算中有很好的应用 2 3 多项式复合与单项式g r 曲n e r 基 本节，我们讨论在什么条件下多项式复合与g r 6 b n e r 基的计算可交换，同 时，我们得到了一些有趣的结果 设，9 k z 1 茁2 ，茁n ，d e g ( ，) ，d e g ( 9 ) 1 ，且 ，= p i - p ；n p ；h ，g = p i 。1 p ；。p ；拍 这里p 1 ，p 2 ，p 。是两两互素的，且v i ，仇是不可约多项式，m o z 入1 i ，入2 0 o 我们称上面厂与夕的分解是厂与夕的标准分解 一般，命题( a ) 是不正确的 ( a ) v i 歹，l t ( 肌) 与1 t 慨) 不互素，且a 1 i o ，a 2 j o = 卺= 器 如果v i ，歹( i 歹) ，( a ) 是正确的，我们就说厂与夕是弱互素的 定理3 1 如果l m ( - 厂) 与l m ( 夕) 是互素的，那么，与夕是弱互素的 一1 4 多项式复合与g r 6 b n e r 基的性质与计算研究 证明 因为l m ( ，) = ( 2 m - ) ) a t - ( f m 2 ) ) 沁2 ( f m ( 仇) ) h s ，l m ( 9 ) = ( 1 m ( p 。) ) h ( 1 m ( p 2 ) ) 蛔( 1 m ( 仇) ) 乜如果存在p i ，聊( i 歹) 使得l m ( 鼽) 与l m ( 巧) 不互素， a 1 i o ，a 2 j o 因( 1 m ( 鼽) ) a - il m ( ，) ，( 1 m ( 功) ) a 2 j l m ( 夕) ，那么l m ( 厂) 与l m ( g ) 不互素矛盾故厂与g 是弱互素的 例1 设，= z ；z 2 ，夕= z l z 2 ，显然，与夕，( 1 m ( ，) a n dl 血( 夕) ) 不互素，但 ，与夕是弱互素的 例2 设k 是实数域，且厂= z 1 ( z 2 + 1 ) ，夕= ( z ；+ 1 ) 显然厂与夕是互素的 但，= z 1 ( z + 1 ) o ( z 2 + 1 ) ，夕= z 2 ( z i + 1 ) ( z 2 + 1 ) o ，对p 1 = z 1 ，p 2 = z ；+ 1 ；f m ( p 1 ) 与f m ( p z ) 不互素，且鲁= ：瓷= j 我们看到，与夕不是弱互素的 定理3 2 如果，与夕是弱互素的，那么，入与夕盯也是弱互素的，这里 入0 ，口0 证明假设，与夕的标准分解为： ，= p i - - p ；地p ；h ，夕= p i 2 1 p ；2 2 p ；2 3 那么 i ，a = p i 札p 1 2 p ；a h ，严= p 子蛔醒a 2 2 形入2 8 - 。： 假如l m ( p 1 ) 与f 仇( 乃) ( i j ) 不互素，且a a n o ，盯a 2 j o ，因，与夕是弱互素 的，那么寰= 妥舞= 妥等= 舞因此，a 与夕盯也是弱互素的 定理3 3 如果，与夕是弱互素的，那么 ，夕 是g r 6 b n e r 基 、 证明 设d = g c d ( ，9 ) ，我们证明l m ( 舌) 与l m ( ) 是互素的由，与g 的 标准分解，我们知道 d = p p 挈p ，如= m i n a 1 i ，a 2 i ) ，1 i s 如果1 m ( 舌) 与l m ( ) 不互素，那么存在p t ，乃( i 歹) 使得l m ( p i ) 与l m ( 功) 不互素，且a l i 一如 0 ，a 2 j 一岛 0 故a n a 2 i 0 ，a 巧一入1 j 0 ，即 a 2 i a 1 j 因厂与9 弱互素，有卺= 等矛盾 1 由定理3 2 ，3 3 ，易得 一1 5 博士学位论文 定理3 4 如果厂与9 弱互素，那么 ，a ，9 仃) 是g r 6 b n e r 基，这里a o ，盯 定理3 5 对任意非负整数a ，仃， ，入，旷 是g r 6 b n e r 基当且仅当，与夕弱 互素的 证明充分性由定理3 4 直接可得 必要性假设厂与夕不弱互素那么，在，与9 的标准分解中存在，a ，岛( j j ) 使得z m ( 耽) ，z m ( 聊) 是不互素的，且a l i o ，a 2 j o ，但笔等不妨设 卺 等，那么a 2 i a 1 j a 1 i 。a 巧令a = a 2 i + a 巧，仃= a 1 i + a 1 j ，那么 入a “= ( a 2 i