On inequality decision problems for low-order holonomic sequences

A sequence is holonomic if its terms obey a linear recurrence relation with polynomial coefficients. In this paper we consider decision problems for first- and second-order holonomic sequences involving inequalities. For first-order sequences <u_n>_n and <v_n>_n, we show that the problem of determining whether u_n ≤ v_n for each n reduces to the problem of testing equality between periods (in the sense of Kontsevich and Zagier) and their generalisations. For second-order sequences whose coefficients are either constants or linear polynomials, we show that Positivity (i.e., the problem of determining whether the terms of a sequence are all non-negative) also reduces to the problem of testing equality between periods and their generalisations.

Submitted, 2023. 14 pages.

PDF © 2023 George Kenison, Oleksiy Klurman, Engel Lefaucheux, Florian Luca, Pieter Moree, Joël Ouaknine, Markus A. Whiteland, and James Worrell.