ACSV

Generating Functions

Definition.
The generating function for

(f_{i})_{i \geq 0}

is

F (x) = f_{0} + f_{1} x + f_{2} x^{2} + \dots + f_{k} x^{k} + \dots

Example.
The Fibonacci sequence

0, 1, 1, 2, \dots

has generating function

F (x) = x + x^{2} + 2 x^{3} + \dots

We can easily verify that

F (x) = x + x F (x) + x^{2} F (x)

, so

F (x) = \frac{x}{1 - x - x^{2}} .

Extraction of Coefficients

Theorem (Cauchy Integral Formula for Coefficients).
Let

C

be a suitable closed curve about the origin. Then

f_{n} = [z^{n}] F (z) = \frac{1}{2 π i} \int_{C} F (z) \frac{d z}{z^{n + 1}} .

Example.
The Fibonacci generating function

F (x) = \frac{x}{1 - x - x^{2}}

has poles at

ϕ^{- 1}

and

- ϕ

. We have

f_{n} = \frac{1}{2 π i} \int_{| x | = ε} \frac{F (x)}{x^{n + 1}} d x

for

ε < ϕ^{- 1}

.

Extraction of Coefficients

Taking $C_{0}$ arbitrarily far from the origin,

$\int_{C_{0}} \frac{F (x)}{x^{n + 1}} d x \to 0.$

Hence, $f_{n} = - {Res}_{z = - ϕ} \frac{F (z)}{z^{n + 1}} - {Res}_{z = ϕ^{- 1}} \frac{F (z)}{z^{n + 1}} = \frac{1}{\sqrt{5}} (- ϕ^{- n} + ϕ^{n}) .$

The Multivariate Case

Assume $F (z) = \frac{G (z)}{H (z)} = \sum_{i \in N^{d}} f_{i} z^{i} = \sum_{i_{1}, \dots, i_{d} \geq 0} f_{i_{1}, \dots, i_{d}} z_{1}^{i_{1}} \dots z_{d}^{i_{d}}$ is a rational function in $d$ variables.

We consider the

r

-diagonal

[z^{n r}] F (z) = f_{n r_{1}, \dots, n r_{d}} .

Multivariate Generating Functions

Why use more variables?

Tracking parameters.

The number of horizontally convex polyominoes with

n

cells and

k

rows is

[x^{n} y^{k}] F (x, y)

where

F (x, y) = \frac{x y (1 - x)^{3}}{(1 - x)^{4} - x y (1 - x - x^{2} + x^{3} + x^{2} y)} .

Capturing a wider range of sequences.

A Lattice Path Example

As it turns out, the univariate ODE is derived from computing the

(1, 1, 1)

-diagonal of the coefficients of

F (x, y, z) = \frac{(1 + x) (1 - 2 z y^{2} (1 + x^{2}))}{(1 - y) (1 - z (x^{2} y^{2} + y^{2} + x)) (1 - z y^{2} (1 + x^{2}))} .

from sage_acsv import diagonal_asymptotics_combinatorial as diagonal
var('x,y,z')
F = (1 + x)*(2*z*x^2*y^2 + 2*z*y^2 - 1)/((-1 + y)*(z*x^2*y^2 + z*y^2 + z*x - 1)*(z*x^2*y^2 + z*y^2 - 1))
diagonal(F)

Now we've verified that

s_{n} \sim (12 \sqrt{2} - 16) \frac{(- 2 \sqrt{2})^{n}}{π n^{2}} + (12 \sqrt{2} + 16) \frac{(2 \sqrt{2})^{n}}{π n^{2}} .

The Theory of ACSV

Our analysis begins with a familiar result...

Multivariate Cauchy Integral Formula
Given a suitable product of circles

C \subset C^{d}

about the origin,

f_{i} = \frac{1}{(2 π i)^{d}} \int_{C} F (z) \frac{d z}{z^{i + 1}} .

Minimality

How far can we deform our circles of integration?

Definition.
Given

V \subset C^{d}

, we say

w \in V

is minimal if there does not exist

z \in V

such that

| z_{i} | < | v_{i} |

for all

i

.

Testing minimality is hard.

Computational ACSV

Our complexity bounds come from a particular univariate rational representation called the Kronecker representation.

