# Common Asymptotic Expansions¶

Asymptotic expansions in SageMath can be built through the asymptotic_expansions object. It contains generators for common asymptotic expressions. For example,

sage: asymptotic_expansions.Stirling('n', precision=5)
sqrt(2)*sqrt(pi)*e^(n*log(n))*(e^n)^(-1)*n^(1/2) +
1/12*sqrt(2)*sqrt(pi)*e^(n*log(n))*(e^n)^(-1)*n^(-1/2) +
1/288*sqrt(2)*sqrt(pi)*e^(n*log(n))*(e^n)^(-1)*n^(-3/2) +
O(e^(n*log(n))*(e^n)^(-1)*n^(-5/2))


generates the first 5 summands of Stirling’s approximation formula for factorials.

To construct an asymptotic expression manually, you can use the class AsymptoticRing. See asymptotic ring for more details and a lot of examples.

Asymptotic Expansions

 HarmonicNumber() harmonic numbers Stirling() Stirling’s approximation formula for factorials log_Stirling() the logarithm of Stirling’s approximation formula for factorials Binomial_kn_over_n() an asymptotic expansion of the binomial coefficient SingularityAnalysis() an asymptotic expansion obtained by singularity analysis ImplicitExpansion() the singular expansion of a function $$y(z)$$ satisfying $$y(z) = z \Phi(y(z))$$ ImplicitExpansionPeriodicPart() the singular expansion of the periodic part of a function $$y(z)$$ satisfying $$y(z) = z\Phi(y(z))$$ InverseFunctionAnalysis() coefficient growth of a function $$y(z)$$ defined implicitly by $$y(z) = z \Phi(y(z))$$

AUTHORS:

• Daniel Krenn (2015)

• Clemens Heuberger (2016)

• Benjamin Hackl (2016)

ACKNOWLEDGEMENT:

• Benjamin Hackl, Clemens Heuberger and Daniel Krenn are supported by the Austrian Science Fund (FWF): P 24644-N26.

## Classes and Methods¶

class sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators

A collection of constructors for several common asymptotic expansions.

A list of all asymptotic expansions in this database is available via tab completion. Type “asymptotic_expansions.” and then hit tab to see which expansions are available.

The asymptotic expansions currently in this class include:

static Binomial_kn_over_n(var, k, precision=None, skip_constant_factor=False)

Return the asymptotic expansion of the binomial coefficient $$kn$$ choose $$n$$.

INPUT:

• var – a string for the variable name.

• k – a number or symbolic constant.

• precision – (default: None) an integer. If None, then the default precision of the asymptotic ring is used.

• skip_constant_factor – (default: False) a boolean. If set, then the constant factor $$\sqrt{k/(2\pi(k-1))}$$ is left out. As a consequence, the coefficient ring of the output changes from Symbolic Constants Subring (if False) to Rational Field (if True).

OUTPUT:

An asymptotic expansion.

EXAMPLES:

sage: asymptotic_expansions.Binomial_kn_over_n('n', k=2, precision=3)
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))
sage: _.parent()
Asymptotic Ring <QQ^n * n^QQ> over Symbolic Constants Subring

sage: asymptotic_expansions.Binomial_kn_over_n('n', k=3, precision=3)
1/2*sqrt(3)/sqrt(pi)*(27/4)^n*n^(-1/2)
- 7/144*sqrt(3)/sqrt(pi)*(27/4)^n*n^(-3/2)
+ 49/20736*sqrt(3)/sqrt(pi)*(27/4)^n*n^(-5/2)
+ O((27/4)^n*n^(-7/2))

sage: asymptotic_expansions.Binomial_kn_over_n('n', k=7/5, precision=3)
1/2*sqrt(7)/sqrt(pi)*(7/10*7^(2/5)*2^(3/5))^n*n^(-1/2)
- 13/112*sqrt(7)/sqrt(pi)*(7/10*7^(2/5)*2^(3/5))^n*n^(-3/2)
+ 169/12544*sqrt(7)/sqrt(pi)*(7/10*7^(2/5)*2^(3/5))^n*n^(-5/2)
+ O((7/10*7^(2/5)*2^(3/5))^n*n^(-7/2))
sage: _.parent()
Asymptotic Ring <(Symbolic Constants Subring)^n * n^QQ>
over Symbolic Constants Subring

