A Short Introduction to Asymptotic Expansions in SageMath

Daniel Krenn, AAU Klagenfurt

@Purdue University, 12.11.2015

A.<n> = AsymptoticRing(growth_group='n^QQ * log(n)^QQ', coefficient_ring=QQ, default_prec=5)

/projects/9a0d876c-4515-4a30-968a-96bd139c3c19/sage-6.10.beta4/local/lib/python2.7/site-packages/sage/structure/unique_representation.py:1021: 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/17601 for details.
  instance = typecall(cls, *args, **options)
/projects/9a0d876c-4515-4a30-968a-96bd139c3c19/sage-6.10.beta4/local/lib/python2.7/site-packages/sage/rings/asymptotic/growth_group_cartesian.py:305: 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/17601 for details.
  GenericGrowthGroup.__init__(self, sets[0], Vars, self.category(), **kwds)

Asymptotic Ring <n^QQ * log(n)^QQ> over Rational Field

n + O(n^(1/2))

n + O(n^(1/2))

n + O(n^2)

O(n^2)

1 / (n-1)

n^(-1) + n^(-2) + n^(-3) + n^(-4) + n^(-5) + O(n^(-6))

exp(1/n)

1 + n^(-1) + 1/2*n^(-2) + 1/6*n^(-3) + 1/24*n^(-4) + O(n^(-5))

log(1/(n+1))

-log(n) - n^(-1) + 1/2*n^(-2) - 1/3*n^(-3) + 1/4*n^(-4) + O(n^(-5))

n.factorial()

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))

# Catalan numbers
(2*n).factorial() / n.factorial()^2 / (n+1)

1/sqrt(pi)*(e^n)^(2*log(2))*n^(-3/2) - 9/8/sqrt(pi)*(e^n)^(2*log(2))*n^(-5/2) + 145/128/sqrt(pi)*(e^n)^(2*log(2))*n^(-7/2) + O((e^n)^(2*log(2))*n^(-9/2))

asymptotic_expansions.SingularityAnalysis('n', alpha=3)

1/2*n^2 + 3/2*n + 1

asymptotic_expansions.SingularityAnalysis('n', alpha=3).parent()

Asymptotic Ring <n^ZZ> over Rational Field

asymptotic_expansions.SingularityAnalysis('n', alpha=-1/2)

-1/2/sqrt(pi)*n^(-3/2) - 3/16/sqrt(pi)*n^(-5/2) - 25/256/sqrt(pi)*n^(-7/2) - 105/2048/sqrt(pi)*n^(-9/2) - 1659/65536/sqrt(pi)*n^(-11/2) - 6237/524288/sqrt(pi)*n^(-13/2) - 50765/8388608/sqrt(pi)*n^(-15/2) - 242385/67108864/sqrt(pi)*n^(-17/2) - 7421843/4294967296/sqrt(pi)*n^(-19/2) - 969969/34359738368/sqrt(pi)*n^(-21/2) - 67456935/549755813888/sqrt(pi)*n^(-23/2) - 8670200175/4398046511104/sqrt(pi)*n^(-25/2) - 104293910895/140737488355328/sqrt(pi)*n^(-27/2) + 6782079968415/1125899906842624/sqrt(pi)*n^(-29/2) + 39625045171275/18014398509481984/sqrt(pi)*n^(-31/2) - 4092706786377825/144115188075855872/sqrt(pi)*n^(-33/2) - 193145813731813635/18446744073709551616/sqrt(pi)*n^(-35/2) + 25703392127157855495/147573952589676412928/sqrt(pi)*n^(-37/2) + 152234998693579097725/2361183241434822606848/sqrt(pi)*n^(-39/2) - 25666434874389019071075/18889465931478580854784/sqrt(pi)*n^(-41/2) + O(n^(-43/2))

s = asymptotic_expansions.SingularityAnalysis('n', alpha=SR.var('a'), precision=5); s

1/gamma(a)*n^(a - 1) + 1/2*((a - 1)*(a - 2) + 2*a - 2)/gamma(a)*n^(a - 2) + 1/24*(3*(a - 1)*(a - 2)*(a - 3)*(a - 4) + 20*(a - 1)*(a - 2)*(a - 3) + 24*(a - 1)*(a - 2))/gamma(a)*n^(a - 3) + 1/48*((a - 1)*(a - 2)*(a - 3)*(a - 4)*(a - 5)*(a - 6) + 14*(a - 1)*(a - 2)*(a - 3)*(a - 4)*(a - 5) + 52*(a - 1)*(a - 2)*(a - 3)*(a - 4) + 48*(a - 1)*(a - 2)*(a - 3))/gamma(a)*n^(a - 4) + 1/5760*(15*(a - 1)*(a - 2)*(a - 3)*(a - 4)*(a - 5)*(a - 6)*(a - 7)*(a - 8) + 360*(a - 1)*(a - 2)*(a - 3)*(a - 4)*(a - 5)*(a - 6)*(a - 7) + 2720*(a - 1)*(a - 2)*(a - 3)*(a - 4)*(a - 5)*(a - 6) + 7392*(a - 1)*(a - 2)*(a - 3)*(a - 4)*(a - 5) + 5760*(a - 1)*(a - 2)*(a - 3)*(a - 4))/gamma(a)*n^(a - 5) + O(n^(a - 6))

s.map_coefficients(lambda c: c.simplify_full())

1/factorial(a - 1)*n^(a - 1) + 1/2*a/((a - 2)*factorial(a - 3))*n^(a - 2) + 1/24*(3*a^2 - a)/((a^2 - 7*a + 12)*factorial(a - 5))*n^(a - 3) + 1/48*(a^3 - a^2)/((a^3 - 15*a^2 + 74*a - 120)*factorial(a - 7))*n^(a - 4) + 1/5760*(15*a^4 - 30*a^3 + 5*a^2 + 2*a)/((a^4 - 26*a^3 + 251*a^2 - 1066*a + 1680)*factorial(a - 9))*n^(a - 5) + O(n^(a - 6))

Example: Bootstrapping

B.<t> = AsymptoticRing(growth_group='QQ^(t^2) * (e^t)^QQ * t^QQ', coefficient_ring=QQ)

z = 2 + O(e^(-t*log(9/8)))

z = 2 - 1 / (z^(t+1) - 1) + O(1 / 2^(t^2)); z

2 - 1/2*(e^t)^(-log(2)) + O((e^t)^(-log(2) - log(9/8))*t)

z = 2 - 1 / (z^(t+1) - 1) + O(1 / 2^(t^2)); z

2 - 1/2*(e^t)^(-log(2)) - 1/8*(e^t)^(-2*log(2))*t - 3/8*(e^t)^(-2*log(2)) + O((e^t)^(-2*log(2) - log(9/8))*t^2)

z = 2 - 1 / (z^(t+1) - 1) + O(1 / 2^(t^2)); z

2 - 1/2*(e^t)^(-log(2)) - 1/8*(e^t)^(-2*log(2))*t - 3/8*(e^t)^(-2*log(2)) - 3/64*(e^t)^(-3*log(2))*t^2 - 19/64*(e^t)^(-3*log(2))*t - 3/8*(e^t)^(-3*log(2)) + O((e^t)^(-3*log(2) - log(9/8))*t^3)