Mikołaj Bojańczyk

Decision Problems for Linear Recurrence Sequences


This one of the courses at the Lipa Summer School.

Joël Ouaknine

Decision Problems for Linear Recurrence Sequences

 

Linear recurrence sequence (LRS), such as the Fibonacci numbers, permeate vast areas of mathematics, physics, and computer science. In this tutorial, I consider some fundamental decision problems for LRS over the integers, such as the Skolem Problem (does the sequence have a zero?) and the Positivity Problem (are all terms of the sequence positive?).

In general, the decidability of such problems is open, but various partial results are known. I will introduce some of the key mathematical tools for attacking these problems, and present some of the known results.