科研进展
(陈绍示)组合恒等式机器证明中Wilf-Zeilberger 猜想的证明
发布时间:2019-01-15 |来源:

  20世纪90年代,组合学家Wilf Zeilberger发展了组合恒等式机器证明的算法理论,即WZ理论。该理论彻底改变了组合恒等式与特殊函数研究的面貌。WZ理论及其相关应用促进了组合数学与符号计算的交互发展。在WZ理论中, 证明恒等式的基本思路是先证明等式两边满足相同的线性微分或差分方程,然后验证有限个初始值来完成证明。Zeilberger算法是WZ理论中用以构造恒等式中涉及求和与积分符号的表达式所满足的线性微分或差分方程的最核心算法之一。Holonomic函数(或称D-有限函数)是满足系数为多项式且解空间维数有限的线性微分方程组的一类特殊函数。这类函数包括指数函数,对数函数,三角函数,代数函数,Bessel函数,超几何函数等组合数学与数学物理中最常用的函数。Zeilberger算法就是通过算法化地操作Holonomic函数所满足的微分方程组来实现更复杂方程的构造。如果离散序列的生成函数是Holonomic的,则称该序列是Holonomic序列。在组合恒等式机器证明中,我们需要判定组合序列是否是Holonomic来保证Zeilberger算法的终止性,但是这在理论上往往是很困难的,且没有统一的方法。 

  混合超几何项是系数为多项式的一阶齐次线性微分与差分方程的解,它是指数函数,根式函数,超几何序列,二项式系数等的统一模型。 Wilf Zeilberger1992年的Invent. Math. 文章中利用混合超几何项的特殊结构给出了涉及这类函数的恒等式证明的新算法,它比适用于一般Holonomic函数的Zeilberger算法效率更高。为了保证该算法的终止性仍然需要判定相应的混合超几何项是否是Holonomic的。通过观察大量恒等式所涉及的混合超几何项的形式,Wilf Zeilberger提出了如下猜想:混合超几何项是Holonomic的当且仅当它是正则的。混合超几何项的正则性是通过一个显示的表达式来刻画的,有统一的算法来验证。在1997年,Garth Payne(美国科学院院士George Andrews 的学生)在其博士论文中解决了Wilf-Zeilberger猜想的多变元离散情形。在不知道Payne工作的情况下,南开大学的侯庆虎(陈永川院士的学生)在其2001年的博士论文中解决了该猜想的双变元离散情形,Abramov Petkovsek2002年也独立解决了该猜想的多变元离散情形。离散情形的解决主要基于多变元超几何项的Ore-Sato 结构定理。为了解决该猜想的一般离散-连续混合情形,在本人2011年的博士论文中将Ore-Sato 结构定理推广到了混合超几何情形,并在2011年国际符号与代数计算年会 (ISSAC2011) 的论文中与合作者进一步将该结构定理推广到包括q-差分情形。利用混合超几何项的结构定理,Holonomic函数与微分有限函数的Bernstein-Kashiwara等价性以及Holonomic理想的消元性质, 本人与奥地利科学院的Koutschan博士合作彻底解决了一般情形的Wilf-Zeilberger猜想。该猜想的解决意味着我们有统一的算法来判定混合超几何项是否是Holonomic的。相关文章已经被符号计算最重要杂志Journal of Symbolic Computation 接收并已在线发表。 

 

 

  发表论文    

  1.Shaoshi Chen and Christoph Koutschan. Proof of the Wilf-Zeilberger Conjecture for Mixed Hypergeometric Terms. Journal of Symbolic Computation, available on-line June 15, 2018 (https://doi.org/10.1016/j.jsc.2018.06.003)  


附件下载:

    联系我们
    参考
    相关文章