# Positivity Problems for Reversible Linear Recurrence Sequences

G. Kenison,
J. Nieuwveld,
J. Ouaknine,
J. Worrell

May, 2023

### 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 *simple* LRS (i.e., those sequences whose characteristic polynomials have 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 $\langle u_n \rangle_{n=0}^\infty$ whose bi-infinite completion $\langle u_n \rangle_{n=-\infty}^\infty$ also takes exclusively integer values; a typical example is the classical Fibonacci (bi-)sequence $\langle \dots, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, \ldots \rangle$. 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.

Publication

*International Colloquium on Automata, Languages, and Programming, ICALP ‘23*