The Positivity Problem for Low-Order Linear Recurrence Sequences

Speaker

James Worrel (University of Oxford)
Title The Positivity Problem for Low-Order Linear Recurrence Sequences
When 24.04.2013, 10:00
Where Room 5052
Abstract Given a linear recurrence sequence over the rationals, the Positivity Problem asks whether the terms of the sequence are all positive. Positivity (and closely related variants) has applications in many different areas, such as theoretical biology (analysis of L-systems, population dynamics), software verification (termination of linear programs), probabilistic model checking (reachability in Markov chains, stochastic logics), quantum computing (threshold problems for quantum automata), as well as combinatorics, term rewriting, and the study of generating functions.The decidability of Positivity is a long-standing open problem. Until now, the only known result was that for integer linear recurrence sequences of order 2, Positivity is decidable [Halava 2007]. Our main results are as follows:

(i) Positivity is decidable for linear recurrence sequences of order 5 or less;

(ii) When the the characteristic polynomial of the linear recurrence sequence has simple roots, it becomes possible to decide Positivity for sequences of order 9 or less;

(iii) Extending (i) even to linear recurrence sequences of order 6 would entail major breakthroughs in the field of Diophantine approximation of transcendental numbers. The present results therefore appear unlikely to be improved in the absence of significant advances in number theory.

Finally, in terms of complexity, we show that our decision procedures lie within the counting hierarchy.

This is joint work with Joel Ouaknine and Matthew Daws