AsymptoticRing SageMath Demonstration

Power Series Expansion

$T(z,t)$: Bivariate Generating function for combinatorial class of rooted plane trees ($z$ counts inner nodes, $t$ counts leaves)

In [3]:
def T(z, t):
    return 1/2 * (1 - (z-t) - sqrt(1 - 2*(z+t) + (z-t)^2))
In [4]:
T(z,t).taylor((z,0), (t,0), 4)
Out[4]:

Expansion Operator $\Phi$

In [5]:
def phi(f, z, t):
    return lambda z, t: (1-t) * f(z/(1-t)^2, z*t/(1-t)^2)
In [6]:
phi(T, z, t)(z,t).simplify_rational()
Out[6]:
In [7]:
phi(T, z, t)(z,t).taylor((z,0), (t,0), 4)
Out[7]:
In [8]:
T(z,t).taylor((z,0), (t,0), 4)
Out[8]:
In [9]:
phi(phi(T, z, t), z, t)(z,t).taylor((z,0), (t,0), 4)
Out[9]:

AsymptoticRing and Friends

In [10]:
SCR = SR.subring(no_variables=True) # complex numbers + symbolic constants
A = AsymptoticRing(growth_group='QQ^n * n^QQ * log(n)^QQ', 
                   coefficient_ring=SCR, 
                   default_prec=5)
n = A.gen()
In [12]:
A
Out[12]:
Asymptotic Ring <QQ^n * n^QQ * log(n)^QQ * Signs^n> over Symbolic Constants Subring
In [14]:
A.an_element()
Out[14]:
In [15]:
42 * (1/3)^n * n^(5/2) * log(n)^2  +  O((1/3)^n * n * log(n)^(1/2))
Out[15]:

Straightforward Computations

In [16]:
log(n+1)
Out[16]:
In [17]:
1/(1 + n)
Out[17]:
In [18]:
(1 + 1/n)^n
Out[18]:

Example: Catalan Numbers

In [19]:
binomial_2n_n = asymptotic_expansions.Binomial_kn_over_n(n, k=2, precision=5)
binomial_2n_n
Out[19]:
In [20]:
catalan_asy = binomial_2n_n / (n+1)
catalan_asy
Out[20]:

Extract coefficients from GF

In [21]:
def catalan(z):
    return (1 - sqrt(1 - 4*z)) / (2*z)
In [22]:
catalan_asy = A.coefficients_of_generating_function(catalan, 
                                                    singularities=(1/4,),
                                                    precision=5)
catalan_asy
Out[22]:

Preparation for later: There are $C_{n-1}$ plane trees with $n$ nodes.

In [23]:
shifted_catalan_asy = catalan_asy.subs(n=n-1)
shifted_catalan_asy
Out[23]:

Leaf-Cutting: Expected Tree Size after $r$ Rounds

In [24]:
var('u v')
var('r', domain='integer')
assume(r > 0)
In [25]:
A.<n> = AsymptoticRing('QQ^n * n^QQ', SR)
A_func.<Z> = AsymptoticRing('Z^QQ * log(Z)^QQ', SR)

Some Preparations

In [26]:
# solve z = u/(1+u)^2, get u as a function of z
def upsilon(z):
    return (1 - sqrt(1 - 4*z))/(2*z) - 1
In [27]:
# results from Proposition
def G_r(u, v):
    return (1-u^(r+2)) / ((1-u^(r+1)) * (1+u)) * \
            T(u * (1-u^(r+1))^2 / (1-u^(r+2))^2 * v, 
              u^(r+1) * (1-u)^2 / (1-u^(r+2))^2 * v)

Sum of remaining tree sizes: $[z^n] \partial_v G_r(u,v)|_{v=1}$.

Function Preparation

Expand $\partial_v G_r(u,v)|_{v=1}$ at $z = 1/4$ in terms of $Z$ where $Z = (1 - 4z)^{-1}$.

In [28]:
z_asy = 1/4 * (1-Z^(-1))
u_asy = upsilon(z_asy) + O(Z^(-3))
In [29]:
# Expansion of u(z) in terms of Z
u_asy
Out[29]:
In [30]:
G_r(u, v).diff(v, 1)(v=1).simplify_rational()
Out[30]:

Function Expansion

In [31]:
%%time
sum_of_remaining_nodes_func = fast_callable(G_r(u, v).diff(v, 1)(v=1)\
                                                     .simplify_rational(),
                                            vars=(u, r))(u_asy, r)
CPU times: user 6.49 s, sys: 146 ms, total: 6.63 s
Wall time: 5.99 s
In [32]:
sum_of_remaining_nodes_func
Out[32]:

Coefficient Extraction

In [33]:
sum_of_remaining_nodes_asy = sum_of_remaining_nodes_func\
                             ._singularity_analysis_(n, 
                                                     zeta=1/4, 
                                                     precision=2)
sum_of_remaining_nodes_asy
Out[33]:
In [34]:
expected_tree_size = sum_of_remaining_nodes_asy / A(shifted_catalan_asy)
expected_tree_size
Out[34]:
In [35]:
expected_tree_size.map_coefficients(lambda ex: ex.subs({1/sqrt(r^2 + 2*r + 1) : 1/(r+1)}).factor())
Out[35]:
In [ ]: