王 晴
(天津大學數(shù)學學院,天津 300350)
求多項式系數(shù)線性差分方程的有理解在計算機代數(shù)中占有重要地位.更準確地說,K是一個域 ,a0(t),a1(t),…,ad(t),f(t) ∈K(t),找到 所有滿足
的有理函數(shù)g(t)∈K()t.許多問題都歸結于此,比如Gosper算法[1]或者尋找非齊次線性差分方程的超幾何解[2].
解決這類問題的一個通常的方法是估計出g(t)的分母,從而把這個問題歸結到找多項式解.這就引出了萬有分母,也就是此分母能夠整除每一個方程(1)解的分母.
Abramov[3-4]首先給出了尋找萬有分母的第一個算法,這個算法依賴所有的系數(shù)a0(t),a1(t),…,ad(t)和f(t);Abramov[5]改進了他的算法,改進的算法只需要利用首項系數(shù)a0(t)和末項系數(shù)ad(t),此算法得到的萬有分母稱為Abramov萬有分母;Barkatou[6]給出了關于Abramov萬有分母在矩陣差分方程中的顯式公式;Chen等[7]利用收斂性得到了相同的公式;Hou和 Mu[8]利用 Gosper算法得到了一階線性差分方程一個新的萬有分母,且這個萬有分母是Abramov萬有分母的因子.
在差分域的情況下,Karr[9-10]引入了 ∏∑-域,并給出了求和算法,允許更一般的求和.在∏∑-域中求解參數(shù)線性差分方程的一個重要應用是簡化和證明嵌套的多和表達式和恒等式.Bronstein[11]和Schneider[12-13]給出了在 ∏∑-域中計算萬有分母的界的算法;Middeke 和 Schneider[14]將萬有分母界的公式[6-7]在給定的差分系統(tǒng)中拓展到∏∑-域.特別地,將∏∑-域中分母的界[11-12]由單變量差分方程擴展到耦合系統(tǒng).本文將文獻[8]中得到的極小萬有分母推廣到∏∑-域,找到滿足
的有理函數(shù)g(t)∈K()t的萬有分母.
線性差分方程的理論與求解算法在組合數(shù)學中有廣泛的應用,尤其是組合恒等式的機器證明.計算線性差分方程的各種閉形式解往往可以轉化為計算有理函數(shù)解問題.通過估計有理函數(shù)解的萬有分母,即通過估計既約有理解的分母的一個倍式,可以將問題進一步轉化為多項式解問題,并最終借助次數(shù)估計將問題轉化為線性方程組求解問題 .給定(F,σ)的 ∏∑-擴張 (F(t),σ)和系數(shù)屬于F(t)的形式為(2)的一階線性差分方程,在假設Spread可以在F[t]中計算且為有限集合的情況下,本文給出了計算其解極小萬有分母d∈F的算法.但目前為止卻無法證明本文中的算法對于高階線性差分方程的情形適用,對于高階線性差分方程解的極小萬有分母有待于進一步研究.