Positivity problems for low-order linear recurrence sequences

7 May 2013
14:30
Joel Ouaknine
Abstract
<p>We consider two decision problems for linear recurrence sequences(LRS) over the integers, namely the Positivity Problem (are all terms of a given LRS positive?) and the Ultimate Positivity Problem (are all but finitely many terms of a given LRS positive?). We show decidability of both problems for LRS of order 5 or less, and for simple LRS (i.e. whose characteristic polynomial has no repeated roots) of order 9 or less. Moreover, we show by way of hardness that extending the decidability of either problem to LRS of order 6 would entail major breakthroughs in analytic number theory, more precisely in the field of Diophantine approximation of transcendental numbers.<br />This talk is based on a recent paper, available at<br />http://www.cs.ox.ac.uk/people/joel.ouaknine/publications/positivity13abs.html<br /> joint with James Worrell and Matt Daws.</p>
  • Combinatorial Theory Seminar