An infinite sequence
<un>n ∈ N
of real numbers is holonomic (also
known as P-recursive or P-finite) if it satisfies a linear
recurrence relation with polynomial coefficients:
gk+1(n)un+k = gk(n)un+k-1 + … + g1(n)un ,
where each coefficient g0, …, gk ∈ Q[n]. Here k is the order of the sequence; order-1 holonomic sequences are also known as hypergeometric sequences. The degree of the sequence is the highest degree of the polynomial coefficients appearing in the recurrence relation. A holonomic sequence <un>n ∈ N is said to be positive if each un ≥ 0, and minimal if, given any other linearly independent sequence <vn>n ∈ N satisfying the same recurrence relation, the ratio un/vn converges to 0. Given two hypergeometric sequences <un>n ∈ N and <vn>n ∈ N, the Hypergeometric Inequality Problem asks whether, for all n, un ≤ vn.
In this paper, we focus on various decision problems for second-order and hypergeometric sequences, and in particular on effective reductions concerning such problems. Some of these reductions also involve certain numerical quantities (known as periods, exponential periods, and pseudoperiods, originating from algebraic geometry and number theory), and classical decision problems regarding equalities among these (the Exponential Period and Pseudoperiod Equality Problems).
We establish the following:
Working paper, 2021. 18 pages.
© 2021 George Kenison, Oleksiy Klurman, Engel
Lefaucheux, Florian Luca, Pieter Moree,
Joël Ouaknine, Markus A. Whiteland, and James Worrell.