The Membership Problem for Hypergeometric Sequences with Rational Parameters

Klara Nosan; Amaury Pouly; Mahsa Shirmohammadi; James Worrell

doi:10.1145/3476446.3535504

The Membership Problem for Hypergeometric Sequences with Rational Parameters

Klara Nosan
, Amaury Pouly
, Mahsa Shirmohammadi
, James Worrell

Laboratoire de Probabilités et Modèles Aléatoires
University of Oxford

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

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.

langue originale	Anglais
titre	ISSAC 2022 - Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022
rédacteurs en chef	Amir Hashemi
Editeur	Association for Computing Machinery
Pages	381-389
Nombre de pages	9
ISBN (Electronique)	9781450386883
Les DOIs	https://doi.org/10.1145/3476446.3535504
état	Publié - 4 juil. 2022
Modification externe	Oui
Evénement	47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022 - Virtual, Online, France Durée: 4 juil. 2022 → 7 juil. 2022

Série de publications

Nom	Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

Une conférence

Une conférence	47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022
Pays/Territoire	France
La ville	Virtual, Online
période	4/07/22 → 7/07/22

Accès au document

10.1145/3476446.3535504

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

Nosan, K., Pouly, A., Shirmohammadi, M., & Worrell, J. (2022). The Membership Problem for Hypergeometric Sequences with Rational Parameters. Dans A. Hashemi (Ed.), ISSAC 2022 - Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022 (p. 381-389). (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). Association for Computing Machinery. https://doi.org/10.1145/3476446.3535504

Nosan, Klara ; Pouly, Amaury ; Shirmohammadi, Mahsa et al. / The Membership Problem for Hypergeometric Sequences with Rational Parameters. ISSAC 2022 - Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022. Editeur / Amir Hashemi. Association for Computing Machinery, 2022. p. 381-389 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

@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",

}

Nosan, K, Pouly, A, Shirmohammadi, M & Worrell, J 2022, The Membership Problem for Hypergeometric Sequences with Rational Parameters. Dans A Hashemi (Ed.), ISSAC 2022 - Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC, Association for Computing Machinery, p. 381-389, 47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022, Virtual, Online, France, 4/07/22. https://doi.org/10.1145/3476446.3535504

The Membership Problem for Hypergeometric Sequences with Rational Parameters. / Nosan, Klara; Pouly, Amaury; Shirmohammadi, Mahsa et al.
ISSAC 2022 - Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022. Ed. / Amir Hashemi. Association for Computing Machinery, 2022. p. 381-389 (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

TY - GEN

T1 - The Membership Problem for Hypergeometric Sequences with Rational Parameters

AU - Nosan, Klara

AU - Pouly, Amaury

AU - Shirmohammadi, Mahsa

AU - Worrell, James

PY - 2022/7/4

Y1 - 2022/7/4

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

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

KW - decidability

KW - hypergeometric sequences

KW - reachability

KW - skolem problem

UR - https://www.scopus.com/pages/publications/85134210992

U2 - 10.1145/3476446.3535504

DO - 10.1145/3476446.3535504

M3 - Conference contribution

AN - SCOPUS:85134210992

T3 - Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC

SP - 381

EP - 389

BT - ISSAC 2022 - Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022

A2 - Hashemi, Amir

PB - Association for Computing Machinery

T2 - 47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022

Y2 - 4 July 2022 through 7 July 2022

ER -

Nosan K, Pouly A, Shirmohammadi M, Worrell J. The Membership Problem for Hypergeometric Sequences with Rational Parameters. Dans Hashemi A, Editeur, ISSAC 2022 - Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation47th International Symposium on Symbolic and Algebraic Computation, ISSAC 2022. Association for Computing Machinery. 2022. p. 381-389. (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC). doi: 10.1145/3476446.3535504

The Membership Problem for Hypergeometric Sequences with Rational Parameters

Résumé

Série de publications

Une conférence

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation