Analytic Combinatorics/Singularity Analysis

Introduction

This article explains how to estimate the coefficients of generating functions involving logarithms and roots.

You first may need to familiarise yourself with:

• Converting between Cartesian and polar coordinates
• Parameterising a curve

Theorems

Standard Function Scale

Theorem from Flajolet and Odlyzko.

If:

$f(z)=(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }$

where $\alpha \notin \{0,1,2,\cdots \},\gamma ,\delta \notin \{1,2,\cdots \}$ then:

$[z^{n}]f(z)\sim {\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }\quad ({\text{as }}n\to \infty )$

Singularity Analysis

Theorem from Flajolet and Sedgewick.

If $f(z)$ has a singularity at $\zeta$ and:

$f(z)\sim \left(1-{\frac {z}{\zeta }}\right)^{\alpha }\left({\frac {1}{\frac {z}{\zeta }}}\log {\frac {1}{1-{\frac {z}{\zeta }}}}\right)^{\gamma }\left({\frac {1}{\frac {z}{\zeta }}}\log \left({\frac {1}{\frac {z}{\zeta }}}\log {\frac {1}{1-{\frac {z}{\zeta }}}}\right)\right)^{\delta }\quad ({\text{as }}z\to \zeta )$

where $\alpha \notin \{0,1,2,\cdots \},\gamma ,\delta \notin \{1,2,\cdots \}$ then:

$[z^{n}]f(z)\sim \zeta ^{-n}{\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }\quad ({\text{as }}n\to \infty )$

The significance of the latter theorem is we only need an approximation of $f(z)$.

Branch points

Before going into the proof, I will explain what it is about roots and logarithms that mean we have to treat them differently to meromorphic functions.

Polar coordinates

Complex numbers can be expressed in two forms: Cartesian coordinates ($x+iy$) or polar coordinates $re^{i\theta }$, where $r$ is the distance from the origin or modulus and $\theta$ is the angle relative to the positive $x$ axis or argument.

For complex functions $f(z)$ of complex variables $z$ we can draw a 3-dimensional graph where the $x$ and $y$ axes are the real and imaginary components respectively of the $z$ variable and the $z$ axis is either the the modulus or the argument of the function $f(z)$.

For roots and logarithms, if we use the argument of the function for the $z$ axis, we see a discontinuity that restricts where we can draw the contour when we want to integrate the function.

The gap you can see along the negative $x$ axis is the discontinuity.

Root and logarithmic functions do not have poles about which we can do a Laurent expansion. Instead, we need to draw our contours to avoid these gaps or discontinuities. This is why in what follows we use contours with slits or wedges taken out of them.

Proof of standard function scale

Proof due to Sedgewick, Flajolet and Odlyzko

The proof for the estimate of the coefficient of the first term.

By Cauchy's coefficient formula

$[z^{n}](1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }={\frac {1}{2\pi i}}\int _{C}(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }{\frac {dz}{z^{n+1}}}$

where $C$ is a circle centred at the origin.

It is possible to deform $C$ without changing the value of the contour integral above.

We will deform $C$ by putting a slit through it along the real axis from 1 to $+\infty$.

We increase the radius of the circle to $\infty$, which reduces its contribution to the integrand to 0.

Therefore, the contour integration around $C$ above is equivalent to the contour integration around the contour which starts at $Re(+\infty )$, winds around 1 and ends at $Re(+\infty )$, which we will call ${H_{\frac {1}{n}}}$.

While we don't know much about the behaviour of the integral around the contour ${H_{\frac {1}{n}}}$, we do know about a similar contour $H_{1}$ (the Hankel contour) which winds around the origin at a distance of 1.

We can calculate the integral around ${H_{\frac {1}{n}}}$ by turning it into an integral around $H_{1}$. Formally:

$\int _{H_{\frac {1}{n}}}f(z)dz=\int _{\psi ^{-1}\circ H_{\frac {1}{n}}}f(\psi (\zeta ))\psi '(\zeta )d\zeta .$

Such that $\psi ^{-1}\circ H_{\frac {1}{n}}=H_{1}$.

Informally this means we want to find a function $\psi ^{-1}(t)$ which turns the contour ${H_{\frac {1}{n}}}$ into $H_{1}$. Geometrically, we move the contour to the left by 1 and multiply it by $n$:

$\psi ^{-1}(t)=n(t-1)$

But, we still want the integrand around $H_{1}$ to be equivalent to the integrand around ${H_{\frac {1}{n}}}$. We do this by dividing the variable by $n$ and adding 1:

$\psi (t)=1+{\frac {t}{n}}$

Therefore, we get the following substitution:

${\begin{aligned}{\frac {1}{2\pi i}}\int _{H_{\frac {1}{n}}}(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }{\frac {dz}{z^{n+1}}}&={\frac {1}{2\pi i}}\int _{\psi ^{-1}\circ H_{\frac {1}{n}}}(1-(1+{\frac {t}{n}}))^{\alpha }\left({\frac {1}{1+{\frac {t}{n}}}}\log {\frac {1}{1-(1+{\frac {t}{n}})}}\right)^{\gamma }\left({\frac {1}{1+{\frac {t}{n}}}}\log \left({\frac {1}{1+{\frac {t}{n}}}}\log {\frac {1}{1-(1+{\frac {t}{n}})}}\right)\right)^{\delta }{\frac {1}{n}}{\frac {dt}{(1+{\frac {t}{n}})^{n+1}}}\\&={\frac {n^{-a-1}}{2\pi i}}\int _{H_{1}}(-t)^{\alpha }\left(\log -{\frac {n}{t}}\right)^{\gamma }\left(\log \left({\frac {1}{1+{\frac {t}{n}}}}\log -{\frac {n}{t}}\right)\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\\&={\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }\int _{H_{1}}(-t)^{\alpha }\left(1-{\frac {\log(-t)}{\log n}}\right)^{\gamma }\left(\log \left({\frac {1}{1+{\frac {t}{n}}}}\log -{\frac {n}{t}}\right)\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\\&\sim {\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }\int _{H_{1}}(-t)^{\alpha }\left(\log \left({\frac {1}{1+{\frac {t}{n}}}}\log -{\frac {n}{t}}\right)\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\quad ({\text{as }}n\to \infty )\\&={\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }\int _{H_{1}}(-t)^{\alpha }\left(\log {\frac {1}{1+{\frac {t}{n}}}}+\log \log -{\frac {n}{t}}\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\\&\sim {\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }\int _{H_{1}}(-t)^{\alpha }\left(\log \log -{\frac {n}{t}}\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\quad ({\text{as }}n\to \infty )\\&={\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }(\log \log n)^{\delta }\int _{H_{1}}(-t)^{\alpha }\left(1-{\frac {\log \log(-t)}{\log \log n}}\right)^{\delta }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\\&\sim {\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }(\log \log n)^{\delta }\int _{H_{1}}(-t)^{\alpha }\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}dt\quad ({\text{as }}n\to \infty )\end{aligned}}$

We have:

$\left(1+{\frac {t}{n}}\right)^{-n-\gamma -\delta -1}\sim e^{-t}$ (as $n\to \infty$)

and:

${\frac {1}{2\pi i}}\int _{H_{1}}(-t)^{\alpha }e^{-t}dt={\frac {1}{\Gamma (-\alpha )}}$

Therefore,

${\frac {1}{2\pi i}}\int _{H_{1}}(-t)^{\alpha }\left(1+{\frac {t}{n}}\right)^{-n-1}dt\sim {\frac {1}{2\pi i}}\int _{H_{1}}(-t)^{\alpha }e^{-t}dt={\frac {1}{\Gamma (-\alpha )}}$

Putting it all together:

${\begin{aligned}[z^{n}](1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }&={\frac {1}{2\pi i}}\int _{C}(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }{\frac {dz}{z^{n+1}}}\\&={\frac {1}{2\pi i}}\int _{H_{\frac {1}{n}}}(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }{\frac {dz}{z^{n+1}}}\\&={\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }(\log \log n)^{\delta }\int _{H_{1}}(-t)^{\alpha }\left(1+{\frac {t}{n}}\right)^{-n-1}dt\\&\sim {\frac {n^{-a-1}}{2\pi i}}(\log n)^{\gamma }(\log \log n)^{\delta }\int _{H_{1}}(-t)^{\alpha }e^{-t}dt\\&={\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }\end{aligned}}$

Singularity Analysis

Explanation and example from Flajolet and Sedgewick.

In the below

$F(z)=(1-z)^{\alpha }\left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)^{\gamma }\left({\frac {1}{z}}\log \left({\frac {1}{z}}\log {\frac {1}{1-z}}\right)\right)^{\delta }\quad (\alpha \notin \{0,1,2,\ldots \},\gamma ,\delta \notin \{1,2,\ldots \})$

Little o

We will be making use of the "little o" notation.

$f(z)=o(g(z))$ as $z\to \zeta$

which means

$\lim _{z\to \zeta }{\frac {f(z)}{g(z)}}=0$

It also means for each $\epsilon >0$ there exists $\delta >0$ such that

$|z-\zeta |\leq \delta \implies f(z)\leq \epsilon g(z)$

a fact we will use in the proof.

It is also useful to note

$f(z)=g(z)+o(g(z))\iff f(z)\sim g(z)$

Summary

For the generating function $f(z)$:

1. Find $f(z)$'s singularity $\zeta$.
2. Construct the $\Delta$-domain at $\zeta$.
3. Check that $f(z)$ is analytic in the $\Delta$-domain.
4. Create an approximation of $f(z)$ near $\zeta$ of the form $f(z)=F\left({\frac {z}{\zeta }}\right)+o\left(F\left({\frac {z}{\zeta }}\right)\right)$.
5. The estimate of $[(z/\zeta )^{n}]f(z)\sim {\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }$ or equivalently $[z^{n}]f(z)\sim \zeta ^{-n}{\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }$.

Details

To find the singularity, find the value of $z$ for which the function equals $\infty$.

As an example, we will use $f(z)={\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}$.

It has a singularity at $z=1$, because

${\frac {e^{-3/4}}{\sqrt {1-1}}}={\frac {e^{-3/4}}{\sqrt {0}}}={\frac {e^{-3/4}}{0}}=\infty$

The $\Delta$-domain at 1 is a circle centred at the origin with radius $R$ with a triangle cut out of it with one vertex at 1 and edges of angles $\phi$ and $-\phi$. See image below. We use this domain as it allows us to make a proof later.

For $f(z)$ to be analytic in the $\Delta$-domain:

$f(z)=\sum _{n=0}^{\infty }a_{n}(z-z_{0})^{n}$

for all $z_{0}$ in the $\Delta$-domain.

Our example is analytic in the $\Delta$-domain because

• $e^{-z/2-z^{2}/4}$ is an entire function (i.e. has no singularities), which means it is analytic everywhere.
• ${\frac {1}{\sqrt {1-z}}}$ is analytic except for the slit along the real axis for $z\geq 1$.
• The product of two analytic functions is an analytic function on the same domain. Therefore, ${\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}$ is analytic on the entire complex domain, including the $\Delta$-domain, except for the real axis $z\geq 1$.

We want an approximation of the form $f(z)=F\left({\frac {z}{\zeta }}\right)+o\left(F\left({\frac {z}{\zeta }}\right)\right)\quad (z\to \zeta )$ (where in our example we set $\gamma ,\delta =0$ and $\zeta =1$).

Normally, this will be in the form of a Taylor series expansion.

For our example, doing the Taylor Expansion near to 1:

$e^{-z/2-z^{2}/4}=e^{-3/4}+e^{-3/4}(1-z)+{\frac {e^{-3/4}}{4}}(1-z)^{2}+\cdots$

${\frac {1}{\sqrt {1-z}}}={\frac {1}{\sqrt {1-z}}}$

${\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}={\frac {e^{-3/4}}{\sqrt {1-z}}}+e^{-3/4}{\sqrt {1-z}}+{\frac {e^{-3/4}}{4}}(1-z)^{\frac {3}{2}}+\cdots$

Therefore:

${\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}={\frac {e^{-3/4}}{\sqrt {1-z}}}+o({\frac {e^{-3/4}}{\sqrt {1-z}}})$

Then $[z^{n}]f(z)\sim {\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }$.

Therefore, in our example:

$[z^{n}]{\frac {e^{-z/2-z^{2}/4}}{\sqrt {1-z}}}\sim {\frac {e^{-3/4}}{\sqrt {\pi n}}}$

The proof of this comes from the fact that:

1. $[z^{n}]f(z)=\zeta ^{-n}[(z/\zeta ^{n}]f(z)$
2. $[(z/\zeta )^{n}]f(z)=[(z/\zeta )^{n}]F(z/\zeta )+[(z/\zeta )^{n}]o(F(z/\zeta ))$
3. the coefficients of the first term $[(z/\zeta )^{n}]F(z/\zeta )\sim {\frac {n^{-\alpha -1}}{\Gamma (-\alpha )}}(\log n)^{\gamma }(\log \log n)^{\delta }$, which we get from the standard function scale.
4. and the coefficients of the second term $[(z/\zeta )^{n}]o(F(z/\zeta ))=o\left(n^{-\alpha -1}(\log n)^{\gamma }(\log \log n)^{\delta }\right)$ which we do in #Proof of error term. This is also the reason why we need to use the $\Delta$-domain.

Proof of error term

Proof from Flajolet and Odlyzko, Flajolet and Sedgewick and Pemantle and Wilson.

We get the estimate of the coefficient for the second term from Cauchy's coefficient formula:

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

where $\gamma$ is any closed contour inside the $\Delta$-domain. See the red line in the image below.

We split $\gamma$ into four parts such that $\gamma =\gamma _{1}\cup \gamma _{2}\cup \gamma _{3}\cup \gamma _{4}$.

$\gamma _{1}=\{z\mid |z-1|={\frac {1}{n}},|arg(z-1)|\geq \phi \}$

$\gamma _{2}=\{z\mid |z-1|\geq {\frac {1}{n}},|z|\leq r,|arg(z-1)|=\phi \}$

$\gamma _{3}=\{z\mid |z|=r>1,|arg(z-1)|\geq \phi \}$

$\gamma _{4}=\{z\mid |z-1|\geq {\frac {1}{n}},|z|\leq r,|arg(z-1)|=-\phi \}$

${\frac {1}{2i\pi }}\int _{\gamma }o(F(z)){\frac {dz}{z^{n+1}}}={\frac {1}{2i\pi }}\int _{\gamma _{1}}o(F(z)){\frac {dz}{z^{n+1}}}+{\frac {1}{2i\pi }}\int _{\gamma _{2}}o(F(z)){\frac {dz}{z^{n+1}}}+{\frac {1}{2i\pi }}\int _{\gamma _{3}}o(F(z)){\frac {dz}{z^{n+1}}}+{\frac {1}{2i\pi }}\int _{\gamma _{4}}o(F(z)){\frac {dz}{z^{n+1}}}$

Contribution of $\gamma _{1}$:

The maximum of $F(z)$ on $\gamma _{1}$ is when $z=1-{\frac {1}{n}}$

$o(F(z))\leq \epsilon n^{-\alpha }(\log n)^{\gamma }(\log {\frac {1}{1-{\frac {1}{n}}}}+\log \log n)^{\delta }{\frac {1}{(1-{\frac {1}{n}})^{\gamma +\delta }}}\sim \epsilon n^{-\alpha }(\log n)^{\gamma }(\log \log n)^{\delta }\quad ({\text{as }}n\to \infty )$

The maximum of ${\frac {1}{z^{n+1}}}$ on $\gamma _{1}$ is

${\frac {1}{(1-{\frac {1}{n}})^{n+1}}}\leq 2e$

The maximum of $dz$ on $\gamma _{1}$ is ${\frac {2\pi }{n}}$

${\frac {1}{2i\pi }}\int _{\gamma _{1}}o(F(z)){\frac {dz}{z^{n+1}}}\leq \epsilon 2en^{-\alpha -1}(\log n)^{\gamma }(\log \log n)^{\delta }=o(n^{-\alpha -1}(\log n)^{\gamma }(\log \log n)^{\delta })$

Contribution of $\gamma _{2}$ and $\gamma _{4}$:

We parameterise the contour $\gamma _{2}$ by converting $z$ to polar form by $z=1+{\frac {t}{n}}e^{i\phi }$, so that $\gamma _{2}$ is a function of $t$ from $1$ to $En$. $E$ is the positive solution to the equation $|1+Ee^{i\phi }|=r$, so that the contour joins $\gamma _{3}$:

$\int _{\gamma _{2}}o(F(z)){\frac {dz}{z^{n+1}}}\leq \int _{1}^{En}|F(1+{\frac {t}{n}}e^{i\phi })|{\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}$

But, remember that the little o relation only holds within a particular $\delta$ of $1$. We know that ${\frac {\log ^{2}n}{n}}$ tends to zero as $n$ increases, and therefore, for any $\epsilon$, we choose an $n$ big enough so that ${\frac {\log ^{2}n}{n}}\leq \delta$. We split the integral above into two at $\log ^{2}n$, so that ${\frac {t}{n}}e^{i\phi }\leq \delta$:

$\int _{1}^{En}|F(1+{\frac {t}{n}}e^{i\phi })|{\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}=\int _{1}^{\log ^{2}n}\epsilon |F(1+{\frac {t}{n}}e^{i\phi })|{\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}+\int _{\log ^{2}n}^{En}F(1+{\frac {t}{n}}e^{i\phi }){\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}$

The first term in the sum:

${\begin{aligned}\int _{1}^{\log ^{2}n}\epsilon |F(1+{\frac {t}{n}}e^{i\phi })|{\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}&\leq {\frac {1}{2i\pi }}\int _{1}^{\infty }\epsilon |{\frac {t}{n}}e^{i\phi }|^{\alpha }|\log {\frac {n}{te^{i\phi }}}|^{\gamma }|\log({\frac {1}{1+{\frac {t}{n}}e^{i\phi }}}\log {\frac {n}{te^{i\phi }}})|^{\delta }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}{\frac {e^{i\phi }dt}{n}}\\&\leq {\frac {1}{2i\pi }}\epsilon \left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\int _{1}^{\infty }|t|^{\alpha }|\log({\frac {1}{1+{\frac {t}{n}}e^{i\phi }}}\log {\frac {n}{e^{i\phi }}})|^{\delta }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}dt\\&\sim {\frac {1}{2i\pi }}\epsilon \left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }\int _{1}^{\infty }|t|^{\alpha }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}dt\quad ({\text{as }}n\to \infty )\\\end{aligned}}$

$|1+{\frac {e^{i\phi }t}{n}}|\geq 1+Re({\frac {e^{i\phi }t}{n}})=1+{\frac {t\cos \phi }{n}}$ (where $Re(x)$ is the real part of x).

$\int _{1}^{\log ^{2}n}|t|^{\alpha }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}dt\leq \int _{1}^{\infty }|t|^{\alpha }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}dt\leq \int _{1}^{\infty }|t|^{\alpha }\left(1+{\frac {t\cos \phi }{n}}\right)^{-n-\gamma -\delta -1}dt\leq \int _{1}^{\infty }t^{a}e^{-t\cos \phi }dt\quad ({\text{as }}n\to \infty )$

This converges to a constant $L$. Therefore:

${\frac {1}{2i\pi }}\epsilon \left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }\int _{1}^{\infty }|t|^{\alpha }|1+{\frac {t}{n}}e^{i\phi }|^{-n-\gamma -\delta -1}dt={\frac {L}{2i\pi }}\epsilon \left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }=o(n^{-\alpha -1}(\log n)^{\gamma }(\log \log n)^{\delta })\quad (n\to \infty )$

The second term in the sum:

${\begin{aligned}\int _{\log ^{2}n}^{En}F(1+{\frac {t}{n}}e^{i\phi }){\frac {e^{i\phi }dt}{n(1+{\frac {t}{n}}e^{i\phi })^{n+1}}}&\leq {\frac {1}{2i\pi }}\left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }\int _{\log ^{2}n}^{En}|t|^{\alpha }\left(1+{\frac {\log ^{2}n\cos \phi }{n}}\right)^{-n-\gamma -\delta -1}dt\\&\leq {\frac {1}{2i\pi }}\left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }\int _{\log ^{2}n}^{En}|t|^{\alpha }e^{-\log ^{2}n\cos \phi }dt\\&\leq {\frac {1}{2i\pi }}\left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }{\frac {|En|^{\alpha }}{n^{\log n\cos \phi }}}En\end{aligned}}$

$n^{\log n\cos \phi }$ grows faster with $n$ than $|En|^{\alpha +1}$, so ${\frac {|En|^{\alpha +1}}{n^{\log n\cos \phi }}}\to 0$ as $n\to \infty$. Therefore:

${\frac {1}{2i\pi }}\left({\frac {e^{i\phi }}{n}}\right)^{\alpha +1}\left(\log {\frac {n}{e^{i\phi }}}\right)^{\gamma }\left(\log \log {\frac {n}{e^{i\phi }}}\right)^{\delta }{\frac {|En|^{\alpha +1}}{n^{\log n\cos \phi }}}=o(n^{-\alpha -1}(\log n)^{\gamma }(\log \log n)^{\delta })\quad (n\to \infty )$

A similar argument applies to $\gamma _{4}$.

Contribution of $\gamma _{3}$:

By Cauchy's inequality

${\frac {1}{2i\pi }}\int _{\gamma _{3}}o(F(z)){\frac {dz}{z^{n+1}}}\leq {\frac {\max _{|z|=r}F(z)}{r^{n}}}$

meaning the contribution of the integral around $\gamma _{3}$ is exponentially small as $n\to \infty$ and can be discarded.

Formula for multiple singularities

The above assumes only one singularity $\zeta$. But, it can be generalised for functions with multiple singularities.

In the case of multiple singularities, the separate contributions from each of the singularities, as given by the basic singularity analysis process, are to be added up.

—Flajolet and Sedgewick 2009, pp. 398.

Theorem from Flajolet and Sedgewick.

If $f(z)$ is analytic on the disc $|z|<\rho$, has a finite number of singularities on the circle $|z|=\rho$ and $f(z)$ is analytic on the $\Delta$-domain with multiple indents at each singularity.

If for each singularity $\zeta _{i}$ (for $i=1,2,\cdots ,r$):

$f(z)\sim \left(1-{\frac {z}{\zeta _{i}}}\right)^{\alpha _{i}}\left({\frac {1}{\frac {z}{\zeta _{i}}}}\log {\frac {1}{1-{\frac {z}{\zeta _{i}}}}}\right)^{\gamma _{i}}\left({\frac {1}{\frac {z}{\zeta _{i}}}}\log \left({\frac {1}{\frac {z}{\zeta _{i}}}}\log {\frac {1}{1-{\frac {z}{\zeta _{i}}}}}\right)\right)^{\delta _{i}}\quad ({\text{as }}z\to \zeta _{i})$

then:

$[z^{n}]f(z)\sim \sum _{i=0}^{r}\zeta _{i}^{n}{\frac {n^{-{\alpha _{i}}-1}}{\Gamma (-{\alpha _{i}})}}(\log n)^{\gamma _{i}}(\log \log n)^{\delta _{i}}\quad ({\text{as }}n\to \infty )$

References

• Flajolet, Philippe; Odlyzko, Andrew (1990). "Singularity analysis of generating functions" (PDF). SIAM Journal on Discrete Mathematics. 1990 (3).
• Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
• Lang, Serge (1999). Complex Analysis (4th ed.). Springer Science+Business Media, LLC.
• Lorenz, Dirk (2011). "Substitution and integration by parts for functions of a complex variable". Retrieved 27 November 2022.
• Pemantle, Robin; Wilson, Mark C. (2013). Analytic Combinatorics in Several Variables (PDF). Cambridge University Press.
• Sedgewick, Robert. "6. Singularity Analysis" (PDF). Retrieved 13 November 2022.
• Stroud, K. A. (2003). Advanced Engineering Mathematics (4th ed.). Palgrave Macmillan.