static HarmonicNumber(var, precision=None, skip_constant_summand=False)

Return the asymptotic expansion of a harmonic number.

INPUT:

• var – a string for the variable name.

• precision – (default: None) an integer. If None, then the default precision of the asymptotic ring is used.

• skip_constant_summand – (default: False) a boolean. If set, then the constant summand euler_gamma is left out. As a consequence, the coefficient ring of the output changes from Symbolic Constants Subring (if False) to Rational Field (if True).

OUTPUT:

An asymptotic expansion.

EXAMPLES:

sage: asymptotic_expansions.HarmonicNumber('n', precision=5)
log(n) + euler_gamma + 1/2*n^(-1) - 1/12*n^(-2) + 1/120*n^(-4) + O(n^(-6))

static ImplicitExpansion(var, phi, tau=None, precision=None)

Return the singular expansion for a function $$y(z)$$ defined implicitly by $$y(z) = z \Phi(y(z))$$.

The function $$\Phi$$ is assumed to be analytic around $$0$$. Furthermore, $$\Phi$$ is not allowed to be an affine-linear function and we require $$\Phi(0) \neq 0$$.

Furthermore, it is assumed that there is a unique positive solution $$\tau$$ of $$\Phi(\tau) - \tau\Phi'(\tau) = 0$$.

All details are given in Chapter VI.7 of [FS2009].

INPUT:

• var – a string for the variable name.

• phi – the function $$\Phi$$. See the extended description for assumptions on $$\Phi$$.

• tau – (default: None) the fundamental constant described in the extended description. If None, then $$\tau$$ is determined automatically if possible.

• precision – (default: None) an integer. If None, then the default precision of the asymptotic ring is used.

OUTPUT:

An asymptotic expansion.

Note

In the given case, the radius of convergence of the function of interest is known to be $$\rho = \tau/\Phi(\tau)$$. Until trac ticket #20050 is implemented, the variable in the returned asymptotic expansion represents a singular element of the form $$(1 - z/\rho)^{-1}$$, for the variable $$z\to\rho$$.

EXAMPLES:

We can, for example, determine the singular expansion of the well-known tree function $$T$$ (which satisfies $$T(z) = z \exp(T(z))$$):

sage: asymptotic_expansions.ImplicitExpansion('Z', phi=exp, precision=8)
doctest:warning
...
FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
See http://trac.sagemath.org/20050 for details.
1 - sqrt(2)*Z^(-1/2) + 2/3*Z^(-1) - 11/36*sqrt(2)*Z^(-3/2) +
43/135*Z^(-2) - 769/4320*sqrt(2)*Z^(-5/2) + 1768/8505*Z^(-3) + O(Z^(-7/2))


Another classical example in this context is the generating function $$B(z)$$ enumerating binary trees with respect to the number of inner nodes. The function satisfies $$B(z) = z (1 + 2B(z) + B(z)^2)$$, which can also be solved explicitly, yielding $$B(z) = \frac{1 - \sqrt{1 - 4z}}{2z} - 1$$. We compare the expansions from both approaches:

sage: def B(z):
....:     return (1 - sqrt(1 - 4*z))/(2*z) - 1
sage: A.<Z> = AsymptoticRing('Z^QQ', QQ, default_prec=3)
sage: B((1-1/Z)/4)
1 - 2*Z^(-1/2) + 2*Z^(-1) - 2*Z^(-3/2) + 2*Z^(-2)
- 2*Z^(-5/2) + O(Z^(-3))
sage: asymptotic_expansions.ImplicitExpansion(Z, phi=lambda u: 1 + 2*u + u^2, precision=7)
1 - 2*Z^(-1/2) + 2*Z^(-1) - 2*Z^(-3/2) + 2*Z^(-2)
- 2*Z^(-5/2) + O(Z^(-3))


Neither $$\tau$$ nor $$\Phi$$ have to be known explicitly, they can also be passed symbolically:

sage: tau = var('tau')
sage: phi = function('phi')
sage: asymptotic_expansions.ImplicitExpansion('Z', phi=phi, tau=tau, precision=3)  # long time
tau + (-sqrt(2)*sqrt(-tau*phi(tau)^2/(2*tau*diff(phi(tau), tau)^2
- tau*phi(tau)*diff(phi(tau), tau, tau)
- 2*phi(tau)*diff(phi(tau), tau))))*Z^(-1/2) + O(Z^(-1))


Note that we do not check whether a passed $$\tau$$ actually satisfies the requirements. Only the first of the following expansions is correct:

sage: asymptotic_expansions.ImplicitExpansion('Z',
....:     phi=lambda u: 1 + 2*u + u^2, precision=5) # correct expansion
1 - 2*Z^(-1/2) + 2*Z^(-1) - 2*Z^(-3/2) + O(Z^(-2))
sage: asymptotic_expansions.ImplicitExpansion('Z', phi=lambda u: 1 + 2*u + u^2, tau=2, precision=5)
Traceback (most recent call last):
...
ZeroDivisionError: symbolic division by zero
sage: asymptotic_expansions.ImplicitExpansion('Z', phi=lambda u: 1 + 2*u + u^2, tau=3, precision=5)
3 - 4*I*sqrt(3)*Z^(-1/2) + 6*I*sqrt(3)*Z^(-3/2) + O(Z^(-2))

static ImplicitExpansionPeriodicPart(var, phi, period, tau=None, precision=None)

Return the singular expansion for the periodic part of a function $$y(z)$$ defined implicitly by $$y(z) = z \Phi(y(z))$$.

The function $$\Phi$$ is assumed to be analytic around $$0$$. Furthermore, $$\Phi$$ is not allowed to be an affine-linear function and we require $$\Phi(0) \neq 0$$. For an integer $$p$$, $$\Phi$$ is called $$p$$-periodic if we have $$\Psi(u^p) = \Phi(u)$$ for a power series $$\Psi$$ where $$p$$ is maximal.

Furthermore, it is assumed that there is a unique positive solution $$\tau$$ of $$\Phi(\tau) - \tau\Phi'(\tau) = 0$$.

If $$\Phi$$ is $$p$$-periodic, then we have $$y(z) = z g(z^p)$$. This method returns the singular expansion of $$g(z)$$.

INPUT:

• var – a string for the variable name.

• phi – the function $$\Phi$$. See the extended description for assumptions on $$\Phi$$.

• period – the period of the function $$\Phi$$. See the extended description for details.

• tau – (default: None) the fundamental constant described in the extended description. If None, then $$\tau$$ is determined automatically if possible.

• precision – (default: None) an integer. If None, then the default precision of the asymptotic ring is used.

OUTPUT:

An asymptotic expansion.

Note

In the given case, the radius of convergence of the function of interest is known to be $$\rho = \tau/\Phi(\tau)$$. Until trac ticket #20050 is implemented, the variable in the returned asymptotic expansion represents a singular element of the form $$(1 - z/\rho)^{-1}$$, for the variable $$z\to\rho$$.

EXAMPLES:

The generating function enumerating binary trees with respect to tree size satisfies $$B(z) = z (1 + B(z)^2)$$. This function can be written as $$B(z) = z g(z^2)$$, and as $$B(z)$$ can be determined explicitly we have $$g(z) = \frac{1 - \sqrt{1 - 4z}}{2z}$$. We compare the corresponding expansions:

sage: asymptotic_expansions.ImplicitExpansionPeriodicPart('Z', phi=lambda u: 1 + u^2,
....:                                                     period=2, precision=7)
doctest:warning
...
FutureWarning: This class/method/function is marked as experimental. It, its functionality or its interface might change without a formal deprecation.
See http://trac.sagemath.org/20050 for details.
2 - 2*Z^(-1/2) + 2*Z^(-1) - 2*Z^(-3/2) + 2*Z^(-2) - 2*Z^(-5/2) + O(Z^(-3))
sage: def g(z):
....:     return (1 - sqrt(1 - 4*z))/(2*z)
sage: A.<Z> = AsymptoticRing('Z^QQ', QQ, default_prec=3)
sage: g((1 - 1/Z)/4)
2 - 2*Z^(-1/2) + 2*Z^(-1) - 2*Z^(-3/2) + 2*Z^(-2) - 2*Z^(-5/2) + O(Z^(-3))

