2018-08-30 | 编辑：文/先进制造部

20世纪90年代，组合学家Wilf 和Zeilberger发展了组合恒等式机器证明的算法理论，即WZ理论。该理论彻底改变了组合恒等式与特殊函数研究的面貌。计算机科学大师Knuth 认为该理论将数学中一些重要的部分从艺术转变成科学。在1996年，Wilf和Zeilberger也因此项奠基性工作获得美国数学会的Leroy P.Steel奖。WZ理论及其相关应用促进了组合数学与符号计算的交互。许多组合问题，如组合恒等式证明，格路计数问题，组合序列的同余、整除、单峰性质等等，可以借助符号计算的算法与软件得到解决或验证。在2015年出版的《Handbook of Enumerative Combinatorics》中，符号计算知名学者Manuel Kauers专门介绍了符号计算中与组合计数相关的基本算法。

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

混合超几何项是一阶齐次多项式系数线性微分与差分方程的解，它是指数函数，根式函数，超几何序列，二项式系数等的统一模型。Wilf 和 Zeilberger在1992年的Invent. Math.文章中利用混合超几何项的特殊结构给出了涉及这类函数的恒等式证明的新算法，它比适用于一般Holonomic函数的Zeilberger算法效率更高。为了保证该算法的终止性仍然需要判定相应的混合超几何项是否是Holonomic的。通过观察大量恒等式所涉及的混合超几何项的形式，Wilf 和 Zeilberger提出了如下猜想：混合超几何项是holonomic的当且仅当它是正则的。混合超几何项的正则性是通过一个显示的表达式来刻画的，有统一的算法来验证。在1997年，Garth Payne（美国科学院院士GeorgeAndrews 的学生）在其博士论文中解决了Wilf-Zeilberger猜想的多变元离散情形。在不知道Payne工作的情况下，南开大学的侯庆虎（陈永川院士的学生）在其2001年的博士论文中解决了该猜想的双变元离散情形，Abramov 与Petkovsek在2002年也独立解决了该猜想的多变元离散情形。 离散情形的解决主要基于多变元超几何项的Ore-Sato 结构定理。为了解决该猜想的一般离散-连续混合情形，先进制造部陈绍示在其2011年的博士论文中将Ore-Sato 结构定理推广到了混合超几何情形，并在2011年国际符号与代数计算年会(ISSAC2011)的论文中与合作者进一步将该结构定理推广到包括q-差分情形。利用混合超几何项的结构定理与Holonomic函数的基本性质，陈绍示与奥地利科学院的Koutschan合作彻底解决了一般情形的Wilf-Zeilberger猜想。该猜想的解决意味着我们有统一的算法来判定混合超几何项是否是Holonomic的。相关文章已经被符号计算最重要杂志Journal of Symbolic Computation 接收并已在线发表。该项工作得到了Zeilberger本人的关注与肯定，在其主页上称文章是“long-awaited paper(http://sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multiwz.html)。文章链接: https://doi.org/10.1016/j.jsc.2018.06.003.Shaoshi Chen and Christoph Koutschan. Proof of the Wilf-Zeilberger Conjecture for Mixed Hypergeometric Terms.Journal of Symbolic Computation. (Available online on June 15, 2018)