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 $𝕂$ be a field of characteristic zero. The dispersion $\mathrm{dis}(p,q)$ of two polynomials $p,q\in 𝕂[n]$ is defined as$$\mathrm{dis}(p,q)=\max \{k\in \mathbb{N}:\mathrm{deg}(\gcd (p(n),q(n+k)))\ge 1\}\cup \{-1\},$$where $\mathbb{N}$ denotes the set of non-negative integers. Therefore the dispersion is the maximum $k\in \mathbb{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 ${\mathrm{res}}_n(p(n),q(n+k))\in 𝕂[k]$. Let ${\sum }_{k=0}^r{p}_k(n)y(n+k)=f(n)$ be a recurrence equation of order $r$ with polynomial coefficients $p_k\in 𝕂[n]$, polynomial right-hand side $f\in 𝕂[n]$ and rational sequence solution $y(n)\in 𝕂(n)$. It is possible to write $y(n)=p(n)/q(n)$ for two relatively prime polynomials $p,q\in 𝕂[n]$. Let $D=\mathrm{dis}(p_r(n-r),p_0(n))$ and$$u(n)=\gcd ([p_0(n+D){]}^{\underset{\_}{D+1}},[p_r(n-r){]}^{\underset{\_}{D+1}})$$where $[p(n){]}^{\underset{\_}{k}}=p(n)p(n-1)\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.

Algorithm

Let again ${\sum }_{k=0}^r{p}_k(n)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)\in 𝕂[n]$ and setting $\ell (n)=\mathrm{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)$ 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 ${\sum }_{k=0}^r{p}_k(n)y(n+k)=f(n),p_k,f\in 𝕂[n],p_0,p_r\ne 0$.
    output: The general rational solution $y$ if there are any solutions, otherwise false.

    $D=\mathrm{disp}(p_r(n-r),p_0(n))$
    $u(n)=\gcd ([p_0(n+D){]}^{\underset{\_}{D+1}},[p_r(n-r){]}^{\underset{\_}{D+1}})$
    $\ell (n)=\mathrm{lcm}(u(n),\dots ,u(n+r))$
    Solve ${\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)$
    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)y(n)+(-n-1)y(n+1)=0$$over $\mathbb{Q}$ has a rational solution. It can be computed by considering the dispersion$$D=\mathrm{dis}(p_1(n-1),p_0(n))=\mathrm{disp}(-n,n-1)=1.$$This yields the following universal denominator:$$u(n)=\gcd ([p_0(n+1){]}^{\underset{\_}{2}},[p_r(n-1){]}^{\underset{\_}{2}})=(n-1)n$$and$$\ell (n)=\mathrm{lcm}(u(n),u(n+1))=(n-1)n(n+1).$$Multiplying the original recurrence equation with $\ell (n)$ and substituting $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$ for an arbitrary constant $c\in \mathbb{Q}$. Using $y(n)=z(n)/u(n)$ the general rational solution is$$y(n)=\frac{c}{(n-1)n}$$for arbitrary $c\in \mathbb{Q}$.

References

WikiProject Mathematics on Wikidata