Analytic Combinatorics/Saddle-point Method

Theorem

Theorem due to Flajolet and Sedgewick.

If $F(z)$ is an admissible function then

$[z^n]F(z)\sim \frac{F(\zeta )}{{\zeta }^{n+1}\sqrt{2\pi f^{{\text{'}}^{\prime }}(\zeta )}}$ as $n\to \mathrm{\infty }$

where $\zeta$ is such that $F^{\text{'}}(\zeta )=0$ and $\frac{F(z)}{z^{n+1}}=e^{f(z)}$.

Proof

Proof due to Flajolet and Sedgewick.

By Cauchy's coefficient formula:

$[z^n]F(z)=\frac{1}{2\pi i}{\int }_C\frac{F(z)}{z^{n+1}}dz$

We can visualise this as a 3D graph whose $x$ and $y$ axes are the real and imaginary parts of $z$ respectively and the $z$ axis is the real part of $\frac{F(z)}{z^{n+1}}$.

For the generating functions we are interested in, $\frac{F(z)}{z^{n+1}}$ has a saddle-point on the positive real axis. This is the highest altitude of the green path in the above graph. Call this $\zeta$.

Being an analytic function (except at $z=0$), we can deform the contour to go through the saddle-point. The biggest contributor to the integral is made by the part of the contour near the saddle-point (call this $C_0$, which is the red part of the path in the graph below). The rest of the contour (call this $C_1$, the green part of the path) contributes relatively little.

$\frac{1}{2\pi i}{\int }_C\frac{F(z)}{z^{n+1}}dz=\frac{1}{2\pi i}{\int }_{C_0}\frac{F(z)}{z^{n+1}}dz+\frac{1}{2\pi i}{\int }_{C_1}\frac{F(z)}{z^{n+1}}dz$

In the below, we set $\frac{F(z)}{z^{n+1}}=e^{f(z)}$

$[z^n]F(z)=\frac{1}{2\pi i}{\int }_C\frac{F(z)}{z^{n+1}}dz=\frac{1}{2\pi i}{\int }_C{e}^{f(z)}dz$

We can deform the contour even more to make the part of the contour near the saddle-point a straight line (in the complex plane). $C_0$ is deformed to a straight, vertical line, perpendicular to the real axis, crossing the saddle-point, starting from $-ia$ to $ia$. $a$ is chosen such that $f^{{\text{'}}^{\prime }}(\zeta )a^2\to \mathrm{\infty }$ and $f^{{\text{'}}^{″}}(\zeta )a^3\to 0$ as $n\to \mathrm{\infty }$. This is so that the Taylor series expansion around $\zeta$

$f(z)=f(\zeta )+\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )(z-\zeta {)}^2+\frac{1}{6}{f}^{{\text{'}}^{″}}(\zeta )(z-\zeta {)}^3+\cdots$.

can be reduced to just $f(\zeta )+\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )(z-\zeta {)}^2$.

$f^{{\text{'}}^{\prime }}(\zeta )=\frac{F^{{\text{'}}^{\prime }}(\zeta )}{F(\zeta )}+\frac{n+1}{{\zeta }^2}$ is real-valued because $\zeta$ is real and $F(z)$, being a generating function, has real coefficients. $z=\zeta +ix$, so $(z-\zeta {)}^2=-x^2$ is real. Therefore, $\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )(z-\zeta {)}^2$ is real-valued.

So, any imaginary part of $f(z)$ can be moved outside the integral, leaving just a real-valued integrand:

$\frac{1}{2\pi i}{\int }_{C_0}\frac{F(z)}{z^{n+1}}dz=\frac{1}{2\pi i}{\int }_{C_0}{e}^{f(z)}dz\sim \frac{e^{f(\zeta )}}{2\pi i}{\int }_{C_0}{e}^{\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )(z-\zeta {)}^2}dz$

This also means that the real-valued surface we discussed in the beginning is a valid estimate of the potentially complex-valued $\frac{F(z)}{z^{n+1}}$.

$C_0:x\in [-a,a]\to ix+\zeta$

We change variables to remove the imaginary part of the interval and turn it into a real-valued integrand over the real line. Setting $g^{-1}(x)=\frac{x-\zeta }{i}$:

${\int }_{C_0}{e}^{\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )(z-\zeta {)}^2}dz={\int }_{-a}^a{e}^{\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )(ix+\zeta -\zeta {)}^2}idx=i{\int }_{-a}^a{e}^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )x^2}dx$

${\int }_{-a}^a{e}^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )x^2}dx={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}{e}^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )x^2}dx-2{\int }_a^{\mathrm{\infty }}{e}^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )x^2}dx$

Because $e^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )x^2}$ is very small for large $x$:

$\left|{\int }_a^{\mathrm{\infty }}{e}^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )x^2}dx\right|\le A{e}^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )a^2}$

Due to our choice of $a$ before, as $n\to \mathrm{\infty }$, $e^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )a^2}\to 0$.

Therefore, the integral can be estimated by a Gaussian integral which we know how to calculate:

