PeWiMeCh04

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 \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 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 d x^{4} + c x^{3} + b x^{2} + a x\)

\(\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 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 [ ]: