Analytic Combinatorics/Saddle-point Method

Theorem

Theorem due to Flajolet and Sedgewick.

If $F(z)$ is an admissible function (we will discuss what this means later) then

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

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

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$

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^{''}(\zeta )a^{2}\to \infty$ and $f^{'''}(\zeta )a^{3}\to 0$ as $n\to \infty$. This is so that the Taylor series expansion around $\zeta$

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

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

$f^{''}(\zeta )={\frac {F^{''}(\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^{''}(\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^{''}(\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^{''}(\zeta )(z-\zeta )^{2}}dz=\int _{-a}^{a}e^{{\frac {1}{2}}f^{''}(\zeta )(ix+\zeta -\zeta )^{2}}idx=i\int _{-a}^{a}e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx$

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

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

$\left|\int _{a}^{\infty }e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx\right|\leq Ae^{-{\frac {1}{2}}f^{''}(\zeta )a^{2}}$

Due to our choice of $a$ before, as $n\to \infty$, $e^{-{\frac {1}{2}}f^{''}(\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^{''}(\zeta )x^{2}}dx\sim \int _{-\infty }^{\infty }e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx={\sqrt {\frac {2\pi }{f^{''}(\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^{''}(\zeta )(z-\zeta )^{2}}dz={\frac {e^{f(\zeta )}i}{2\pi i}}\int _{-a}^{a}e^{-{\frac {1}{2}}f^{''}(\zeta )x^{2}}dx\sim {\frac {e^{f(\zeta )}}{2\pi }}{\sqrt {\frac {2\pi }{f^{''}(\zeta )}}}={\frac {F(\zeta )}{\zeta ^{n+1}{\sqrt {2\pi f^{''}(\zeta )}}}}$

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}{\sqrt {2\pi b(\zeta )}}}}$ as $n\to \infty$

where $b(z)=z^{2}{\frac {d^{2}}{dz^{2}}}\ln F(z)+z{\frac {d}{dz}}\ln F(z)$ and $\zeta$ is the solution to the equation $a(\zeta )=\zeta {\frac {F'(\zeta )}{F(\zeta )}}=n$.

Admissibility

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\quad (0<R\leq \infty )$
• There exists an $R_{0}<R$ such that $F(r)>0\quad (R_{0}<r<R)$
• H₁: $\lim _{r\to R}a(r)=+\infty$ and $\lim _{r\to R}b(r)=+\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(re^{i\theta })\sim F(r)e^{i\theta a(r)-{\frac {1}{2}}\theta ^{2}b(r)}$

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

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

$F(re^{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₂.

Proof

Proof due to Flajolet and Sedgewick

By Cauchy's coefficient formula

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

Converting to polar form $z=re^{i\theta }$ so we can apply our admissibility conditions

${\frac {1}{2\pi i}}\int _{C}F(z){\frac {dz}{z^{n+1}}}={\frac {1}{r^{n}2\pi }}\int _{-\pi }^{\pi }F(re^{i\theta })e^{-ni\theta }d\theta$

Split the integral into a central approximation crossing the saddle-point and a tail

$\int _{-\pi }^{\pi }F(re^{i\theta })e^{-ni\theta }d\theta =\int _{-\theta _{0}}^{\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta +\int _{\theta _{0}}^{2\pi -\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta$

By H₃

$\int _{\theta _{0}}^{2\pi -\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta <\int _{\theta _{0}}^{2\pi -\theta _{0}}{\frac {F(\zeta )}{\sqrt {b(\zeta )}}}e^{-ni\theta }d\theta \leq 2\pi \zeta {\frac {F(\zeta )}{\sqrt {b(\zeta )}}}$

therefore

$\int _{\theta _{0}}^{2\pi -\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta =o\left({\frac {F(\zeta )}{\sqrt {b(\zeta )}}}\right)$

and this allows us to ignore the tail in our estimate.

By H₂

$\int _{-\theta _{0}}^{\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta \sim F(\zeta )\int _{-\theta _{0}}^{\theta _{0}}e^{-\theta ^{2}b(\zeta )/2}d\theta$

because $a(\zeta )=n$ by assumption in the theorem.

Changing variables with $g(x)={\frac {x}{\sqrt {b(\zeta )}}}$

$\int _{-\theta _{0}}^{\theta _{0}}e^{-\theta ^{2}b(\zeta )/2}d\theta ={\frac {1}{\sqrt {b(\zeta )}}}\int _{-\theta _{0}{\sqrt {b(\zeta )}}}^{\theta _{0}{\sqrt {b(\zeta )}}}e^{-t^{2}/2}dt\sim {\frac {1}{\sqrt {b(\zeta )}}}\int _{-\infty }^{\infty }e^{-t^{2}/2}dt$

because ${\sqrt {b(\zeta )}}\to +\infty$ as $n\to +\infty$.

$\int _{-\infty }^{\infty }e^{-t^{2}/2}dt={\sqrt {2\pi }}$

Putting it all together

$[z^{n}]F(z)={\frac {1}{2\pi i}}\int _{C}F(z){\frac {dz}{z^{n+1}}}={\frac {1}{r^{n}2\pi }}\int _{-\pi }^{\pi }F(re^{i\theta })e^{-ni\theta }d\theta \sim {\frac {1}{\zeta ^{n}2\pi }}\int _{-\theta _{0}}^{\theta _{0}}F(\zeta e^{i\theta })e^{-ni\theta }d\theta \sim {\frac {F(\zeta )}{\zeta ^{n}2\pi }}\int _{-\theta _{0}}^{\theta _{0}}e^{-\theta ^{2}b(\zeta )/2}d\theta \sim {\frac {F(\zeta )}{\zeta ^{n}2\pi {\sqrt {b(\zeta )}}}}\int _{-\infty }^{\infty }e^{-t^{2}/2}dt={\frac {F(\zeta )}{\zeta ^{n}{\sqrt {2\pi b(\zeta )}}}}$

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 $+\infty$ and is positive for all $z\geq 0$.
2. H₁: $a(z)=z{\frac {(e^{z})'}{e^{z}}}=z{\frac {e^{z}}{e^{z}}}=z$. Therefore, $\lim _{z\to +\infty }z=+\infty$.
3. H₁: $b(z)=z^{2}{\frac {d^{2}}{dz^{2}}}\ln e^{z}+z{\frac {d}{dz}}\ln e^{z}=z^{2}{\frac {d^{2}z}{dz^{2}}}+z{\frac {dz}{dz}}=z$. Therefore, $\lim _{z\to +\infty }z=+\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$ centered at the origin.
5. Choose $\delta (ne^{i\theta })=n^{-{\frac {2}{5}}}$.
6. H₃: For $n^{-{\frac {2}{5}}}\leq |\theta |\leq \pi$ as $n\to +\infty$

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

7. H₂: For $n<1\quad e^{ne^{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.

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

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

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.
• Widder, David Vernon (1941). The Laplace Transform. Princeton University Press.