asymptotics

Functions for determining asymptotics of the coefficients of multivariate rational functions.

The following examples illustrate some typical use cases. We first import relevant functions and define the required symbolic variables:

sage: from sage_acsv import diagonal_asymptotics_combinatorial, get_expansion_terms
sage: var('w x y z')
(w, x, y, z)

The asymptotic expansion for the sequence of central binomial coefficients, \(\binom{2n}{n}\), generated along the \((1, 1)\)-diagonal of \(F(x, y) = \frac{1}{1 - x - y}\) is computed by

sage: diagonal_asymptotics_combinatorial(1 / (1 - x - y))
1/sqrt(pi)*4^n*n^(-1/2) + O(4^n*n^(-3/2))

The precision of the expansion can be controlled by the expansion_precision keyword argument:

sage: diagonal_asymptotics_combinatorial(1 / (1 - x - y), expansion_precision=4)
1/sqrt(pi)*4^n*n^(-1/2) - 1/8/sqrt(pi)*4^n*n^(-3/2) + 1/128/sqrt(pi)*4^n*n^(-5/2) + 5/1024/sqrt(pi)*4^n*n^(-7/2) + O(4^n*n^(-9/2))

sage: F1 = (2*y^2 - x)/(x + y - 1)
sage: diagonal_asymptotics_combinatorial(F1, expansion_precision=3)
1/4/sqrt(pi)*4^n*n^(-3/2) + 3/32/sqrt(pi)*4^n*n^(-5/2) + O(4^n*n^(-7/2))

sage: F2 = (1+x)*(1+y)/(1-w*x*y*(x+y+1/x+1/y))
sage: diagonal_asymptotics_combinatorial(F2, expansion_precision=3)
4/pi*4^n*n^(-1) - 6/pi*4^n*n^(-2) + 1/pi*4^n*n^(-3)*(e^(I*arg(-1)))^n + 19/2/pi*4^n*n^(-3) + O(4^n*n^(-4))

The following example comes from Apéry’s proof concerning the irrationality of \(\zeta(3)\).

sage: F3 = 1/(1 - w*(1 + x)*(1 + y)*(1 + z)*(x*y*z + y*z + y + z + 1))
sage: apery_expansion = diagonal_asymptotics_combinatorial(F3, expansion_precision=2); apery_expansion
1.225275868941647?/pi^(3/2)*33.97056274847714?^n*n^(-3/2) - 0.5128314911970734?/pi^(3/2)*33.97056274847714?^n*n^(-5/2) + O(33.97056274847714?^n*n^(-7/2))

While the representation might suggest otherwise, the numerical constants in the expansion are not approximations, but in fact explicitly known algebraic numbers. We can use the get_expansion_terms() function to inspect them closer:

sage: coefs = get_expansion_terms(apery_expansion); coefs
[Term(coefficient=1.225275868941647?, pi_factor=pi^(-3/2), base=33.97056274847714?, power=-3/2),
 Term(coefficient=-0.5128314911970734?, pi_factor=pi^(-3/2), base=33.97056274847714?, power=-5/2)]
sage: coefs[0].coefficient.radical_expression()
1/4*sqrt(17/2*sqrt(2) + 12)
sage: coefs[0].base.radical_expression()
12*sqrt(2) + 17

sage: F4 = -1/(1 - (1 - x - y)*(20 - x - 40*y))
sage: diagonal_asymptotics_combinatorial(F4, expansion_precision=2)
0.09677555757474702?/sqrt(pi)*5.884442204019508?^n*n^(-1/2) + 0.002581950724843528?/sqrt(pi)*5.884442204019508?^n*n^(-3/2) + O(5.884442204019508?^n*n^(-5/2))

The package raises an exception if it detects that some of the requirements are not met:

sage: F5 = 1/(x^4*y + x^3*y + x^2*y + x*y - 1)
sage: diagonal_asymptotics_combinatorial(F5)
Traceback (most recent call last):
...
ACSVException: No smooth minimal critical points found.

