Deep Forest by Emily Carr (1931)
Under generic assumptions, the methods of ACSV give explicit asymptotics.
When \(F\) is combinatorial, these methods are rigorously implemented in Sage, along with simple limit theorems.
In the combinatorial case the amoeba picture captures relevant information for asymptotics.
In general, you need to be careful about behaviour in \(\mathbb{C}^d\).
Having a smooth singular variety \(\mathcal{V}\) is a generic property but there are many applications with \(\mathcal{V}\) non-smooth.
Having a smooth singular variety \(\mathcal{V}\) is a generic property but there are many applications with \(\mathcal{V}\) non-smooth.
Minimality is a property of \(\mathcal{D}\) and does not depend on smoothness.
Having a smooth singular variety \(\mathcal{V}\) is a generic property but there are many applications with \(\mathcal{V}\) non-smooth.
Minimality is a property of \(\mathcal{D}\) and does not depend on smoothness.
But critical points depend on smoothness: if
$$H(\mathbf{w}) = H_{z_1}(\mathbf{w}) = H_{z_d}(\mathbf{w}) = 0$$
then \(\mathbf{w}\) trivially satisfies the critical point equations.
Suppose \(\displaystyle F(x,y) = \frac{G(x,y)}{\ell_1(x,y)\ell_2(x,y)}\) where
$$ \ell_1(x,y) = 1 - \frac{2x+y}{3} \qquad\text{and}\qquad \ell_2(x,y) = 1 - \frac{3x+y}{4}.$$
Suppose \(\displaystyle F(x,y) = \frac{G(x,y)}{\ell_1(x,y)\ell_2(x,y)}\) where
$$ \ell_1(x,y) = 1 - \frac{2x+y}{3} \qquad\text{and}\qquad \ell_2(x,y) = 1 - \frac{3x+y}{4}.$$
Then \(\mathcal{V} = {\color{red}\mathcal{S}_1} \cup {\color{paleturquoise}\mathcal{S}_2} \cup {\color{lightgreen}\mathcal{S}_{1,2}}\) for smooth sets
$$ \begin{aligned} {\color{red}\mathcal{S}_1} \; &{\color{red}= \{\ell_1(x,y) = 0\}} \setminus {\color{lightgreen}\mathcal{S}_{1,2}} \\[+3mm] {\color{paleturquoise}\mathcal{S}_2} \; &{\color{paleturquoise}= \{\ell_2(x,y) = 0\}} \setminus {\color{lightgreen}\mathcal{S}_{1,2}} \\[+3mm] {\color{lightgreen}\mathcal{S}_{1,2}} \; &{\color{lightgreen}= \{\ell_1(x,y)=\ell_2(x,y)=0\}} \\ &{\color{lightgreen}=\{(1,1)\}}\end{aligned}$$
$$ (1,1)$$
On \(\mathcal{S}_1:\) \(\ell_1(x,y) = sx(\ell_1)_x - ry(\ell_1)_y = 0\) has unique solution
$$\boldsymbol{\sigma}_1 = \frac{1}{r+s}\left(\frac{3r}{2},3s\right) \qquad (r \neq 2s)$$
On \(\mathcal{S}_2:\) \(\ell_2(x,y) = sx(\ell_2)_x - ry(\ell_2)_y = 0\) has unique solution
$$\boldsymbol{\sigma}_2 = \frac{1}{r+s}\left(\frac{4r}{3},4s\right) \qquad (r \neq 3s)$$
On \(\mathcal{S}_{1,2}:\) The only point \(\boldsymbol{\sigma}_{1,2}=(1,1)\) is trivially critical.
The point \(\boldsymbol{\sigma}_1\) is a smooth strictly minimal critical point.
We can compute asymptotics as before.
The point \(\boldsymbol{\sigma}_1\) is a smooth strictly minimal critical point.
We can compute asymptotics as before.
$$f_{rn,sn} \approx \int_{|\mathbf{z}|=\times} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
The point \(\boldsymbol{\sigma}_1\) is a smooth strictly minimal critical point.
We can compute asymptotics as before.
$$f_{rn,sn} \approx \int_{|\mathbf{z}|=\times} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
The point \(\boldsymbol{\sigma}_1\) is a smooth strictly minimal critical point.
We can compute asymptotics as before.
$$f_{rn,sn} \approx \int_{|\mathbf{z}|=\times} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
The point \(\boldsymbol{\sigma}_1\) is a smooth strictly minimal critical point.
We can compute asymptotics as before.
$$f_{rn,sn} \approx \int_{|x|=a}$$
Res
The point \(\boldsymbol{\sigma}_1\) is a smooth strictly minimal critical point.
We can compute asymptotics as before.
$$f_{rn,sn} = \frac{\left( \frac{3^{-r-s} 2^r (r+s)^{r+s}}{r^r s^s} \right)^n}{\sqrt{ns}} \left( \frac{4\sqrt{2}(r+s)^{\frac{3}{2}}}{\sqrt{\pi}(2s-r)\sqrt{r}} + O\left(\frac{1}{n}\right) \right)$$
The point \(\boldsymbol{\sigma}_2\) is a smooth minimal critical point.
We can compute asymptotics as before.
The point \(\boldsymbol{\sigma}_2\) is a smooth minimal critical point.
We can compute asymptotics as before.
$$f_{rn,sn} = \frac{\left( \frac{3^r 2^{-2r-2s} (r+s)^{r+s}}{r^r s^s} \right)^n}{\sqrt{ns}} \left( \frac{9\sqrt{2}(r+s)^{\frac{3}{2}}}{2\sqrt{\pi}(r-3s)\sqrt{r}} + O\left(\frac{1}{n}\right) \right)$$
The non-smooth point \(\boldsymbol{\sigma}_{1,2}\) is the only minimal critical point.
$$f_{rn,sn} \approx \int_{|\mathbf{z}|=\times} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
The non-smooth point \(\boldsymbol{\sigma}_{1,2}\) is the only minimal critical point.
$$f_{rn,sn} \approx \int_{|\mathbf{z}|=\times} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
The non-smooth point \(\boldsymbol{\sigma}_{1,2}\) is the only minimal critical point.
$$f_{rn,sn} \approx \int_{|\mathbf{z}|=\times} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
$$+ \int_{|\mathbf{z}|= \;\;} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
The non-smooth point \(\boldsymbol{\sigma}_{1,2}\) is the only minimal critical point.
Only now can we introduce three integrals with small error.
$$f_{rn,sn} \approx \int_{|\mathbf{z}|=\times} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
$$+ \int_{|\mathbf{z}|= \;\;} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
The non-smooth point \(\boldsymbol{\sigma}_{1,2}\) is the only minimal critical point.
Only now can we introduce three integrals with small error.
$$f_{rn,sn} \approx \int_{|\mathbf{z}|=\times} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
The non-smooth point \(\boldsymbol{\sigma}_{1,2}\) is the only minimal critical point.
Only now can we introduce three integrals with small error.
Res 1
Res 2
$$f_{rn,sn} \approx \int_{|\mathbf{z}|=\times} \qquad\qquad - \int_{|\mathbf{z}|=\;\;}$$
The non-smooth point \(\boldsymbol{\sigma}_{1,2}\) is the only minimal critical point.
Only now can we introduce three integrals with small error.
Res 1
Res 2
The non-smooth point \(\boldsymbol{\sigma}_{1,2}\) is the only minimal critical point.
Only now can we introduce three integrals with small error.
\(f_{rn,sn} = 12 + O(\tau^n)\) for some \(0<\tau<1\)
More generally, suppose
$$ F(\mathbf{z}) = \frac{G(\mathbf{z})}{\ell_1(\mathbf{z})^{p_1} \cdots \ell_m(\mathbf{z})^{p_m}}$$
where \(\ell_j(\mathbf{z}) = 1 - \mathbf{b}^{(j)} \cdot \mathbf{z}\) is a real linear function.
More generally, suppose
$$ F(\mathbf{z}) = \frac{G(\mathbf{z})}{\ell_1(\mathbf{z})^{p_1} \cdots \ell_m(\mathbf{z})^{p_m}}$$
where \(\ell_j(\mathbf{z}) = 1 - \mathbf{b}^{(j)} \cdot \mathbf{z}\) is a real linear function.
For any \(S = \{k_1,\dots,k_s\} \subset \{1,\dots,m\}\) define the flat
$$\mathcal{V}_S = \mathcal{V}(\ell_{k_1},\dots,\ell_{k_s})$$
and the stratum
$$\mathcal{S}_S = \mathcal{V}_S \setminus \bigcup_{\mathcal{V}_T \subsetneq \mathcal{V}_S} \mathcal{V}_T.$$
Each stratum \(\mathcal{S}_S\) is a complex manifold.
We call \(F\) simple if the coefficient vectors \(\mathbf{b}^{(k_1)}, \; \dots, \; \mathbf{b}^{(k_s)}\) are linearly independent whenever \(\mathcal{V}_{k_1,\dots,k_s}\neq\varnothing\).
In the simple case, the codimension of \(\mathcal{S}_S\) is \(|S|\).
Each stratum \(\mathcal{S}_S\) is a complex manifold.
We call \(F\) simple if the coefficient vectors \(\mathbf{b}^{(k_1)}, \; \dots, \; \mathbf{b}^{(k_s)}\) are linearly independent whenever \(\mathcal{V}_{k_1,\dots,k_s}\neq\varnothing\).
In the simple case, the codimension of \(\mathcal{S}_S\) is \(|S|\).
Recall the height map
$$ h_{\mathbf{r}}(\mathbf{z}) = - \sum_{j=1}^d r_j \log |z_j|.$$
In the simple case, the critical points of \(h_\mathbf{r}\) on \(\mathcal{V}_{k_1,\dots,k_s}\) are defined by the points where
$$ N = \begin{pmatrix} -\nabla \ell_{k_1} \\ \vdots \\[+2mm] -\nabla \ell_{k_s} \\ -\nabla h \end{pmatrix} = \begin{pmatrix} \mathbf{b}^{(k_1)} \\ \vdots \\[+2mm] \mathbf{b}^{(k_s)} \\ r_1/z_1 \quad \cdots \quad r_d/z_d \end{pmatrix}$$
is rank deficient. This is defined by the vanishing of the \((s+1)\times(s+1)\) minors of \(N\).
Note: If \(s=d\) then every point is trivially critical.
In the simple case, the critical points of \(h_\mathbf{r}\) on \(\mathcal{S}_{k_1,\dots,k_s}\) are the critical points of \(\mathcal{V}_{k_1,\dots,k_s}\) that lie in \(\mathcal{S}_{k_1,\dots,k_s}\).
In the simple case, the critical points of \(h_\mathbf{r}\) on \(\mathcal{S}_{k_1,\dots,k_s}\) are the critical points of \(\mathcal{V}_{k_1,\dots,k_s}\) that lie in \(\mathcal{S}_{k_1,\dots,k_s}\).
We call \(\mathbf{r}\) a generic direction if for each flat \(\mathcal{V}_S\) any critical point on \(\mathcal{V}_S\) lies on the stratum \(\mathcal{S}_S\) (no CP is on two flats).
In the simple case, the critical points of \(h_\mathbf{r}\) on \(\mathcal{S}_{k_1,\dots,k_s}\) are the critical points of \(\mathcal{V}_{k_1,\dots,k_s}\) that lie in \(\mathcal{S}_{k_1,\dots,k_s}\).
We call \(\mathbf{r}\) a generic direction if for each flat \(\mathcal{V}_S\) any critical point on \(\mathcal{V}_S\) lies on the stratum \(\mathcal{S}_S\) (no CP is on two flats).
The critical points of \(F\) are the union of the critical points over all strata.
In the simple case, the critical points of \(h_\mathbf{r}\) on \(\mathcal{S}_{k_1,\dots,k_s}\) are the critical points of \(\mathcal{V}_{k_1,\dots,k_s}\) that lie in \(\mathcal{S}_{k_1,\dots,k_s}\).
We call \(\mathbf{r}\) a generic direction if for each flat \(\mathcal{V}_S\) any critical point on \(\mathcal{V}_S\) lies on the stratum \(\mathcal{S}_S\) (no CP is on two flats).
The critical points of \(F\) are the union of the critical points over all strata.
Lemma
In the real linear case, all critical points are real.
In the simple case, the critical points of \(h_\mathbf{r}\) on \(\mathcal{S}_{k_1,\dots,k_s}\) are the critical points of \(\mathcal{V}_{k_1,\dots,k_s}\) that lie in \(\mathcal{S}_{k_1,\dots,k_s}\).
We call \(\mathbf{r}\) a generic direction if for each flat \(\mathcal{V}_S\) any critical point on \(\mathcal{V}_S\) lies on the stratum \(\mathcal{S}_S\) (no CP is on two flats).
The critical points of \(F\) are the union of the critical points over all strata.
Lemma (Varchenko)
In the real linear case, the number of critical points is the number of bounded components of \(\mathbb{R}^d\setminus\mathcal{V}\).
The (log)normal cone of \(\boldsymbol{\sigma} \in \mathcal{V}_S\) is
$$N(\boldsymbol{\sigma}) = \left\{\sum_{j \in S}a_j(\boldsymbol{\sigma} \odot \mathbf{b}^{(j)}) : a_j>0\right\}$$
where
$$\boldsymbol{\sigma} \odot \mathbf{b}^{(j)} = -(\nabla_{\log} \ell_j)(\boldsymbol{\sigma}) = \left(\sigma_1b_1^{(j)}, \;\dots,\; \sigma_db_d^{(j)}\right).$$
We call \(\boldsymbol{\sigma}\) a contributing point if \(\mathbf{r} \in N(\boldsymbol{\sigma})\).
The (log)normal cone of \(\boldsymbol{\sigma} \in \mathcal{V}_S\) is
$$N(\boldsymbol{\sigma}) = \left\{\sum_{j \in S}a_j(\boldsymbol{\sigma} \odot \mathbf{b}^{(j)}) : a_j>0\right\}$$
where
$$\boldsymbol{\sigma} \odot \mathbf{b}^{(j)} = -(\nabla_{\log} \ell_j)(\boldsymbol{\sigma}) = \left(\sigma_1b_1^{(j)}, \;\dots,\; \sigma_db_d^{(j)}\right).$$
We call \(\boldsymbol{\sigma}\) a contributing point if \(\mathbf{r} \in N(\boldsymbol{\sigma})\).
Note: Every contributing point is a critical point.
\(\mathbf{r}\)
\(\mathbf{r}\)
\(\mathbf{r}\)
Theorem (Baryshnikov, M., Pemantle 2024)
Consider the power series expansion of simple \(F(\mathbf{z})\) and suppose \(\mathbf{r}\) is a generic direction with positive coordinates. If \(\chi\) is the set of contributing singularities for \(F\) in direction \(\mathbf{r}\) then
$$[\mathbf{z}^{n\mathbf{r}}] = \sum_{\boldsymbol{\sigma}\in\chi} I_{\boldsymbol{\sigma}}$$
where \(I_{\boldsymbol{\sigma}}\) is a saddle-point integral of dimension \(d-|\mathcal{S}(\boldsymbol{\sigma})|\).
Theorem (Baryshnikov, M., Pemantle 2024)
Consider the power series expansion of simple \(F(\mathbf{z})\) and suppose \(\mathbf{r}\) is a generic direction with positive coordinates. If \(\chi\) is the set of contributing singularities for \(F\) in direction \(\mathbf{r}\) then
$$[\mathbf{z}^{n\mathbf{r}}] = \sum_{\boldsymbol{\sigma}\in\chi} I_{\boldsymbol{\sigma}}$$
where \(I_{\boldsymbol{\sigma}}\) is a saddle-point integral of dimension \(d-|\mathcal{S}(\boldsymbol{\sigma})|\).
Note: This is an exact equality.
Theorem (Baryshnikov, M., Pemantle 2024)
Consider the power series expansion of simple \(F(\mathbf{z})\) and suppose \(\mathbf{r}\) is a generic direction with positive coordinates. If \(\chi\) is the set of contributing singularities for \(F\) in direction \(\mathbf{r}\) then
$$[\mathbf{z}^{n\mathbf{r}}] = \sum_{\boldsymbol{\sigma}\in\chi} I_{\boldsymbol{\sigma}}$$
where \(I_{\boldsymbol{\sigma}}\) is a saddle-point integral of dimension \(d-|\mathcal{S}(\boldsymbol{\sigma})|\).
Note: This is an exact equality.
Note: If \(|S(\boldsymbol{\sigma})|=d\) then \(I_{\boldsymbol{\sigma}} = \boldsymbol{\sigma}^{-n\mathbf{r}}P_{\boldsymbol{\sigma}}(n)\) for polynomial \(P_{\boldsymbol{\sigma}}\).
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\oplus$$
$$\ominus$$
$$\oplus$$
$$\ominus$$
$$\oplus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\oplus$$
$$\ominus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\oplus$$
$$\ominus$$
$$\oplus$$
$$\ominus$$
$$\ominus$$
$$\oplus$$
$$\oplus$$
$$\ominus$$
$$\oplus$$
$$\ominus$$
sage: var('x y')
sage: from sage_acsv import diagonal_asymptotics_hyperplane
sage: H = (1-2*x/3-y/3)*(1-3*x/4-y/4)
# Case 1: 0 < r/(r+s) < 2/3
sage: diagonal_asymptotics_hyperplane(1/H, r = [1,1])
> 16/sqrt(pi)*(8/9)^n*n^(-1/2) + O((8/9)^n*n^(-3/2))
sage: var('x y')
sage: from sage_acsv import diagonal_asymptotics_hyperplane
sage: H = (1-2*x/3-y/3)*(1-3*x/4-y/4)
# Case 1: 0 < r/(r+s) < 2/3
sage: diagonal_asymptotics_hyperplane(1/H, r = [1,1])
> 16/sqrt(pi)*(8/9)^n*n^(-1/2) + O((8/9)^n*n^(-3/2))
# Case 2: 3/4 < r/(r+s)
sage: diagonal_asymptotics_hyperplane(1/H, r = [4,1])
> 35.57?/sqrt(pi)*(253125/262144)^n*n^(-1/2)
+ O((253125/262144)^n*n^(-3/2))
sage: var('x y')
sage: from sage_acsv import diagonal_asymptotics_hyperplane
sage: H = (1-2*x/3-y/3)*(1-3*x/4-y/4)
# Case 1: 0 < r/(r+s) < 2/3
sage: diagonal_asymptotics_hyperplane(1/H, r = [1,1])
> 16/sqrt(pi)*(8/9)^n*n^(-1/2) + O((8/9)^n*n^(-3/2))
# Case 2: 3/4 < r/(r+s)
sage: diagonal_asymptotics_hyperplane(1/H, r = [4,1])
> 35.57?/sqrt(pi)*(253125/262144)^n*n^(-1/2)
+ O((253125/262144)^n*n^(-3/2))
# Case 3: 2/3 < r/(r+s) < 3/4
# Note the exponentially small error
sage: diagonal_asymptotics_hyperplane(1/H, r = [5,2])
> 12 + O((200120949/204800000)^n*n^(-1))When there are linear dependencies among the \(\ell_j\) then these can be used to decompose \(F\) as a sum of simple functions.
sage: from sage_acsv.decomposition import
compute_leinartas_decomposition as decomp
sage: R.<x,y> = PolynomialRing(QQ, 2)
sage: DE = decomp(R,1,(2-x-y)*(3-2*x-y)*(3-x-2*y))
sage: show(add([SR(p[0])/SR(p[1]).factor() for p in DE]))$$\frac{-1}{3(2x + y - 3)(x + y - 2)^2} + \frac{-1}{3(x + 2y - 3)(x + y - 2)^2}$$
When there are linear dependencies among the \(\ell_j\) then these can be used to decompose \(F\) as a sum of simple functions.
sage: from sage_acsv.decomposition import
compute_leinartas_decomposition as decomp
sage: R.<x,y> = PolynomialRing(QQ, 2)
sage: DE = decomp(R,1,(2-x-y)*(3-2*x-y)*(3-x-2*y))
sage: show(add([SR(p[0])/SR(p[1]) for p in DE]).factor())$$\frac{-1}{(2x + y - 3)(x + y - 2)(x + y - 2)}$$
When there are linear dependencies among the \(\ell_j\) then these can be used to decompose \(F\) as a sum of simple functions.
Leǐnartas (1978): Seminal work on multivariate partial fraction decompositions.
de Korte and Yu (2026): Recent study of partial fraction decomposition in linear factor case.
When there are linear dependencies among the \(\ell_j\) then these can be used to decompose \(F\) as a sum of simple functions.
Leǐnartas (1978): Seminal work on multivariate partial fraction decompositions.
de Korte and Yu (2026): Recent study of partial fraction decomposition in linear factor case.
Note: We can reduce our Cauchy integrals to have simple poles via Gelfand-Shilov cohomology decomposition.
# Compute Gelfand-Shilov cohomology decomposition
sage: from sage_acsv.decomposition
import compute_cohomology_decomposition
sage: R = QQ[x,y]
sage: var('x y n')
sage: G, H = x^(-n-1)*y^(-n-1), R((2-x-y)^2*(3-2*x-y))
sage: g, h = compute_cohomology_decomposition(R, G, H)
sage: show(SR(g)/SR(h).factor())$$\frac{(2(n+1)x - (n+1)y)x^{-n-2}y^{-n-2}}{(2x + y - 3)(x + y - 2)}$$
$$\begin{aligned} &\int \frac{1}{(2x + y - 3)(x + y - 2)^2} \; \frac{dxdy}{x^{n+1}y^{n+1}} \\[+4mm] &= 2(n+1) \int \frac{1}{(2x + y - 3)(x + y - 2)}\frac{dxdy}{x^{n+1}y^{n+2}} \\[+4mm] &\;\;\;\; - (n+1)\int \frac{1}{(2x + y - 3)(x + y - 2)}\frac{dxdy}{x^{n+2}y^{n+1}} \end{aligned} $$
# Compute Gelfand-Shilov cohomology decomposition
sage: from sage_acsv.decomposition
import compute_cohomology_decomposition
sage: R = QQ[x,y]
sage: var('x y n')
sage: G, H = x^(-n-1)*y^(-n-1), R((2-x-y)^2*(3-2*x-y))
sage: g, h = compute_cohomology_decomposition(R, G, H)
sage: show(SR(g)/SR(h).factor())$$\begin{aligned} &[x^ny^n] \frac{1}{(2x + y - 3)(x + y - 2)^2} \\[+4mm] &= 2(n+1) [x^ny^{n+1}] \frac{1}{(2x + y - 3)(x + y - 2)}\\[+4mm] &\;\;\;\; -(n+1)[x^{n+1}y^n] \frac{1}{(2x + y - 3)(x + y - 2)} \end{aligned} $$
# Compute Gelfand-Shilov cohomology decomposition
sage: from sage_acsv.decomposition
import compute_cohomology_decomposition
sage: R = QQ[x,y]
sage: var('x y n')
sage: G, H = x^(-n-1)*y^(-n-1), R((2-x-y)^2*(3-2*x-y))
sage: g, h = compute_cohomology_decomposition(R, G, H)
sage: show(SR(g)/SR(h).factor())1) Decompose \(F\) into a sum of rational functions with simple denominators (and simple poles if desired).
2) For each summand, compute the contributing points and sort by height.
3) For generic directions, approximate the saddle-point integrals of max height.
Note: No longer need to check for minimality!
# Our general asymptotics function calls the hyperplane code
sage: from sage_acsv import
diagonal_asymptotics_combinatorial as diagonal
sage: diagonal(1/H, r = [5,2])
> 12 + O((200120949/204800000)^n*n^(-1))
# Try non-generic direction
sage: try:
sage: diagonal(1/H, r = [2,1])
sage: except Exception as e:
sage: print(e)
> Non-generic direction detected - critical point [1, 1]
is contained in 0-dimensional stratumNon-generic directions occur when \(\mathbf{r} \in \partial N(\boldsymbol{\sigma})\) for some contributing point \(\boldsymbol{\sigma}\) and we cannot take enough residues.
Non-generic directions occur when \(\mathbf{r} \in \partial N(\boldsymbol{\sigma})\) for some contributing point \(\boldsymbol{\sigma}\) and we cannot take enough residues.
\(\mathbf{r} = (2,1)\)
Non-generic directions occur when \(\mathbf{r} \in \partial N(\boldsymbol{\sigma})\) for some contributing point \(\boldsymbol{\sigma}\) and we cannot take enough residues.
\(\mathbf{r} = (2,1)\)
$$\oplus$$
$$\ominus$$
Non-generic directions occur when \(\mathbf{r} \in \partial N(\boldsymbol{\sigma})\) for some contributing point \(\boldsymbol{\sigma}\) and we cannot take enough residues.
\(\mathbf{r} = (2,1)\)
$$\oplus$$
$$\ominus$$
$$\ominus$$
$$\oplus$$
Non-generic directions occur when \(\mathbf{r} \in \partial N(\boldsymbol{\sigma})\) for some contributing point \(\boldsymbol{\sigma}\) and we cannot take enough residues.
\(\mathbf{r} = (2,1)\)
$$\oplus$$
$$\ominus$$
Non-generic directions occur when \(\mathbf{r} \in \partial N(\boldsymbol{\sigma})\) for some contributing point \(\boldsymbol{\sigma}\) and we cannot take enough residues.
Analytically, we get a saddle-point integral with a critical point on the boundary.
Non-generic directions occur when \(\mathbf{r} \in \partial N(\boldsymbol{\sigma})\) for some contributing point \(\boldsymbol{\sigma}\) and we cannot take enough residues.
Analytically, we get a saddle-point integral with a critical point on the boundary.
In the simple pole case, the leading term of \(I_{\boldsymbol{\sigma}}\) is half what it would be if \(\mathbf{r}\) was generic.
Non-generic directions occur when \(\mathbf{r} \in \partial N(\boldsymbol{\sigma})\) for some contributing point \(\boldsymbol{\sigma}\) and we cannot take enough residues.
Analytically, we get a saddle-point integral with a critical point on the boundary.
In the simple pole case, the leading term of \(I_{\boldsymbol{\sigma}}\) is half what it would be if \(\mathbf{r}\) was generic.
There is a more complicated expression for higher-order poles.
Exponential growth varies smoothly with \(\boldsymbol{\sigma}\).
Subexponential growth transitions from \(n^{-1/2}\) to a constant.
The transition occurs at a square-root scale.
Exponential growth varies smoothly with \(\boldsymbol{\sigma}\).
Subexponential growth transitions from \(n^{-1/2}\) to a constant.
The transition occurs at a square-root scale.
Theorem (Baryshnikov, Pemantle, M. 2024)
For non-generic directions on a codimension 1 face of \(N(\boldsymbol{\sigma})\) there exist constants \(A,B\in\mathbb{R}\) and \(\mathbf{v}\in\mathbb{R}^2\) such that
$$\boldsymbol{\sigma}^{n\mathbf{r} + t\sqrt{n}\mathbf{v}} \cdot \left[\mathbf{z}^{n\mathbf{r} + t\sqrt{n}\mathbf{v}}\right]F(\mathbf{z}) \sim A \cdot {\color{red}\text{erf}(Bt)} + A, \quad {\color{red}\text{erf}(x)} = \frac{1}{\pi}\int_{-x}^x e^{-y^2}dy$$
Exponential growth varies smoothly with \(\boldsymbol{\sigma}\).
Subexponential growth transitions from \(n^{-1/2}\) to a constant.
The transition occurs at a square-root scale.
Theorem (Baryshnikov, Pemantle, M. 2024)
For non-generic directions on a codimension 1 face of \(N(\boldsymbol{\sigma})\) there exist constants \(A,B\in\mathbb{R}\) and \(\mathbf{v}\in\mathbb{R}^2\) such that
$$\boldsymbol{\sigma}^{n\mathbf{r} + t\sqrt{n}\mathbf{v}} \cdot \left[\mathbf{z}^{n\mathbf{r} + t\sqrt{n}\mathbf{v}}\right]F(\mathbf{z}) \sim A \cdot {\color{red}\text{erf}(Bt)} + A, \quad {\color{red}\text{erf}(x)} = \frac{1}{\pi}\int_{-x}^x e^{-y^2}dy$$
$$6\; \text{erf}\left(\frac{t}{\sqrt{192}}\right)+6$$
$$\left[x^{2 \cdot 16^2 + t16(3/4)}y^{16^2 + t16(1/4)}\right]F(x,y)$$
$$\begin{aligned} \mathbf{r} &= (2,1) \\[+2mm] \mathbf{v} &= (3/4,1/4) \\[+2mm] \boldsymbol{\sigma} &= (1,1)\end{aligned}$$
How do we define critical points in the direction \(\mathbf{r}\) in general?
How do we define critical points in the direction \(\mathbf{r}\) in general?
Partition \(\mathcal{V}\) into smooth sets \(\mathcal{S}\) and take the critical points of the map \(\phi:\mathcal{S}\rightarrow\mathbb{C}^d\) defined by \(\phi(\mathbf{z})=\mathbf{z}^\mathbf{r}\).
How should we partition \(\mathcal{V}\) in general?
How do we define critical points in the direction \(\mathbf{r}\) in general?
Partition \(\mathcal{V}\) into smooth sets \(\mathcal{S}\) and take the critical points of the map \(\phi:\mathcal{S}\rightarrow\mathbb{C}^d\) defined by \(\phi(\mathbf{z})=\mathbf{z}^\mathbf{r}\).
How should we partition \(\mathcal{V}\) in general?
We want the local picture to be consistent on each smooth set.
$$\begin{aligned} {\color{red}\mathcal{S}_1} &\;\;{\color{red}= \mathcal{V}(\ell_1)} \\[+2mm] {\color{paleturquoise}\mathcal{S}_2} & \;\; {\color{paleturquoise} = \mathcal{V}(\ell_2) \setminus \mathcal{V}(\ell_1)}\end{aligned}$$
$$\begin{aligned} {\color{red}\mathcal{S}_1} &\;\;{\color{red}= \mathcal{V}(\ell_1)\setminus\mathcal{V}(\ell_2)} \\[+2mm] {\color{paleturquoise}\mathcal{S}_2} & \;\; {\color{paleturquoise} = \mathcal{V}(\ell_2) \setminus \mathcal{V}(\ell_1)}\\[+2mm] {\color{lightgreen}\mathcal{S}_3} &\;\; {\color{lightgreen}=\mathcal{V}(\ell_1,\ell_2)}\end{aligned}$$
Whitney (1965): Local conditions on limits of tangent spaces that imply consistent local behaviour on smooth strata.
Whitney (1965): Local conditions on limits of tangent spaces that imply consistent local behaviour on smooth strata.
Teissier (1982): If \(\mathcal{V}\) is an algebraic variety then there exist algebraic sets
$$ \mathcal{V} = \mathcal{F}_0 \supsetneq \mathcal{F}_1 \supsetneq \cdots \supsetneq \mathcal{F}_m = \varnothing$$
such that the connected components of all \(\mathcal{F}_k \setminus \mathcal{F}_{k+1}\) form a Whitney stratification of \(\mathcal{V}\).
Whitney (1965): Local conditions on limits of tangent spaces that imply consistent local behaviour on smooth strata.
Teissier (1982): If \(\mathcal{V}\) is an algebraic variety then there exist algebraic sets
$$ \mathcal{V} = \mathcal{F}_0 \supsetneq \mathcal{F}_1 \supsetneq \cdots \supsetneq \mathcal{F}_m = \varnothing$$
such that the connected components of all \(\mathcal{F}_k \setminus \mathcal{F}_{k+1}\) form a Whitney stratification of \(\mathcal{V}\).
(And every other Whitney stratification of \(\mathcal{V}\) is a refinement of this one.)
Helmer and Nanda (2022): Effective algorithm using conormal spaces (and implementation in M2).
Luo (2026): Implementation in Sage.
# Compute Whitney Stratification
sage: from sage_acsv import whitney_stratification
sage: R.<x, y, z> = PolynomialRing(QQ, 3)
sage: IX = Ideal(y^2 + z^3 - x^2*z^2); IX
> Ideal (-x^2*z^2 + z^3 + y^2) of Multivariate
Polynomial Ring in x, y, z over Rational Field
sage: whitney_stratification(IX, R)
> [Ideal (z, y, x), Ideal (z, y),
Ideal (x^2*z^2 - z^3 - y^2)]$${\color{lightblue} \mathcal{V}(y^2 + z^3 - x^2z^2)}$$
This plot is interactive.
$$\begin{aligned}{\color{lightblue}\mathcal{F}_1} &\;\;{\color{lightblue}= \mathcal{V}(y^2 + z^3 - x^2z^2)} \\ {\color{orange}\mathcal{F}_2} &\;\;{\color{orange}= \mathcal{V}(y,z)} \\ {\color{red}\mathcal{F}_3} &\;\; {\color{red}= \mathcal{V}(x,y,z)}\end{aligned}$$
This plot is interactive.
Suppose \(\mathcal{F}_i = \mathcal{V}(p_1,\dots,p_s)\) and \(\mathcal{F}_{i+1} = \mathcal{V}(q_1,\dots,q_r)\).
Assume every component of \(\mathcal{F}_i\) has codimension \(c\).
Then the critical points in the direction \(\mathbf{r}\) on \(\mathcal{S} = \mathcal{F}_i \setminus \mathcal{F}_{i+1}\)
are defined by \( p_1 = \cdots = p_s = 0\), \(q_1, \dots, q_r \neq 0\), and the vanishing of all \((c+1)\times(c+1)\) minors of the matrix
$$\begin{pmatrix} \nabla_{\log}p_1 \\ \vdots \\ \nabla_{\log}p_s \\ \mathbf{r} \end{pmatrix}$$
Note: These are all polynomial (non)equalities.
When no critical point of \(\mathcal{S}\) lies in \(\mathcal{F}_{i+1}\) (the generic case) then they can be computed by (for instance) a Grobner basis computation and an ideal saturation.
Note: These are all polynomial (non)equalities.
When no critical point of \(\mathcal{S}\) lies in \(\mathcal{F}_{i+1}\) (the generic case) then they can be computed by (for instance) a Grobner basis computation and an ideal saturation.
Critical points always solve determinantal systems.
Note: These are all polynomial (non)equalities.
When no critical point of \(\mathcal{S}\) lies in \(\mathcal{F}_{i+1}\) (the generic case) then they can be computed by (for instance) a Grobner basis computation and an ideal saturation.
Critical points always solve determinantal systems.
Gopalakrishnan, Neiger, Safey El Din (2023): Improved complexity in \(F_5\) algorithm by predicting reductions to zero
# Computing critical points with a cone singularity
sage: from sage_acsv import critical_points
sage: var('w x y z')
sage: H = 1 - (w + x + y + z) + 27*w*x*y*z
sage: critical_points(1/H)
> [[1/3, 1/3, 1/3, 1/3],
[-0.3333333333333334? - 0.4714045207910317?*I,
-0.3333333333333334? - 0.4714045207910317?*I,
-0.3333333333333334? - 0.4714045207910317?*I,
-0.3333333333333334? - 0.4714045207910317?*I],
[-0.3333333333333334? + 0.4714045207910317?*I,
-0.3333333333333334? + 0.4714045207910317?*I,
-0.3333333333333334? + 0.4714045207910317?*I,
-0.3333333333333334? + 0.4714045207910317?*I]]# Computing critical points with a cone singularity
sage: from sage_acsv import critical_points
sage: var('w x y z')
sage: H = 1 - (w + x + y + z) + 27*w*x*y*z
sage: critical_points(1/H)
> [[1/3, 1/3, 1/3, 1/3],
[-0.3333333333333334? - 0.4714045207910317?*I,
-0.3333333333333334? - 0.4714045207910317?*I,
-0.3333333333333334? - 0.4714045207910317?*I,
-0.3333333333333334? - 0.4714045207910317?*I],
[-0.3333333333333334? + 0.4714045207910317?*I,
-0.3333333333333334? + 0.4714045207910317?*I,
-0.3333333333333334? + 0.4714045207910317?*I,
-0.3333333333333334? + 0.4714045207910317?*I]]
sage: H2 = H.subs(x=x+1/3,y=y+1/3,z=z+1/3,w=w+1/3)
sage: H2.taylor((w,0),(x,0),(y,0),(z,0),2).expand()
> 3*w*x + 3*w*y + 3*x*y + 3*w*z + 3*x*z + 3*y*zsage: from sage_acsv
import minimal_critical_points_combinatorial
sage: minimal_critical_points_combinatorial(1/H)
> [[1/3, 1/3, 1/3, 1/3]]In the combinatorial case we can also verify which of the critical points are minimal.
sage: from sage_acsv
import minimal_critical_points_combinatorial
sage: minimal_critical_points_combinatorial(1/H)
> [[1/3, 1/3, 1/3, 1/3]]In the combinatorial case we can also verify which of the critical points are minimal.
As seen in the hyperplane arrangement example, in the non-smooth case it is possible to have minimal critical points that do not give a contribution to asymptotics.
Which critical points matter for diagonal asympotics?
Baryshnikov-Pemantle (2011): For any minimal point \(\mathbf{w}\) there is a cone \(N(\mathbf{w})\) that varies in a nice way with \(\mathbf{w}\) such that the Cauchy integral for \(f_{n\mathbf{r}}\) can be "deformed past" \(\mathbf{w}\) whenever \(\mathbf{r} \notin N(\mathbf{w})\).
Baryshnikov-Pemantle (2011): For any minimal point \(\mathbf{w}\) there is a cone \(N(\mathbf{w})\) that varies in a nice way with \(\mathbf{w}\) such that the Cauchy integral for \(f_{n\mathbf{r}}\) can be "deformed past" \(\mathbf{w}\) whenever \(\mathbf{r} \notin N(\mathbf{w})\).
Smooth Case: \((\nabla_{\log}H)(\mathbf{w}) = \lambda\mathbf{v}\) and \(N(\mathbf{w})\) is the halfspace with normal \(\mathbf{v}\) (with proper orientation).
Baryshnikov-Pemantle (2011): For any minimal point \(\mathbf{w}\) there is a cone \(N(\mathbf{w})\) that varies in a nice way with \(\mathbf{w}\) such that the Cauchy integral for \(f_{n\mathbf{r}}\) can be "deformed past" \(\mathbf{w}\) whenever \(\mathbf{r} \notin N(\mathbf{w})\).
Smooth Case: \((\nabla_{\log}H)(\mathbf{w}) = \lambda\mathbf{v}\) and \(N(\mathbf{w})\) is the halfspace with normal \(\mathbf{v}\) (with proper orientation).
(Locally) Simple Hyperplane Arrangement: Intersection of halfspaces from each smooth factor.
Baryshnikov-Pemantle (2011): For any minimal point \(\mathbf{w}\) there is a cone \(N(\mathbf{w})\) that varies in a nice way with \(\mathbf{w}\) such that the Cauchy integral for \(f_{n\mathbf{r}}\) can be "deformed past" \(\mathbf{w}\) whenever \(\mathbf{r} \notin N(\mathbf{w})\).
Smooth Case: \((\nabla_{\log}H)(\mathbf{w}) = \lambda\mathbf{v}\) and \(N(\mathbf{w})\) is the halfspace with normal \(\mathbf{v}\) (with proper orientation).
(Locally) Simple Hyperplane Arrangement: Intersection of halfspaces from each smooth factor.
Cone Singularity (Quadratic): Dual quadratic form.
Next Case for Asymptotics: Every singularity is locally a hyperplane arrangement.
Suppose
$$F(\mathbf{z}) = \frac{G(\mathbf{z})}{H_1(\mathbf{z})\cdots H_m(\mathbf{z})}$$
where
Then every singularity is a transverse multiple point.
In the transverse multiple point case, it is enough to compute a stratification analogously to hyperplane arrangements.
For any \(S = \{k_1,\dots,k_s\}\) define the flat
$$\mathcal{V}_S = \mathcal{V}_{k_1,\dots,k_s} = \mathcal{V}(H_{k_1},\dots,H_{k_s}),$$
and the stratum
$$\mathcal{S}_S = \mathcal{V}_S \setminus \bigcup_{\mathcal{V}_T \subsetneq \mathcal{V}_s} \mathcal{V}_T.$$
The critical points on \(\mathcal{S}\) are the points where \(\mathbf{r}\) is in the span of \( \nabla_{\log}H_{k_1}, \dots, \nabla_{\log}H_{k_s}\).
The critical points on \(\mathcal{S}\) are the points where \(\mathbf{r}\) is in the span of \( \nabla_{\log}H_{k_1}, \dots, \nabla_{\log}H_{k_s}\).
If \(\mathbf{w}\) is a minimal critical point on \(\mathcal{S}_{k_1,\dots,k_s}\) then we let \(\mathbf{v}_j \in \mathbb{R}^d\) be \((\nabla_{\log}H_{k_j})(\mathbf{w})\) scaled by any of its non-zero entries.
The critical points on \(\mathcal{S}\) are the points where \(\mathbf{r}\) is in the span of \( \nabla_{\log}H_{k_1}, \dots, \nabla_{\log}H_{k_s}\).
If \(\mathbf{w}\) is a minimal critical point on \(\mathcal{S}_{k_1,\dots,k_s}\) then we let \(\mathbf{v}_j \in \mathbb{R}^d\) be \((\nabla_{\log}H_{k_j})(\mathbf{w})\) scaled by any of its non-zero entries.
If \(\mathbf{r} = \lambda_1\mathbf{v}_1 + \cdots + \lambda_s\mathbf{v}_s\) where each \(\lambda_i>0\) then we call \(\mathbf{w}\) a contributing point.
The critical points on \(\mathcal{S}\) are the points where \(\mathbf{r}\) is in the span of \( \nabla_{\log}H_{k_1}, \dots, \nabla_{\log}H_{k_s}\).
If \(\mathbf{w}\) is a minimal critical point on \(\mathcal{S}_{k_1,\dots,k_s}\) then we let \(\mathbf{v}_j \in \mathbb{R}^d\) be \((\nabla_{\log}H_{k_j})(\mathbf{w})\) scaled by any of its non-zero entries.
If \(\mathbf{r} = \lambda_1\mathbf{v}_1 + \cdots + \lambda_s\mathbf{v}_s\) where each \(\lambda_i>0\) then we call \(\mathbf{w}\) a contributing point.
Note: This matches our definition in the smooth case.
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}}\)
sage: ini = [1,1,2,3,8,15,39]
sage: deq = (196608*z^16 - 4096*z^15 - 106496*z^14 + 90112*z^13 + 4096*z^12 + 16192*z^11 + 3776*z^10 - 4736*z^9 - 560*z^8 - 124*z^7 - 33*z^6 + 52*z^5 + 7*z^4 - 2*z^3)*Dz^4 + (3145728*z^15 - 462848*z^14 - 1073152*z^13 + 1252352*z^12 + 192512*z^11 + 370112*z^10 + 76800*z^9 - 58176*z^8 - 11152*z^7 - 2468*z^6 - 968*z^5 + 518*z^4 + 90*z^3 - 22*z^2)*Dz^3 + (14155776*z^14 - 3870720*z^13 - 2199552*z^12 + 4733952*z^11 + 1582080*z^10 + 2059392*z^9 + 525696*z^8 - 164256*z^7 - 47904*z^6 - 9648*z^5 - 5508*z^4 + 1236*z^3 + 306*z^2 - 60*z)*Dz^2 + (18874368*z^13 - 7544832*z^12 + 294912*z^11 + 5081088*z^10 + 3201024*z^9 + 3148416*z^8 + 1068864*z^7 - 68832*z^6 - 41136*z^5 - 5520*z^4 - 7584*z^3 + 648*z^2 + 276*z - 36)*Dz + 4718592*z^12 - 2482176*z^11 + 811008*z^10 + 964608*z^9 + 1075200*z^8 + 880128*z^7 + 387648*z^6 + 31296*z^5 + 6864*z^4 + 3024*z^3 - 1320*z^2 + 72*z + 36
sage: bound_coefficients(deq, ini, prec=20)
> 1.00000 * 3^n
*(([+/- 1.56e-12] + [+/- 1.56e-12]*I)*n^(-1/2)
+ ([+/- 3.21e-12] + [+/- 3.21e-12]*I)*n^(-3/2)
+ ([+/- 8.71e-12] + [+/- 8.71e-12]*I)*n^(-5/2)
+ B([2.18961e+7 +/- 68.1]*n^(-7/2), n >= 10))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.
sage: ini = [1,1,2,3,8,15,39]
sage: deq = (196608*z^16 - 4096*z^15 - 106496*z^14 + 90112*z^13 + 4096*z^12 + 16192*z^11 + 3776*z^10 - 4736*z^9 - 560*z^8 - 124*z^7 - 33*z^6 + 52*z^5 + 7*z^4 - 2*z^3)*Dz^4 + (3145728*z^15 - 462848*z^14 - 1073152*z^13 + 1252352*z^12 + 192512*z^11 + 370112*z^10 + 76800*z^9 - 58176*z^8 - 11152*z^7 - 2468*z^6 - 968*z^5 + 518*z^4 + 90*z^3 - 22*z^2)*Dz^3 + (14155776*z^14 - 3870720*z^13 - 2199552*z^12 + 4733952*z^11 + 1582080*z^10 + 2059392*z^9 + 525696*z^8 - 164256*z^7 - 47904*z^6 - 9648*z^5 - 5508*z^4 + 1236*z^3 + 306*z^2 - 60*z)*Dz^2 + (18874368*z^13 - 7544832*z^12 + 294912*z^11 + 5081088*z^10 + 3201024*z^9 + 3148416*z^8 + 1068864*z^7 - 68832*z^6 - 41136*z^5 - 5520*z^4 - 7584*z^3 + 648*z^2 + 276*z - 36)*Dz + 4718592*z^12 - 2482176*z^11 + 811008*z^10 + 964608*z^9 + 1075200*z^8 + 880128*z^7 + 387648*z^6 + 31296*z^5 + 6864*z^4 + 3024*z^3 - 1320*z^2 + 72*z + 36
sage: bound_coefficients(deq, ini, prec=20)
> 1.00000 * 3^n
*(([+/- 1.56e-12] + [+/- 1.56e-12]*I)*n^(-1/2)
+ ([+/- 3.21e-12] + [+/- 3.21e-12]*I)*n^(-3/2)
+ ([+/- 8.71e-12] + [+/- 8.71e-12]*I)*n^(-5/2)
+ B([2.18961e+7 +/- 68.1]*n^(-7/2), n >= 10))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)$$
# Function whose diagonal counts N,SE,SW quadrant walks
sage: from sage_acsv
import minimal_critical_points_combinatorial as MC,
contributing_points_combinatorial as CONTRIB
sage: var('x,y,t')
sage: G = (1 + x)*(2*t*x^2*y^2 + 2*t*y^2 - 1)
sage: H = (y-1)*(t*x^2*y^2+t*y^2+t*x-1)*(t*x^2*y^2+t*y^2-1)
# There are 5 minimal critical points.
# The point [1/3, 1, 1] would give exponential growth 3^n.
sage: MC(G/H)
> [[1/3, 1, 1],
[1/2, 1, -0.7071067811865475?],
[1/2, 1, 0.7071067811865475?],
[-1/2, -1, 0.7071067811865475?*I],
[-1/2, -1, -0.7071067811865475?*I]]# Function whose diagonal counts N,SE,SW quadrant walks
sage: from sage_acsv
import minimal_critical_points_combinatorial as MC,
contributing_points_combinatorial as CONTRIB
sage: var('x,y,t')
sage: G = (1 + x)*(2*t*x^2*y^2 + 2*t*y^2 - 1)
sage: H = (y-1)*(t*x^2*y^2+t*y^2+t*x-1)*(t*x^2*y^2+t*y^2-1)
# There are only 4 contributing points.
# The point [1/3, 1, 1] IS NOT CONTRIBUTING.
sage: CONTRIB(G/H)
> [[1/2, 1, -0.7071067811865475?],
[1/2, 1, 0.7071067811865475?],
[-1/2, -1, 0.7071067811865475?*I],
[-1/2, -1, -0.7071067811865475?*I]]Each transverse contributing point gives an explicit asymptotic expansion, just like hyperplane arrangements.
Each transverse contributing point gives an explicit asymptotic expansion, just like hyperplane arrangements.
The same definition works with higher-order poles, and with functions where only the minimal critical points are transverse multiple points.
Each transverse contributing point gives an explicit asymptotic expansion, just like hyperplane arrangements.
The same definition works with higher-order poles, and with functions where only the minimal critical points are transverse multiple points.
When \(d=s\) the contribution to asymptotics is still an exponential times a polynomial in \(n\).
Each transverse contributing point gives an explicit asymptotic expansion, just like hyperplane arrangements.
The same definition works with higher-order poles, and with functions where only the minimal critical points are transverse multiple points.
When \(d=s\) the contribution to asymptotics is still an exponential times a polynomial in \(n\).
We no longer get a complete expression for \(f_{n\mathbf{r}}\) in terms of saddle-point integrals.
sage: from sage_acsv import diagonal_asymptotics_combinatorial
as diagonal
sage: var('x,y')
sage: G = (1 + x)*(2*z*x^2*y^2 + 2*z*y^2 - 1)
sage: H = (-1 + y)*(z*x^2*y^2 + z*y^2 + z*x - 1)
*(z*x^2*y^2 + z*y^2 - 1)
sage: from sage_acsv import diagonal_asymptotics_combinatorial
as diagonal
sage: var('x,y')
sage: G = (1 + x)*(2*z*x^2*y^2 + 2*z*y^2 - 1)
sage: H = (-1 + y)*(z*x^2*y^2 + z*y^2 + z*x - 1)
*(z*x^2*y^2 + z*y^2 - 1)
sage: diagonal(F)
sage: from sage_acsv import diagonal_asymptotics_combinatorial
as diagonal
sage: var('x,y')
sage: G = (1 + x)*(2*z*x^2*y^2 + 2*z*y^2 - 1)
sage: H = (-1 + y)*(z*x^2*y^2 + z*y^2 + z*x - 1)
*(z*x^2*y^2 + z*y^2 - 1)
sage: diagonal(F)
> O(2.828427124746190?^n*n^(-2))
sage: from sage_acsv import diagonal_asymptotics_combinatorial
as diagonal
sage: var('x,y')
sage: G = (1 + x)*(2*z*x^2*y^2 + 2*z*y^2 - 1)
sage: H = (-1 + y)*(z*x^2*y^2 + z*y^2 + z*x - 1)
*(z*x^2*y^2 + z*y^2 - 1)
sage: diagonal(F)
> O(2.828427124746190?^n*n^(-2))
sage: diagonal(F, expansion_precision=2)
> 32.97056274847714?/pi * 2.828427124746190?^n * n^(-2)
+ 0.9705627484771406?/pi * (-2.828427124746190?)^n * n^(-2)
+ O(2.828427124746190?^n*n^(-3))sage: from sage_acsv import diagonal_asymptotics_combinatorial
as diagonal
sage: var('x,y')
sage: G = (1 + x)*(2*z*x^2*y^2 + 2*z*y^2 - 1)
sage: H = (-1 + y)*(z*x^2*y^2 + z*y^2 + z*x - 1)
*(z*x^2*y^2 + z*y^2 - 1)
sage: diagonal(F)
> O(2.828427124746190?^n*n^(-2))
sage: diagonal(F, expansion_precision=2)
> 32.97056274847714?/pi * 2.828427124746190?^n * n^(-2)
+ 0.9705627484771406?/pi * (-2.828427124746190?)^n * n^(-2)
+ O(2.828427124746190?^n*n^(-3))Luo, M, Schost (2026): Bit-complexity analysis for transverse multiple point case.
Problem: Checking for minimal points is a real algebraic geometry problem and slow.
Problem: Checking for minimal points is a real algebraic geometry problem and slow.
Solution: For large \(n\) the modulus of
$$ f_{n\mathbf{r}} = \frac{1}{(2\pi i)^d}\int_\mathcal{C}F(\mathbf{z})\frac{d\mathbf{z}}{\mathbf{z}^{n\mathbf{r}}+\mathbf{1}}$$
is captured by
$$ h(\mathbf{z}) = -r_1\log|z_1| - \cdots - r_d\log|z_d|.$$
Problem: Checking for minimal points is a real algebraic geometry problem and slow.
Solution: For large \(n\) the modulus of
$$ f_{n\mathbf{r}} = \frac{1}{(2\pi i)^d}\int_\mathcal{C}F(\mathbf{z})\frac{d\mathbf{z}}{\mathbf{z}^{n\mathbf{r}}+\mathbf{1}}$$
is captured by
$$ h(\mathbf{z}) = -r_1\log|z_1| - \cdots - r_d\log|z_d|.$$
We try to push down intersection cycles.
Start with the expression
$$ \binom{2n}{n} = \frac{1}{(2\pi i)^2}\int_{\substack{|x|=\epsilon \\[+0.5mm] |y|=\epsilon}} \frac{1}{1-x-y}\,\frac{dxdy}{x^{n+1}y^{n+1}}.$$
Start with the expression
$$ \binom{2n}{n} = \frac{1}{(2\pi i)^2}\int_{\substack{|x|=\epsilon \\[+0.5mm] |y|=\epsilon}} \frac{1}{1-x-y}\,\frac{dxdy}{x^{n+1}y^{n+1}}.$$
Expand \(|y|\) until you hit \(\mathcal{V}\) and take a residue
$$\binom{2n}{n} = \frac{-1}{2\pi i}\int_{|x|=\epsilon}\frac{dx}{x^{n+1}(1-x)^{n+1}}.$$
Start with the expression
$$ \binom{2n}{n} = \frac{1}{(2\pi i)^2}\int_{\substack{|x|=\epsilon \\[+0.5mm] |y|=\epsilon}} \frac{1}{1-x-y}\,\frac{dxdy}{x^{n+1}y^{n+1}}.$$
Expand \(|y|\) until you hit \(\mathcal{V}\) and take a residue
$$\binom{2n}{n} = \frac{-1}{2\pi i}\int_{|x|=\epsilon}\frac{dx}{x^{n+1}(1-x)^{n+1}}.$$
Then flow the cycle \(|x|=\epsilon\) to points of lower height.
Negative gradient flow of \(x=a+ib\) starting with \(|x|=1/10\).
$$h(x) = -\log|x|-\log|1-x| = -\frac{1}{2}\log(a^2+b^2) - \frac{1}{2}\log\left((1-a)^2+b^2\right)$$
$$ \binom{2n}{n} = \frac{1}{(2\pi i)^2}\int_{\color{red}\mathcal{C'}} \frac{dx}{x^{n+1}(1-x)^{n+1}} = \frac{4^n}{\sqrt{\pi n}}\left(1+O\left(n^{-1}\right)\right)$$
Actually performing these flows is inefficient!
Actually performing these flows is inefficient!
But we can predict where they get stuck — at critical points!
And we get saddle-point integrals!
Actually performing these flows is inefficient!
But we can predict where they get stuck — at critical points!
And we get saddle-point integrals!
Morse theory: Topological study of manifolds via height functions Stratified Morse theory: Study of varieties (and more)
Actually performing these flows is inefficient!
But we can predict where they get stuck — at critical points!
And we get saddle-point integrals!
Morse theory: Topological study of manifolds via height functions Stratified Morse theory: Study of varieties (and more)
Problem: Our height functions are not proper
Solution: Ignore parts not contributing to dominant asymptotics
Flows of \(|x|=1/10\) on \(\mathcal{V}(1-x-xy)\) and \(\mathcal{V}(1-x-y-x^2y)\)
There exist checkable conditions (no critical points at infinity) under which the results of Morse theory hold and
$$f_{n\mathbf{r}} = \sum_{\mathbf{w}\in\text{crit}} \kappa_\mathbf{w}\Psi_\mathbf{w}(n) + \text{asymptotically negligible error}$$
where \(\kappa_\mathbf{w} \in \mathbb{Z}\) and \(\Psi_\mathbf{w}(n)\) is a local integral.
There exist checkable conditions (no critical points at infinity) under which the results of Morse theory hold and
$$f_{n\mathbf{r}} = \sum_{\mathbf{w}\in\text{crit}} \kappa_\mathbf{w}\Psi_\mathbf{w}(n) + \text{asymptotically negligible error}$$
where \(\kappa_\mathbf{w} \in \mathbb{Z}\) and \(\Psi_\mathbf{w}(n)\) is a local integral.
How can we determine \(\kappa_\mathbf{w}\)?
There exist checkable conditions (no critical points at infinity) under which the results of Morse theory hold and
$$f_{n\mathbf{r}} = \sum_{\mathbf{w}\in\text{crit}} \kappa_\mathbf{w}\Psi_\mathbf{w}(n) + \text{asymptotically negligible error}$$
where \(\kappa_\mathbf{w} \in \mathbb{Z}\) and \(\Psi_\mathbf{w}(n)\) is a local integral.
How can we determine \(\kappa_\mathbf{w}\)?
Combine techniques!
Consider again \(\displaystyle F(w,x,y,z) = \frac{1}{1-(w+x+y+z)+27wxyz}\).
Consider again \(\displaystyle F(w,x,y,z) = \frac{1}{1-(w+x+y+z)+27wxyz}\).
There are three critical points, with asymptotic contributions
$$\begin{aligned} \Phi_1(n) &= 81^n \cdot \Theta(n) && (w = x = y = z = 1/3) \\[10pt] \Phi_2(n) &= \left( \frac{11621 - i\sqrt{30803599}}{20420} \right) \frac{(-7 - 4i\sqrt{2})^n}{n^{3/2}\pi^{3/2}} && (w = x = y = z = -1/3 + i\sqrt{2}/3) \\[10pt] \Phi_3(n) &= \left( \frac{11621 + i\sqrt{30803599}}{20420} \right) \frac{(-7 + 4i\sqrt{2})^n}{n^{3/2}\pi^{3/2}} && (w = x = y = z = -1/3 - i\sqrt{2}/3) \end{aligned} $$
Consider again \(\displaystyle F(w,x,y,z) = \frac{1}{1-(w+x+y+z)+27wxyz}\).
There are three critical points, with asymptotic contributions
$$\begin{aligned} \Phi_1(n) &= 81^n \cdot \Theta(n) && (w = x = y = z = 1/3) \\[10pt] \Phi_2(n) &= \left( \frac{11621 - i\sqrt{30803599}}{20420} \right) \frac{(-7 - 4i\sqrt{2})^n}{n^{3/2}\pi^{3/2}} && (w = x = y = z = -1/3 + i\sqrt{2}/3) \\[10pt] \Phi_3(n) &= \left( \frac{11621 + i\sqrt{30803599}}{20420} \right) \frac{(-7 + 4i\sqrt{2})^n}{n^{3/2}\pi^{3/2}} && (w = x = y = z = -1/3 - i\sqrt{2}/3) \end{aligned} $$
There are no critical points at infinity.
Consider again \(\displaystyle F(w,x,y,z) = \frac{1}{1-(w+x+y+z)+27wxyz}\).
There are three critical points, with asymptotic contributions
$$\begin{aligned} \Phi_1(n) &= 81^n \cdot \Theta(n) && (w = x = y = z = 1/3) \\[10pt] \Phi_2(n) &= \left( \frac{11621 - i\sqrt{30803599}}{20420} \right) \frac{(-7 - 4i\sqrt{2})^n}{n^{3/2}\pi^{3/2}} && (w = x = y = z = -1/3 + i\sqrt{2}/3) \\[10pt] \Phi_3(n) &= \left( \frac{11621 + i\sqrt{30803599}}{20420} \right) \frac{(-7 + 4i\sqrt{2})^n}{n^{3/2}\pi^{3/2}} && (w = x = y = z = -1/3 - i\sqrt{2}/3) \end{aligned} $$
Thus, \(f_{n,n,n,n} = {\color{red}\kappa_1} \Phi_1(n) + {\color{red}\kappa_2} \Phi_2(n) + {\color{red}\kappa_3} \Phi_3(n)\) for \({\color{red}\kappa_1,\kappa_2,\kappa_3} \in \mathbb{Z}\).
Consider again \(\displaystyle F(w,x,y,z) = \frac{1}{1-(w+x+y+z)+27wxyz}\).
The diagonal coefficients satisfy the P-recurrence
$$ \begin{aligned} 0 = (n^3 + 6n^2 + 12n + 8)c_{n+2} &+ (14n^3 + 63n^2 + 97n + 51)c_{n+1} \\&+ (81n^3 + 243n^2 + 243n + 81)c_n \end{aligned} $$ which has an asymptotic basis of solutions
$$\Psi_1(n) = \frac{(94i\sqrt{2} - 7)^n}{n^{3/2}} \left(1 + O\left(\frac{1}{n}\right)\right) \quad \Psi_2(n) = \frac{(-94i\sqrt{2} - 7)^n}{n^{3/2}} \left(1 + O\left(\frac{1}{n}\right)\right)$$
Consider again \(\displaystyle F(w,x,y,z) = \frac{1}{1-(w+x+y+z)+27wxyz}\).
The diagonal coefficients satisfy the P-recurrence
$$ \begin{aligned} 0 = (n^3 + 6n^2 + 12n + 8)c_{n+2} &+ (14n^3 + 63n^2 + 97n + 51)c_{n+1} \\&+ (81n^3 + 243n^2 + 243n + 81)c_n \end{aligned} $$ which has an asymptotic basis of solutions
$$\Psi_1(n) = \frac{(94i\sqrt{2} - 7)^n}{n^{3/2}} \left(1 + O\left(\frac{1}{n}\right)\right) \quad \Psi_2(n) = \frac{(-94i\sqrt{2} - 7)^n}{n^{3/2}} \left(1 + O\left(\frac{1}{n}\right)\right)$$
Thus, \(f_{n,n,n,n} = {\color{turquoise}\sigma_1} \Psi_1(n) + {\color{turquoise}\sigma_2} \Psi_2(n)\) for \({\color{turquoise}\sigma_1,\sigma_2\in\mathbb{C}}\).
We have shown
$$\begin{aligned} f_{n,n,n,n} &= {\color{red}\kappa_1} \Phi_1(n) + {\color{red}\kappa_2} \Phi_2(n) + {\color{red}\kappa_3} \Phi_3(n) && {\color{red}\text{Unknown }\mathbb{Z}}\\ f_{n,n,n,n} &= {\color{turquoise}\sigma_1} \Psi_1(n) + {\color{turquoise}\sigma_2} \Psi_2(n) && {\color{turquoise}\text{Approximated } \mathbb{C}}\end{aligned}$$
We have shown
$$\begin{aligned} f_{n,n,n,n} &= {\color{red}\kappa_1} \Phi_1(n) + {\color{red}\kappa_2} \Phi_2(n) + {\color{red}\kappa_3} \Phi_3(n) && {\color{red}\text{Unknown }\mathbb{Z}}\\ f_{n,n,n,n} &= {\color{turquoise}\sigma_1} \Psi_1(n) + {\color{turquoise}\sigma_2} \Psi_2(n) && {\color{turquoise}\text{Approximated } \mathbb{C}}\end{aligned}$$
Integer homology coefficients seem very hard to compute.
We have shown
$$\begin{aligned} f_{n,n,n,n} &= {\color{red}\kappa_1} \Phi_1(n) + {\color{red}\kappa_2} \Phi_2(n) + {\color{red}\kappa_3} \Phi_3(n) && {\color{red}\text{Unknown }\mathbb{Z}}\\ f_{n,n,n,n} &= {\color{turquoise}\sigma_1} \Psi_1(n) + {\color{turquoise}\sigma_2} \Psi_2(n) && {\color{turquoise}\text{Approximated } \mathbb{C}}\end{aligned}$$
Integer homology coefficients seem very hard to compute.
Approximation cannot prove results without explicit bounds.
We have shown
$$\begin{aligned} f_{n,n,n,n} &= {\color{red}\kappa_1} \Phi_1(n) + {\color{red}\kappa_2} \Phi_2(n) + {\color{red}\kappa_3} \Phi_3(n) && {\color{red}\text{Unknown }\mathbb{Z}}\\ f_{n,n,n,n} &= {\color{turquoise}\sigma_1} \Psi_1(n) + {\color{turquoise}\sigma_2} \Psi_2(n) && {\color{turquoise}\text{Approximated } \mathbb{C}}\end{aligned}$$
Integer homology coefficients seem very hard to compute.
Approximation cannot prove results without explicit bounds.
By combining these representations we can solve the connection problem!
sage: from sage_acsv import compute_asymptotics_at_points as CAP
sage: from sage_acsv import get_expansion_terms, critical_points
sage: var('w,x,y,z')
sage: F = 1/(1 - (w + x + y + z) + 27*w*x*y*z)
sage: CPs = critical_points(F)[1:]
sage: Phi = [term.coefficient * CBF(term.pi_factor)
for term in get_expansion_terms(CAP(F, CPs))]
sage: Phi
> [[0.1022028 +/- 8.27e-17] + [ 0.048811298 +/- 7.71e-17]*I,
[0.1022028 +/- 8.27e-17] + [-0.048811298 +/- 7.71e-17]*I]sage: from ore_algebra.analytic.singularity_analysis
import bound_coefficients as BC
sage: from sage_periods import compute_diagonal_annihilator
as diagonal
sage: asm = BC(diagonal(F), [1, -3], order=1)
sage: C2 = [term.coefficient for term
in list(asm.series_factor().summands)[0:2]]
sage: C2
> [[0.3066086 +/- 5.52e-16] + [ 0.146433 +/- 2.88e-16]*I,
[0.3066086 +/- 5.52e-16] + [-0.146433 +/- 2.88e-16]*I]
sage: from ore_algebra.analytic.singularity_analysis
import bound_coefficients as BC
sage: from sage_periods import compute_diagonal_annihilator
as diagonal
sage: asm = BC(diagonal(F), [1, -3], order=1)
sage: C2 = [term.coefficient for term
in list(asm.series_factor().summands)[0:2]]
sage: C2
> [[0.3066086 +/- 5.52e-16] + [ 0.146433 +/- 2.88e-16]*I,
[0.3066086 +/- 5.52e-16] + [-0.146433 +/- 2.88e-16]*I]
# This is an integer!
sage: C2[0]/C1[0]
> [3.00000000000000 +/- 7.88e-15] + [+/- 5.90e-15]*IBaryshnikov, M., and Pemantle detect CPAI by homogenizing the critical point equations then saturating to take the closure at infinity (or using Gröbner basis with a graded term ordering).
Baryshnikov, M., and Pemantle detect CPAI by homogenizing the critical point equations then saturating to take the closure at infinity (or using Gröbner basis with a graded term ordering).
This works, but is inefficient and destroys the structure of the system. It is hard to characterize the directions with CPAI.
Baryshnikov, M., and Pemantle detect CPAI by homogenizing the critical point equations then saturating to take the closure at infinity (or using Gröbner basis with a graded term ordering).
This works, but is inefficient and destroys the structure of the system. It is hard to characterize the directions with CPAI.
Solution: Take the closure in a toric variety.
Sattelberger - van der Veer (2023): If \(\mathcal{V}\) is schön (aka Newton nondegenerate) then all directions with CPAI in the tropical compactification of \(\mathcal{V}\) are perpendicular to the rays of a smooth refinement of the Newton polytope normal fan.
Sattelberger - van der Veer (2023): If \(\mathcal{V}\) is schön (aka Newton nondegenerate) then all directions with CPAI in the tropical compactification of \(\mathcal{V}\) are perpendicular to the rays of a smooth refinement of the Newton polytope normal fan.
Note: If \(\mathcal{V}\) is schön and its Newton polytope has a smooth normal fan then CPAI occur only in directions parallel to the faces of the Newton polytope.
Sattelberger - van der Veer (2023): If \(\mathcal{V}\) is schön (aka Newton nondegenerate) then all directions with CPAI in the tropical compactification of \(\mathcal{V}\) are perpendicular to the rays of a smooth refinement of the Newton polytope normal fan.
Note: If \(\mathcal{V}\) is schön and its Newton polytope has a smooth normal fan then CPAI occur only in directions parallel to the faces of the Newton polytope.
Baryshnikov, Ergür, George, Gillen, Liu, M., Pemantle (2026): Adapt this to ACSV setting for asymptotics.
The overall viewpoint of smooth ACSV generalizes to non-smooth cases, especially the multiple point case.
Using the surgery method or cones of hyperbolicity, we still need minimal points.
Stratified Morse theory gives a very general framework for ACSV, and reduces the reliance on minimality.
It requires computing certain integers which seems very hard. But we can combine with D-finite techniques!
https://melczer.ca/MPI26
Feel free to contact me with any questions.