The zero multiplicity of linear recurrence sequences

DOI10.1007/BF02392575MaRDI QIDQ1588913zbMATH OpenOpenAlexFDO

Authors Wolfgang M. Schmidt

Publication date 6 December 2000

Published in Acta Mathematica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02392575

zbMATH Keywords

exponential polynomial equations linear recurrence sequences

Mathematics Subject Classification ID

Recurrences (11B37) Exponential Diophantine equations (11D61)

Review text

A sequence of complex numbers \(U=\{ u_n\}_{n\in{\mathbb{Z}}}\) is said to be a linear recurrence sequence if it satisfies a linear recurrence relation (1) \(u_n=c_1u_{n-1}+\cdots +c_tu_{n-t}\) \((n\in{\mathbb{Z}})\) where \(c_1,\ldots,c_t\) are fixed complex numbers. Let \(t\) be the smallest integer for which \(U\) satisfies a relation of type (1). Then we call \(t\) the order, and \(P_U(z)=z^t-c_1z^{t-1}-\cdots -c_t\) the companion polynomial of \(U\). Write \(P_U(z)=\prod_{i=1}^k (z-\alpha_i)^{a_i}\) where \(\alpha_1,\ldots,\alpha_k\) are the distinct roots of \(P_U\) and \(a_1,\ldots,a_k\) the multiplicities of these roots. Then we can express the terms \(u_n\) of \(U\) as \(u_n=\sum_{i=1}^k f_i(n)\alpha_i^n\) where each \(f_i\) is a polynomial of degree \(a_i-1\). The sequence \(U\) is called non-degenerate if none of the quotients \(\alpha_i/\alpha_j\) \((1\leq i<j\leq k)\) is a root of unity, and it is called simple if \(P_U\) is simple, i.e., if \(a_i=1\) for \(i=1,\ldots,k\). Denote by \(N(U)\) the zero multiplicity of \(U\), that is the number of \(n\in{\mathbb{Z}}\) with (2) \(u_n=0\). Equivalently, \(N(U)\) is the number of solutions of the exponential polynomial equation (3) \(\sum_{i=1}^k f_i(n)\alpha_i^n=0\). Henceforth we assume that \(U\) is non-degenerate. A classical result of Skolem-Mahler-Lech implies that in that case \(N(U)\) is finite. A long outstanding conjecture states that \(N(U)\) is bounded above by a constant depending only on the order \(t\) of \(U\). This conjecture was proved by Schlickewei in the special case that the sequence \(U\) has its terms in the field of rational numbers. More generally, \textit{H. P. Schlickewei} proved that if \(U\) has its terms in an algebraic number field \(K\) of degree \(D\) then \(N(U)\leq c(t,D)\) where \(c(t,D)\) is some effectively computable number depending only on \(t\) and \(D\) [Acta Math. 170, 151-180 (1993; Zbl 0789.11012)]. \textit{F. Beukers} and \textit{H. P. Schlickewei} [Acta Arith. 78, 189-199 (1996; Zbl 0880.11034)] proved that \(N(U)\leq 61\) if \(t=3\) and \(U\) is simple. Further, \textit{J.-H. Evertse, H. P. Schlickewei} and \textit{W. M. Schmidt} [Ann. Math. (2) (to appear)] proved that \(N(U)\leq \exp ((6t)^{3t})\) for any \(t\geq 3\) but again only for simple recurrence sequences \(U\). The main tool in the proof of this result was a new version of the quantitative Subspace Theorem, due to \textit{J.-H. Evertse} and \textit{H. P. Schlickewei} [J. Reine Angew. Math. (to appear)]. In the present paper, the author proves the conjecture in full generality. More precisely, he shows that for any non-degenerate linear recurrence sequence \(U\) of order \(t\geq 3\), \(N(U)\leq \exp\exp\exp (3t\log t)\). To make the step from simple to non-simple recurrence sequences involved some difficult problems, and that the author has been able to overcome these is indeed a major achievement. We give some features of the author's proof. By invoking a suitable specialisation argument, one may reduce the general case that \(U\) has complex terms to the special case that all terms of \(U\), as well as the coefficients of the polynomials \(f_i\) and the numbers \(\alpha_i\) from (3), belong to some algebraic number field \(K\). Then we may rewrite equation (3) as (4) \(c_1x_1+\cdots +c_sx_s=0\) where \(s\leq t\), \(c_1,\ldots,c_s\) are fixed non-zero numbers from \(K\) and where \(x_l=n^{i_l}\alpha_{j_l}^n\) with \(j_l\in\{ 1,\ldots,k\}\), and \(0\leq i_l<a_{j_l}\) for \(l=1,\ldots,s\). Using the quantitative version of the Subspace Theorem of Schlickewei and the reviewer mentioned above one may show that the solution vector \({\mathbf x}=(x_1,\ldots,x_s)\) of (4) is contained in some finite union \(V_1\cup\cdots\cup V_u\) of proper linear subspaces of \(K^s\) and give an explicit upper bound for \(u\). By translating this back to the equation \(u_n=0\) one may show that each solution \(n\) satisfies one among \(u\) equations \(v_{i,n}=0\) where \(V_i=\{ v_{i,n}\}_{n\in{\mathbb{Z}}}\) is a linear recurrence sequence of order \(<t\) for \(i=1,\ldots,u\). If the sequence \(U\) is simple, i.e., if \(i_l=0\) for \(l=1,\ldots,s\) then the upper bound for \(u\) is a constant depending only on \(t\) and then one may deduce by induction an explicit upper bound for the number of solutions to \(u_n=0\) depending only on \(t\). Assume that \(U\) is not simple. Denote by \(h(\alpha)\) the absolute logarithmic height of an algebraic number. Then one may deduce an explicit upper bound for \(u\) which is an increasing function of \(t\) and \(h^{-1}\) where \(h:=\max_{1\leq i<j\leq k} h(\alpha_i/\alpha_j)\). (In fact, the upper bound for \(u\) depends on how small the height of the vector of monomial terms \((n^{i_1},\ldots,n^{i_s})\) is compared with the height of \({\mathbf x}=(n^{i_1}\alpha_{j_1}^n,\ldots,n^{i_s}\alpha_{j_s}^n)\) and to make this precise one needs the term \(h^{-1}\).) A priori, \(h\) is bounded from below by a function of \(D=[K:{\mathbb{Q}}]\). This would imply an upper bound for \(N(U)\) depending on \(t\) and \(D\) which was already achieved by Schlickewei. However, by means of a very ingenious argument, which uses the result for simple recurrence sequences of Evertse, Schlickewei and Schmidt mentioned above, as well as some combinatorics and analytic number theory, the author proves the following: The set of solutions \(n\in{\mathbb{Z}}\) of \(u_n=0\) fall into at most \(H(t)\) classes, where \(H(t)\) depends only on \(t\). For each class \(C\) there is a positive integer \(m=m_C\) such that \(n_1\equiv n_2\pmod m\) for all \(n_1,n_2\in C\) and moreover \(\max_{1\leq i<j\leq k} h(\alpha_i^m/\alpha_j^m)\geq h(t)\) where \(h(t)>1\) depends only on \(t\). Now consider all solutions of \(u_n=0\) lying in a fixed class \(C\). The integers \(n\in C\) can be expressed as \(a+mp\) with \(p\in \mathbb{Z}\) and \(a\) fixed, and we have that \(p\) is a solution to \(u_{a+mp}=0\). Further, the companion polynomial of \(U_C=\{ u_{a+mp}\}_{p\in{\mathbb{Z}}}\) has roots \(\alpha_i^m\) \((i=1,\ldots,k)\). Hence the arguments above give that each solution \(p\) to \(u_{a+mp}=0\) is in fact a solution to one among \(u_C\) equations \(v_{i,C,p}=0\) where \(V_{i,C}=\{ v_{i,C,p}\}_{p\in{\mathbb{Z}}}\) is a linear recurrence sequence of order \(<t\) and where \(u_C\) depends only on \(t\) and \(h(t)^{-1}\), whence only on \(t\). So altogether, each \(n\) with \(u_n=0\) is a zero of one of at most \(u_C\cdot H(t)=: u(t)\) linear recurrence sequences of order \(<t\). Now it follows easily by induction that \(N(U)\) is bounded from above by a quantity depending only on \(t\). Reviewer's remark: Meanwhile the author has proved the following improvement and generalization of the result mentioned above [Publ. Math. 56, 609-630 (2000; Zbl 0963.11007)]: let \(U= \{u_n\}_{n\in\mathbb{Z}}\) be a not necessarily non-degenerate linear recurrence sequence of order \(t\). Let \(Z(U)\) be the set of \(n\in \mathbb{Z}\) with \(u_n= 0\). Then \(Z(U)= S\cup A_1\cup\dots\cup A_{q_2}\) where \(S\) is a finite set of cardinality \(q_1\) and where \(A_1,\dots, A_{q_2}\) are arithmetic progressions such that \(q_1+ q_2\leq \exp\exp\exp (20t)\). In the case that \(U\) is non-degenerate one may take \(q_2=0\).

Recommendations

Cites work

Cited in

(64)

This page was built for publication: The zero multiplicity of linear recurrence sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1588913)