Occurrence of zero in a linear recursive sequence
type: Item
instance of: scholarly article
title: Occurrence of zero in a linear recursive sequence
zbMATH Open document ID: 0595.10007
DOI: 10.1007/BF01156238
published in: Mathematical Notes
publication date: 1985-01-01T00:00:00Z
review text: Let \(\{u_ m\}^{\infty}_{m=0}\) be a sequence of algebraic numbers satisfying a recurrence relation \(u_{m+k}=a_ 1 u_{m+k-1}+...+a_ k u_ m\) (m\(\geq 0)\) of order k. The main problem considered is that of finding an algorithm to determine all the solutions of the equation \(u_ m=0\). Write \(u_ m=\sum^{s}_{j=1}P_ j(m) w^ m_ j\) as an exponential polynomial in m, with roots w ordered so that \(| w_ 1| \geq | w_ 2| \geq...\geq | w_ s|.\) There is a straightforward reduction to the non-degenerate case in which none of the numbers \(w_ i/w_ j\) is a root of unity. By a theorem of Skolem and Mahler, the equation \(u_ m=0\) now has only finitely many solutions. This result, however, is ineffective. Effective results have only been obtained when the number of roots \(w_ j\) with \(| w_ j| =| w_ 1|\) is small. For example, if there is a single dominant root (that is, \(| w_ 1| >| w_ 2| \geq...\geq | w_ s|)\), then the theory of linear forms in logarithms can be applied directly to show that \(| u_ m| \geq | w_ 1|^ m m^{-c}\) for \(m\geq m_ 0\) with computable numbers c and \(m_ 0\) which gives an effective algorithm for solving \(u_ m=0\) in this case. A nice geometrical idea and an application of linear forms in logarithms leads to a similar lower bound when the sequence has up to three dominant terms. The key observation is that if \(A_ 1,A_ 2,A_ 3\), \(w_ 1,w_ 2,w_ 3\) are algebraic, \(| w_ 1| =| w_ 2| =| w_ 3|\) and no \(w_ i/w_ j\) is a root of unity, then \[ | A_ 1 w^ m_ 1+A_ 2 w^ m_ 2+A_ 3 w^ m_ 3| \geq | w_ 1|^ m m^{-c}\quad for\quad m\geq m_ 0 \] with computable numbers c and \(m_ 0\). It follows that the zeros of a recurrence of order at most three can be determined effectively. Further, the zeros of a recurrence of real algebraic numbers of order at most four can be determined effectively. The same ideas have been found by \textit{M. Mignotte}, \textit{T. N. Shorey} and \textit{R. Tijdeman} [J. Reine Angew. Math. 349, 63-76 (1984; Zbl 0521.10011)].
reviewed by: John H. Loxton
Mathematics Subject Classification ID: 11B37
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11D61
zbMATH DE Number: 3957203
zbMATH Keywords: sequence of algebraic numbers
zbMATH Keywords: recurrence relation
zbMATH Keywords: algorithm
zbMATH Keywords: effective algorithm
zbMATH Keywords: linear forms in logarithms
zbMATH Keywords: lower bound
zbMATH Keywords: zeros
author: Nikolai K. Vereshchagin
MaRDI profile type: Publication
cites work: Q4155837
cites work: Deux propriétés décidables des suites récurrentes linéaires
cites work: Q4771027
cites work: An Exact Method for Finding the Roots of a Complex Polynomial
cites work: Q3674747
cites work: A note on linear recursive sequences
cites work: Q5758707
cites work: Q3671245
full work available at URL: https://doi.org/10.1007/bf01156238
OpenAlex ID: W2035848785
description: scientific article; zbMATH DE number 3957203