（基础数学专业论文）求解某些特殊序列发生函数的自动化方法.pdf

摘要 本文研究了某些特殊组合恒等式的自动证明算法及某些特殊序列发生函数的自动求 解算法论文的主要内容如下， 第一章简要地介绍了组合恒等式证明理论的发展进程 第二章介绍组台恒等式自动证明算法的理论基础，即完整性函数理论与非交换算子 代数理论 在第三章中，针对现有z e i l b e r g e r 算法所需内存较大，有些恒等式，比如d i x o n 公式， 无法成功地得以证明的问题，我们将e u c l i d e a n 算法推广到非交换算子代数c ( 靠，鼠，n ，k ) 下，完成非交换环境中的消元，并利用这一方法替代s y l v e s t e r 的析配消元法来改善z e i l - b e r g e r 算法，从而完成可终止超几何级数恒等式( = 项式系数恒等式) 的自动证明根 据改进的z e i l b e r g e r 算法，我们编写了m a p l e 程序，并验证了【2 6 】中所证明的恒等式，包 括s a a l s c h u t z 恒等式，v a n d e r m o n d e - c h u 卷积公式，d i x o n 公式以及 1 0 】中的1 9 6 个恒 等式而且，依据吴方法的基本思想，我们解决了非交换算子代数中多个变量的消元问 题，并提出多变量可终止超几何级数恒等式的自动证明算法在这一章的最后，我们简 要地介绍了非交换算子代数c ( 巩，d 。，$ 埘中的主要结论，并讨论了带有积分号的恒等式 的自动证明问题 基于第三章的讨论，在第四章中。我们将发生函数看作是既含有连续变量又含有离 散变量的特殊形式的恒等式，从而给出某些特殊序列发生函数的自动求解算法在这一 章，我们首先提出了普通幂级数发生函数与指数发生函数的自动求解算法，利用这一算 法，我们计算了一些正交多项式以及特殊组合数的发生函数接着根据第三章提出的非 交换环境下消去多个变量的算法，我们研究了如何求解双变量普通幂级数发生函数与混 合型的发生函数最后我们将讨论推广到一般形式的发生函数上 关键词：组合恒等式；发生函数；完整性函数；非交换算子代数；z e i l b e r g e r 算法 a b s t r a c t i nt h et h e s i s ，a l g o r i t h m sf o rv c r i f y i n gs o m es p e c i a lc o m b i n a t o r i a li d e n t i t i e sa n dc o m p u t i n g t h eg e n e r a t i n gf u n c t i o n so fs o m e s p e c i a ls e q u e n c e sa r es t u d i e d t h em a i n c o n t e n t so ft h i st h e s i s c a l lb es u m m a r i z e da sf o l l o w s ： c h a p t e r1d e s c r i b e st h ee v o l u t i o no ft h ep r o o ft h e o r yo fc o m b i n a t o r i a li d e n t i t i e s c h a p t e r2i sa b o u tt h ef u n d a m e n t a lt h e o r yo ft h ea u t o m a t i ca p p r o a c ht oc o m b i n a t o r i a l i d e n t i t i e s ，t h a ti s ，h o l o n o m i cf u n c t i o n sa n dn o n c o m m _ 1 1 t a t i v eo p e r a t o ra l g e b r a s b e c a u s et h e p r e s e n tz e i l b e r g e ra l g o r i t h mr e q u i r e sal o to fm e m o r ys ot h a ts o m ei d e n t i t i e s ， s u c ha sd i x o n si d e n t i t ：lc a nn o tb ev e r i f i e ds u c c e s s f u l l y , w e g e n e r a l i z et h ee u c l i d e a na l g o r i t h mt o t h en o n e o m m u t a t i v e o p e r a t o ra l g e b r ac ( 晶，瓯，n ，k ) i nc h a p t e r3 ，a n de s t a b l i s ht h ee l i m i n a t i o n i nt h en o n c o m m u t a t i v ec o n t e x t b yt h eu s eo ft h ee l i m i n a t i o ni n s t e a do fs y l v e s t e r s d i a l y t i c e l i m i n a t i o n ，w em o d i f yt h ez e i l b e r g e ra l g o r i t h ms ot h a tt e r m i n a t i n gh y p e r g e o m e t r i ci d e n t i t i e s ( b i n o m i a l c o e f f i c i e n t si d e n t i t i e s ) c a nb ev e r i f i e da u t o m a t i c a l l y b e s i d e s ，w i t ht h e m a p l ep r o g r a m b a s e do nt h em o d i f i e da l g o r i t h m ，w eh a v ep r o v e nt h ei d e n t i t i e si n 2 6 】，i n c l u d i n gs a a l s c h u t z s i d e n t i t y ，t h ev a n d e r m o n d c - c h uc o n v o l u t i o nf o r m u l a ，a n dd i x o n si d e n t i t y ，a n d1 9 6i d e n t i t i e s i nf 1 0 1 m o r e o v e r ，w i t ht h ew u m e t h o d ，w ec o n s t r u c tt h ew a yo fe l i m i n a t i n gs e v e r a lv a r i a b l e s a n dd e v e l o pa na u t o m a t i ca p p r o a c ht op r o v i n gt e r m i n a t i n gh y p e r g e o m c t r i ci d e n t i t i e so fs e v e r a l v a r i a b l e s a tt h ee n do ft h i sc h a p t e r ，w ei n t r o d u c et h em a i nr e s u l t si nc ( d x ，d ，z ，y ) a n d d i s c u s st h ep r o b l e mo f v e r i f y i n gt h ei d e n t i t i e sw i t ht i l ei n t e g r a ls i g n b a s e do l lt h ed i s c u s s i o no fc h a p t e r3 ，i nc h a p t e r4 ，w ec o n s i d e rt h e g e n e r a t i n gf u n c t i o n s a ss p e c i a li d e n t i t i e sw h i c hc o n t a i nc o n t i n u o u sv a r i a b l e sa sw e l la sd i s c r e t eo n e s ，a n de s t a b l i s h a l g o r i t h m sf o rc o m p u t i n gt h eg e n e r a t i n gf u n c t i o n so fs o m es p e c i a ls e q u e n c e s i nt h i sc h a p t e r ， w ef i r s tg i v et h e a l g o r i t h mf o rc o m p u t i n gt h eo r d i n a r yp o w e rs e r i e sg e n e r a t i n gf u n c t i o n sa n dt h e e x p o n e n t i a lg e n e r a t i n gf u n c t i o n s b yt h eu s eo ft h i sa l g o r i t h m ，w ec o m p u t et h e g e n e r a t i n gf u n c t i o n so fs o m e o r t h o g o n a lp o l y n o m i a l sa n d s o m es p e c i a lc o m b i n a t o r i a l s e q u e n c e s n e x t ，w es t u d y t h em e t h o do fc o m p u t i n g2 - v a r i a b l eo r d i n a r yp o w e rs e r i e sg e n e r a t i n gf u n c t i o n sa n d m i x e d t y p e g e n e r a t i n gf u n c t i o n sw i t ht h ea p p r o a c ht oe l i m i n a t i n gs e v e r a lv a r i a b l e si nt h en o n c o m m u t a t i v e c o n t e x td e v e l o p e di nc h a p t e r3 a n da tl a s t ，w eg e n e r a l i z eo u rd i s c u s s i o nt ot h eg e n e r a t i n g f u n c t i o n sw i t hg e n e r a lf o r m s k e y w o r d s ：c o m b i n a t o r i a li d e n t i t y ；g e n e r a t i n gf u n c t i o n ；h o l o n o m i cf u n c t i o n ；n o n c o m m u t a t i v eo p e r a t o ra l g e b r a ；z e i l b e r g e ra l g o r i t h m i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的 研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也 不包含为获得大连理工大学或其他单位的学位或证书所使用过的材 料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明 确的说明并表示了谢意。 作者签名：兰年车一日期；塑! ：! ：! ! 1 绪论 母个恒等式( i d e n t i t y ) 郡是个数学方程，它表明两个看起来不i 司的事物实际上是相 同的，或者至少在某些条件下是相同的比如说“2 + 2 = 4 ”是一个恒等式，尽管它看起 来可能太过平凡； “渖+ 1 ) 2 = l + 2 x + $ 2 也是一个恒等式，这个恒等式可能要更高级 一些，因为它畲有_ 个自由的参量“z ”，并且表明无论z 取什么实数或复数，这个等式都 会成立 数学的许多分支中都有漂亮的恒等式存在，比如以下几个例子： a ( 坐笔乎) 2 + b ( 坐笔霉) + c _ 0 ， v e + f = 2 d e t ( a b ) = d e t ( a ) d e t ( b ) ， i 。，譬，z ，n zjx y z o ，礼 2 ，z “+ “= 名“) i = o ， 9 5 8 0 0 4 + 2 1 7 5 1 9 4 + 4 1 4 5 6 0 4 = 4 2 2 4 8 1 4 ，+ m 妻= l 两矗= f i 巧南 组合数学是恒等式的一个重要的来源，存在着许多迷人的例子，比如以下的几个： 加12_(：)，j=o x d jla ， 、nj ；+ 量。( 坝拟。净。蒹。( 了) ， 唧 m l 扩。1 嘉 叫+ 萎1 ( + 1 r 1 ；， 1 一 e 霎( - 1 ) 3 刊m 黜， 8 一) = ( 一1 ) ”然， s = 0 、，、一7 莩c 叫8 g ：) g ：驰：) = 警， 薹去羔卜，”g ) ( 2 ”二2 m ) 扩一狮矿= 万去 漂亮的恒等式总是激励着数学家们为它们寻找漂亮的证明，这些证明可能表明了等 式两边的组合的或其他的意义，也可能仅仅以它们的简洁和精致使人们为之目眩在这 盔整堡三盔堂塑主堂垡堡奎! 塞堡苤些壁蕉壁型丝皇里塑盟旦塾! 堕整一 篇论文中，我们就将讨论与恒等式证明相关的问题当然，我们不可能研究所有的恒等 式，我们仅仅研究在组合数学中出现的一些特殊的恒等式 在讨论之前，让我们首先回顾一下历史组合恒等式证明理论的发展大致经历了三 个阶段 最初人们只能根据恒等式自身的特点来处理它们，重要的证明方法有递归方法、反 演方法、发生函数方法、分拆多项式方法和算子方法( 参见【1 6 ) ，尽管许多特殊的方法是 巧妙而有效的，但是缺乏一个统一的广泛适用的方法 后来，人们认识到一大类组合恒等式，即那些包含二项式系数及阶乘的恒等式，事 实上仅是一些非常一般的超几何级数恒等式( h y p e r g e o m e t r i ci d e m i w ) 的特例这样，证明 了一个超几何级数恒等式就相当于证明了好几个二项式系数恒等式( b i n o m i a lc o e f f i c i e n t s i d e n t i t y ) ，因为对超几何级数恒等式的参数取特殊值，就得到相应的二项式系数恒等式 在这里，超几何级数具有形式( 参见【1 5 】) ： ，蜀 ：x 刊2 轰甓跺姑蔷， 其中( 。) 为升自阶乘，定义为 ，、jn ( 口+ 1 ) ( o + 2 ) a + 一1 ) ，i f 女1 ； 旧灿一l1 ， i fk = 0 超几何级数理论在1 9 世纪由c f g a u s s 创立，并且在其发展过程中，有许多一般的 恒等式被发现，但是直到1 9 7 4 年，人们才认识到上述问题，也就是说，从超几何级数理 论的创立到其应用到二项式系数恒等式上间隔了相当长的时间 在上世纪9 0 年代初期，初文昌深入研究了超几何级数理论，并利用g o u l d h s u 反演 ( g o u l d h s ui n v e r s i o n ) 1 1 1 对超几何级数恒等式进行了分类g o u l d - h s u 反演是： 令他) 与 b i 为两个数列使得对任意非负整数z ，n ， n 妒陋，n ) = i i ( a i + 以$ ) 0 i = 1 并且令砂( z ，0 ) = 1 ，则如下反演公式成立 ，( n ) = ( 一1 ) k = 0 g c n ) = ( 一1 ) k = o ( 1 1 ) ( 1 2 ) 初文昌的方法是，对某个给定的超几何级数恒等式，将其参数特殊化后看作( 1 1 ) ，应 用g o u l d - h s u 反演得到( 1 2 ) ，则这两个恒等式在g o u l d - h s u 反演的意义下是等价的这 样，初文昌证明了超几何级数恒等式可以分为三类 2 七 ， 七 驴 h + 地 、化p 加b 整! 里堕堕 组合恒等式证明理论发展的第三个阶段经历了与第二个阶段类似的时间滞后，但是 这次间隔要短的多上世纪4 0 年代，s i s t e rm a r y c e l i n ef a s e n m y e r 提出了自动发现超几 何和式所满足的递归关系的方法直到1 9 8 2 年，才由d o r o nz e i l b e r g e r 2 5 】发现， s i s t e r c e l i n e 的方法同时也为超几何级数恒等式的自动证明提供了工具z e i l b e r g e r 认识到以下 事实t 如果要证明恒等式女s u m m a n d ( n ， ) = a n s w e t ( ) ，我们可以 找到等式左端的和式所满足的递归关系； 通过代换证明a n s w e r ( n ) 也满足同样的递归关系； 验证等式两端适合相同的初始条件 在这一认识的基础上，z e i l b e r g e r 2 6 利用完整性系统理论( h o l o n o m l es y s t e m ) 提出了 特殊函数恒等式的自动证明方法z e i l b e r g e r 的这一方法不仅为恒等式的自动证明提供 了一个般性的理论框架，而且还提出了数学上及算法上具有挑战性的问题，例如，非交 换算子代数中的消元i _ 可题等等特别地，z e i l b e r g e r 在【2 6 】中给出了自动证明可终止超几 何级数恒等式( 二项式系数恒等式) 的具体算法及m a p l e 程序接着，利用g o s p e r 算法， z e i l b e r g e r 提出了寻找组合和式所满足的递归关系的 c r e a t i v et e l e s c o p i n g ”算法 2 7 ，2 8 ，这 一算法比s i s t e rc e l i n e 的方法要快的多同样地，利用g o s p e r 算法，w i l l 与z d l b e r g e r 2 3 发展了w z 对理论( w z - p a i r s ) w z 对理论可以为一类组合恒等式提供精致的证明，而且 还能够用来寻找新的恒等式在1 2 4 】中，w i l f 与z e i l b e r g e r 又将恒等式的证明理论推广 到多重和式、叮和式等等更进一步，p e t k o v e k 给出了求解多项式系数线性递归方程 的算法，利用p e t k o v e k 的算法及前面所提及的寻找递归关系的算法，我们就可以确定一 个超几何和式是否具有封闭形式这些研究成果已被集中地收录到 15 中 除他们之外， c h y z a k 【5 ，6 ，7 】，p a u l e 1 4 ，t a k a y a m a 1 9 l 等人在这方面也作出了卓越的 贡献这些数学家的辛勤工作不仅极大地推动了恒等式证明理论的发展，而且还为我们 的学习和工作提供了便利正如k n u t h 在 1 5 的前言中所说的：为了计算二项式系数和 式及许多在实际工作中频繁产生的类似的公式，我们不再需要费尽心思去求解，我们现 在可以采用一种机械化的方法相当系统地找到答案 基于 2 6 】，我们研究了可终止超几何级数恒等式( t e r m i n a t i n gh y p e r g e o m e t r i ci d e n t i t y ) 的自动证明问题，并进一步讨论了某些特殊序列发生耐敦( g e n e r a t i n gf u n c t i o n 或者g f ) 的自动求解问题这篇论文的结构是这样的：在第二章，我们将介绍恒等式自动证明算 法的理论基石，即完整性函数理论与非交换算子代数理论非交换算子代数中的消元问 题以及可终止超几何级数恒等式的自动证明算法将在第三章中讨论最后，在第四章， 我们将把发生函数看作是特殊的恒等式，利用类似于第三章的方法给出自动求解特殊序 列发生函数的算法，并将这算法从通常的普通幂级数发生函数及指数发生函数推广到 一般形式的发生函数上 3 2 完整性函数及非交换算子代数 2 1 完整性函数 一个幂级数，( $ ) = o 一称作是d - 有限的( d i f f e r e n t i a b l yf i n i t e 或者d - f i n i t e ) ，如果， 的导数张成c ( z ) 上的一个有限维向量空间，其中c ( x ) 是关于变量。的有理函数域这等价 于说，满足一个多项式系数线性微分方程一个序列h ) 称作是p 一递归的( p o l y n o m i a u y r e c u r s i v e 或者p - r e c u r s i v e ) ，如果它满足一个多项式系数线性递归方程s t a n l e y 在 1 7 】中 系统地研究了d 有限幂级数( 单变量的情形) 与p 递归序列这两个概念是密切相关 的：一个序列( 啦) 是p 递归的当且仅当其发生函数，( z ) = a i 是d 有限的 d 有限性的概念可以直接推广到含多个变量的幂级数的情形，但是p 递归性的推 广并不那么容易z e i l b e r g e r 2 5 曾试图给出这一推广，但是他的定义是不准确的这一 工作最终由l i p s h i t z 1 3 完成下面我们就将给出多变量情形下d 有限性的概念，而对 于p _ 递归性，由于其定义比较复杂，我们将不给出其明确的定义 定义2 1 令f ( x l ，$ n ) = a ( i l ，k ) z l l z 。“c k l ，。 为关于变量 。= ( ：z 1 ，) 的形式幂级数，称作是d 一有限的，如果其导数( 彰o z l ) o 一( 8 a 。严， 张成c ( x l ，。) 上的有限维向量空间，其中o t i ，0 ，c ( 。l ，z 。) 是关于 变量x l ，的有理函数域一个序列口( i l ，如) 是只递归的当且仅当幂级数 ，( 。1 ，z 。) = 口( 1 ， 。) 。l 1 - $ 。“是j ) 有限的 对于d 有限幂级数与p - 递归序列，以下两个定理成立 定理2 1 ( 【1 3 】，命题2 ；2 ) f 是d 一有限的当且仅当，满足如下形式的线性偏微分方程组 卜( 射一( 射岫) ，一o ，n ， 其中a i j ( z ) c t z 定理2 2 ( 1 3 】，定理3 8v i i ) 如果序列a ( i l ，i 。) 是p 递归的，那么它满足如下形式的 递归方程组 壹p ，( i l ， 。) 。( t 1 ，4 j - 1 , 如+ l ，弓+ l ，一， 。) ：0 ，j ：1 ，n l = 0 其中硝是多项式，且对每个j 至少有一个0 5 大连理工大学硕士学位论文：求解某些鲎鲞壁型蕉童鱼甄鳗宣塑垡查鳖 为了强调p - 递归序列及相应的d - 有限发生函数之间的对偶性，我们将它们统称为 完整性函数( h o l o n o m i cf l l l l c t i o n ) 完整性函数满足许多封闭的性质，比如说完整性函数关 于加法运算与乘法运算封闭；完整性函数关于一个变量的积分( 或求和) 也是完整的， 也就是说，如果，( 。，z 。) 是关于n 个变量的完整性函数，则嚣，( 。- ，z 。) 如。 是关于z l ，- ，z 。- 的完整性函数，类似地，如果( m l ，m 。) ：z “_ c 是完整的， 则。，( m z ，m 。) 关于变量m 一，m 。一- 也是完整的有关p 递归序列，d - 有 限幂级数或者更一般地，完整性函数的性质，请参阅 5 ，1 2 ，1 3 ，1 7 ，2 6 下面我们给出几个完整性函数的例子，其中巩表示关于变量。的微分算子( d i 地r ， e n t i a t i o no p e r a t o r ) ，岛表示关于变量n 的移位算子( s h j r o p e r a t o r ) ，在后文中，类似的记号 都是用同样的方式定义的， 函数，( z ，t ) = ! 箬! 氅是d 有限的，从而是完整的这是因为它的导数的集合 以协j ，1 ( i ，j ) 砰) 生成有理函数域q ( = ，t ) 上的一个有限维向量空间事实上，利用如下的线 性偏微分方程组 d ；2 - ，+ t 2 ，= 0 ，t ( t 2 1 ) d t ，+ z ( 1 一t 2 ) d ；，+ 亡2 ，= 0 我们可以证明戗玩， 构成该向量空间的一组基 ，( n ) ：= n ! 满足( 晶一n i ) = 0 ，g ( n ) ：= 1 n ! 满足( + 1 ) 岛一1 ) g = 0 ，因此它们都 是完整的( 。n + b k + c ) ! 及其倒数关于变量n ，自也是完整的，其中g ，b 为整数，c 为复 数或参数所有的多项式尸都是完整的，并且1 p 也是完整的，只要它有定义多项式 系数l + + 协。) ! ”l ! m 。! 也是完整的相关证明请参阅【1 3 ，2 6 1 序列n 。：= 楚o ( ：) 2 ( “妁满足如下的递归方程 n 3 a n 一( 3 4 n 3 5 1 n 2 + 2 7 n 一5 ) a n _ l + ( n 一1 ) 3 一2 = 0 所以是p _ 递归的，从而是完整的 d - 有限性与p - 递归性也能在同一个系统中共存，比如l e g e n d r e 多项式( l e g e n d r e p o l y n o m i a l s ) ( r ( ) 满足如下几个方程( 参见【1 1 公式( 2 2 6 1 3 ，2 2 7 1 0 ，2 2 8 5 ) ) ： ( 1 一善2 ) r ”0 ) 一2 z r ( 。) + 扎( n + 1 ) r 0 ) = 0 ， ( n + 2 ) j + 2 ( 。) 一( 2 n + 3 ) 茹j + l ( ) + ( n + 1 ) 只。( $ ) = 0 ( 1 一z 2 ) 晶+ i ( z ) + ( n + 1 ) z r + 1 ( z ) 一( n + 1 ) r ( 茁) = 0 ( 2 1 ) ( 2 2 ) ( 2 3 ) 由( 2 1 ) 与( 2 2 ) 可知，l e 铲n d r e 多项式既是d 一有限的也是只递归的，其他的正交多项 式也满足类似的性质不仅如此，根据( 2 3 ) 可知，l e g e n d r e 多项式还满足混合的微分 递归方程，这样我们可以将完整性函数的范围从连续函数( d 有限幂级数) 与离散函数 ( p - 递归序列) 推广到混合的连续离散函数( r a k e d c o n t i n u o u s d i s c r e t ef u n c t i o n ) ，比如说 ，：渺1 z ”- + c 是这样的个函数，那么，不仅满足一些微分方程、递归方程，还可 能满足一些混合的微分递归方程 6 蔓! 童塞墼堡里墼墨韭壅堡茎王垡墼 根据定理2 1 可知d 有限幂级数满足一系列微分方程同样地，根据定理2 2 ，p - 递 归序列满足一系列递归方程由于它们所满足的方程都可以转换成关于微分算子与移位 算子的多项式，因此处理d 。有限幂级数与p - 递归序列的算法是类似的，也就是说，对 于完整性函数，我们可以用一种统一的方法米处理它们为此，我们需要将微分算子与 移位算子统一到个概念之中，下一节介绍的非交换算子代数就可以实现这一目标。 2 2 非交换算子代数 由于d 一有限幂级数的导数张成一个有限维的向量空间，因此其导数被线性相关性 所限制这些关系可以表示成零化该d 有限幂级数的微分算子我们可以在w e y l 代数 的框架内处理这些微分算子 定义2 2 设z = ( 。i ，z d ) ，a = ( 0 1 ，剐，k 是一个特征为零的域非交换多项式 环唰$ ，0 ) = 唰$ l ，z d ，a ，也) 称为是一个w e y l 代数( w e y la l g e b r a ) ，如果它满足 如下的交换关系： 晚= 。，夙+ 6 i , i ，魂岛= a j a ，q q = q q ， 其中( ，j ) 1 ，d ) 2 ，也，j 是k r o n e c k e r 记号 在本文中，k 代表特征为零的域，且通常为q r 或c ，k 也可能是q 的一个有限 扩域如果在定义2 2 中，未定元嗣代表用剐乘算子，未定元穗代表关于q 的微分算 子，那么w e y l 代数就是微分算子代数关于w e y l 代数的问题，读者可以参阅【3 ，5 ，2 6 下面我们考虑如何将微分算子、移位算子及其他一些线性算子统一起来 我们知道l e i b n l z 法则表明对任意两个可微函数厶g ，( 内) = f g + f g 令沈为关于 变量。的微分算子，与，7 表示用函数，或，7 乘算子，那么l e i b n i z 法则可以用算子形 式描述 巩，= f d = + ，( 2 4 ) 再考虑差分运算( ，g ) 扛+ 1 ) 一( 内) ( z ) = ，0 + 1 ) ( 9 扛+ 1 ) 9 ( z ) ) + ( ， + 1 ) 一，( z ) ) 9 ( 。) ，令 s 为移位算子，( s - ，) ( $ ) = f ( x + 1 ) ，a = s 一1 为差分算子( d i f f e r e n c eo p e r a t o r ) ，那么 ( f g ) = p ，) ( g ) + ( a f ) g ， ，= ( s - f ) a + ( a - ，) ( 2 5 ) 类似地，由于【( s f ) - 引( ) = 陋- ( ，g ) l ( z ) = ，0 - i - 1 ) 9 0 + 1 ) = 【( s f ) s - 鲥( $ ) ，因此 s ，= ( s f ) s ( 2 6 ) 由( 2 4 ) ，( 2 5 ) ，( 2 6 ) 可以看出微分算子、差分算子、移位算子均满足如下形式的交换关系 o f = 口( ，) a - 1 - d ( ，) ，( 2 7 ) 7 大连理工大学硕士学位论文：求解某些特殊序列莲塑数的鱼塑丝查鳖 其中仉d 与具体的算子a 有关由于a 是线性算子，则6 也是线性的，又考虑到 ( o f ) g = a ( f g ) ，因此 c , ( i g ) o + d ( ，g ) = 口( ，) 幻+ d ( ，) 口= 口( ，) 口0 ) 口+ 口( ，) j ( 9 ) + j ( ，岫 通过比较系数我们可以得到 o ( i g ) = 口( ，p ( 9 ) ， 6 ( ，9 ) = 盯( ，) 6 ( g ) + 占( ，b ( 2 8 ) ( 2 9 ) 可见o - 保持加法与乘法运算，是一个环同态；而d 为线性的且满足( 2 9 ) ，是一个口导算 子基于上面的讨论，我们可以给出如下的般的定义； 定义2 3 令a 是一个整环一个斜多项式环( s k e wp o l y n o m i a l 咖) a c o ；吼川为系数在a 中，关于a 的多项式的集合，满足通常的加法以及由如下的交换法则所定义的乘法： v a a ，o a = f ( n ) a + d ( b ) 其中口是a 的环自同态，d 是口导算子，即j 是a 的加法自同态并且满足 v a ，b a ，d 0 6 ) = 口( n ) d ( 6 ) + 6 ( o ) 6 ( 2 1 0 ) ( 2 儿) 利用交换法则( 2 1 0 ) ，a 0 ；a ，司中的任意元素都可以唯一地写成冬oq 伊的形式，即 将算子a 写在右边这样由于系数均在单项式的左边，我们可以像通常的交换情形一样 定义a 的次数和系数 定理2 , 3 ( 【6 ，命题1 1 ) 斜多项式环a 【a i 仃，川是一个整环 通过选择合适的整环a ，我们可以利用定义2 3 与定理2 3 构造各种各样的多变量斜 多项式环特别地，我们有如下重要的特殊情形 定义2 4 令k 是一个域，a = 啦l ，一，。一为一个交换的多项式环( 当5 = 0 时，a = 竭 斜多项式环a 吼；叽，d l 】r ；岛，以! 称作是一个o r e 代数( o r ea l g e b r a ) ，如果以，如可以交 换，1 t ，js ni j ，并且满足以( 岛) = 岛，最( 白) = 0 ，i 当日= 0 时，记作；口，卅， 当s 0 时，称作是一个多项式o r e 代数( p o l y n o m i a l o r e a l g e b r a ) ，并记作啦】 8 ；口，讣 需注意，根据定义中以，毛所满足的条件可知算子取是可以交换的，即岛国= 岛民1 t ，j sr o r e 最先研究了斜多项式环，c h y z a k 5 ，6 】为了研究_ 般的完整性函数及恒等式自动 证明的算法引入了o r e 代数的概念o r e 代数的适用范围很广，包含许多特殊的实例 例如，w e y l 代数嚼。1 ，$ 。j 1 2 x ，；1 ，玩。】【皿。；1 ，岛。】是一个多项式o r e 代数 8 苎! 童 塞鳖墼里墼垦韭銮堡蔓垡塾一 又例如，根据( 2 1 ) ，( 2 2 ) 与( 2 3 ) 可知，l e g e n d r e 多项式 r ( $ ) ) 可以被o r e 代数 q l n ，司【艮；岛，o i d 。；1 ，三q 中的算子g 1 ，g 2 ，g 3 零化： g 1 = ( 1 一品2 ) d ，一2 x d ，：+ n ( 住+ 1 ) ， g 2 = ( n 十2 ) & 2 一( 2 n + 3 ) x s + ( n + 1 ) ， g 3 = ( 1 一茁2 ) d 。岛+ ( n + 1 ) 。最。一m + 1 ) 在论文第三、四章中出现的非交换算子代数都是特殊的o r e 代数 由于w e y l 代数是o r e 代数的个特例，因此我们有时也用与w e y l 代数相同的记号 来表示o r e 代数，即砥$ ，a ) = 砬( $ l ，。d ，巩，如，此时，卅 ；晶，o p 。；1 ，d z l 可以表示成q ( n ，丑晶，皿) 在后面，我们都采用这种记号这样，对于o r e 代数唰。，a ) ， 若取口( 。) = z + 1 ，6 ( z ) = 0 ，则如= 扛十1 ) a ，a 是移位算子将a 分别换成，则 瓯n = + 1 ) 品，k ( o ，a ) = 唰n ，品) 除微分算子，移位算子、差分算子外，其他一些算子 例如q 扩张算子( q - d i l a t i o no p e r a t o r ) 、e 。- 微分算子( e 。一d i f f e r e n t i a t i o no p e r a t o r ) 等等也可 以包括在o r e 代数的框架之中，请参阅 5 ，6 】 在我们的讨论中，o r e 代数中零化某个给定的完整性函数的算子的集合起着重要 的作用，对于任意给定的完整性函数，我们用a n n f 表示这个集合，即a n n ：= 伽 聪( z i ，。d ，巩，啦) ，叫，= o ) 显然a n n ，是o r e 代数中的一个左理想，我们构造的 关于组合恒等式自动证明以及发生函数自动求解的算法就是在o r e 代数中零化某个完整 性函数的左理想中进行的，这在后面两章中将会清楚地看到 9 3 非交换算子代数中的消元及恒等式的自动证明 3 1 介绍 在 2 6 】中，z e u b e r g e r 提出了证明特殊函数恒等式的自动化方法特别地，z e i l b e r g e r 给出了自动证明具有如下形式的可终止超几何级数恒等式的具体算法及m a p l e 程序 f ( n ，) 具有形式 f ( 七) f ( n ，) = r 胁( n ) g a ：a ! l kj i i ：i n 墨1 ( 玩n + 磁+ 6 7 ) 2 其中啦，n ：，k ，醒为整数，而z ，o ? ，醪为任意的复数或参数 若( 3 1 ) 的右端r h s ( n ) 明确地给出，它应具有形式 帆= g 黼扩 ( 3 1 ) ( 3 2 ) ( 3 3 ) 其中面，- l 为整数，而a ：，配c ，i 为任意的复数或参数 或者r h s ( n ) 没有明确地给出，而是给出能够零化r h s ( n ) 的具有最小阶的多项式系数 线性递归算子c o n j ( n ，晶) 以及适当的初始条件 由于( o n + b k + c ) ! 及其倒数是关于变量m 的完整性函数，其中o ，b 为整数，c 为 复数或参数，根据完整性函数的性质，f ( n ，k ) 是完整的，且女f ( n ，) 关于变量n 也是 完整的，因此。f ( n ，) 满足某个多项式系数线性递归方程 为了寻找这一递归方程，z e i l b e r g e r 在其算法中应用了s y l v e s t e r 经典的析配消元法 ( d i a l y t i ce l i m i n a t i o n ) ，因此z e u b e r g e r 算法所需内存较大，有些恒等式，比如d i x o n 公式， 就无法成功地证明 考虑到这一问题，我们研究了非交换算子代数( 包括移位算子、扩张算子及微分算 子) 中的消元问题，并利用我们的消元法改进了z e i l b e r g e r 算法改进之后的z e i l b e r g e r 算法不仅仅能够自动证明包括d i x o n 公式在内的可终止超几何级数恒等式，而且还能够 证明g - 正常超几何恒等式【2 9 】以及带有积分号的恒等式除此之外，利用吴文俊先生所 创立的机械化方法【2 1 ，2 2 ，3 0 ，我们进一步给出了自动证明多变量可终止超几何级数恒等 式的算法 大连理工大学硕士学位论文一求解某些特殊壁型塞皇鱼墼堕旦垫垡茎睦 事实上，我们关于这一问题的研究可以追溯至1 9 9 7 年，在【3 2 中，我们这一理论的 基本框架已经形成，并且孙晓丽1 3 1 】用m a t h e m a t i c a 实现了这一算法在此基础上，作者 进一步研究了消元的过程以及算法与程序的结构，对已有的m a t h e m a t i c a 程序进行了较 大的修改，完善了程序的输入输出，并扩大了程序的适用范围，之后又分别用m a p l e 及 c 语言实现了该算法，并且用这些程序验证了许多实例特别地，在具体分析程序结构 的过程中，作者对中间变量的值进行了合理的处理，使程序效率得到显著的提高 本章的主要内容如下：基于移位算子的非交换代数中的消元问题将在3 2 节中研究 在这一节中，我们将把e u c l i d e a n 算法推广到非交换算子代数的环境下，并给出这一章最 重要的定理，即，给定两个多项式 ，b c ( 晶，最，n ) ，总存在多项式u ，w c ( 品，鼠，n ) 使 得u a = ”b ，其中，瓯分别是关于n ，k 的移位算子然后，我们将展示如何从两个多 项式p q 中消去未定元k ，其中p ，q c ( 品，s k ，n ，k ) 在3 a 节中，我们将给出改进的 z e i l b e r g e r 算法，并且辅以m a p l e 程序运行实例作者对程序的一些处理也将在此节中说 明证明多变量恒等式的基本思想及其算法将在3 4 节中体现最后，在3 5 节中，我们 给出微分算子的有关结论，这些结论为自动证明带有积分号的恒等式及自动求解特殊序 列发生函数提供了理论上的储备 3 2 基于移位算子的非交换代数中的消元 移位算子，瓯定义为晶，( n ，) ：= ，m + 1 ，) ，鼠，( m ) ：= f ( n ，女+ 1 ) 任意一个关于四 个未定元n ，& ，最的多项式都是一个多项式系数偏递归算子( p a