The behaviour of \(F(z) = \sum_{n\geq0}f_nz^n\) near its singularities transfers to the asymptotic behaviour of \(f_n\).
 

Analytic combinatorics is based on complex analysis and gives a framework for computing asymptotics automatically.

The behaviour of \(F(z) = \sum_{n\geq0}f_nz^n\) near its singularities transfers to the asymptotic behaviour of \(f_n\).
 

Analytic combinatorics is based on complex analysis and gives a framework for computing asymptotics automatically.

Asymptotics for algebraic generating functions is automatic* using tools from commutative algebra.

The behaviour of \(F(z) = \sum_{n\geq0}f_nz^n\) near its singularities transfers to the asymptotic behaviour of \(f_n\).
 

Analytic combinatorics is based on complex analysis and gives a framework for computing asymptotics automatically.

Asymptotics for algebraic generating functions is automatic* using tools from commutative algebra.

Asymptotics for D-finite generating functions can run up against the connection problem (even in practice).

The behaviour of \(F(z) = \sum_{n\geq0}f_nz^n\) near its singularities transfers to the asymptotic behaviour of \(f_n\).
 

Analytic combinatorics is based on complex analysis and gives a framework for computing asymptotics automatically.

Asymptotics for algebraic generating functions is automatic* using tools from commutative algebra.

Asymptotics for D-finite generating functions can run up against the connection problem (even in practice).

D-algebraic asymptotics are undecidable in general.

A univariate generating function \(F(z)\) tracks one parameter in a combinatorial class (the size of an object).

A multivariate generating function

$$ F(\mathbf{z})=F(z_1,\dots,z_d) = \sum_{i_1,\dots,i_d \geq 0}f_{i_1,\dots,i_d}z_1^{i_1}\cdots z_d^{i_d} = \sum_{\mathbf{i}\in\mathbb{N}^d}f_\mathbf{i} \mathbf{z}^\mathbf{i}$$
tracks multiple parameters.

A univariate generating function \(F(z)\) tracks one parameter in a combinatorial class (the size of an object).

A multivariate generating function

$$ F(\mathbf{z})=F(z_1,\dots,z_d) = \sum_{i_1,\dots,i_d \geq 0}f_{i_1,\dots,i_d}z_1^{i_1}\cdots z_d^{i_d} = \sum_{\mathbf{i}\in\mathbb{N}^d}f_\mathbf{i} \mathbf{z}^\mathbf{i}$$
tracks multiple parameters.

Multivariate GFs can be derived using tracking atoms.

Example (Binary Trees by Size and Leaves)

The class of (non-empty rooted planar) binary trees has the specification

$$\mathcal{B} \;\;=\;\; \underbrace{\mathcal{Z}}_\text{no children} +\;\; \underbrace{\mathcal{Z} \times \mathcal{B} \times \mathcal{E}}_\text{only left child} \;\; + \;\; \underbrace{\mathcal{Z} \times \mathcal{E} \times \mathcal{B}}_\text{only right child} \;\; + \;\; \underbrace{\mathcal{Z} \times \mathcal{B}^2}_\text{two children}$$

Example (Binary Trees by Size and Leaves)

The class of (non-empty rooted planar) binary trees has the specification

$$\mathcal{B} \;\;=\;\; \underbrace{\mathcal{Z}}_\text{no children} +\;\; \underbrace{\mathcal{Z} \times \mathcal{B} \times \mathcal{E}}_\text{only left child} \;\; + \;\; \underbrace{\mathcal{Z} \times \mathcal{E} \times \mathcal{B}}_\text{only right child} \;\; + \;\; \underbrace{\mathcal{Z} \times \mathcal{B}^2}_\text{two children}$$

If \(\mu\) marks leaves then

$$\mathcal{B} \;\;=\;\; \mu \times \mathcal{Z} \;\;+\;\; \mathcal{Z} \times \mathcal{B} \times \mathcal{E} \;\; + \;\; \mathcal{Z} \times \mathcal{E} \times \mathcal{B} \;\; + \;\; \mathcal{Z} \times \mathcal{B}^2$$
and
$$ B(u,z) = uz + 2zB(u,z) + zB(u,z)^2.$$

Example (Binary Trees by Size and Leaves)

$$ B(u,z) = uz + 2zB(u,z) + zB(u,z)^2$$

Example (Binary Trees by Size and Leaves)

$$ B(u,z) = uz + 2zB(u,z) + zB(u,z)^2$$

Example (Binary Trees by Size and Leaves)

$$ B(u,z) = uz + 2zB(u,z) + zB(u,z)^2$$

Example (Binary Trees by Size and Leaves)

$$ B(u,z) = uz + 2zB(u,z) + zB(u,z)^2$$

Example (Binary Trees by Size and Leaves)

$$ B(u,z) = uz + 2zB(u,z) + zB(u,z)^2$$
Note: In this case we can solve the quadratic to get

$$ B(u,z) = \frac{1-2z-\sqrt{1-4z-4(u-1)z^2}}{2z}$$
 

Example (Binary Trees by Size and Leaves)

$$ B(u,z) = uz + 2zB(u,z) + zB(u,z)^2$$
Note: In this case we can solve the quadratic to get

$$ B(u,z) = \frac{1-2z-\sqrt{1-4z-4(u-1)z^2}}{2z}$$

In the multivariate case asymptotic behaviour of \([u^rz^s]B(u,z)\) depends on how \(r\) and \(s\) go to infinity.

Example (Binary Trees by Size and Leaves)

$$ B(u,z) = uz + 2zB(u,z) + zB(u,z)^2$$
Note: In this case we can solve the quadratic to get

$$ B(u,z) = \frac{1-2z-\sqrt{1-4z-4(u-1)z^2}}{2z}$$

In the multivariate case asymptotic behaviour of \([u^rz^s]B(u,z)\) depends on how \(r\) and \(s\) go to infinity.

Interesting behaviour usually happens when indices go to infinity at a proportional rate.

We can use a multivariate generating function to track the number of coins and which coins we use to make change for \(n\) euro cents.

Consider the \(d\)-variate series
 

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}z_1^{i_1}\cdots z_d^{i_d} = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}\mathbf{z}^{\mathbf{i}}$$
 

The \(\color{violet}\mathbf{r}-\)diagonal sequence of \(F\) consists of the coefficients
 

$$(f_{n\mathbf{r}}) = f_{\mathbf{0}}, f_\mathbf{r}, f_{2\mathbf{r}},\dots $$
Note: The coefficient is only defined if \(n\mathbf{r}\in\mathbb{N^d}\).

Consider the \(d\)-variate series
 

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}z_1^{i_1}\cdots z_d^{i_d} = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}\mathbf{z}^{\mathbf{i}}$$
 

 \((1,1)-\)Diagonal (Main Diagonal)

$$\begin{aligned} F(x, y) &= \frac{1}{1 - x - y} \\[+4mm] &= 1 + x + y + 2xy + x^2 + y^2 + 3x^2y + 3xy^2 + y^3 + 6x^2y^2 + \cdots \end{aligned}$$

Consider the \(d\)-variate series
 

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}z_1^{i_1}\cdots z_d^{i_d} = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}\mathbf{z}^{\mathbf{i}}$$
 

 \((2,1)-\)Diagonal

$$\begin{aligned} F(x, y) &= \frac{1}{1 - x - y} \\[+4mm] &= 1 + x + y + 2xy + x^2 + y^2 + 3x^2y  + \cdots + 15x^4y^2 + \cdots \end{aligned}$$

Consider the \(d\)-variate series
 

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}z_1^{i_1}\cdots z_d^{i_d} = \sum_{\mathbf{i}\in\mathbb{N}^d} f_{\mathbf{i}}\mathbf{z}^{\mathbf{i}}$$
 

We write

$$ (\Delta_{\mathbf{r}}F)(t) = \sum_{n \geq 0}f_{n\mathbf{r}}t^n $$
and use the shorthand \(\Delta F = \Delta_\mathbf{1} F\) for the main diagonal.

Useful encodings for interesting univariate sequences

Uniform asymptotics over most directions

Yield combinatorial limit theorems in applications

Analytic combinatorics in several variables (ACSV) relates analytic properties of a multivariate generating function to asymptotic properties of its diagonal coefficient sequences

Consider the number \(w_n\) of walks in \(\mathbb{N}^2\) on the steps N-SE-SW.
Its GF is D-finite but runs into the connection problem.

We can show \(\displaystyle w_n = {\color{pink}\lambda_1} \cdot \frac{3^n}{\sqrt{n}}(1+\cdots) + O((2\sqrt{2})^n)\) where \({\color{pink}|\lambda_1|<10^{-1000}}\)

How can we (automatically) prove \({\color{pink}\lambda_1=0}\)?

The GF of \(w_n\) can also be represented as

$$W(t) = \Delta \left(\frac{(1 + x)(2zx^2y^2 + 2zy^2 - 1)}{(-1 + y)(zx^2y^2 + zy^2 + zx - 1)(zx^2y^2 + zy^2 - 1)}\right)$$

The GF of \(w_n\) can also be represented as

$$W(t) = \Delta \left(\frac{(1 + x)(2zx^2y^2 + 2zy^2 - 1)}{(-1 + y)(zx^2y^2 + zy^2 + zx - 1)(zx^2y^2 + zy^2 - 1)}\right)$$

GF tracking divisions
and polynomial degree
in Euclidean Algorithm
over \(\mathbb{F}_p[x]\) is

$$F(u,z) = \frac{1}{1-pz-p(p-1)uz}$$
(Flajolet and Sedgewick Ex. IX.15)

