Positivity Problems for Low-Order Linear Recurrence Sequences

2013/07/10 by Joël Ouaknine, James Worrell, Ouaknine, Joel +1 · 5 citations
Computer Science · #Algorithms and Data Compression #Chaos-based Image/Signal Encryption #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.1307.2779

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

Abstract

We consider two decision problems for linear recurrence sequences (LRS) over the integers, namely the Positivity Problem (are all terms of a given LRS positive?) and the Ultimate Positivity Problem (are all but finitely many terms of a given LRS positive?). We show decidability of both problems for LRS of order 5 or less, with complexity in the Counting Hierarchy for Positivity, and in polynomial time for Ultimate Positivity. Moreover, we show by way of hardness that extending the decidability of either problem to LRS of order 6 would entail major breakthroughs in analytic number theory, more precisely in the field of Diophantine approximation of transcendental numbers.

Cited by

• The Target Discounted-Sum Problem
• Positivity of Nearly Linearly Recurrent Sequences
• On Expansions of Monadic Second-Order Logic with Dynamical Predicates
• Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space
• The Ultimate Signs of Second-Order Holonomic Sequences

Related

• On the Positivity Problem for Simple Linear Recurrence Sequences
• Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences
• Robust Positivity Problems for Linear Recurrence Sequences
• Positivity of Nearly Linearly Recurrent Sequences
• The Positivity Set of a Recurrence Sequence