static InverseFunctionAnalysis(var, phi, tau=None, period=1, precision=None)

Return the coefficient growth of a function $$y(z)$$ defined implicitly by $$y(z) = z \Phi(y(z))$$.

The function $$\Phi$$ is assumed to be analytic around $$0$$. Furthermore, $$\Phi$$ is not allowed to be an affine-linear function and we require $$\Phi(0) \neq 0$$. For an integer $$p$$, $$\Phi$$ is called $$p$$-periodic if we have $$\Psi(u^p) = \Phi(u)$$ for a power series $$\Psi$$ where $$p$$ is maximal.

Furthermore, it is assumed that there is a unique positive solution $$\tau$$ of $$\Phi(\tau) - \tau\Phi'(\tau) = 0$$.

INPUT:

• var – a string for the variable name.

• phi – the function $$\Phi$$. See the extended description for assumptions on $$\Phi$$.

• tau – (default: None) the fundamental constant described in the extended description. If None, then $$\tau$$ is determined automatically if possible.

• period – (default: $$1$$) the period of the function $$\Phi$$. See the extended description for details.

• precision – (default: None) an integer. If None, then the default precision of the asymptotic ring is used.

OUTPUT:

An asymptotic expansion.

Note

It is not checked that the passed period actually fits to the passed function $$\Phi$$.

The resulting asymptotic expansion is only valid for $$n \equiv 1 \mod p$$, where $$p$$ is the period. All other coefficients are $$0$$.

EXAMPLES:

There are $$C_n$$ (the $$n$$-th Catalan number) different binary trees of size $$2n+1$$, and there are no binary trees with an even number of nodes. The corresponding generating function satisfies $$B(z) = z (1 + B(z)^2)$$, which allows us to compare the asymptotic expansions for the number of binary trees of size $$n$$ obtained via $$C_n$$ and obtained via the analysis of $$B(z)$$:

sage: assume(SR.an_element() > 0)
sage: A.<n> = AsymptoticRing('QQ^n * n^QQ', SR)
sage: binomial_expansion = asymptotic_expansions.Binomial_kn_over_n(n, k=2, precision=3)
sage: catalan_expansion = binomial_expansion / (n+1)
sage: catalan_expansion.subs(n=(n-1)/2)
2*sqrt(1/2)/sqrt(pi)*2^n*n^(-3/2) - 3/2*sqrt(1/2)/sqrt(pi)*2^n*n^(-5/2)
+ 25/16*sqrt(1/2)/sqrt(pi)*2^n*n^(-7/2) + O(2^n*n^(-9/2))
sage: asymptotic_expansions.InverseFunctionAnalysis(n, phi=lambda u: 1 + u^2, period=2,
....:                                               tau=1, precision=8)
2*sqrt(1/2)/sqrt(pi)*2^n*n^(-3/2) - 3/2*sqrt(1/2)/sqrt(pi)*2^n*n^(-5/2)
+ 25/16*sqrt(1/2)/sqrt(pi)*2^n*n^(-7/2) + O(2^n*n^(-9/2))


The code in the aperiodic case is more efficient, however. Therefore, it is recommended to use combinatorial identities to reduce to the aperiodic case. In the example above, this is well-known: we now count binary trees with $$n$$ internal nodes. The corresponding generating function satisfies $$B(z) = z (1 + 2B(z) + B(z)^2)$$:

sage: catalan_expansion
1/sqrt(pi)*4^n*n^(-3/2) - 9/8/sqrt(pi)*4^n*n^(-5/2)
+ 145/128/sqrt(pi)*4^n*n^(-7/2) + O(4^n*n^(-9/2))
sage: asymptotic_expansions.InverseFunctionAnalysis(n, phi=lambda u: 1 + 2*u + u^2,
....:                                               tau=1, precision=8)
1/sqrt(pi)*4^n*n^(-3/2) - 9/8/sqrt(pi)*4^n*n^(-5/2)
+ 145/128/sqrt(pi)*4^n*n^(-7/2) + O(4^n*n^(-9/2))

sage: forget()

static SingularityAnalysis(var, zeta=1, alpha=0, beta=0, delta=0, precision=None, normalized=True)

