## 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
<*u*_{n}>_{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:

*g*_{k+1}(*n*)*u*_{n+k} = *g*_{k}(*n*)*u*_{n+k-1} + … + *g*_{1}(*n*)*u*_{n} ,

where each coefficient
*g*_{0}, …, *g*_{k}
∈ **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
<*u*_{n}>_{n ∈ N} is
said to be *positive* if each
*u*_{n} ≥ 0,
and *minimal* if, given any other
linearly independent sequence
<*v*_{n}>_{n ∈ N}
satisfying the same recurrence relation, the ratio
*u*_{n}/*v*_{n} converges to 0.
Given two hypergeometric sequences
<*u*_{n}>_{n ∈ N}
and
<*v*_{n}>_{n ∈ N},
the
*Hypergeometric Inequality Problem*
asks whether, for all *n*, *u*_{n} ≤ *v*_{n}.

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:

- For second-order holonomic sequences, the Positivity Problem
reduces to the Minimality Problem.
- For second-order, degree-1 holonomic sequences, the
Positivity and Minimality Problems both reduce to the Equality Problems
for exponential periods and pseudoperiods.
- 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