Olha Shkaravska, and Marko van Eekelen. Polynomial solutions of algebraic difference equations and homogeneous symmetric polynomials. Technical report: ICIS-R18001, October, Radboud University Nijmegen, 2018.

This article addresses the problem of computing an upper bound of the degree d of a polynomial solution P of an algebraic difference equation of the form $G(x)(P(x-tau1),..., P(x-taus))+G0(x)=0$ when such P in K[x] exists and where a field K is of characteristic zero, G in K[x][x_1,\ldots,x_s] and G0 in K[x]. It is known that, contrary to linear difference equations, there is no general theory for algebraic ones where G has total degree greater than 1.
It will be shown that if G is a quadratic polynomial with constant coefficients then one can construct a countable family of polynomials f{l}(u0) with the following property: if a nonnegative integer number l0 is the minimal index such that f{l0}(u0) is a non-zero polynomial, then either the degree d is among its roots, or d <=l0, or d < deg(G0). Moreover, the existence of such l0 is guaranteed if K is the field of real numbers, and an explicit upper bound for this case will be given. It will be shown that these results do not hold for polynomials G of degree three or greater due to a module-rank reason.
A sufficient condition for the existence of an indicial polynomial for difference equations with G of arbitrary total degree and with variate coefficients will be proven. Moreover we will give an example of the connection between Diophantine equations and algebraic difference equations with variate coefficients.