Conference item icon

Conference item

The membership problem for hypergeometric sequences with rational parameters

Abstract:
We investigate the Membership Problem for hypergeometric sequences: given a hypergeometric sequence ❬un❭∞n=0 of rational numbers and a target t∈Q, 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.
Publication status:
Published
Peer review status:
Peer reviewed

Actions

Access Document

Files:
Publisher copy:
10.1145/3476446.3535504

Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Oxford college:
Green Templeton College
Role:
Author


Publisher:
Association for Computing Machinery
Host title:
ISSAC '22: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation
Pages:
381-389
Publication date:
2022-07-04
Acceptance date:
2022-05-08
Event title:
ISSAC '22: International Symposium on Symbolic and Algebraic Computation
Event location:
Lille, France
Event website:
https://www.issac-conference.org/2022/
Event start date:
2022-07-04
Event end date:
2022-07-07
DOI:
ISBN:
9781450386883


Language:
English
Keywords:
Pubs id:
1269975
Local pid:
pubs:1269975
Deposit date:
2022-08-08
ARK identifier:

Terms of use


Views and Downloads

Views and downloads will return soon






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP