User:Dom walden/Multivariate Analytic Combinatorics/Basics

Complex analysis in several variables

Vectors in multidimensional space

The spaces $\mathbb {C} ^{d}$ and $\mathbb {R} ^{d}$ are made up of ordered sets of $n$ complex or real (resp.) numbers

${\textbf {z}}=(z_{1},\cdots ,z_{d})\quad (z_{i}\in \mathbb {C} )$

${\textbf {x}}=(x_{1},\cdots ,x_{d})\quad (x_{i}\in \mathbb {R} )$

We write ${\textbf {z}}\in \mathbb {C} ^{d}$ or ${\textbf {x}}\in \mathbb {R} ^{d}$.

Polydisk and polytorus

For the vectors ${\textbf {a}}\in \mathbb {C} ^{d}$ and ${\textbf {r}}\in \mathbb {R} _{>0}^{d}$ the open polydisk centred at ${\textbf {a}}$ of radius ${\textbf {r}}$

$D_{\textbf {a}}({\textbf {r}})=\{{\textbf {z}}\in \mathbb {C} ^{d}:|z_{1}-a_{1}|<r_{1},\cdots ,|z_{d}-a_{d}|<r_{d}\}$

and the polytorus

$T_{\textbf {a}}({\textbf {r}})=\{{\textbf {z}}\in \mathbb {C} ^{d}:|z_{1}-a_{1}|=r_{1},\cdots ,|z_{d}-a_{d}|=r_{d}\}$

Multivariate Cauchy coefficient formula

This is the multivariate version of the Cauchy coefficient formula.

By the multiple Cauchy integral

$f(z)={\frac {1}{(2\pi i)^{n}}}\int _{T}{\frac {f(\zeta )d\zeta _{1}\cdots d\zeta _{n}}{(\zeta _{1}-z)\cdots (\zeta _{n}-z)}}={\frac {1}{(2\pi i)^{n}}}\int _{T}{\frac {f(\zeta )d\zeta }{(\zeta -z)}}$

and the fact that

${\frac {1}{\zeta -z}}=\sum _{|k|=0}^{\infty }{\frac {(z-a)^{k}}{(\zeta -a)^{k+1}}}$

we can re-write $f(z)$

$f(z)=\sum _{|k|=0}^{\infty }{\frac {1}{(2\pi i)^{n}}}\int _{T}{\frac {f(\zeta )d\zeta }{(\zeta -a)^{k+1}}}(z-a)^{k}=\sum _{|k|=0}^{\infty }c_{k}(z-a)^{k}$

where:

$c_{k}={\frac {1}{(2\pi i)^{n}}}\int _{T}{\frac {f(\zeta )d\zeta }{(\zeta -a)^{k+1}}}$

Domain of convergence

The domain of convergence of a power series is the set of points ${\textbf {z}}\in \mathbb {C} ^{d}$ such that the power series converges absolutely for some neighbourhood of ${\textbf {z}}$.

The associated or conjugate radii of convergence are the vectors ${\textbf {r}}\in \mathbb {R} _{>0}^{d}$ such that the power series converges in the domain $\{{\textbf {z}}\in \mathbb {C} ^{d}:|z_{1}-a_{1}|<r_{1},\cdots ,|z_{d}-a_{d}|<r_{d}\}$ and diverges in the domain $\{{\textbf {z}}\in \mathbb {C} ^{d}:|z_{1}-a_{1}|>r_{1},\cdots ,|z_{d}-a_{d}|>r_{d}\}$. Note that ${\textbf {r}}$ is not necessarily unique and there may be infinite such ${\textbf {r}}$.

In our example, ${\frac {1}{1-x-y}}$, the denominator is zero for $0\leq x\leq 1$ and $y=1-x$.

Topology

Multivariate generating functions

Multivariate formal power series

For a generating function in $d$ variables.

${\textbf {z}}=(z_{1},\cdots ,z_{d})\in \mathbb {C} ^{d}$, ${\textbf {n}}=(n_{1},\cdots ,n_{d})\in \mathbb {N} ^{d}$ and ${\textbf {z}}^{\textbf {n}}=z_{1}^{n_{1}}\cdots z_{d}^{n_{d}}$

The multivariate formal power series

