Valuations of rational solutions of linear difference equations at irreducible polynomials

We discuss two algorithms which, given a linear difference equation with rational function coefficients over a field k of characteristic 0, construct a finite set M of polynomials, irreducible in k[x], such that if the given equation has a solution F(x)∈k(x) and for an irreducible p(x), then p(x)∈M. After this for each p(x)∈M the algorithms compute a lower bound for , which is valid for any rational function solution F(x) of the initial equation. The algorithms are applicable to scalar linear equations of arbitrary orders as well as to linear systems of first-order equations.The algorithms are based on a combination of renewed approaches used in earlier algorithms for finding a universal denominator (Abramov and Barkatou (1998) [6], ), and on a denominator bound (van Hoeij (1998) [12]). A complexity analysis of the two proposed algorithms is presented.