Wilf-Zeilberger 理论的算法设计, 复杂度分析及其应用

In the 1990s, combinatorists Wilf and Zeilberger developed an algorithmic proof theory for combinatorial identities, which is called the Wilf-Zeilberger theory. This theory has been the bridge between symbolic computation and other research fields, such as combinatoric, special-function theory, and mathematical physics etc. Telescoper is the core concept of this theory. The two fundamental problems on telescopers are:.1. for a given special function, how to decide the existence of telescopers, i.e., the existence problem;.2. if telescopers exist, how to design efficient algorithms to compute them, i.e., the construction problem..In the bivariate case, these problems have been solved rather satisfactorily. The project mainly concerns the existence of telescopers and their construction in the case of three or more variables. The main challenge in this project is to develop algorithms for symbolic integration and summation for multivariate functions. We plan to apply classical results on algebraic surfaces, and use recent results on the structure.of the hyperexpoential-hypergeometric terms and discrete residues. As applications, we will apply our results to the computational problems in enumerative combinatorics, statistical physics, and the Galois theory of parameterized differential equations.

上世纪90年代，组合学家 Wilf和 Zeilberger建立了组合恒等式的机器证明理论，即Wilf-Zeilberger 理论。 该理论现已成为符号计算应用于组合数学，特殊函数论，数学物理等领域的桥梁。邻差算子是 Wilf-Zeilberger 理论的核心概念。与此相关的两个基本问题是：1. 对于给定特殊函数，如何判定邻差算子是否存在，即存在性问题；2. 在邻差算子存在的前提下，如何设计高效算法计算邻差算子，即构造性问题。在双变元情形，上述问题已经得到比较完整的解答。本项目主要针对三元或更多元情形，研究邻差算子的存在性及其构造。其难点是多元函数的符号积分与求和问题。我们计划利用经典的代数曲面理论，以及近年来发展的超指数-超几何项的结构定理与离散留数方法对上述问题展开研究, 并且将研究结果应用于解决计数组合学，统计物理，含参微分方程伽罗瓦理论等领域中一些困难的计算问题。

上世纪90年代初，组合学家Wilf和Zeilberger建立了组合恒等式机器证明的算法理论，即Wilf-Zeilberger 理论。 该理论现已成为符号计算应用于组合数学，特殊函数论，数学物理等领域的桥梁。邻差算子是 Wilf-Zeilberger 理论的核心概念。与此相关的两个基本问题是：1. 对于给定特殊函数，如何判定邻差算子是否存在，即存在性问题；2. 在邻差算子存在的前提下，如何设计高效算法计算邻差算子，即构造性问题。.本项目围绕这两个基本问题开展了系统性的研究。在存在性问题方面，解决了著名的Wilf-Zeilberger猜想，从而给出了判定混合超几何项的完整性的高效算法；首次建立了三变元有理函数的邻差算子存在的判定准则, 解决了Zeilberger算法对此类函数的终止性问题。在构造性问题方面，发展了基于约化的构造代数函数与Fuchsian微分有限函数的邻差算子的高效算法, 并应用于组合恒等式的自动证明与格路计数等问题。微分有限函数是Wilf-Zeilberger理论涉及的一类重要特殊函数。本项目也给出了消去这类函数的伪奇点的随机高效算法，并将Szego型有理性定理从单变元推广到多变元。以上成果得到了国际同行包括美国Rutger大学的Zeilberger教授的肯定。本项目共发表文章11篇，其中符号计算领域最重要期刊Journal of Symbolic Computation发表4篇，符号与代数计算方向权威国际会议ISSAC发表4篇，组合理论最权威期刊Journal of Combinatorial Theory, Series A 发表1篇。