${\int }_{-a}^a{e}^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )x^2}dx\sim {\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}{e}^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )x^2}dx=\sqrt{\frac{2\pi }{f^{{\text{'}}^{\prime }}(\zeta )}}$

Putting it all together:

$\frac{1}{2\pi i}{\int }_C\frac{F(z)}{z^{n+1}}dz\sim \frac{e^{f(\zeta )}}{2\pi i}{\int }_{C_0}{e}^{\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )(z-\zeta {)}^2}dz=\frac{e^{f(\zeta )}i}{2\pi i}{\int }_{-a}^a{e}^{-\frac{1}{2}{f}^{{\text{'}}^{\prime }}(\zeta )x^2}dx\sim \frac{e^{f(\zeta )}}{2\pi }\sqrt{\frac{2\pi }{f^{{\text{'}}^{\prime }}(\zeta )}}=\frac{F(\zeta )}{{\zeta }^{n+1}\sqrt{2\pi f^{{\text{'}}^{\prime }}(\zeta )}}$

Admissibility

This formalises the conditions under which we can apply the saddle-point method. Definition from Flajolet and Sedgewick and Wilf. Also known as Hayman-admissibility.

The function $F(z)$ is admissible if:

• $F(z)$ is a function with radius of convergence $R(0<R\le \mathrm{\infty })$
• There exists an $R_0<R$ such that $F(r)>0(R_0<r<R)$
• H₁: $\underset{r\to R}{lim}a(r)=+\mathrm{\infty }$ and $\underset{r\to R}{lim}b(r)=+\mathrm{\infty }$
• H₂: There exists a function $\delta (r)$ defined for $R_0<r<R$ such that $0<\delta (r)<\pi$ and as $r\to R$

$F(r{e}^{i\theta })\sim F(r)e^{i\theta a(r)-\frac{1}{2}{\theta }^{2}b(r)}$

uniformly for $|\theta |\le \delta (r)$

• H₃: Uniformly for $\delta (r)\le |\theta |\le \pi$ and as $r\to R$

$F(r{e}^{i\theta })=o\left(\frac{F(r)}{\sqrt{b(r)}}\right)$

Intuitive explanation

To find the coefficients of a function, we can use the Cauchy coefficient formula. This requires us to find the integral of a path in the complex plane. Imagine trying to estimate this integral, displayed as the red and green line below.

The biggest contribution to the integral comes from around the saddle-point (displayed in red) and the tail's contribution (displayed in green) is negligible (by H₃).

Therefore, to estimate the integral of the entire path you can estimate the integral of just the red part of the path. This is the asymptotic relation described in H₂.

Example

Example from Wilf and Flajolet and Sedgewick.

Say we want to estimate the coefficients of $e^z$:

1. $e^z$ has radius of convergence $+\mathrm{\infty }$ and is positive for all $z\ge 0$.
2. H₁: $a(z)=z\frac{(e^z{)}^{\prime }}{e^z}=z\frac{e^z}{e^z}=z$. Therefore, $\underset{z\to +\mathrm{\infty }}{lim}z=+\mathrm{\infty }$.
3. H₁: $b(z)=z^2\frac{d^2}{d{z}^2}\ln e^z+z\frac{d}{dz}\ln e^z=z^2\frac{d^{2}z}{d{z}^2}+z\frac{dz}{dz}=z$. Therefore, $\underset{z\to +\mathrm{\infty }}{lim}z=+\mathrm{\infty }$.
4. Find the saddle-point $\zeta$ by solving the equation $a(\zeta )=\zeta =n$. Therefore, $\zeta =n$ and the path of integration is the circle of radius $n$ centred at the origin.
5. Choose $\delta (n{e}^{i\theta })=n^{-\frac{2}{5}}$.
6. H₃: For $n^{-\frac{2}{5}}\le |\theta |\le \pi$ as $n\to +\mathrm{\infty }$

   $|e^{n{e}^{i\theta }}|=e^{n\cos \theta }\le e^{n\cos n^{-\frac{2}{5}}}=o\left(\frac{e^n}{\sqrt{n}}\right)$.

7. H₂: For $n<1e^{n{e}^{i\theta }}\sim e^{n+i\theta n-\frac{1}{2}{\theta }^{2}n}=e^n{e}^{i\theta n-\frac{1}{2}{\theta }^{2}n}$ (due to the power series expansion of $e^{i\theta }$).
8. Apply the theorem: $[z^n]e^z\sim \frac{e^n}{n^n\sqrt{2\pi n}}$.

Saddle-points of higher order

Theorem from Flajolet and Sedgewick.

The above assumes $F^{\prime }(\zeta )=0$ and $F^{″}(\zeta )\ne 0$. In the case where all derivatives up to the $p$th are zero but $F^{(p+1)}\ne 0$, we call it a saddle-point of order or multiplicity $p$.

If $F(z)$ has a saddle-point of order $p+1$:

$[z^n]F(z)\sim \frac{\omega }{p}\mathrm{\Gamma }\left(\frac{1}{p}\right)\frac{F(\zeta )}{{\zeta }^{(n+1)}\sqrt[p]{-f^{(p)}(\zeta )/p!}}$

where ${\omega }^p=1$.

References

• Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
• Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.