Decision Problems for Linear Recurrence Sequences

Linear recurrence sequences (LRS), such as the Fibonacci numbers, permeate vast areas of mathematics and computer science. In this talk, we consider three natural decision problems for LRS over the integers, namely the Skolem Problem (does a given LRS have a zero?), the Positivity Problem (are all terms of a given LRS positive?), and the Ultimate Positivity Problem (are all but finitely many terms of a given LRS positive?). Such questions have applications in a wide array of scientific areas, ranging from theoretical biology and software verification to quantum computing and statistical physics. Perhaps surprisingly, the study of decision problems for linear recurrence sequences (and more generally linear dynamical systems) involves techniques from a variety of mathematical fields, including analytic and algebraic number theory, Diophantine geometry, and algebraic geometry. I will survey some of the known results as well as recent advances and open problems.

This is joint work with James Worrell