Document Open Access Logo

On Positivity and Minimality for Second-Order Holonomic Sequences

Authors George Kenison, Oleksiy Klurman, Engel Lefaucheux, Florian Luca, Pieter Moree , Joël Ouaknine , Markus A. Whiteland , James Worrell

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.67.pdf
  • Filesize: 0.69 MB
  • 15 pages

Document Identifiers

Author Details

George Kenison
  • Institute for Logic and Computation, The Technical University of Vienna, Austria
Oleksiy Klurman
  • School of Mathematics, University of Bristol, UK
  • Max Planck Institute for Mathematics, Bonn, Germany
Engel Lefaucheux
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
Florian Luca
  • School of Mathematics, University of the, Witwatersrand, Johannesburg, South Africa
  • Research Group in Algebraic Structures & , Applications, King Abdulaziz University, Riyadh, Saudi Arabia
  • Centro de Ciencias Matemáticas UNAM, Morelia, Mexico
Pieter Moree
  • Max Planck Institute for Mathematics, Bonn, Germany
Joël Ouaknine
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
Markus A. Whiteland
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany
James Worrell
  • Department of Computer Science, University of Oxford, UK

Funding

  • Kenison, George: WWTF Grant ProbInG ICT19-018 and the ERC Consolidator Grant ARTIST 101002685.
  • Ouaknine, Joël: ERC grant AVS-ISS (648701), and DFG grant 389792660 as part of TRR 248 (see https://perspicuous-computing.science). Joël Ouaknine is also affiliated with Keble College, Oxford as http://emmy.network/ Fellow.
  • Worrell, James: EPSRC Fellowship EP/N008197/1.

Acknowledgements

This work was partly carried out during a visit of Florian Luca at the Max Planck Institute for Software Systems in Saarbrücken, Germany from September 2020 to March 2021. He thanks the institution for its hospitality and excellent working conditions. The authors would like to thank the anonymous referees for their detailed comments, which have led to significant improvements and clarifications in the final version of this paper.

Cite AsGet BibTex

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. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 67:1-67:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.67

Abstract

An infinite sequence ⟨u_n⟩_n of real numbers is holonomic (also known as P-recursive or P-finite) if it satisfies a linear recurrence relation with polynomial coefficients. Such a sequence is said to be positive if each u_n ≥ 0, and minimal if, given any other linearly independent sequence ⟨v_n⟩_n satisfying the same recurrence relation, the ratio u_n/v_n → 0 as n → ∞. In this paper we give a Turing reduction of the problem of deciding positivity of second-order holonomic sequences to that of deciding minimality of such sequences. More specifically, we give a procedure for determining positivity of second-order holonomic sequences that terminates in all but an exceptional number of cases, and we show that in these exceptional cases positivity can be determined using an oracle for deciding minimality.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic and verification
Keywords
  • Holonomic sequences
  • Minimal solutions
  • Positivity Problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Roger Apéry. Irrationalité de ζ (2) et ζ (3). Astérisque, 61:11-13, 1979. Luminy Conference on Arithmetic. Google Scholar
  2. Douglas Bowman and James Mc Laughlin. Polynomial continued fractions. Acta Arith., 103(4):329-342, 2002. Google Scholar
  3. Annie Cuyt, Vigdis B. Petersen, Brigitte Verdonk, Haakon Waadeland, and William B. Jones. Handbook of continued fractions for special functions. Springer, New York, 2008. Google Scholar
  4. Alfred Deaño and Javier Segura. Transitory minimal solutions of hypergeometric recursions and pseudoconvergence of associated continued fractions. Mathematics of Computation, 76(258):879-901, 2007. Google Scholar
  5. Alfred Deaño, Javier Segura, and Nico M. Temme. Computational properties of three-term recurrence relations for Kummer functions. J. Computational Applied Mathematics, 233(6):1505-1510, 2010. Google Scholar
  6. Graham Everest, Alfred J. van der Poorten, Igor E. Shparlinski, and Thomas Ward. Recurrence Sequences, volume 104 of Mathematical surveys and monographs. American Mathematical Society, 2003. Google Scholar
  7. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. Google Scholar
  8. Walter Gautschi. Computational aspects of three-term recurrence relations. SIAM Rev., 9:24-82, 1967. Google Scholar
  9. Walter Gautschi. Anomalous Convergence of a Continued Fraction for Ratios of Kummer Functions. Mathematics of Computation, 31(140):994-999, 1977. Google Scholar
  10. Walter Gautschi. Minimal solutions of three-term recurrence relations and orthogonal polynomials. Mathematics of Computation, 36(154), 1981. Google Scholar
  11. Amparo Gil, Javier Segura, and Nico M. Temme. Numerical Methods for Special Functions, chapter 4, pages 87-122. SIAM, 2007. Google Scholar
  12. Vesa Halava, Tero Harju, and Mika Hirvensalo. Positivity of second order linear recurrent sequences. Discrete Appl. Math., 154(3):447-451, 2006. Google Scholar
  13. Lisa Jacobsen. On the convergence of limit periodic continued fractions K(a_n/1), where a_n → -1/4. II. In Analytic theory of continued fractions, II (Pitlochry/Aviemore, 1985), volume 1199 of Lecture Notes in Math., pages 48-58. Springer, Berlin, 1986. Google Scholar
  14. Lisa Jacobsen and Alphonse Magnus. On the convergence of limit periodic continued fractions K(a_n/1), where a_n → -1/4. In Peter Russell Graves-Morris, Edward B. Saff, and Richard S. Varga, editors, Rational Approximation and Interpolation, pages 243-248, Berlin, Heidelberg, 1984. Springer Berlin Heidelberg. Google Scholar
  15. Lisa Jacobsen and David R. Masson. On the convergence of limit periodic continued fractions K(a_n/1), where a_n → -1/4. III. Constr. Approx., 6(4):363-374, 1990. Google Scholar
  16. Lisa Jacobsen and David R. Masson. A sequence of best parabola theorems for continued fractions. Rocky Mountain J. Math., 21(1):377-385, March 1991. Google Scholar
  17. 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
  18. Robert-Jan Kooman. Convergence properties of recurrence sequences. Centrum voor Wiskunde en Informatica, 1991. Google Scholar
  19. Robert-Jan Kooman and Robert Tijdeman. Convergence properties of linear recurrence sequences. Nieuw Arch. Wisk. (4), 8(1):13-25, 1990. Google Scholar
  20. Vichian Laohakosol and Pinthira Tangsupphathawat. Positivity of third order linear recurrence sequences. Discrete Appl. Math., 157(15):3239-3248, 2009. Google Scholar
  21. Lily L. Liu. Positivity of three-term recurrence sequences. Electron. J. Combin., 17(1):Research Paper 57, 10, 2010. Google Scholar
  22. Lisa Lorentzen. Computation of limit periodic continued fractions. A survey. Numerical Algorithms, 10(1):69-111, 1995. Google Scholar
  23. Lisa Lorentzen and Haakon Waadeland. Continued fractions with applications, volume 3 of Studies in Computational Mathematics. North-Holland Publishing Co., Amsterdam, 1992. Google Scholar
  24. Lisa Lorentzen and Haakon Waadeland. Continued fractions. Vol. 1, volume 1 of Atlantis Studies in Mathematics for Engineering and Science. Atlantis Press, Paris; World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, second edition, 2008. Google Scholar
  25. James Mc Laughlin and N. J. Wyshinski. Real numbers with polynomial continued fraction expansions. Acta Arith., 116(1):63-79, 2005. Google Scholar
  26. Marc Mezzarobba and Bruno Salvy. Effective bounds for P-recursive sequences. J. Symbolic Comput., 45(10):1075-1096, 2010. Google Scholar
  27. 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, volume 198 of LIPIcs, pages 99:1-99:20, 2021. Google Scholar
  28. Joël Ouaknine and James Worrell. Positivity problems for low-order linear recurrence sequences. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 366-379. ACM, New York, 2014. Google Scholar
  29. Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, volume 8573 of Lecture Notes in Computer Science, pages 330-341. Springer, 2014. Google Scholar
  30. Joël Ouaknine and James Worrell. On linear recurrence sequences and loop termination. SIGLOG News, 2(2):4-13, 2015. Google Scholar
  31. Marko Petkovšek, Herbert Wilf, and Doron Zeilberger. A=B. A. K. Peters, 1997. Google Scholar
  32. Veronika Pillwein. Termination conditions for positivity proving procedures. In Manuel Kauers, editor, International Symposium on Symbolic and Algebraic Computation, ISSAC'13, Boston, MA, USA, June 26-29, 2013, pages 315-322. ACM, 2013. Google Scholar
  33. Veronika Pillwein and Miriam Schussler. An efficient procedure deciding positivity for a class of holonomic functions. ACM Comm. Computer Algebra, 49(3):90-93, 2015. Google Scholar
  34. Salvatore Pincherle. Delle Funzioni ipergeometriche, e di varie questioni ad esse attinenti. Giorn. Mat. Battaglini, 32:209-291, 1894. Google Scholar
  35. Alfred van der Poorten. A proof that Euler missed…Apéry’s proof of the irrationality of ζ (3). Math. Intelligencer, 1(4):195-203, 1979. Google Scholar
  36. Haakon Waadeland. Tales about tails. Proceedings of the American Mathematical Society, 90(1):57-57, 1984. Google Scholar
  37. John Wallis. Arithmetica infinitorum, sive nova methodus inquirendi in curvilineorum quadraturam, aliaque difficiliori matheseos problemata. Oxford, pages 1-199, 1655. Google Scholar
  38. John Wallis. The arithmetic of infinitesimals. Sources and Studies in the History of Mathematics and Physical Sciences. Springer-Verlag, New York, 2004. Translated from the Latin and with an introduction by Jacqueline A. Stedall. Google Scholar
  39. Ernest X. W. Xia and X. M. Yao. The signs of three-term recurrence sequences. Discrete Applied Mathematics, 159(18):2290-2296, 2011. Google Scholar
  40. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact