Applications of ACSV

The following papers apply the results of ACSV to different problems.

• Asymptotics of coefficients of algebraic series via embedding into rational series Torin Greenwood, Stephen Melczer, Tiadora Ruza, and Mark C. Wilson. Submitted, 2021. Supplement – Sage code – Sage in static HTML.
  Click here for abstract

  We present a strategy for computing asymptotics of coefficients of d-variate algebraic generating functions. Using known constructions, we embed the coefficient array into an array represented by a rational generating functions in d+1 variables, and then apply ACSV theory to analyse the latter. This method allows us to give systematic results in the multivariate case, seems more promising than trying to derive analogs of the rational ACSV theory for algebraic GFs, and gives the prospect of further improvements as embedding methods are studied in more detail.

• Multivariate Analytic Combinatorics for Cost Constrained Channels and Subsequence Enumeration Andreas Lenz, Stephen Melczer, Cyrus Rashtchian, Paul H. Siegel. Submitted, 2021.
  Click here for abstract

  Analytic combinatorics in several variables is a powerful tool for deriving the asymptotic behavior of combinatorial quantities by analyzing multivariate generating functions. We study information-theoretic questions about sequences in a discrete noiseless channel under cost and forbidden substring constraints. Our main contributions involve the relationship between the graph structure of the channel and the singularities of the bivariate generating function whose coefficients are the number of sequences satisfying the constraints. We combine these new results with methods from multivariate analytic combinatorics to solve questions in many application areas. For example, we determine the optimal coded synthesis rate for DNA data storage when the synthesis supersequence is any periodic string. This follows from a precise characterization of the number of subsequences of an arbitrary periodic strings. Along the way, we provide a new proof of the equivalence of the combinatorial and probabilistic definitions of the cost-constrained capacity, and we show that the cost-constrained channel capacity is determined by a cost-dependent singularity, generalizing Shannon's classical result for unconstrained capacity.

• Asymptotic Enumeration of Lonesum Matrices Jessica Khera, Erik Lundberg, and Stephen Melczer. Advances in Applied Mathematics, Volume 123, 102–118, 2021.
  Click here for abstract

  We provide bivariate asymptotics for the poly-Bernoulli numbers, a combinatorial array that enumerates lonesum matrices, using the methods of Analytic Combinatorics in Several Variables (ACSV). For the diagonal asymptotic (i.e., for the special case of square lonesum matrices) we present an alternative proof based on Parseval's identity. In addition, we provide an application in Algebraic Statistics on the asymptotic ML-degree of the bivariate multinomial missing data problem, and strengthen an existing result on asymptotic enumeration of permutations having a specified excedance set.

• Counting walks with large steps in an orthant Alin Bostan, Mireille Bousquet-Mélou, and Stephen Melczer. Journal of the European Mathematical Society, Volume 23 (7), 2221–2297, 2021.
  Click here for abstract

  In the past fifteen years, the enumeration of lattice walks with steps taken in a prescribed set S and confined to a given cone, especially the first quadrant of the plane, has been intensely studied. As a result, the generating functions of quadrant walks are now well-understood, provided the allowed steps are small, that is S in ${−1,0,1}^2$. In particular, having small steps is crucial for the definition of a certain group of bi-rational transformations of the plane. It has been proved that this group is finite if and only if the corresponding generating function is D-finite (that is, it satisfies a linear differential equation with polynomial coefficients). This group is also the key to the uniform solution of 19 of the 23 small step models possessing a finite group. In contrast, almost nothing is known for walks with arbitrary steps. In this paper, we extend the definition of the group, or rather of the associated orbit, to this general case, and generalize the above uniform solution of small step models. When this approach works, it invariably yields a D-finite generating function. We apply it to many quadrant problems, including some infinite families. After developing the general theory, we consider the 13 110 two-dimensional models with steps in ${−2,−1,0,1}^2$ having at least one −2 coordinate. We prove that only 240 of them have a finite orbit, and solve 231 of them with our method. The 9 remaining models are the counterparts of the 4 models of the small step case that resist the uniform solution method (and which are known to have an algebraic generating function). We conjecture D-finiteness for their generating functions, but only two of them are likely to be algebraic. We also prove non-D-finiteness for the 12 870 models with an infinite orbit, except for 16 of them.

• Higher Dimensional Lattice Walks: Connecting Combinatorial and Analytic Behavior by Stephen Melczer and Mark C. Wilson. SIAM Journal on Discrete Mathematics, Volume 33(4), 2140–2174, 2019.
  Click here for abstract

  We consider the enumeration of walks on the non-negative lattice $\mathbb{N}^d$, with steps defined by a set $S\subset\{-1,0,1\}^d - \{0\}$. Previous work in this area has established asymptotics for the number of walks in certain families of models by applying the techniques of analytic combinatorics in several variables (ACSV), where one encodes the generating function of a lattice path model as the diagonal of a multivariate rational function. Melczer and Mishna obtained asymptotics when the set of steps $S$ is symmetric over every axis; in this setting one can always apply the methods of ACSV to a multivariate rational function whose whose set of singularities is a smooth manifold (the simplest case). Here we go further, providing asymptotics for models with generating functions that must be encoded by multivariate rational functions with non-smooth singular sets. In the process, our analysis connects past work to deeper structural results in the theory of analytic combinatorics in several variables. One application is a closed form for asymptotics of models defined by step sets which are symmetric over all but one axis. As a special case, we apply our results when $d=2$ to give a rigorous proof of asymptotics conjectured by Bostan and Kauers; asymptotics for walks returning to boundary axes and the origin are also given.