Return the asymptotic expansion of the coefficients of an power series with specified pole and logarithmic singularity.

More precisely, this extracts the $$n$$-th coefficient

$[z^n] \left(\frac{1}{1-z/\zeta}\right)^\alpha \left(\frac{1}{z/\zeta} \log \frac{1}{1-z/\zeta}\right)^\beta \left(\frac{1}{z/\zeta} \log \left(\frac{1}{z/\zeta} \log \frac{1}{1-z/\zeta}\right)\right)^\delta$

(if normalized=True, the default) or

$[z^n] \left(\frac{1}{1-z/\zeta}\right)^\alpha \left(\log \frac{1}{1-z/\zeta}\right)^\beta \left(\log \left(\frac{1}{z/\zeta} \log \frac{1}{1-z/\zeta}\right)\right)^\delta$

(if normalized=False).

INPUT:

• var – a string for the variable name.

• zeta – (default: $$1$$) the location of the singularity.

• alpha – (default: $$0$$) the pole order of the singularity.

• beta – (default: $$0$$) the order of the logarithmic singularity.

• delta – (default: $$0$$) the order of the log-log singularity. Not yet implemented for delta != 0.

• precision – (default: None) an integer. If None, then the default precision of the asymptotic ring is used.

• normalized – (default: True) a boolean, see above.

OUTPUT:

An asymptotic expansion.

EXAMPLES:

sage: asymptotic_expansions.SingularityAnalysis('n', alpha=1)
1
sage: asymptotic_expansions.SingularityAnalysis('n', alpha=2)
n + 1
sage: asymptotic_expansions.SingularityAnalysis('n', alpha=3)
1/2*n^2 + 3/2*n + 1
sage: _.parent()
Asymptotic Ring <n^ZZ> over Rational Field

sage: asymptotic_expansions.SingularityAnalysis('n', alpha=-3/2,
....:     precision=3)
3/4/sqrt(pi)*n^(-5/2)
+ 45/32/sqrt(pi)*n^(-7/2)
+ 1155/512/sqrt(pi)*n^(-9/2)
+ O(n^(-11/2))
sage: asymptotic_expansions.SingularityAnalysis('n', alpha=-1/2,
....:     precision=3)
-1/2/sqrt(pi)*n^(-3/2)
- 3/16/sqrt(pi)*n^(-5/2)
- 25/256/sqrt(pi)*n^(-7/2)
+ O(n^(-9/2))
sage: asymptotic_expansions.SingularityAnalysis('n', alpha=1/2,
....:     precision=4)
1/sqrt(pi)*n^(-1/2)
- 1/8/sqrt(pi)*n^(-3/2)
+ 1/128/sqrt(pi)*n^(-5/2)
+ 5/1024/sqrt(pi)*n^(-7/2)
+ O(n^(-9/2))
sage: _.parent()
Asymptotic Ring <n^QQ> over Symbolic Constants Subring

sage: S = SR.subring(rejecting_variables=('n',))
sage: asymptotic_expansions.SingularityAnalysis(
....:     'n', alpha=S.var('a'),
....:     precision=4).map_coefficients(lambda c: c.factor())
1/gamma(a)*n^(a - 1)
+ (1/2*(a - 1)*a/gamma(a))*n^(a - 2)
+ (1/24*(3*a - 1)*(a - 1)*(a - 2)*a/gamma(a))*n^(a - 3)
+ (1/48*(a - 1)^2*(a - 2)*(a - 3)*a^2/gamma(a))*n^(a - 4)
+ O(n^(a - 5))
sage: _.parent()
Asymptotic Ring <n^(Symbolic Subring rejecting the variable n)>
over Symbolic Subring rejecting the variable n

