The membership problem for hypergeometric sequences with rational parameters
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...
| প্রধান লেখক: | , , , |
|---|---|
| বিন্যাস: | Conference item |
| ভাষা: | English |
| প্রকাশিত: |
Association for Computing Machinery
2022
|
| _version_ | 1826308275614777344 |
|---|---|
| author | Nosan, K Pouly, A Shirmohammadi, M Worrell, J |
| author_facet | Nosan, K Pouly, A Shirmohammadi, M Worrell, J |
| author_sort | Nosan, K |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T07:15:39Z |
| format | Conference item |
| id | oxford-uuid:a1fd2ebc-5bb0-48e8-9ba7-ec56c5a2cd42 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:15:39Z |
| publishDate | 2022 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:a1fd2ebc-5bb0-48e8-9ba7-ec56c5a2cd422022-08-09T14:47:52ZThe membership problem for hypergeometric sequences with rational parametersConference itemhttp://purl.org/coar/resource_type/c_5794uuid:a1fd2ebc-5bb0-48e8-9ba7-ec56c5a2cd42EnglishSymplectic ElementsAssociation for Computing Machinery2022Nosan, KPouly, AShirmohammadi, MWorrell, JWe 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. |
| spellingShingle | Nosan, K Pouly, A Shirmohammadi, M Worrell, J The membership problem for hypergeometric sequences with rational parameters |
| title | The membership problem for hypergeometric sequences with rational parameters |
| title_full | The membership problem for hypergeometric sequences with rational parameters |
| title_fullStr | The membership problem for hypergeometric sequences with rational parameters |
| title_full_unstemmed | The membership problem for hypergeometric sequences with rational parameters |
| title_short | The membership problem for hypergeometric sequences with rational parameters |
| title_sort | membership problem for hypergeometric sequences with rational parameters |
| work_keys_str_mv | AT nosank themembershipproblemforhypergeometricsequenceswithrationalparameters AT poulya themembershipproblemforhypergeometricsequenceswithrationalparameters AT shirmohammadim themembershipproblemforhypergeometricsequenceswithrationalparameters AT worrellj themembershipproblemforhypergeometricsequenceswithrationalparameters AT nosank membershipproblemforhypergeometricsequenceswithrationalparameters AT poulya membershipproblemforhypergeometricsequenceswithrationalparameters AT shirmohammadim membershipproblemforhypergeometricsequenceswithrationalparameters AT worrellj membershipproblemforhypergeometricsequenceswithrationalparameters |