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.^{[1] [2]}

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

Let again ${\textstyle \sum _{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 ${\textstyle u(n)}${\textstyle u(n)} a universal denominator. After substituting ${\textstyle y(n)=z(n)/u(n)}${\textstyle y(n)=z(n)/u(n)} for an unknown polynomial ${\textstyle z(n)\in \mathbb {K} [n]}${\textstyle z(n)\in \mathbb {K} [n]} and setting ${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))}${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))} the recurrence equation is equivalent to$${\displaystyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n).}$${\displaystyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (n).}As the ${\textstyle 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 ${\textstyle z(n)}${\textstyle z(n)}. There are algorithms to find polynomial solutions. The solutions for ${\textstyle z(n)}${\textstyle z(n)} can then be used again to compute the rational solutions ${\textstyle y(n)=z(n)/u(n)}${\textstyle y(n)=z(n)/u(n)}.^[2]

algorithm rational_solutions is
 input: Linear recurrence equation ${\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}${\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 ${\textstyle y}${\textstyle y} if there are any solutions, otherwise false.
 ${\textstyle D=\operatorname {disp} (p_{r}(n-r),p_{0}(n))}${\textstyle D=\operatorname {disp} (p_{r}(n-r),p_{0}(n))}
 ${\textstyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})}${\textstyle u(n)=\gcd([p_{0}(n+D)]^{\underline {D+1}},[p_{r}(n-r)]^{\underline {D+1}})}
 ${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))}${\textstyle \ell (n)=\operatorname {lcm} (u(n),\dots ,u(n+r))}
 Solve ${\textstyle \sum _{k=0}^{r}p_{k}(n){\frac {z(n+k)}{u(n+k)}}\ell (n)=f(n)\ell (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 ${\textstyle z(n)}${\textstyle z(n)}
 if solution ${\textstyle z(n)}${\textstyle z(n)} exists then
 return general solution ${\textstyle y(n)=z(n)/u(n)}${\textstyle y(n)=z(n)/u(n)}
 else
 return false
 end if

The homogeneous recurrence equation of order ${\textstyle 1}${\textstyle 1}$${\displaystyle (n-1),円y(n)+(-n-1),円y(n+1)=0}$${\displaystyle (n-1),円y(n)+(-n-1),円y(n+1)=0}over ${\textstyle \mathbb {Q} }${\textstyle \mathbb {Q} } has a rational solution. It can be computed by considering the dispersion$${\displaystyle D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {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:$${\displaystyle u(n)=\gcd([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n}$${\displaystyle u(n)=\gcd([p_{0}(n+1)]^{\underline {2}},[p_{r}(n-1)]^{\underline {2}})=(n-1)n}and$${\displaystyle \ell (n)=\operatorname {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 ${\textstyle \ell (n)}${\textstyle \ell (n)} and substituting ${\textstyle y(n)=z(n)/u(n)}${\textstyle y(n)=z(n)/u(n)} leads to$${\displaystyle (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 ${\textstyle z(n)=c}${\textstyle z(n)=c} for an arbitrary constant ${\textstyle c\in \mathbb {Q} }${\textstyle c\in \mathbb {Q} }. Using ${\textstyle y(n)=z(n)/u(n)}${\textstyle y(n)=z(n)/u(n)} the general rational solution is$${\displaystyle y(n)={\frac {c}{(n-1)n}}}$${\displaystyle y(n)={\frac {c}{(n-1)n}}}for arbitrary ${\textstyle c\in \mathbb {Q} }${\textstyle c\in \mathbb {Q} }.

• Computer algebra