Occurrence of zero in a linear recursive sequence (Q1077447)

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)].