analysis of data structures

quantum information theory

DNA synthesis encoding

quantum thermodynamics

analysis of online logistic regression algorithms

analysis of high-dimensional fast FFT

random group theory

bioinformatic sequence alignment

studies of stable and random polynomials

loop models

the Ising model

arctic curves for dimers and Aztec diamonds

sampling perfect matchings in bipartite graphs

boson unitary operators

chemical reaction networks

polymer systems

Click here for Google Scholar page tracking citations to ACSV

Topics in citing papers include:

Given a point \(\mathbf{a}\in\mathbb{C}^d\) and \(\mathbf{m}\in\mathbb{R}_{>0}^d\) we define the

• open polydisk centered at \(\mathbf{a}\) with radius \(\mathbf{m}\) 
   

$$D_{\mathbf{a}}(\mathbf{m}) = \left\{\mathbf{z}\in\mathbb{C}^d : |z_1-a_1|<m_1, \;\dots,\; |z_d-a_d|<m_d\right\}$$

• torus centered at \(\mathbf{a}\) with radius \(\mathbf{m}\)
   

$$T_{\mathbf{a}}(\mathbf{m}) = \left\{\mathbf{z}\in\mathbb{C}^d : |z_1-a_1|=m_1, \;\dots,\; |z_d-a_d|=m_d\right\}$$

Given a point \(\mathbf{a}\in\mathbb{C}^d\) and \(\mathbf{m}\in\mathbb{R}_{>0}^d\) we define the

• open polydisk centered at \(\mathbf{a}\) with radius \(\mathbf{m}\) 
   

$$D_{\mathbf{a}}(\mathbf{m}) = \left\{\mathbf{z}\in\mathbb{C}^d : |z_1-a_1|<m_1, \;\dots,\; |z_d-a_d|<m_d\right\}$$

• torus centered at \(\mathbf{a}\) with radius \(\mathbf{m}\)
   

$$T_{\mathbf{a}}(\mathbf{m}) = \left\{\mathbf{z}\in\mathbb{C}^d : |z_1-a_1|=m_1, \;\dots,\; |z_d-a_d|=m_d\right\}$$

Note: When \(d>1\) the torus \(T_\mathbf{a}(\mathbf{m})\) is a subset of \(\partial D_\mathbf{a}(\mathbf{m})\).

Given a point \(\mathbf{a}\in\mathbb{C}^d\) and \(\mathbf{m}\in\mathbb{R}_{>0}^d\) we define the

• open polydisk centered at \(\mathbf{a}\) with radius \(\mathbf{m}\) 
   

$$D_{\mathbf{a}}(\mathbf{m}) = \left\{\mathbf{z}\in\mathbb{C}^d : |z_1-a_1|<m_1, \;\dots,\; |z_d-a_d|<m_d\right\}$$

• torus centered at \(\mathbf{a}\) with radius \(\mathbf{m}\)
   

$$T_{\mathbf{a}}(\mathbf{m}) = \left\{\mathbf{z}\in\mathbb{C}^d : |z_1-a_1|=m_1, \;\dots,\; |z_d-a_d|=m_d\right\}$$

Note: If \(\mathbf{a}=\mathbf{0}\) we just write \(D(\mathbf{m})\) and \(T(\mathbf{m})\).

Given a point \(\mathbf{a}\in\mathbb{C}^d\) and \(\mathbf{m}\in\mathbb{R}_{>0}^d\) we define the

• open polydisk centered at \(\mathbf{a}\) with radius \(\mathbf{m}\) 
   

$$D_{\mathbf{a}}(\mathbf{m}) = \left\{\mathbf{z}\in\mathbb{C}^d : |z_1-a_1|<m_1, \;\dots,\; |z_d-a_d|<m_d\right\}$$

• torus centered at \(\mathbf{a}\) with radius \(\mathbf{m}\)
   

$$T_{\mathbf{a}}(\mathbf{m}) = \left\{\mathbf{z}\in\mathbb{C}^d : |z_1-a_1|=m_1, \;\dots,\; |z_d-a_d|=m_d\right\}$$

Note: For any \(\mathbf{w}\in\mathbb{C}_*^d\) with non-zero coordinates we define

$$ D(\mathbf{w}) = \left\{\mathbf{z}\in \mathbb{C}^d : |z_1|<|w_1|,\; \dots,\; |z_d|<|w_d| \right\}$$

Given a point \(\mathbf{a}\in\mathbb{C}^d\) and \(\mathbf{m}\in\mathbb{R}_{>0}^d\) we define the

• open polydisk centered at \(\mathbf{a}\) with radius \(\mathbf{m}\) 
   

$$D_{\mathbf{a}}(\mathbf{m}) = \left\{\mathbf{z}\in\mathbb{C}^d : |z_1-a_1|<m_1, \;\dots,\; |z_d-a_d|<m_d\right\}$$

• torus centered at \(\mathbf{a}\) with radius \(\mathbf{m}\)
   

$$T_{\mathbf{a}}(\mathbf{m}) = \left\{\mathbf{z}\in\mathbb{C}^d : |z_1-a_1|=m_1, \;\dots,\; |z_d-a_d|=m_d\right\}$$

Note: For any \(\mathbf{w}\in\mathbb{C}_*^d\) with non-zero coordinates we define

$$ T(\mathbf{w}) = \left\{\mathbf{z}\in \mathbb{C}^d : |z_1|=|w_1|,\; \dots,\; |z_d|=|w_d| \right\}$$

Cauchy (1831) and Jordan (1893): \(F(\mathbf{z})\) is analytic if it is analytic in each variable separately.

Cauchy (1831) and Jordan (1893): \(F(\mathbf{z})\) is analytic if it is analytic in each variable separately.

Weierstrass (1860/70s) and Poincaré (1879): \(F(\mathbf{z})\) is analytic if it has a convergent multivariate series representation.

Cauchy (1831) and Jordan (1893): \(F(\mathbf{z})\) is analytic if it is analytic in each variable separately.

Weierstrass (1860/70s) and Poincaré (1879): \(F(\mathbf{z})\) is analytic if it has a convergent multivariate series representation.

Osgood (1899) + Hartogs (1905): These are equivalent.

Cauchy (1831) and Jordan (1893): \(F(\mathbf{z})\) is analytic if it is analytic in each variable separately.

Weierstrass (1860/70s) and Poincaré (1879): \(F(\mathbf{z})\) is analytic if it has a convergent multivariate series representation.

Osgood (1899) + Hartogs (1905): These are equivalent.

Bottazzini and Gray (2013): Nice history of complex analysis

We say \(F:\mathbb{C}^d \rightarrow \mathbb{C}\) is analytic at \(\mathbf{a}\in\mathbb{C}^d\) if there exists an absolutely and uniformly convergent series representation

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_\mathbf{i}(\mathbf{z}-\mathbf{a})^\mathbf{i}$$
on some polydisk \(D_\mathbf{a}(\mathbf{m})\) with radius \(\mathbf{m}\in\mathbb{R}_{>0}^d\).

 

We say \(F:\mathbb{C}^d \rightarrow \mathbb{C}\) is analytic at \(\mathbf{a}\in\mathbb{C}^d\) if there exists an absolutely and uniformly convergent series representation

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_\mathbf{i}(\mathbf{z}-\mathbf{a})^\mathbf{i}$$
on some polydisk \(D_\mathbf{a}(\mathbf{m})\) with radius \(\mathbf{m}\in\mathbb{R}_{>0}^d\).

Abel's Lemma: If \(\sum f_\mathbf{i}\mathbf{z}^\mathbf{i}\) converges at \(\mathbf{w}\) then it converges absolutely and uniformly on compact subsets of \(D(\mathbf{w})\).
 

We say \(F:\mathbb{C}^d \rightarrow \mathbb{C}\) is analytic at \(\mathbf{a}\in\mathbb{C}^d\) if there exists an absolutely and uniformly convergent series representation

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_\mathbf{i}(\mathbf{z}-\mathbf{a})^\mathbf{i}$$
on some polydisk \(D_\mathbf{a}(\mathbf{m})\) with radius \(\mathbf{m}\in\mathbb{R}_{>0}^d\).

Abel's Lemma: If \(\sum f_\mathbf{i}\mathbf{z}^\mathbf{i}\) converges at \(\mathbf{w}\) then it converges absolutely and uniformly on compact subsets of \(D(\mathbf{w})\).

Note: Absolute convergence implies we can sum in any order.

Example
Whenever \(|x+y|<1\) we can write
 

$$ \frac{1}{1-x-y} = \sum_{n \geq 0}(x+y)^n = \sum_{n \geq 0}\sum_{k=0}^n\binom{n}{k}x^ky^{n-k}. $$

Example
Whenever \(|x+y|<1\) we can write
 

$$ \frac{1}{1-x-y} = \sum_{n \geq 0}(x+y)^n = \sum_{n \geq 0}\sum_{k=0}^n\binom{n}{k}x^ky^{n-k}. $$
But we would like to rearrange and write
 

$$ \frac{1}{1-x-y} = \sum_{i,j \geq 0}\binom{i+j}{i}x^iy^j.$$
This is not possible when (for instance) \(x=10\) and \(y=-9.5\).

We have absolute convergence when \(|x|+|y|<1\) since

$$ \sum_{i,j \geq 0}\binom{i+j}{i}|x|^i|y|^j = \frac{1}{1-|x|-|y|}$$

The real-logarithm (Relog) map from \(\mathbb{C}_*^d\) to \(\mathbb{R}^d\) is

$$ \text{Relog}(\mathbf{z}) = {\Big(}\log |z_1|, \, \log |z_2|, \, \dots, \, \log |z_d|{\Big)} $$

