ICALP 2023

Positivity Problems for Reversible Linear Recurrence Sequences

Jul 11, 2023, 3:30 PM

20m

Seminar Room 3 (HNF)

Track B

Speakers

George Kenison Joris Nieuwveld

Description

George Kenison, Joris Nieuwveld, Joël Ouaknine, and James Worrell

Abstract: It is a longstanding open problem whether there is an algorithm to decide the Positivity Problem for linear recurrence sequences (LRS) over the integers, namely whether given such a sequence, all its terms are non-negative. Decidability is known for LRS of order $5$ or less, i.e., for those sequences in which every new term depends linearly on the previous five (or fewer) terms. For \emph{simple} LRS (i.e., those whose characteristic polynomial has no repeated roots), decidability of Positivity is known up to order $9$.

In this paper, we focus on the important subclass of reversible LRS, i.e., those integer LRS $⟨u_n{⟩}_{n=0}^{\mathrm{\infty }}$ whose bi-infinite completion $⟨u_n{⟩}_{n=-\mathrm{\infty }}^{\mathrm{\infty }}$ also takes exclusively integer values; a typical example is the classical Fibonacci (bi-)sequence $⟨\dots ,5,-3,2,-1,1,0,1,1,2,3,5,\dots ⟩$. Our main results are that Positivity is decidable for reversible LRS of order $11$ or less, and for simple reversible LRS of order $17$ or less.