$F({\textbf {z}})=\sum _{{\textbf {n}}\in \mathbb {N} ^{d}}f_{\textbf {n}}{\textbf {z}}^{\textbf {n}}=\sum _{(n_{1},\cdots ,n_{d})\in \mathbb {N} ^{d}}f_{n_{1},\cdots ,n_{d}}z_{1}^{n_{1}}\cdots z_{d}^{n_{d}}$

For example

${\frac {1}{1-x-y}}=\sum _{(n,m)\in \mathbb {N} ^{2}}{\binom {n+m}{m}}x^{m}y^{n}=\sum _{n\geq 0}\sum _{m\geq 0}{\binom {n+m}{m}}x^{m}y^{n}$

Diagonals

The central diagonal of a power series

$\Delta F({\textbf {z}})=\sum _{n\geq 0}f_{n,\cdots ,n}z^{n}$

For our example power series, ${\frac {1}{1-x-y}}$, we can represent it in two dimensions like below. The central diagonal is highlighted in green.

	$x^{0}$	$x^{1}$	$x^{2}$	$x^{3}$	$x^{4}$
$y^{0}$	$1x^{0}y^{0}$	$1x^{1}y^{0}$	$1x^{2}y^{0}$	$1x^{3}y^{0}$	$1x^{4}y^{0}$
$y^{1}$	$1x^{0}y^{1}$	$2x^{1}y^{1}$	$3x^{2}y^{1}$	$4x^{3}y^{1}$	$5x^{4}y^{1}$
$y^{2}$	$1x^{0}y^{2}$	$3x^{1}y^{2}$	$6x^{2}y^{2}$	$10x^{3}y^{2}$	$15x^{4}y^{2}$
$y^{3}$	$1x^{0}y^{3}$	$4x^{1}y^{3}$	$10x^{2}y^{3}$	$20x^{3}y^{3}$	$35x^{4}y^{3}$
$y^{4}$	$1x^{0}y^{4}$	$5x^{1}y^{4}$	$15x^{2}y^{4}$	$35x^{3}y^{4}$	$70x^{4}y^{4}$

We can generalise this to a diagonal along a ray r, where ${\textbf {r}}=(r_{1},\cdots ,r_{d})\in \mathbb {N} ^{d}$

$\Delta ^{\textbf {r}}F({\textbf {z}})=\sum _{n\geq 0}f_{nr_{1},\cdots ,nr_{d}}z^{n}$

For example

$\Delta ^{(2,1)}{\frac {1}{1-x-y}}=\sum _{n\geq 0}{\binom {2n+n}{n}}z^{n}$

which is represented below in green.

	$x^{0}$	$x^{1}$	$x^{2}$	$x^{3}$	$x^{4}$
$y^{0}$	$1x^{0}y^{0}$	$1x^{1}y^{0}$	$1x^{2}y^{0}$	$1x^{3}y^{0}$	$1x^{4}y^{0}$
$y^{1}$	$1x^{0}y^{1}$	$2x^{1}y^{1}$	$3x^{2}y^{1}$	$4x^{3}y^{1}$	$5x^{4}y^{1}$
$y^{2}$	$1x^{0}y^{2}$	$3x^{1}y^{2}$	$6x^{2}y^{2}$	$10x^{3}y^{2}$	$15x^{4}y^{2}$
$y^{3}$	$1x^{0}y^{3}$	$4x^{1}y^{3}$	$10x^{2}y^{3}$	$20x^{3}y^{3}$	$35x^{4}y^{3}$
$y^{4}$	$1x^{0}y^{4}$	$5x^{1}y^{4}$	$15x^{2}y^{4}$	$35x^{3}y^{4}$	$70x^{4}y^{4}$

Cauchy-Hadamard in several complex variables

Theorem

Let $\alpha$ be an n-dimensional vector of natural numbers ($\alpha =(\alpha _{1},\cdots ,\alpha _{n})\in \mathbb {N} ^{n}$) with $||\alpha ||=\alpha _{1}+\cdots +\alpha _{n}$, then $f(x)$ converges with radius of convergence $\rho =(\rho _{1},\cdots ,\rho _{n})\in \mathbb {R} ^{n}$ with $\rho ^{\alpha }=\rho _{1}^{\alpha _{1}}\cdots \rho _{n}^{\alpha _{n}}$ if and only if

