Rational Solutions of Linear Difference Equations

This paper contains a new bound for the denominator of rational solutions of (systems of) difference equations. The bound is sharper than other known bounds, in particular if all solutions are rational then the bound is exact.

In the paper the bound is given by the valuation (i.e. the pole and root orders) in a certain matrix. I have implemented the bound for the case of a scalar equation, and I use some tricks to get these pole orders quickly without doing costly matrix products. This is used in my implementation for hypergeometric solutions. An illustration how to do such computations for a scalar equation is given in Example 2 in the paper Set of Poles of Solutions of Linear Difference Equations with Polynomial Coefficients, other examples and additional explanations on this are found in the papers listed here.

Download this paper.