TY - JOUR
T1 - Coefficient Asymptotics of Algebraic Multivariable Generating Functions
AU - Baryshnikov, Yuliy
AU - Jin, Kaitian
AU - Pemantle, Robin
N1 - Publisher Copyright:
© The Author(s), under exclusive licence to Springer Science+Business Media LLC, part of Springer Nature 2024.
PY - 2024/3
Y1 - 2024/3
N2 - 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].
AB - 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].
KW - 05A16
KW - Algebraic
KW - Analytic combinatorics
KW - Coefficient extraction
KW - Generating function
KW - secondary 57Q99
UR - http://www.scopus.com/inward/record.url?scp=85195586771&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85195586771&partnerID=8YFLogxK
U2 - 10.1007/s44007-024-00086-1
DO - 10.1007/s44007-024-00086-1
M3 - Article
AN - SCOPUS:85195586771
SN - 2730-9657
VL - 3
SP - 293
EP - 336
JO - Matematica
JF - Matematica
IS - 1
ER -