sage: ae = asymptotic_expansions.SingularityAnalysis('n',
....:          alpha=1/2, beta=1, precision=4); ae
1/sqrt(pi)*n^(-1/2)*log(n) + ((euler_gamma + 2*log(2))/sqrt(pi))*n^(-1/2)
- 5/8/sqrt(pi)*n^(-3/2)*log(n) + (1/8*(3*euler_gamma + 6*log(2) - 8)/sqrt(pi)
- (euler_gamma + 2*log(2) - 2)/sqrt(pi))*n^(-3/2) + O(n^(-5/2)*log(n))
sage: n = ae.parent().gen()
1/sqrt(pi)*n^(-1/2)*log(n)
+ ((euler_gamma + 2*log(2))/sqrt(pi))*n^(-1/2)
- 1/8/sqrt(pi)*n^(-3/2)*log(n)
+ (-1/8*(euler_gamma + 2*log(2))/sqrt(pi))*n^(-3/2)
+ O(n^(-5/2)*log(n))

sage: asymptotic_expansions.SingularityAnalysis('n',
....:     alpha=1, beta=1/2, precision=4)
log(n)^(1/2) + 1/2*euler_gamma*log(n)^(-1/2)
+ (-1/8*euler_gamma^2 + 1/48*pi^2)*log(n)^(-3/2)
+ (1/16*euler_gamma^3 - 1/32*euler_gamma*pi^2 + 1/8*zeta(3))*log(n)^(-5/2)
+ O(log(n)^(-7/2))

sage: ae = asymptotic_expansions.SingularityAnalysis('n',
....:     alpha=0, beta=2, precision=14)
sage: n = ae.parent().gen()
sage: ae.subs(n=n-2)
2*n^(-1)*log(n) + 2*euler_gamma*n^(-1) - n^(-2) - 1/6*n^(-3) + O(n^(-5))

sage: asymptotic_expansions.SingularityAnalysis(
....:     'n', 1, alpha=-1/2, beta=1, precision=2, normalized=False)
-1/2/sqrt(pi)*n^(-3/2)*log(n)
+ (-1/2*(euler_gamma + 2*log(2) - 2)/sqrt(pi))*n^(-3/2)
+ O(n^(-5/2)*log(n))
sage: asymptotic_expansions.SingularityAnalysis(
....:     'n', 1/2, alpha=0, beta=1, precision=3, normalized=False)
2^n*n^(-1) + O(2^n*n^(-2))


ALGORITHM:

See [FS2009].

static Stirling(var, precision=None, skip_constant_factor=False)

Return Stirling’s approximation formula for factorials.

INPUT:

• var – a string for the variable name.

• precision – (default: None) an integer $$\ge 3$$. If None, then the default precision of the asymptotic ring is used.

• skip_constant_factor – (default: False) a boolean. If set, then the constant factor $$\sqrt{2\pi}$$ is left out. As a consequence, the coefficient ring of the output changes from Symbolic Constants Subring (if False) to Rational Field (if True).

OUTPUT:

An asymptotic expansion.

EXAMPLES:

sage: asymptotic_expansions.Stirling('n', precision=5)
sqrt(2)*sqrt(pi)*e^(n*log(n))*(e^n)^(-1)*n^(1/2) +
1/12*sqrt(2)*sqrt(pi)*e^(n*log(n))*(e^n)^(-1)*n^(-1/2) +
1/288*sqrt(2)*sqrt(pi)*e^(n*log(n))*(e^n)^(-1)*n^(-3/2) +
O(e^(n*log(n))*(e^n)^(-1)*n^(-5/2))
sage: _.parent()
Asymptotic Ring <(e^(n*log(n)))^QQ * (e^n)^QQ * n^QQ * log(n)^QQ>
over Symbolic Constants Subring

static log_Stirling(var, precision=None, skip_constant_summand=False)

Return the logarithm of Stirling’s approximation formula for factorials.

INPUT:

• var – a string for the variable name.

• precision – (default: None) an integer. If None, then the default precision of the asymptotic ring is used.

• skip_constant_summand – (default: False) a boolean. If set, then the constant summand $$\log(2\pi)/2$$ is left out. As a consequence, the coefficient ring of the output changes from Symbolic Constants Subring (if False) to Rational Field (if True).

OUTPUT:

An asymptotic expansion.

EXAMPLES:

sage: asymptotic_expansions.log_Stirling('n', precision=7)
n*log(n) - n + 1/2*log(n) + 1/2*log(2*pi) + 1/12*n^(-1)
- 1/360*n^(-3) + 1/1260*n^(-5) + O(n^(-7))


This is an instance of AsymptoticExpansionGenerators whose documentation provides more details.