基于离散余数的有理数可求和性的计算方法及其应用
《Journal of Symbolic Computation》:A computational approach to rational summability and its applications via discrete residues
【字体:
大
中
小
】
时间:2026年02月11日
来源:Journal of Symbolic Computation 0.9
编辑推荐:
卡洛斯·E·阿雷切 | 哈里·P·西陶拉
德克萨斯大学达拉斯分校数学科学系,美国德克萨斯州理查森市坎贝尔西路800号,邮编75080
**摘要**
若存在有理函数$g(x)$使得$f(x)=g(x+1)-g(x)$,则称有理函数$f(x)$为可理性求和的。判断给定有
卡洛斯·E·阿雷切 | 哈里·P·西陶拉
德克萨斯大学达拉斯分校数学科学系,美国德克萨斯州理查森市坎贝尔西路800号,邮编75080
**摘要**
若存在有理函数$g(x)$使得$f(x)=g(x+1)-g(x)$,则称有理函数$f(x)$为可理性求和的。判断给定有理函数是否可求和是研究移位差分方程相关问题的重要基础计算问题。2012年,陈与辛格提出了离散残差概念,该概念具有阻碍性性质:一个有理函数可求和当且仅当其所有离散残差均为零。然而,这些离散残差需要基于该有理函数的完全部分分式分解结果来定义,而这类分解通常无法通过计算获得。本文介绍了如何仅借助最大公约数运算、线性代数以及一个用于计算分母多项式自分散集的“黑箱”算法,高效地计算任意有理函数的离散残差(及其有理表达形式)。同时,本文还阐述了如何将这类算法应用于序列可求和问题与创造性望远镜求和问题,以及如何利用这些计算结果研究差分方程的伽罗瓦群。
**引言**
设$K$为特征为零的域,且不假定其为代数闭域,用$K(x)$表示以$K$中系数为元素、关于未知数$x$的有理函数域。给定$f(x)\in K(x)$,阿布拉莫夫在1971年首次提出了有理求和问题,即寻找$f(x)=g(x+1)-g(x)+h(x)$中的$g(x),h(x)\in K(x)$,并要求$h(x)$的分母次数尽可能小。这样的$h(x)$被称为$f(x)$的简化形式。在过去半个世纪中,有理求和问题吸引了众多学者的关注(参见相关文献)。不难看出,该问题存在解——可从平凡的(未必是最简的)对$(g(x),h(x))=(f(x-1),f(x-1))$出发,再运用良序原理即可得到解。此外,若已知一组解$(g(x),h(x))$,还可得到另一组解$(g(x)-h(x),h(x+1))$,因为$h(x+1)$的分母次数与$h(x)$相同,因此即便是最简解通常也并非唯一。在现有研究中,人们采用了多种方法来处理这种非唯一性问题。例如,可以要求$g(x)$的分母尽可能小,或者尽可能高效地计算出满足方程(1.1)的任意解$(g(x),h(x))$。皮拉斯特与斯特雷尔在1995年的文章中对这些不同方法进行了简要总结与比较。
任何解决有理求和问题的算法,都会顺便解决另一个问题:即判断给定$f(x)\in K(x)$时,是否存在$g(x)\in K(x)$使得$f(x)=g(x+1)-g(x)$(仅需回答“是/否”)。此时称$f(x)$为可理性求和的。为了解决这个更简单的问题,人们设计了多种算法,避免进行通常成本高昂且往往无关紧要的证书$g(x)$的计算。相关研究可见马图塞维奇2000年的论文、格哈德等人2003年的研究、博斯坦等人2010年的工作、陈与辛格2012年的成果、陈等人2015年的研究、侯与王2015年的论文、吉斯布雷希特等人2022年的研究及其中引用的文献。
本文的主要目标是详细阐述如何有效、高效地实现陈与辛格2012年提出的基于残差理论的有理可求和判定方法,这一方法是在阿雷切与西陶拉2024年的初步研究成果基础上进一步发展而来的。$f(x)\in K(x)$的离散残差(见定义3.1)是一组属于$K$的代数闭包$K^{\prime}$的常数,它们由$f(x)$的完全部分分式分解结果定义,具有阻碍性性质:当且仅当$f(x)$可理性求和时,这些残差才全部为零。通常情况下,直接根据定义计算这些离散残差是不可能的,因为对分母多项式进行必要的线性因子分解同样难以实现。我们在这里提出的算法避免了昂贵或不可行的分母多项式线性因子完全分解,几乎完全依赖于最大公约数运算与线性代数。之所以说“几乎”,是因为我们确实需要一个“黑箱”算法来计算多项式的自分散集,而目前已知最有效的计算该方法依赖于对$K[x]$中分母多项式进行不可约因子分解(关于这一重要且微妙的问题,详见备注5.3)。除了计算方法之外,离散残差的原始定义还存在另一个固有问题:通常这些残差属于$K$的任意高次代数扩展域。因此,受布朗斯坦与萨尔维1993年定理的启发,我们提出了$f(x)\in K(x)$的离散残差的$K$-有理表示方法,即用多项式对来表示这些残差。对于每一对多项式,第一个多项式的根集合对应了$f(x)$具有非零残差的位置,第二个多项式在这些根处的取值则对应了相应的离散残差值(更多细节见定义3.4)。
推动我们所有计算的一个关键思想是:通过对$f(x)$反复应用经典的埃尔米特约化方法,我们可以将研究重点集中在$f(x)$仅有简单极点的特殊情形上。这一思路最早在霍洛维茨1971年的论文中有所提及,但在现有文献中似乎并未得到广泛应用。因此,本文的次要目标就是推广这一实用技巧。尽管我们尚未正式计算出该方法的理论最坏情况复杂度(见算法1),但我们推测,就分母次数而言,其复杂度应与仅应用一次经典埃尔米特约化方法的复杂度大致相同。
一旦将问题简化为仅有简单极点的有理函数情形,所有用于计算$f(x)$的简化形式$h(x)$的方法似乎都会呈现出相似的思路。正如阿雷切与西陶拉2024年所提到的,我们的方法与格哈德等人2003年的方法思路类似。但后者的步骤必然更为复杂,因为它需要处理比我们所需的更一般的输入,而我们已经通过前面的约化将问题简化为仅有简单极点的情形。我们方法的相对简洁性正是让我们能够轻松衍生出更适合特定用途的变体。
一旦我们计算出了$f(x)$的简化形式$f^{\bar{x}}$,且该形式的分母既无平方因子也无移位因子,那么$f(x)$的离散残差就会与$f^{\bar{x}}$的经典一阶残差相等。后者无需因式分解即可通过特雷格1976年的著名结论进行计算。
我们之所以关注离散残差的计算,部分原因是受到以下序列型可求和问题的启发,这类问题通常是计算与移位差分方程相关的伽罗瓦群算法中的基础子问题(参见范德普特与辛格1997年的研究、亨德里克斯1998年的研究)。给定任意$n$元有理函数组$f=(f_1(x),\dots,f_n(x))\in K(x)^n$,我们在命题7.4中展示了如何计算$K$-向量空间$V(f):=\{v=(v_1,\dots,v_n)\in K^n \mid v_1f_1+\dots+v_nf_n$是可求和的$\}$的基。我们方法的适应性还使我们能够在命题7.7中处理序列型微分创造性望远镜问题,这类问题是对方程(1.2)的推广,即将未知常数$v_i\in K$替换为具有$K$系数的未知线性微分算子$L_i\in K[ddx]$。类似地,这类问题也经常出现在计算移位差分方程的微分伽罗瓦群的过程中(参见哈杜安与辛格2008年的研究、阿雷切2017年的研究)。在计算这类微分算子空间时,还有一个额外的难点,即需要事先确定需要考虑的算子的阶数。据我们所知,第一个此类上界是在命题7.9中得到的,该上界的得出依赖于我们关于离散残差的算法研究成果。
我们基于离散残差的方法使得同时处理多个$f_i(x)$的问题变得极为简单,就像方程(1.2)中所做的那样;而使用其他约化方法来实现类似适配则不太容易(不过可参考陈等人2015年的第5节)。对于$q$-差分方程(陈与辛格2012年)、马勒差分方程(阿雷切与张2022年、阿雷切与张2024年),以及椭圆曲线上的差分方程(德雷弗斯等人2018年、哈杜安与辛格2021年、巴比特2025年、阿雷切与巴比特2025年),也存在离散残差的直接类比形式。我们希望,我们在此继续发展的这种概念上简洁的方法,也能有助于在移位情形之外的其他相关(但技术难度更高的)领域中构建类似方法。
与阿雷切与西陶拉2024年提出的早期初步版本相比,本文进行了多处修正与改进,同时还增加了一些新内容。新增内容包括:第7.2节对序列型微分望远镜问题的详细讨论(在阿雷切与西陶拉2024年的备注7.5中仅作了简要提及)、第8节对伽罗瓦理论应用的拓展讨论(在阿雷切与西陶拉2024年的第8节中仅作了简要概述)、第9节基于我们部分基本算法的初步实现所进行的实验时间分析,以及第10节中的一些新的、经过扩展的示例,这些示例用于说明我们的主要算法及其不同变体之间的差异。
**章节片段**
**基本符号与约定**
我们用$N$表示严格正整数集合,用$K$表示一个可计算的、特征为零的域。用$K^{\prime}$表示$K$的一个固定代数闭包。我们不假定$K$是代数闭域,在证明或定义理论概念时才会用到$K^{\prime}$,而在实际计算中则不会使用它。我们对$K$做一个如下技术性假设:要么可以计算出所有以$K$中系数为元素的任意多项式方程的整数解,要么……
**离散残差与可求和性**
**定义3.1**(陈与辛格,2012年,定义2.3)
设$f\in K(x)$,考虑其完全部分分式分解:
$$f=p+\sum_{k\in N}\sum_{\alpha\in K^{\prime}}c_k(\alpha)(x-\alpha)^k,$$
其中$p\in K[x]$,且对于所有的$k\in N$和$\alpha\in K^{\prime}$,除了有限个$c_k(\alpha)$之外,其余的都等于零。则$f$在轨道$\omega\in K^{\prime}/Z$处的$k$阶离散残差定义为:
$$dres(f,\omega,k):=\sum_{\alpha\in\omega}c_k(\alpha).$$
离散残差与有理可求和性研究的相关性可通过以下结论体现。
**命题3.2**(陈与辛格,2012年,命题2.5)
$f\in K(x)$是可理性求和的,当且仅当对于所有的$\omega\in K^{\prime}$和$k\in N$,都有$dres(f,\omega,k)=0$。如陈与辛格(2012年,备注)所指出的……
**迭代埃尔米特约化**
从定义3.1可以直接看出,$f\in K(x)$中的多项式部分$p$无论是对研究可求和性还是计算离散残差来说都是无关的。因此,从本节开始,我们将研究范围限制在真有理函数$f\in K(x)$上。
我们的首要任务是将问题简化为$f$的分母为无平方因子的情形。在本节中,我们将介绍如何计算对于$f$的理论部分分式分解(3.1)而言,满足特定条件的多项式$f_k\in K(x)$,即……
**简单约化**
上一节的结果让我们能够进一步将研究范围限制在具有简单极点的真有理函数$f\in K(x)$上。我们可以将这类函数唯一表示为$f=ab$的形式,其中$a,b\in K[x]$,$b$为首一多项式且无平方因子,同时满足$\deg(a)<\deg(b)$。
我们下面的算法3可以计算出一个简化形式$f^{\bar{x}}\in K(x)$,使得对于所有的$\omega\in K^{\prime}/Z$,都有$dres(f,\omega,1)=dres(f^{\bar{x}},\omega,1)$,并且$f^{\bar{x}}$的分母既无平方因子也无移位因子。正如我们在引言中已经提到的,目前已经有许多算法被开发出来……
**离散残差的计算**
现在,我们希望将前面各节中介绍的算法结合起来,按照第3节所述的方式,符号化地计算任意真有理函数$f\in K(x)$的所有离散残差。为此,我们首先回顾以下结论,它阐述了如何借助辅助多项式以符号方式计算经典剩余值,以及简短的证明,说明了如何在实践中实际计算该多项式。引理6.1,Trager,1976年,引理5.1:设f=ab∈K(x),其中a,b∈K[x]且满足a≠0、deg(a)
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号