Computing error bounds for asymptotic expansions of regular P-recursive sequences

Dong, Ruiwen; Melczer, Stephen; Mezzarobba, Marc

doi:10.1090/mcom/3888

Computing error bounds for asymptotic expansions of regular P-recursive sequences
HTML articles powered by AMS MathViewer

by Ruiwen Dong, Stephen Melczer and Marc Mezzarobba

Math. Comp. 93 (2024), 977-1017

DOI: https://doi.org/10.1090/mcom/3888

Published electronically: August 16, 2023

HTML | PDF

Abstract:

Over the last several decades, improvements in the fields of analytic combinatorics and computer algebra have made determining the asymptotic behaviour of sequences satisfying linear recurrence relations with polynomial coefficients largely a matter of routine, under assumptions that hold often in practice. The algorithms involved typically take a sequence, encoded by a recurrence relation and initial terms, and return the leading terms in an asymptotic expansion up to a big-O error term. Less studied, however, are effective techniques giving an explicit bound on asymptotic error terms. Among other things, such explicit bounds typically allow the user to automatically prove sequence positivity (an active area of enumerative and algebraic combinatorics) by exhibiting an index when positive leading asymptotic behaviour dominates any error terms.

In this article, we present a practical algorithm for computing such asymptotic approximations with rigorous error bounds, under the assumption that the generating series of the sequence is a solution of a differential equation with regular (Fuchsian) dominant singularities. Our algorithm approximately follows the singularity analysis method of Flajolet and Odlyzko [SIAM J. Discrete Math. 3 (1990), pp. 216–240], except that all big-O terms involved in the derivation of the asymptotic expansion are replaced by explicit error terms. The computation of the error terms combines analytic bounds from the literature with effective techniques from rigorous numerics and computer algebra. We implement our algorithm in the SageMath computer algebra system and exhibit its use on a variety of applications (including our original motivating example, solution uniqueness in the Canham model for the shape of genus one biomembranes).

References

