• Images
• Videos
• Documents
• Books
• Articles

Universal denominator

The main concept in Abramov's algorithm is a universal denominator. Let K {\textstyle \mathbb {K} } be a field of characteristic zero. The dispersion dis ⁡ ( p , q ) {\textstyle \operatorname {dis} (p,q)} of two polynomials p , q ∈ K [ n ] {\textstyle p,q\in \mathbb {K} [n]} is defined as dis ⁡ ( p , q ) = max { k ∈ N : deg ⁡ ( gcd ( p ( n ) , q ( n + k ) ) ) ≥ 1 } ∪ { − 1 } , {\displaystyle \operatorname {dis} (p,q)=\max\{k\in \mathbb {N} \,:\,\deg(\gcd(p(n),q(n+k)))\geq 1\}\cup \{-1\},} where N {\textstyle \mathbb {N} } denotes the set of non-negative integers. Therefore the dispersion is the maximum k ∈ N {\textstyle k\in \mathbb {N} } such that the polynomial p {\textstyle p} and the k {\textstyle k} -times shifted polynomial q {\displaystyle q} have a common factor. It is − 1 {\textstyle -1} if such a k {\textstyle k} does not exist. The dispersion can be computed as the largest non-negative integer root of the resultant res n ⁡ ( p ( n ) , q ( n + k ) ) ∈ K [ k ] {\textstyle \operatorname {res} _{n}(p(n),q(n+k))\in \mathbb {K} [k]} .³⁴ Let ∑ k = 0 r p k ( n ) y ( n + k ) = f ( n ) {\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)} be a recurrence equation of order r {\textstyle r} with polynomial coefficients p k ∈ K [ n ] {\displaystyle p_{k}\in \mathbb {K} [n]} , polynomial right-hand side f ∈ K [ n ] {\textstyle f\in \mathbb {K} [n]} and rational sequence solution y ( n ) ∈ K ( n ) {\textstyle y(n)\in \mathbb {K} (n)} . It is possible to write y ( n ) = p ( n ) / q ( n ) {\textstyle y(n)=p(n)/q(n)} for two relatively prime polynomials p , q ∈ K [ n ] {\textstyle p,q\in \mathbb {K} [n]} . Let D = dis ⁡ ( p r ( n − r ) , p 0 ( n ) ) {\textstyle D=\operatorname {dis} (p_{r}(n-r),p_{0}(n))} and u ( n ) = gcd ( [ p 0 ( n + D ) ] D + 1 _ , [ p r ( n − r ) ] D + 1 _ ) {\displaystyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})} where [ p ( n ) ] k _ = p ( n ) p ( n − 1 ) ⋯ p ( n − k + 1 ) {\textstyle [p(n)]^{\underline {k}}=p(n)p(n-1)\cdots p(n-k+1)} denotes the falling factorial of a function. Then q ( n ) {\textstyle q(n)} divides u ( n ) {\textstyle u(n)} . So the polynomial u ( n ) {\textstyle u(n)} can be used as a denominator for all rational solutions y ( n ) {\textstyle y(n)} and hence it is called a universal denominator.⁵

Algorithm

Let again ∑ k = 0 r p k ( n ) y ( n + k ) = f ( n ) {\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)} be a recurrence equation with polynomial coefficients and u ( n ) {\textstyle u(n)} a universal denominator. After substituting y ( n ) = z ( n ) / u ( n ) {\textstyle y(n)=z(n)/u(n)} for an unknown polynomial z ( n ) ∈ K [ n ] {\textstyle z(n)\in \mathbb {K} [n]} and setting ℓ ( n ) = lcm ⁡ ( u ( n ) , … , u ( n + r ) ) {\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))} the recurrence equation is equivalent to ∑ k = 0 r p k ( n ) z ( n + k ) u ( n + k ) ℓ ( n ) = f ( n ) ℓ ( n ) . {\displaystyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n).} As the u ( n + k ) {\textstyle u(n+k)} cancel this is a linear recurrence equation with polynomial coefficients which can be solved for an unknown polynomial solution z ( n ) {\textstyle z(n)} . There are algorithms to find polynomial solutions. The solutions for z ( n ) {\textstyle z(n)} can then be used again to compute the rational solutions y ( n ) = z ( n ) / u ( n ) {\textstyle y(n)=z(n)/u(n)} .⁶

