next up previous
Next: The Subspace Theorem Up: Diophantine Equations and Diophantine Previous: Linear equations with unknowns

Linear recurrence sequences

The by far best known example of a linear recurrence sequence is the Fibonacci sequence $ \{ F_n\}_{n=0}^{\infty}$ given by $ F_0=0$, $ F_1=1$ and $ F_n=F_{n-1}+F_{n-2}$ for $ n\geqslant 2$. In general a linear recurrence sequence is a sequence $ U=\{ U_n\}_{n=0}^{\infty}$ of complex numbers given by initial values $ U_0,\ldots,U_{k-1}$ and by a linear recurrence relation

$ U_n=c_1U_{n-1}+c_2U_{n-2}+\cdots +c_kU_{n-k}\quad (n\geqslant k ) $ (3)

where $ c_1,\ldots,c_k$ are fixed complex numbers. One may show that there is only one recurrence relation satisfied by $ U$ for which $ k$ is minimal. Assuming that in relation (3), $ k$ is minimal, we call $ k$ the order, and $ F_U:=X^k-c_1X^{k-1}-\cdots-c_k$ the companion polynomial of $ U$. Write $ F_U=(X-\alpha_1)^{e_1}\cdots (X-\alpha_t)^{e_t}$, where $ \alpha_1,\ldots,\alpha_t$ are the distinct roots of $ f_U$ and where $ e_1,\ldots,e_t$ are positive integers. A basic fact for linear recurrence relations states that there are polynomials $ f_i\in{\mathbb{C}}[X]$ of degree $ <e_i$ $ (i=1,\ldots,t)$ such that

$ U_n=f_1(n)\alpha_1^n+\cdots+f_t(n)\alpha_t^n$   for $ n\in{\mathbb{Z}}_{\geqslant 0}$. (4)

The sequence $ U$ is called simple if all multiplicities $ e_i$ are $ 1$, and non-degenerate if none of the quotients $ \alpha_i/\alpha_j$ ($ 1\leqslant i<j\leqslant t$) is a root of unity (non-degeneracy implies that for any positive integer $ k$, the number of zeros of the companion polynomial of $ U^{(k)}:=\{ U_{nk}\}_{n=0}^{\infty}$ is equal to the number of zeros of the companion polynomial of $ U$).

We are interested in the Diophantine equation $ U_n=0$, that is,

$ f_1(n)\alpha_1^n+\cdots+f_t(n)\alpha_t^n=0$   in $ n\in{\mathbb{Z}}_{\geqslant 0}$. (5)

The classical Skolem-Mahler-Lech theorem (cf. [16]) states that the number of solutions of (5) is finite if $ U$ is non-degenerate. The proof was by means of p-adic analysis. Denote the number of solutions of (5) by $ N_U$. An old conjecture attributed to Ward states that $ N_U$ can be bounded above by a quantity depending on the order of $ U$ only. Throughout the last decades several partial solutions to this problem have been obtained (Beukers, Tijdeman, Schlickewei, Schmidt). We will mention only the most recent result of Schmidt [27], which completely settles Ward's conjecture.
Theorem (Schmidt). Suppose $ U$ is a non-degenerate linear recurrence sequence of order $ k$. Then $ N_U\leqslant \exp\exp\exp (3k\log k)$.

In his proof, Schmidt used the quantitative version of the Subspace Theorem of Schlickewei and the author mentioned above. But apart from that there were some formidable technical difficulties which Schmidt managed to deal with. We mention that for simple linear recurrence sequences, the polynomials $ f_i$ in (4) are all constants. So in that case equation (5) is just a special case of equation (2) and then Theorem 1 implies an upper bound for $ N_U$ depending only on $ k$. The case that not all polynomials $ f_i$ are constants turned out to be much harder.

next up previous
Next: The Subspace Theorem Up: Diophantine Equations and Diophantine Previous: Linear equations with unknowns