Composite polynomials in linear recurrence sequences

Abstract

Let $(G_n(x){)}_{n=0}^{\infty }$ be a $d$-th order linear recurrence sequence having polynomial characteristic roots, one of which has degree strictly greater than the others. Moreover, let $m\ge 2$ be a given integer. We ask for $n\in \mathbb{N}$ such that the equation $G_n(x)=g\circ h$ is satisfied for a polynomial $g\in \mathbb{C}[x]$ with deg$g=m$ and some polynomial $h\in \mathbb{C}[x]$ with deg$h>1$. We prove that for all but finitely many $n$ these decompositions can be described in "finite terms" coming from a generic decomposition parameterized by an algebraic variety. All data in this description will be shown to be effectively computable.

21 pages