Abramov's algorithm

In mathematics, particularly in computer algebra, Abramov's algorithm computes all rational solutions of a linear recurrence equation with polynomial coefficients.

Uses your system voice; voice and rate in settings.

≈ 5 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

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.[1][2]

Universal denominator

edit edit source

The main concept in Abramov's algorithm is a universal denominator. Let 𝕂 be a field of characteristic zero. The dispersion dis⁡(p,q) of two polynomials p,q∈𝕂[n] is defined asdis⁡(p,q)=max⁡{k∈ℕ:deg⁡(gcd⁡(p(n),q(n+k)))≥1}∪{−1},where ℕ denotes the set of non-negative integers. Therefore the dispersion is the maximum k∈ℕ 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 resn(p(n),q(n+k))∈𝕂[k].[3][4] Let ∑k=0rpk(n)y(n+k)=f(n) be a recurrence equation of order r with polynomial coefficients pk∈𝕂[n], polynomial right-hand side f∈𝕂[n] and rational sequence solution y(n)∈𝕂(n). It is possible to write y(n)=p(n)/q(n) for two relatively prime polynomials p,q∈𝕂[n]. Let D=dis⁡(pr(n−r),p0(n)) andu(n)=gcd⁡([p0(n+D)]D+1_,[pr(n−r)]D+1_)where [p(n)]k_=p(n)p(n−1)⋯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.[5]

Algorithm

edit edit source

Let again ∑k=0rpk(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)∈𝕂[n] and setting ℓ(n)=lcm⁡(u(n),…,u(n+r)) the recurrence equation is equivalent to∑k=0rpk(n)z(n+k)u(n+k)ℓ(n)=f(n)ℓ(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).[2]

algorithm rational_solutions is input: Linear recurrence equation ∑k=0rpk(n)y(n+k)=f(n),pk,f∈𝕂[n],p0,pr≠0. output: The general rational solution y if there are any solutions, otherwise false. D=disp⁡(pr(n−r),p0(n)) u(n)=gcd⁡([p0(n+D)]D+1_,[pr(n−r)]D+1_) ℓ(n)=lcm⁡(u(n),…,u(n+r)) Solve ∑k=0rpk(n)z(n+k)u(n+k)ℓ(n)=f(n)ℓ(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

edit edit source

The homogeneous recurrence equation of order 1(n−1)y(n)+(−n−1)y(n+1)=0over ℚ has a rational solution. It can be computed by considering the dispersionD=dis⁡(p1(n−1),p0(n))=disp⁡(−n,n−1)=1.This yields the following universal denominator:u(n)=gcd⁡([p0(n+1)]2_,[pr(n−1)]2_)=(n−1)nandℓ(n)=lcm⁡(u(n),u(n+1))=(n−1)n(n+1).Multiplying the original recurrence equation with ℓ(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∈ℚ. Using y(n)=z(n)/u(n) the general rational solution isy(n)=c(n−1)nfor arbitrary c∈ℚ.

References

edit edit source
  1. ^ Abramov, Sergei A. (1989). "Rational solutions of linear differential and difference equations with polynomial coefficients". USSR Computational Mathematics and Mathematical Physics. 29 (6): 7–12. doi:10.1016/s0041-5553(89)80002-3. ISSN 0041-5553. Wikipedia revision 1250450504, retrieved 2026-11-18
  2. ^ a b Abramov, Sergei A. (1995). "Rational solutions of linear difference and q -difference equations with polynomial coefficients". Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95. pp. 285–289. doi:10.1145/220346.220383. ISBN 978-0897916998. S2CID 15424889. Wikipedia revision 1250450504, retrieved 2026-11-18
  3. ^ Man, Yiu-Kwong; Wright, Francis J. (1994). "Fast polynomial dispersion computation and its application to indefinite summation". Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94. pp. 175–180. doi:10.1145/190347.190413. ISBN 978-0897916387. S2CID 2192728. Wikipedia revision 1250450504, retrieved 2026-11-18
  4. ^ Gerhard, Jürgen (2005). Modular Algorithms in Symbolic Summation and Symbolic Integration. Lecture Notes in Computer Science. Vol. 3218. doi:10.1007/b104035. ISBN 978-3-540-24061-7. ISSN 0302-9743. Wikipedia revision 1250450504, retrieved 2026-11-18
  5. ^ Chen, William Y. C.; Paule, Peter; Saad, Husam L. (2007). "Converging to Gosper's Algorithm". arXiv:0711.3386 [math.CA]. Wikipedia revision 1250450504, retrieved 2026-11-18
WikiProject Mathematics on Wikidata

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

Words in each sectionUniversal denominatorUniversal denominatorUniversal denominator: 247 words247AlgorithmAlgorithmAlgorithm: 234 words234ExampleExampleExample: 143 words143
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001250450504 · captured 2024-10-10 · ledger · version history

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