Positivity problems for low-order linear recurrence sequences
|
Tue, 07/05 14:30 |
Joel Ouaknine (University of Oxford) |
Combinatorial Theory Seminar  |
L3 |
| 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.This talk is based on a recent paper, available athttp://www.cs.ox.ac.uk/people/joel.ouaknine/publications/positivity13abs.html joint with James Worrell and Matt Daws. | |||