This post makes notes on residue theorem and its application, since most non-mathematicians only need to remember this after learning complex analysis. Some definitions may be not defined very rigorously from a complex analysis view.

Isolated Singularity

There are 3 kinds of isolated singularities for a single-valued function $f(z)$,

• removable singularities: The limit $\lim_{z\to c}f(z)$ exists.
  • The function becomes analytic at $c$ if we define $f(c)$ to be this limit.
  • The Laurent expansion about $c$ does not contain negative terms (terms with negative degree).
• poles: The limit $\lim_{z\to c}f(z) = \infty$.
  • The Laurent expansion about $c$ contains finitely many negative terms (i.e. finite principal part)
  • The order of pole $c$ is the integer $n$ s.t. $(z-c)^nf(z)$ is analytic and non-zero at $z$.
• essential singularities: $\lim_{z\to c}f(z)$ diverges.
  • The Laurent expansion about $c$ contains infinitely many negative terms.

Liouville’s theorem implies that any non-constant analytic function must have at least one pole or essential singularity.

Residue Theorem

The residue is the coefficient of $-1$ term of the Laurent expansion ($c\neq\infty$):

Let $U$ be a simply connected open set, $f$ be analytic in $U\setminus\{c_1,\ldots,c_m\}$ and continuous in $\bar{U}$, $C$ be the boundary of $U$ which is a closed rectifiable curve. Then,

If $c$ is a pole of order $m$, then the residue at $c$ is

Especially, when $m=1$:

Proof (sketch): Break $C$ into multiple loops that enclose a pole each. By the coefficient of Laurent expansion:

Another way to look at this is that $\frac{1}{z^n}$ is single-valued and goes to 0 along a loop. But $\ln z$ increases by $2\pi\mathrm{i}$.

Sum of Infinite Series

Suppose the target series to calculate is $\sum_{n=-\infty}^{\infty}{f(n)}$, with $f(n) = O(\frac{1}{n})$. Let $G(z) = \pi\cot{\pi z}$. Note that $G$ is analytic in $\mathbb{C}\setminus\mathbb{Z}$ and $\operatorname{res}G(n) = 1$ for all $n\in \mathbb{Z}$. Take curve $C_N$ be the square $[-N-\frac{1}{2}, N+\frac{1}{2}]\times[(-N-\frac{1}{2})\mathrm{i}, (N+\frac{1}{2})\mathrm{i}]$.

Theorem: If $f(z)$ has finitely many poles in $\mathbb{C}$ and analytic in the rest of the complex plane, then

Proof: $|\pi\cot{\pi z}| \leq 2\pi$ on the curve $C_N$.

Theorem: If $f(z)$ satisfies all conditions above and all poles $\{c_1, \ldots, c_m\}$ are non-integer, then

Proof: Take $N\to\infty$. For any $n\in\mathbb{Z}$,

Apply the theorem above.

Example:

Proof: We cannot use the theorem directly, but we have

Suppose the Laurent expansion of $\cot z$ at $z=0$ is

Then,

Thus,

Solve it and get

Substitute $- \frac{1}{3} \pi^2$ into the first equation for $[z^1 ] (\pi\cot{\pi z})$.

Asymptotics of Generating Functions

Principles of Coefficient Asymptotics: For $[ z^n]F(z) = A^n\theta(n)$

• The location of a function’s singularities dictates the exponential growth ($A^n$) of its coefficients.
• The nature of a function’s singularities determines the associate subexponential factor ($\theta(n)$).

Exponential Growth

Def: $\{a_n\}$ is of exponential order $K^n$ if for any $\epsilon>0$, $|a_n|$ exceeds $(K-\epsilon)^n$ infinitely often and is dominated by $(K+\epsilon)^n$ cofinitely.

This can be rephrased as $a_n = K^n\theta(n)$ where $\lim\sup |\theta(n)|^{1/n} = 1$.

Exponential Growth Formula: If the radius of convergence of the series $f_n = [z^n ]f(z)$ at 0 is $\mathrm{R_{conv}}(f; 0) = R$, then

Proof:

• By the definition of radius of convergence, $ | f_n |(R-\epsilon)^n\to 0$.
• If $ | f_n |(R+\epsilon)^n$ were bounded, then $ | f_n |(R+\frac{1}{2}\epsilon)^n$ would converge. So $ | f_n |(R+\epsilon)^n$ is unbounded.

Note: for a complex series $f(z)$, $R$ is the modulus of a singularity nearest to the origin.

Example: The EGF of the number of surjections (surjections from $[ n]$ to $[ m]$ for some $m$), and the EGF of the number of chains in Boolean lattice $B_n$, are

By the proposition, we have $\frac{r_n}{n!} \bowtie \frac{1}{(\ln 2)^{n}}$.

Saddle-point bound: Let $M(f; r) := \sup_{|z| = r}|f(z)|$ (the maximum modulus on a ring) for $r< R$. Then, for any $r\in (0,R)$, the family of saddle point bounds

If in addition $f(z)$ has non-negative coefficients, then

The best $r$ can be obtained by the zero derivative:

Proof:

By the coeffcients of Laurent expansion:

Example: Apply this to $[ z^n]e^z$ we have

Subexponential Factor

One can show that if singularities of $f(z)$ are polar, then $\theta(n)$ is a polynomial.

Def: If $f(z) = \frac{N(z)}{D(z)}$ with $N, D$ being polynomials, $f(z)$ is a rational function.

Coefficients of rational functions satisfy linear recurrence relations with constant coefficients:

Rational Function Case: If $f(z) = \frac{N(z)}{D(z)}$ is a rational function that is analytic at 0 and has poles at $a_1, \ldots, a_m$, then its coefficients are a sum of exponential–polynomials. That is, for $n$ larger than $n_0:= \mathrm{deg}(N) - \mathrm{deg}(D)$:

Furthermore, the degree of $P_j$ is equal to the order of the pole of $f$ at $a_j$ minus one.

Proof: Apply the partial fraction expansion:

where $Q$ is of degree $n_0$. Since

The binomial coefficient is a polynomial of degree $r − 1$ in $n$. Collect all terms.

Cor: If $f(z) = \frac{N(z)}{(z-a)^r}$ that has a single dominant pole $a$ with order $r$, then

This is a direct result of the theorem. (The book has a typo) For $r=1$, one can verifies:

Example: Fibonacci numbers have OGF $F(z) = \frac{z}{1 - z - z^2}$. The poles are $a_1 = - \varphi = -\frac{\sqrt{5}+1}{2}$ and $a_2 = \psi = \frac{\sqrt{5} - 1}{2}$. $\operatorname{res} F(\psi) = \frac{\sqrt{5} - 5}{10}$, $\operatorname{res} F(-\varphi) = \frac{-\sqrt{5} - 5}{10}$. Thus,

Actually,

Analytic Function Case: If $f(z)$ is analytic at $|z| \leq R$ except for poles $a_1, \ldots, a_m$. Then, there exist $m$ polynomials $P_j$ s.t.

Furthermore, the degree of $P_j$ is equal to the order of the pole of $f$ at $a_j$ minus one.

Proof: (The 1st one by the book)
Take the Laurant expansion of $f(z)$ at $a$:

where $S_a$ is the principal part and $H_a$ is the regular part. Note that $S_a$ is polynomial. Let $S = \sum_{j}S_{a_j}$. Observe that and $f-S$ is analytic for $|z| \leq R$. Then.

The coefficient of $S$ is obtained by the polynomial theorem. And, by saddle-point bound at $z=R$,

example: The EGF of the number of surjections $R(z) = \frac{1}{2 - e^z}$ has a dominant pole $a = \ln 2$ of order $1$. $\operatorname{res} R(a) = -\frac{1}{2}$. Thus,

References

• Wu Chongshi, Methods of Mathematical Physics, Peking University Press, 2003.
• Ph. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.