The Membership and Threshold Problems for Hypergeometric Sequences with Quadratic Parameters

MaRDI QIDQ6416167zbMATH OpenFDO

Authors George Kenison

Publication date 4 November 2022

Abstract: The membership and threshold problems for recurrence sequences are fundamental open decision problems in automated verification. The former problem asks whether a chosen target is an element of a sequence, whilst the latter asks whether every term in a sequence is bounded from below by a given value. A rational-valued sequence $langle{u}_{n}angl{e}_n$ is hypergeometric if it satisfies a first-order linear recurrence of the form $p(n)u_{n+1}=q(n)u_n$ with polynomial coefficients $p,qinmathbbZ[x]$. In this note we establish decidability results for the aforementioned problems for restricted classes of hypergeometric sequences. For example, we establish decidability for the aforementioned problems under the assumption that the polynomial coefficients $p,qinmathbbZ[x]$ are monic and split over an imaginary rational extension of $mathbbQ$. We also establish conditional decidability results; that is, conditional on Schanuel's conjecture, when the irreducible factors of the monic polynomial coefficients $p,qinmathbbZ[x]$ are either linear or quadratic.

This page was built for publication: The Membership and Threshold Problems for Hypergeometric Sequences with Quadratic Parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6416167)