You are here: Home Publications Univariate polynomial solutions of algebraic difference equations

Univariate polynomial solutions of algebraic difference equations

Shkaravska, O., & Van Eekelen, M. (2014). Univariate polynomial solutions of algebraic difference equations. Journal of Symbolic Computation, 60, 15-28. doi:10.1016/j.jsc.2013.10.010.
Contrary to linear difference equations, there is no general theory of difference equations of the form G(P(x−τ1),…,P(x−τs))+G0(x)=0, with τi∈K, G(x1,…,xs)∈K[x1,…,xs] of total degree D⩾2 and G0(x)∈K[x], where K is a field of characteristic zero. This article is concerned with the following problem: given τi, G and G0, find an upper bound on the degree d of a polynomial solution P(x), if it exists. In the presented approach the problem is reduced to constructing a univariate polynomial for which d is a root. The authors formulate a sufficient condition under which such a polynomial exists. Using this condition, they give an effective bound on d, for instance, for all difference equations of the form G(P(x−a),P(x−a−1),P(x−a−2))+G0(x)=0 with quadratic G, and all difference equations of the form G(P(x),P(x−τ))+G0(x)=0 with G having an arbitrary degree.
About MPI

This is the MPI

The Max Planck Institute for Psycholinguistics is an institute of the German Max Planck Society. Our mission is to undertake basic research into the psychological,social and biological foundations of language. The goal is to understand how our minds and brains process language, how language interacts with other aspects of mind, and how we can learn languages of quite different types.

The institute is situated on the campus of the Radboud University. We participate in the Donders Institute for Brain, Cognition and Behaviour, and have particularly close ties to that institute's Centre for Cognitive Neuroimaging. We also participate in the Centre for Language Studies. A joint graduate school, the IMPRS in Language Sciences, links the Donders Institute, the CLS and the MPI.


Street address
Wundtlaan 1
6525 XD Nijmegen
The Netherlands

Mailing address
P.O. Box 310
6500 AH Nijmegen
The Netherlands

Phone:   +31-24-3521911
Fax:        +31-24-3521213

Public Outreach Officer
Charlotte Horn