## On the Positivity Problem for simple
linear recurrence sequences

*Joel
Ouaknine* and *James Worrell*
Given a linear recurrence sequence (LRS) over the integers, the
*Positivity Problem* asks whether all terms of the sequence are
positive. We show that, for simple LRS (those whose characteristic
polynomial has no repeated roots) of order 9 or less, Positivity is
decidable, with complexity in the Counting Hierarchy.

*Proceedings of ICALP 14*, LNCS 8573, 2014. 26 pages.

PDF
© 2014
Springer-Verlag.