A set \(\Omega \subset \mathbb{C}^d\) is called log-convex if \(\text{Relog}(\Omega)\) is convex.

The real-logarithm (Relog) map from \(\mathbb{C}_*^d\) to \(\mathbb{R}^d\) is

$$ \text{Relog}(\mathbf{z}) = {\Big(}\log |z_1|, \, \log |z_2|, \, \dots, \, \log |z_d|{\Big)} $$

A set \(\Omega \subset \mathbb{C}^d\) is called log-convex if \(\text{Relog}(\Omega)\) is convex.

Proposition: The (absolute) domain of convergence \(\mathcal{D}\) of a multivariate power series around the origin is log-convex.

The real-logarithm (Relog) map from \(\mathbb{C}_*^d\) to \(\mathbb{R}^d\) is

$$ \text{Relog}(\mathbf{z}) = {\Big(}\log |z_1|, \, \log |z_2|, \, \dots, \, \log |z_d|{\Big)} $$

A set \(\Omega \subset \mathbb{C}^d\) is called log-convex if \(\text{Relog}(\Omega)\) is convex.

Proposition: The (absolute) domain of convergence \(\mathcal{D}\) of a multivariate power series around the origin is log-convex.

Q: How do we characterize \(\mathcal{D}\)?

The real-logarithm (Relog) map from \(\mathbb{C}_*^d\) to \(\mathbb{R}^d\) is

$$ \text{Relog}(\mathbf{z}) = {\Big(}\log |z_1|, \, \log |z_2|, \, \dots, \, \log |z_d|{\Big)} $$

A set \(\Omega \subset \mathbb{C}^d\) is called log-convex if \(\text{Relog}(\Omega)\) is convex.

Proposition: The (absolute) domain of convergence \(\mathcal{D}\) of a multivariate power series around the origin is log-convex.

Q: How do we characterize \(\partial\mathcal{D}\)?

The real-logarithm (Relog) map from \(\mathbb{C}_*^d\) to \(\mathbb{R}^d\) is

$$ \text{Relog}(\mathbf{z}) = {\Big(}\log |z_1|, \, \log |z_2|, \, \dots, \, \log |z_d|{\Big)} $$

A set \(\Omega \subset \mathbb{C}^d\) is called log-convex if \(\text{Relog}(\Omega)\) is convex.

Proposition: The (absolute) domain of convergence \(\mathcal{D}\) of a multivariate power series around the origin is log-convex.

Q: How do we characterize \(\partial\log(\mathcal{D})\)?

The real-logarithm (Relog) map from \(\mathbb{C}_*^d\) to \(\mathbb{R}^d\) is

$$ \text{Relog}(\mathbf{z}) = {\Big(}\log |z_1|, \, \log |z_2|, \, \dots, \, \log |z_d|{\Big)} $$

A set \(\Omega \subset \mathbb{C}^d\) is called log-convex if \(\text{Relog}(\Omega)\) is convex.

Proposition: The (absolute) domain of convergence \(\mathcal{D}\) of a multivariate power series around the origin is log-convex.

Q: How do we characterize \(\partial\log(\mathcal{D})\)?

A: Complex analysis in several variables.

Theorem

Suppose \(F\) is analytic on a domain \(\Omega \subset \mathbb{C}^d\) and \(\overline{D(\mathbf{m})} \subset \Omega\). If

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_\mathbf{i}\mathbf{z}^\mathbf{i} $$
on \(D(\mathbf{m})\) then, for all \(\mathbf{i}\in\mathbb{N}^d\),

$$ f_\mathbf{i} = \frac{1}{(2\pi i)^d} \int_{T(\mathbf{m})} \frac{F(\mathbf{z})}{\mathbf{z}^{\mathbf{i}+\mathbf{1}}}  d\mathbf{z}.$$
 

Theorem

Suppose \(F\) is analytic on a domain \(\Omega \subset \mathbb{C}^d\) and \(\overline{D(\mathbf{m})} \subset \Omega\). If

$$ F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{N}^d} f_\mathbf{i}\mathbf{z}^\mathbf{i} $$
on \(D(\mathbf{m})\) then, for all \(\mathbf{i}\in\mathbb{N}^d\),

$$ f_\mathbf{i} = \frac{1}{(2\pi i)^d} \int_{T(\mathbf{m})} \frac{F(\mathbf{z})}{\mathbf{z}^{\mathbf{i}+\mathbf{1}}}  d\mathbf{z}.$$
Note: We integrate over product of circles. This is nice, but not a boundary like when \(d=1\).

Suppose \(G\) and \(H\) analytic in a domain \(\Omega \subset\mathbb{C}^d\) with \(H \not\equiv 0\).

We say that \(F(\mathbf{z})=G(\mathbf{z})/H(\mathbf{z})\) has a (pole) singularity 
at \(\mathbf{z}=\mathbf{a}\) if \(|F(\mathbf{z})|\) is unbounded in any neighbourhood of \(\mathbf{a}\).

Suppose \(G\) and \(H\) analytic in a domain \(\Omega \subset\mathbb{C}^d\) with \(H \not\equiv 0\).

We say that \(F(\mathbf{z})=G(\mathbf{z})/H(\mathbf{z})\) has a (pole) singularity 
at \(\mathbf{z}=\mathbf{a}\) if \(|F(\mathbf{z})|\) is unbounded in any neighbourhood of \(\mathbf{a}\).

Example
\(F(x,y)=(x+y)/(x-y)\) has a pole whenever \(x=y\).

Suppose \(G\) and \(H\) analytic in a domain \(\Omega \subset\mathbb{C}^d\) with \(H \not\equiv 0\).

We say that \(F(\mathbf{z})=G(\mathbf{z})/H(\mathbf{z})\) has a (pole) singularity 
at \(\mathbf{z}=\mathbf{a}\) if \(|F(\mathbf{z})|\) is unbounded in any neighbourhood of \(\mathbf{a}\).

Example
\(F(x,y)=(x+y)/(x-y)\) has a pole whenever \(x=y\).

Note that \(x+y\) and \(x-y\) vanish at \((0,0)\) but

$$ F\left(\frac{1}{n}+\frac{1}{n^2},\frac{1}{n}\right) = 2n+1 \rightarrow \infty \qquad (n\rightarrow\infty)$$

Proposition

If \(F(\mathbf{z})=G(\mathbf{z})/H(\mathbf{z})\) is the ratio of coprime polynomials then the singular set of \(F\) is the singular variety

$$\mathcal{V} = \{\mathbf{z}\in\mathbb{C}^d : H(\mathbf{z})=0\}.$$

 

Proposition

If \(F(\mathbf{z})=G(\mathbf{z})/H(\mathbf{z})\) is the ratio of coprime polynomials then the singular set of \(F\) is the singular variety

$$\mathcal{V} = \{\mathbf{z}\in\mathbb{C}^d : H(\mathbf{z})=0\}.$$

Note: A similar result holds for analytic functions using local rings to define coprimality.

Proposition

If \(F(\mathbf{z})=G(\mathbf{z})/H(\mathbf{z})\) is the ratio of coprime polynomials then the singular set of \(F\) is the singular variety

$$\mathcal{V} = \{\mathbf{z}\in\mathbb{C}^d : H(\mathbf{z})=0\}.$$

Note: A similar result holds for analytic functions using local rings to define coprimality.

Proposition
When \(d\geq2\), meromorphic functions have no isolated singularities.

Corollary of Multivariate CIF

Let \(F=\sum f_\mathbf{i}\mathbf{z}^\mathbf{i}\) have domain of convergence \(\mathcal{D}\). If \(\mathbf{w}\in\partial\mathcal{D}\) then there exists a singularity \(\mathbf{v}\) of \(F\) with \(|v_j|=|w_j|\) for all \(j\).

A minimal point of \(F\) is an element of \(\partial \mathcal{D} \cap \mathcal{V}\).

Corollary of Multivariate CIF

Let \(F=\sum f_\mathbf{i}\mathbf{z}^\mathbf{i}\) have domain of convergence \(\mathcal{D}\). If \(\mathbf{w}\in\partial\mathcal{D}\) then there exists a singularity \(\mathbf{v}\) of \(F\) with \(|v_j|=|w_j|\) for all \(j\).

A minimal point of \(F\) is an element of \(\partial \mathcal{D} \cap \mathcal{V}\).

Note:  The point \(\mathbf{w}\in\mathcal{V}\) is minimal if and only if there does not exist \(\mathbf{v}\in\mathcal{V}\) with \(|v_j|<|w_j|\) for all \(j\).

Example

Recall the domain of convergence

$$\mathcal{D} = \{(x,y) \in \mathbb{C}^d : |x|+|y|<1\}$$
for the series

$$ F(x,y) = \frac{1}{1-x-y} = \sum_{i,j \geq 0}\binom{i+j}{i}x^i y^j.$$
 

Example

Recall the domain of convergence

$$\mathcal{D} = \{(x,y) \in \mathbb{C}^d : |x|+|y|<1\}$$
for the series

$$ F(x,y) = \frac{1}{1-x-y} = \sum_{i,j \geq 0}\binom{i+j}{i}x^i y^j.$$
 

Example

Recall the domain of convergence

$$\mathcal{D} = \{(x,y) \in \mathbb{C}^d : |x|+|y|<1\}$$
for the series

$$ F(x,y) = \frac{1}{1-x-y} = \sum_{i,j \geq 0}\binom{i+j}{i}x^i y^j.$$
If \(|x|+|y| = 1\) and \(x+y=1\) then \(x\) and \(y\) must be real and positive, so the minimal points are \(\{(x,1-x) : 0 \leq x \leq 1\}\).

Example

Recall the domain of convergence

$$\mathcal{D} = \{(x,y) \in \mathbb{C}^d : |x|+|y|<1\}$$
for the series

$$ F(x,y) = \frac{1}{1-x-y} = \sum_{i,j \geq 0}\binom{i+j}{i}x^i y^j.$$
If \(|x|+|y| = 1\) and \(x+y=1\) then \(x\) and \(y\) must be real and positive, so the minimal points are \(\{(x,1-x) : 0 \leq x \leq 1\}\).

How can we visualize \(\mathcal{D}\) in \(\mathbb{C}^d\)?

How can we visualize \(\mathcal{D}\) in \(\mathbb{C}^d\)?

Step 1) Take coordinate-wise moduli to lie in \(\mathbb{R}^d\)

How can we visualize \(\mathcal{D}\) in \(\mathbb{C}^d\)?

Step 1) Take coordinate-wise moduli to lie in \(\mathbb{R}^d\)

Step 2) Take coordinate-wise logarithms

How can we visualize \(\mathcal{D}\) in \(\mathbb{C}^d\)?

Step 1) Take coordinate-wise moduli to lie in \(\mathbb{R}^d\)

Step 2) Take coordinate-wise logarithms

The amoeba of a polynomial \(H(\mathbf{z})\) is

$$ \displaystyle \text{amoeba}(H) = \left\{\text{Relog}(\mathbf{z}): \mathbf{z}\in\mathbb{C}_*^d \text{ and } H(\mathbf{z})=0\right\}. $$
Let \(\mathcal{D} = \) domain of convergence of \(1/H\).

Figure from Discriminants, Resultants, and Multidimensional Determinants, Gelfand, Kapranov, and Zelevinsky, 1994.

$$\text{amoeba}(1-x-y)$$
 

$$\text{amoeba}(1-x-y)$$
 

\(\text{Relog}(\mathcal{D})\)

$$\text{amoeba}(1-x-y)$$
 

\(\partial\text{Relog}(\mathcal{D})\)

$$\text{amoeba}(1 - x - y - 6xy - x^2y^2)$$

\(\text{Relog}(\mathcal{D})\)

$$\text{amoeba}(1 - x - y - 6xy - x^2y^2)$$

\(\partial\text{Relog}(\mathcal{D})\)

The components of \(\text{amoeba}(H)^c\) are convex subsets of \(\mathbb{R}^d\).

One of them corresponds to \(\text{Relog}(\mathcal{D})\).

What do the other components represent?

The components of \(\text{amoeba}(H)^c\) are convex subsets of \(\mathbb{R}^d\).

One of them corresponds to \(\text{Relog}(\mathcal{D})\).

What do the other components represent?

Domains of convergence of other Laurent expansions!

The components of \(\text{amoeba}(H)^c\) are convex subsets of \(\mathbb{R}^d\).

One of them corresponds to \(\text{Relog}(\mathcal{D})\).

What do the other components represent?

Domains of convergence of other Laurent expansions!

One rational function naturally encodes several convergent Laurent expansions.

Example
The geometric series formula implies

$$ \frac{1}{1-z} = \sum_{n \geq 0}z^n \qquad {\big(}|z|<1{\big)} $$
 

Example
The geometric series formula implies

$$ \frac{1}{1-z} = \sum_{n \geq 0}z^n \qquad {\big(}|z|<1{\big)} $$
but it also implies

$$ \frac{1}{1-z} = \frac{-1/z}{1-1/z} = -\sum_{n \geq 0}z^{-n-1} \qquad {\big(}|z|>1{\big)} $$

Example
The geometric series formula implies

$$ \frac{1}{1-z} = \sum_{n \geq 0}z^n \qquad {\big(}|z|<1{\big)} $$
but it also implies

$$ \frac{1}{1-z} = \frac{-1/z}{1-1/z} = -\sum_{n \geq 0}z^{-n-1} \qquad {\big(}|z|>1{\big)} $$
Note: Different series have disjoint domains of convergence.

Example
We have seen the expansion

$$ \frac{1}{1-x-y} = \sum_{i,j \geq 0}\binom{i+j}{i} x^iy^j \qquad {\big(}|x|+|y|<1{\big)} $$
but there are also expansions

 

Example
We have seen the expansion

$$ \frac{1}{1-x-y} = \sum_{i,j \geq 0}\binom{i+j}{i} x^iy^j \qquad {\big(}|x|+|y|<1{\big)} $$
but there are also expansions

$$ \begin{aligned} \frac{-1/x}{1-(1-y)/x} &= \sum_{i,j \geq 0}\binom{j}{i}(-1)^{i+1}x^{-j-1}y^i \qquad {\big(}1+|y|<|x|{\big)} \end{aligned}$$

Example
We have seen the expansion

$$ \frac{1}{1-x-y} = \sum_{i,j \geq 0}\binom{i+j}{i} x^iy^j \qquad {\big(}|x|+|y|<1{\big)} $$
but there are also expansions

$$ \begin{aligned} \frac{-1/x}{1-(1-y)/x} &= \sum_{i,j \geq 0}\binom{j}{i}(-1)^{i+1}x^{-j-1}y^i \qquad {\big(}1+|y|<|x|{\big)} \\[+6mm] \frac{-1/y}{1-(1-x)/y} &= \sum_{i,j \geq 0}\binom{j}{i}(-1)^{i+1}x^iy^{-j-1} \qquad {\big(}1+|x|<|y|{\big)} \end{aligned}$$

$$\text{amoeba}(1-x-y)$$
 

$$ \sum_{i,j \geq 0}\binom{i+j}{i} x^iy^j $$

$$ \sum_{i,j \geq 0}\binom{j}{i}(-1)^{i+1}x^{-j-1}y^i $$

$$ \sum_{i,j \geq 0}\binom{j}{i}(-1)^{i+1}x^iy^{-j-1} $$

$$\text{amoeba}(1-x-y)$$
 

Theorem (GKZ 1994)

If \(G\) and \(H\) are coprime polynomials then the convergent Laurent expansions of \(F(\mathbf{z})=G(\mathbf{z})/H(\mathbf{z})\) are in bijection with the connected components of \(\text{amoeba}(H)^c\). 

\(\mathcal{D} = \text{Relog}^{-1}(B)\) then

$$ f_\mathbf{i} = \frac{1}{(2\pi i)^d} \int_{T(\mathbf{z})} \frac{F(\mathbf{z})}{\mathbf{z}^{\mathbf{i} + \mathbf{1}}} \, d\mathbf{z}$$
for any \(\mathbf{z} \in \mathcal{D}\).

Theorem (GKZ 1994)

If \(G\) and \(H\) are coprime polynomials then the convergent Laurent expansions of \(F(\mathbf{z})=G(\mathbf{z})/H(\mathbf{z})\) are in bijection with the connected components of \(\text{amoeba}(H)^c\). 

If the domain of convergence of the series \(\displaystyle F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{Z}^d} f_{\mathbf{i}}\mathbf{z}^\mathbf{i}\) is

\(\mathcal{D} = \text{Relog}^{-1}(B)\) then

$$ f_\mathbf{i} = \frac{1}{(2\pi i)^d} \int_{\color{red}T(\mathbf{z})} \frac{F(\mathbf{z})}{\mathbf{z}^{\mathbf{i} + \mathbf{1}}} \, d\mathbf{z}$$
for any \(\mathbf{z} \in \mathcal{D}\).

Theorem (GKZ 1994)

If \(G\) and \(H\) are coprime polynomials then the convergent Laurent expansions of \(F(\mathbf{z})=G(\mathbf{z})/H(\mathbf{z})\) are in bijection with the connected components of \(\text{amoeba}(H)^c\). 

If the domain of convergence of the series \(\displaystyle F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{Z}^d} f_{\mathbf{i}}\mathbf{z}^\mathbf{i}\) is

Theorem (GKZ 1994)

If \(G\) and \(H\) are coprime polynomials then the convergent Laurent expansions of \(F(\mathbf{z})=G(\mathbf{z})/H(\mathbf{z})\) are in bijection with the connected components of \(\text{amoeba}(H)^c\). 

If the domain of convergence of the series \(\displaystyle F(\mathbf{z}) = \sum_{\mathbf{i}\in\mathbb{Z}^d} f_{\mathbf{i}}\mathbf{z}^\mathbf{i}\) is

\(\mathcal{D} = \text{Relog}^{-1}(B)\) then

$$ f_\mathbf{i} = \frac{1}{(2\pi i)^d} \int_{\color{red}\text{Relog}^{-1}(\mathbf{x})} \frac{F(\mathbf{z})}{\mathbf{z}^{\mathbf{i} + \mathbf{1}}} \, d\mathbf{z}$$
for any \(\mathbf{x} \in B\).

\((1 - x - y - 6xy - x^2y^2)^{-1}\) has 5 convergent Laurent expansions

We can approximate \(\text{amoeba}(H)\) by taking many roots \(H(a,b)=0\) and plotting \((\log|a|,\log|b|)\).

Can we do better?

We can approximate \(\text{amoeba}(H)\) by taking many roots \(H(a,b)=0\) and plotting \((\log|a|,\log|b|)\).

Can we do better?

Corollary of Multivariate CIF

If \(\mathbf{x} \in \partial \text{amoeba}(H)\) then \(\mathbf{x} = \text{Relog}(\mathbf{w})\) for some \(\mathbf{w}\in\mathcal{V}\).

We can approximate \(\text{amoeba}(H)\) by taking many roots \(H(a,b)=0\) and plotting \((\log|a|,\log|b|)\).

Can we do better?

Corollary of Multivariate CIF

If \(\mathbf{x} \in \partial \text{amoeba}(H)\) then \(\mathbf{x} = \text{Relog}(\mathbf{w})\) for some \(\mathbf{w}\in\mathcal{V}\).
 

Minimal points are defined by \(\mathcal{V} \cap \partial \mathcal{D}\) for each expansion.

We can approximate \(\text{amoeba}(H)\) by taking many roots \(H(a,b)=0\) and plotting \((\log|a|,\log|b|)\).

Can we do better?

Corollary of Multivariate CIF

If \(\mathbf{x} \in \partial \text{amoeba}(H)\) then \(\mathbf{x} = \text{Relog}(\mathbf{w})\) for some \(\mathbf{w}\in\mathcal{V}\).
 

Minimal points are defined by \(\mathcal{V} \cap \partial \mathcal{D}\) for each expansion.

How can we characterize minimal points?

Given \(f: \mathbb{C}^d \rightarrow \mathbb{C}\) we define the logarithmic gradient
 

$$ (\nabla_{\text{log}}f)(\mathbf{z}) = {\big(}z_1f_{z_1},\dots,z_df_{z_d}{\big)}$$
Theorem (Mikhalkin 2000)
If \(\mathbf{w} \in \mathcal{V} \cap \partial \mathcal{D}\) then \((\nabla_{\text{log}}H)(\mathbf{w})\) is a multiple of a real vector.

 

Given \(f: \mathbb{C}^d \rightarrow \mathbb{C}\) we define the logarithmic gradient
 

$$ (\nabla_{\text{log}}f)(\mathbf{z}) = {\big(}z_1f_{z_1},\dots,z_df_{z_d}{\big)}$$
Theorem (Mikhalkin 2000)
If \(\mathbf{w} \in \mathcal{V} \cap \partial \mathcal{D}\) then \((\nabla_{\text{log}}H)(\mathbf{w})\) is a multiple of a real vector.

Corollary: The contour

$$\mathcal{C}(H) = \left\{\text{Relog}(\mathbf{z}) : H(\mathbf{z})=0 \text{ and } (\nabla_{\text{log}}H)(\mathbf{z})=\lambda \mathbf{v} \text{ for some } \mathbf{v} \in \mathbb{R}^d\right\}$$
is a superset of the amoeba boundary.

Given \(f: \mathbb{C}^d \rightarrow \mathbb{C}\) we define the logarithmic gradient
 

$$ (\nabla_{\text{log}}f)(\mathbf{z}) = {\big(}z_1f_{z_1},\dots,z_df_{z_d}{\big)}$$
Theorem (Mikhalkin 2000)
If \(\mathbf{w} \in \mathcal{V} \cap \partial \mathcal{D}\) then \((\nabla_{\text{log}}H)(\mathbf{w})\) is a multiple of a real vector.

Theobold (2002): Use homotopy tracking to solve the system

$$ H(x,y) = 0 \qquad xH_x(x,y) = t \, yH_y(x,y) $$
and plot curves \((\log|x(t)|,\log|y(t)|)\) for \(t\in\mathbb{R}\).

\(\mathcal{C}(H)\)

$$1-x-y$$
 

\(\mathcal{C}(H)\)

$$1-x-y$$
 

\(\mathcal{C}(H)\)

$$1 - x - y - 6xy - x^2y^2$$

\(\mathcal{C}(H)\)

$$1 - x - y - 6xy - x^2y^2$$

$$1 + 10(x^2y + xy^2 + x + y + 5xy)(1+x+y)$$

\(\mathcal{C}(H)\)

\(\mathcal{C}(H)\)

$$1 + 10(x^2y + xy^2 + x + y + 5xy)(1+x+y)$$

$$(x^2y + xy^2 + x + y + 41xy/10)(1+x+y)$$

\(\mathcal{C}(H)\)

\(\mathcal{C}(H)\)

$$(x^2y + xy^2 + x + y + 41xy/10)(1+x+y)$$

Let \(\Omega\) be the set of connected components of \(\text{amoeba}(H)^c\).

The Newton polytope \(\mathcal{N}(H)\) is the convex hull of \(\text{support(H)}\).

$$\mathcal{N}(1-x-y)$$
 

$$\mathcal{N}(1 - x - y - 6xy - x^2y^2)$$

Let \(\Omega\) be the set of connected components of \(\text{amoeba}(H)^c\).

The Newton polytope \(\mathcal{N}(H)\) is the convex hull of \(\text{support(H)}\).

Theorem (GKZ 1994 / Forsberg, Passare, Tsikh 2000)
There is an injective map \(\nu\) from \(\Omega\) to the integer points of \(\mathcal{N}(H)\). Every vertex of \(\mathcal{N}(H)\) is in the image of \(\nu\).

Let \(\Omega\) be the set of connected components of \(\text{amoeba}(H)^c\).

The Newton polytope \(\mathcal{N}(H)\) is the convex hull of \(\text{support(H)}\).

Theorem (GKZ 1994 / Forsberg, Passare, Tsikh 2000)
There is an injective map \(\nu\) from \(\Omega\) to the integer points of \(\mathcal{N}(H)\). Every vertex of \(\mathcal{N}(H)\) is in the image of \(\nu\).

If \(\mathbf{x} \in B\) then \(\nu(B) \in \mathbb{Z}^d\) is the vector with entries

$$ \nu(B)_k = \frac{1}{(2\pi i)^d} \int_{\text{Relog}^{-1}(\mathbf{x})} \frac{z_kH_{z_k}(\mathbf{z})}{H(\mathbf{z})} \, \frac{d\mathbf{z}}{z_1\cdots z_d}.$$

$$1-x-y$$
 

$$1 - x - y - 6xy - x^2y^2$$

$$(x^2y + xy^2 + x + y + 41xy/10)(1+x+y)$$

The dual cone to convex \(S \subset \mathbb{R}^d\) at \(\mathbf{v} \in S\) is the set of vectors \(\mathbf{x}\in\mathbb{R}^d\) such that \(\mathbf{x} \cdot \mathbf{v} \geq \mathbf{x} \cdot \mathbf{s}\) for all \(\mathbf{s}\in S\).

The recession cone of convex \(B \subset \mathbb{R}^d\) is the set of vectors \(\mathbf{x}\in\mathbb{R}^d\) such that \(\mathbf{x} + \mathbf{b} \in B\) for all \(\mathbf{b}\in B\).

\(B_1\)

\(B_2\)

\(B_3\)

\(\mathbf{v}_1\)

\(\mathbf{v}_2\)

\(\mathbf{v}_3\)

Theorem (GKZ 1994 / Forsberg, Passare, Tsikh 2000)
If \(\nu(B) = \mathbf{v}\) then the recession cone of \(B\) equals the dual cone to \(\mathcal{N}(H)\) at \(\mathbf{v}\).

\(B_1\)

\(B_2\)

\(B_3\)

\(\mathbf{v}_1\)

\(\mathbf{v}_2\)

\(\mathbf{v}_3\)

Theorem (GKZ 1994 / Forsberg, Passare, Tsikh 2000)
If \(\nu(B) = \mathbf{v}\) then the recession cone of \(B\) equals the dual cone to \(\mathcal{N}(H)\) at \(\mathbf{v}\).

This helps visualize the amoeba complement.


 

Theorem (GKZ 1994 / Forsberg, Passare, Tsikh 2000)
If \(\nu(B) = \mathbf{v}\) then the recession cone of \(B\) equals the dual cone to \(\mathcal{N}(H)\) at \(\mathbf{v}\).

This helps visualize the amoeba complement.


Note: Interior points of \(\mathbb{Z}^d \cap \mathcal{N}\) correspond to the bounded components of \(\text{amoeba}(H)^c\).

Theorem (GKZ 1994 / Forsberg, Passare, Tsikh 2000)
If \(\nu(B) = \mathbf{v}\) then the recession cone of \(B\) equals the dual cone to \(\mathcal{N}(H)\) at \(\mathbf{v}\).

This helps visualize the amoeba complement.


Note: Interior points of \(\mathbb{Z}^d \cap \mathcal{N}\) correspond to the bounded components of \(\text{amoeba}(H)^c\).

Note: Vertices of \(\mathbb{Z}^d \cap \mathcal{N}\) correspond to components of \(\text{amoeba}(H)^c\) whose recession cones have non-empty interior.

$$1 + 10(x^2y + xy^2 + x + y + 5xy)(1+x+y)$$

$$1 + 10(x^2y + xy^2 + x + y + 5xy)(1+x+y)$$

The amoeba "thins out" as it goes off to infinity.

How can we describe the limit directions (tentacles) in

$$ \lim_{M\rightarrow\infty} {\Big(} \frac{\text{amoeba}(H)}{M} \;\;\cap\;\; \text{unit sphere} {\Big)} $$

The amoeba "thins out" as it goes off to infinity.

How can we describe the limit directions (tentacles) in

$$ \lim_{M\rightarrow\infty} {\Big(} \frac{\text{amoeba}(H)}{M} \;\;\cap\;\; \text{unit sphere} {\Big)} $$

They can be deduced from the normal fan of \(\mathcal{N}(H)\).

The amoeba "thins out" as it goes off to infinity.

How can we describe the limit directions (tentacles) in

$$ \lim_{M\rightarrow\infty} {\Big(} \frac{\text{amoeba}(H)}{M} \;\;\cap\;\; \text{unit sphere} {\Big)} $$

They can be deduced from the normal fan of \(\mathcal{N}(H)\).

