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

• A workshop at the American Institute of Mathematics (AIM). Orginally scheduled for Summer 2021 and delayed by covid until Summer 2022.

# 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

• Analytic Combinatorics in Several Variables by Robin Pemantle and Mark C. Wilson. Cambridge University Press, 2013.

• Textbook containing the most complete and expansive treatment of the theory for researchers. Second edition with S. Melczer to come in 2022
• 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. More computational focus and less prerequisite knowledge of geometry and topology assumed.

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

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

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.

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.

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

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

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

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.

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

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

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

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

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.

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

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.

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.

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.

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

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

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.

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

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.

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.

## 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

• T. George. Grove arctic curves from periodic cluster modular transformations. International Mathematics Research Notices, Volume 2021(20), 2021.

• Jeffrey S. Geronimo, Hugo J. Woerdeman, and Chung Y. Wong. Spectral density functions of bivariable stable polynomials. Ramanujan Journal, Volume 56(1), 2021.

• Ofir Gordon, Yuval Filmus, Oren Salzman. Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds. Proceedings of the Fourteenth International Symposium on Combinatorial Search (SoCS2021), 2021.

• Etienne Granet, Fabian H. L. Essler. A systematic 1/c-expansion of form factor sums for dynamical correlations in the Lieb-Liniger model. SciPost Physics, Volume 9(6), 2020.

• Marni Mishna and Samuel Simon. The asymptotics of reflectable weighted walks in arbitrary dimension. Annals of Applied Mathematics, Volume 118, 2020.

• M. Kovacevic. Runlength-Limited Sequences and Shift-Correcting Codes: Asymptotic Analysis. IEEE Transactions on Information Theory 2019.

• R. Vidunas. Counting derangements and Nash equilibria. Annals of Combinatorics 2017.

• J. Pantone. The Asymptotic Number of Simple Singular Vector Tuples of a Cubical Tensor. Online Journal of Analytic Combinatorics, 2017.

• RF de Andrade, E Lundberg, B Nagle. Asymptotics of the extremal excedance set statistic. European Journal of Combinatorics 2015.

• A. Straub, W. Zudilin. Positivity of rational functions and their diagonals. Journal of Approximation Theory 2015.

• P Di Francesco, R Soto-Garrido. Arctic curves of the octahedron equation. Journal of Physics A 2014.

• I. Bena, M. Berkooz, J. de Boer, S. El-Showk, D. Scaling BPS solutions and pure-Higgs states. Journal of High Energy Physics 2012.

• Petersen, K. An adic dynamical system related to the Delannoy numbers. Ergodic Theory and Dynamical Systems 32 (2012), 809-823.

• M. Erickson, S. Fernando, K. Tran, Enumerating Rook and Queen Paths, Bulletin of the Institute for Combinatorics and Its Applications 60 (2010), 37–48.

• Noble, R. Asymptotics of a family of binomial sums. Journal of Number Theory 130 (2010), 2561-2585.

• Sahlmann, H. Entropy calculation for a toy black hole. Classical and Quantum Gravity, 200825 (5), art. no. 055004.

• Kong, Y. Asymptotics of the monomer-dimer model on two-dimensional semi-infinite lattices, Physical Review E 75, 051123 (2007) (13 pages).

• Kong, Y. Monomer-dimer model in two-dimensional rectangular lattices with fixed dimer density. Physical Review E 74, 061102 (2006) (15 pages).

• Corteel, S., Louchard, G., Pemantle, R. Common intervals in permutations. Discrete Mathematics and Theoretical Computer Science 8 (2006), pp. 189-214. Wormald, N. Tournaments with many Hamilton cycles. Preprint, 2001.

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