The Analytic Combinatorics in Several Variables Project

The aim of this project is to systematize (asymptotic) coefficient extraction from a wide class of naturally occurring multivariate generating functions. We aim to take a genuinely multivariate approach, and to improve over previous work in the areas of generality, ease of use, and suitability for effective computation. The topic is inherently interdisciplinary and uses complex analysis in one and several variables, asymptotics of integrals, topology, algebraic geometry, and symbolic computation. The application areas are many: we are particularly motivated by specific naturally occurring problems arising from areas such as multivariate recurrence relations, random tilings, queueing theory, and analysis of algorithms and data structures.

Our methods use complex analysis and oscillatory integrals to analyse singularities of explicitly known generating functions. We deal with generating functions of the form $F(\mathbf{z})=\sum a_{r_1,\dots,r_d}z_1^{r_1}\cdots z_d^{r_d}$ which can locally be expressed in the form $G/H$ for analytic functions $G$ and $H$. The singular set of this function (zero-set of $H$) plays a large role.

Publications in this Project

Publications are generally listed in reverse chronological order of production. Papers applying results of this project to other areas are listed below this section. Versions linked here are usually not the official published versions, but they are usually the latest prepublication versions held by the authors.

Main references

Publications concerning core theory of the project

  1. Stationary points at infinity for analytic combinatorics by Yuliy Baryshnikov, Stephen Melczer and Robin Pemantle. To appear in Foundations of Computational Mathematics.
    Click here for abstract

  2. Asymptotics of multivariate sequences in the presence of a lacuna by Yuliy Baryshnikov, Stephen Melczer and Robin Pemantle. Under review 2021.
    Click here for abstract

  3. 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

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

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

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

  7. Automatic asymptotics for coefficients of smooth, bivariate rational functions by Timothy DeVries, Joris van der Hoeven and Robin Pemantle. Online J. Anal. Comb., vol. 6, 24 pages (2012).
    Click here for abstract

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

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

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

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

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

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

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

  15. Twenty combinatorial examples of asymptotics derived from multivariate generating functions by Robin Pemantle and Mark C. Wilson. SIAM Review 50 (2008), 199-272.
    Click here for abstract

  16. 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

  17. 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

  18. 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

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

  20. Convolutions of inverse linear functions via multivariate residues by Yuliy Baryshnikov and Robin Pemantle. Preprint (2004), 42 pages.
    Click here for abstract

  21. 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

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

  23. 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

  24. 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

Papers using the basic theory in application areas

Applications of our work by others

We try to update this a few times a year to give an idea of the variety of applications. There are many more citations, some of which use the methods, while others only mention them. A full list can be found using Google Scholar, for example. Citations to Pemantle-Wilson 2002 | Citations to 2008 SIAM Review paper | Citations to 2013 book


Last updated December 14, 2021.
Maintained by S. Melczer and M. C. Wilson.