sage: F6 = 1/((-x + 1)^4 - x*y*(x^3 + x^2*y - x^2 - x + 1))
sage: diagonal_asymptotics_combinatorial(F6)  # long time
Traceback (most recent call last):
...
ACSVException: No contributing points found.

Here is the asymptotic growth of the Delannoy numbers:

sage: F7 = 1/(1 - x - y - x*y)
sage: diagonal_asymptotics_combinatorial(F7)
1.015051765128218?/sqrt(pi)*5.828427124746190?^n*n^(-1/2) + O(5.828427124746190?^n*n^(-3/2))

sage: F8 = 1/(1 - x^7)
sage: diagonal_asymptotics_combinatorial(F8)
1/7 + 1/7*(e^(I*arg(-0.2225209339563144? + 0.9749279121818236?*I)))^n + 1/7*(e^(I*arg(-0.2225209339563144? - 0.9749279121818236?*I)))^n + 1/7*(e^(I*arg(-0.9009688679024191? + 0.4338837391175581?*I)))^n + 1/7*(e^(I*arg(-0.9009688679024191? - 0.4338837391175581?*I)))^n + 1/7*(e^(I*arg(0.6234898018587335? + 0.7818314824680299?*I)))^n + 1/7*(e^(I*arg(0.6234898018587335? - 0.7818314824680299?*I)))^n + O(n^(-1))

This example is for a generating function whose singularities have very close moduli:

sage: F9 = 1/(8 - 17*x^3 - 9*x^2 + 7*x)
sage: diagonal_asymptotics_combinatorial(F9, return_points=True)
(0.03396226416457560?*1.285654384750451?^n + O(1.285654384750451?^n*n^(-1)),
 [[0.7778140158516262?]])
sage_acsv.asymptotics.MinimalCriticalCombinatorial(F, r=None, linear_form=None, whitney_strat=None)[source]
sage_acsv.asymptotics.contributing_points_combinatorial(F, r=None, linear_form=None, whitney_strat=None)[source]

Compute contributing points of a multivariate rational function \(F=G/H\) admitting a finite number of critical points.

The function is assumed to have a combinatorial expansion.

INPUT:

  • F – Symbolic fraction, the rational function assumed to have a finite number of critical points.

  • r – (Optional) Length \(d\) vector of positive integers.

  • linear_form – (Optional) A linear combination of the input variables that separates the critical point solutions.

  • whitney_strat – (Optional) If known / precomputed, a Whitney Stratification of \(V(H)\). The program will not check if this stratification is correct. Should be a list of length \(d\), where the \(k\)-th entry is a list of tuples of ideas generators representing a component of the \(k\)-dimensional stratum.

OUTPUT:

A list of minimal contributing points of \(F\) in the direction \(r\).

NOTE:

The code randomly generates a linear form, which for generic rational functions separates the solutions of an intermediate polynomial system with high probability. This separation step can fail, but (assuming \(F\) has a finite number of critical points) the code can be rerun until a separating form is found.

EXAMPLES:

sage: from sage_acsv import contributing_points_combinatorial
sage: var('x y')
(x, y)
sage: pts = contributing_points_combinatorial(1/((1-(2*x+y)/3)*(1-(3*x+y)/4)))
sage: sorted(pts)
[[3/4, 3/2]]
sage_acsv.asymptotics.contributing_points_combinatorial_smooth(G, H, variables, r=None, linear_form=None)[source]

Compute contributing points of a multivariate rational function \(F=G/H\) admitting a finite number of critical points. Assumes that the singular variety of \(F\) is smooth and the function has a combinatorial expansion.

Typically, this function is called as a subroutine of _diagonal_asymptotics_combinatorial_smooth().

INPUT:

  • G, H – Coprime polynomials with \(F = G/H\).

  • variables – List of variables of G and H.

  • r – (Optional) the direction, a vector of positive algebraic numbers (usually integers).

  • linear_form – (Optional) A linear combination of the input variables that separates the critical point solutions.

OUTPUT:

List of minimal critical points of \(F\) in the direction \(r\), as a list of tuples of algebraic numbers.

NOTE:

The code randomly generates a linear form, which for generic rational functions separates the solutions of an intermediate polynomial system with high probability. This separation step can fail, but (assuming F has a finite number of critical points) the code can be rerun until a separating form is found.

