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 $\mathbb$ be a field of characteristic zero. The ''dispersion'' $\operatorname (p,q)$ of two polynomials p, q \in \mathbb /math> 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 /math>. Let $\sum_^r p_k(n) \, y (n+k) = f(n)$ be a recurrence equation of order $r$ with polynomial coefficients p_k \in \mathbb /math>, polynomial right-hand side f \in \mathbb /math> 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 /math>. Let $D=\operatorname (p_r(n-r), p_0 (n) )$ andu(n) = \gcd ( _0 (n+D), _r (n-r))where $$(n)=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_^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 \mathbb /math> 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 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 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 ( _0 (n+D), _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 ( _0 (n+1), _r (n-1)) = (n-1)nand$\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"
, WikiProject Mathematics on Wikidata

Computer algebra