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 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
<un>n=0n=∞
whose bi-infinite completion
<un>n=-∞n=∞
also takes exclusively integer
values; a typical example is the classical Fibonacci (bi-)sequence
<…,5,-3,2,-1,1,0,1,1,2,3,5,…>. 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.
Proceedings of ICALP 23, LIPIcs 261, 2023. 17 pages.
PDF
© 2023 George Kenison, Joris Nieuwveld, Joël Ouaknine, and
James Worrell.