On the Positivity Problem for Simple Linear Recurrence Sequences

2013/09/06 by Joël Ouaknine, James Worrell, Ouaknine, Joel +1 · 1 citation
Computer Science · Engineering · #Coding theory and cryptography #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Polynomial and algebraic computation #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1309.1550

openalex publication_date 2013/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Linear Equations in Variables which Lie in a Multiplicative Group

Cited by

• Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space

Related

• Positivity Problems for Low-Order Linear Recurrence Sequences
• Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences
• Robust Positivity Problems for Linear Recurrence Sequences
• The Positivity Set of a Recurrence Sequence
• Positivity of Nearly Linearly Recurrent Sequences