ACSV Project
Home Textbook
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.
Upcoming events related to this project
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.
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
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
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.
Asymptotics of multivariate sequences in the presence of a lacuna by Yuliy Baryshnikov, Stephen Melczer and Robin Pemantle. Under review 2021.
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.
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.
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.
Analytic Combinatorics: A Multidimensional Approach by Marni Mishna. Discrete Mathematics and its Applications, CRC Press.
Asymptotics of Bivariate Generating Functions with Algebraic Singularities by Torin Greenwood. J. Combinatorial Theory A, 2018.
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.
Analytic Combinatorics in Several Variables: Effective Asymptotics and Lattice Path Enumeration by Stephen Melczer. PhD thesis (Waterloo/Lyon), 259 pages, 2017.
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.
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).
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.
New software for computing asymptotics of multivariate generating functions by Alexander Raichev. ACM Communications in Computer Algebra 45 (2011), 183-185.
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].
Asymptotics of coefficients of multivariate generating functions: improvements for smooth points by Alexander Raichev and Mark C. Wilson. Online Journal of Analytic Combinatorics, 2011.
Let $\sum_{\beta \in N^d} F_\beta x^\beta$ be a multivariate power series. For example this could be a generating function for a combinatorial class. Assume that in a neighbourhood of the origin this series represents a nonentire function $F=G/H^p$ where $G$ and $H$ are holomorphic and $p$ is a positive integer. Given a direction $\alpha \in \mathbb{N}^d$ for which the asymptotics are controlled by a smooth point of the singular variety $H=0$, we compute the asymptotics of $F_{n\alpha}$ as $n\rightarrow\infty$. We do this via multivariate singularity analysis and give an explicit formula for the full asymptotic expansion. This improves on earlier work of R. Pemantle and the second author and allows for more accurate numerical approximation, as demonstrated by our examples.
Analytic combinatorics in $d$ variables: An overview by Robin Pemantle. AMS Contemporary Mathematics 520, 2010.
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.
A case study in bivariate singularity analysis by Timothy Devries. AMS Contemporary Mathematics 520, 2010.
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.
Asymptotic expansions of oscillatory integrals with complex phase by Robin Pemantle and Mark C. Wilson. AMS Contemporary Mathematics 520.
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.
Asymptotics of multivariate sequences, part III: Quadratic points by Yuliy Baryshnikov and Robin Pemantle. Advances in Mathematics 228 (2011), 3127-3206.
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'
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.
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.
Twenty combinatorial examples of asymptotics derived from multivariate generating functions by Robin Pemantle and Mark C. Wilson. SIAM Review 50 (2008), 199-272.
We illustrate the use of the techniques of some of the papers below, on a variety of problems of combinatorial interest. The survey begins by summarizing previous work on the asymptotics of univariate and multivariate generating functions. Next we describe the Morse-theoretic underpinnings of some new asymptotic techniques. We then quote and summarize these results in such a way that only elementary analyses are needed to check hypotheses and carry out computations. The remainder of the survey focuses on combinatorial applications, such as enumeration of words with forbidden substrings, edges and cycles in graphs, polyominoes, and descents in permutations. After the individual examples, we discuss three broad classes of examples, namely functions derived via the transfer matrix method, those derived via the kernel method, and those derived via the method of Lagrange inversion. These methods have the property that generating functions derived from them are amenable to our asymptotic analyses, and we describe further machinery that facilitates computations for these classes of examples.
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.
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.
Uniform formulae for coefficients of meromorphic functions in two variables. Part I by Manuel Lladser. SIAM Journal on Discrete Mathematics 20 (2007), 811-828.
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.
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.
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.
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).
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.
Convolutions of inverse linear functions via multivariate residues by Yuliy Baryshnikov and Robin Pemantle. Preprint (2004), 42 pages.
This uses stratified Morse theory to derive complete expansions when $V$ is a union of hyperplanes ($H$ is a product of linear factors). Such GFs occur often in queueing theory. It does not handle directions on the boundary of the cones mentioned below (Asymptotics of Multivariate Sequences, II). At present, each of these articles does something the other cannot.
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.
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.
Asymptotic enumeration via singularity analysis by Manuel Lladser. PhD thesis, Ohio State University 2003.
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.
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.
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$.
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.
Explains why our multivariate asymptotic expansions sometimes have only finitely many terms, and hence are effectively computable.
Papers using the basic theory in application areas
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.
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.
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.
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.
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.
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
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.
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).
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.
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.
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.
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.
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 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.