$\limsup _{||\alpha ||\to \infty }{\sqrt[{||\alpha ||}]{|c_{\alpha }|\rho ^{\alpha }}}=1$

to the multidimensional power series

$\sum _{\alpha \geq 0}c_{\alpha }(z-a)^{\alpha }:=\sum _{\alpha _{1}\geq 0,\ldots ,\alpha _{n}\geq 0}c_{\alpha _{1},\ldots ,\alpha _{n}}(z_{1}-a_{1})^{\alpha _{1}}\cdots (z_{n}-a_{n})^{\alpha _{n}}$

Proof

Set $z=a+t\rho$ $(z_{i}=a_{i}+t\rho _{i})$, then

$\sum _{\alpha \geq 0}c_{\alpha }(z-a)^{\alpha }=\sum _{\alpha \geq 0}c_{\alpha }\rho ^{\alpha }t^{||\alpha ||}=\sum _{\mu \geq 0}\left(\sum _{||\alpha ||=\mu }|c_{\alpha }|\rho ^{\alpha }\right)t^{\mu }$

This is a power series in one variable $t$ which converges for $|t|<1$ and diverges for $|t|>1$. Therefore, by the Cauchy-Hadamard theorem for one variable

$\limsup _{\mu \to \infty }{\sqrt[{\mu }]{\sum _{||\alpha ||=\mu }|c_{\alpha }|\rho ^{\alpha }}}=1$

Setting $|c_{m}|\rho ^{m}=\max _{||\alpha ||=\mu }|c_{\alpha }|\rho ^{\alpha }$ gives us an estimate

$|c_{m}|\rho ^{m}\leq \sum _{||\alpha ||=\mu }|c_{\alpha }|\rho ^{\alpha }\leq (\mu +1)^{n}|c_{m}|\rho ^{m}$

Because ${\sqrt[{\mu }]{(\mu +1)^{n}}}\to 1$ as $\mu \to \infty$

${\sqrt[{\mu }]{|c_{m}|\rho ^{m}}}\leq {\sqrt[{\mu }]{\sum _{||\alpha ||=\mu }|c_{\alpha }|\rho ^{\alpha }}}\leq {\sqrt[{\mu }]{|c_{m}|\rho ^{m}}}\implies {\sqrt[{\mu }]{\sum _{||\alpha ||=\mu }|c_{\alpha }|\rho ^{\alpha }}}={\sqrt[{\mu }]{|c_{m}|\rho ^{m}}}\qquad (\mu \to \infty )$

Therefore

$\limsup _{||\alpha ||\to \infty }{\sqrt[{|\alpha |}]{|c_{\alpha }|\rho ^{\alpha }}}=\limsup _{\mu \to \infty }{\sqrt[{\mu }]{|c_{m}|\rho ^{m}}}=1$

Example

For the central diagonal of our example, $\Delta {\frac {1}{1-x-y}}=\sum _{n\geq 0}f_{n,n}x^{n}y^{n}$:

$\limsup _{n\to \infty }{\sqrt[{n}]{|f_{n,n}|x^{n}y^{n}}}=1\implies \limsup _{n\to \infty }|f_{n,n}|={\frac {1}{(xy)^{n}}}$

$x^{n}y^{n}$ is at its largest when $x=y={\frac {1}{2}}$ so that $\limsup _{n\to \infty }|f_{n,n}|=4^{n}$.

We know by Stirling's approximation that this is a good estimate.

But what about a diagonal along an arbitrary ray, like the above example $\Delta ^{(2,1)}{\frac {1}{1-x-y}}$?

$\limsup _{|n{\textbf {r}}|\to \infty }{\sqrt[{|n{\textbf {r}}|}]{|f_{2n,n}|x^{2n}y^{n}}}=1\implies \limsup _{|n{\textbf {r}}|\to \infty }|f_{2n,n}|={\frac {1}{(x^{2}y)^{n}}}$

If we keep $x=y={\frac {1}{2}}$ then $\limsup _{|n{\textbf {r}}|\to \infty }|f_{2n,n}|=8^{n}$

