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 decidabi...

Expand abstract
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 Publisher's website
Pages:
381-389
Host title:
ISSAC '22: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation
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-04T00:00:00Z
Event end date:
2022-07-07T00:00:00Z
DOI:
ISBN:
9781450386883
Language:
English
Keywords:
Pubs id:
1269975
Local pid:
pubs:1269975
Deposit date:
2022-08-08

Terms of use


Views and Downloads






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

TO TOP