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.<\/p>\n
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\u2013240], 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).<\/p>","DOI":"10.1090\/mcom\/3888","type":"journal-article","created":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T09:13:06Z","timestamp":1689153186000},"page":"977-1017","source":"Crossref","is-referenced-by-count":6,"title":["Computing error bounds for asymptotic expansions of regular P-recursive sequences"],"prefix":"10.1090","volume":"93","author":[{"given":"Ruiwen","family":"Dong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Melczer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Mezzarobba","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2023,8,16]]},"reference":[{"key":"1","unstructured":"M. A. Barkatou, Contribution \u00e0 l\u2019\u00e9tude des \u00e9quations diff\u00e9rentielles et aux diff\u00e9rences dans le champ complexe, Th\u00e8se de doctorat, Institut national polytechnique de Grenoble, 1989."},{"key":"2","isbn-type":"print","first-page":"Art. No. 12, 15","article-title":"Diagonal asymptotics for symmetric rational functions via ACSV","author":"Baryshnikov, Yuliy","year":"2018","ISBN":"https:\/\/id.crossref.org\/isbn\/9783959770781"},{"issue":"1","key":"3","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF02547522","article-title":"Formal theory of irregular linear difference equations","volume":"54","author":"Birkhoff, George D.","year":"1930","journal-title":"Acta Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5962","issn-type":"print"},{"issue":"1","key":"4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02398269","article-title":"Analytic theory of singular difference equations","volume":"60","author":"Birkhoff, George D.","year":"1933","journal-title":"Acta Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5962","issn-type":"print"},{"issue":"5","key":"5","doi-asserted-by":"publisher","first-page":"2131","DOI":"10.1090\/proc\/15836","article-title":"A hypergeometric proof that \ud835\udda8\ud835\uddcc\ud835\uddc8 is bijective","volume":"150","author":"Bostan, Alin","year":"2022","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"key":"6","isbn-type":"print","first-page":"789","article-title":"Rational and algebraic series in combinatorial enumeration","author":"Bousquet-M\u00e9lou, Mireille","year":"2006","ISBN":"https:\/\/id.crossref.org\/isbn\/9783037190227"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1145\/321941.321944","article-title":"Fast multiple-precision evaluation of elementary functions","volume":"23","author":"Brent, Richard P.","year":"1976","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"8","unstructured":"C. Chabaud, S\u00e9ries g\u00e9n\u00e9ratrices alg\u00e9briques : asymptotique et applications combinatoires, Ph.D. thesis, Universit\u00e9 Pierre et Marie Curie (UPMC), 2002."},{"key":"9","unstructured":"R. Dong, Asymptotic expansion and error bounds of p-recursive sequences, Master\u2019s thesis, Master parisien de recherche en informatique."},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/BFb0071350","article-title":"Solutions irr\u00e9guli\u00e8res d\u2019\u00e9quations aux diff\u00e9rences polynomiales","author":"Duval, Anne","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/3540126848"},{"issue":"2","key":"11","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0403019","article-title":"Singularity analysis of generating functions","volume":"3","author":"Flajolet, Philippe","year":"1990","journal-title":"SIAM J. Discrete Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4801","issn-type":"print"},{"issue":"2","key":"12","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1145\/5383.5453","article-title":"Partial match retrieval of multidimensional data","volume":"33","author":"Flajolet, Philippe","year":"1986","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"issue":"1","key":"13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0304-3975(91)90145-R","article-title":"Automatic average-case analysis of algorithms","volume":"79","author":"Flajolet, Philippe","year":"1991","journal-title":"Theoret. Comput. Sci.","ISSN":"https:\/\/id.crossref.org\/issn\/0304-3975","issn-type":"print"},{"key":"14","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic combinatorics","author":"Flajolet, Philippe","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9780521898065"},{"key":"15","isbn-type":"print","first-page":"53","article-title":"Continued fractions, comparison algorithms, and fine structure constants","author":"Flajolet, Philippe","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0821821679"},{"issue":"2","key":"16","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0523024","article-title":"Error bounds for the asymptotic expansion of the ratio of two gamma functions with complex argument","volume":"23","author":"Frenzen, C. L.","year":"1992","journal-title":"SIAM J. Math. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1410","issn-type":"print"},{"key":"17","isbn-type":"print","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1145\/1073884.1073907","article-title":"A procedure for proving special function inequalities involving a discrete parameter","author":"Gerhold, Stefan","year":"2005","ISBN":"https:\/\/id.crossref.org\/isbn\/1595930957"},{"key":"18","unstructured":"B. Hackl, C. Heuberger, and D. Krenn, Asymptotic expansions in SageMath, module in SageMath 6.10."},{"issue":"7","key":"19","doi-asserted-by":"publisher","first-page":"1827","DOI":"10.1142\/S1793042118501099","article-title":"D-finite numbers","volume":"14","author":"Huang, Hui","year":"2018","journal-title":"Int. J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/1793-0421","issn-type":"print"},{"key":"20","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/mana.19992000104","article-title":"On the relation between linear difference and differential equations with polynomial coefficients","volume":"200","author":"Immink, G. K.","year":"1999","journal-title":"Math. Nachr.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-584X","issn-type":"print"},{"issue":"1","key":"21","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1137\/0522014","article-title":"Reduction to canonical forms and the Stokes phenomenon in the theory of linear difference equations","volume":"22","author":"Immink, G. K.","year":"1991","journal-title":"SIAM J. Math. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1410","issn-type":"print"},{"issue":"8","key":"22","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1109\/TC.2017.2690633","article-title":"Arb: efficient arbitrary-precision midpoint-radius interval arithmetic","volume":"66","author":"Johansson, Fredrik","year":"2017","journal-title":"IEEE Trans. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9340","issn-type":"print"},{"key":"23","unstructured":"S. Julliot, Automatic asymptotics for combinatorial series, Master\u2019s thesis, Universit\u00e9 Paris Diderot."},{"issue":"1","key":"24","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/BF01601817","article-title":"Sur les s\u00e9ries de Taylor n\u2019ayant que des singularit\u00e9s alg\u00e9brico-logarithmiques sur leur cercle de convergence","volume":"3","author":"Jungen, R.","year":"1931","journal-title":"Comment. Math. Helv.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-2571","issn-type":"print"},{"issue":"4","key":"25","first-page":"62","article-title":"Fast computation of the values of the Hurwitz zeta function and Dirichlet \ud835\udc3f-series","volume":"34","author":"Karatsuba, E. A.","year":"1998","journal-title":"Problemy Peredachi Informatsii","ISSN":"https:\/\/id.crossref.org\/issn\/0555-2923","issn-type":"print"},{"key":"26","unstructured":"M. Kauers, A Mathematica package for computing asymptotic expansions of solutions of P-finite recurrence equations, Tech. report, 2011."},{"key":"27","isbn-type":"print","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-319-15081-9_6","article-title":"Ore polynomials in Sage","author":"Kauers, Manuel","year":"2015","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319150802"},{"key":"28","isbn-type":"print","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1145\/1837934.1837974","article-title":"When can we detect that a P-finite sequence is positive?","author":"Kauers, Manuel","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450301503"},{"key":"29","isbn-type":"print","first-page":"Art. No. 67, 15","article-title":"On positivity and minimality for second-order holonomic sequences","author":"Kenison, George","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783959772013"},{"key":"30","doi-asserted-by":"crossref","unstructured":"S. Melczer, An Invitation to Analytic Combinatorics: From One to Several Variables, Texts and Monographs in Symbolic Computation, Springer International Publishing, 2021.","DOI":"10.1007\/978-3-030-67080-1_7"},{"issue":"2","key":"31","first-page":"Paper No. 4, 20","article-title":"Sequence positivity through numeric analytic continuation: uniqueness of the Canham model for biomembranes","volume":"2","author":"Melczer, Stephen","year":"2022","journal-title":"Comb. Theory"},{"key":"32","unstructured":"M. Mezzarobba, Autour de l\u2019\u00e9valuation num\u00e9rique des fonctions D-finies, Th\u00e8se de doctorat, \u00c9cole polytechnique, November 2011."},{"key":"33","unstructured":"M. Mezzarobba, Rigorous multiple-precision evaluation of D-finite functions in SageMath, Tech. Report, arXiv:1607.01967, 2016."},{"key":"34","doi-asserted-by":"publisher","first-page":"99","DOI":"10.5802\/ahl.17","article-title":"Truncation bounds for differentially finite series","volume":"2","author":"Mezzarobba, Marc","year":"2019","journal-title":"Ann. H. Lebesgue"},{"key":"35","series-title":"Probability and Mathematical Statistics","isbn-type":"print","volume-title":"Lattice path counting and applications","author":"Mohanty, Sri Gopal","year":"1979","ISBN":"https:\/\/id.crossref.org\/isbn\/0125040504"},{"issue":"2203","key":"36","doi-asserted-by":"publisher","first-page":"20170363","DOI":"10.1098\/rspa.2017.0363","article-title":"Error bounds for the asymptotic expansion of the Hurwitz zeta function","volume":"473","author":"Nemes, G.","year":"2017","journal-title":"Proc. A","ISSN":"https:\/\/id.crossref.org\/issn\/1364-5021","issn-type":"print"},{"key":"37","isbn-type":"print","first-page":"Art. No. 99, 20","article-title":"Decision problems for second-order holonomic recurrences","author":"Neumann, Eike","year":"2021","ISBN":"https:\/\/id.crossref.org\/isbn\/9783959771955"},{"key":"38","isbn-type":"print","first-page":"1063","article-title":"Asymptotic enumeration methods","author":"Odlyzko, A. M.","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/044488002X"},{"key":"39","series-title":"Computer Science and Applied Mathematics","volume-title":"Asymptotics and special functions","author":"Olver, F. W. J.","year":"1974"},{"key":"40","isbn-type":"print","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1137\/1.9781611973402.27","article-title":"Positivity problems for low-order linear recurrence sequences","author":"Ouaknine, Jo\u00ebl","year":"2014","ISBN":"https:\/\/id.crossref.org\/isbn\/9781611973389"},{"key":"41","isbn-type":"print","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1145\/2465506.2465945","article-title":"Termination conditions for positivity proving procedures","author":"Pillwein, Veronika","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450320597"},{"issue":"1","key":"42","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/BF02418993","article-title":"Sur la g\u00e9n\u00e9ration de syst\u00e9mes r\u00e9currents","volume":"16","author":"Pincherle, S.","year":"1892","journal-title":"Acta Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0001-5962","issn-type":"print"},{"key":"43","volume-title":"Introduction to the theory of linear differential equations","author":"Poole, E. G. C.","year":"1960"},{"key":"44","unstructured":"B. Salvy, Fonctions g\u00e9n\u00e9ratrices et asymptotique automatique, Tech. report, INRIA, January 1989."},{"key":"45","unstructured":"B. Salvy, Asymptotique automatique et fonctions g\u00e9n\u00e9ratrices, Th\u00e8se de doctorat, \u00c9cole polytechnique, January 1991."},{"key":"46","volume-title":"Solutions formelles d'\\'{e}quations diff\\'{e}rentielles","author":"Tournier, \u00c9velyne","year":"1987"},{"key":"47","doi-asserted-by":"crossref","first-page":"133","DOI":"10.2140\/pjm.1951.1.133","article-title":"The asymptotic expansion of a ratio of gamma functions","volume":"1","author":"Tricomi, F. G.","year":"1951","journal-title":"Pacific J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0030-8730","issn-type":"print"},{"issue":"6","key":"48","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1006\/jsco.2000.0474","article-title":"Fast evaluation of holonomic functions near and in regular singularities","volume":"31","author":"van der Hoeven, Joris","year":"2001","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"4","key":"49","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1016\/j.jsc.2006.12.005","article-title":"Efficient accelero-summation of holonomic functions","volume":"42","author":"van der Hoeven, Joris","year":"2007","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"50","unstructured":"J. van der Hoeven, Efficient accelero-summation of holonomic functions, Corrected version of \\cite{Hoeven2007}, 2021, \\url{https:\/\/hal.science\/hal-03154241}."},{"key":"51","unstructured":"J. van der Hoeven, Fuchsian holonomic sequences, July 2021."},{"key":"52","series-title":"Lecture Notes in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0096118","volume-title":"Galois theory of difference equations","volume":"1666","author":"van der Put, Marius","year":"1997","ISBN":"https:\/\/id.crossref.org\/isbn\/3540632433"},{"issue":"4","key":"53","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.1090\/proc\/15750","article-title":"Uniqueness of Clifford torus with prescribed isoperimetric ratio","volume":"150","author":"Yu, Thomas","year":"2022","journal-title":"Proc. Amer. Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9939","issn-type":"print"},{"key":"54","unstructured":"D. Zeilberger, AsyRec: A Maple package for computing the asymptotics of solutions of linear recurrence equations with polynomial coefficients, April 2008."}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-346\/S0025-5718-2023-03888-1\/mcom3888_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-346\/S0025-5718-2023-03888-1\/S0025-5718-2023-03888-1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T05:13:53Z","timestamp":1776834833000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2024-93-346\/S0025-5718-2023-03888-1\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,16]]},"references-count":54,"journal-issue":{"issue":"346","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["S0025-5718-2023-03888-1"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3888","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2023,8,16]]}}}