Analytic Combinatorics/Cauchy-Hadamard theorem

In analytic combinatorics we start with a generating function and we want to understand the behaviour of its ${\displaystyle n}$th coefficient as ${\displaystyle n}$ gets very large.

We first present coefficients as a sequence and discuss the properties of sequences that we want to know, namely its limit superior.

We then present power series representations of our generating function and the concept of convergence.

Finally, we present the Cauchy-Hadamard theorem which shows that the convergence of a power series is directly related to the limit superior of the sequence of its coefficients.

This gives us our first asymptotic estimate of coefficients.

One key concept in analysis is a sequence of numbers. In our case, the sequence of numbers we are interested in are the coefficients of the generating function we are studying. For example, if the generating function is ${\displaystyle a_{0}+a_{1}z+a_{2}z^{2}+\cdots }$ then the sequence is ${\displaystyle (a_{0},a_{1},a_{2},\cdots )}$, often written as ${\displaystyle (a_{n})}$.

A point of accumulation (or cluster point) of a sequence is a number ${\displaystyle t}$ such that, for any ${\displaystyle \epsilon >0}$, there are infinitely many ${\displaystyle n}$ such that^[1]

${\displaystyle |a_{n}-t|<\epsilon }$.

A sequence might have more than one point of accumulation (even an infinite number of them). The points of accumulation might not be in the sequence.

Examples:

• The coefficients of ${\displaystyle {\frac {1}{1-z}}}$ (${\displaystyle (1,1,1,\cdots )}$) have point of accumulation ${\displaystyle 1}$
• The coefficients of ${\displaystyle e^{z}}$ (${\displaystyle (1,{\frac {1}{2!}},{\frac {1}{3!}},\cdots )}$) have point of accumulation ${\displaystyle 0}$ (note that ${\displaystyle 0}$ is not in the sequence of coefficients)
• The coefficients of ${\displaystyle {\frac {1}{1-z^{2}}}}$ (${\displaystyle (1,0,1,0,\cdots )}$) have two points of accumulation, ${\displaystyle 0}$ and ${\displaystyle 1}$
• The sequence of positive rational numbers (${\displaystyle (1,{\frac {2}{1}},{\frac {1}{2}},{\frac {1}{3}},{\frac {3}{1}},\cdots )}$) has every positive real number as a point of accumulation.

The least upper bound or supremum of a set of numbers ${\displaystyle X}$, written ${\displaystyle \sup X}$, is a number ${\displaystyle \alpha }$ such that

• ${\displaystyle x\leq \alpha }$ for all members ${\displaystyle x}$ of ${\displaystyle X}$
• for any ${\displaystyle \beta <\alpha }$ there exists a member ${\displaystyle x}$ of ${\displaystyle X}$ such that ${\displaystyle x>\beta }$.

Note that the least upper bound of a set need not be in the set.

The limit superior of a sequence ${\displaystyle (a_{n})}$, written ${\displaystyle \limsup a_{n}}$, is the least upper bound of the set of points of accumulation of the sequence.^[2]

In our above examples, these would be ${\displaystyle 1}$, ${\displaystyle 0}$, ${\displaystyle 1}$ and ${\displaystyle +\infty }$ respectively.

If ${\displaystyle \limsup a_{n}=s}$ then, for any ${\displaystyle \epsilon >0}$,^[3]

• ${\displaystyle a_{n}\leq (s+\epsilon )}$ for all but a finite number of ${\displaystyle a_{n}}$
• ${\displaystyle a_{n}\geq (s-\epsilon )}$ for an infinite number of ${\displaystyle a_{n}}$.

Note that in our context "for all but a finite number" is stronger than "for an infinite number of". For example, it is true to say of the sequence ${\displaystyle (1,0,1,0,\cdots )}$ that "an infinite number" is equal to 1. But, it is also true to say that "an infinite number" is equal to 0. On the other hand, we could only say something is true "for all but a finite number" of a sequence if it is always true after a certain point in the sequence.

In other words, to say ${\displaystyle \limsup a_{n}=s}$ means that after a certain point ${\displaystyle a_{n}}$ will not exceed ${\displaystyle s+\epsilon }$, but there could be an infinite number of ${\displaystyle a_{n}}$ that are less than ${\displaystyle s-\epsilon }$.

Note also some loss of information when we look only at the limit superior. For example, both the sequences ${\displaystyle (1,1,1,1,\cdots )}$ and ${\displaystyle (1,0,1,0,\cdots )}$ have the same limit superior, 1.

We should already be familiar with representing generating functions as power series of the form ${\displaystyle \sum a_{n}z^{n}}$. This is called a Taylor series around the point 0, otherwise known as a Maclaurin series. We will see other types of series later, but for now this is all we are interested in.

A complex number is a number ${\displaystyle z=x+iy}$ where ${\displaystyle x}$ and ${\displaystyle y}$ are both real numbers and ${\displaystyle i}$ is the imaginary unit where ${\displaystyle i^{2}=-1}$. ${\displaystyle x}$ is called the real component and ${\displaystyle y}$ the imaginary component (note that ${\displaystyle y}$ is itself a real number).

Complex numbers can be expressed in two forms: Cartesian coordinates (${\displaystyle x+iy}$) or polar coordinates ${\displaystyle re^{i\theta }}$, where ${\displaystyle r}$ is the distance from the origin or modulus and ${\displaystyle \theta }$ (theta) or ${\displaystyle \phi }$ (phi) is the angle relative to the positive ${\displaystyle x}$ axis or argument. We write the modulus of ${\displaystyle z}$ as ${\displaystyle |z|}$ and the argument of ${\displaystyle z}$ as ${\displaystyle arg(z)}$. In other words, ${\displaystyle |re^{i\theta }|=r}$, ${\displaystyle arg(re^{i\theta })=\theta }$.

It turns out if we treat the variable ${\displaystyle z}$ in our power series as a complex number there are lots of theorems and techniques we can use to estimate its coefficients.

But, to use these theorems and techniques, we must make sure that the power series converges.

We define the partial sum of a power series as ${\displaystyle s_{n}(z)=\sum _{k=0}^{n}a_{k}z^{k}}$. We say a power series converges for a particular number ${\displaystyle z_{1}}$ if there exists a number ${\displaystyle w<\infty }$ such that for each ${\displaystyle \epsilon >0}$ there exists an ${\displaystyle N}$ such that for all ${\displaystyle n>N}$

${\displaystyle |s_{n}(z_{1})-w|<\epsilon }$.

It may fail to converge if:

• ${\displaystyle \sum a_{n}z^{n}=\infty }$ as in the case of ${\displaystyle \sum 1}$, whose partial sum ${\displaystyle s_{n}=n}$.
• The partial sums oscillate between different values, such as ${\displaystyle \sum (-1)^{n}}$, where ${\displaystyle s_{n}=0}$ for odd ${\displaystyle n}$, ${\displaystyle s_{n}=1}$ for even ${\displaystyle n}$.

There are various tests for whether or not a series converges and for which values of ${\displaystyle z}$.

D'Alembert's ratio test^[4]

the series ${\displaystyle \sum a_{n}}$ converges if

${\displaystyle \lim _{n\to \infty }{\frac {a_{n+1}}{a_{n}}}<1}$

For example, for ${\displaystyle \sum z^{n}}$ the ratio is ${\displaystyle {\frac {z^{n+1}}{z^{n}}}}$ which is only less than ${\displaystyle 1}$ as ${\displaystyle n}$ goes to infinity if ${\displaystyle |z|<1}$. Therefore, the series converges for values of ${\displaystyle z}$ less than ${\displaystyle 1}$.

Comparison test^[5]

Suppose ${\displaystyle (b_{n})}$ is a convergent series and there exists a ${\displaystyle K>0}$ such that for all sufficiently large ${\displaystyle n}$ we have ${\displaystyle a_{n}\leq Kb_{n}}$. Then the series ${\displaystyle (a_{n})}$ converges.

It should be noted that if a power series converges for some number ${\displaystyle z_{1}}$ then it converges for all numbers ${\displaystyle |z|<|z_{1}|}$. Given that ${\displaystyle \sum a_{n}z_{1}^{n}}$ converges then ${\displaystyle a_{n}z_{1}^{n}\to 0}$ as ${\displaystyle n\to \infty }$ and therefore we can find a constant ${\displaystyle K}$ such that for all ${\displaystyle n}$ we have ${\displaystyle a_{n}z_{1}^{n}<K}$. If ${\displaystyle |z_{1}|=r_{1}}$ then for any ${\displaystyle |z|\leq r<r_{1}}$

${\displaystyle |a_{n}z^{n}|=\left|a_{n}z_{1}^{n}\left({\frac {z}{z_{1}}}\right)^{n}\right|<K\left({\frac {r}{r_{1}}}\right)^{n}}$

The series ${\displaystyle \left({\frac {r}{r_{1}}}\right)^{n}}$ converges by D'Alembert's ratio test and, therefore, ${\displaystyle a_{n}z^{n}}$ converges by the comparison test.^[6]

Similarly, if a power series fails to converge for some number ${\displaystyle z_{1}}$ then it fails to converge for all numbers ${\displaystyle |z|>|z_{1}|}$. Because if it did converge for some ${\displaystyle |z|>|z_{1}|}$ then we have already proved that this implies it converges for ${\displaystyle z_{1}}$, which is a contradiction.

Therefore, we can talk about a power series having a radius of convergence, a real number ${\displaystyle r}$ such that

• for ${\displaystyle |z|<r}$ the power series converges
• for ${\displaystyle |z|>r}$ the power series does not converge
• for ${\displaystyle |z|=r}$ the power series may or may not converge.

In our example, the radius of convergence of ${\displaystyle \sum z^{n}}$ is ${\displaystyle 1}$.

We say a power series converges uniformly to a bounded function ${\displaystyle s(z)}$ on the set ${\displaystyle S}$ if for any ${\displaystyle \epsilon >0}$ there exists an ${\displaystyle N}$ such that for all ${\displaystyle n\geq N}$

${\displaystyle \sup\{|s_{n}(z)-s(z)|\mid z\in S\}<\epsilon }$.

Fortunately, if a power series is convergent then it is uniformly convergent. We have seen that ${\displaystyle a_{n}z^{n}}$ converges for all points ${\displaystyle z}$ inside its radius of convergence and possibly also for some points on its circle of convergence. Therefore, for all such ${\displaystyle z}$, it has a sum ${\displaystyle s(z)}$ to which it converges. For radius of convergence ${\displaystyle r_{1}}$ and any ${\displaystyle r<r_{1}}$, for any ${\displaystyle |z|\leq r}$

${\displaystyle |s(z)-s_{n}(z)|=|a_{n+1}z^{n+1}+a_{n+2}z^{n+2}+\cdots |<K\left({\frac {r}{r_{1}}}\right)^{n+1}+K\left({\frac {r}{r_{1}}}\right)^{n+2}+\cdots }$.

Since we have established that the latter series converges we can make it less than any ${\displaystyle \epsilon }$ by making ${\displaystyle n}$ sufficiently high. Since the latter series is independent of ${\displaystyle z}$ we see that ${\displaystyle s_{n}(z)}$ can be made to be within ${\displaystyle \epsilon }$ of ${\displaystyle s(z)}$ for all ${\displaystyle z}$ for which it converges, meeting the requirements for uniform convergence.^[7]

In our example, inside the radius of convergence ${\displaystyle \sum z^{n}={\frac {1}{1-z}}}$ uniformly.

A function which can be represented as a convergent power series is called an analytic function. It should be noted that, for an analytic function ${\displaystyle f}$, the radius of convergence of its Maclaurin series is equal to the smallest singularity of ${\displaystyle f}$.^[8] We will read about singularities later.

If ${\displaystyle f(z)=\sum a_{n}z^{n}}$ and ${\displaystyle R}$ its radius of convergence then^[9]

${\displaystyle {\frac {1}{R}}=\limsup _{n\to \infty }|a_{n}|^{1/n}}$.

Two consequences of this theorem are, for all ${\displaystyle \epsilon >0}$^[10]

• ${\displaystyle a_{n}\leq \left({\frac {1}{R}}+\epsilon \right)^{n}}$ (for all but finitely many ${\displaystyle n}$)
• ${\displaystyle a_{n}\geq \left({\frac {1}{R}}-\epsilon \right)^{n}}$ (for infinitely many ${\displaystyle n}$).

Proof due to Wilf^[11] and Lang.^[12]

Take ${\displaystyle f(z)=\sum a_{n}z^{n}}$, ${\displaystyle R}$ its radius of convergence and ${\displaystyle t=\limsup _{n\to \infty }|a_{n}|^{1/n}}$. Start with ${\displaystyle t\neq 0,\infty }$. By definition of limit superior, for all but a finite number of ${\displaystyle n}$

${\displaystyle |a_{n}|\leq (t+\epsilon )^{n}}$.

${\displaystyle f(z)}$ converges if ${\displaystyle |z|<{\frac {1}{(t+\epsilon )}}}$ because then ${\displaystyle |a_{n}z^{n}|<{\frac {(t+\epsilon )^{n}}{(t+\epsilon )^{n}}}=1}$ for all but a finite number of ${\displaystyle n}$ and so converges by D'Alembert's ratio test. Therefore ${\displaystyle R\geq {\frac {1}{(t+\epsilon )}}}$.

By definition of limit superior, there exist infinitely many ${\displaystyle n}$

${\displaystyle |a_{n}|\geq (t-\epsilon )^{n}}$

${\displaystyle f(z)}$ does not converge if ${\displaystyle |z|={\frac {1}{(t-\epsilon )}}}$, because in this case its nth term does not tend to 0. Therefore ${\displaystyle R\leq {\frac {1}{(t-\epsilon )}}}$.

If ${\displaystyle R\geq {\frac {1}{(t+\epsilon )}}}$ and ${\displaystyle R\leq {\frac {1}{(t-\epsilon )}}}$ then ${\displaystyle R={\frac {1}{t}}}$ and ${\displaystyle {\frac {1}{R}}=\limsup _{n\to \infty }|a_{n}|^{1/n}}$.

In the case that ${\displaystyle t=0}$, then ${\displaystyle |a_{n}|\leq \epsilon ^{n}}$ for all but a finite number of ${\displaystyle n}$. ${\displaystyle f(z)}$ converges if ${\displaystyle |z|<{\frac {1}{\epsilon }}}$ which tends to infinity as ${\displaystyle \epsilon }$ tends to 0. Therefore, it converges for any value of ${\displaystyle |z|<\infty }$ and we say ${\displaystyle R=\infty }$.

In the case that ${\displaystyle t=\infty }$, then ${\displaystyle |a_{n}|}$ is unbounded. Therefore, ${\displaystyle f(z)}$ converges for no value of ${\displaystyle z}$ except ${\displaystyle |z|=0}$ and we say ${\displaystyle R=0}$.

Now, we prove the two consequences of the theorem.

If ${\displaystyle {\frac {1}{R}}=\limsup _{n\to \infty }|a_{n}|^{1/n}}$ then, by definition of limit superior, for all but a finite number of ${\displaystyle n}$

${\displaystyle |a_{n}|\leq \left({\frac {1}{R}}+\epsilon \right)^{n}}$

and there exist infinitely many ${\displaystyle n}$

${\displaystyle |a_{n}|\geq \left({\frac {1}{R}}-\epsilon \right)^{n}}$.

• Hardy, G. H. (1921). A Course of Pure Mathematics (3rd ed.). Cambridge University Press.
• Lang, Serge (1999). Complex Analysis (4th ed.). Springer Science+Business Media, LLC.
• Lewin, Jonathan; Lewin, Myrtle (1993). An Introduction to Mathematical Analysis (2nd ed.). McGraw-Hill, Inc.
• Stroud, K. A. (2003). Advanced Engineering Mathematics (4th ed.). Palgrave Macmillan.
• Stroud, K. A. (2001). Engineering Mathematics (5th ed.). Palgrave Macmillan.
• Titchmarsh, E. C. (1939). The Theory of Functions (2nd ed.). Oxford University Press.
• Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.