Skolem meets Schanuel

A linear recurrence of order~$r$ over a number field~$K$ is a map ${U:\mathbb{Z}\to K}$ satisfying a relation of the form
$<br />U(n+r)=a_{r-1}U(n+r-1)+ \cdots+ a_0U(n) \qquad (n\in \mathbb{Z}), <br />$
where ${a_0, \ldots, a_{r-1}\in K}$ and ${a_0\ne 0}$. A linear recurrence is called simple if the characteristic polynomial ${X^r-a_{r-1}X^{r-1}-\ldots- a_0}$ has only simple roots, and non-degenerate if ${\lambda/\lambda'}$ is not a root of unity for any two distinct roots $\lambda, \lambda'$ of the characteristic polynomial. The classical Theorem of Skolem-Mahler-Lech asserts that a non-degenerate linear recurrence may have at most finitely many zeros. However, all known proofs of this theorem are non-effective and do not produce any tool to determine the zeros.


In this talk I will describe a simple algorithm that, when terminates, produces the rigorously certified list of zeros of a given simple linear recurrence. This algorithm always terminates subject to two celebrated conjectures: the $p$-adic Schanuel Conjecture, and the Exponential Local-Global Principle. We do not give any running time bound (even conditional to some conjectures), but the algorithm performs well in practice, and was implemented in the \textit{Skolem tool}
$<br />\text{https://skolem.mpi-sws.org/}<br />$
that I will demonstrate. This is a joint work with Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser and James Worrell.