On inequality decision problems for low-order holonomic sequences

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

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, …, gkQ[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:

  1. For second-order holonomic sequences, the Positivity Problem reduces to the Minimality Problem.
  2. For second-order, degree-1 holonomic sequences, the Positivity and Minimality Problems both reduce to the Equality Problems for exponential periods and pseudoperiods.
  3. The Hypergeometric Inequality Problem reduces to the Pseudoperiod Equality Problem.

Working paper, 2021. 18 pages.

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



Imprint / Data Protection