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 |
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
¶ Bases:
sage.structure.sage_object.SageObject
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. IfNone
, 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 fromSymbolic Constants Subring
(ifFalse
) toRational Field
(ifTrue
).
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
sage: S = asymptotic_expansions.Stirling('n', precision=5) sage: n = S.parent().gen() sage: all( # long time ....: SR(asymptotic_expansions.Binomial_kn_over_n( ....: 'n', k=k, precision=3)).canonicalize_radical() == ....: SR(S.subs(n=k*n) / (S.subs(n=(k-1)*n) * S)).canonicalize_radical() ....: for k in [2, 3, 4]) True
-
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. IfNone
, then the default precision of the asymptotic ring is used.skip_constant_summand
– (default:False
) a boolean. If set, then the constant summandeuler_gamma
is left out. As a consequence, the coefficient ring of the output changes fromSymbolic Constants Subring
(ifFalse
) toRational Field
(ifTrue
).
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))
sage: asymptotic_expansions.HarmonicNumber( ....: 'n', precision=5, skip_constant_summand=True) log(n) + 1/2*n^(-1) - 1/12*n^(-2) + 1/120*n^(-4) + O(n^(-6)) sage: _.parent() Asymptotic Ring <n^ZZ * log(n)^ZZ> over Rational Field sage: for p in range(5): ....: print(asymptotic_expansions.HarmonicNumber( ....: 'n', precision=p)) O(log(n)) log(n) + O(1) log(n) + euler_gamma + O(n^(-1)) log(n) + euler_gamma + 1/2*n^(-1) + O(n^(-2)) log(n) + euler_gamma + 1/2*n^(-1) - 1/12*n^(-2) + O(n^(-4)) sage: asymptotic_expansions.HarmonicNumber('m', precision=5) log(m) + euler_gamma + 1/2*m^(-1) - 1/12*m^(-2) + 1/120*m^(-4) + O(m^(-6))
-
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 singularty.beta
– (default: \(0\)) the order of the logarithmic singularity.delta
– (default: \(0\)) the order of the log-log singularity. Not yet implemented fordelta != 0
.precision
– (default:None
) an integer. IfNone
, 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() sage: ae.subs(n=n-1).map_coefficients(lambda x: x.canonicalize_radical()) 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] together with the errata list.
REFERENCES:
[FS2009] (1, 2, 3) Philippe Flajolet and Robert Sedgewick, Analytic combinatorics. Cambridge University Press, Cambridge, 2009. sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', alpha=0) Traceback (most recent call last): ... NotImplementedOZero: The error term in the result is O(0) which means 0 for sufficiently large n. sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', alpha=-1) Traceback (most recent call last): ... NotImplementedOZero: The error term in the result is O(0) which means 0 for sufficiently large n.
sage: asymptotic_expansions.SingularityAnalysis( ....: 'm', alpha=-1/2, precision=3) -1/2/sqrt(pi)*m^(-3/2) - 3/16/sqrt(pi)*m^(-5/2) - 25/256/sqrt(pi)*m^(-7/2) + O(m^(-9/2)) sage: _.parent() Asymptotic Ring <m^QQ> over Symbolic Constants Subring
Location of the singularity:
sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', alpha=1, zeta=2, precision=3) (1/2)^n sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', alpha=1, zeta=1/2, precision=3) 2^n sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', alpha=1, zeta=CyclotomicField(3).gen(), ....: precision=3) (-zeta3 - 1)^n sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', alpha=4, zeta=2, precision=3) 1/6*(1/2)^n*n^3 + (1/2)^n*n^2 + 11/6*(1/2)^n*n + O((1/2)^n) sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', alpha=-1, zeta=2, precision=3) Traceback (most recent call last): ... NotImplementedOZero: The error term in the result is O(0) which means 0 for sufficiently large n. sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', alpha=1/2, zeta=2, precision=3) 1/sqrt(pi)*(1/2)^n*n^(-1/2) - 1/8/sqrt(pi)*(1/2)^n*n^(-3/2) + 1/128/sqrt(pi)*(1/2)^n*n^(-5/2) + O((1/2)^n*n^(-7/2))
The following tests correspond to Table VI.5 in [FS2009].
sage: A.<n> = AsymptoticRing('n^QQ * log(n)^QQ', QQ) sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, alpha=-1/2, beta=1, precision=2, ....: normalized=False) * (- sqrt(pi*n^3)) 1/2*log(n) + 1/2*euler_gamma + log(2) - 1 + O(n^(-1)*log(n)) sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, alpha=0, beta=1, precision=3, ....: normalized=False) n^(-1) + O(n^(-2)) sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, alpha=0, beta=2, precision=14, ....: normalized=False) * n 2*log(n) + 2*euler_gamma - n^(-1) - 1/6*n^(-2) + O(n^(-4)) sage: (asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, alpha=1/2, beta=1, precision=4, ....: normalized=False) * sqrt(pi*n)).\ ....: map_coefficients(lambda x: x.expand()) log(n) + euler_gamma + 2*log(2) - 1/8*n^(-1)*log(n) + (-1/8*euler_gamma - 1/4*log(2))*n^(-1) + O(n^(-2)*log(n)) sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, alpha=1, beta=1, precision=13, ....: normalized=False) log(n) + euler_gamma + 1/2*n^(-1) - 1/12*n^(-2) + 1/120*n^(-4) + O(n^(-6)) sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, alpha=1, beta=2, precision=4, ....: normalized=False) log(n)^2 + 2*euler_gamma*log(n) + euler_gamma^2 - 1/6*pi^2 + O(n^(-1)*log(n)) sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, alpha=3/2, beta=1, precision=3, ....: normalized=False) * sqrt(pi/n) 2*log(n) + 2*euler_gamma + 4*log(2) - 4 + 3/4*n^(-1)*log(n) + O(n^(-1)) sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, alpha=2, beta=1, precision=5, ....: normalized=False) n*log(n) + (euler_gamma - 1)*n + log(n) + euler_gamma + 1/2 + O(n^(-1)) sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, alpha=2, beta=2, precision=4, ....: normalized=False) / n log(n)^2 + (2*euler_gamma - 2)*log(n) - 2*euler_gamma + euler_gamma^2 - 1/6*pi^2 + 2 + n^(-1)*log(n)^2 + O(n^(-1)*log(n))
Be aware that the last result does not coincide with [FS2009], they do have a different error term.
Checking parameters:
sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, 1, 1/2, precision=0, normalized=False) Traceback (most recent call last): ... ValueError: beta and delta must be integers sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', 1, 1, 1, 1/2, normalized=False) Traceback (most recent call last): ... ValueError: beta and delta must be integers
sage: asymptotic_expansions.SingularityAnalysis( ....: 'n', alpha=0, beta=0, delta=1, precision=3) Traceback (most recent call last): ... NotImplementedError: not implemented for delta!=0
-
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\). IfNone
, 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 fromSymbolic Constants Subring
(ifFalse
) toRational Field
(ifTrue
).
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
See also
-
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. IfNone
, 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 fromSymbolic Constants Subring
(ifFalse
) toRational Field
(ifTrue
).
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))
See also
sage: asymptotic_expansions.log_Stirling( ....: 'n', precision=7, skip_constant_summand=True) n*log(n) - n + 1/2*log(n) + 1/12*n^(-1) - 1/360*n^(-3) + 1/1260*n^(-5) + O(n^(-7)) sage: _.parent() Asymptotic Ring <n^ZZ * log(n)^ZZ> over Rational Field sage: asymptotic_expansions.log_Stirling( ....: 'n', precision=0) O(n*log(n)) sage: asymptotic_expansions.log_Stirling( ....: 'n', precision=1) n*log(n) + O(n) sage: asymptotic_expansions.log_Stirling( ....: 'n', precision=2) n*log(n) - n + O(log(n)) sage: asymptotic_expansions.log_Stirling( ....: 'n', precision=3) n*log(n) - n + 1/2*log(n) + O(1) sage: asymptotic_expansions.log_Stirling( ....: 'n', precision=4) n*log(n) - n + 1/2*log(n) + 1/2*log(2*pi) + O(n^(-1)) sage: asymptotic_expansions.log_Stirling( ....: 'n', precision=5) n*log(n) - n + 1/2*log(n) + 1/2*log(2*pi) + 1/12*n^(-1) + O(n^(-3)) sage: asymptotic_expansions.log_Stirling( ....: 'm', precision=7, skip_constant_summand=True) m*log(m) - m + 1/2*log(m) + 1/12*m^(-1) - 1/360*m^(-3) + 1/1260*m^(-5) + O(m^(-7))
-
static
-
sage.rings.asymptotic.asymptotic_expansion_generators.
asymptotic_expansions
= <class 'sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators'>¶ A collection of several common asymptotic expansions.
This is an instance of
AsymptoticExpansionGenerators
whose documentation provides more details.