Definition.
Let

f = (f_{1}, \dots, f_{s}) \subset C [z_{1}, \dots, z_{d}]

be a zero-dimensional system. A Kronecker representation of

f

consists of a separating linear form

u = λ_{1} f_{1} + \dots + λ_{s} f_{s}

and polynomials

P, Q_{1}, \dots, Q_{d} \in C [u]

such that there is a 1-to-1 correspondence of solutions

(w_{1}, \dots, w_{d})

to

f

and roots

u

of

P

where

w_{i} = \frac{Q_{i} (u)}{P^{'} (u)}

for

1 \leq i \leq d

.

Computational ACSV

Under assumptions on

H

that are satisfied generically, we obtain the following complexity bound.

Melczer, Salvy 2020.
Let

H

be a polynomial of degree

δ

and height

h

that can be computed with a straight line program of length

L

, and define

D = δ^{d}

. A kronecker representation for the critical point system

\begin{aligned} z_{i} H_{z_{i}} (z) r_{d} - λ r_{i} = & 0 (1 \leq i \leq d), \\ H (z) = & 0, \\ H (t z) = & 0. \end{aligned}

can be computed with a probabilistic algorithm in

\tilde{O} (D^{3} d^{2} (d + h))

bit operations, with polynomials of degree and height at most

n d D

and

\tilde{O} (D d (d + h))

, respectively.

Computational ACSV

Our package comes with an interface for computing a Kronecker Representation.

from sage_acsv import kronecker_representation
var('x,y,z')
sys = [x+y+z, x*y+y*z+x*z, x*y*z - 1]
kronecker_representation(sys, [x,y,z])

We also offer an msolve backend.

from sage_acsv import diagonal_asymptotics_combinatorial as diagonal, ACSVSettings as AS, kronecker_representation
AS.set_default_kronecker_backend(AS.Kronecker.MSOLVE)
var('x,y,z')
sys = [x+y+z, x*y+y*z+x*z, x*y*z - 1]
kronecker_representation(sys, [x,y,z])

Relaxing the Smoothness Condition

When $V (H)$ is non-smooth, we want to decompose it into smooth manifolds.

Whitney Stratifications

Definition.
A Whitney Stratification of the variety

X

is a decomposition

X = X_{d} \supset X_{d - 1} \supset \dots \supset X_{1} \supset X_{0}

such that each

X_{k} ∖ X_{k - 1}

is a manifold of dimension

k

with the additional property that limits of secant lines lie in the limit of tangent spaces of any stratum.

The key result of Whitney Stratification computations, by Helmer and Nanda, come from the following result:

Helmer, Nanda 2022
Let

X \subset P^{n}

be a pure-dimensional projective variety and

Y \subseteq X_{sing}

a subset of the singular locus of

X

. Then there exists a computable variety

A \subseteq Y

such that

Y - A

satisfies Whitney's conditions with respect to

X

.

Such a computation is done over the conormal space of

X

.

Our package comes with an interface for computing Whitney Stratifications.

from sage_acsv import whitney_stratification
R = PolynomialRing(QQ, ['x','y','z'])
x,y,z = R.gens()
IX = Ideal(y^2 + z^3 - x^2*z^2)
whitney_stratification(IX, R)

The General Critical Point Equation

Critical points on

V (p_{1}, \dots, p_{s})

come from the maximal minors of

\begin{array}{r} N = N_{w} (p_{1}, . . ., p_{s}) = (\begin{array}{c} \nabla_{\log} p_{1} (w) \\ ⋮ \\ \nabla_{\log} p_{s} (w) \\ r \end{array}), \end{array}

where

\nabla_{\log} f = (z_{1} f_{z_{1}}, \dots, z_{d} f_{z_{d}})

.

If

V (p_{1}, . . ., p_{s})

is non-smooth, additional algebraic techniques are used to clear extraneous solutions. One option is to take an ideal saturation.

For higher order terms, we must compute an implicitly defined function. This can be achieved via Newton Iteration.

Consider the function

T (x)

implicitly defined by

x T^{2} - T - x = 0

in a neighbourhood of the origin.

from sage_acsv.helpers import compute_newton_series
R = PolynomialRing(QQ, ['x','T'])
x, T = R.gens()
compute_newton_series(x*T^2 - T-x, [x, T], 7)

Complexity of Transverse Case

What is the complexity of solving the transverse critical point system?

Work in progress!

Recall that we are taking maximal minors of

\begin{array}{r} N = N_{w} (p_{1}, . . ., p_{s}) = (\begin{array}{c} \nabla_{\log} p_{1} (w) \\ ⋮ \\ \nabla_{\log} p_{s} (w) \\ r \end{array}), \end{array}

where

\nabla_{\log} f = (z_{1} f_{z_{1}}, \dots, z_{d} f_{z_{d}})

.

We can obtain bounds using a similar technique as that for the smooth case. However, the multihomogeneous nature of the matrix (and that we are taking determinants) may yield more effective bounds.

Example 1. Central Binomial Coefficients

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

var('x y')
F = 1/(1 - x - y)
diagonal(F)

Example 4. Horizontally Convex Polyominoes

F (x, y) = \frac{x y (1 - x)^{3}}{(1 - x)^{4} - x y (1 - x - x^{2} + x^{3} + x^{2} y)}

F (x, y) = \frac{x y (1 - x)^{3}}{(1 - x)^{4} - x y (1 - x - x^{2} + x^{3} + x^{2} y)}

var('x y')
F = x*y*(1 - x)^3/((1 - x)^4 - x*y*(1 - x - x^2 + x^3 + x^2*y))
diagonal(F, r=[2,1])

Example 5. Rooted Binary Trees with Tracked Leaves

Definition
A rooted binary tree consists of a a leaf node

\circ

or an internal node

∙

with one or two children who are binary rooted trees.

Let

T (x, y)

be the generating function where

[x^{n} y^{k}] T (x, y)

is the number of rooted binary trees of n total nodes and k leaves. Then,

T (x, y) = x y + 2 x T (x, y) + x T (x, y)^{2} .

T (x, y) = x y + 2 x T (x, y) + x T (x, y)^{2} .

Then,

T (x, y) = \frac{1 - 2 x - \sqrt{1 - 4 x (1 - x + x y)}}{2 x} .

Fact.
Any algebraic series in

d

variables is a generalized diagonal of a rational series in

d + 1

variables.

Fact.
Any algebraic series in

d

variables is a generalized diagonal of a rational series in

d + 1

variables.

So what about our binary tree example?

Example.
The

[n, k]

diagonal of

T (x, y)

is the

[k, n + k, n + 2 k]

diagonal of

\tilde{T} (u, x, Y) = \frac{G (u, x, Y)}{H (u, x, Y)},

where

H (u, x, Y) = 16 Y^{9} u^{2} x^{8} + 16 Y^{8} u^{2} x^{7} + 12 Y^{7} u^{2} x^{6} + 4 Y^{6} u^{2} x^{5} + 8 Y^{6} u x^{5} + Y^{5} u^{2} x^{4} + 4 Y^{5} u x^{4} + 8 Y^{4} u x^{4} + 2 Y^{4} u x^{3} + Y^{3} x^{2} + 2 Y x - 1,

and

G (u, x, Y) = (64 Y^{12} u^{3} x^{11} + 96 Y^{11} u^{3} x^{10} + 96 Y^{10} u^{3} x^{9} + 56 Y^{9} u^{3} x^{8} + 32 Y^{9} u^{2} x^{8} + 24 Y^{8} u^{3} x^{7} + 32 Y^{8} u^{2} x^{7} + 6 Y^{7} u^{3} x^{6} + 32 Y^{7} u^{2} x^{7} + 24 Y^{7} u^{2} x^{6} + Y^{6} u^{3} x^{5} + 16 Y^{6} u^{2} x^{6} + 8 Y^{6} u^{2} x^{5} + 12 Y^{6} u x^{5} + 8 Y^{5} u^{2} x^{5} + 2 Y^{5} u^{2} x^{4} + 6 Y^{5} u x^{4} + 8 Y^{4} u x^{4} + 3 Y^{4} u x^{3} + 2 Y^{3} x^{2} - Y u x + 2 Y x - 1) Y^{2} x

Example.
The

[n, k]

diagonal of

T (x, y)

is the

[k, n + k, n + 2 k]

diagonal of

\tilde{T} (u, x, Y) = \frac{G (u, x, Y)}{H (u, x, Y)},

where

H (u, x, Y) = 16 Y^{9} u^{2} x^{8} + 16 Y^{8} u^{2} x^{7} + 12 Y^{7} u^{2} x^{6} + 4 Y^{6} u^{2} x^{5} + 8 Y^{6} u x^{5} + Y^{5} u^{2} x^{4} + 4 Y^{5} u x^{4} + 8 Y^{4} u x^{4} + 2 Y^{4} u x^{3} + Y^{3} x^{2} + 2 Y x - 1,

and

G (u, x, Y) = (64 Y^{12} u^{3} x^{11} + 96 Y^{11} u^{3} x^{10} + 96 Y^{10} u^{3} x^{9} + 56 Y^{9} u^{3} x^{8} + 32 Y^{9} u^{2} x^{8} + 24 Y^{8} u^{3} x^{7} + 32 Y^{8} u^{2} x^{7} + 6 Y^{7} u^{3} x^{6} + 32 Y^{7} u^{2} x^{7} + 24 Y^{7} u^{2} x^{6} + Y^{6} u^{3} x^{5} + 16 Y^{6} u^{2} x^{6} + 8 Y^{6} u^{2} x^{5} + 12 Y^{6} u x^{5} + 8 Y^{5} u^{2} x^{5} + 2 Y^{5} u^{2} x^{4} + 6 Y^{5} u x^{4} + 8 Y^{4} u x^{4} + 3 Y^{4} u x^{3} + 2 Y^{3} x^{2} - Y u x + 2 Y x - 1) Y^{2} x

var('u x Y')
F = x*Y^2*(64*Y^12*u^3*x^11 + 96*Y^11*u^3*x^10 + 96*Y^10*u^3*x^9 + 56*Y^9*u^3*x^8 + 32*Y^9*u^2*x^8 + 24*Y^8*u^3*x^7 + 32*Y^8*u^2*x^7 + 6*Y^7*u^3*x^6 + 32*Y^7*u^2*x^7 + 24*Y^7*u^2*x^6 + Y^6*u^3*x^5 + 16*Y^6*u^2*x^6 + 8*Y^6*u^2*x^5 + 12*Y^6*u*x^5 + 8*Y^5*u^2*x^5 + 2*Y^5*u^2*x^4 + 6*Y^5*u*x^4 + 8*Y^4*u*x^4 + 3*Y^4*u*x^3 + 2*Y^3*x^2 - Y*u*x + 2*Y*x - 1)/(16*Y^9*u^2*x^8 + 16*Y^8*u^2*x^7 + 12*Y^7*u^2*x^6 + 4*Y^6*u^2*x^5 + 8*Y^6*u*x^5 + Y^5*u^2*x^4 + 4*Y^5*u*x^4 + 8*Y^4*u*x^4 + 2*Y^4*u*x^3 + Y^3*x^2 + 2*Y*x - 1)
diagonal(F, r=[5,1,4])

Theorem.
The number of rooted binary trees where exactly half the nodes are leaves is

[u^{n} x^{2 n} Y^{3 n}] \tilde{T} (u, x, Y) = (\binom{2 n}{n}) .

Proof.

Left as an exercise.

Applications of Computer Algebra in Analytic Combinatorics

Generating Functions

Extraction of Coefficients

Extraction of Coefficients

Extraction of Coefficients

The Multivariate Case

The Multivariate Case

Multivariate Generating Functions

A Lattice Path Example

A Lattice Path Example

A Lattice Path Example

The Theory of ACSV

The Theory of ACSV

Minimality

Computational ACSV

Computational ACSV

Computational ACSV

Relaxing the Smoothness Condition

Whitney Stratifications

The General Critical Point Equation

The Transverse Case

Complexity of Transverse Case

Example 1. Central Binomial Coefficients

Example 2. Apéry's Numbers

Example 3. Winning Choices in a Single Player Game

Example 4. Horizontally Convex Polyominoes

Example 5. Rooted Binary Trees with Tracked Leaves

What's Next?

Documentation and Further Reading