Publications in the Project

On this page we list the core papers which developed the area of ACSV as it is known today. Readers wanting pedagogical sources developing the theory of ACSV can consult

• An Invitation to Analytic Combinatorics: From One to Several Variables by Stephen Melczer. Texts & Monographs in Symbolic Computation, Springer International Publishing, 2021. (Introduction to the theory aimed at graduate students and those looking to enter the field. There is a computational focus with no prerequisite knowledge of geometry and topology assumed.)

• Analytic Combinatorics in Several Variables (2nd Edition) by Robin Pemantle, Mark C. Wilson, and Stephen Melczer. Cambridge University Press, 2024. (The most complete and expansive treatment of the theory for researchers, making use of stratified Morse theory to present a comprehensive framework for studying multivariate generating functions. The first edition came out in 2013.)

and those wanting to see further examples illustrating the theory can consult

• Twenty combinatorial examples of asymptotics derived from multivariate generating functions by Robin Pemantle and Mark C. Wilson. SIAM Review 50, 199-272, 2008.

• Analytic Combinatorics: A Multidimensional Approach by Marni Mishna. Discrete Mathematics and its Applications, CRC Press, 2020.

The following list of papers is updated on an ongoing basis and listed in reverse chronological order.

1. Asymptotics of multivariate sequences in the presence of a lacuna by Yuliy Baryshnikov, Stephen Melczer and Robin Pemantle. Accepted to Annales de l’Institut Henri Poincaré D: Combinatorics, Physics and their Interactions, 2024.
   Click here for abstract

   We explain a discontinuous drop in the exponential growth rate for certain multivariate generating functions at a critical parameter value, in even dimensions at least 4. This result depends on computations in the homology of the algebraic variety where the generating function has a pole. These computations are similar to, and inspired by, a thread of research in applications of complex algebraic geometry to hyperbolic PDEs, going back to Leray, Petrowski, Atiyah, Bott and Garding. As a consequence, we give a topological explanation for certain asymptotic phenomenon appearing in the combinatorics and number theory literature. Furthermore, we show how to combine topological methods with symbolic algebraic computation to determine explicitly the dominant asymptotics for such multivariate generating functions. This in turn enables the rigorous determination of integer coefficients in the Morse-Smale complex, which are difficult to determine using direct geometric methods.

2. Asymptotics of multivariate sequences IV: generating functions with poles on a hyperplane arrangement by Yuliy Baryshnikov, Stephen Melczer and Robin Pemantle. Accepted to Annals of Combinatorics, 2023.
   Click here for abstract

   Let F be the quotient of an analytic function with a product of linear functions. Working in the framework of analytic combinatorics in several variables, we compute asymptotic formulae for the Taylor coefficients of F using multivariate residues and saddle-point approximations. Because the singular set of F is the union of hyperplanes, we are able to make explicit the topological decompositions which arise in the multivariate singularity analysis. In addition to effective and explicit asymptotic results, we provide the first results on transitions between different asymptotic regimes, and provide the first software package to verify and compute asymptotics in non-smooth cases of analytic combinatorics in several variables. It is also our hope that this paper will serve as an entry to the more advanced corners of analytic combinatorics in several variables for combinatorialists.

3. Stationary points at infinity for analytic combinatorics by Yuliy Baryshnikov, Stephen Melczer and Robin Pemantle. Foundations of Computational Mathematics, Volume 22 (5), 1631–1664, 2022.
   Click here for abstract

   On complex algebraic varieties, height functions arising in combinatorial applications fail to be proper. This complicates the description and computation via Morse theory of key topological invariants. Here we establish checkable conditions under which the behavior at infinity may be ignored, and the usual theorems of classical and stratified Morse theory may be applied.

4. Effective Coefficient Asymptotics of Multivariate Rational Functions via Semi-Numerical Algorithms for Polynomial Systems by Stephen Melczer and Bruno Salvy. Journal of Symbolic Computation, Volume 103, 234–279, 2021.
   Click here for abstract

   This subsumes the results in the earlier conference paper (ISSAC 2016). The coefficient sequences of multivariate rational functions appear in many areas of combinatorics. Their diagonal coefficient sequences enjoy nice arithmetic and asymptotic properties, and the field of analytic combinatorics in several variables (ACSV) makes it possible to compute asymptotic expansions. We consider these methods from the point of view of effectivity. In particular, given a rational function, ACSV requires one to determine a (generically) finite collection of points that are called critical and minimal. Criticality is an algebraic condition, meaning it is well treated by classical methods in computer algebra, while minimality is a semi-algebraic condition describing points on the boundary of the domain of convergence of a multivariate power series. We show how to obtain dominant asymptotics for the diagonal coefficient sequence of multivariate rational functions under some genericity assumptions using symbolic-numeric techniques. To our knowledge, this is the first completely automatic treatment and complexity analysis for the asymptotic enumeration of rational functions in an arbitrary number of variables.

5. Asymptotics of Bivariate Generating Functions with Algebraic Singularities by Torin Greenwood. Journal of Combinatorial Theory Series A, Volume 153, 2018.
   Click here for abstract

   In this paper, we use the multivariate analytic techniques of Pemantle and Wilson to derive asymptotic formulae for the coefficients of a broad class of multivariate generat- ing functions with algebraic singularities. Then, we apply these results to a generating function encoding information about the stationary distributions of a graph coloring algorithm studied by Butler, Chung, Cummings, and Graham (2015). Historically, Flajolet and Odlyzko (1990) analyzed the coefficients of a class of univariate generating functions with algebraic singularities. These results have been extended to classes of multivariate generating functions by Gao and Richmond (1992) and Hwang (1996, 1998), in both cases by immediately reducing the multivariate case to the univariate case. Pemantle and Wilson (2013) outlined new multivariate analytic techniques and used them to analyze the coefficients of rational generating functions. These multivariate techniques are used here to analyze functions with algebraic singularities.

6. Analytic Combinatorics in Several Variables: Effective Asymptotics and Lattice Path Enumeration by Stephen Melczer. PhD thesis (ENS Lyon / UWaterloo), 259 pages, 2017.
   Click here for abstract

   We give a pedagogical introduction to the methods of ACSV from a computer algebra viewpoint, developing rigorous algorithms and giving the first complexity results in this area under conditions which are broadly satisfied. Furthermore, we give several new applications of ACSV to the enumeration of lattice walks restricted to certain regions. In addition to proving several open conjectures on the asymptotics of such walks, a detailed study of lattice walk models with weighted steps is undertaken.

7. Automatic asymptotics for coefficients of smooth, bivariate rational functions by Timothy DeVries, Joris van der Hoeven and Robin Pemantle. Online Journal of Analytic Combinatorics, Volume 6, 24 pages, 2012.
   Click here for abstract

   We consider a bivariate rational generating function $F(x,y) = P(x,y)/Q(x,y) = \sum_{r,s} a_{r,s} x^r y^s$ under the assumption that the complex algebraic curve on which $Q$ vanishes is smooth. Formulae for the asymptotics of the coefficients $a_{r,s}$ were derived by Pemantle and Wilson (2002). These formulae are in terms of algebraic and topological invariants of the pole variety, but up to now these invariants could be computed only under a minimality hypothesis, namely that the dominant saddle lies on the boundary of the domain of convergence. In the present paper, we give an effective method for computing the topological invariants, and hence the asymptotics of the values $a_{r,s}$, without the minimality assumption. This leads to a theoretically rigorous algorithm, whose implementation is in progress.

8. New software for computing asymptotics of multivariate generating functions by Alexander Raichev. ACM Communications in Computer Algebra 45, 183-185, 2011.
   Click here for abstract

   We introduce amgf, a new Sage software package for computing asymptotics of multivariate generating functions. It implements recent algorithms [note: this package is now built-in to Sage].

9. Asymptotics of coefficients of multivariate generating functions: improvements for multiple points by Alexander Raichev and Mark C. Wilson. Online Journal of Analytic Combinatorics, Number 6, 2011.
   Click here for abstract

   Let $F(x) = \sum_{\nu \in \mathbb{N}^d}F_\nu x^\nu$ be a multivariate power series with complex coefficients that converges in a neighborhood of the origin. Assume $F = G/H$ for some functions $G$ and $H$ holomorphic in a neighborhood of the origin. We derive asymptotics for the coefficients $F_{r\alpha}$ as $r\rightarrow\infty$ with $r\alpha \in \mathbb{N}^d$ for $alpha$ in a permissible subset of d-tuples of positive reals. More specifically, we give an algorithm for computing arbitrary terms of the asymptotic expansion for $F_{r\alpha}$ when the asymptotics are controlled by a transverse multiple point of the analytic variety $H = 0$. This improves upon earlier work by R. Pemantle and M. C. Wilson. We have implemented our algorithm in Sage and apply it to obtain accurate numerical results for several rational combinatorial generating functions.

10. Asymptotics of multivariate sequences, part III: Quadratic points by Yuliy Baryshnikov and Robin Pemantle. Advances in Mathematics 228, 3127-3206, 2011.
    Click here for abstract

    We consider a number of combinatorial problems in which rational generating functions may be obtained, whose denominators have factors with certain singularities. Specifically, there exist cone points, near which one of the factors is asymptotic to a nondegenerate quadratic. We compute the asymptotics of the coefficients of such a generating function. The computation requires some topological deformations as well as Fourier-Laplace transforms of generalized functions. We apply the results of the theory to specific combinatorial problems. This deals with another case in the original taxonomy outlined in the first paper of Pemantle and Wilson. Note: original title was 'Tilings, groves and multiset permutations: asymptotics of rational generating functions whose pole set includes a cone'

11. Analytic combinatorics in $d$ variables: An overview by Robin Pemantle. AMS Contemporary Mathematics 520, 2010.
    Click here for abstract

    Let $F(\mathbf{Z}) = \sum a_\mathbf{r} \mathbf{Z}^\mathbf{r}$ be a rational generating function in the $d$ variables $Z_1,\dots, Z_d$. Asymptotic formulae for the coefficients $a_\mathbf{r}$ may be obtained via Cauchy’s integral formula in $\mathbb{C}^d$. Evaluation of this integral is not as straightforward as it is in the univariate case. This paper discusses geometric techniques that are needed for evaluation of these integrals and surveys classes of functions for which these techniques lead to explicit and effectively computable asymptotic formulae.

12. A case study in bivariate singularity analysis by Timothy Devries. AMS Contemporary Mathematics 520, 2010.
    Click here for abstract

    The multivariate singularity analysis of Pemantle and Wilson is explored and then used to derive an asymptotic expression for the number of bicolored supertrees, realized as the diagonal sequence of a bivariate rational function $F$. These asymptotics have been obtained previously by univariate methods, but the analysis contained herein serves as a case study for the general multivariate method. The analysis itself relies heavily on the structure of a height function $h$ along the pole set $V$ of $F$. What makes this example interesting is the geometry of $h$ on $V$, namely that h has a degenerate saddle point away from the boundary of the domain of analyticity of F that contributes to the asymptotic analysis. Due to the geometry of h at this point, the coefficient analysis can not be computed directly from the standard formulas of multivariate singularity analysis. Performing the analysis in this case represents a first step towards understanding general cases of this geometric type.

13. Asymptotic expansions of oscillatory integrals with complex phase by Robin Pemantle and Mark C. Wilson. AMS Contemporary Mathematics 520, 2010.
    Click here for abstract

    We consider saddle point integrals in d variables whose phase functions are neither real nor purely imaginary. Results analogous to those for Laplace (real phase) and Fourier (imaginary phase) integrals hold whenever the phase function is analytic and nondegenerate. These results generalize what is well known for integrals of Laplace and Fourier type. The proofs are via contour shifting in complex d-space. This work is motivated by applications to asymptotic enumeration.

14. Asymptotics of coefficients of multivariate generating functions: improvements for smooth points by Alexander Raichev and Mark C. Wilson. Electron. J. Combin. 15, no. 1, Research Paper 89, 17 pp, 2008.
    Click here for abstract

    We improve over the first paper by Pemantle and Wilson, and derive explicit formulae for the entire asymptotic series obtained by analysis near a smooth point of the singular variety. The numerical results obtained show how well these approximations work in practice.

15. A new method for computing asymptotics of diagonal coefficients of multivariate generating functions by Alexander Raichev and Mark C. Wilson. Proceedings of International Conference on Analysis of Algorithms, Juan-les-Pins, 2007.
    Click here for abstract

    Let $\sum_{\mathbf{n}\in\mathbb{N}^d} f_{\mathbf{n}}\mathbf{x}^{\mathbf{n}}$ be a multivariate generating function that converges in a neighborhood of the origin of $\mathbb{C}^d$. We present a new, multivariate method for computing the asymptotics of the diagonal coefficients $f_{a_1n,\dots,a_dn}$ and show its superiority over the standard, univariate diagonal method.

