Effective Positivity Problems for Simple Linear Recurrence Sequences?

Abstract. We consider two computational problems for linear recur-rence sequences (LRS) over the integers, namely the Positivity Problem (determine whether all terms of a given LRS are positive) and the ef-fective Ultimate Positivity Problem (determine whether all but finitely many terms of a given LRS are positive, and if so, compute an index threshold beyond which all terms 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 Count-ing Hierarchy, and effective Ultimate Positivity is solvable in polynomial time.