21 August 2012
2:30 - 4:00   Joel Ouaknine (Oxford)
Positivity Problems for Low-Order Linear Recurrence Sequences

Abstract
Given a linear recurrence sequence over the reals (such as the Fibonacci numbers), the Positivity Problem asks whether the terms of the sequence are all positive, and similarly the Ultimate Positivity Problem asks whether the terms of the sequence are all positive except possibly for finitely many exceptions. Positivity and Ultimate Positivity (as well as closely related variants) have 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 and Ultimate Positivity (for integer, rational, or algebraic sequences) is a long-standing open problem (mentioned, for example, in [Sal76], but likely going back much earlier). Recent progress on the subject include decidability for integer linear recurrence sequences of order two [HHH06] and order three [LT09]. Our main results are as follows:

(i) Positivity and Ultimate Positivity are decidable for algebraic linear recurrence sequences of order 5 or less. Moreover, the computational complexity of our decision procedures lies in the counting hierarchy for the former and is in polynomial time for the latter.

(ii) When the companion matrix of the linear recurrence sequence is diagonalisable, these problems become decidable for sequences of order 9 or less.

(iii) Extending either Positivity or Ultimate Positivity even to integer 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 (at the very least) of significant advances in number theory.

I will introduce the main results, discuss their significance, and present some of the key ideas appearing in the proofs.
(This is joint work with James Worrell and Matt Daws.)

References:

[HHH06] V. Halava, T. Harju, and M. Hirvensalo. Positivity of second order linear recurrent sequences. Discrete Applied Mathematics, 154(3), 2006.

[LT09] V. Laohakosol and P. Tangsupphathawat. Positivity of third order linear recurrence sequences. Discrete Applied Mathematics, 157(15), 2009.

[Sal76] A. Salomaa. Growth functions of Lindenmayer systems: Some new approaches. In A. Lindenmayer and G. Rozenberg, editors, Automata, Languages, Development. North-Holland, 1976.