EXAMPLES:

sage: from sage_acsv import contributing_points_combinatorial_smooth
sage: R.<x, y, w, lambda_, t, u_> = QQ[]
sage: pts = contributing_points_combinatorial_smooth(
....:     1,
....:     1 - w*(y + x + x^2*y + x*y^2),
....:     [w, x, y],
....: )
sage: sorted(pts)
[[-1/4, -1, -1], [1/4, 1, 1]]
sage_acsv.asymptotics.critical_points(F, r=None, linear_form=None, whitney_strat=None)[source]

Compute critical points of a multivariate rational function \(F=G/H\) admitting a finite number of critical points.

Typically, this function is called as a subroutine of diagonal_asymptotics_combinatorial().

INPUT:

  • F – Symbolic fraction, the rational function of interest.

  • r – (Optional) Length d vector of positive integers

  • linear_form – (Optional) A linear combination of the input variables that separates the critical point solutions

  • whitney_strat – (Optional) If known / precomputed, a Whitney Stratification of \(V(H)\). The program will not check if this stratification is correct. Should be a list of length d, where the k-th entry is a list of tuples of ideas generators representing a component of the k-dimensional stratum.

OUTPUT:

A list of minimal contributing points of \(F\) in the direction \(r\),

NOTE:

The code randomly generates a linear form, which for generic rational functions separates the solutions of an intermediate polynomial system with high probability. This separation step can fail, but (assuming F has a finite number of critical points) the code can be rerun until a separating form is found.

EXAMPLES:

sage: from sage_acsv import critical_points
sage: var('x y')
(x, y)
sage: pts = critical_points(1/((1-(2*x+y)/3)*(1-(3*x+y)/4)))
sage: sorted(pts)
[[2/3, 2], [3/4, 3/2], [1, 1]]
sage_acsv.asymptotics.diagonal_asy(F, r=None, linear_form=None, expansion_precision=1, return_points=False, output_format=None, whitney_strat=None, as_symbolic=False)[source]
sage_acsv.asymptotics.diagonal_asymptotics_combinatorial(F, r=None, linear_form=None, expansion_precision=1, return_points=False, output_format=None, whitney_strat=None, as_symbolic=False)[source]

Asymptotic behavior of the coefficient array of a multivariate rational function \(F\) along a given direction \(r\). The function is assumed to have a combinatorial expansion.

INPUT:

  • F – The rational function \(G/H\) in \(d\) variables. This function is assumed to have a combinatorial expansion.

  • r – (Optional) A vector of length \(d\) of positive algebraic numbers. Defaults to the appropriate vector of all 1’s if not specified.

  • linear_form – (Optional) A linear combination of the input variables that separates the critical point solutions. Is generated randomly if not specified.

  • expansion_precision – (Optional) A positive integer, the number of terms to compute in the asymptotic expansion. Defaults to 1, which only computes the leading term.

  • return_points – (Optional) If True, also returns the coordinates of minimal critical points. By default False.

  • output_format – (Optional) A string or ACSVSettings.Output specifying the way the asymptotic growth is returned. Allowed values currently are:

    • "tuple": the growth is returned as a list of tuples of the form (a, n^b, pi^c, d) such that the \(r\)-diagonal of \(F\) behaves like the sum of a^n n^b pi^c d + O(a^n n^{b-1}) over these tuples.

    • "symbolic": the growth is returned as an expression from the symbolic ring SR in the variable n.

    • "asymptotic": the growth is returned as an expression from an appropriate AsymptoticRing in the variable n.

    • None: the default, which uses the default set for ACSVSettings.Output itself via ACSVSettings.set_default_output_format(). The default behavior is asymptotic output.

  • as_symbolic – deprecated in favor of the equivalent output_format="symbolic". Will be removed in a future release.

  • whitney_strat – (Optional) If known / precomputed, a Whitney Stratification of \(V(H)\). The program will not check if this stratification is correct. Should be a list of length d, where the k-th entry is a list of tuples of ideas generators representing a component of the k-dimensional stratum.

OUTPUT:

A representation of the asymptotic behavior of the coefficient array of \(F\) along the specified direction.

NOTE:

The code randomly generates a linear form, which for generic rational functions separates the solutions of an intermediate polynomial system with high probability. This separation step can fail, but (assuming \(F\) has a finite number of critical points) the code can be rerun until a separating form is found.

EXAMPLES:

sage: from sage_acsv import diagonal_asymptotics_combinatorial
sage: var('x, y, z, w')
(x, y, z, w)
sage: diagonal_asymptotics_combinatorial(1/(1-x-y))
1/sqrt(pi)*4^n*n^(-1/2) + O(4^n*n^(-3/2))
sage: diagonal_asymptotics_combinatorial(1/(1-(1+x)*y), r = [1,2], return_points=True)
(1/sqrt(pi)*4^n*n^(-1/2) + O(4^n*n^(-3/2)), [[1, 1/2]])
sage: diagonal_asymptotics_combinatorial(1/(1-(x+y+z)+(3/4)*x*y*z), output_format="symbolic")
0.840484893481498?*24.68093482214177?^n/(pi*n)
sage: diagonal_asymptotics_combinatorial(1/(1-(x+y+z)+(3/4)*x*y*z))
0.840484893481498?/pi*24.68093482214177?^n*n^(-1) + O(24.68093482214177?^n*n^(-2))
sage: var('n')
n
sage: asy = diagonal_asymptotics_combinatorial(
....:     1/(1 - w*(1 + x)*(1 + y)*(1 + z)*(x*y*z + y*z + y + z + 1)),
....:     output_format="tuple",
....: )
sage: sum([
....:      a.radical_expression()^n * b * c * QQbar(d).radical_expression()
....:      for (a, b, c, d) in asy
....: ])
1/4*(12*sqrt(2) + 17)^n*sqrt(17/2*sqrt(2) + 12)/(pi^(3/2)*n^(3/2))

Not specifying any output_format falls back to the default asymptotic representation:

sage: diagonal_asymptotics_combinatorial(1/(1 - 2*x))
2^n + O(2^n*n^(-1))
sage: diagonal_asymptotics_combinatorial(1/(1 - 2*x), output_format="tuple")
[(2, 1, 1, 1)]

Passing "symbolic" lets the function return an element of the symbolic ring in the variable n that describes the asymptotic growth:

sage: growth = diagonal_asymptotics_combinatorial(1/(1 - 2*x), output_format="symbolic"); growth
2^n
sage: growth.parent()
Symbolic Ring

The argument "asymptotic" constructs an asymptotic expansion over an appropriate AsymptoticRing in the variable n, including the appropriate error term:

sage: assume(SR.an_element() > 0)  # required to make coercions involving SR work properly
sage: growth = diagonal_asymptotics_combinatorial(1/(1 - x - y), output_format="asymptotic"); growth
1/sqrt(pi)*4^n*n^(-1/2) + O(4^n*n^(-3/2))
sage: growth.parent()
Asymptotic Ring <(Algebraic Real Field)^n * n^QQ * (Arg_(Algebraic Field))^n> over Symbolic Ring

Increasing the precision of the expansion returns an expansion with more terms (works for all available output formats):

sage: diagonal_asymptotics_combinatorial(1/(1 - x - y), expansion_precision=3, output_format="asymptotic")
1/sqrt(pi)*4^n*n^(-1/2) - 1/8/sqrt(pi)*4^n*n^(-3/2) + 1/128/sqrt(pi)*4^n*n^(-5/2)
+ O(4^n*n^(-7/2))

The direction of the diagonal, \(r\), defaults to the standard diagonal (i.e., the vector of all 1’s) if not specified. It also supports passing non-integer values, notably rational numbers:

sage: diagonal_asymptotics_combinatorial(1/(1 - x - y), r=(1, 17/42), output_format="symbolic")
1.317305628032865?*2.324541507270374?^n/(sqrt(pi)*sqrt(n))

and even algebraic numbers (note, however, that the performance for complicated algebraic numbers is significantly degraded):