16. Uniform formulae for coefficients of meromorphic functions in two variables. Part I by Manuel Lladser. SIAM Journal on Discrete Mathematics 20 (2007), 811-828.
    Click here for abstract

    This paper derives uniform asymptotics in the smooth bivariate case when the directions in question are such that there is no phase change in the underlying Fourier-Laplace integral. This generalizes results in the first Pemantle-Wilson paper.

17. Mixed powers of generating functions by Manuel Lladser. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, Discrete Mathematics and Theoretical Computer Science Proceedings, AG, 171-182, 2006.
    Click here for abstract

    This paper derives uniform asymptotics for a multivariate generalization of Riordan arrays, namely a GF of the form $\prod_j(1-w_jf_j(z))^{-1}$. In other words we seek the asymptotics of $[z^{n_0}]\prod_jf_j(z)^{n_j}$ as at least one of the exponents $n_j$ tends to infinity. This generalizes several results in the literature. Once again reduction to Fourier-Laplace integral is the key step.

18. Asymptotics for generalized Riordan arrays by Mark C. Wilson. Proceedings of the 2005 International Conference on Analysis of Algorithms (Barcelona), Discrete Mathematics and Theoretical Computer Science, volume AD, 323-334, 2005.
    Click here for abstract

    This applies the results of papers below to derive bivariate asymptotics for the special case $F(x,y) = \phi(x)/(1-y\nu(x))$, which arises frequently in applications.

19. Asymptotics of multivariate sequences II: multiple points of the singular variety by Robin Pemantle and Mark C. Wilson. Combinatorics, Probability and Computing 13 (2004), 735-761.
    Click here for abstract

    In this article we deal with multiple points of $V$. Our results show that the central limit (Ornstein-Zernike) behavior typical of the smooth case does not hold in the multiple point case. For example, when $V$ has a multiple point singularity at $(1,\dots,1)$ rather than $a_{\mathbf{r}}$ decaying as $|\mathbf{r}|^{-1/2}$ as $|\mathbf{r}|\rightarrow\infty$, $ a_{\mathbf{r}}$ is very nearly polynomial in a cone of directions.

20. Asymptotic enumeration via singularity analysis by Manuel Lladser. PhD thesis, Ohio State University 2003.
    Click here for abstract

    Asymptotics for smooth points are computed in the above articles by Fourier-Laplace integrals, and are usually uniform for most sets of directions. However there can be directions where the asymptotic behaviour changes (for example, in 'Airy phenomena' where $ r^{-1/2} $ becomes $ r^{-1/3} $) and uniformity breaks down. The thesis studies such situations in detail in the two-dimensional case. It relies on the asymptotic analysis of a certain type of 'parameter-varying' F-L integral of the form $ \int \exp(-sP(d,x))A(d,x) dx $. The cases of interest are when either the phase term $P(d,x)$ or the amplitude term $A(d,x)$ exhibits a change of degree as $d$ approaches a degenerate direction. These are handled by a generalized version of the stationary phase and the coalescing saddle point method. Uniform expansions and local limit results are obtained.

21. Asymptotics of multivariate sequences I: smooth points of the singular variety by Robin Pemantle and Mark C. Wilson, Journal of Combinatorial Theory A 97 (2002), 129-161.
    Click here for abstract

    This article treats the case of smooth points of $V$. It includes a detailed introduction to the project, discusses previous work on the topic and lays the groundwork for further papers by devising a taxonomy. Then it treats the most commonly occurring case, smooth points. Companion papers will treat points of $V$ where the local geometry is more complicated, and for which other methods of analysis are not known. Note: the published version (reprints are available) contains many errors, several the fault of the publisher. In particular, in Thm 3.5 there should be a minus sign in the denominator of the expression for the constant $C_0$.

22. Generating functions with high-order poles are nearly polynomial by Robin Pemantle. Mathematics and computer science (Versailles, 2000), 305–321. Trends in Mathematics, Birkhauser, Basel, 2000.
    Click here for abstract

    Explains why our multivariate asymptotic expansions sometimes have only finitely many terms, and hence are effectively computable.