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

DOI10.1090/MCOM/3888MaRDI QIDQ6181106zbMATH OpenFDO

Authors Stephen Melczer, Marc Mezzarobba

Publication date 2 January 2024

Published in Mathematics of Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2212.11742

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Interval and finite arithmetic (65G30) Symbolic computation and algebraic computation (68W30)

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, 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).

Cites work

• A hypergeometric proof that \(\mathsf{Iso}\) is bijective
• A procedure for proving special function inequalities involving a discrete parameter
• An invitation to analytic combinatorics. From one to several variables
• Analytic combinatorics
• Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic
• Automatic average-case analysis of algorithms
• D-finite numbers
• Diagonal asymptotics for symmetric rational functions via ACSV
• Efficient accelero-summation of holonomic functions
• Error bounds for the asymptotic expansion of the Hurwitz zeta function
• Error Bounds for the Asymptotic Expansion of the Ratio of Two Gamma Functions with Complex Argument
• Fast evaluation of holonomic functions near and in regular singularities
• Fast Multiple-Precision Evaluation of Elementary Functions
• Galois theory of difference equations
• scientific article; zbMATH DE number 3832515 (Why is no real title available?)
• scientific article; zbMATH DE number 3147792 (Why is no real title available?)
• scientific article; zbMATH DE number 3712896 (Why is no real title available?)
• scientific article; zbMATH DE number 3474264 (Why is no real title available?)
• scientific article; zbMATH DE number 1552278 (Why is no real title available?)
• scientific article; zbMATH DE number 863491 (Why is no real title available?)
• scientific article; zbMATH DE number 7724240 (Why is no real title available?)
• On the Relation between Linear Difference and Differential Equations with Polynomial Coefficients
• Ore polynomials in Sage
• Partial match retrieval of multidimensional data
• Positivity problems for low-order linear recurrence sequences
• Rational and algebraic series in combinatorial enumeration
• Reduction to Canonical Forms and the Stokes Phenomenon in the Theory of Linear Difference Equations
• Sequence positivity through numeric analytic continuation: uniqueness of the Canham model for biomembranes
• Singularity Analysis of Generating Functions
• Termination conditions for positivity proving procedures
• The asymptotic expansion of a ratio of gamma functions
• Truncation bounds for differentially finite series
• Uniqueness of Clifford torus with prescribed isoperimetric ratio
• When can we detect that a P-finite sequence is positive?

Cited in

(1)

• Recursion-free formula for certain differentiably finite power series by inversion of pseudo-differential operators

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Computing error bounds for asymptotic expansions of regular P-recursive sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6181106)