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:
-
-
(Preview, Accepted manuscript, pdf, 435.7KB, Terms of use)
-
- Publisher copy:
- 10.1145/3476446.3535504
Authors
- 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
- Copyright holder:
- Association for Computing Machinery
- Copyright date:
- 2022
- Rights statement:
- Copyright © 2022 ACM.
- Notes:
-
This is the accepted manuscript version of the paper. The final version is available online from the Association for Computing Machinery at:
https://doi.org/10.1145/3476446.3535504
If you are the owner of this record, you can report an update to it here: Report update to this record