Oberseminar Zahlentheorie
Florian Luca
Title: Recent progress on the Skolem problem
Abstract:
The celebrated Skolem-Mahler-Lech Theorem states that the set of zeros of a linear recurrence sequence is the union of a finite set and finitely many arithmetic progressions. The corresponding computational question, the Skolem Problem, asks to determine whether a given linear recurrence sequence has a zero term. Although the Skolem-Mahler-Lech Theorem is almost 90 years old, decidability of the Skolem Problem remains open. One of the main contributions of the talk is to present an algorithm to solve the Skolem Problem for simple linear recurrence sequences (those with simple characteristic roots). Whenever the algorithm terminates, it produces a stand-alone certificate that its output is correct - a set of zeros together with a collection of witnesses that no further zeros exist. We give a proof that the algorithm always terminates assuming two classical number-theoretic conjectures: the Skolem Conjecture (also known as the Exponential Local-Global Principle) and the \(p\)-adic Schanuel Conjecture. Preliminary experiments with an implementation of this algorithm within the tool SKOLEM point to the practical applicability of this method.
In the second part of the talk, we present the notion of an Universal Skolem Set, which is a subset of the positive integers on which the Skolem is decidable regardless of the linear recurrence. We give two examples of such sets, one of which is of positive density (that is, contains a positive proportion of all the positive integers).
(Coathors: Y. Bilu, J. Nieuwveld, J. Ouaknine, D. Purser, and J. Worrell)
|
14:00 |
Übungsraum 2 |