×Time: 14.15 on 23 Nov, 2023
Place: SR 00.003, Spiegelgasse 1
Yuri Bilu (Université de Bordeaux)
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 $$U(n+r)=a_{r-1}U(n+r-1)+ \cdots+ a_0U(n) \qquad (n\in \mathbb{Z}), $$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 complexity bound (even conditional to some conjectures), but the algorithm performs well in practice, and was implemented in the Skolem tool https://skolem.mpi-sws.org/that I will demonstrate.A joint work with Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser andJames Worrell.