research-article

The Membership Problem for Hypergeometric Sequences with Rational Parameters

Authors:

Mahsa Shirmohammadi,

James WorrellAuthors Info & Claims

ISSAC '22: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation

Pages 381 - 389

https://doi.org/10.1145/3476446.3535504

Published: 05 July 2022 Publication History

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.

References

[1]

T. Amdeberhan, L. Medina, and V. Moll. 2007. Asymptotic valuations of sequences satisfying first order recurrences. Proc. Amer. Math. Soc., Vol. 137 (10 2007), 885--890.

[2]

Y. André. 2004. Une introduction aux motifs (motifs purs, motifs mixtes, périodes). Panoramas et Synthèses, Vol. 17. Société Mathématique de France.

[3]

J. Bell, S. Burris, and K. Yeats. 2011. On the set of zero coefficients of a function satisfying a linear differential equation. Mathematical Proceedings of the Cambridge Philosophical Society, Vol. 153 (05 2011), 235--247.

[4]

M. A. Bennett, G. Martin, K. O'Bryant, and A. Rechnitzer. 2018. Explicit bounds for primes in arithmetic progressions. Illinois Journal of Mathematics, Vol. 62, 1--4 (2018), 427 -- 532.

[5]

M. Chamberland and A. Straub. 2013. On gamma quotients and infinite products. Advances in Applied Mathematics, Vol. 51, 5 (2013), 546--562.

Digital Library

[6]

E. Delaygue, T. Rivoal, and J. Roques. 2013. On Dwork's p-adic formal congruences theorem and hypergeometric mirror maps. Memoirs of the American Mathematical Society, Vol. 246 (09 2013). https://doi.org/10.1090/memo/1163

[7]

M. Kauers and P. Paule. 2011. The Concrete Tetrahedron - Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates .Springer.

[8]

M. Kauers and V. Pillwein. 2010. When can we detect that a P-finite sequence is positive?. In Symbolic and Algebraic Computation, International Symposium, ISSAC, Proceedings, Wolfram Koepf (Ed.). ACM, 195--201.

[9]

G. Kenison, O. Klurman, E. Lefaucheux, F. Luca, P. Moree, J. Ouaknine, A. Whiteland, and J. Worrell. 2020. On Inequality Decision Prolems for Low-Order Holonomic Sequences .arxiv: 2007.12282 Submitted.

[10]

G. Kenison, O. Klurman, E. Lefaucheux, F. Luca, P. Moree, J. Ouaknine, M. A. Whiteland, and J. Worrell. 2021. On Positivity and Minimality for Second-Order Holonomic Sequences. In 46th International Symposium on Mathematical Foundations of Computer Science, MFCS (LIPIcs, Vol. 202). Schloss Dagstuhl - Leibniz-Zentrum fü r Informatik, 67:1--67:15.

[11]

N. Koblitz and A. Ogus. 1979. Algebraicity of some products of values of the F function, Appendix of Valeurs de fonctions L et periodes d'intégrales. Proceedings of Symposia in Pure Mathematics, Vol. 33 (1979), part 2, 313--346.

[12]

S. Lang. 1977--1978. Relations de distributions et exemples classiques. Séminaire Delange-Pisot-Poitou. Théorie des nombres, Vol. 19, 2 (1977--1978).

[13]

M. Mignotte, T. N. Shorey, and R. Tijdeman. 1984. The distance between terms of an algebraic recurrence sequence. Journal für die reine und angewandte Mathematik, Vol. 349 (1984).

[14]

J. Nagura. 1952. On The Interval Containing At Least One Prime Number. Proceedings of the Japan Academy, Vol. 28, 4 (1952), 177--181. https://doi.org/10.3792/pja/1195570997

[15]

E. Neumann, J. Ouaknine, and J. Worrell. 2021. Decision Problems for Second-Order Holonomic Recurrences. In 48th International Colloquium on Automata, Languages, and Programming, ICALP (LIPIcs, Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum fü r Informatik, 99:1--99:20.

[16]

M. Petkovsek, H. Wilf, and D. Zeilberger. 1997. A=B. A K Peters.

[17]

V. Pillwein and M. Schussler. 2015. An efficient procedure deciding positivity for a class of holonomic functions. ACM Commun. Comput. Algebra, Vol. 49, 3 (2015), 90--93.

Digital Library

[18]

N. K. Vereshchagin. 1985. The problem of appearance of a zero in a linear recurrence sequence (in Russian). Mat. Zametki, Vol. 38, 2 (1985).

[19]

M. Waldschmidt. 2006. Transcendence of periods: the state of the art. Pure and Applied Mathematics Quarterly, Vol. 2, 2 (2006), 435--463.

Cited By

Kenison GNosan KShirmohammadi MWorrell J(2023)The Membership Problem for Hypergeometric Sequences with Quadratic ParametersProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597121(407-416)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597121
van der Hoeven J(2023)Fuchsian holonomic sequencesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-023-00616-4Online publication date: 24-Sep-2023
https://doi.org/10.1007/s00200-023-00616-4

Index Terms

The Membership Problem for Hypergeometric Sequences with Rational Parameters
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

The Membership Problem for Hypergeometric Sequences with Quadratic Parameters
ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation

Hypergeometric sequences are rational-valued sequences that satisfy first-order linear recurrence relations with polynomial coefficients; that is, a hypergeometric sequence is one that satisfies a recurrence of the form f(n)un = g(n)un − 1 where .

In ...
Subanalytic solutions of linear difference equations and multidimensional hypergeometric sequences

We consider linear difference equations with polynomial coefficients over C and their solutions in the form of sequences indexed by the integers (sequential solutions). We investigate the C-linear space of subanalytic solutions, i.e., those sequential ...
Hypergeometric-type sequences
Abstract
We introduce hypergeometric-type sequences. They are linear combinations of interlaced hypergeometric sequences (of arbitrary interlacements). We prove that they form a subring of the ring of holonomic sequences. An interesting family of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '22: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation

July 2022

547 pages

ISBN:9781450386883

DOI:10.1145/3476446

General Chair:
Marc Moreno Maza
University of Western Ontario, Canada
,
Program Chair:
Lihong Zhi
Chinese Academy of Sciences, China

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Research Council

Conference

ISSAC '22

Sponsor:

SIGSAM

ISSAC '22: International Symposium on Symbolic and Algebraic Computation

July 4 - 7, 2022

Villeneuve-d'Ascq, France

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
69
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kenison GNosan KShirmohammadi MWorrell J(2023)The Membership Problem for Hypergeometric Sequences with Quadratic ParametersProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597121(407-416)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597121
van der Hoeven J(2023)Fuchsian holonomic sequencesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-023-00616-4Online publication date: 24-Sep-2023
https://doi.org/10.1007/s00200-023-00616-4

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents