Positivity Problem for Linear Recurrence Sequences

Select arbitrary finite order k>=1, rational constant coefficients a_1,...,a_k and rational initial values u_0,...,u_(k-1), each finitely encoded in binary, with u_(n+k)=sum_(i=1)^k a_i u_(n+k-i) for all n>=0. The assertion is that a total algorithm exists which, for EVERY such input, halts and correctly decides whether u_n>=0 for EVERY n>=0. There is no running-time bound. All coefficient values, including a_k=0, are permitted.

Source: Positivity-hardness results on Markov decision processes, arXiv2302.13675v2, 5 April 2024; TheoretiCS3 Article9.

Status Open · subcases solved Status review date not recorded in this edition

Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.