This notebook contains worked examples from Chapter 4 of the text Analytic Combinatorics in Several Variables (2nd edition) by Pemantle, Wilson and Melczer.¶
Further details can be found on the book website at https://acsvproject.com/acsvbook/ .
Example numbers match the published version.
Lemma 4.5 - Compositional Inverse¶
In [1]:
# Compute compositional inverse using a Newton iteration (which is computationally faster)
# Function takes a function F as a series to order O(x^M)
def Newton(F,M):
y = x/F.diff(x).subs(x=0)
K = RR(log(M,2)).floor()
for k in range(1,K+1):
y = (y - y.diff(x) * (F.subs(x=y)-x)).series(x,2^(k+1)).truncate().polynomial(QQ)
return SR(y).series(x,M).truncate().polynomial(QQ)
In [2]:
# Example inverting sin(x)
F = sin(x).series(x,21).truncate().polynomial(QQ)
g = Newton(F,20)
show("The inverse of \t", latex(sin(x)), " = \t", F)
show("is the function whose series begins")
show(g)
show("The composition of these series equals")
show(SR(F.subs(x=g)).series(x,20))
\(\displaystyle \verb|The|\verb| |\verb|inverse|\verb| |\verb|of|\verb| |\verb| | \sin\left(x\right) \verb| |\verb|=|\verb| |\verb| | -\frac{1}{121645100408832000} x^{19} + \frac{1}{355687428096000} x^{17} - \frac{1}{1307674368000} x^{15} + \frac{1}{6227020800} x^{13} - \frac{1}{39916800} x^{11} + \frac{1}{362880} x^{9} - \frac{1}{5040} x^{7} + \frac{1}{120} x^{5} - \frac{1}{6} x^{3} + x\)
\(\displaystyle \verb|is|\verb| |\verb|the|\verb| |\verb|function|\verb| |\verb|whose|\verb| |\verb|series|\verb| |\verb|begins|\)
\(\displaystyle \frac{12155}{1245184} x^{19} + \frac{6435}{557056} x^{17} + \frac{143}{10240} x^{15} + \frac{231}{13312} x^{13} + \frac{63}{2816} x^{11} + \frac{35}{1152} x^{9} + \frac{5}{112} x^{7} + \frac{3}{40} x^{5} + \frac{1}{6} x^{3} + x\)
\(\displaystyle \verb|The|\verb| |\verb|composition|\verb| |\verb|of|\verb| |\verb|these|\verb| |\verb|series|\verb| |\verb|equals|\)
\(\displaystyle 1 x + \mathcal{O}\left(x^{20}\right)\)
In [3]:
# Do Newton iteration manually over symbolic field
var('a b c d x')
F = a*x + b*x^2 + c*x^3 + d*x^4
y = x/a
y = (y - y.diff(x) * (F.subs(x=y)-x)).series(x,2^2).truncate()
y = (y - y.diff(x) * (F.subs(x=y)-x)).series(x,2^3).truncate()
y = y.series(x,5).expand()
show("The compositional inverse of a function whose series begins")
show(F)
show("is the function whose series begins")
show(y)
show("The composition of these series equals")
show(F.subs(x=y).series(x,5).simplify_full())
\(\displaystyle \verb|The|\verb| |\verb|compositional|\verb| |\verb|inverse|\verb| |\verb|of|\verb| |\verb|a|\verb| |\verb|function|\verb| |\verb|whose|\verb| |\verb|series|\verb| |\verb|begins|\)
\(\displaystyle d x^{4} + c x^{3} + b x^{2} + a x\)
\(\displaystyle \verb|is|\verb| |\verb|the|\verb| |\verb|function|\verb| |\verb|whose|\verb| |\verb|series|\verb| |\verb|begins|\)
\(\displaystyle {(\frac{1}{a})} x + {(-\frac{b}{a^{3}})} x^{2} + {(\frac{2 \, b^{2}}{a^{5}} - \frac{c}{a^{4}})} x^{3} + {(-\frac{5 \, b^{3}}{a^{7}} + \frac{5 \, b c}{a^{6}} - \frac{d}{a^{5}})} x^{4} + \mathcal{O}\left(x^{5}\right)\)
\(\displaystyle \verb|The|\verb| |\verb|composition|\verb| |\verb|of|\verb| |\verb|these|\verb| |\verb|series|\verb| |\verb|equals|\)
\(\displaystyle x + \mathcal{O}\left(x^{5}\right)\)
Example 4.8¶
In [4]:
SCR = SR.subring(no_variables=True) # Create symbolic ring with no variables
A.<n> = AsymptoticRing(
growth_group='QQ^n * n^QQ * log(n)^QQ',
coefficient_ring=SCR,
default_prec=4
)
# Compute an asymptotic expansion
def GF(z):
return (1-z)^(-1/2)
asm = A.coefficients_of_generating_function(
function=GF,
singularities=(1,),
precision=3
)
show("[z^n]", SR("(1-z)^(-1/2)"), " = \t", asm)
\(\displaystyle \verb|[z^n]| \frac{1}{\sqrt{-z + 1}} \verb| |\verb|=|\verb| |\verb| | \frac{1}{\sqrt{\pi}} n^{-\frac{1}{2}} - \frac{1}{8 \, \sqrt{\pi}} n^{-\frac{3}{2}} + \frac{1}{128 \, \sqrt{\pi}} n^{-\frac{5}{2}} + O\!\left(n^{-\frac{7}{2}}\right)\)
In [ ]: