DOI：10.19789/j.1004-9398.2022.02.002

文献引用：王晴.∏∑-域上一阶线性差分方程的极小万有分母[J].首都师范大学学报（自然科学版），2022，43（2）：7-13+28.WANG Q.Minimal universal denominators for first-order linear difference equations in ∏∑-fields[J].Journal of Capital Normal University（Natural Science Edition），2022，43（2）：7-13+28.

∏∑-域上一阶线性差分方程的极小万有分母*

王 晴

（天津大学数学学院，天津 300350）

摘要：符号求和的一个关键问题是求解线性差分方程的有理解.解决这类问题的第一步是得到每个有理解分母的界，一旦知道分母界，就可以将有理解的问题简化为多项式解的问题.本文提供了一种用于在∏∑-域中寻找多项式系数一阶线性差分方程有理解的极小万有分母的算法，得到的极小万有分母为根据Abramov算法在∏∑-域上推广得到的万有分母的因子.

关键词：线性差分方程；极小万有分母；Abramov万有分母；∏∑-域

中图分类号：O157.1

收稿日期：2021-01-11

*国家自然科学基金项目（11771330）

Minimal universal denominators for first-order linear difference equations in∏∑-fields*

WANG Qing
（School of Mathematics，Tianjin University，Tianjin 300350）

Abstract：A key problem of symbolic summation is to solve the rational solution of linear difference equation.The first step in solving it is to obtain the denominator bound of each rational solution.Once the denominator bound is known，the problem of solving rational solutions is reduced to the problem of solving polynomial solutions.This study provides an algorithm for finding a minimal universal denominator of rational solutions for fist-order linear difference equation with polynomial coefficients in ∏∑-fields，and the minimal universal denominator is a factor of universal denominator obtained by the generalization of the Abramov algorithm in∏∑-fields.

Keywords：linear difference equation；minimal universal denominator；Abramov’s universal denominator；∏∑-fields

CLC：O157.1

0 引 言

求多项式系数线性差分方程的有理解在计算机代数中占有重要地位.更准确地说，K是一个域 ，a0(t)，a1(t)，…，ad(t)，f(t) ∈ K(t)，找到 所有满足

的有理函数g(t)∈K()t.许多问题都归结于此，比如Gosper算法[1]或者寻找非齐次线性差分方程的超几何解[2].

解决这类问题的一个通常的方法是估计出g(t)的分母，从而把这个问题归结到找多项式解.这就引出了万有分母，也就是此分母能够整除每一个方程（1）解的分母.

Abramov[3-4]首先给出了寻找万有分母的第一个算法，这个算法依赖所有的系数a0(t)，a1(t)，…，ad(t)和f(t)；Abramov[5]改进了他的算法，改进的算法只需要利用首项系数a0(t)和末项系数ad(t)，此算法得到的万有分母称为Abramov万有分母；Barkatou[6]给出了关于Abramov万有分母在矩阵差分方程中的显式公式；Chen等[7]利用收敛性得到了相同的公式；Hou和 Mu[8]利用 Gosper算法得到了一阶线性差分方程一个新的万有分母，且这个万有分母是Abramov万有分母的因子.

在差分域的情况下，Karr[9-10]引入了 ∏∑-域，并给出了求和算法，允许更一般的求和.在∏∑-域中求解参数线性差分方程的一个重要应用是简化和证明嵌套的多和表达式和恒等式.Bronstein[11]和Schneider[12-13]给出了在 ∏∑-域中计算万有分母的界的算法；Middeke 和 Schneider[14]将万有分母界的公式[6-7]在给定的差分系统中拓展到∏∑-域.特别地，将∏∑-域中分母的界[11-12]由单变量差分方程扩展到耦合系统.本文将文献[8]中得到的极小万有分母推广到∏∑-域，找到满足

的有理函数g(t)∈K()t的万有分母.

1 万有分母

2 极小性

3 例 子

4 结束语

线性差分方程的理论与求解算法在组合数学中有广泛的应用，尤其是组合恒等式的机器证明.计算线性差分方程的各种闭形式解往往可以转化为计算有理函数解问题.通过估计有理函数解的万有分母，即通过估计既约有理解的分母的一个倍式，可以将问题进一步转化为多项式解问题，并最终借助次数估计将问题转化为线性方程组求解问题 .给定(F，σ)的 ∏∑-扩张 (F(t)，σ)和系数属于F(t)的形式为（2）的一阶线性差分方程，在假设Spread可以在F[t]中计算且为有限集合的情况下，本文给出了计算其解极小万有分母d∈F的算法.但目前为止却无法证明本文中的算法对于高阶线性差分方程的情形适用，对于高阶线性差分方程解的极小万有分母有待于进一步研究.

参考文献

[1]PETKOVŠEK M.A generalization of Gosper's algorithm[J].Discrete Mathematics，1994，134（1/2/3）：125-131.

[2]PETKOVŠEK M.Hypergeometric solutions of linear recurrences with polynomial coefficients[J].Journal of Symbolic Computation，1992，14（2/3）：243-264.

[3]ABRAMOV S A.Rational solutions of linear differential and difference equations with polynomial coeffcients[J].USSR Computational Mathematics and Mathematical Physics，1991，29：7-12.

[4]ABRAMOV S A.The denominators of rational solutions to linear difference equations[J].Programming and Computer Software，1994，20（1）：30-33.

[5]ABRAMOV S A.Rational solutions of linear difference and q-difference equations with polynomial coeffcients[J].In ISSAC95：International Symposium on Symbolic and Algebraic Computation，1995（6）：285-289.

[6]BARKATOU M A.Rational solutions of matrix difference equations：the problem of equivalence and factorization [C]//GEDDES K.In ISSAC 99：International symposium on symbolic and algebraic computation.Vancouver：Association for Computing Machinery，1999.

[7]CHEN Y C，PAULE P，SAAD H L.Converging to Gosper's algorithm[J].Advances in Applied Mathematics，2008，41（3）：351-364.

[8]HOU Q H，MU Y P.Minimal universal denominators for linear difference equations[J].Journal of Difference Equations and Applications，2011，17（6）：977-986.

[9]KARR M.Summation in finite terms[J].Journal of the ACM，1981，28（2）：305-350.

[10]KARR M.Theory of summation in finite terms[J].Journal of Symbolic Computation，1985，1：303-315.

[11]BRONSTEIN M.On solutions of linear ordinary difference equations in their coefficient field[J].Journal of Symbolic Computation，2000，29（6）：841-877.

[12]SCHNEIDER C.A collection of denominator bounds to solve parameterized linear difference equations in∏∑-extensions[J].Annals of the West University of Timisoara：Mathematics and Computer Science，2004，42（2）：163-179.

[13]SCHNEIDER C.Symbolic summation in difference filelds[D].Austria：Johannes Kepler University Linz，2001.

[14]MIDDEKE J，SCHNEIDER C.Denominator bounds for systems of recurrence equations using∏∑-Extensions[M].Austria：Advances in Computer Algebra，2018：149-173.

[15]ABRAMOV S A，BRONSTEIN M，PETKOVŠEK M，et al.On rational and hypergeometric solutions of linear ordinary difference equations in∏∑*-field extensions[J].Journal of Symbolic Computation，2021，107：23-66.

（责任编辑：马田田）