Diophantine representations of linear recurrent sequences. II (Q1977917)

The work belongs to the series of papers (see Zbl 0938.11004 for Part I) aiming at solving the open problem 2.3 from [\textit{Yu. V. Matiyasevich}, Hilbert's tenth problem (Russian). Moscow, Nauka (1993; Zbl 0790.03009)]. Let a sequence \(a_n\) be defined by the recurrent relation of order \(k\) \[ a_{n+k}=b_{k-1}a_{n+k-1}+\ldots{+}b_0{a_n} \] where \(b_i\) are integers, \(b_0=\pm{1},\) with the initial conditions \[ 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,\) where \(f\) is irreducible over \({\mathbb Q.}\) 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}). \] Let \(F_B=\det{A}(x_0,\ldots,x_{k-1}).\) If \( 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.\) Let \(\lambda\) be a root of the polynomial \(f.\) Then the field \({\mathbb Q}(\lambda)\) is an extension of \({\mathbb Q}\) of degree \(k.\) Let \((\mathbb{Z} [\lambda])^*\) denote the multiplicative group of order \((\mathbb{Z} [\lambda]).\) It is shown that relation (1) is characteristic for the sequence \((a_n)\) if and only if \((\mathbb{Z} [\lambda])^*=\{\pm {\lambda}^n:n\in \mathbb{Z} .\}\) If relation (1) is characteristic, the one of the following conditions holds: a) \(k=2\), b) \(k=3,\) and the polynomial \(f\) has exactly one real root, c) \(k=4\), and \(f\) has no real roots. In conclusion, the second- and the third order sequences are investigated.