M. A. Barkatou, Contribution à l’étude des équations différentielles et aux différences dans le champ complexe, Thèse de doctorat, Institut national polytechnique de Grenoble, 1989.
Yuliy Baryshnikov, Stephen Melczer, Robin Pemantle, and Armin Straub, Diagonal asymptotics for symmetric rational functions via ACSV, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, LIPIcs. Leibniz Int. Proc. Inform., vol. 110, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018, pp. Art. No. 12, 15. MR 3826131
George D. Birkhoff, Formal theory of irregular linear difference equations, Acta Math. 54 (1930), no. 1, 205–246. MR 1555307, DOI 10.1007/BF02547522
George D. Birkhoff and W. J. Trjitzinsky, Analytic theory of singular difference equations, Acta Math. 60 (1933), no. 1, 1–89. MR 1555364, DOI 10.1007/BF02398269
Alin Bostan and Sergey Yurkevich, A hypergeometric proof that $\mathsf {Iso}$ is bijective, Proc. Amer. Math. Soc. 150 (2022), no. 5, 2131–2136. MR 4392347, DOI 10.1090/proc/15836
Mireille Bousquet-Mélou, Rational and algebraic series in combinatorial enumeration, International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, 2006, pp. 789–826. MR 2275707
Richard P. Brent, Fast multiple-precision evaluation of elementary functions, J. Assoc. Comput. Mach. 23 (1976), no. 2, 242–251. MR 395314, DOI 10.1145/321941.321944
C. Chabaud, Séries génératrices algébriques : asymptotique et applications combinatoires, Ph.D. thesis, Université Pierre et Marie Curie (UPMC), 2002.
R. Dong, Asymptotic expansion and error bounds of p-recursive sequences, Master’s thesis, Master parisien de recherche en informatique.
Anne Duval, Solutions irrégulières d’équations aux différences polynomiales, Differential equations and Pfaffian systems in the complex field, II, Lecture Notes in Math., vol. 1015, Springer, Berlin, 1983, pp. 64–101 (French). MR 766243, DOI 10.1007/BFb0071350
Philippe Flajolet and Andrew Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (1990), no. 2, 216–240. MR 1039294, DOI 10.1137/0403019
Philippe Flajolet and Claude Puech, Partial match retrieval of multidimensional data, J. Assoc. Comput. Mach. 33 (1986), no. 2, 371–407. MR 835110, DOI 10.1145/5383.5453
Philippe Flajolet, Bruno Salvy, and Paul Zimmermann, Automatic average-case analysis of algorithms. no. 1 (Part A), Theoret. Comput. Sci. 79 (1991), no. 1, (Part A), 37–109. Algebraic and computing treatment of noncommutative power series (Lille, 1988). MR 1102951, DOI 10.1016/0304-3975(91)90145-R
Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235, DOI 10.1017/CBO9780511801655
Philippe Flajolet and Brigitte Vallée, Continued fractions, comparison algorithms, and fine structure constants, Constructive, experimental, and nonlinear analysis (Limoges, 1999) CRC Math. Model. Ser., vol. 27, CRC, Boca Raton, FL, 2000, pp. 53–82. MR 1777617
C. L. Frenzen, Error bounds for the asymptotic expansion of the ratio of two gamma functions with complex argument, SIAM J. Math. Anal. 23 (1992), no. 2, 505–511. MR 1147874, DOI 10.1137/0523024
Stefan Gerhold and Manuel Kauers, A procedure for proving special function inequalities involving a discrete parameter, ISSAC’05, ACM, New York, 2005, pp. 156–162. MR 2280542, DOI 10.1145/1073884.1073907
B. Hackl, C. Heuberger, and D. Krenn, Asymptotic expansions in SageMath, module in SageMath 6.10.
Hui Huang and Manuel Kauers, D-finite numbers, Int. J. Number Theory 14 (2018), no. 7, 1827–1848. MR 3831395, DOI 10.1142/S1793042118501099
G. K. Immink, On the relation between linear difference and differential equations with polynomial coefficients, Math. Nachr. 200 (1999), 59–76. MR 1682781, DOI 10.1002/mana.19992000104
G. K. Immink, Reduction to canonical forms and the Stokes phenomenon in the theory of linear difference equations, SIAM J. Math. Anal. 22 (1991), no. 1, 238–259. MR 1080156, DOI 10.1137/0522014
Fredrik Johansson, Arb: efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Trans. Comput. 66 (2017), no. 8, 1281–1292. MR 3681746, DOI 10.1109/TC.2017.2690633
S. Julliot, Automatic asymptotics for combinatorial series, Master’s thesis, Université Paris Diderot.
R. Jungen, Sur les séries de Taylor n’ayant que des singularités algébrico-logarithmiques sur leur cercle de convergence, Comment. Math. Helv. 3 (1931), no. 1, 266–306 (French). MR 1509439, DOI 10.1007/BF01601817
E. A. Karatsuba, Fast computation of the values of the Hurwitz zeta function and Dirichlet $L$-series, Problemy Peredachi Informatsii 34 (1998), no. 4, 62–75 (Russian, with Russian summary); English transl., Problems Inform. Transmission 34 (1998), no. 4, 342–353 (1999). MR 1793495
M. Kauers, A Mathematica package for computing asymptotic expansions of solutions of P-finite recurrence equations, Tech. report, 2011.
Manuel Kauers, Maximilian Jaroschek, and Fredrik Johansson, Ore polynomials in Sage, Computer algebra and polynomials, Lecture Notes in Comput. Sci., vol. 8942, Springer, Cham, 2015, pp. 105–125. MR 3335570, DOI 10.1007/978-3-319-15081-9_{6}
Manuel Kauers and Veronika Pillwein, When can we detect that a P-finite sequence is positive?, ISSAC 2010—Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2010, pp. 195–201. MR 2920554, DOI 10.1145/1837934.1837974
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, 46th International Symposium on Mathematical Foundations of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., vol. 202, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, pp. Art. No. 67, 15. MR 4309740
S. Melczer, An Invitation to Analytic Combinatorics: From One to Several Variables, Texts and Monographs in Symbolic Computation, Springer International Publishing, 2021.
Stephen Melczer and Marc Mezzarobba, Sequence positivity through numeric analytic continuation: uniqueness of the Canham model for biomembranes, Comb. Theory 2 (2022), no. 2, Paper No. 4, 20. MR 4449812
M. Mezzarobba, Autour de l’évaluation numérique des fonctions D-finies, Thèse de doctorat, École polytechnique, November 2011.
M. Mezzarobba, Rigorous multiple-precision evaluation of D-finite functions in SageMath, Tech. Report, arXiv:1607.01967, 2016.
Marc Mezzarobba, Truncation bounds for differentially finite series, Ann. H. Lebesgue 2 (2019), 99–148 (English, with English and French summaries). MR 3974489, DOI 10.5802/ahl.17
Sri Gopal Mohanty, Lattice path counting and applications, Probability and Mathematical Statistics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London-Toronto, 1979. MR 554084
G. Nemes, Error bounds for the asymptotic expansion of the Hurwitz zeta function, Proc. A. 473 (2017), no. 2203, 20170363, 16. MR 3685478, DOI 10.1098/rspa.2017.0363
Eike Neumann, Joël Ouaknine, and James Worrell, Decision problems for second-order holonomic recurrences, 48th International Colloquium on Automata, Languages, and Programming, LIPIcs. Leibniz Int. Proc. Inform., vol. 198, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2021, pp. Art. No. 99, 20. MR 4288929
A. M. Odlyzko, Asymptotic enumeration methods, Handbook of combinatorics, Vol. 1, 2, Elsevier Sci. B. V., Amsterdam, 1995, pp. 1063–1229. MR 1373678
F. W. J. Olver, Asymptotics and special functions, Computer Science and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1974. MR 435697
Joël Ouaknine and James Worrell, Positivity problems for low-order linear recurrence sequences, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, 2014, pp. 366–379. MR 3376387, DOI 10.1137/1.9781611973402.27
Veronika Pillwein, Termination conditions for positivity proving procedures, ISSAC 2013—Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2013, pp. 315–321. MR 3206373, DOI 10.1145/2465506.2465945
S. Pincherle, Sur la génération de systémes récurrents, Acta Math. 16 (1892), no. 1, 341–363 (French). Au moyen d’une équation linéaire différentielle. MR 1554831, DOI 10.1007/BF02418993
E. G. C. Poole, Introduction to the theory of linear differential equations, Dover Publications, Inc., New York, 1960. MR 111886
B. Salvy, Fonctions génératrices et asymptotique automatique, Tech. report, INRIA, January 1989.
B. Salvy, Asymptotique automatique et fonctions génératrices, Thèse de doctorat, École polytechnique, January 1991.
Évelyne Tournier, Solutions formelles d’équations différentielles, Doctorat d’État, 1987.
F. G. Tricomi and A. Erdélyi, The asymptotic expansion of a ratio of gamma functions, Pacific J. Math. 1 (1951), 133–142. MR 43948, DOI 10.2140/pjm.1951.1.133
Joris van der Hoeven, Fast evaluation of holonomic functions near and in regular singularities, J. Symbolic Comput. 31 (2001), no. 6, 717–743. MR 1834006, DOI 10.1006/jsco.2000.0474
Joris van der Hoeven, Efficient accelero-summation of holonomic functions, J. Symbolic Comput. 42 (2007), no. 4, 389–428. MR 2317557, DOI 10.1016/j.jsc.2006.12.005
J. van der Hoeven, Efficient accelero-summation of holonomic functions, Corrected version of \cite{Hoeven2007}, 2021, https://hal.science/hal-03154241.
J. van der Hoeven, Fuchsian holonomic sequences, July 2021.
Marius van der Put and Michael F. Singer, Galois theory of difference equations, Lecture Notes in Mathematics, vol. 1666, Springer-Verlag, Berlin, 1997. MR 1480919, DOI 10.1007/BFb0096118
Thomas Yu and Jingmin Chen, Uniqueness of Clifford torus with prescribed isoperimetric ratio, Proc. Amer. Math. Soc. 150 (2022), no. 4, 1749–1765. MR 4375762, DOI 10.1090/proc/15750
D. Zeilberger, AsyRec: A Maple package for computing the asymptotics of solutions of linear recurrence equations with polynomial coefficients, April 2008.