On the Positivity Problem for simple linear recurrence sequences

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.