Holonomic Techniques, Periods, and Decision Problems (Invited Talk)

Author Joël Ouaknine



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.4.pdf
  • Filesize: 309 kB
  • 3 pages

Document Identifiers

Author Details

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

Cite AsGet BibTex

Joël Ouaknine. Holonomic Techniques, Periods, and Decision Problems (Invited Talk). In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 4:1-4:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.4

Abstract

Holonomic techniques have deep roots going back to Wallis, Euler, and Gauss, and have evolved in modern times as an important subfield of computer algebra, thanks in large part to the work of Zeilberger and others over the past three decades. In this talk, I will give an overview of the area, and in particular will present a select survey of known and original results on decision problems for holonomic sequences and functions. (Holonomic sequences satisfy linear recurrence relations with polynomial coefficients, and holonomic functions satisfy linear differential equations with polynomial coefficients.) I will also discuss some surprising connections to the theory of periods and exponential periods, which are classical objects of study in algebraic geometry and number theory; in particular, I will relate the decidability of certain decision problems for holonomic sequences to deep conjectures about periods and exponential periods, notably those due to Kontsevich and Zagier.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • holonomic techniques
  • decision problems
  • recurrence sequences
  • minimal solutions
  • Positivity Problem
  • continued fractions
  • special functions
  • periods
  • exponential periods

Metrics

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

References

  1. Gil Amparo, Javier Segura, and Nico M. Temme. Numerical methods for special functions, 2007. Google Scholar
  2. Roger Apéry. Irrationalité de ζ (2) et ζ (3). In Journées Arithmétiques de Luminy, number 61 in Astérisque, pages 11-13. Société mathématique de France, 1979. URL: http://www.numdam.org/item/AST_1979__61__11_0.
  3. Alfredo 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
  4. Alfredo 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
  5. 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
  6. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009. Google Scholar
  7. Walter Gautschi. Computational aspects of three-term recurrence relations. SIAM Rev., 9:24-82, 1967. Google Scholar
  8. Walter Gautschi. Anomalous convergence of a continued fraction for ratios of kummer functions. Mathematics of Computation, 31(140):994-999, 1977. Google Scholar
  9. Walter Gautschi. Minimal solutions of three-term recurrence relations and orthogonal polynomials. Mathematics of Computation, 36(154), 1981. Google Scholar
  10. V. Halava, T. Harju, and M. Hirvensalo. Positivity of second order linear recurrent sequences. Discrete Appl. Math., 154(3):447-451, 2006. Google Scholar
  11. 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
  12. 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: https://arxiv.org/abs/2007.12282.
  13. Maxim Kontsevich and Don Zagier. Periods. In Mathematics unlimited - 2001 and beyond, pages 771-808. Springer, Berlin, 2001. Google Scholar
  14. V. Laohakosol and P. Tangsupphathawat. Positivity of third order linear recurrence sequences. Discrete Appl. Math., 157(15):3239-3248, 2009. Google Scholar
  15. Lily Liu. Positivity of three-term recurrence sequences. Electron. J. Combin., 17(1):Research Paper 57, 10, 2010. Google Scholar
  16. M. Mezzarobba and B. Salvy. Effective bounds for P-recursive sequences. J. Symbolic Comput., 45(10):1075-1096, 2010. Google Scholar
  17. 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
  18. Joël Ouaknine and James Worrell. On linear recurrence sequences and loop termination. SIGLOG News, 2(2):4-13, 2015. Google Scholar
  19. 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
  20. Marko Petkovšek, Herbert Wilf, and Doron Zeilberger. A=B. A. K. Peters, 1997. Google Scholar
  21. 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
  22. 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
  23. 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
  24. 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