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

Videos: 1234

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.