2024/12/11 by Alaa Ibrahim, Bruno Salvy, Ibrahim, Alaa +1
Computer Science · Mathematics · #FOS: Computer and information sciences #Mathematics and Applications #Matrix Theory and Algorithms #Polynomial and algebraic computation #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.2412.08576
openalex publication_date 2024/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Deciding the positivity of a sequence defined by a linear recurrence with polynomial coefficients and initial condition is difficult in general. Even in the case of recurrences with constant coefficients, it is known to be decidable only for order up to~5. We consider a large class of linear recurrences of arbitrary order, with polynomial coefficients, for which an algorithm decides positivity for initial conditions outside of a hyperplane. The underlying algorithm constructs a cone, contracted by the recurrence operator, that allows a proof of positivity by induction. The existence and construction of such cones relies on the extension of the classical Perron-Frobenius theory to matrices leaving a cone invariant.