Computing with a sequence requires an encoding, usually using its generating function.
 

Computing with a sequence requires an encoding, usually using its generating function.
 

Computing asymptotics for (univariate) rational generating functions is interesting but solved* in practice.

Computing with a sequence requires an encoding, usually using its generating function.
 

Computing asymptotics for (univariate) rational generating functions is interesting but solved* in practice.

Can we handle different types of generating functions?

$$ \text{rational} \;\subset\; \text{algebraic} \;\subset\; \text{D-finite} \;\subset\; \text{D-algebraic}$$

Computing with a sequence requires an encoding, usually using its generating function.
 

Computing asymptotics for (univariate) rational generating functions is interesting but solved* in practice.

Can we handle different types of generating functions?

$$ \text{rational} \;\subset\; \text{algebraic} \;\subset\; \text{D-finite} \;\subset\; \text{D-algebraic}$$

What can we say in general?

The exponential growth of a sequence \((f_n)\) is

$$ \rho = \limsup_{n \rightarrow \infty} |f_n|^{1/n} .$$ If \(\rho>0\) is finite then

$$ f_n = \rho^n \cdot \theta(n) $$
for a sub-exponential function \(\theta(n)\).

The exponential growth of a sequence \((f_n)\) is

$$ \rho = \limsup_{n \rightarrow \infty} |f_n|^{1/n} .$$ If \(\rho>0\) is finite then

$$ f_n = \rho^n \cdot \theta(n) $$
for a sub-exponential function \(\theta(n)\).

Example
If \( f_n \sim 4^n/\sqrt{\pi n^3} \) then \(f_n\) has exponential growth \(4\).

 

The exponential growth of a sequence \((f_n)\) is

$$ \rho = \limsup_{n \rightarrow \infty} |f_n|^{1/n} .$$ If \(\rho>0\) is finite then

$$ f_n = \rho^n \cdot \theta(n) $$
for a sub-exponential function \(\theta(n)\).

Example
If \( f_n \sim 4^n/\sqrt{\pi n^3} \) then \(f_n\) has exponential growth \(4\).

Example
The exponential growth of \(\displaystyle f_n = {\big(}1+(-1)^n{\big)} \cdot 4^n  \) is also \(4\).

The exponential growth of a sequence \((f_n)\) is

$$ \rho = \limsup_{n \rightarrow \infty} |f_n|^{1/n} .$$ If \(\rho>0\) is finite then

$$ f_n = \rho^n \cdot \theta(n) $$
for a sub-exponential function \(\theta(n)\).

This is the coarsest part of asymptotic behaviour (for us).

The exponential growth of a sequence \((f_n)\) is

$$ \rho = \limsup_{n \rightarrow \infty} |f_n|^{1/n} .$$ If \(\rho>0\) is finite then

$$ f_n = \rho^n \cdot \theta(n) $$
for a sub-exponential function \(\theta(n)\).

This is the coarsest part of asymptotic behaviour (for us).

If \(F(z) = \sum_{n \geq 0} f_nz^n \) has radius of convergence \(R>0\) then Cauchy's root test implies \(\rho = 1/R\).

The exponential growth of a sequence \((f_n)\) is

$$ \rho = \limsup_{n \rightarrow \infty} |f_n|^{1/n} .$$ If \(\rho>0\) is finite then

$$ f_n = \rho^n \cdot \theta(n) $$
for a sub-exponential function \(\theta(n)\).

This is the coarsest part of asymptotic behaviour (for us).

Problem: How do we find \(R\) without knowing \(f_n\)?

The exponential growth of a sequence \((f_n)\) is

$$ \rho = \limsup_{n \rightarrow \infty} |f_n|^{1/n} .$$ If \(\rho>0\) is finite then

$$ f_n = \rho^n \cdot \theta(n) $$
for a sub-exponential function \(\theta(n)\).

This is the coarsest part of asymptotic behaviour (for us).

Solution: Use analytic properties of \(F(z)\) directly.

The exponential growth of a sequence \((f_n)\) is

$$ \rho = \limsup_{n \rightarrow \infty} |f_n|^{1/n} .$$ If \(\rho>0\) is finite then

$$ f_n = \rho^n \cdot \theta(n) $$
for a sub-exponential function \(\theta(n)\).

This is the coarsest part of asymptotic behaviour (for us).

First we need some facts from complex analysis.

An analytic function at \(a \in \mathbb{C}\) is one which has a convergent power series expansion in some disk around \(a\).

$$F(z) = \sum_{n \geq 0}f_n(z-a)^n$$

An analytic function in an open set \(U \subset \mathbb{C}\) is one which is analytic at each point of \(U\).

If \(\displaystyle F(z) = \sum_{n \geq 0}f_nz^n \) is analytic at the origin then

$$ f_n = \frac{1}{2\pi i}\int_{\color{violet}\mathcal{C}} \frac{F(z)}{z^{n+1}}dz$$

where \(\mathcal{C}\) is any sufficiently small circle* around the origin.

If \(\displaystyle F(z) = \sum_{n \geq 0}f_nz^n \) is analytic at the origin then

$$ f_n = \frac{1}{2\pi i}\int_{\color{violet}\mathcal{C}} \frac{F(z)}{z^{n+1}}dz$$

where \(\mathcal{C}\) is any sufficiently small circle* around the origin.

A. Cauchy, Exercices d'Analyse et de Physique Mathématique 2, Paris, 1841.

If \(\mathcal{C}\) and \(\mathcal{C}'\) are simple closed curves and \(\mathcal{C}\) can be deformed
to \(\mathcal{C}'\) in an open set where \(F(z)\) is analytic then

$$\int_{\color{violet}\mathcal{C}} F(z)dz = \int_{\color{lightblue}\mathcal{C}'}F(z)dz$$

If \(g(z)\) is continuous on \(\mathcal{C}\) then

$$ \left|\int_\mathcal{C} g(z) dz\right| \leq \text{length}(\mathcal{C}) \times \max_{z \in \mathcal{C}}|g(z)|$$

A domain is an open connected subset of \(\mathbb{C}^d\).

Let \(U\) and     be domains with                    .
Let \(F\) be an analytic function on \(U\).

\(F:U \rightarrow \mathbb{C}\)

\(V\)

\(U \cap V \neq \emptyset\)

A domain is an open connected subset of \(\mathbb{C}^d\).

Let \(U\) and     be domains with                    .
Let \(F\) be an analytic function on \(U\).

The direct analytic continuation of \(F\) from \(U\) to     is the analytic function \(G\) on     with \(F=G\) on              (if it exists).

\(F:U \rightarrow \mathbb{C}\)

\(G:V \rightarrow \mathbb{C}\)

\(F=G\)

\(V\)

\(V\)

\(V\)

\(U \cap V\)

\(U \cap V \neq \emptyset\)

Example: The series

$$F(z)=\sum_{n \geq 0}2^nz^n \qquad (|z|<1/2)$$
admits the direct analytic continuation

$$G(z)=\frac{1}{1-2z} \qquad\; (z \neq 1/2)$$

\(U\)

\(W\)

\(U\)

\(W\)

The Sage ore_algebra package (Kauers, Mezzarobba, ...) can numerically compute analytic continuations for functions 
satisfying linear ODEs.

This will be important for D-finite asymptotics (to come).

The Sage ore_algebra package (Kauers, Mezzarobba, ...) can numerically compute analytic continuations for functions 
satisfying linear ODEs.

This will be important for D-finite asymptotics (to come).

Note

This illustrates why we need branch cuts to define algebraic functions such as \(\sqrt{z}\).

A singularity of \(F\) is a point which \(F\) can be analytically continued arbitrarily close to but not directly at.

Example

The only singularity of \(F(z) = \displaystyle\sum_{n\geq0}2^nz^n\) is \(z=1/2\). 

A singularity of \(F\) is a point which \(F\) can be analytically continued arbitrarily close to but not directly at.

Example

The only singularity of \(F(z) = \displaystyle\sum_{n\geq0}2^nz^n\) is \(z=1/2\). 

Common Singularity Types: Dividing by zero, putting zero in a square-root, cube-root, logarithm, etc.

Let \(F(z) = \sum_{n \geq 0}f_nz^n\) be analytic at the origin.
Let \(M\) be the minimum modulus among the singularities of \(F\).

Lemma
The radius of convergence of \(F\) as a series is \(R=M\).

Let \(F(z) = \sum_{n \geq 0}f_nz^n\) be analytic at the origin.
Let \(M\) be the minimum modulus among the singularities of \(F\).

Lemma
The radius of convergence of \(F\) as a series is \(R=M\).

Proof is an Exercise (CIF and Max Modulus Bound)

 

Let \(F(z) = \sum_{n \geq 0}f_nz^n\) be analytic at the origin.
Let \(M\) be the minimum modulus among the singularities of \(F\).

Lemma
The radius of convergence of \(F\) as a series is \(R=M\).

Proof is an Exercise (CIF and Max Modulus Bound)

Corollary
The exponential growth of \(f_n\) is \(\rho=1/M\).

Example (Binary Trees)

The generating function for binary trees
 

$$ F(z) = \frac{1-\sqrt{1-4z}}{2z} $$
has only one singularity, when \(z=1/4\). Thus,

$$ [z^n]F(z) = 4^n \cdot \theta(n) $$
for some sub-exponential function \(\theta\).

Example (Binary Trees)

The generating function for binary trees
 

$$ F(z) = \frac{1-\sqrt{1-4z}}{2z} $$
has only one singularity, when \(z=1/4\). Thus,

$$ [z^n]F(z) = 4^n \cdot \theta(n) $$
for some sub-exponential function \(\theta\).

Corollary: Need at least \(2n\) bits to encode binary trees.

Example (Binary Trees)

The generating function for binary trees
 

$$ F(z) = \frac{1-\sqrt{1-4z}}{2z} $$
has only one singularity, when \(z=1/4\). Thus,

$$ [z^n]F(z) = 4^n \cdot \theta(n) $$
for some sub-exponential function \(\theta\).

Corollary: Need at least \(2n\) bits to encode binary trees.
Note:         Storing child labels for each vertex uses \(n\log n\) bits!

Theorem (Vivanti-Pringsheim)

If \(F(z)=\sum_{n \geq 0}f_nz^n\) with each \(f_n\geq0\) then one singularity of \(F\) with minimal modulus is positive and real.

Theorem (Vivanti-Pringsheim)

If \(F(z)=\sum_{n \geq 0}f_nz^n\) with each \(f_n\geq0\) then one singularity of \(F\) with minimal modulus is positive and real.

Example
A surjection of size \(n\) is a mapping from \(\{1,\dots,n\}\) onto any set of the form \(\{1,\dots,k\}\). The EGF of the class of surjections is
 

    \(\displaystyle S(z) = \sum_{n \geq 0}\frac{s_n}{n!} z^n =  \frac{1}{2-e^z}.\)

 

Theorem (Vivanti-Pringsheim)

If \(F(z)=\sum_{n \geq 0}f_nz^n\) with each \(f_n\geq0\) then one singularity of \(F\) with minimal modulus is positive and real.

Example
A surjection of size \(n\) is a mapping from \(\{1,\dots,n\}\) onto any set of the form \(\{1,\dots,k\}\). The EGF of the class of surjections is
 

    \(\displaystyle S(z) = \sum_{n \geq 0}\frac{s_n}{n!} z^n =  \frac{1}{2-e^z}.\)

The singularities of \(S\) are

   \(\{\log(2) + 2\pi i k : k \in \mathbb{Z}\}\).

Theorem (Vivanti-Pringsheim)

If \(F(z)=\sum_{n \geq 0}f_nz^n\) with each \(f_n\geq0\) then one singularity of \(F\) with minimal modulus is positive and real.

Example
A surjection of size \(n\) is a mapping from \(\{1,\dots,n\}\) onto any set of the form \(\{1,\dots,k\}\). The EGF of the class of surjections is
 

    \(\displaystyle S(z) = \sum_{n \geq 0}\frac{s_n}{n!} z^n =  \frac{1}{2-e^z}.\)

So
        \(\displaystyle \frac{s_n}{n!} = \left(\frac{1}{\log 2}\right)^n \cdot \Theta(n).\)

First Principle of Univariate
Analytic Combinatorics

The locations of the singularities of a generating function determine the exponential growth of its coefficient sequence.

First Principle of Univariate
Analytic Combinatorics

The locations of the singularities of a generating function determine the exponential growth of its coefficient sequence.

Second Principle of Univariate
Analytic Combinatorics

The type of the singularities of a generating function determine the sub-exponential growth of its coefficient sequence.

The simplest type of singularity is a pole singularity.

The point \(\omega\in\mathbb{C}\) is a pole of \(F\) if there exists a convergent Laurent expansion near \(\omega\),
 

$$ F(z) = \sum_{n \in\mathbb{Z}} f_n (z-\omega)^n, $$
with only a finite number of negative powers appearing.

The simplest type of singularity is a pole singularity.

The point \(\omega\in\mathbb{C}\) is a pole of \(F\) if there exists a convergent Laurent expansion near \(\omega\),
 

$$ F(z) = \sum_{n \in\mathbb{Z}} f_n (z-\omega)^n, $$
with only a finite number of negative powers appearing.

The largest \(m>0\) such that \(f_{-m}\neq0\) is the order of the pole.

The simplest type of singularity is a pole singularity.

The point \(\omega\in\mathbb{C}\) is a pole of \(F\) if there exists a convergent Laurent expansion near \(\omega\),
 

$$ F(z) = \sum_{n \in\mathbb{Z}} f_n (z-\omega)^n, $$
with only a finite number of negative powers appearing.

We say \(F\) is meromorphic on a domain \(U\) if it is either analytic or has a pole at every point of \(U\).

If \(F(z) = \sum_{n \in\mathbb{Z}} f_n (z-\omega)^n\) then the residue of \(F\) at \(\omega\) is

$$\mathop{\mathrm{Res}}\limits_{z=\omega} {\Big(}F(z){\Big)} = f_{-1}$$
Example
The computation




shows that
$$\mathop{\mathrm{Res}}\limits_{z=\pi/2}{\Big(}\tan(z){\Big)} = -1$$

A meromorphic function \(F\) on \(U\) is a ratio \(F(z)=G(z)/H(z)\) of analytic functions on \(U\).

The residue of \(F\) at \(z=\omega\) is computable from the derivatives of \(G\) and \(H\) at \(z=\omega\).


 

A meromorphic function \(F\) on \(U\) is a ratio \(F(z)=G(z)/H(z)\) of analytic functions on \(U\).

The residue of \(F\) at \(z=\omega\) is computable from the derivatives of \(G\) and \(H\) at \(z=\omega\).


Example
If \(H(\omega)=0\) but \(G(\omega)\neq0\) and \(H'(\omega)\neq0\) then \(\omega\) is a pole of \(F\) with order 1 and
$$\mathop{\mathrm{Res}}\limits_{z=\omega} {\Big(}F(z){\Big)} = \frac{-G(\omega)}{\omega H'(\omega)}.$$

Assume

• \(F(z)\) meromorphic inside and on a
  positively oriented simple closed curve \(\mathcal{C}\)
   
• \(F\) has no poles on \(\mathcal{C}\) and the poles
  inside \(\mathcal{C}\) form the (necessarily finite) set \(\Omega\).

Then

$$ \frac{1}{2\pi i}\int_{\mathcal{C}}F(z)dz = \sum_{\omega \in \Omega} \mathop{\mathrm{Res}}\limits_{z=\omega} {\Big(}F(z){\Big)} .$$

An alternating permutation is a permutation \(\pi\) of odd length such that \(\pi_1 > \pi_2 < \pi_3 > \cdots \)

The alternating permutations of length three: 213 and 312
 

$$A(z) = \sum_{k \geq 0}\frac{a_{2k+1}}{(2k+1)!}z^{2k+1} {\color{black} = \tan z\;} $$

An alternating permutation is a permutation \(\pi\) of odd length such that \(\pi_1 > \pi_2 < \pi_3 > \cdots \)

The alternating permutations of length three: 213 and 312
 

$$A(z) = \sum_{k \geq 0}\frac{a_{2k+1}}{(2k+1)!}z^{2k+1} = \tan z$$

The Cauchy integral formula implies

$$ \frac{a_n}{n!} = [z^n]\tan z = \frac{1}{2\pi i}\int_{\color{violet}\mathcal{C}} \frac{\tan z}{z^{n+1}} $$

The Cauchy integral formula implies

$$ \frac{a_n}{n!} = [z^n]\tan z = \frac{1}{2\pi i}\int_{\color{violet}\mathcal{C}} \frac{\tan z}{z^{n+1}} $$

The Cauchy integral formula implies

$$ \frac{a_n}{n!} = [z^n]\tan z = \frac{1}{2\pi i}\int_{\color{violet}\mathcal{C}} \frac{\tan z}{z^{n+1}} $$

The Cauchy integral formula implies

$$ \frac{a_n}{n!} = [z^n]\tan z = \frac{1}{2\pi i}\int_{\color{violet}\mathcal{C}} \frac{\tan z}{z^{n+1}} $$

The Cauchy integral formula implies

$$ \frac{a_n}{n!} = [z^n]\tan z = \frac{1}{2\pi i}\int_{\color{violet}\mathcal{C}} \frac{\tan z}{z^{n+1}} $$

$$ \frac{a_n}{n!} = {\color{lightblue}\frac{1}{2\pi i}\int_{\mathcal{C_1}} \frac{\tan z}{z^{n+1}}} + {\color{lightgreen}\frac{1}{2\pi i}\int_{\mathcal{C_2}} \frac{\tan z}{z^{n+1}}} + {\color{orange}\frac{1}{2\pi i}\int_{|z|=\pi} \frac{\tan z}{z^{n+1}}} $$

$$ \frac{a_n}{n!} = {\color{lightblue}-\mathop{\mathrm{Res}}\limits_{z=-\pi/2}\left(\frac{\tan z}{z^{n+1}}\right)}   {\color{lightgreen}-\mathop{\mathrm{Res}}\limits_{z=\pi/2}\left(\frac{\tan z}{z^{n+1}}\right)} + {\color{orange}O\left(\left(\frac{1}{\pi}\right)^n\right)} $$

$$ \frac{a_n}{n!} = {\color{lightblue}\left(\frac{-2}{\pi}\right)^{n+1}} +  {\color{lightgreen}\left(\frac{2}{\pi}\right)^{n+1}} + {\color{orange}O\left(\left(\frac{1}{\pi}\right)^n\right)} $$

$$ \frac{a_n}{n!} = 2\left(\frac{2}{\pi}\right)^{n+1} + O\left(\left(\frac{1}{\pi}\right)^n\right) \quad (n \text{ odd})  $$

$$ \frac{a_n}{n!} = 2\left(\frac{2}{\pi}\right)^{n+1} + 2\left(\frac{2}{3\pi}\right)^{n+1} +  O\left(\left(\frac{2}{5\pi}\right)^n\right) \quad (n \text{ odd})  $$

$$ \frac{a_n}{n!} = 2\left(\frac{2}{\pi}\right)^{n+1}\sum_{k \geq 0}\frac{1}{(2k+1)^{n+1}}  \quad (n \text{ odd})$$

$$ \frac{a_n}{n!} = 2\left(\frac{2}{\pi}\right)^{n+1}\sum_{k \geq 0}\frac{1}{(2k+1)^{n+1}}  \quad (n \text{ odd})$$

$$\left(\frac{2}{\pi}\right)^{n+1}$$

$$\left(\frac{2}{3\pi}\right)^{n+1}$$

$$\left(-\frac{2}{\pi}\right)^{n+1}$$

$$\left(-\frac{2}{3\pi}\right)^{n+1}$$

Theorem
Suppose \(F(z)\) is analytic on \(|z|=R\)
and at the origin, and has only pole singularities \(\omega_1,\dots,\omega_s\) in \(|z|<R\). Then
 

$$ f_n = \sum_{k=1}^m P_k(n) \; \omega_k^{-n} + O\left(R^{-n}\right)$$
where \(P_k(n)\) is a computable polynomial in \(n\) of degree one less than the order of the pole of \(F\) at \(z=\omega_k\).

Theorem
If \(z=\omega_k\) is a pole of order \(m\) of \(F(z)=G(z)/H(z)\) and \(G(\omega_k)\neq0\) then

$$ p_k(n) = \frac{m \; G(\lambda_k)}{(-\lambda_k)^{m} H^{(m)}(\lambda_k)} \, n^{m-1} + O\left(n^{m-2}\right).$$

Theorem
If \(z=\omega_k\) is a pole of order \(m\) of \(F(z)=G(z)/H(z)\) and \(G(\omega_k)\neq0\) then

$$ p_k(n) = \frac{m \; G(\lambda_k)}{(-\lambda_k)^{m} H^{(m)}(\lambda_k)} \, n^{m-1} + O\left(n^{m-2}\right).$$
Example (Surjections)
The EGF \(S(z) = 1/(2-e^z)\) has a pole of order 1 at \(z=\log(2)\) and

$$ s_n = n! [z^n]S(z) \sim \frac{n!}{2(\log 2)^{n+1}}.$$

Residues only work for isolated singularities -- not for branch points like \(z^{1/k}\) or \(\log(z)\) at \(z=0\).

Residues only work for isolated singularities -- not for branch points like \(z^{1/k}\) or \(\log(z)\) at \(z=0\).

It is still possible to prove transfer theorems of the form

$$ F(z) = a(z) + O{\Big(}b(z){\Big)} \implies [z^n]F(z) = [z^n]a(z) + O{\Big(}[z^n]b(z){\Big)}  $$

Residues only work for isolated singularities -- not for branch points like \(z^{1/k}\) or \(\log(z)\) at \(z=0\).

It is still possible to prove transfer theorems of the form

$$ F(z) = a(z) + O{\Big(}b(z){\Big)} \implies [z^n]F(z) = [z^n]a(z) + O{\Big(}[z^n]b(z){\Big)}  $$

There are many known formulas for different singularities (see Flajolet and Odlyzko 1990)

$$ F(z) \sim (1-z)^\alpha\left(\log\frac{1}{1-z}\right)^\beta \implies f_n \sim  \frac{n^{-\alpha-1}}{\Gamma(-\alpha)}(\log n)^\beta + \cdots$$

$$ \frac{1}{\sqrt{\pi}} n^{-\frac{3}{2}} 4^{n} - \frac{9}{8 \, \sqrt{\pi}} n^{-\frac{5}{2}} 4^{n} + \frac{145}{128 \, \sqrt{\pi}} n^{-\frac{7}{2}} 4^{n} - \frac{1155}{1024 \, \sqrt{\pi}} n^{-\frac{9}{2}} 4^{n} + O\!\left(n^{-5} 4^{n}\right) $$

Many of these contributions have been automated in Sage using the AsymptoticRing (Hackl, Heuberger, Krenn).

To analyze \(f_n\)

     1. Find singularities of \(F(z)\) closest to the origin

     2. Find leading terms in the series expansions of \(F\)

     3. Add corresponding contributions

An algebraic function is a root \(P(z,F(z))=0\) of some

$$ P(z,y) = p_d(z)y^d + \cdots + p_1(z)y + p_0(z) \in \mathbb{Z}[z][y].$$

 

Algebraic functions have branch cuts.

Thus we expand them in slit disks.

An algebraic function is a root \(P(z,F(z))=0\) of some

$$ P(z,y) = p_d(z)y^d + \cdots + p_1(z)y + p_0(z) \in \mathbb{Z}[z][y].$$
Puiseux's Theorem
If \(P\) is irreducible then in a slit disk around any \(\omega\in\mathbb{C}\) there exist \(d\) roots \(y_1(z),\dots,y_d(z)\) represented by convergent series expansions with fractional exponents

$$ y_k(z) = \sum_{n \geq N} c_{k,n}(1-z/\omega)^{{\color{red}n/d}}$$
where all coefficients are algebraic numbers and \(N\in\mathbb{Z}\).

An algebraic function is a root \(P(z,F(z))=0\) of some

$$ P(z,y) = p_d(z)y^d + \cdots + p_1(z)y + p_0(z) \in \mathbb{Z}[z][y].$$
Puiseux's Theorem
If \(P\) is irreducible then in a slit disk around any \(\omega\in\mathbb{C}\) there exist \(d\) roots \(y_1(z),\dots,y_d(z)\) represented by convergent series expansions with fractional exponents

$$ y_k(z) = \sum_{n \geq N} c_{k,n}(1-z/\omega)^{{\color{red}n/d}}$$
When do we have singularities?

An algebraic function is a root \(P(z,F(z))=0\) of some

$$ P(z,y) = p_d(z)y^d + \cdots + p_1(z)y + p_0(z) \in \mathbb{Z}[z][y].$$
Corollary (of Implicit Function Theorem)
All roots of \(P(z,y)=0\) around \(z=\omega\) are analytic power series (near \(\omega\)) unless \(P(\omega,y)\) has less than \(d\) distinct roots:

An algebraic function is a root \(P(z,F(z))=0\) of some

$$ P(z,y) = p_d(z)y^d + \cdots + p_1(z)y + p_0(z) \in \mathbb{Z}[z][y].$$
Corollary (of Implicit Function Theorem)
All roots of \(P(z,y)=0\) around \(z=\omega\) are analytic power series (near \(\omega\)) unless \(P(\omega,y)\) has less than \(d\) distinct roots:

$$p_d(\omega) = 0 \qquad\text{or}\qquad \text{resultant}_y(P,P_y)=0.$$

An algebraic function is a root \(P(z,F(z))=0\) of some

$$ P(z,y) = {\color{red}p_d(z)}y^d + \cdots + p_1(z)y + p_0(z) \in \mathbb{Z}[z][y].$$
Corollary (of Implicit Function Theorem)
All roots of \(P(z,y)=0\) around \(z=\omega\) are analytic power series (near \(\omega\)) unless \(P(\omega,y)\) has less than \(d\) distinct roots:

$${\color{red}p_d(\omega) = 0} \qquad\text{or}\qquad \text{resultant}_y(P,P_y)=0.$$

Roots going off to infinity

An algebraic function is a root \(P(z,F(z))=0\) of some

$$ P(z,y) = p_d(z)y^d + \cdots + p_1(z)y + p_0(z) \in \mathbb{Z}[z][y].$$
Corollary (of Implicit Function Theorem)
All roots of \(P(z,y)=0\) around \(z=\omega\) are analytic power series (near \(\omega\)) unless \(P(\omega,y)\) has less than \(d\) distinct roots:

$${\color{red}p_d(\omega) = 0} \qquad\text{or}\qquad {\color{black}\text{resultant}_y(P,P_y)=0}.$$

$$\text{resultant}_y(P,P_y)= 0$$

Roots going off to infinity

Collision of two roots

An algebraic function is a root \(P(z,F(z))=0\) of some

$$ P(z,y) = p_d(z)y^d + \cdots + p_1(z)y + p_0(z) \in \mathbb{Z}[z][y].$$
Corollary (of Implicit Function Theorem)
All roots of \(P(z,y)=0\) around \(z=\omega\) are analytic power series (near \(\omega\)) unless \(P(\omega,y)\) has less than \(d\) distinct roots:

$${\color{red}p_d(\omega) = 0} \qquad\text{or}\qquad {\color{black}\text{resultant}_y(P,P_y)=0}.$$
Corollary
Singularities of \(F\) are roots of \(\Xi(z) = p_d(z) \cdot \text{resultant}_y(P,P_y)(z)\).

$$\text{resultant}_y(P,P_y)= 0$$

$$P(z,y) = zy^2 - y + 1$$

$$p_d(z) = z$$

$$P(z,y) = zy^2 - y + 1$$

Roots going off to infinity

$$P(z,y) = zy^2 - y + 1$$

$$p_d(z) = z$$

$$\text{resultant}_y(P,P_y)= z(4z-1)$$

Roots going off to infinity

Collision of two roots

Lemma

If \(\alpha \notin \mathbb{N}\) there is an asymptotic expansion
 

$$ [z^n] (1-z/\omega)^\alpha =  \omega^{-n} \frac{n^{-\alpha-1}}{\Gamma(-\alpha)}\left( 1 + \frac{\alpha(\alpha+1)}{2n} + \cdots\right).$$

Lemma

If \(\alpha \notin \mathbb{N}\) there is an asymptotic expansion

$$ [z^n] (1-z/\omega)^\alpha =  \omega^{-n} \frac{n^{-\alpha-1}}{\Gamma(-\alpha)}\left( 1 + \frac{\alpha(\alpha+1)}{2n} + \cdots\right).$$

Example (Central Binomial Coefficients)
If \(F(z) = \displaystyle \sum_{n \geq 0}\binom{2n}{n}z^n = (1-4z)^{-1/2}\) then

$$ [z^n]F(z) = \frac{4^n}{\sqrt{\pi n}} \left(1 - \frac{1}{8 \, n}  + \cdots \right).$$

$$ \frac{1}{\sqrt{\pi}} n^{-\frac{1}{2}} 4^{n} - \frac{1}{8 \, \sqrt{\pi}} n^{-\frac{3}{2}} 4^{n} + \frac{1}{128 \, \sqrt{\pi}} n^{-\frac{5}{2}} 4^{n} + \frac{5}{1024 \, \sqrt{\pi}} n^{-\frac{7}{2}} 4^{n} + O\!\left(n^{-9/2} 4^{n}\right) $$

Lemma

If \(\alpha \notin \mathbb{N}\) there is an asymptotic expansion
 

$$ [z^n] (1-z/\omega)^\alpha =  \omega^{-n} \frac{n^{-\alpha-1}}{\Gamma(-\alpha)}\left( 1 + \frac{\alpha(\alpha+1)}{2n} + \cdots\right).$$

Example (Central Binomial Coefficients)

Corollary (Darboux's Theorem)
If \(F(z)\) is algebraic then

$$ f_n = \frac{\beta^n \, n^s}{\Gamma(s+1)} \sum_{j=1}^m C_j \omega_j^n + O\left(\beta^n n^t\right)$$

where \(\beta>0\) and the \(\omega_j,C_j\) are algebraic with all \(|\omega_j|=1\)

            \(s \in \mathbb{Q} \setminus \{-1,-2,\dots\}\) with \(t<s\)
 

Corollary (Darboux's Theorem)
If \(F(z)\) is algebraic then

$$ f_n = \frac{\beta^n \, n^s}{\Gamma(s+1)} \sum_{j=1}^m C_j \omega_j^n + O\left(\beta^n n^t\right)$$

where \(\beta>0\) and the \(\omega_j,C_j\) are algebraic with all \(|\omega_j|=1\)

            \(s \in \mathbb{Q} \setminus \{-1,-2,\dots\}\) with \(t<s\)

Notes

• All constants are algebraic except for possibly \(\Gamma(s+1)\).
  
• The exponent in \(n^s\) cannot be a negative integer.

Example (Labelled 2-Regular Graphs)

If \(g_n\) is the number of 2-regular labelled simple graphs then
 

$$ G(z) = \sum_{n \geq 0}\frac{g_n}{n!} z^n = \frac{e^{-z/2-z^2/4}}{\sqrt{1-z}}.$$The expansion

$$ G(z)  = e^{-3/4}(1-z)^{-1/2} + \cdots $$
at the only singularity \(z=1\) of \(G\) shows

$$\frac{g_n}{n!} \sim e^{-3/4} \frac{n^{-1/2}}{\Gamma(1/2)} = \frac{e^{-3/4}}{\sqrt{n \pi}}.$$

Example (Labelled 2-Regular Graphs)

If \(g_n\) is the number of 2-regular labelled simple graphs then
 

$$ G(z) = \sum_{n \geq 0}\frac{g_n}{n!} z^n = \frac{e^{-z/2-z^2/4}}{\sqrt{1-z}}.$$

$$ \frac{e^{-3/4}}{\sqrt{\pi}} n^{-\frac{1}{2}} - \frac{5e^{-3/4}}{8\sqrt{\pi}} n^{-\frac{3}{2}}  + \frac{e^{-3/4}}{128\sqrt{\pi}} n^{-\frac{5}{2}} +  O\!\left(n^7\right) $$

Example (Powers of Central Binomial Coefficients)

Recall that 

$$ \binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}. $$
For positive integers \(k\) the series

$$ F_{2k}(z) = \sum_{n \geq 0}\binom{2n}{n}^{2k}z^n$$
is transcendental as \(\binom{2n}{n}^{2k} \sim 4^{2kn} n^{-k} \pi ^{-k}\) has a negative integer power of \(n\).

Example (Powers of Central Binomial Coefficients)

Recall that 

$$ \binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}. $$
For positive integers \(k\) the series

$$ F_{2k}(z) = \sum_{n \geq 0}\binom{2n}{n}^{2k}z^n$$
is transcendental as \(\binom{2n}{n}^{2k} \sim 4^{2kn} n^{-k} \pi ^{-k}\) has a negative integer power of \(n\).
What about \(F_{2k+1}(z)\)? Exercise.

Example (Transcendence of Zeta Generating Function)

The series

$$ F(z) = \sum_{n \geq 1} \frac{z^n}{n^5} $$
is transcendental for the same reason.

Recall it is unknown if \(F(1)=\zeta(5)\) is irrational.


 

Example (Transcendence of Zeta Generating Function)

The series

$$ F(z) = \sum_{n \geq 1} \frac{z^n}{n^5} $$
is transcendental for the same reason.

Recall it is unknown if \(F(1)=\zeta(5)\) is irrational.


Flajolet 1987: Many context free languages are ambiguous as their generating functions are transcendental.

Suppose we know that \(F(z)\) satisfies \(P(z,F(z))=0\).





 

Suppose we know that \(F(z)\) satisfies \(P(z,F(z))=0\).

How do we check which roots of \(\Xi(z)\) are singularities of \(F\)?



 

Suppose we know that \(F(z)\) satisfies \(P(z,F(z))=0\).

How do we check which roots of \(\Xi(z)\) are singularities of \(F\)?

How do we find a series expansion of \(F\) near its dominant singularities?

 

Suppose we know that \(F(z)\) satisfies \(P(z,F(z))=0\).

How do we check which roots of \(\Xi(z)\) are singularities of \(F\)?

How do we find a series expansion of \(F\) near its dominant singularities?


Step 1: Find algorithm to compute series expansions of all roots \(y(z)\) of \(P(z,y)=0\) near a point \(\omega\in\mathbb{C}\).

Suppose we know that \(F(z)\) satisfies \(P(z,F(z))=0\).

How do we check which roots of \(\Xi(z)\) are singularities of \(F\)?

How do we find a series expansion of \(F\) near its dominant singularities?


Step 1: Find algorithm to compute series expansions of all roots \(y(z)\) of \(P(z,y)=0\) near a point \(\omega\in\mathbb{C}\).

Step 2: Determine which series expansion corresponds to \(F(z)\) and whether it is a power series.

The series expansions around the origin are computable using the Newton-Puiseux algorithm (and around any point with a change of variable \(z \mapsto a-z\)).

The series expansions around the origin are computable using the Newton-Puiseux algorithm (and around any point with a change of variable \(z \mapsto a-z\)).

Idea
Substitute generic solution
 

$$ y(z) = c_\alpha z^\alpha + \cdots $$
into \(P(z,y(z))=0\) and try to cancel lowest powers.

The series expansions around the origin are computable using the Newton-Puiseux algorithm (and around any point with a change of variable \(z \mapsto a-z\)).

Example
The GF for 3-ary trees is a root of \(P(z,y) = zy^3-y+1\).

The series expansions around the origin are computable using the Newton-Puiseux algorithm (and around any point with a change of variable \(z \mapsto a-z\)).

Corollary (of Implicit Function Theorem)
If \(y_k(z)\) is the only root of \(P(z,y)\) whose expansion begins

$$p_k(z) = c_az^{a/d}  +  c_{a+1}z^{(a+1)/d} + \cdots + c_b z^{b/d}$$
then all series coefficients of \(y_k(z)\) lie in \(\mathbb{Q}(c_a,\dots,c_b)\).

If \(p_k(z)\) is a polynomial then \(y_k(z)\) is a power series.

The series expansions around the origin are computable using the Newton-Puiseux algorithm (and around any point with a change of variable \(z \mapsto a-z\)).

Theorem (Walsh 1999)
At most \(2d_zd_y(2d_y-1)\) terms are needed to separate all roots of \(P(z,y)\).

 

The series expansions around the origin are computable using the Newton-Puiseux algorithm (and around any point with a change of variable \(z \mapsto a-z\)).

Theorem (Walsh 1999)
At most \(2d_zd_y(2d_y-1)\) terms are needed to separate all roots of \(P(z,y)\).

Note: After separation can make a change of variables and use symbolic Newton iteration to get \(N\) terms in the expansion of \(y_k(z)\) in \(\tilde{O}(N)\) operations.

Assume we can compute the expansion of \(F(z)\) at \(z=0\).

How can we determine which series solution of \(P(z,y)=0\) around \(z=\omega\) corresponds to \(F\)?

This is a connection problem: we want to relate local behaviour of solutions near different points.

 

Assume we can compute the expansion of \(F(z)\) at \(z=0\).

How can we determine which series solution of \(P(z,y)=0\) around \(z=\omega\) corresponds to \(F\)?

This is a connection problem: we want to relate local behaviour of solutions near different points.

Solvable using: 

• Homotopy methods,
• Root separation bounds, or
• "Branch ranking" for real solutions.

Example

The generating function of bicoloured supertrees begins

$$F(z) = 2z^2 + 2z^3 + \cdots$$
and satisfies \(P(z,F(z))=0\) where

$$P(z,y) = y^4 - 2y^3 + (1+2z)y^2 - 2zy + 4z^3.$$

$$F(z) = 2z^2 + 2z^3 + \cdots$$

$$F(z) = 2z^2 + 2z^3 + \cdots$$

$$F(z) = 2z^2 + 2z^3 + \cdots$$

$$F(z) = 2z^2 + 2z^3 + \cdots$$

$$F(z) = 2z^2 + 2z^3 + \cdots$$

$$F(z) = 2z^2 + 2z^3 + \cdots$$

$$F(z) = 2z^2 + 2z^3 + \cdots$$

$$F(z) = 2z^2 + 2z^3 + \cdots$$

$$ F(z) = \frac{1}{2} - \frac{1}{2}\left(1-4z\right)^{1/4} + O\left(\left(1-4z\right)^{3/4}\right)$$

$$F(z) = 2z^2 + 2z^3 + \cdots$$

$$ f_n = - \frac{4^n n^{-5/4}}{2\;\Gamma(-1/4)} + O\left(4^nn^{-7/4}\right)$$

$$F(z) = 2z^2 + 2z^3 + \cdots$$

$$ f_n = \frac{4^n n^{-5/4}}{8 \; \Gamma(3/4)} + O\left(4^nn^{-7/4}\right)$$

\(F(z)\) is D-finite if it satisfies a linear differential equation

$$ p_s(z)F^{(s)}(z) + \cdots + p_1(z)F'(z) + p_0(z)F(z) = 0.$$

\(F(z)\) is D-finite if it satisfies a linear differential equation

$$ p_s(z)F^{(s)}(z) + \cdots + p_1(z)F'(z) + p_0(z)F(z) = 0.$$

This happens if and only if \(f_n\) is P-recursive

$$ c_r(n)f_{n+r} + \cdots + c_1(n)f_{n+1} + c_0(n)f_n = 0$$

It is automatic to convert D-finite \(F(z) \leftrightarrow\) P-recursive \(f_n\)

We can encode a P-recursion using the Shift algebra consisting of polynomials in \(S_n\) and \(n\) such that \(S_n n = (n+1)S_n\)

Walks in \(\mathbb{N}^2\)
 

The solutions of a P-recurrence form a \(\mathbb{C}\)-vector space

We can compute series expansions of an asymptotic basis

Thus, there exist \({\color{pink}\lambda_1},{\color{lightblue}\lambda_2} \in \mathbb{C}\) such that

The solutions of a P-recurrence form a \(\mathbb{C}\)-vector space

$$ w_n = {\color{pink}\lambda_1} \frac{4^n}{n}\left(1 - \frac{3}{2n} + \cdots\right) + {\color{lightblue}\lambda_2} \frac{(-4)^n}{n^2}\left(1 - \frac{9}{2n} + \cdots\right) $$

How do we prove \({\color{pink}\lambda_1 \neq 0}\) in general?

The solutions of a D-finite equation form a \(\mathbb{C}\)-vector space

The solutions of a D-finite equation form a \(\mathbb{C}\)-vector space

We can compute expansions of a basis around \(z=0\)

The solutions of a D-finite equation form a \(\mathbb{C}\)-vector space

We can compute expansions of a basis around \({\color{lightgreen}z=1}\)

The solutions of a D-finite equation form a \(\mathbb{C}\)-vector space

We can compute expansions of a basis around \({\color{pink}z=1/4}\)

We have

$$\begin{aligned}W(z) &= {\color{lightblue}\alpha_1}{\Big(}z^{-2} + \cdots{\Big)} \hspace{0.54in} +  {\color{lightblue}\alpha_2}{\Big(}z^{-1} + \cdots{\Big)} +  {\color{lightblue}\alpha_3}{\Big(}1 + \cdots{\Big)} \\[+4mm] &={\color{pink}\gamma_1}{\Big(}\log(z-1/4) + \cdots{\Big)} +  {\color{pink}\gamma_2}{\Big(}1 + \cdots{\Big)} \hspace{0.15in}+  {\color{pink}\gamma_3}{\Big(}(z-1/4) + \cdots{\Big)} \end{aligned}$$

Using ore_algebra we can get 1000 digits in a few seconds!

Using ore_algebra we can get 1000 digits in a few seconds!

And so \(\displaystyle w_n \sim {\color{pink}(1.27324\dots)} \cdot \frac{4^n}{n}\)

Dong, M., Mezzarobba (2024)
Algorithm for asymptotics with bounded error

Dong, M., Mezzarobba (2024)
Algorithm for asymptotics with bounded error

Thus 

when \(n \geq 7\)

$$\begin{aligned}w_n \in \frac{4^{n}}{n} \cdot \biggl( &\left[1.27 \pm 4.39 \cdot 10^{-5}\right]+ \left[-1.91 \pm 5.60 \cdot 10^{-5}\right] \frac{1}{n} + \left[1503.38\pm 3.05 \cdot 10^{-3}\right] \frac{\log^2 n}{n^2} \biggr)\end{aligned}$$

Yu and Chen (2020): The genus one Canham model for 

biomembrane shape has a unique solution if a P-recursive sequence \((d_n)\) has all positive terms.

Yu and Chen (2020) - Michalet and Bensimon (1995)

Asymptotic expansion shows \(d_n \geq 0\) when \(n \geq 50\)

Check \(d_0,\dots,d_{50}\) by hand

D-finite functions can have complicated singular behaviour.
We usually work in a special case.

A power series \(F(z) = \sum_{n \geq 0}f_nz^n\) with \(f_n \in \mathbb{Q}\) is a G-function if

• \(F\) is D-finite, and
   
• both \(|f_n|\) and the least common denominator of \(f_0,\dots,f_n\) grow at most exponentially

D-finite functions can have complicated singular behaviour.
We usually work in a special case.

A power series \(F(z) = \sum_{n \geq 0}f_nz^n\) with \(f_n \in \mathbb{Q}\) is a G-function if

• \(F\) is D-finite, and
   
• both \(|f_n|\) and the least common denominator of \(f_0,\dots,f_n\) grow at most exponentially

Note: If \(F\) is a D-finite generating function (with integer coefficients) analytic at the origin then it is a G-function.

Theorem (André-Chudnovsky-Katz)

If \(F(z)\) is a G-function then a minimal order annihilating D-finite equation for \(F\) has only regular singular points and its indicial polynomial \(I(\theta)\) has only rational roots.

Theorem (André-Chudnovsky-Katz)

If \(F(z)\) is a G-function then a minimal order annihilating D-finite equation for \(F\) has only regular singular points and its indicial polynomial \(I(\theta)\) has only rational roots.

Corollary

If \(F(z)\) is a G-function then \(f_n\) has an asymptotic expansion given by a sum of terms of the form \(C \, n^{\alpha} \, (\log n)^\ell \, \zeta^n \) where \(C \in \mathbb{C}, \, \alpha \in \mathbb{Q}, \,\ell \in \mathbb{N}, \,\) and \(\zeta\) is algebraic.

Theorem (André-Chudnovsky-Katz)

If \(F(z)\) is a G-function then a minimal order annihilating D-finite equation for \(F\) has only regular singular points and its indicial polynomial \(I(\theta)\) has only rational roots.

Corollary

If \(F(z)\) is a G-function then \(f_n\) has an asymptotic expansion given by a sum of terms of the form \({\color{red}C } \, n^{\alpha} \, (\log n)^\ell \, \zeta^n\) where \({\color{red}C \in \mathbb{C}},\, \alpha \in \mathbb{Q},\, \ell \in \mathbb{N},\,\) and \(\zeta\) is algebraic.

Theorem (André-Chudnovsky-Katz)

If \(F(z)\) is a G-function then a minimal order annihilating D-finite equation for \(F\) has only regular singular points and its indicial polynomial \(I(\theta)\) has only rational roots.

Corollary

If \(F(z)\) is a G-function then \(f_n\) has an asymptotic expansion given by a sum of terms of the form \(C \, n^{{\color{red}\alpha}} \, (\log n)^\ell \, \zeta^n\) where \(C \in \mathbb{C},\, {\color{red}\alpha \in \mathbb{Q}},\, \ell \in \mathbb{N},\,\) and \(\zeta\) is algebraic.

Theorem (André-Chudnovsky-Katz)

If \(F(z)\) is a G-function then a minimal order annihilating D-finite equation for \(F\) has only regular singular points and its indicial polynomial \(I(\theta)\) has only rational roots.

Corollary

If \(F(z)\) is a G-function then \(f_n\) has an asymptotic expansion given by a sum of terms of the form \(C \, n^{\alpha} \, (\log n)^{{\color{red}\ell}} \, \zeta^n\) where \(C \in \mathbb{C},\, \alpha \in \mathbb{Q},\, {\color{red}\ell \in \mathbb{N}},\,\) and \(\zeta\) is algebraic.

Theorem (André-Chudnovsky-Katz)

If \(F(z)\) is a G-function then a minimal order annihilating D-finite equation for \(F\) has only regular singular points and its indicial polynomial \(I(\theta)\) has only rational roots.

Corollary

If \(F(z)\) is a G-function then \(f_n\) has an asymptotic expansion given by a sum of terms of the form \(C \, n^{\alpha} \, (\log n)^{\ell} \, {\color{red}\zeta}^n\) where \(C \in \mathbb{C},\, \alpha \in \mathbb{Q},\, \ell \in \mathbb{N},\,\) and \({\color{red}\zeta}\) is algebraic.

Skolem's Problem: When can cancellation occur with multiple singularities of minimal modulus?

Consider walks in \(\mathbb{N}^2\) on the steps N-SE-SW

Consider walks in \(\mathbb{N}^2\) on the steps N-SE-SW

Bostan and Kauers (FPSAC 2009): Conjectured asymptotics for 23 "small step" models in \(\mathbb{N}^2\)

M. and Wilson (FPSAC 2016): Finished proofs for all models 

Rigorous derivation of the D-finite equations for lattice path models usually uses the kernel method

1. Get functional equation for \(W(z)\)

2. Represent \(W(z)\) using a multivariate series

3. Use creative telescoping to get D-finite equation

A D-algebraic function satisfies a polynomial ODE.

Example (Tutte 1982)
The generating function enumerating 4-coloured rooted triangulations by number of vertices satisfies

$$2z^2H''(z)+5H(z)H''(z)-3z^2H'(z)H''(z)=48z^2$$

Example (Ramanujan)
The generating function \(P(q)\) for integer partitions satisfies

$$\begin{aligned}q^2 P^3 P^{(4)} &+ 20 q^2 P^2 P' P^{(3)} - 39 q^2 P^2 (P'')^2 + 12 q^2 P (P')^2 P'' + 6 q^2 (P')^4 & \\  &+ 5 q P^3 P^{(3)} - 15 q P^2 P' P'' + 10 q P (P')^3 + 4 P^3 P'' - 16 P^2 (P')^2=0 \end{aligned}$$

Some D-algebraic equations say very little about their solutions.


Theorem (Duffin 1981)
For any real continuous function \(g(z)\) and \(\epsilon>0\) there exist initial conditions for a four times continuously differentiable solution \(s(z)\) to

$$ 2F''''(z)F'(z)^2 - 5F'''(z)F''(z)F'(z) + 3F''(z)^3 = 0 $$
such that \(|s(z)-g(z)|<\epsilon\) for all \(z\in\mathbb{R}\).

Theorem (Denef and Lipshitz, 1989)
It is undecidable (by reduction to Hilbert's 10th problem) to determine whether an analytic D-algebraic defined by initial conditions at \(z=0\) has radius of convergence \(<1\) or \(\geq 1\).

Theorem (Denef and Lipshitz, 1989)
It is undecidable (by reduction to Hilbert's 10th problem) to determine whether an analytic D-algebraic defined by initial conditions at \(z=0\) has radius of convergence \(<1\) or \(\geq 1\).

Thus, asymptotics behaviour is

• decidable (up to Skolem) for rational and algebraic GFs
   
• undecidable for D-algebraic GFs
   
• still open for D-finite GFs

Transfer series expansions of \(F(z)\) near singularities into contributions to asymptotics of \(f_n\).

Meromorphic asymptotics behave like rational asymptotics up to exponentially small error.

Commutative algebra tools allow for automatic* asymptotics of algebraic functions.

Decidability of D-finite asymptotics depends on resolving the connection problem.