Polynomial solutions of algebraic difference equations and homogeneous symmetric polynomials (Q2211187)

Whereas there is a general solution theory for linear difference equations, algebraic difference equations lack such a general theory. In this article the authors consider a special class of difference equations. They derive degree bounds for difference equations of this special class. They consider both difference equations with constant coefficients and also with polynomial coefficients. Finally they show that if the first-order theory of the ground field is decidable, then there exists an algorithm for deciding whether a difference equation of the form considered in this article has a polynomial solution of degree up to a given \(d\). Reviewer's remark: When reading the paper, I had a problem understanding equation (1).