Theorem: The cone over the limit directions is the non-Archimedian tropical hypersurface \(\mathcal{T}(H)\) defined by \(H\).

The amoeba "thins out" as it goes off to infinity.

How can we describe the limit directions (tentacles) in

$$ \lim_{M\rightarrow\infty} {\Big(} \frac{\text{amoeba}(H)}{M} \;\;\cap\;\; \text{unit sphere} {\Big)} $$

They can be deduced from the normal fan of \(\mathcal{N}(H)\).

“Tropical geometry is a combinatorial shadow of algebraic geometry.” -- Maclagan and Sturmfels (2015)

The amoeba "thins out" as it goes off to infinity.

How can we describe the limit directions (tentacles) in

$$ \lim_{M\rightarrow\infty} {\Big(} \frac{\text{amoeba}(H)}{M} \;\;\cap\;\; \text{unit sphere} {\Big)} $$

They can be deduced from the normal fan of \(\mathcal{N}(H)\).

“Amoebas are shadows of algebraic varieties and tropical varieties are their combinatorial spirit.” -- Timo de Wolff (2017)

$$\mathcal{T}(H)$$

$$1 + 10(x^2y + xy^2 + x + y + 5xy)(1+x+y)$$

$$\text{amoeba}(H)$$

$$\mathcal{T}(H)$$

$$1 + 10(x^2y + xy^2 + x + y + 5xy)(1+x+y)$$

$$\text{amoeba}(H)$$

$$1-x-y-z+xyz$$

Lopsided Approximation (de Wolff, 2016): Approximation based on lopsided amoebas and cyclic resultants.

PolynomialAmoebas.jl (Timme, 2018): Amoeba sketching using the Passare-Rullgård spine and polygon refinements.

amoebas.ru (Sadykov and Zhukov, 2023): Approximations based on growing parallelpipes in amoeba complements by numerically approximating jumps in the order map \(\nu(\mathbf{x})\).

Now we focus on diagonals of rational functions.

Because we can increase dimension, the class of rational diagonals is more expressive than it may seem.

Recall decidability of asymptotics is known for algebraic functions and open for D-finite functions.

Diagonals fit into the interesting part of the hierarchy.

Theorem

If \(F(x,y) = G(x,y)/H(x,y)\) is a bivariate rational function then \(\Delta F\) is algebraic.

Proof Idea

$$ \sum_{n \geq 0} f_{n,n}t^n = \left[x^{-1}\right] x^{-1} \sum_{i,n \geq 0} f_{i,n} x^{i-n}t^n = \frac{1}{2\pi i} \int_\mathcal{C_{|t|}} \frac{G(x,t/x)}{x H(x,t/x)} dx$$

Theorem

If \(F(x,y) = G(x,y)/H(x,y)\) is a bivariate rational function then \(\Delta F\) is algebraic.

Proof Idea

$$ \sum_{n \geq 0} f_{n,n}t^n = \left[x^{-1}\right] x^{-1} \sum_{i,n \geq 0} f_{i,n} x^{i-n}t^n = \frac{1}{2\pi i} \int_\mathcal{C_{|t|}} \frac{G(x,t/x)}{x H(x,t/x)} dx$$

Theorem

If \(F(x,y) = G(x,y)/H(x,y)\) is a bivariate rational function then \(\Delta F\) is algebraic.

Proof Idea

$$ \sum_{n \geq 0} f_{n,n}t^n = \left[x^{-1}\right] x^{-1} \sum_{i,n \geq 0} f_{i,n} x^{i-n}t^n = \frac{1}{2\pi i} \int_\mathcal{C_{|t|}} \frac{G(x,t/x)}{x H(x,t/x)} dx$$

For fixed \(t\) this is a sum of residues at algebraic roots \(x_k(t)\) of \(H(x,t/x)=0\).

Theorem

If \(F(x,y) = G(x,y)/H(x,y)\) is a bivariate rational function then \(\Delta F\) is algebraic.

Note: Only the poles with \(x_k(t)\rightarrow0\) as \(t\rightarrow0\) will be inside the curve \(\mathcal{C}_{|t|}\) for \(t\) near the origin.
 

Bostan, Dumont, Salvy (2017): Fast algorithm to compute minimal polynomial of \(\Delta F\) using resultants.

Fast algorithm implemented in Sage by P. Tao (2025).

Example (Central Binomial Coefficients)

$$\Delta\left(\frac{1}{1-x-y}\right) = (1-4t)^{-1}$$

Fast algorithm implemented in Sage by P. Tao (2025).

Example (Balanced multiset problem)

By comparing computing initial terms we can prove the diagonal is \((1+t^2)/((1-t)(1-t^2)(1-t^3))\).

Conversely, every algebraic diagonal is a rational diagonal (in one additional variable).

Theorem

If \(f(\mathbf{x})\) is an algebraic function in \(d\) variables then there exists a rational function \(R(\mathbf{x},y)\) in \(d+1\) variables such that
 

$$\left[\mathbf{x}^\mathbf{r}\right]f(\mathbf{x}) = \left[\mathbf{x}^\mathbf{r}y^{|\mathbf{r}|}\right]R(\mathbf{x},y)$$

where \(|\mathbf{r}| = r_1 + \cdots + r_d\).

Theorem (Furstenberg 1967)

If \(f(\mathbf{x})\) with \(f(\mathbf{0})=0\) has minimal polynomial \(P(\mathbf{x},y)\) with \(P_y(\mathbf{0},0)\neq0\) then

$$\left[\mathbf{x}^\mathbf{r}\right]f(\mathbf{x}) = \left[\mathbf{x}^\mathbf{r}y^{|\mathbf{r}|}\right] \left(\frac{y^2P_y(y\mathbf{x},y)}{P(y\mathbf{x},y)}\right).$$

Theorem (Furstenberg 1967)

If \(f(\mathbf{x})\) with \(f(\mathbf{0})=0\) has minimal polynomial \(P(\mathbf{x},y)\) with \(P_y(\mathbf{0},0)\neq0\) then

$$\left[\mathbf{x}^\mathbf{r}\right]f(\mathbf{x}) = \left[\mathbf{x}^\mathbf{r}y^{|\mathbf{r}|}\right] \left(\frac{y^2P_y(y\mathbf{x},y)}{P(y\mathbf{x},y)}\right).$$

Proof

Expand the series and do elementary algebra.

Example (Catalan Numbers)

The function
 

$$f(x) = \frac{1-\sqrt{1-4x}}{2x} - 1$$
has minimal polynomial \(P(x,y) = x(y+1)^2-y\) and

$$f(x) = 1 + \Delta\left(\frac{y(1-2xy^2-2xy)}{1-x(1+y)^2}\right).$$

Example (Catalan Numbers 2)

The function
 

$$f(x) = x \cdot \frac{1-\sqrt{1-4x}}{2x} $$
has minimal polynomial \(P(x,y) = y^2-y+x\) and

$$xf(x) = \Delta\left(\frac{y(1-2y)}{1-x-y}\right).$$

Example (Binary Trees by Vertices and Leaves)

Recall \(B(u,z) = uz + 2zB(u,z) + zB(u,z)^2\) so

$$ \left[u^iz^n\right]B(u,z) = \left[u^iz^ny^{i+n}\right]\frac{y(2y^2z + 2yz - 1)}{uyz + y^2z + 2yz - 1}$$

Example (Binary Trees by Vertices and Leaves)

Recall \(B(u,z) = uz + 2zB(u,z) + zB(u,z)^2\) so

$$ \left[u^iz^n\right]B(u,z) = \left[u^iz^ny^{i+n}\right]\frac{y(2y^2z + 2yz - 1)}{uyz + y^2z + 2yz - 1}$$

Theorem (Denef and Lipshitz, 1987) 

Let \(f(\mathbf{x})\) be any algebraic function. There exists algebraic \(\phi(\mathbf{x})\) and rational \(W(\mathbf{x},y)\) such that

• \(f(\mathbf{x}) = W(\mathbf{x},\phi(\mathbf{x}))\)
• \(\phi\) satisfies the conditions of Furstenberg's Theorem.

Theorem (Denef and Lipshitz, 1987) 

Let \(f(\mathbf{x})\) be any algebraic function. There exists algebraic \(\phi(\mathbf{x})\) and rational \(W(\mathbf{x},y)\) such that

• \(f(\mathbf{x}) = W(\mathbf{x},\phi(\mathbf{x}))\)
• \(\phi\) satisfies the conditions of Furstenberg's Theorem.

In this case
 

$$\left[\mathbf{x}^\mathbf{r}\right]f(\mathbf{x}) = \left[\mathbf{x}^\mathbf{r}y^{|\mathbf{r}|}\right] \left(\frac{yW(y\mathbf{x},y)Q_y(y\mathbf{x},y)}{Q(y\mathbf{x},y)}\right)$$
where \(Q\) is the minimal polynomial of \(\phi\).

Unfortunately, their argument was non-constructive.

Unfortunately, their argument was non-constructive.

The condition \(P_y(\mathbf{0},0)=0\) means that multiple branches go through the origin. 

When \(d=1\) we can compute enough terms to separate the branch of interest and then perform a change of variables.

Unfortunately, their argument was non-constructive.

The condition \(P_y(\mathbf{0},0)=0\) means that multiple branches go through the origin. 

When \(d=1\) we can compute enough terms to separate the branch of interest and then perform a change of variables.

Let \(\text{ord}_x \left(g(x)\right)\) = lowest power of \(x\) in \(g\).

We need to compute at least \(\text{ord}_x\left( P_y(\mathbf{x},f(\mathbf{x}))\right)\) terms.

