Diophantine representations of linear recurrences. I (Q1376907)

The work is the first of a series of papers aiming at solving the open problem 2.3 from [\textit{Yu. V. Matijasevich}, Hilbert's tenth problem (in Russian), Moscow, Nauka (1993; Zbl 0790.03009)]. Let the sequence \(a_n\) be defined by the recurrence \[ a_{n+k}=b_{k-1}a_{n+k-1}+\ldots{+}b_0{a_n} \] where \(b_i\) are integers, \(b_0=\pm{1},\) and where the initial conditions are \[ a_0=1, a_{-1}=a_{-2}=\ldots=a_{-k+1}=0. \] Let \(f(\lambda)={\lambda}^k-b_{k-1}{\lambda}_{k-1}-\ldots{-}b_1\lambda- b_0.\) It is possible to define \(a_n\) for all negative integers \(n\) by \[ a_n=(a_{n+k}-b_{k-1}a_{n+k-1}-\ldots{-}b_1a_{n+1})/b_0. \] Consider the matrices \[ B=\left[\begin{matrix} 0&0&\ldots&0&b_0\\ 1&0&\ldots&0&b_1\\ 0&1&\ldots&0&b_2\\ \ldots&\ldots&\ldots&\ldots&\ldots\\ 0&0&\ldots&1&b_{k-1}\end{matrix}\right], \] \[ A(x_0,\ldots,x_{k-1})=\sum_{l=0}^{k-1}x_i(B^l-\sum_{j=1}^l b_{k-j}B^{l-j}), \] and define the polynomial \(F_B=\det{A}(x_0,\ldots,x_{k-1}).\) If the equality \[ F_B(x_0,\ldots,x_{k-1})=\pm{1} \] for integer \(x_0,\ldots,x_{k-1}\) implies for some integer \(n\) either \[ x_0=a_n,{\ldots},x_{k-1}=a_{n-k+1} \] or \[ x_0=-a_n,{\ldots},x_{k-1}=-a_{n-k+1}, \] the equality (1) is called characteristic for the sequence \(a_n.\) Necessary conditions are found for the equality (1) to be characteristic for the sequence \(a_n.\) In case \(k=3\) necessary and sufficient conditions are proved.