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 key concept in Abramov's algorithm is a universal denominator. Let ${\textstyle \mathbb {K} }$ be a field of characteristic zero. The dispersion ${\textstyle \operatorname {dis} (p,q)}$ of two polynomials ${\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 ${\textstyle \mathbb {N} }$ denotes the set of non-negative integers. Therefore the dispersion is the maximum ${\textstyle k\in \mathbb {N} }$ such that the polynomial ${\textstyle p}$ and the ${\textstyle k}$-times shifted polynomial $q$ have a common factor. It is ${\textstyle -1}$ if such a ${\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]}$. Let ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ be a recurrence equation of order ${\textstyle r}$ with polynomial coefficients $p_{k}\in \mathbb {K} [n]$, polynomial right-hand side ${\textstyle f\in \mathbb {K} [n]}$ and rational sequence solution ${\textstyle y(n)\in \mathbb {K} (n)}$. It is possible to write ${\textstyle y(n)=p(n)/q(n)}$ for two relatively prime polynomials ${\textstyle p,q\in \mathbb {K} [n]}$. Let ${\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 ${\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)}$ divides ${\textstyle u(n)}$. So the polynomial ${\textstyle u(n)}$ can be used as a denominator for all rational solutions ${\textstyle y(n)}$ and hence it is called a universal denominator.

References

WikiProject Mathematics on Wikidata