Unfortunately, their argument was non-constructive.

The condition \(P_y(\mathbf{0},0)=0\) means that multiple branches go through the origin. 

When \(d=1\) we can compute enough terms to separate the branch of interest and then perform a change of variables.

Let \(\text{ord}_x \left(g(x)\right)\) = lowest power of \(x\) in \(g\).

We need to compute at least \(\text{ord}_x\left( P_y(\mathbf{x},f(\mathbf{x}))\right)\) terms.

It is sufficient to take \(\text{ord}_x \left(\text{resultant}_y(P,P_y)\right)\) terms.

Example

The function \(f(x)=x\sqrt{1-x}\) has minimal polynomial
 

$$P(x,y)=y^2-x^2(1-x).$$
 

Example

The function \(f(x)=x\sqrt{1-x}\) has minimal polynomial
 

$$P(x,y)=y^2-x^2(1-x).$$
Since \(\text{resultant}_y(P,P_y) = 4x^{\color{red}2}(x-1)\) and \(f(x) = x - x^2/2 + \cdots\) we write

$$P(x,x-x^2/2+x^2y) = \frac{x^3}{4}\underbrace{\left[4xy^2 + 4(2-x)y + x\right]}_{Q(x,y)}.$$
 

Example

The function \(f(x)=x\sqrt{1-x}\) has minimal polynomial
 

$$P(x,y)=y^2-x^2(1-x).$$
Since \(\text{resultant}_y(P,P_y) = 4x^{\color{red}2}(x-1)\) and \(f(x) = x - x^2/2 + \cdots\) we write

$$P(x,x-x^2/2+x^2y) = \frac{x^3}{4}\underbrace{\left[4xy^2 + 4(2-x)y + x\right]}_{Q(x,y)}.$$
Thus \(\displaystyle f(x) = x - x^2/2 + x^2 \Delta\left(\frac{y^2Q_y(xy,y)}{Q(xy,y)}\right)\).

Example

The function \(f(x)=x\sqrt{1-x}\) has minimal polynomial
 

$$P(x,y)=y^2-x^2(1-x).$$
Since \(\text{resultant}_y(P,P_y) = 4x^{\color{red}2}(x-1)\) and \(f(x) = x - x^2/2 + \cdots\) we write

$$P(x,x-x^2/2+x^2y) = \frac{x^3}{4}\underbrace{\left[4xy^2 + 4(2-x)y + x\right]}_{Q(x,y)}.$$
Thus \(\displaystyle f(x) = \Delta\left(xy - (xy)^2/2 + (xy)^2 \frac{4y(2xy^2-xy+2)}{8+x-4xy+4xy^2}\right)\).

Theorem (Safonov 2000)

If \(f(\mathbf{0})=0\) then there is a computable rational function \(R(\mathbf{x},y)\) and a unimodular matrix \(M\) such that

$$ \left[\mathbf{x}^\mathbf{r}\right]f(\mathbf{x}) = \left[\mathbf{x}^{M\mathbf{r}}y^{|M\mathbf{r}|}\right]R(\mathbf{x},y)$$

Theorem (Safonov 2000)

If \(f(\mathbf{0})=0\) then there is a computable rational function \(R(\mathbf{x},y)\) and a unimodular matrix \(M\) such that

$$ \left[\mathbf{x}^\mathbf{r}\right]f(\mathbf{x}) = \left[\mathbf{x}^{M\mathbf{r}}y^{|M\mathbf{r}|}\right]R(\mathbf{x},y)$$
Proof Idea
Effective resolution of singularities by setting

$$y = f_{\leq q}(\mathbf{x}) + w$$

and then repeated monomial transformations of the form

$$\begin{aligned} w&=wz_i^\mu \\ z_i &= z_i \\ z_j &= z_iz_j \quad (i \neq j) \end{aligned}$$

Greenwood, M., Ruza, Wilson (2026+)

Implementation in Sage with study of 50+ multivariate algebraic generating functions from the literature.
 

Example (Planar Maps)

The generating function \(F(x,t)\) tracking planar rooted maps by edges in the outer face \((x)\) and total edges \((t)\) is a root of

$$\begin{aligned}P(x,t,y) &= 27y^4x^2t^3 - 54xt^2(x^2t - x + 1)y^3 \\ &+ t(27x^4t^2 - 90x^3t - x^3 + 108x^2t + 27x^2 - 54x + 27)y^2 \\&+ x(36xt + x - 54t)(x^2t - x + 1)y \\&+ 16x^4t^2 + 8x^4t + x^4 - 36x^3t - x^3 + 27x^2t. \end{aligned}$$ Goulden and Jackson: "no convenient expression" for sequence

When \(d \geq 2\) rational diagonals can be transcendental.

Example

$$[t^n]\Delta\left(\frac{1}{1-x-y-z}\right) = \frac{(3n)!}{(n!)^3} \sim \frac{\sqrt{3}}{2} \, 27^n \, n^{-1}$$

When \(d \geq 2\) rational diagonals can be transcendental.

Example

$$[t^n]\Delta\left(\frac{1}{1-x-y-z}\right) = \frac{(3n)!}{(n!)^3} \sim \frac{\sqrt{3}}{2} \, 27^n \, n^{-1}$$

Christol (1984): Every rational diagonal is D-finite.

When \(d \geq 2\) rational diagonals can be transcendental.

Example

$$[t^n]\Delta\left(\frac{1}{1-x-y-z}\right) = \frac{(3n)!}{(n!)^3} \sim \frac{\sqrt{3}}{2} \, 27^n \, n^{-1}$$

Christol (1984): Every rational diagonal is D-finite.

Lipshitz (1988): Every D-finite diagonal is D-finite.

When \(d \geq 2\) rational diagonals can be transcendental.

Example

$$[t^n]\Delta\left(\frac{1}{1-x-y-z}\right) = \frac{(3n)!}{(n!)^3} \sim \frac{\sqrt{3}}{2} \, 27^n \, n^{-1}$$

Christol (1984): Every rational diagonal is D-finite.

Lipshitz (1988): Every D-finite diagonal is D-finite.

How fast can we compute a D-finite equation?
This is the domain of creative telescoping.

Very powerful algorithmic framework for sequences and functions. See talk of Hadrien Brochet at 15:30 today.

For \(F(t,\mathbf{z})\) we have

$$ \begin{aligned} (\Delta F)(t) &= \left[z_1^{-1} \cdots z_d^{-1}\right] (z_1^{-1} \cdots z_d^{-1}) F\left(\frac{t}{z_1\cdots z_d},z_1,\dots,z_d\right) \\[5mm]  \end{aligned}$$

Very powerful algorithmic framework for sequences and functions. See talk of Hadrien Brochet at 15:30 today.

For \(F(t,\mathbf{z})\) we have

$$ \begin{aligned} (\Delta F)(t) &= \left[z_1^{-1} \cdots z_d^{-1}\right] (z_1^{-1} \cdots z_d^{-1}) F\left(\frac{t}{z_1\cdots z_d},z_1,\dots,z_d\right) \\[5mm] &= \int_{\text{Relog}^{-1}(\mathbf{x})}\frac{F\left(\frac{t}{z_1\cdots z_d},z_1,\dots,z_d\right)}{z_1\cdots z_d}\, d\mathbf{z} \\ \end{aligned}$$

We thus aim to compute annihilators of period integrals.

Very powerful algorithmic framework for sequences and functions. See talk of Hadrien Brochet at 15:30 today.

Problem: Given rational \(R(t,\mathbf{z})\) find

• a D-finite operator \(\mathcal{L}\) in \(t\) and \(\partial_t\)
   
• rational functions \(C_1,\dots,C_d\) with \(\text{poles}(C_k) \subset \text{poles}(R)\)

such that

$$\mathcal{L}(R) = \sum_{k=1}^d(\partial_k C_k)(t,\mathbf{z}).$$

$$\mathcal{L}\left(\int_\Gamma R(t,\mathbf{z})d\mathbf{z}\right) = \sum_{k=1}^d \int_\Gamma (\partial_k C_k)(t,\mathbf{z}) d\mathbf{z} = 0$$

$$\mathcal{L}\left(\int_\Gamma R(t,\mathbf{z})d\mathbf{z}\right) = \sum_{k=1}^d \int_\Gamma (\partial_k C_k)(t,\mathbf{z}) d\mathbf{z} = 0$$

Note: \(\mathcal{L}\) annihilates diagonals of all Laurent expansions.

We call \(\mathcal{L}\) a telescoper and the \(C_k\) (regular) certificates.

$$\mathcal{L}\left(\int_\Gamma R(t,\mathbf{z})d\mathbf{z}\right) = \sum_{k=1}^d \int_\Gamma (\partial_k C_k)(t,\mathbf{z}) d\mathbf{z} = 0$$

Note: \(\mathcal{L}\) annihilates diagonals of all Laurent expansions.

We call \(\mathcal{L}\) a telescoper and the \(C_k\) (regular) certificates.

Bostan, Lairez, Salvy (2013): Algorithm to compute \(\mathcal{L}\) in bit complexity polynomial in \(\delta^d\) where \(\delta\) is a degree bound.

$$\mathcal{L}\left(\int_\Gamma R(t,\mathbf{z})d\mathbf{z}\right) = \sum_{k=1}^d \int_\Gamma (\partial_k C_k)(t,\mathbf{z}) d\mathbf{z} = 0$$

Note: \(\mathcal{L}\) annihilates diagonals of all Laurent expansions.

We call \(\mathcal{L}\) a telescoper and the \(C_k\) (regular) certificates.

