The Membership Problem for Hypergeometric Sequences with Quadratic Parameters
share
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^∞ is one that satisfies a recurrence of the form f(n)u_n = g(n)u_n-1 where f,g ∈ℤ[x]. In this paper, we consider the Membership Problem for hypergeometric sequences: given a hypergeometric sequence ⟨ u_n ⟩_n=0^∞ and a target value t∈ℚ, 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 ℚ. Our results are based on an analysis of the prime divisors of polynomial sequences ⟨ f(n) ⟩_n=1^∞ and ⟨ g(n) ⟩_n=1^∞ appearing in the recurrence relation.
READ FULL TEXT