Abramov's algorithm

In mathematics, particularly in computer algebra, Abramov's algorithm computes all Rational function, rational solutions of a P-recursive equation, 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 $\mathbb$ be a Field (mathematics), field of Characteristic (algebra), characteristic zero. The ''dispersion'' $\operatorname (p,q)$ of two polynomials $p, q \in \mathbb[n]$ is defined as$\operatorname (p,q) =\max \ \cup \,$where $\N$ denotes the set of non-negative integers. Therefore the dispersion is the maximum $k \in \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 $\operatorname_n (p(n), q(n+k) ) \in \mathbb[k]$. Let $\sum_^r p_k(n) \, y (n+k) = f(n)$ be a P-recursive equation, recurrence equation of order $r$ with polynomial coefficients $p_k \in \mathbb [n]$, polynomial right-hand side $f \in \mathbb[n]$ and rational sequence solution $y (n) \in \mathbb(n)$. It is possible to write $y (n) = p(n)/q(n)$ for two relatively prime polynomials $p, q \in \mathbb[n]$. Let $D=\operatorname (p_r(n-r), p_0 (n) )$ and$u(n) = \gcd ([p_0 (n+D)]^, [p_r (n-r)]^)$where $[p(n)]^=p(n)p(n-1)\cdots p(n-k+1)$ denotes the Falling and rising factorials, 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_^r p_k(n) \, y (n+k) = f(n)$ be a P-recursive equation, 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 \mathbb [n]$ and setting $\ell(n) = \operatorname(u(n), \dots, u(n+r))$ the recurrence equation is equivalent to$\sum_^r p_k (n) \frac \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 Polynomial solutions of P-recursive equations, 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_^r p_k(n) \, y (n+k) = f(n), p_k, f \in \mathbb[n], p_0, p_r \neq 0$.
output: The general rational solution $y$ if there are any solutions, otherwise false.

$D = \operatorname (p_r(n-r), p_0 (n) )$
$u(n) = \gcd ([p_0 (n+D)]^, [p_r (n-r)]^)$
$\ell(n) = \operatorname(u(n), \dots, u(n+r))$
Solve $\sum_^r p_k (n) \frac \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 $\Q$ has a rational solution. It can be computed by considering the dispersion$D = \operatorname (p_1 (n-1), p_0 (n) ) = \operatorname (-n,n-1) = 1.$This yields the following universal denominator:$u(n) = \gcd ([p_0 (n+1)]^, [p_r (n-1)]^) = (n-1)n$and$\ell(n) = \operatorname (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 \Q$. Using $y(n) = z(n) / u(n)$ the general rational solution is$y(n) = \frac$for arbitrary $c \in \Q$.

References

{, class="wikitable" style="width: 100%"
, - align="center"
, :d:Wikidata:WikiProject Mathematics, WikiProject Mathematics on Wikidata

Computer algebra