An infinite sequence
of real numbers is holonomic (also
known as P-recursive or P-finite) if it satisfies a linear
recurrence relation with polynomial coefficients. Such a sequence is
said to be positive if each
un ≥ 0,
and minimal if, given any other
linearly independent sequence
satisfying the same recurrence relation, the ratio
un/vn → 0
as n → ∞.
In this paper we give a Turing reduction of the problem of deciding positivity of second-order holonomic sequences to that of deciding minimality of such sequences. More specifically, we give a procedure for determining positivity of second-order holonomic sequences that terminates in all but an exceptional number of cases, and we show that in these exceptional cases positivity can be determined using an oracle for deciding minimality.
Proceedings of MFCS 21, LIPIcs 202, 2021. 15 pages.
© 2021 George Kenison, Oleksiy Klurman, Engel
Lefaucheux, Florian Luca, Pieter Moree,
Joël Ouaknine, Markus A. Whiteland, and James Worrell.