@inproceedings{986aa58b311d404d9e7d19301a62500b,
title = "The Membership Problem for Hypergeometric Sequences with Rational Parameters",
abstract = "We investigate the Membership Problem for hypergeometric sequences: given a hypergeometric sequence unn=0 of rational numbers and a target tQ, decide whether t occurs in the sequence. We show decidability of this problem under the assumption that in the defining recurrence p(n)un = q(n)un-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.",
keywords = "decidability, hypergeometric sequences, reachability, skolem problem",
author = "Klara Nosan and Amaury Pouly and Mahsa Shirmohammadi and James Worrell",
note = "Publisher Copyright: {\textcopyright} 2022 ACM.; 47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022 ; Conference date: 04-07-2022 Through 07-07-2022",
year = "2022",
month = jul,
day = "4",
doi = "10.1145/3476446.3535504",
language = "English",
series = "Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC",
publisher = "Association for Computing Machinery",
pages = "381--389",
editor = "Amir Hashemi",
booktitle = "ISSAC 2022 - Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022",
}