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

Algorithm

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

algorithm rational_solutions is
    input: Linear recurrence equation [math]\displaystyle{ \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 }[/math].
    output: The general rational solution [math]\displaystyle{ y }[/math] if there are any solutions, otherwise false.

    [math]\displaystyle{ D = \operatorname{disp} (p_r(n-r), p_0 (n) ) }[/math]
    [math]\displaystyle{ u(n) = \gcd ([p_0 (n+D)]^{\underline{D+1}}, [p_r (n-r)]^{\underline{D+1}}) }[/math]
    [math]\displaystyle{ \ell(n) = \operatorname{lcm}(u(n), \dots, u(n+r)) }[/math]
    Solve [math]\displaystyle{ \sum_{k=0}^r p_k (n) \frac{z(n+k)}{u(n+k)} \ell(n) = f(n) \ell(n) }[/math] for general polynomial solution [math]\displaystyle{ z(n) }[/math]
    if solution [math]\displaystyle{ z(n) }[/math] exists then
        return general solution [math]\displaystyle{ y (n) = z(n)/u(n) }[/math]
    else
        return false
    end if

Example

The homogeneous recurrence equation of order [math]\displaystyle{ 1 }[/math][math]\displaystyle{ (n-1) \, y(n) + (-n-1) \, y(n+1) = 0 }[/math]over [math]\displaystyle{ \Q }[/math] has a rational solution. It can be computed by considering the dispersion[math]\displaystyle{ D = \operatorname{dis} (p_1 (n-1), p_0 (n) ) = \operatorname{disp} (-n,n-1) = 1. }[/math]This yields the following universal denominator:[math]\displaystyle{ u(n) = \gcd ([p_0 (n+1)]^{\underline{2}}, [p_r (n-1)]^{\underline{2}}) = (n-1)n }[/math]and[math]\displaystyle{ \ell(n) = \operatorname{lcm} (u(n), u(n+1) ) = (n-1)n(n+1). }[/math]Multiplying the original recurrence equation with [math]\displaystyle{ \ell(n) }[/math] and substituting [math]\displaystyle{ y(n) = z(n)/u(n) }[/math] leads to[math]\displaystyle{ (n-1)(n+1)\, z(n) + (-n-1) (n-1) \, z(n+1) = 0. }[/math]This equation has the polynomial solution [math]\displaystyle{ z(n) = c }[/math] for an arbitrary constant [math]\displaystyle{ c \in \Q }[/math]. Using [math]\displaystyle{ y(n) = z(n) / u(n) }[/math] the general rational solution is[math]\displaystyle{ y(n) = \frac{c}{(n-1)n} }[/math]for arbitrary [math]\displaystyle{ c \in \Q }[/math].

References

WikiProject Mathematics on Wikidata