（应用数学专业论文）有限验证法证明超几何恒等式.pdf

摘要 摘要 本文主要研究了证明超几何恒等式的有限验证法，并给出了所需验证项数较 小的估计 通过验证有限项来证明超几何恒等式这种思想最早是由d z e i l b e r g e r 提出 的他指出，给定恒等式 f ，) = ，( n ) ，n 伽， 其中f ( n ，克) 和，( n ) 都是超几何函数，则存在可以直接由f ( n ，) 和，( n ) 得到 的整数n 1 ，使得若k f ( n ，) = ，( ) 对竹= 伽，礼o + 1 ，n l 成立，则它对所 有的礼2 勘都成立 1 9 9 3 年，l y e n 在其博士论文中首次实现了这一思想，对超几何恒等式估计 出了礼l ，她估计n 1 的方法是，估计出证明恒等式两边满足相同的递归关系所需 验证的项数n ，和该递归关系的阶数，以及几。，满足当他时，递归关系的 首项系数恒不为零，则取礼1 = m a x 吃一1 ，礼，) 即可。其中吃= m a x 礼。，佗o + 册 但y e n 得到的估计非常大，无法用于实际证明例如对恒等式( ：) = 2 “估计 出的钆1 为1 0 1 1 ，而对恒等式k 谨) 。；( 哿) ，这一估计更是达到l o n 5 1 9 9 6 年 y e n 还进一步对g - 超几何恒等式得到了n l 更小的估计2 0 0 3 年，张宝印利用吴 消元法，进一步减小了对g - 超几何恒等式n l 的估计 上述方法所需估计的三个数值中，最难估计的是，它一般情况下也是三 者中最大的为了进一步挖掘求和项所蕴含的信息以减小对的估计。本文引 入了多项式的次数高度对( d h 对) 的概念，进而定义了d h 向量和d h 矩阵以 及它们之间的运算法则，并研究了d h 对，d h 向量、d h 矩阵以及它们之间的 运算所满足的一些性质 基于c r 砌e r 法则和y e n 给出的形式地求齐次线性方程组多项式解的算法， 我们给出了求齐次线性方程组多项式解的d h 对上界的算法利用s i s t e rc e l i n e 算法和新z 以b e r g e r 算法可以碍到关于递归关系多项式系数的方程组，对此方程 组利用上述求d h 对上界的算法，我们可以估计出递归关系系数多项式的d h 对 上界，从而得出竹。和n 1 的估计 i 摘要 实例表明，本文的结果改进了对n - 的估计例如对一般的超几何恒等式，我 们对恒等式( ：) = 扩，利用s i s t e rc e n n e 算法得到竹1 = 1 6 ，利用新z e i l b e r g e r 算法得到乱l = 4 对恒等式t ( 0 。= ( 轨) ，利用s i s t e rc e i i n e 算法得到n 1 = 2 5 2x1 0 船，利用新z e i l b e r g e r 算法得到礼l = 2 4 7 0 0 对g - 超几何恒等式，我们 利用新铲z e i l b e r g e r 算法对j a b i 三重积恒等式的一种有限形式得到佗1 = 9 ，对 哥v a n d e r m o n d e - c h u 恒等式得到n l = 3 0 ，对l j r o g e r 6 提出的欧拉五角数定 理的一种有限形式得到几1 = 4 2 关键词；组合恒等式的机器证明有限验证法d h 对 s i s t e rc e l i n e 算法 z e i l b e r g e r 算法 i i a b 8 t r a c t a b s t r a c t i nt h i 6t h e s i s ，w em a i n l ys t u d yt h eq u e s t i o n0 fp r o 、，i n g1 1 y p e r g e o m e t r i ci d e n - t i t i e sb yc h e c k i n ga 丘i l i t en u m b e ro fs p e c i a lc 踮e 8 ，a n dg e tc o n s i d e r a b l ys m 札l e s t i m a t e sf o rt h i sn u l b e r i tw a sd ，z e i l b e r g e rw h of i r s tr e a l i z e dt h a to n ec a np r o v eah y p e r g e o m e t r i c i d e m i t yb yc h e c k i n ga i i n i t en 衄幽e ro fs p e c i 8 lc a s e 8 。h es 8 i dt h t ，p r o v i d e dt h e f o u o w i n gi d e n t i t y ：f ( 礼，惫) = ，( n ) ，n 乱o ， 知 w h e r ef ( 竹，功a n d ，) a r eb o t hh y p e r g e o m e t r i cf u n c t i o l l s ，t h e nt h e r ee ) ( i s t sa n 啪b e r 仃1w h i c l lc a nb eg o t o mf ( 扎，七) a n d ，( n ) ，8 j 1 di ft h ea b o v ei d e n t 时 h o l d 6 f o r 仡= 几o ，伽+ 1 ，竹l ，t h e n j th 0 i d s f o ra un 之n o i n1 9 9 3 ，ly 毫ni nh e rd o c t o r a id i s s e r 乇a t i o ng 孙，e 乇h e 矗r s t 口p 心d 疗e s t j m a t e f o rt h i 6 u m b e rf o rh y p e r g e o m e t r i ci d e n t i t i e 8 h e rm e t h o di 8 ：g i v i n ga ne 6 t i m a t e o f t h en 瑚如e r 凡，f o rp r o 、r i i l g t h a t t h e 细os i d 鹤o f t h e i d e n t i t ys a t i s 移t h es 锄e r e c u r r e n c e ，t h eo r d e r ，o ft h er e c u r r e n c e ，a n dt h ei n t e g e r 扎o8 u c ht h a tt h el e a d i n g c o e 毋c i e n to ft h er e c u h e n c ei 8n o ti d e n t i c a l l yz e r ow h e n 佗礼4 。t h e nw eh a v e n 1 = m a x 怯一1 ，唧) ，w h e r e 怯= m a x 礼o ，珊+ 以b u ty e n 8e s t i m a t ei st o o l 盯g e t o b ep r a c t i c a i 。f 0 r e x 锄中l e ，h e re s t i m a t eo f 礼l i 8 l o n 耳( ：) = 扩，a n d 1 0 1 1 5f o r ( ：) 2 = ( 蛩) f 1 1 汕e r m o r e ，i n1 9 9 6 ，y e ns h o w e dt h a tf o r 口i d e n t i t i e s t h ep r i o r ie s t i m a t e s0 fn lc a nb es p e c t a c i l l 盯l yr e d u 船d i i l2 0 0 3 ，b - y z h a n g g a v ee v e ns m a n e re s t i m a t e s0 fn 1f o r 争i d e n t i t i 鹋b yw h se l i m i n a t i o nm e t h o d a m o n gt h et h r e em l i l l b e r 8i n v o l v e di nt h ea b o v em e t h o d ，n 口i 8a l w a y st h e 1 a r g e s ta n dm o s td i m c u l tt oe s t i m a t e i no r d e rt og e ts m 虬l e r 扎nf o rh y p e r g 咿 m e t r i c 主d n t i t i e s ，w ed 培o u tm o r ei n f o m a t j o nf o mt h e8 u m m a n d w 色i n l | r o d u e e t h ec o n c e p to fd e f e e i h e i g h tp a j r ( d hp a i r ) ap 0 1 y n o m i 出，a n dd e 丘n et h ed h v e c t o r ，d hm a t r 投，a n ds o i n eo p e r a t i o 璐锄o n gt h e m t h ep r o p e r t i 髑8 a t i s 丘e d b yt h ed hp a i r ，d hv e c t o r ，d hm a t r i ) 【a n dt h eo p e r a t i o n sa r e 以8 0s t u d i 耐 b a s e do nc r 锄e r 8n l l ea n dy e n 8 以g o r i t h mf o rf i n d i n gt h ef o m a lp o l y n o - n l i 以s o l u t i o nt oau n e 缸8 y s t e mo fe q u a t i o 璐，w eg i 、，ea na l g o r i t h mf o r6 n d i n g t h eu p p e rb o u n d0 ft h ed hp a i ro fah 鲫。黜l l sl i n e a rs y 8 t e m sp 0 】y n o m 瑚 s 0 1 u t i o n b ys i s t e rc e n n e s l e t h o da n dt h en e wv e r s i o no fz e i l b e r g e r sa i g o _ r i t 虹，w eo b t 越ah o m o g e n e o l l 8l i e 盯巧s t 锄e q u a t i o i l sw h 0 8 e 咖k n 帆s 盯e t h ep o l y l l 锄a lc o e 伍c i e n t so ft h er e c u r r e n c e f b mt h i s 盯s t e m ，w ec a ng e tt h e i i i a b s t r a c t e s t i m a t eo ft h eu p p e rb o u n do fn 塘p o l y i l o m i a lc o e m c i e n t s d hp a j r s ，t h e nt h e e s t i m a t eo f a n d 扎1c a nb eg o ts t r a i g h t f o r w 龇d l y n 恤e r i c de x 锄p l e 88 h o wt h a to l i r 铝t i m a t e ba r eo d n s i d e r a b i ys m a l l f b r i n s t a n c e ，f o ro r d i i l 引yh y p e r 目e o m e t r i ci d e n t i t i e 8 ，w eg e tn 1 = 1 6b ys i 8 t e rc e l i n e s m e t h o da n d 礼1 = 4b yz e i l b e r g e r s 龃g o r i t h mf o r ( ：) = 2 “，a n d 礼l = 2 5 2 1 0 2 5b ys i 8 t e rc e l i n e sm e t h o d8 n dn l = 2 4 7 0 0b yz e i l b e r g e r sa l g o r i t h mf o r ( ：) 。= ( 翟) f 0 r 口- h y p e r g e o m e t r i ci d e n t i t i e s ，w eg e tn l = 9 f o raf i n i t e v e r s i o no fj a c o b i st r i p l ep r o d u c ti d e n t i t y ，礼1 = 3 0f b ft h e 驴v a n d e l 吼o n d e c h u i d e n t i t y a n d 露1 = 4 2f o ra 丘n j t ef o r mo fe l l l e r sp e n t 雒r o n a ln u m b e rt h e o r e md u e t ol j r o g e r 8b yt h en e wv e r 8 i o no fg - z e i l b e r g e r s8 1 9 0 r i t l l m k e y w o r d s ：c o m p u t e rp r o o fo fc o m b i n a t o r i a li d e n t i t i e sc h e c k i n g 丘i l i t ev “u e s d hp a i rs i s t e rc e u n e 8m e t h o dz e i l b e 疆e r s 缸g o r i t h m i v 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、- 缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版：在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：部弓歌埒 。 + 伽o 年l 卜月f 7 日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： 韬莲一 ，转繁，餮爹象譬，o劳譬每譬譬雩萎 洳矗磅嚣孵嗨毪 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：巧p 弓星、褥 伽。c 7 年峰月f7 日 第一章引言 第一章引言 1 1 组合恒等式的机器证明 组合恒等式没有明确的定义，一般可以将其大致理解为离散的求和公式，以 及关于各种具有组合意义的数量的恒等式对组合恒等式的研究具有十分悠久的 历史，甚至可以追溯到十一世纪，当时中国已经有了完备的二项式系数表，并且 还有表的编制方法传统的证明组合恒等式的方法涉及生成函数，反演公式，组 合映射等等。通常需要很巧妙的构思直到近几十年，人们才开始寻找系统证明 组合恒等式的方法 近代组合数学的奠基人g i a n c 缸l or d t a 教授为了给出一套系统地证明组合 恒等式的方法，发明了哑演算理论( u m b r a lc a l c u l l l s ) ，对许多组合恒等式，特别 是二项型的恒等式( b i n o i n i a l 咖e ) 能给出系统的证明但是，r _ 0 t 8 的理论并不 包括一般的超几何恒等式近些年来，在r w g o s p e r ，h s w i l f ，d z e i l b e r g e r ， m p e t 跏e k 等人的工作之后，组合恒等式的证明发生了革命性的变化很多组 合恒等式的证明可以转化为多项式和有理函数的符号计算，然后由计算机完成 基于g o s p e r 算法( 【2 4 ，2 5 】) z e i l b e r g e r 算法( 【5 1 ，5 2 ，5 3 】) w z 方法( 【4 1 ，4 2 】) 和 p e t k o v 琵k 的超几何算法( 【3 4 】) ，几乎所有的组合恒等式和超几何恒等式都能用 计算机证明，而且还有越来越多类型的恒等式被纳入机器证明的理论体系之中 正如吴文俊先生指出，在数学研究中，计算机将越来越多地取代人脑的工作原 来需要很高的技巧才能证明的定理，将被大量而不需要技巧的计算代替数学机 械化将成为数学现代化发展的一个重要趋势 组合恒等式机器证明的理论基础是由s i s t e rm a r yc e l i n ef 缸e n i r l y e r 在其 1 9 4 5 年的博士论文【2 0 】中完成的她在该文中给出了寻找超几何和式满足的递 归关系的机械化方法，并在以后的两篇文章【2 1 ，2 2 】中继续发展了这种方法，她 的这些工作也被麟n v i l l e 收入在书( 3 8 1 中s i 8 t e rc e i i n e 的方法简单有效，但速 度较慢，通常不用于证明较复杂的恒等式但其重要意义还在于s i s t e rc e l i n e 存 第一章引言 在性基本定理，该定理证明了所有正则超几何函数都满足一个七无关递归关系 事实上，存在七无关递归关系的超几何函数也都是正则的( 【1 2 ，1 3 ，1 4 ，2 6 ，2 7 】) 1 9 7 8 年，r w g o s p e r 在 2 4 】中提出了g o s p e r 算法，成功回答了“一个具 有闭形式的函数的不定和是否也具有闭形式”这个问题，如果是，该算法还能求 出和的闭形式后人又对g o s p e r 算法在有理函数，q 一超几何项，混合超几何项， 多重和等方面做了许多推广( 【1 6 ，1 8 ，1 9 ，2 8 ，2 9 ，3 2 ，3 3 ，3 5 ，3 7 】) 此外，g o s p e r 算法还对z e i l b e r g e r 算法，w z 方法和p e t l 【0 v e k 的超几何算法起到了很大的作 用，因此成为恒等式机器证明理论的基石 d z e i l b e r g e r 于1 9 9 0 年提出的z e i l b e r g e r 算法是继g o s p e r 算法之后恒等式 机器证明领域的又一里程碑，它基于g 0 8 p e r 算法，能快速找到超几何和式满足 的斜递归关系z e i l b e r g e r 算法对所有正则超几何函数甚至一部分非正则超几何 函数都是适用的，从而使得许多以前g o s p e r 算法无能为力的恒等式都得到了机 械化的证明z e i i b e r g e r 算法也可推广到口一超几何函数( 【2 9 】) ，并且z e i l b e r g e r 算 法和q - z e i l b e r g e r 算法的适用范围已由s a a b r 锄0 v ( 【4 ，5 】) ，a b r 锄o 、，和h q l e ( 【8 】) ，以及陈永川，侯庆虎和穆彦平( 【17 】) 得到 w z 方法提供了迄今为止最为简洁的一种证明组合恒等式的方法，对于已知 恒等式，它可以通过仅仅计算出该恒等式的w z 认证完成证明w z 方法虽不 及s i 8 t e rc e n n e 算法和z e i l b e r g e r 算法的适用佳广泛，但其简洁高效使得w z 方法也不失为证明组合恒等式的一个有力方法，而且对大多数超几何恒等式来 说，w z 方法都是适用的另外，w z 方法在证明已知恒等式的同时，还能发现 新的恒等式 利用s i s t e rc e l i n e 算法和z e i l b e r g e r 算法只是可以得到求和式满足的递归关 系，而要得到其闭形式，还需要求解此递归关系常用的求解递归关系的算法有； 求多项式解的多项式算法( 【3 4 ，7 】) ，求有理解的算法( 【l ，2 ，3 ，6 ，1 8 ，4 0 】) ，求超几 何解的算法( 【3 4 ，9 ，3 5 ，1 9 】) ，以及求更为一般的d a l e h l b e r t i a n 解的算法( 【l o 】) 1 2 证明超几何恒等式的有限验证法 通过验证有限项来证明超几何恒等式这种思想是d z e i i b e r g e r 最早提出的， 2 第一章引言 他在研究s i s t e rc e l i n e 算法时( 【4 9 ，5 0 】) ，意识到可以通过仅验证有限的一些特 殊情况来证明超几何恒等式，就像我们要证明两个次数不超过的多项式相等， 只需证明它们在+ 1 处相等一样z e i l b e r g e r 在 5 0 1 中提出，给定恒等式 f ( 七) = 砌) ，竹伽， 其中f ( n ，七) 和，( n ) 都是超几何函数，则存在可以直接由f ( 礼，七) 和，( n ) 得到 的整数n 1 ，使得若k f ( 扎，七) = ，( n ) 对n = 锄，竹1 成立，则它对所有的 n 之伽都成立 上述想法由l 。y e n 在其1 9 9 3 年的博士论文【4 6 】中首先实现，她的主要思 想如下， 设我们要证明的恒等式为 f ( 耐= ，( 哟，礼2 锄， ( 1 1 ) 且s ( 几) = t f ( 七) 满足递归关系 码( 竹) s ( n j ) = o ( 1 2 ) 再假设当n 时有印( n ) o ，则当n 吃= m a x n 。，伽+ ，) 时有 跏) - - 南喜咖坝一n 于是s ( 住) 就由初值s ( n o ) ，s ( 伽+ 1 ) ，s ( 畦一1 ) 完全决定因此，为了证明 s ( 扎) = ，( 绍) ，我们只需证明，( 佑) 和s ( n ) 满足相同的递归关系，且初值相同而 这一点也可以通过验证等式，( 扎) = s ( n ) 对有限项孔= 伽，n ，成立得以证 明 综上，欲证明恒等式( 1 1 ) ，我们需要估计如下三个数值： l 递归关系( 1 2 ) 的阶数，； 2 使n 0 ( 礼) o ，v 礼的最小非负整数； 3 为证明，( 竹) 与s ( n ) 满足相同的递归关系所需的估计值礼， 第一章引言 从而得到几1 = m a x 吃一l ，n ，) ，满足恒等式( 1 1 ) 成立当且仅当它对 = 伽，n l 成立 采用上述思想，y e n 在她的博士论文中讨论了对一般的超几何恒等式估计扎1 的方法，但这一估计相当大，使得有限验证仅仅在理论上是可能的例如对恒等 式( ：) = 2 ”估计出的竹1 为1 0 n ，而对恒等式k ( ：) 2 = ( 哿) ，这一估计更是 达到1 0 1 1 5 组合恒等式机器证明领域的经典文献a = b 3 6 1 一书中就评价说这 一估计是无法用于实际证明的，同时又指出使这一先验估计尽量小是一个很有意 义的研究课题 1 9 9 6 年，y e n 利用上述思想又进一步对q _ 超几何恒等式给出了n 1 的估计， 由于口一超几何函数具有一些特殊的性质，因此对于超几何恒等式所估计出的扎。 比一般超几何恒等式要小得多如她对口- v m d e r m o n d e c h u 恒等式估计出竹1 = 2 3 5 8 2 0 0 3 年，张宝印在论文【3 0 ，5 4 】和他的博士论文【5 5 】中，进一步利用吴消 元法，对口- 超几何恒等式得到了礼l 的更小的估计。如对j a c o b i 三重积恒等式的 有限形式估计出n 1 = 7 4 ，对酽v a n d e r m o n d e _ c h u 恒等式估计出n l = 1 9 1 ，对 l j r d g e r s 提出的欧拉五角数定理的一种有限形式估计出n l = 2 0 9 上述方法所需估计的三个数值中，最难估计的是，它一般情况下也是三 者中最大的本文的主要工作就是通过进一步挖掘超几何函数求和项f ( n ，后) 所 蕴涵的信息，从而得到更小的估计 本文第二章介绍了超几何函数的基本概念，以及我们后面将要用到的组合恒 等式机器证明的三个最基本的算法；s i s t e rc e u n e 算法，g o s p e r 算法和z e i l b e r g e r 算法 第三章是本文的核心部分。给出了估计n 1 的d h 对方法第三章第一节首 先引入了多项式的次数高度对( d h 对) 的概念，进而定义了d h 向量和d h 矩 阵以及它们之间的运算法则，并研究了d h 对，d h 向量、d h 矩阵以及它们之 间的运算所满足的一些性质 第二节基于c r a m e r 法则和y e n 在【4 6 ，4 7 】中给出的形式地求齐次线性方程 组多项式解的算法，给出了求齐次线性方程组多项式解的d h 对上界的c r a m e r d h 算法 第三节给出了利用s i s t e rc e h n e 算法估计n 1 的方法首先利用s i s t e rc e l i n e 4 第一章引言 算法得到关于求和项f ( n ，忌) 满足的递归关系的多项式系数的齐次线性方程组， 然后利用第二节的c r a i n e r - d h 算法，得到这些系数多项式的d h 对上界，并进 一步将其转化为和式所满足的递归关系的系数多项式的d h 对上界，从而得出 n 。和n l 的估计对恒等式( ：) = 妒，我们利用s i s t e rc e l i n e 算法得到的方 程组估计出n l = 1 6 对恒等式( ：) 。= ( 蛩) ，得到n 1 = 2 5 2 1 0 2 5 第四节研究了利用新z e i l b e r g e r 算法来估计竹1 首先介绍了m o h a l m e d 和 z e i l b e r g e r 在【3 1 】中提出的新z e i l b e r g e r 算法利用新z e i l b e r g e r 算法，我们可 以直接得到关于和式女f ( 佗，七) 满足的递归关系的多项式系数的齐次线性方程 组，同样利用第二节的c r 锄e 卜d h 算法，估计出这些系数多项式的d h 对上界， 从而得出和n l 的估计利用新z e i l b e r g e r 算法，我们对恒等式女( ：) = 妒 得到n 1 = 4 对恒等式kq ) = ( 翟) ，得到n l = 2 4 7 0 0 第五节研究了利用新争z e i l b e r g e r 算法对铲超几何恒等式估计n 1 对g - 超 几何恒等式，我们只需估计递归关系的系数多项式关于口和矿的次数利用新 铲z e n b e r g e r 算法，我们对j a c o b i 三重积恒等式的一种有限形式得到扎1 = 9 ，对 铲v a n d e r m o n d e - c h u 恒等式得到n 1 = 3 0 。对l j r d g 雕s 提出的欧拉五角数定 理的一种有限形式得到n l = 4 2 5 第二章组合恒等式机器证明的基本算法 第二章组合恒等式机器证明的基本算法 2 1 超几何函数 本文中所研究的恒等式均为可容许的超几何恒等式，为此本节介绍超几何函 数和可容许超几何项的基本概念 定义2 1 1 称f ( n ，七) 是双超几何的，如果 警和等 都是关于扎和南的有理函数 定义2 1 2 一个函数称为正则超几何的。如果它可以写成如下形式。 咐) - p 砷恐黑 ( 2 1 ) 其中，z 是未知复数，且 1 p m ，七) 是关于n ，詹的多项式， 2 ，以，都是整数， 3 c | ，是可以含其它未定参数的常数， 4 钍t 和口t ，是有限，非负的整数 具有形式( 2 1 ) 的f 在点( n ，后) 是有定义的，如果 口m + 以七+ 岛) 罂1 中没 有负整数如果f 在( n ，七) 点有定义，且至少有一个 m + 七十t l j ，) 罂1 是负 整数，或p ( n ，七) = o ，则我们说f ( n ，七) = 0 显然正则超几何函数都是双超几何的，下面给出几个正则超几何函数的例 子 6 第二章组合恒等式机器证明的基本算法 g ) 2 是正则超几何函数，因为它可以写成 取驴( 扩= 赢z ， 满足定义的形式 f ( 礼，七) = 1 + 3 七+ 1 ) 虽然看起来不满足定义的形式，但是它可以变形为 定义的形式： 1 + 3 七) ! 石丽2 石辅丽 故其也是正则超几何函数 f ( n ，七) = 1 ( n 2 + 七2 + 1 ) 总是不能变形为定义中的形式，故其不是正则超 几何函数 记集合 1 ，2 ，n 为m ，并记【明u o ) 为【明o 下面定义可容许超几何项 定义2 1 3 对固定的几，设使函数f ( n ，詹) 有意义的七的取值区间为陋( n ) ，p ( 几) 】， 称b ( 几) = 【d ( n ) j6 ( 礼) 1 为f ( n ，) 的自然支集( n a t l l r ds u p p o r t ) ，若 ( 1 ) k ( 扎) ，6 ( n ) 】【o ( 竹) ，卢( n ) 】， ( 2 ) f ( n ，n ( 扎) ) o ，f ( n ，6 ( 礼) ) o ， ( 3 ) 对任意的q ( n ) 七 ，砧( 2 ，3 ) 其中礼。是使得f ( n ，七) 有意义的初值，与，是f ( n ，七) 所满足的膏无关递归 关系的阶 7 第二章组合恒等式机器证明的基本算法 2 2 s i s t e rc e l i n e 算法 下述存在性基本定理是s i s t e rc e u n e 算法的基础 定理2 2 1 ( 存在性基本定理) 设f ( n ，七) 是形如( 2 1 ) 所定义的正则超几何函 数，则存在关于f ( n ，后) 的，且系数与后无关的递归关系也就是说，存在正整 数，和关于n 的不全为零的多项式口l j ( 礼) “= 0 ，j ；j = 0 ，) 。使得 递归关系 啦。( n ) f m 一互一1 ) = o ( 2 4 ) = oj = 0 在所有f ，) o 的点，后) 成立 对n n m 之。兮( z ) 而l ( z ) 5 ，( z ) 巫l ( z ) 塑， 可知，在( 2 5 ) 的分母中，对每个s ，都把0 + 砒) + 和( 一j 一饥) + 关于l ，j 取到最大值，则所得的多项式必然是所有马寄鲁铲项的分母的公倍式。从而引 理成立 i 下面我们就来证明定理2 2 1 在( 2 4 ) 式两边同时除以f ( n ，克) 得； 妻参锴一o ( 2 。) = 0 = o 1 7 令 j m ，) = p ( 几一j ，七一i ) ( n m + 6 。七+ c 。+ 1 ) 丽( 。n + 七+ 叫，) 垃咝， 盈j ( n ，是) = g p ( 珏，寿) 。 ( 几+ k 忌+ 岛) 堕竺! 业( t 。n + 詹+ 叫。+ 1 ) f 瓦；丽 9 第二章组合恒等式机器证明的基本算法 则由( 2 5 ) 知，h 。( n ，) 和( 扎，岛) 都是关于n ，七的多项式，且 ! ! 竺二墨! 二翌；竺i ! 兰! 塑 ，( 忍，詹)盈j ( 扎，七) 在( 2 6 ) 两边同时乘以引理2 2 2 中的公分母，得： i3 萎篆m 小，动瓦南训 ( 2 7 ) - = o 卸 u 、7 7 上式左边是关于疗，后的多项式 为了证明定理，只需证明存在和，使得( 2 7 ) 有非平凡解啦j ( n ) 为此， 我们令( 2 7 ) 式左边后的所有幂次的系数为零，从而得到关于啦j ( n ) 的线性方 程组下面我们就来估计其关于的次数由， e d e g e ( ) = f ( ( 以) + + ( 一) + ) + ，( + + ( 一“。) + ) 8 1 91毒弱滴 + d e g 七( 尸( 礼，七) ) ， d e g k ( j ) = ( 一j n ，一t k ) + + u u 。+ t ) + + d e g k ( p ( n 一 一t ) ) ， 鼢蕊 d e g i ( 盈j ) = d + i k ) + + ( 一j “，一i ) + + d e g t ( p ( m 七) ) 珏磊 再利用( z ) + ( 一z ) + = z ，并注意到d e 鲰( p ( n ，七) ) = d e g ( p 一j ，后一 ) ) ，得 ( 2 7 ) 左边关于七的次数为； d e g k ( ) + d e ( 巩，) 一d e 既( 点j ) = d e 乳( ) 一歹( a 一( ，) 一 ( b 一矿) d e g ( ) + ，( u a ) + + ，( y b ) + ， 其中， ”tnit w a = ，b = k ，u = u ，y = 蹦嘲z 高 ”1 于是令( 2 7 ) 左边的任何幂次的系数为零，我们至多可以得到d e g k ( ) + ，( u a ) + + ，( y b ) + + 1 个关于啦。( n ) 的方程，而未知数口l j ( n ) 的个数为：( ，+ 1 0 第二章组合恒等式机器证明的基本算法 1 ) ( j + 1 ) ，由线性代数的知识知，对于齐次线性方程组，当未知数的个数多于方 程的个数时。线性方程组有非平凡解，因此我们只需使下述不等式成立： ( + 1 ) ( j + 1 ) d e g 矗( ) + ，( u a ) + + ，( y 一日) + + l _ ( 2 8 ) 上述不等式左边关于，t ，是二次的，而右边关于，是线性的，因此当j ，l ，充 分大时，不等式( 2 8 ) 必然成立。从而( 2 7 ) 有非平凡的解，m ) 定理证毕1 s i s t e rc e 】i n e 算法即建立在上述存在性基本定理证明的基础之上 s i s t e rc e h i l e 算法 输人：正则超几何函数f ( n ，后) 输出；关于n 的多项式 啦。( 扎) ) 。使得式( 2 4 ) 成立 1 选取，和j 的初值，通常取j = ，= 1 2 假定所求递归关系形如( 2 4 ) ，其中，( n ) 为待定系数 3 在( 2 4 ) 两边同时除以f ( 几，七) ，得到( 2 6 ) ，并化简，求出公分母 4 在上一步化简得到的等式两边再同时乘以公分母，得到( 2 7 ) ，这时等式左边 是关于的多项式，将其按是的幂次合并同类项 5 令的各次幂的系数为零，得到关于啦j ( 礼) 的线性方程组如果方程组有 非平凡解，则输出结果否则，增大递归关系的阶，即增大，j 的值，转第3 步 我们之所以研究可容许超几何恒等式，是因为可容许超几何函数具有下述非 常好的性质 设f ( 扎，七) 是一个可容许的正则超几何函数，其自然支集为b ( 礼) ，记，( n ) = k 。b ( 。) f ( n ，) ，则由定理2 2 1 可知，f ( 礼，) 满足形如( 2 4 ) 的后无关递归关 系，将其对七从口( n ) 到6 ( n ) + ，求和可得 jj a ( 讳) + ，j 扣) + j l 啦。( n ) f 一j ，j c i ) = 儡。( 礼) f m j ，仇) j = o | ；o 七；“n ) j = ol = o m = d ( n ) - l 1 1 第二章组合恒等式机器证明的基本算法 由( 2 2 ) 和( 2 3 ) 可知，对任意的o 冬i ，0 j 正n2 伽，f ( n j ，m ) 对m i o ( 几) 一t ，6 ( n ) + ，一司有意义，且对o ( n ) 一i m 口( 佗一j ) 和 6 一j ) n o 其中，8 ，( 馆) = o ，1 ，乃是关于珏的多项式，且硒( 珏) o 2 3g o s p e r 算法 g o s p e r 算法是组合恒等式机器证明领域的基石，它不仅是研究不定和问题 的一个里程碑，对组合恒等式机器证明的另外两个重要算法tz e i l b e r g e r 算法和 w z 算法也产生了重要的影响，在本文第三章将要用到的新z e i l b e r g e r 算法中也 能找到g o 印e r 算法的影子本节就来介绍这一著名算法 g o s p e r 算法回答了下面的问题：给定一个超几何项k ，是否存在一个超几 何项锄满足 磊+ 1 一= k ( 2 9 ) 若答案是肯定的，该算法输出项，从而得到和式= 高“的闭形式，此 时我们称k 是g o s p e r 可求和的另一方面，如果g o s p e r 算法输出的是一个否 定的答案，则“证明”( 2 9 ) 没有超几何解 如果是一个满足( 2 9 ) 的超几何项，则 卺2 署乏2 击 ( 2 1 0 ) k + l 一：詈一l 】2 第二章组合恒等式机器证明的基本算法 是n 的有理函数令 = ( n ) k ， 这里f ( n ) 是几的有理函数用g ) k 替换( 2 9 ) 式中的，则( 2 9 ) 式变为 r ( n ) 暑，( n + 1 ) 一可( 呐= 1 ，( 2 1 1 ) r ( 扎) 由r ( 七) = t k + l t k 定义这样求( 2 9 ) 超几何解的问题就转化为寻找( 2 1 1 ) 的有理解了 后面会看到，任意的有理函数r ( 礼) ，均可表示成如下形式- 咖) = 器等， ( 2 1 2 ) 这里o ( n ) ，6 ( 竹) ，c ( n ) 是关于”的多项式，且 g c d ( n ( n ) ，6 ( n + ) ) ：l ，b 魄n ，( 2 1 3 ) 于是( 2 1 1 ) 变为 口( n ) 堕谱业_ 6 ( 州) 揣- c ( 咄 令z ( n ) = 絮搿，代入上式可得： o ( n ) z ( 礼+ 1 ) 一6 ( n 一1 ) z ( 扎) = c ( n ) ( 2 1 4 ) 可以证明卫( 礼) 是关于n 的多项式，这样，寻找( 2 9 ) 的超几何解等价于寻找 ( 2 1 4 ) 的多项式解而( 2 1 4 ) 的多项式解可以很容易的通过待定系数法得到如 果。( n ) 是( 2 1 4 ) 的多项式解，则 气= 掣如c i 凡i 是( 2 9 ) 的超几何解，反之亦然 我们将g o s p e r 算法描述如下 g 0 8 p e r 算法 输人s 超几何项屯。 输出：超几何项，满足钿+ l 一= k ，或证明不存在 1 计算r ( n ) = k + l k ，这里r ( n ) 是n 的有理函数 1 3 第二章组合恒等式机器证明的基本算法 2 将r ( n ) 表示为器絮挚的形式 3 求( 2 1 4 ) 的多项式解，如果无解，则返回磊不存在 4 返回= 皆t 。 上述g o s p e r 算法第2 步所用到的有理函数分解算法如下， 1 ，令r ( n ) ：z 翁，z 是常数， 9 是首一的互质的多项式 2 计算结式月( ) = r e s 山t a 丑t t ( ，( 扎) ，9 + ) ) 令5 = 2 ，九，是 r ( ) 的非负整数解，这里j 、r2o ，o 危1 i p t l ，。n 时，有p ( z ) o 由此定理易知，我们对他的估计可转化为对勘( n ) 末项系数的估计但两个 多项式做加减运算时有可能消去末项系数，因此更一般地，我们考虑估计o o ( n ) 的高度，也就是它所有次幂的系数绝对值的最大值另外，我们估计n ，时需要 用到0 j ( n ) 次数，为此我们引入多项式的次数高度对的概念 定义3 1 2 设多项式尸( z ) = 啦4 + 珏l 矿1 + + 8 l + 奶，称p ( z ) 关于。 的次数d 和高度 = m a 洳 l 列i 啦i 构成的有序数对( d ， ) 为多项式p ( z ) 的次 数高度对，简称