Algorithmic Problems for Recurrence Sequences (Ben WORRELL, University of Oxford)

15.10.2026 16:15

Recurrence sequences arise across mathematics and theoretical computer science and some of their most basic properties lead to surprisingly difficult algorithmic questions. For example: given a sequence of rational numbers defined by a linear recurrence and initial conditions, can we determine whether the sequence has a zero and/or whether all terms are nonnegative?

In this talk, we will survey these and related decision problems, and explain how they are related to topics in program analysis, dynamical systems, and combinatorics. We start with the classical Skolem–Mahler–Lech theorem, which gives a structural description of the zeros of linear recurrence sequences but leaves open the question of effectively determining the zeros.

I will discuss the current state of the art on the decidability of such problems, highlighting what is known and salient open questions.
Along the way, we will explain how central results from Diophantine geometry and transcendence theory, such as the Subspace Theorem and the analytic subgroup theorem, enter the algorithmic theory of recurrence sequences.

Le colloque sera suivi d'un apéritif

Lieu

Bâtiment: Conseil Général 7-9

Salle 1-15, Colloque de mathématiques

entrée libre

Fichiers joints

Ben Worell.pdf

90.7 Kb