On the positivity problem for simple linear recurrence sequences
From MaRDI portal
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.
Recommendations
Cited in
(53)- The presence of a zero in an integer linear recurrent sequence is NP-hard to decide
- Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\)
- Exact optimal values of step-size coefficients for boundedness of linear multistep methods
- Quadratic maximization of reachable values of affine systems with diagonalizable matrix
- On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
- A robust class of linear recurrence sequences
- Algebraic model checking for discrete linear dynamical systems
- A switch convergence for a small perturbation of a linear recurrence equation
- On the complexity of polynomial recurrence sequences
- Recurrence relations, succession rules and the positivity problem
- Positivity of second order linear recurrent sequences
- Recurrence relations, succession rules, and the positivity problem
- A remark about the positivity problem problem of fourth order linear recurrence sequences
- scientific article; zbMATH DE number 5837696 (Why is no real title available?)
- The positivity problem for fourth order linear recurrence sequences is decidable
- Pumping lemmas for weighted automata
- scientific article; zbMATH DE number 4198066 (Why is no real title available?)
- Positivity of linear transformations of mean-starshaped sequences
- Decision problems for linear recurrence sequences
- scientific article; zbMATH DE number 6154366 (Why is no real title available?)
- On the Identity Problem for the Special Linear Group and the Heisenberg Group.
- Effective divergence analysis for linear recurrence sequences
- Dold sequences, periodic points, and dynamics
- Ultimate periodicity problem for linear numeration systems
- Toric varieties from cyclic matrix semigroups
- On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond
- scientific article; zbMATH DE number 7204378 (Why is no real title available?)
- Complexity of Restricted Variants of Skolem and Related Problems
- scientific article; zbMATH DE number 7407779 (Why is no real title available?)
- Decision problems for linear recurrences involving arbitrary real numbers
- Ultimate positivity is decidable for simple linear recurrence sequences
- Positivity problems for low-order linear recurrence sequences
- Point lattices and oscillating recurrence sequences†
- On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
- What's decidable about discrete linear dynamical systems?
- Skolem and positivity completeness of ergodic Markov chains
- On robustness for the Skolem, positivity and ultimate positivity problems
- Positivity-hardness results on Markov decision processes
- On the complexity of robust eventual inequality testing for C-finite functions
- Computing the density of the positivity set for linear recurrence sequences
- Linear dynamical systems with weight functions
- The threshold problem for hypergeometric sequences with quadratic parameters
- Positivity proofs for linear recurrences through contracted cones
- Robust positivity problems for linear recurrence sequences: the frontiers of decidability for explicitly given neighbourhoods
- Positive moments forever: undecidable and decidable cases
- Linear dynamical systems with continuous weight functions
- Polynomial loops: beyond termination
- Quadratic maximization of reachable values of stable discrete-time affine systems
- Targeting completeness: automated complexity analysis of integer programs
- Positivity proofs for linear recurrences with several dominant eigenvalues
- Deciding robust instances of an escape problem for dynamical systems in Euclidean space
- Analyzing ultimate positivity for solvable systems
- Positivity of third order linear recurrence sequences
This page was built for publication: On the positivity problem for simple linear recurrence sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167848)