sage: diagonal_asymptotics_combinatorial(1/(1 - x - y), r=(sqrt(2), 1))
0.9238795325112868?/sqrt(pi)*(2.414213562373095?/0.5857864376269049?^1.414213562373095?)^n*n^(-1/2) + O((2.414213562373095?/0.5857864376269049?^1.414213562373095?)^n*n^(-3/2))

sage: diagonal_asymptotics_combinatorial(1/(1 - x - y*x^2), r=(1, 1/2 - 1/2*sqrt(1/5)), output_format="asymptotic")
1.710862642974252?/sqrt(pi)*1.618033988749895?^n*n^(-1/2)
+ O(1.618033988749895?^n*n^(-3/2))

The function times individual steps of the algorithm, timings can be displayed by increasing the printed verbosity level of our debug logger:

sage: import logging
sage: from sage_acsv import ACSVSettings
sage: ACSVSettings.set_logging_level(logging.INFO)
sage: diagonal_asymptotics_combinatorial(1/(1 - x - y))
INFO:sage_acsv:... Executed Kronecker in ... seconds.
INFO:sage_acsv:... Executed Minimal Points in ... seconds.
INFO:sage_acsv:... Executed Final Asymptotics in ... seconds.
1/sqrt(pi)*4^n*n^(-1/2) + O(4^n*n^(-3/2))
sage: ACSVSettings.set_logging_level(logging.WARNING)

Extraction of coefficient asymptotics even works in cases where the singular variety of \(F\) is not smooth but is the transverse union of smooth varieties:

sage: diagonal_asymptotics_combinatorial(1/((1-(2*x+y)/3)*(1-(3*x+y)/4)), r = [17/24, 7/24], output_format = 'asymptotic')
12 + O(n^(-1))

sage: diagonal_asymptotics_combinatorial(1/((1-(2*x+y)/3)*(1-(3*x+y)/4)), r = [17/24, 7/24], output_format = 'asymptotic')
12 + O(n^(-1))
sage: G = (1+x)*(1-x*y^2+x^2)
sage: H = (1-z*(1+x^2+x*y^2))*(1-y)*(1+x^2)
sage: strat = [
....:     [(1-z*(1+x^2+x*y^2), 1-y, 1+x^2)],
....:     [(1-z*(1+x^2+x*y^2), 1-y),(1-z*(1+x^2+x*y^2), 1+x^2),(1-y,1+x^2)],
....:     [(H,)],
....: ]
sage: diagonal_asymptotics_combinatorial(G/H, r = [1,1,1], output_format = 'asymptotic', whitney_strat = strat)
0.866025403784439?/sqrt(pi)*3^n*n^(-1/2) + O(3^n*n^(-3/2))
sage_acsv.asymptotics.minimal_critical_points_combinatorial(F, r=None, linear_form=None, whitney_strat=None)[source]

Compute nonzero minimal critical points of a combinatorial multivariate rational function \(F=G/H\) admitting a finite number of critical points.

The function is assumed to have a combinatorial expansion.

INPUT:

  • F – Symbolic fraction, the rational function of interest.

  • r – (Optional) Length d vector of positive integers

  • linear_form – (Optional) A linear combination of the input variables that separates the critical point solutions

  • whitney_strat – (Optional) If known / precomputed, a Whitney Stratification of \(V(H)\). The program will not check if this stratification is correct. Should be a list of length d, where the k-th entry is a list of tuples of ideas generators representing a component of the k-dimensional stratum.

OUTPUT:

A list of minimal contributing points of \(F\) in the direction \(r\).

NOTE:

The code randomly generates a linear form, which for generic rational functions separates the solutions of an intermediate polynomial system with high probability. This separation step can fail, but (assuming F has a finite number of critical points) the code can be rerun until a separating form is found.

EXAMPLES:

sage: from sage_acsv import minimal_critical_points_combinatorial
sage: var('x y')
(x, y)
sage: pts = minimal_critical_points_combinatorial(1/((1-(2*x+y)/3)*(1-(3*x+y)/4)))
sage: sorted(pts)
[[3/4, 3/2], [1, 1]]
sage_acsv.asymptotics.strip_symbolic(expression)[source]