This isn't a good estimate.

Better to use $x={\frac {2}{3}},y={\frac {1}{3}}$ then $\limsup _{|n{\textbf {r}}|\to \infty }|f_{2n,n}|=\left({\frac {27}{4}}\right)^{n}=(6.75)^{n}$

Exponential bounds

We need a general way of finding the ${\textbf {z}}$ which minimises our estimate in the direction ${\textbf {r}}$.

Assuming $F({\textbf {z}})={\frac {G({\textbf {z}})}{H({\textbf {z}})}}$

The set of points $z$ where $H(z)=0$ is called the singular variety ${\mathcal {V}}$.

Define

$Relog({\textbf {z}})=(\log |z_{1}|,\cdots ,\log |z_{d}|)$

$amoeba(H)=\{Relog({\textbf {z}}):H({\textbf {z}})=0\}$

[Example of amoeba for 1 - x - y]

The domain of convergence of our function can now be defined as the complement of this amoeba

$amoeba(H)^{c}=\mathbb {R} ^{d}\setminus amoeba(H)$

Note that this may leave us with multiple unconnected components. Each one is for a different Laurent series expansion. Denote the component we are interested in as $B$

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

Minimising ${\textbf {w}}^{\textbf {r}}$ is difficult as it is a nonlinear function. It is easier to minimise a linear function

$h_{\textbf {r}}({\textbf {z}})=-\sum _{j=1}^{d}r_{j}\log |z_{j}|$

We define

$\nabla _{\log }H({\textbf {w}})=\left(w_{1}{\frac {\partial H({\textbf {w}})}{\partial w_{1}}},\cdots ,w_{d}{\frac {\partial H({\textbf {w}})}{\partial w_{d}}}\right)$

Lemma If ${\textbf {w}}\in {\mathcal {V}}\cap \partial {\mathcal {D}}$ and $\nabla _{\log }H({\textbf {w}})=\tau {\textbf {r}}$ $(\tau \neq 0)$ then ${\textbf {w}}$ is either a maximiser or minimiser for $h_{\textbf {r}}({\textbf {z}})$ on ${\overline {\mathcal {D}}}$.

Proof

Therefore, to find the minimiser of $h_{\textbf {r}}({\textbf {z}})$ we need to find the conditions under which $\nabla _{\log }H({\textbf {w}})$ is a scalar multiple of ${\textbf {r}}$. This means they are not linearly independent and therefore the matrix

${\begin{pmatrix}w_{1}{\frac {\partial H}{\partial z_{1}}}({\textbf {w}})&\cdots &w_{d}{\frac {\partial H}{\partial z_{d}}}({\textbf {w}})\\r_{1}&\cdots &r_{d}\end{pmatrix}}$

is rank deficient, or its 2 x 2 submatrices have zero determinants. This is equivalent to a system of equations referred to as the critical point equations

$H({\textbf {w}})=0\quad r_{j}w_{1}{\frac {\partial H}{\partial z_{1}}}({\textbf {w}})-r_{1}w_{j}{\frac {\partial H}{\partial z_{j}}}({\textbf {w}})=0\quad (2\leq j\leq d).$

But, even after finding our ${\textbf {z}}$, the estimate is only a bound and it may not be tight.

References

• Fuks, B. A. (1963). Theory of Analytic Functions of Several Complex Variables. American Mathematical Society, Providence, Rhode Island.
• Melczer, Stephen (2021). An Invitation to Analytic Combinatorics: From One to Several Variables (PDF). Springer Texts & Monographs in Symbolic Computation.
• Mishna, Marni (2020). Analytic Combinatorics: A Multidimensional Approach. Taylor & Francis Group, LLC.
• Pemantle, Robin; Wilson, Mark C.; Melczer, Stephen (2024). Analytic Combinatorics in Several Variables (PDF) (2nd ed.). Cambridge University Press.
• Shabat, B. V. (1992). Introduction to Complex Analysis. Part II: Functions of Several Variables. American Mathematical Society, Providence, Rhode Island.

As of 14th April 2024, this article is derived in whole or in part from Wikipedia. The copyright holder has licensed the content in a manner that permits reuse under CC BY-SA 3.0 and GFDL. All relevant terms must be followed.