algorithm rational_solutions is input: Linear recurrence equation ∑ k = 0 r p k ( n ) y ( n + k ) = f ( n ) , p k , f ∈ K [ n ] , p 0 , p r ≠ 0 {\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n),p_{k},f\in \mathbb {K} [n],p_{0},p_{r}\neq 0} . output: The general rational solution y {\textstyle y} if there are any solutions, otherwise false. D = disp ⁡ ( p r ( n − r ) , p 0 ( n ) ) {\textstyle D=\operatorname {disp} (p_{r}(n-r),p_{0}(n))} u ( n ) = gcd ( [ p 0 ( n + D ) ] D + 1 _ , [ p r ( n − r ) ] D + 1 _ ) {\textstyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})} ℓ ( n ) = lcm ⁡ ( u ( n ) , … , u ( n + r ) ) {\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))} Solve ∑ k = 0 r p k ( n ) z ( n + k ) u ( n + k ) ℓ ( n ) = f ( n ) ℓ ( n ) {\textstyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n)} for general polynomial solution z ( n ) {\textstyle z(n)} if solution z ( n ) {\textstyle z(n)} exists then return general solution y ( n ) = z ( n ) / u ( n ) {\textstyle y(n)=z(n)/u(n)} else return false end if

Example

The homogeneous recurrence equation of order 1 {\textstyle 1} ( n − 1 ) y ( n ) + ( − n − 1 ) y ( n + 1 ) = 0 {\displaystyle (n-1)\,y(n)+(-n-1)\,y(n+1)=0} over Q {\textstyle \mathbb {Q} } has a rational solution. It can be computed by considering the dispersion D = dis ⁡ ( p 1 ( n − 1 ) , p 0 ( n ) ) = disp ⁡ ( − n , n − 1 ) = 1. {\displaystyle D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {disp} (-n,n-1)=1.} This yields the following universal denominator: u ( n ) = gcd ( [ p 0 ( n + 1 ) ] 2 _ , [ p r ( n − 1 ) ] 2 _ ) = ( n − 1 ) n {\displaystyle u(n)=\gcd([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n} and ℓ ( n ) = lcm ⁡ ( u ( n ) , u ( n + 1 ) ) = ( n − 1 ) n ( n + 1 ) . {\displaystyle \ell (n)=\operatorname {lcm} (u(n),u(n+1))=(n-1)n(n+1).} Multiplying the original recurrence equation with ℓ ( n ) {\textstyle \ell (n)} and substituting y ( n ) = z ( n ) / u ( n ) {\textstyle y(n)=z(n)/u(n)} leads to ( n − 1 ) ( n + 1 ) z ( n ) + ( − n − 1 ) ( n − 1 ) z ( n + 1 ) = 0. {\displaystyle (n-1)(n+1)\,z(n)+(-n-1)(n-1)\,z(n+1)=0.} This equation has the polynomial solution z ( n ) = c {\textstyle z(n)=c} for an arbitrary constant c ∈ Q {\textstyle c\in \mathbb {Q} } . Using y ( n ) = z ( n ) / u ( n ) {\textstyle y(n)=z(n)/u(n)} the general rational solution is y ( n ) = c ( n − 1 ) n {\displaystyle y(n)={\frac {c}{(n-1)n}}} for arbitrary c ∈ Q {\textstyle c\in \mathbb {Q} } .

WikiProject Mathematics on Wikidata

References

1. Abramov, Sergei A. (1989). "Rational solutions of linear differential and difference equations with polynomial coefficients". USSR Computational Mathematics and Mathematical Physics. 29 (6): 7–12. doi:10.1016/s0041-5553(89)80002-3. ISSN 0041-5553. /wiki/Doi_(identifier) ↩

2. Abramov, Sergei A. (1995). "Rational solutions of linear difference and q -difference equations with polynomial coefficients". Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95. pp. 285–289. doi:10.1145/220346.220383. ISBN 978-0897916998. S2CID 15424889. 978-0897916998 ↩

3. Man, Yiu-Kwong; Wright, Francis J. (1994). "Fast polynomial dispersion computation and its application to indefinite summation". Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94. pp. 175–180. doi:10.1145/190347.190413. ISBN 978-0897916387. S2CID 2192728. 978-0897916387 ↩

4. Gerhard, Jürgen (2005). Modular Algorithms in Symbolic Summation and Symbolic Integration. Lecture Notes in Computer Science. Vol. 3218. doi:10.1007/b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743. 978-3-540-24061-7 ↩

5. Chen, William Y. C.; Paule, Peter; Saad, Husam L. (2007). "Converging to Gosper's Algorithm". arXiv:0711.3386 [math.CA]. /wiki/ArXiv_(identifier) ↩

6. Abramov, Sergei A. (1995). "Rational solutions of linear difference and q -difference equations with polynomial coefficients". Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95. pp. 285–289. doi:10.1145/220346.220383. ISBN 978-0897916998. S2CID 15424889. 978-0897916998 ↩