Abramov's algorithm explained

In mathematics, particularly in computer algebra, Abramov's algorithm computes all rational solutions of a linear recurrence equation with polynomial coefficients. The algorithm was published by Sergei A. Abramov in 1989.^{[1] [2]}

Universal denominator

The main concept in Abramov's algorithm is a universal denominator. Let $\backslash mathbb$ be a field of characteristic zero. The dispersion $\backslash operatorname\; (p,q)$ of two polynomials $p,\; q\; \backslash in\; \backslash mathbb[n]$ is defined as$$\backslash operatorname\; (p,q)\; =\backslash max\; \backslash \; \backslash cup\; \backslash ,$$where $\backslash N$ denotes the set of non-negative integers. Therefore the dispersion is the maximum $k\; \backslash in\; \backslash N$ such that the polynomial $p$ and the $k$-times shifted polynomial

q have a common factor. It is $-1$ if such a $k$ does not exist. The dispersion can be computed as the largest non-negative integer root of the resultant $\backslash operatorname\_n\; (p(n),\; q(n+k))\; \backslash in\; \backslash mathbb[k]$.^{[3] [4]} Let $\backslash sum\_^r\; p\_k(n)\; \backslash ,\; y\; (n+k)\; =\; f(n)$ be a recurrence equation of order $r$ with polynomial coefficients p _{k} \in K [n] , polynomial right-hand side $f\; \backslash in\; \backslash mathbb[n]$ and rational sequence solution $y\; (n)\; \backslash in\; \backslash mathbb(n)$. It is possible to write $y\; (n)\; =\; p(n)/q(n)$ for two relatively prime polynomials $p,\; q\; \backslash in\; \backslash mathbb[n]$. Let $D=\backslash operatorname\; (p\_r(n-r),\; p\_0\; (n))$ and$$u(n)\; =\; \backslash gcd\; ([p\_0\; (n+D)]^,\; [p\_r\; (n-r)]^)$$where $[p(n)]^=p(n)p(n-1)\backslash cdots\; p(n-k+1)$ denotes the falling factorial of a function. Then $q(n)$ divides $u(n)$. So the polynomial $u(n)$ can be used as a denominator for all rational solutions $y(n)$ and hence it is called a universal denominator.^[5]

Algorithm

Let again $\backslash sum\_^r\; p\_k(n)\; \backslash ,\; y\; (n+k)\; =\; f(n)$ be a recurrence equation with polynomial coefficients and $u(n)$ a universal denominator. After substituting $y\; (n)\; =\; z(n)/u(n)$ for an unknown polynomial $z(n)\; \backslash in\; \backslash mathbb\; [n]$ and setting $\backslash ell(n)\; =\; \backslash operatorname(u(n),\; \backslash dots,\; u(n+r))$ the recurrence equation is equivalent to$$\backslash sum\_^r\; p\_k\; (n)\; \backslash frac\; \backslash ell(n)\; =\; f(n)\; \backslash ell(n).$$As the $u(n+k)$ cancel this is a linear recurrence equation with polynomial coefficients which can be solved for an unknown polynomial solution $z(n)$. There are algorithms to find polynomial solutions. The solutions for $z(n)$ can then be used again to compute the rational solutions $y(n)\; =\; z(n)/u(n)$.

algorithm rational_solutions is input: Linear recurrence equation $\backslash sum\_^r\; p\_k(n)\; \backslash ,\; y\; (n+k)\; =\; f(n),\; p\_k,\; f\; \backslash in\; \backslash mathbb[n],\; p\_0,\; p\_r\; \backslash neq\; 0$. output: The general rational solution $y$ if there are any solutions, otherwise false. $D\; =\; \backslash operatorname\; (p\_r(n-r),\; p\_0\; (n))$ $u(n)\; =\; \backslash gcd\; ([p\_0\; (n+D)]^,\; [p\_r\; (n-r)]^)$ $\backslash ell(n)\; =\; \backslash operatorname(u(n),\; \backslash dots,\; u(n+r))$ Solve $\backslash sum\_^r\; p\_k\; (n)\; \backslash frac\; \backslash ell(n)\; =\; f(n)\; \backslash ell(n)$ for general polynomial solution $z(n)$ if solution $z(n)$ exists then return general solution $y\; (n)\; =\; z(n)/u(n)$ else return false end if

Example

The homogeneous recurrence equation of order $1$$$(n-1)\; \backslash ,\; y(n)\; +\; (-n-1)\; \backslash ,\; y(n+1)\; =\; 0$$over $\backslash Q$ has a rational solution. It can be computed by considering the dispersion$$D\; =\; \backslash operatorname\; (p\_1\; (n-1),\; p\_0\; (n))\; =\; \backslash operatorname\; (-n,n-1)\; =\; 1.$$This yields the following universal denominator:$$u(n)\; =\; \backslash gcd\; ([p\_0\; (n+1)]^,\; [p\_r\; (n-1)]^)\; =\; (n-1)n$$and$$\backslash ell(n)\; =\; \backslash operatorname\; (u(n),\; u(n+1))\; =\; (n-1)n(n+1).$$Multiplying the original recurrence equation with $\backslash ell(n)$ and substituting $y(n)\; =\; z(n)/u(n)$ leads to$$(n-1)(n+1)\backslash ,\; z(n)\; +\; (-n-1)\; (n-1)\; \backslash ,\; z(n+1)\; =\; 0.$$This equation has the polynomial solution $z(n)\; =\; c$ for an arbitrary constant $c\; \backslash in\; \backslash Q$. Using $y(n)\; =\; z(n)\; /\; u(n)$ the general rational solution is$$y(n)\; =\; \backslash frac$$for arbitrary $c\; \backslash in\; \backslash Q$.

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. 10.1016/s0041-5553(89)80002-3. 0041-5553.
2. Book: Abramov, Sergei A.. 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. 1995. http://dl.acm.org/citation.cfm?id=220346.220383. 285–289. 10.1145/220346.220383. 978-0897916998. 15424889.
3. Book: Man. Yiu-Kwong. Wright. Francis J.. Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94 . Fast polynomial dispersion computation and its application to indefinite summation . 1994. 175–180. 10.1145/190347.190413. 978-0897916387. 2192728.
4. Book: Gerhard, Jürgen. Modular Algorithms in Symbolic Summation and Symbolic Integration . Lecture Notes in Computer Science . 2005. 3218. en-gb. 10.1007/b104035. 0302-9743. 978-3-540-24061-7.
5. Chen. William Y. C.. Paule. Peter. Saad. Husam L.. 2007. Converging to Gosper's Algorithm. 0711.3386. math.CA.