Leírás
Online Number Theory Seminar
Abstract: A linear recurrence of order $r$ over a number field $K$ is a map $U: \mathbb{Z} \rightarrow K$ satisfying a relation of the form
$$
U(n + r) = a_{r-1}U(n + r - 1)+ \ldots + a_0U(n)\quad (n\in\mathbb{Z}),
$$
where $a_0,\ldots,a_{r-1}\in K$ and $a_0\neq 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 Skolem tool
that I will demonstrate.
A joint work with Florian Luca, Joris Nieuwveld, Jo\"el Ouaknine, David Purser and James Worrell.
For access please contact the organizers (ntrg[at]science.unideb.hu).