Bostan, Lairez, Salvy (2013): Algorithm to compute \(\mathcal{L}\) in bit complexity polynomial in \(\delta^d\) where \(\delta\) is a degree bound.

Note: Generically certificates have size \(\delta^{(1-o(1))d^2}\) (impractical).

First homogenize to control the pole at infinity to obtain

$$F_\text{hom}(t,z_0,\dots,z_d) = z_0^{-d-1} F(t,z_1/z_0, \dots, z_d/z_0)$$

Write \(F_\text{hom} = a/f^\ell\) for positive integer \(\ell\) and \(f\) square-free.

 

First homogenize to control the pole at infinity to obtain

$$F_\text{hom}(t,z_0,\dots,z_d) = z_0^{-d-1} F(t,z_1/z_0, \dots, z_d/z_0)$$

Write \(F_\text{hom} = a/f^\ell\) for positive integer \(\ell\) and \(f\) square-free.

Reducing \(a\) modulo Gröbner basis of \(\text{Jac}(f) = (\partial_{z_0}f,\dots,\partial_{z_d}f)\) gives \(a = r + \sum_{k=0}^d p_k \cdot (\partial_{z_k} f)\) 

First homogenize to control the pole at infinity to obtain

$$F_\text{hom}(t,z_0,\dots,z_d) = z_0^{-d-1} F(t,z_1/z_0, \dots, z_d/z_0)$$

Write \(F_\text{hom} = a/f^\ell\) for positive integer \(\ell\) and \(f\) square-free.

Reducing \(a\) modulo Gröbner basis of \(\text{Jac}(f) = (\partial_{z_0}f,\dots,\partial_{z_d}f)\) gives \(a = r + \sum_{k=0}^d p_k \cdot (\partial_{z_k} f)\) and for \(\ell>1\)

$$F_\text{hom} = \frac{r}{f^\ell} + \frac{\frac{1}{\ell-1}\sum_{k=0}^d \partial_{z_k}p_k}{f^{\ell-1}} + \sum_{k=0}^d \partial_{z_k}\left(\frac{-p_k}{(\ell-1)f^{\ell-1}}\right)$$

First homogenize to control the pole at infinity to obtain

$$F_\text{hom}(t,z_0,\dots,z_d) = z_0^{-d-1} F(t,z_1/z_0, \dots, z_d/z_0)$$

Write \(F_\text{hom} = a/f^\ell\) for positive integer \(\ell\) and \(f\) square-free.

Reducing \(a\) modulo Gröbner basis of \(\text{Jac}(f) = (\partial_{z_0}f,\dots,\partial_{z_d}f)\) gives \(a = r + \sum_{k=0}^d p_k \cdot (\partial_{z_k} f)\) and for \(\ell>1\)

$$F_\text{hom} = \frac{r}{f^\ell} + \frac{\frac{1}{\ell-1}\sum_{k=0}^d \partial_{z_k}p_k}{f^{\ell-1}} + {\color{red} \sum_{k=0}^d \partial_{z_k}\left(\frac{-p_k}{(\ell-1)f^{\ell-1}}\right)}$$

First homogenize to control the pole at infinity to obtain

$$F_\text{hom}(t,z_0,\dots,z_d) = z_0^{-d-1} F(t,z_1/z_0, \dots, z_d/z_0)$$

Write \(F_\text{hom} = a/f^\ell\) for positive integer \(\ell\) and \(f\) square-free.

Reducing \(a\) modulo Gröbner basis of \(\text{Jac}(f) = (\partial_{z_0}f,\dots,\partial_{z_d}f)\) gives \(a = r + \sum_{k=0}^d p_k \cdot (\partial_{z_k} f)\) and for \(\ell>1\)

$$F_\text{hom} \equiv \frac{r}{f^\ell} + \frac{\frac{1}{\ell-1}\sum_{k=0}^d \partial_{z_k}p_k}{f^{\ell-1}} $$

First homogenize to control the pole at infinity to obtain

$$F_\text{hom}(t,z_0,\dots,z_d) = z_0^{-d-1} F(t,z_1/z_0, \dots, z_d/z_0)$$

Write \(F_\text{hom} = a/f^\ell\) for positive integer \(\ell\) and \(f\) square-free.

Reducing \(a\) modulo Gröbner basis of \(\text{Jac}(f) = (\partial_{z_0}f,\dots,\partial_{z_d}f)\) gives \(a = r + \sum_{k=0}^d p_k \cdot (\partial_{z_k} f)\) and for \(\ell>1\)

$$F_\text{hom} \equiv \frac{r}{f^\ell} + {\color{lightblue} \frac{\frac{1}{\ell-1}\sum_{k=0}^d \partial_{z_k}p_k}{f^{\ell-1}}} $$

Repeat the process to express \(F_\text{hom}\) as a sum of polynomials reduced modulo \(\text{Jac}(f)\) over powers of \(f\) modulo certificates.

BLS 2013 (via Griffiths 1969): If \(\mathcal{V}(\text{Jac}(f))\) is smooth then the reduction \([R]\) lies in a vector space of dimension \(\leq \delta^d\).

Repeat the process to express \(F_\text{hom}\) as a sum of polynomials reduced modulo \(\text{Jac}(f)\) over powers of \(f\) modulo certificates.

BLS 2013 (via Griffiths 1969): If \(\mathcal{V}(\text{Jac}(f))\) is smooth then the reduction \([R]\) lies in a vector space of dimension \(\leq \delta^d\).

Algorithm: Compute reductions \([R], \, [\partial_t R], \, [\partial_t^2 R],\dots\) until a relation is found.

Repeat the process to express \(F_\text{hom}\) as a sum of polynomials reduced modulo \(\text{Jac}(f)\) over powers of \(f\) modulo certificates.

BLS 2013 (via Griffiths 1969): If \(\mathcal{V}(\text{Jac}(f))\) is smooth then the reduction \([R]\) lies in a vector space of dimension \(\leq \delta^d\).

Algorithm: Compute reductions \([R], \, [\partial_t R], \, [\partial_t^2 R],\dots\) until a relation is found.

Non-smooth case can be handled by deformation, but there is a better way...

Key Idea in Smooth Case: When \((\partial_{z_0}f,\dots,\partial_{z_d}f)\) is a regular sequence its syzygies are generated by trivial syzygies.

Lairez (2016): Create algebraic machinery to capture and reduce using higher order relations between syzygies.

Key Idea in Smooth Case: When \((\partial_{z_0}f,\dots,\partial_{z_d}f)\) is a regular sequence its syzygies are generated by trivial syzygies.

Lairez (2016): Create algebraic machinery to capture and reduce using higher order relations between syzygies.

Lairez gave a MAGMA implementation of his algorithm.

Used to compute hundreds of Picard-Fuchs equations for parameterized hypersurfaces.

M. and Smith (2026): Implementation of Lairez's algorithm in Sage. Designed to interface with other Sage packages.

Implementation takes ~170 seconds total on 50 representative examples from my two books.

Example (Rigorous NSEW Quadrant Asymptotics) 

The kernel method (see exercises) implies the generating function for quadrant walks on NSEW steps has GF

$$ \Delta\left(\frac{(1+x)(1+y)}{1-txy(1/x+x+1/y+y)}\right)$$

Which D-finite functions are rational diagonals?

Which D-finite functions are rational diagonals?

Every rational diagonal is globally bounded: there exist non-zero \(a,b\in\mathbb{Z}\) such that \(aF(bz)\) has integer coefficients.

Example
\(F(z)=e^z\) is D-finite but not globally bounded.

Which D-finite functions are rational diagonals?

Every rational diagonal is globally bounded: there exist non-zero \(a,b\in\mathbb{Z}\) such that \(aF(bz)\) has integer coefficients.

Example
\(F(z)=e^z\) is D-finite but not globally bounded.

Conjecture (Christol, 1990): Every globally bounded D-finite function is a rational diagonal.

The \({}_3F_2\) hypergeometric function

$$ f(z) = \sum_{n \geq 0} \frac{(1/9)_n(4/9)_n(5/9)_n}{(1/3)_n(1)_n} \frac{z^n}{n!}, \quad (x)_n = x(x+1)\cdots(x+n-1)$$

is globally bounded and satisfies

$$ \begin{aligned}729z^2(z-1)f'''(z) &+ 81z(37z - 21)f''(z) \\ &+ 9(200z - 27)f'(z) + 20f(z) = 0 \end{aligned}$$

Open Problem (Christol 1986): Is \(f\) a rational diagonal?

Every globally bounded D-finite function is a G-function.

Corollary

Suppose \(F(\mathbf{z})\in\mathbb{Q}(\mathbf{z})\) is analytic at the origin. Then any diagonal coefficient sequence of \(F\) 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.

Every globally bounded D-finite function is a G-function.

Corollary

Suppose \(F(\mathbf{z})\in\mathbb{Q}(\mathbf{z})\) is analytic at the origin. Then any diagonal coefficient sequence of \(F\) 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.

Example (Denisov and Wachtel 2015)

The number \(w_n\) of NSEW-walks starting at \((1,1)\) and staying in \(0<y<2x\) satisfies \(w_n \sim C \, 4^n \, n^{-\pi/2\arctan 2}\). 

Diagonals capture behaviour of multivariate generating functions and are data structures for univariate sequences.

Rational diagonals capture algebraic behaviour too.
They can be studied using D-finite techniques.

Complex analysis in several variables is more complicated than the univariate theory, but many results generalize.

It is hard to picture things (even \(\mathbb{C}^2\) has 4 real dimensions) but polynomial amoebas are a useful tool.