多变元D-有限幂级数的理论、算法及其在组合分析中的应用

D-finite power series were first introduced by Stanley in 1980, which are now widely used in enumerative combinatorics. D-finite power series satisfy linear differential equations with polynomial coefficients, which are generalizations of rational functions, algebraic functions and hypergeometric series. In the Wilf-Zeilberger theory, a large amount of combinatorial identities can be verified mechanically by the algorithmic manipulations of D-finite power series. The tools of symbolic computation are successfully used to solve some long-pending problems, such as Gessel’s conjecture and the q-TSPP conjecture, via efficient algorithms for D-finite power series. The theory and algorithms for univariate D-finite power series have been well-developed, while the multivariate case is still developing. In this project, we will focus on the theory and algorithms for multivariate D-finite power series and their applications in combinatorial analysis. On the theoretical side, we will study the rationality theorems, desingularization theory, and the problem of diagonal representations for such power series. On the algorithmic side, we will study the computational problems of diagonals and telescopers for multivariate D-finite power series. Finally, we will apply the theoretical and algorithmic results to solve the combinatorial problems related to the mechanical proving of combinatorial identities and enumerations of lattice walks in high dimension.

组合学家Stanley在1980年引入了具有丰富组合应用的D-有限幂级数。这类幂级数满足多项式系数的线性微分方程，是有理函数、代数函数与超几何级数的推广。在Wilf-Zeilberger理论中，一大类组合恒等式通过算法化操作D-有限幂级数得以实现机械化证明。基于D-有限幂级数的高效算法，符号计算方法现已成功地应用于解决一些组合数学中长期悬而未决的问题，如Gessel猜想与q-TSPP猜想。单变元D-有限幂级数的理论与算法已经相当成熟，而多变元情形方兴未艾。本项目主要研究多变元D-有限幂级数的理论、算法及其在组合分析中的应用。在理论方面，研究多变元D-有限幂级数的有理性定理、奇点消去理论与对角表示问题；在算法方面，研究多变元D-有限幂级数的对角与邻差算子的计算问题；在应用方面，将多变元D-有限幂级数的相应理论与算法应用于组合恒等式的机器证明与高维格路的计数问题。

多变元D-有限幂级数是组合数学中一类很基本的特殊函数。这类幂级数满足多项式系数的线性微分方程，是有理函数、代数函数与超几何级数的推广，并在数学物理、数论、符号计算等与组合相关的数学分支中有丰富的应用。 本项目主要研究多变元D-有限幂级数的理论、 算法及其在组合分析中的应用。在理论方面，给出了一类系数具有群结构的多变元D-有限幂级数的有理性定理；发展了D-有限系统的奇点消去理论与算法。在算法与应用方面，解决了三变元有理函数的邻差算子存在性判定问题，并给出了构造算法；发展了D-有限幂级数的系数对应的P-递归序列的整基理论与算法，并应用于组合恒等式机器证明。本项目所取得的研究成果丰富了多变元D-有限幂级数的理论与算法，并扩大了其在组合恒等式机器证明中的应用范围。. 本项目共发表论文15篇，其中符号计算领域最重要期刊Journal of Symbolic Computation发表3篇，符号与代数计算方向旗舰国际会议ISSAC发表7篇，数学重要期刊Advances in Applied Mathematics, European Journal of Combinatorics, Algebra and Number Theory等各发表１篇。项目负责人陈绍示在本项目资助期间获得了第二届“吴文俊计算机数学青年学者奖”（2019），国际符号与代数计算年会“ISSAC2021 杰出论文奖”（2021），国际计算机代数应用大会“ACA2022青年学者奖”（2022）。体现了本项目所取得的成果在国内外重要的学术影响。