Diophantine representations of linear recurrences. I
type: Item
instance of: scholarly article
title: Diophantine representations of linear recurrences. I
zbMATH Open document ID: 0938.11004
DOI: 10.1007/BF02355857
published in: Journal of Mathematical Sciences (New York)
publication date: 1998-10-12T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 11B37
Mathematics Subject Classification ID: 11B39
zbMATH DE Number: 1107900
zbMATH Keywords: diophantine set
zbMATH Keywords: diophantine representation
zbMATH Keywords: recurrence
zbMATH Keywords: Fibonacci number
author: Maxim Vsemirnov
MaRDI profile type: Publication
cites work: An explicit diophantine definition of the exponential function
cites work: Hilbert's Tenth Problem is Unsolvable
cites work: Q3333105
cites work: Q3897100
cites work: Q5613949
cites work: Q5643974
cites work: Q4133963
cites work: Q3992465
cites work: Reduction of an arbitrary diophantine equation to one in 13 unknowns
full work available at URL: https://doi.org/10.1007/bf02355857
OpenAlex ID: W2081122869
Recommended article: Diophantine representations of linear recurrent sequences. II
Recommended article: Factorizations and representations of binary polynomial recurrences by matrix methods
Recommended article: Solving equations in sequences
Recommended article: Q3403507
Recommended article: Q5769923
Recommended article: Q5689940
Recommended article: Q4441313
Recommended article: Q4021501
Recommended article: Q3027082
Recommended article: Linear recursive sequences and powers of matrices
description: scientific article; zbMATH DE number 1107900