The Membership Problem for Hypergeometric Sequences with Quadratic Parameters

Abstract

Hypergeometric sequences are rational-valued sequences that satisfy first-order linear recurrence relations with polynomial coefficients; that is, a hypergeometric sequence $⟨u_n{⟩}_{n=0}^{\infty }$ is one that satisfies a recurrence of the form $f(n)u_n=g(n)u_{n-1}$ where $f,g\in \mathbb{Z}[x]$. In this paper, we consider the Membership Problem for hypergeometric sequences: given a hypergeometric sequence $⟨u_n{⟩}_{n=0}^{\infty }$ and a target value $t\in \mathbb{Q}$, determine whether $u_n=t$ for some index $n$. We establish decidability of the Membership Problem under the assumption that either (i) $f$ and $g$ have distinct splitting fields or (ii) $f$ and $g$ are monic polynomials that both split over a quadratic extension of $\mathbb{Q}$. Our results are based on an analysis of the prime divisors of polynomial sequences $⟨f(n){⟩}_{n=1}^{\infty }$ and $⟨g(n){⟩}_{n=1}^{\infty }$ appearing in the recurrence relation.

18 pages (including appendices). Accepted at ISSAC 2023