The main concept in Abramov's algorithm is a universal denominator. Let be a field of characteristic zero. The dispersion of two polynomials is defined as
where denotes the set of non-negative integers. Therefore the dispersion is the maximum such that the polynomial and the -times shifted polynomial have a common factor. It is if such a does not exist. The dispersion can be computed as the largest non-negative integer root of the resultant.[3][4] Let be a recurrence equation of order with polynomial coefficients , polynomial right-hand side and rational sequence solution . It is possible to write for two relatively prime polynomials . Let and
where denotes the falling factorial of a function. Then divides . So the polynomial can be used as a denominator for all rational solutions and hence it is called a universal denominator.[5]
As the cancel this is a linear recurrence equation with polynomial coefficients which can be solved for an unknown polynomial solution . There are algorithms to find polynomial solutions. The solutions for can then be used again to compute the rational solutions . [2]
algorithm rational_solutions isinput: Linear recurrence equation .
output: The general rational solution if there are any solutions, otherwise false.
Solve for general polynomial solution if solution exists thenreturn general solution elsereturn false
end if
^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. ISSN0041-5553.
^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. ISBN978-0897916387. S2CID2192728.