Positivity Problems for Low-Order Linear Recurrence Sequences
Positivity Problems for Low-Order Linear Recurrence Sequences
复制标题
DOI：
10.1137/1.9781611973402.27
复制
发表时间：
2013-07
期刊：
影响因子：
--
通讯作者：
Joël Ouaknine;J. Worrell
中科院分区：
文献类型：
--
作者：
Joël Ouaknine;J. Worrell
我们考虑了整数上线性递归序列（LRS）的两个决策问题，即正性问题（给定LRS的所有项都是正的吗？）和最终正性问题}（给定LRS的所有项都是正的吗？）对于5阶或更小的LRS，我们证明了这两个问题的可判决性，对于正性具有计数层次的复杂性，对于最终正性具有多项式时间的复杂性。此外，我们通过硬度的方式表明，将这两个问题的可决性扩展到6阶的LRS将需要在解析数论中取得重大突破，更准确地说，在超越数的丢芬图近似领域。
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, with complexity in the Counting Hierarchy for Positivity, and in polynomial time for Ultimate Positivity. 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.