Coefficient Asymptotics of Algebraic Multivariable Generating Functions

• Published in: La matematica 2024-02, Vol.3 (1), p.293-336
• Main Authors: Baryshnikov, Yuliy, Jin, Kaitian, Pemantle, Robin
• Format: Article
• Language: English
• Subjects: Mathematics; Mathematics and Statistics; Original Research Article
• ISSN: 2730-9657; 2730-9657
• DOI: 10.1007/s44007-024-00086-1

Analytic combinatorics in several variables (ACSV) seeks to extract the asymptotic behavior of coefficients from a generating function in several variables. As much as possible, the extraction should be automatic, taking as input some finite specification of the generating function. A complexity hierarchy of specifiable generating functions usually begins with rational functions, then goes up to algebraic functions, D-finite functions, and perhaps beyond. Already the first two classes contain the majority of combinatorial problems for which any kind of generating function has been written down. For examples of rational multivariate generating functions in combinatorics, see [ 27 ]. For examples of algebraic multivariate generating functions, see [ 13 ]. ACSV machinery developed for rational generating functions uses integrals of residue forms over intersection cycles to provide asymptotics for coefficients via the multivariate Cauchy integral formula. By embedding the coefficient array for an algebraic generating function as the generalized diagonal of the coefficient array of a rational generating function with one more variable, the authors of [ 13 ] are able to reduce coefficient asymptotics for a class of algebraic generating functions to a previously solved problem involving a rational function in one more variable. In this paper, we take a different approach, namely to write the Cauchy integral for an arbitrarily specified algebraic function directly as an integral over the defining surface for the algebraic function. This leads to a similar computation, without invoking the technical apparatus of residue forms and intersection cycles. We give examples of how to apply this method to the functions in [ 13 ] and compare the difficulty of our computations and transparency of our formulas to those presented in the online appendix to [ 13 ].