Decision Problems for Second-Order Holonomic Recurrences

Authors Eike Neumann, Joël Ouaknine, James Worrell



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.99.pdf
  • Filesize: 0.69 MB
  • 20 pages

Document Identifiers

Author Details

Eike Neumann
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
Joël Ouaknine
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
James Worrell
  • Department of Computer Science, Oxford University, UK

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

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)
    0
    PDF Downloads

References

  1. 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. Google Scholar
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. 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.
  5. Maxim Kontsevich and Don Zagier. Periods. In Mathematics unlimited - 2001 and beyond, pages 771-808. Springer, Berlin, 2001. Google Scholar
  6. 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. Google Scholar
  7. Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger. A = B. A.K. Peters, 1997. Google Scholar
  8. 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. Google Scholar
  9. 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. Google Scholar
  10. R.P. Stanley. Differentiably finite power series. European Journal of Combinatorics, 1(2):175-188, 1980. Google Scholar
  11. Doron Zeilberger. A holonomic systems approach to special functions identities. Journal of Computational and Applied Mathematics, 32(3):321-368, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail