The Membership Problem for Hypergeometric Sequences with Rational Parameters

2022/02/15 by Nosan, Klara, Pouly, Amaury, Shirmohammadi, Mahsa +1 · 2 citations
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.2202.07416

Abstract

We investigate the Membership Problem for hypergeometric sequences: given a hypergeometric sequence ⟨ u_n ⟩_n=0^∞ of rational numbers and a target t ∈ ℚ, decide whether t occurs in the sequence. We show decidability of this problem under the assumption that in the defining recurrence p(n)u_n=q(n)u_n-1, the roots of the polynomials p(x) and q(x) are all rational numbers. Our proof relies on bounds on the density of primes in arithmetic progressions. We also observe a relationship between the decidability of the Membership problem (and variants) and the Rohrlich-Lang conjecture in transcendence theory.

Cited by

• On the growth of hypergeometric sequences
• The Ultimate Signs of Second-Order Holonomic Sequences

Related

• The Membership Problem for Hypergeometric Sequences with Quadratic Parameters
• The Threshold Problem for Hypergeometric Sequences with Quadratic Parameters
• On the growth of hypergeometric sequences
• HTP-complete rings of rational numbers
• Denominator Bounds and Polynomial Solutions for Systems of q-Recurrences over K(t) for Constant K