• Quiver Asymptotics: $\mathcal{N}=1$ Free Chiral Ring Sanjaye Ramgoolam, Mark C. Wilson and Ali Zahabi. Journal of Physics A: Mathematical and Theoretical 53 (10), 105401, 2020
  Click here for abstract

  The large $N$ generating functions for the counting of chiral operators in $\mathcal{N}=1$, four-dimensional quiver gauge theories have previously been obtained in terms of the weighted adjacency matrix of the quiver diagram. We introduce the methods of multi-variate asymptotic analysis to study this counting in the limit of large charges. We describe a Hagedorn phase transition associated with this asymptotics, which refines and generalizes known results on the 2-matrix harmonic oscillator. Explicit results are obtained for two infinite classes of quiver theories, namely the generalized clover quivers and affine $\mathbb{C}^3/\tilde{A}_n$ orbifold quivers.

• Asymptotic lattice path enumeration using diagonals Stephen Melczer and Marni Mishna. Algorithmica 75, 782-811, 2016.
  Click here for abstract

  Uses the smooth point theory to deal with highly symmetric walks confined to the positive orthant.

• Diagonal asymptotics for products of combinatorial classes Mark C. Wilson. Combinatorics, Probability and Computing 24, 354-372, 2015 (Flajolet memorial issue).
  Click here for abstract

  We generalize and improve recent results by B\'{o}na and Knopfmacher and by Banderier and Hitczenko concerning the joint distribution of the sum and number of parts in tuples of restricted compositions. Specifically, we generalize the problem to general combinatorial classes and relax the requirement that the sizes of the compositions be equal. We extend the main explicit results to enumeration problems whose counting sequences are Riordan arrays. In this framework, we give an alternative method for computing asymptotics in the supercritical case, which avoids explicit diagonal extraction and seems likely to be computationally more efficient.

• Quantum random walks on the integer lattice via generating functions Andrew Bressler. PhD thesis, U. Penn., 2009.
  Click here for abstract

  This thesis contains several early results from the papers below. It also includes exact asymptotics for a three-chirality walk on the line and the 2-D Hadamard walk, as well as a proof of Airy phenomena for the two-chirality walk. It concludes with a preliminary discussion of higher dimensions.

• Random walk on the integer lattice: examples and phenomena Andrew Bressler, Torin Greenwood, Robin Pemantle, and Marko Petkovsek, Contemporary Mathematics Volume 520, 2010.
  Click here for abstract

  We apply results from the previous 2-D QRW paper to compute limiting probability profiles for various quantum random walks in one and two dimensions. Using analytic machinery we show some features of the limit distribution that are not evident in an empirical intensity plot of the time 10,000 distribution. Some conjectures are stated and computational techniques are discussed as well.

• Two-dimensional quantum random walk Yuliy Baryshnikov, Wil Brady, Andrew Bressler, and Robin Pemantle. Journal of Statistical Physics 142 (2011), 78-107.
  Click here for abstract

  We analyze several families of two-dimensional quantum random walks. The feasible region (the region where probabilities do not decay exponentially with time) grows linearly with time, as is the case with one-dimensional QRW. The limiting shape of the feasible region is, however, quite different. The limit region turns out to be an algebraic set, which we characterize as the rational image of a compact algebraic variety. We also compute the probability profile within the limit region, which is essentially a negative power of the Gaussian curvature of the same algebraic variety. Our methods are based on analysis of the space-time generating function, following the methods of the first paper of Pemantle and Wilson. Some extensions to toral singularities are required.

• Quantum random walks in one dimension via generating functions Andrew Bressler and Robin Pemantle. Proceedings of International Conference on Analysis of Algorithms, Juan-les-Pins, 2007.

• Quantum random walks on $\mathbb{Z}^2$ Wil Brady. MS thesis, U. Penn., 2007.
  Click here for abstract

  This thesis computes the asymptotic probability profile for nearest-neighbor quantum random walks in the two-dimensional integer lattice with various quantum coins (4x4 unitary matrices). A shape theorem is proved for the Hadamard coin (the standard choice). Analogous results for other coins, exhibiting an unexpectedly wide range of visual phenomena, are verified numerically but not proved. The numeric finite-time profiles are compared to pictures of the theoretically computed range of non-exponential decay. The shapes are indeed the same. Furthermore, plots of the normalized probabilities in the non-exponential region turn out to have internal structure that is mirrored in the rendering of the theoretically predicted non-exponential decay region via point plotting. This has led to followup work showing why both of these are essentially the same as a plot of the push-forward via the Gauss map of the surface measure on the toral part of the pole variety.

Applications of ACSV by others

This is a partial list – further applications can be found by searching Google Scholar. For instance, see Citations to Pemantle and Wilson 2002 | Citations to 2013 book | Citations to 2021 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.