Abramov's algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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. The main concept in Abramov's algorithm is a universal denominator. Let \mathbb{K} be a field of characteristic zero. The dispersion \operatorname{dis} (p,q) of two polynomials p, q \in \mathbb{K}[n] is defined as \operatorname{dis} (p,q) =\max \{ k \in \N \, : \, \deg (\gcd (p(n), q(n+k) )) \geq 1 \} \cup \{ -1 \}, 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{res}_n (p(n), q(n+k) ) \in \mathbb{K}[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 \mathbb{K} [n] , polynomial right-hand side f \in \mathbb{K}[n] and rational sequence solution y (n) \in \mathbb{K}(n) . It is possible to write y (n) = p(n)/q(n) for two relatively prime polynomials p, q \in \mathbb{K}[n] . Let 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 [p(n)]^{\underline{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. 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 \mathbb{K} [n] and setting \ell(n) = \operatorname{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 \mathbb{K}[n], p_0, p_r \neq 0 . output: The general rational solution y if there are any solutions, otherwise false. D = \operatorname{disp} (p_r(n-r), p_0 (n) ) u(n) = \gcd ([p_0 (n+D)]^{\underline{D+1}}, [p_r (n-r)]^{\underline{D+1}}) \ell(n) = \operatorname{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 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{dis} (p_1 (n-1), p_0 (n) ) = \operatorname{disp} (-n,n-1) = 1. This yields the following universal denominator: u(n) = \gcd ([p_0 (n+1)]^{\underline{2}}, [p_r (n-1)]^{\underline{2}}) = (n-1)n and \ell(n) = \operatorname{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 \Q . Using y(n) = z(n) / u(n) the general rational solution is y(n) = \frac{c}{(n-1)n} for arbitrary c \in \Q .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1250450504 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001250450504 · captured 1728561451.0 · version history

Cite this page as: encyclopegia.org, “Abramov's algorithm”, snapshot enwiki-001250450504. https://encyclopegia.org/a/abramov-s-algorithm

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.