LIPIcs.ICALP.2021.99.pdf
- Filesize: 0.69 MB
- 20 pages
Document
Decision Problems for Second-Order Holonomic Recurrences
Authors
-
Part of:
Volume:
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-07-02
Cite AsGet BibTex
Eike Neumann, Joël Ouaknine, and James Worrell. Decision Problems for Second-Order Holonomic Recurrences. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 99:1-99:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.99
https://doi.org/10.4230/LIPIcs.ICALP.2021.99
Abstract
We study decision problems for sequences which obey a second-order holonomic recurrence of the form f(n + 2) = P(n) f(n + 1) + Q(n) f(n) with rational polynomial coefficients, where P is non-constant, Q is non-zero, and the degree of Q is smaller than or equal to that of P. We show that existence of infinitely many zeroes is decidable. We give partial algorithms for deciding the existence of a zero, positivity of all sequence terms, and positivity of all but finitely many sequence terms. If Q does not have a positive integer zero then our algorithms halt on almost all initial values (f(1), f(2)) for the recurrence. We identify a class of recurrences for which our algorithms halt for all initial values. We further identify a class of recurrences for which our algorithms can be extended to total ones.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Discrete mathematics
Keywords
- holonomic sequences
- Positivity Problem
- Skolem Problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Jason P. Bell, Stanley N. Burris, and Karen Yeats. On the set of zero coefficients of a function satisfying a linear differential equation. Mathematical Proceedings of the Cambridge Philosophical Society, 153(2):235-247, 2012.
-
Stefan Gerhold and Manuel Kauers. A procedure for proving special function inequalities involving a discrete parameter. In Manuel Kauers, editor, Symbolic and Algebraic Computation, International Symposium ISSAC 2005, Beijing, China, July 24-27, 2005, Proceedings, pages 156-162. ACM, 2005.
-
Manuel Kauers and Veronika Pillwein. When can we detect that a P-finite sequence is positive? In Wolfram Koepf, editor, Symbolic and Algebraic Computation, International Symposium, ISSAC 2010, Munich, Germany, July 25-28, 2010, Proceedings, pages 195-201. ACM, 2010.
- George Kenison, Oleksiy Klurman, Engel Lefaucheux, Florian Luca, Pieter Moree, Joël Ouaknine, Markus A. Whiteland, and James Worrell. On positivity and minimality for second-order holonomic sequences. CoRR, abs/2007.12282, 2020. URL: http://arxiv.org/abs/2007.12282.
-
Maxim Kontsevich and Don Zagier. Periods. In Mathematics unlimited - 2001 and beyond, pages 771-808. Springer, Berlin, 2001.
-
Joël Ouaknine and James Worrell. Positivity problems for low-order linear recurrence sequences. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 366-379. SIAM, 2014.
-
Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger. A = B. A.K. Peters, 1997.
-
Veronika Pillwein. Termination conditions for positivity proving procedures. In Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ISSAC '13, page 315–322, New York, NY, USA, 2013. Association for Computing Machinery.
-
Veronika Pillwein and Miriam Schussler. An efficient procedure deciding positivity for a class of holonomic sequences. ACM Communications in Computer Algebra, 49(3):90-93, 2015. Extended abstract of the poster presentation at ISSAC 2015.
-
R.P. Stanley. Differentiably finite power series. European Journal of Combinatorics, 1(2):175-188, 1980.
-
Doron Zeilberger. A holonomic systems approach to special functions identities. Journal of Computational and Applied Mathematics, 32(3):321-368, 1990.