# Abramov's algorithm

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.

## 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$\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$ 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}\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)]^{\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$\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)}.

## Example

The homogeneous recurrence equation of order 1{\textstyle 1}$(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=\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)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n$and$\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.$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)={\frac {c}{(n-1)n}}$for arbitrary c∈Q{\textstyle c\in \mathbb {Q} }.