Robin Pemantle and I have written a book summarizing over a decade of research. The first draft sent to the publisher is available from the book website. We expect publication in 2013 and welcome feedback on this draft version.
Category Archives: AMS project
Asymptotic expansions of oscillatory integrals with complex phase
Robin Pemantle and I have just submitted this paper, which fills in some gaps from our previous work. There is still more to be done along these lines – asymptotics of integrals whose stationary points are not isolated or are at a vertex of a simplex, for example, requires more work.
Abstract: We consider saddle point integrals in d variables whose phase function is
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 method is via contour shifting in
complex d-space. This work is motivated by applications to asymptotic
enumeration.
Higher order asymptotics from generating functions
Alex Raichev and I have just submitted a journal article on this topic (read it on arXiv). The associated Maple 11 worksheets can be found on Alex’s site. We improve over previous work by Robin Pemantle and me, and derive explicit formulae for the entire asymptotic series obtained by approximating the coefficients of a generating function near a smooth point of the singular variety. The numerical results obtained show how well these approximations work in practice.
I heard a talk by Wojtek Szpankowski a few years ago where he quoted Ziv as saying that second order asymptotics were needed in information theory. Persi Diaconis told me years ago that the work with Robin is all very nice, but what about looking at approximations that work for moderately small values, not just asymptotic approximations. I hope that this paper will satisfy both needs.
A new method for computing asymptotics of diagonal coefficients of multivariate generating functions
Alexander Raichev and Mark C. Wilson, to appear in Proceedings of the International Conference on Analysis of Algorithms (Juan-les-Pins, June 2007).
Let $latex sum_{mathbf{n}inmathbb{N}^d} f_{mathbf{n}} mathbf{x}^mathbf{n}$ be a multivariate generating function that converges in a neighborhood of the origin of $latex mathbb{C}^d$. We present a new, multivariate method for computing the asymptotics of the diagonal coefficients $latex f_{a_1n,ldots,a_dn}$ and show its superiority over the standard, univariate diagonal method.
Note: there is a typo: in Example 3.6, we should have $latex c = ( (L-b)/a, (L-a)/b )$ where $latex L = sqrt{a^2 + b^2}$.
Twenty combinatorial examples of asymptotics derived from multivariate generating functions
Robin Pemantle and Mark C. Wilson, to appear in SIAM Review, June 2008.
Abstract: Let $latex F$ be a power series in at least two variables that defines a meromorphic function in a neighbourhood of the origin; for example, $latex F$ may be a rational multivariate generating function. We discuss recent results that allow the effective computation of asymptotic expansions for the coefficients of $latex F$, uniform in certain explicitly defined cones of directions.
The purpose of this article is to illustrate the use of these techniques on a variety of problems of combinatorial interest. The first part reviews the Morse-theoretic underpinnings of these techniques, and then summarizes the necessary results so that only elementary analyses are needed to check hypotheses and carry out computations. The remainder focuses on combinatorial applications. Specific examples deal with enumeration of words with forbidden substrings, edges and cycles in graphs, polyominoes, descents and solutions to integer equations. 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. Generating functions derived in these three ways are amenable to our asymptotic analyses, and we state some further general results that apply to these cases.
Asymptotics for generalized Riordan arrays
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).
Abstract: The machinery of Riordan arrays has been used recently by several authors. We show how meromorphic singularity analysis can be used to provide uniform bivariate asymptotic expansions, in the central regime, for a generalization of these arrays. We show how to do this systematically, for various descriptions of the array. Several examples from recent literature are given.
Asymptotics of multivariate sequences, part II: multiple points of the singular variety
Robin Pemantle and Mark C. Wilson, Combinatorics, Probability and Computing 13 (2004), 735-761.
Abstract: Let $latex F(mathbf{z})=sum_mathbf{r} a_mathbf{r}mathbf{z^r}$ be a multivariate generating function which is meromorphic in some neighborhood of the origin of $latex mathbb{C}^d$, and let $latex mathcal{V}$ be its set of singularities. Effective asymptotic expansions for the coefficients can be obtained by complex contour integration near points of $latex mathcal{V}$.
In the first article in this series, we treated the case of smooth points of $latex mathcal{V}$. In this article we deal with multiple points of $latex mathcal{V}$.
Asymptotics of multivariate sequences, part I: smooth points of the singular variety
Robin Pemantle and Mark C. Wilson, Journal of Combinatorial Theory Series A 97 (2002), 129-161.
Abstract: Given a multivariate generating function $latex F(z_1 , ldots , z_d) = sum a_{r_1 , ldots , r_d} z_1^{r_1} cdots z_d^{r_d}$, we determine asymptotics for the coefficients. Our approach is to use Cauchy’s integral formula near singular points of $latex F$, resulting in a tractable oscillating integral. This paper treats the case where the singular point of $latex F$ is a smooth point of a surface of poles. Companion papers will treat singular points of $latex F$ where the local geometry is more complicated, and for which other methods of analysis are not known.