Asymptotic Ring¶

This module provides a ring (called AsymptoticRing) for computations with asymptotic expansions.

(Informal) Definition¶

An asymptotic expansion is a sum such as

\[5z^3 + 4z^2 + O(z)\]

as \(z \to \infty\) or

\[3x^{42}y^2 + 7x^3y^3 + O(x^2) + O(y)\]

as \(x\) and \(y\) tend to \(\infty\). It is a truncated series (after a finite number of terms), which approximates a function.

The summands of the asymptotic expansions are partially ordered. In this module these summands are the following:

Exact terms \(c\cdot g\) with a coefficient \(c\) and an element \(g\) of a growth group (see below).
\(O\)-terms \(O(g)\) (see Big O notation; also called Bachmann–Landau notation) for a growth group element \(g\) (again see below).

See the Wikipedia article on asymptotic expansions for more details. Further examples of such elements can be found here.

Growth Groups and Elements¶

The elements of a growth group are equipped with a partial order and usually contain a variable. Examples—the order is described below these examples—are

elements of the form \(z^q\) for some integer or rational \(q\) (growth groups with description strings z^ZZ or z^QQ),
elements of the form \(\log(z)^q\) for some integer or rational \(q\) (growth groups log(z)^ZZ or log(z)^QQ),
elements of the form \(a^z\) for some rational \(a\) (growth group QQ^z), or
more sophisticated constructions like products \(x^r \cdot \log(x)^s \cdot a^y \cdot y^q\) (this corresponds to an element of the growth group x^QQ * log(x)^ZZ * QQ^y * y^QQ).

The order in all these examples is induced by the magnitude of the elements as \(x\), \(y\), or \(z\) (independently) tend to \(\infty\). For elements only using the variable \(z\) this means that \(g_1 \leq g_2\) if

\[\lim_{z\to\infty} \frac{g_1}{g_2} \leq 1.\]

Note

Asymptotic rings where the variable tend to some value distinct from \(\infty\) are not yet implemented.

To find out more about

growth groups,
on how they are created and
about the above used descriptions strings

see the top of the module growth group.

More Examples¶

The mathematical constant e as a limit¶

The base of the natural logarithm \(e\) satisfies the equation

\[e = \lim_{n\to\infty} \left(1+\frac{1}{n}\right)^n\]

By using asymptotic expansions, we obtain the more precise result

Sage

sage: E.<n> = AsymptoticRing(growth_group='n^ZZ', coefficient_ring=SR, default_prec=5); E
Asymptotic Ring <n^ZZ> over Symbolic Ring
sage: (1 + 1/n)^n
e - 1/2*e*n^(-1) + 11/24*e*n^(-2) - 7/16*e*n^(-3) + 2447/5760*e*n^(-4) + O(n^(-5))

Python

>>> from sage.all import *
>>> E = AsymptoticRing(growth_group='n^ZZ', coefficient_ring=SR, default_prec=Integer(5), names=('n',)); (n,) = E._first_ngens(1); E
Asymptotic Ring <n^ZZ> over Symbolic Ring
>>> (Integer(1) + Integer(1)/n)**n
e - 1/2*e*n^(-1) + 11/24*e*n^(-2) - 7/16*e*n^(-3) + 2447/5760*e*n^(-4) + O(n^(-5))

Various¶

AUTHORS:

Benjamin Hackl (2015)
Daniel Krenn (2015)
Clemens Heuberger (2016)

ACKNOWLEDGEMENT:

Benjamin Hackl, Clemens Heuberger and Daniel Krenn are supported by the Austrian Science Fund (FWF): P 24644-N26.
Benjamin Hackl is supported by the Google Summer of Code 2015.

Classes and Methods¶

class sage.rings.asymptotic.asymptotic_ring.AsymptoticExpansion(parent, summands, simplify=True, convert=True)[source]¶

Bases: CommutativeAlgebraElement

Class for asymptotic expansions, i.e., the elements of an AsymptoticRing.

INPUT:

parent – the parent of the asymptotic expansion
summands – the summands as a MutablePoset, which represents the underlying structure
simplify – boolean (default: True); it controls automatic simplification (absorption) of the asymptotic expansion
convert – boolean (default: True); if set, then the summands are converted to the asymptotic ring (the parent of this expansion). If not, then the summands are taken as they are. In that case, the caller must ensure that the parent of the terms is set correctly.

EXAMPLES:

There are several ways to create asymptotic expansions; usually this is done by using the corresponding asymptotic rings:

Sage

sage: R_x.<x> = AsymptoticRing(growth_group='x^QQ', coefficient_ring=QQ); R_x
Asymptotic Ring <x^QQ> over Rational Field
sage: R_y.<y> = AsymptoticRing(growth_group='y^ZZ', coefficient_ring=ZZ); R_y
Asymptotic Ring <y^ZZ> over Integer Ring

Python

>>> from sage.all import *
>>> R_x = AsymptoticRing(growth_group='x^QQ', coefficient_ring=QQ, names=('x',)); (x,) = R_x._first_ngens(1); R_x
Asymptotic Ring <x^QQ> over Rational Field
>>> R_y = AsymptoticRing(growth_group='y^ZZ', coefficient_ring=ZZ, names=('y',)); (y,) = R_y._first_ngens(1); R_y
Asymptotic Ring <y^ZZ> over Integer Ring

At this point, \(x\) and \(y\) are already asymptotic expansions:

Sage

sage: type(x)
<class 'sage.rings.asymptotic.asymptotic_ring.AsymptoticRing_with_category.element_class'>

Python

>>> from sage.all import *
>>> type(x)
<class 'sage.rings.asymptotic.asymptotic_ring.AsymptoticRing_with_category.element_class'>

The usual ring operations, but allowing rational exponents (growth group x^QQ) can be performed:

Sage

sage: x^2 + 3*(x - x^(2/5))
x^2 + 3*x - 3*x^(2/5)
sage: (3*x^(1/3) + 2)^3
27*x + 54*x^(2/3) + 36*x^(1/3) + 8

Python

>>> from sage.all import *
>>> x**Integer(2) + Integer(3)*(x - x**(Integer(2)/Integer(5)))
x^2 + 3*x - 3*x^(2/5)
>>> (Integer(3)*x**(Integer(1)/Integer(3)) + Integer(2))**Integer(3)
27*x + 54*x^(2/3) + 36*x^(1/3) + 8

One of the central ideas behind computing with asymptotic expansions is that the \(O\)-notation (see Wikipedia article Big_O_notation) can be used. For example, we have:

Sage

sage: (x+2*x^2+3*x^3+4*x^4) * (O(x)+x^2)
4*x^6 + O(x^5)

Python

>>> from sage.all import *
>>> (x+Integer(2)*x**Integer(2)+Integer(3)*x**Integer(3)+Integer(4)*x**Integer(4)) * (O(x)+x**Integer(2))
4*x^6 + O(x^5)

In particular, O() can be used to construct the asymptotic expansions. With the help of the summands(), we can also have a look at the inner structure of an asymptotic expansion:

Sage

sage: expr1 = x + 2*x^2 + 3*x^3 + 4*x^4; expr2 = O(x) + x^2
sage: print(expr1.summands.repr_full())
poset(x, 2*x^2, 3*x^3, 4*x^4)
+-- null
|   +-- no predecessors
|   +-- successors:   x
+-- x
|   +-- predecessors:   null
|   +-- successors:   2*x^2
+-- 2*x^2
|   +-- predecessors:   x
|   +-- successors:   3*x^3
+-- 3*x^3
|   +-- predecessors:   2*x^2
|   +-- successors:   4*x^4
+-- 4*x^4
|   +-- predecessors:   3*x^3
|   +-- successors:   oo
+-- oo
|   +-- predecessors:   4*x^4
|   +-- no successors
sage: print(expr2.summands.repr_full())
poset(O(x), x^2)
+-- null
|   +-- no predecessors
|   +-- successors:   O(x)
+-- O(x)
|   +-- predecessors:   null
|   +-- successors:   x^2
+-- x^2
|   +-- predecessors:   O(x)
|   +-- successors:   oo
+-- oo
|   +-- predecessors:   x^2
|   +-- no successors
sage: print((expr1 * expr2).summands.repr_full())
poset(O(x^5), 4*x^6)
+-- null
|   +-- no predecessors
|   +-- successors:   O(x^5)
+-- O(x^5)
|   +-- predecessors:   null
|   +-- successors:   4*x^6
+-- 4*x^6
|   +-- predecessors:   O(x^5)
|   +-- successors:   oo
+-- oo
|   +-- predecessors:   4*x^6
|   +-- no successors

Python

>>> from sage.all import *
>>> expr1 = x + Integer(2)*x**Integer(2) + Integer(3)*x**Integer(3) + Integer(4)*x**Integer(4); expr2 = O(x) + x**Integer(2)
>>> print(expr1.summands.repr_full())
poset(x, 2*x^2, 3*x^3, 4*x^4)
+-- null
|   +-- no predecessors
|   +-- successors:   x
+-- x
|   +-- predecessors:   null
|   +-- successors:   2*x^2
+-- 2*x^2
|   +-- predecessors:   x
|   +-- successors:   3*x^3
+-- 3*x^3
|   +-- predecessors:   2*x^2
|   +-- successors:   4*x^4
+-- 4*x^4
|   +-- predecessors:   3*x^3
|   +-- successors:   oo
+-- oo
|   +-- predecessors:   4*x^4
|   +-- no successors
>>> print(expr2.summands.repr_full())
poset(O(x), x^2)
+-- null
|   +-- no predecessors
|   +-- successors:   O(x)
+-- O(x)
|   +-- predecessors:   null
|   +-- successors:   x^2
+-- x^2
|   +-- predecessors:   O(x)
|   +-- successors:   oo
+-- oo
|   +-- predecessors:   x^2
|   +-- no successors
>>> print((expr1 * expr2).summands.repr_full())
poset(O(x^5), 4*x^6)
+-- null
|   +-- no predecessors
|   +-- successors:   O(x^5)
+-- O(x^5)
|   +-- predecessors:   null
|   +-- successors:   4*x^6
+-- 4*x^6
|   +-- predecessors:   O(x^5)
|   +-- successors:   oo
+-- oo
|   +-- predecessors:   4*x^6
|   +-- no successors

In addition to the monomial growth elements from above, we can also compute with logarithmic terms (simply by constructing the appropriate growth group):

Sage

sage: R_log = AsymptoticRing(growth_group='log(x)^QQ', coefficient_ring=QQ)
sage: lx = R_log(log(SR.var('x')))
sage: (O(lx) + lx^3)^4
log(x)^12 + O(log(x)^10)

Python

>>> from sage.all import *
>>> R_log = AsymptoticRing(growth_group='log(x)^QQ', coefficient_ring=QQ)
>>> lx = R_log(log(SR.var('x')))
>>> (O(lx) + lx**Integer(3))**Integer(4)
log(x)^12 + O(log(x)^10)

B(valid_from=0)[source]¶

Convert all terms in this asymptotic expansion to \(B\)-terms.

INPUT:

valid_from – dictionary mapping variable names to lower bounds for the corresponding variable. The bound implied by this term is valid when all variables are at least their corresponding lower bound. If a number is passed to valid_from, then the lower bounds for all variables of the asymptotic expansion are set to this number

OUTPUT: an asymptotic expansion

EXAMPLES:

Sage

sage: AR.<x, z> = AsymptoticRing(growth_group='x^ZZ * z^ZZ', coefficient_ring=ZZ)
sage: AR.B(2*x^2, {x: 10}) # indirect doctest
B(2*x^2, x >= 10)
sage: expr = 42*x^42 + x^10 + AR.B(x^2, 20); expr # indirect doctest
42*x^42 + x^10 + B(x^2, x >= 20, z >= 20)
sage: type(AR.B(x, 10)) # indirect doctest
<class 'sage.rings.asymptotic.asymptotic_ring.AsymptoticRing_with_category.element_class'>
sage: 2*z^3 + AR.B(5*z^2, {z: 20}) # indirect doctest
2*z^3 + B(5*z^2, z >= 20)
sage: (2*x).B({x: 20})
B(2*x, x >= 20)
sage: AR.B(4*x^2*z^3, valid_from=10) # indirect doctest
B(4*x^2*z^3, x >= 10, z >= 10)
sage: AR.B(42*x^2) # indirect doctest
B(42*x^2, x >= 0, z >= 0)

Python

>>> from sage.all import *
>>> AR = AsymptoticRing(growth_group='x^ZZ * z^ZZ', coefficient_ring=ZZ, names=('x', 'z',)); (x, z,) = AR._first_ngens(2)
>>> AR.B(Integer(2)*x**Integer(2), {x: Integer(10)}) # indirect doctest
B(2*x^2, x >= 10)
>>> expr = Integer(42)*x**Integer(42) + x**Integer(10) + AR.B(x**Integer(2), Integer(20)); expr # indirect doctest
42*x^42 + x^10 + B(x^2, x >= 20, z >= 20)
>>> type(AR.B(x, Integer(10))) # indirect doctest
<class 'sage.rings.asymptotic.asymptotic_ring.AsymptoticRing_with_category.element_class'>
>>> Integer(2)*z**Integer(3) + AR.B(Integer(5)*z**Integer(2), {z: Integer(20)}) # indirect doctest
2*z^3 + B(5*z^2, z >= 20)
>>> (Integer(2)*x).B({x: Integer(20)})
B(2*x, x >= 20)
>>> AR.B(Integer(4)*x**Integer(2)*z**Integer(3), valid_from=Integer(10)) # indirect doctest
B(4*x^2*z^3, x >= 10, z >= 10)
>>> AR.B(Integer(42)*x**Integer(2)) # indirect doctest
B(42*x^2, x >= 0, z >= 0)

O()[source]¶

Convert all terms in this asymptotic expansion to \(O\)-terms.

OUTPUT: an asymptotic expansion

EXAMPLES:

Sage

sage: AR.<x> = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: O(x)
O(x)
sage: type(O(x))
<class 'sage.rings.asymptotic.asymptotic_ring.AsymptoticRing_with_category.element_class'>
sage: expr = 42*x^42 + x^10 + O(x^2); expr
42*x^42 + x^10 + O(x^2)
sage: expr.O()
O(x^42)
sage: (2*x).O()
O(x)

Python

>>> from sage.all import *
>>> AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ, names=('x',)); (x,) = AR._first_ngens(1)
>>> O(x)
O(x)
>>> type(O(x))
<class 'sage.rings.asymptotic.asymptotic_ring.AsymptoticRing_with_category.element_class'>
>>> expr = Integer(42)*x**Integer(42) + x**Integer(10) + O(x**Integer(2)); expr
42*x^42 + x^10 + O(x^2)
>>> expr.O()
O(x^42)
>>> (Integer(2)*x).O()
O(x)

See also

sage.rings.power_series_ring.PowerSeriesRing(), sage.rings.laurent_series_ring.LaurentSeriesRing().

compare_with_values(variable, function, values, rescaled=True, ring=Real Interval Field with 53 bits of precision)[source]¶

Compute the (rescaled) difference between this asymptotic expansion and the given values.

INPUT:

variable – an asymptotic expansion or a string
function – a callable or symbolic expression giving the comparison values
values – list or iterable of values where the comparison shall be carried out
rescaled – boolean (default: True); determines whether the difference is divided by the error term of the asymptotic expansion
ring – (default: RIF) the parent into which the difference is converted

OUTPUT:

A list of pairs containing comparison points and (rescaled) difference values.

EXAMPLES:

Sage

sage: assume(SR.an_element() > 0)
sage: A.<n> = AsymptoticRing('QQ^n * n^ZZ', SR)
sage: catalan = binomial(2*x, x)/(x+1)
sage: expansion = 4^n*(1/sqrt(pi)*n^(-3/2)
....:     - 9/8/sqrt(pi)*n^(-5/2)
....:     + 145/128/sqrt(pi)*n^(-7/2) + O(n^(-9/2)))
sage: expansion.compare_with_values(n, catalan, srange(5, 10))
[(5, 0.5303924444775?),
 (6, 0.5455279498787?),
 (7, 0.556880411050?),
 (8, 0.565710587724?),
 (9, 0.572775029098?)]
sage: expansion.exact_part().compare_with_values(n, catalan, [5, 10, 20])
Traceback (most recent call last):
...
NotImplementedError: exactly one error term required
sage: expansion.exact_part().compare_with_values(n, catalan, [5, 10, 20], rescaled=False)
[(5, 0.3886263699387?), (10, 19.1842458318?), (20, 931314.63637?)]
sage: expansion.compare_with_values(n, catalan, [5, 10, 20], rescaled=False, ring=SR)
[(5, 168/5*sqrt(5)/sqrt(pi) - 42),
 (10, 1178112/125*sqrt(10)/sqrt(pi) - 16796),
 (20, 650486218752/125*sqrt(5)/sqrt(pi) - 6564120420)]

Python

>>> from sage.all import *
>>> assume(SR.an_element() > Integer(0))
>>> A = AsymptoticRing('QQ^n * n^ZZ', SR, names=('n',)); (n,) = A._first_ngens(1)
>>> catalan = binomial(Integer(2)*x, x)/(x+Integer(1))
>>> expansion = Integer(4)**n*(Integer(1)/sqrt(pi)*n**(-Integer(3)/Integer(2))
...     - Integer(9)/Integer(8)/sqrt(pi)*n**(-Integer(5)/Integer(2))
...     + Integer(145)/Integer(128)/sqrt(pi)*n**(-Integer(7)/Integer(2)) + O(n**(-Integer(9)/Integer(2))))
>>> expansion.compare_with_values(n, catalan, srange(Integer(5), Integer(10)))
[(5, 0.5303924444775?),
 (6, 0.5455279498787?),
 (7, 0.556880411050?),
 (8, 0.565710587724?),
 (9, 0.572775029098?)]
>>> expansion.exact_part().compare_with_values(n, catalan, [Integer(5), Integer(10), Integer(20)])
Traceback (most recent call last):
...
NotImplementedError: exactly one error term required
>>> expansion.exact_part().compare_with_values(n, catalan, [Integer(5), Integer(10), Integer(20)], rescaled=False)
[(5, 0.3886263699387?), (10, 19.1842458318?), (20, 931314.63637?)]
>>> expansion.compare_with_values(n, catalan, [Integer(5), Integer(10), Integer(20)], rescaled=False, ring=SR)
[(5, 168/5*sqrt(5)/sqrt(pi) - 42),
 (10, 1178112/125*sqrt(10)/sqrt(pi) - 16796),
 (20, 650486218752/125*sqrt(5)/sqrt(pi) - 6564120420)]

Instead of a symbolic expression, a callable function can be specified as well:

Sage

sage: A.<n> = AsymptoticRing('n^ZZ * log(n)^ZZ', SR)
sage: def H(n):
....:     return sum(1/k for k in srange(1, n+1))
sage: H_expansion = (log(n) + euler_gamma + 1/(2*n)
....:                - 1/(12*n^2) + O(n^-4))
sage: H_expansion.compare_with_values(n, H, srange(25, 30)) # rel tol 1e-6
[(25, -0.008326995?),
 (26, -0.008327472?),
 (27, -0.008327898?),
 (28, -0.00832828?),
 (29, -0.00832862?)]
sage: forget()

Python

>>> from sage.all import *
>>> A = AsymptoticRing('n^ZZ * log(n)^ZZ', SR, names=('n',)); (n,) = A._first_ngens(1)
>>> def H(n):
...     return sum(Integer(1)/k for k in srange(Integer(1), n+Integer(1)))
>>> H_expansion = (log(n) + euler_gamma + Integer(1)/(Integer(2)*n)
...                - Integer(1)/(Integer(12)*n**Integer(2)) + O(n**-Integer(4)))
>>> H_expansion.compare_with_values(n, H, srange(Integer(25), Integer(30))) # rel tol 1e-6
[(25, -0.008326995?),
 (26, -0.008327472?),
 (27, -0.008327898?),
 (28, -0.00832828?),
 (29, -0.00832862?)]
>>> forget()

See also

plot_comparison()

error_part()[source]¶

Return the expansion consisting of all error terms of this expansion.

OUTPUT: an asymptotic expansion

EXAMPLES:

Sage

sage: R.<x,y> = AsymptoticRing('x^QQ * log(x)^QQ * y^QQ', QQ)
sage: (x*log(x) + y^2 + O(x) + O(y)).error_part()
O(x) + O(y)

Python

>>> from sage.all import *
>>> R = AsymptoticRing('x^QQ * log(x)^QQ * y^QQ', QQ, names=('x', 'y',)); (x, y,) = R._first_ngens(2)
>>> (x*log(x) + y**Integer(2) + O(x) + O(y)).error_part()
O(x) + O(y)

exact_part()[source]¶

Return the expansion consisting of all exact terms of this expansion.

OUTPUT: an asymptotic expansion

EXAMPLES:

Sage

sage: R.<x> = AsymptoticRing('x^QQ * log(x)^QQ', QQ)
sage: (x^2 + O(x)).exact_part()
x^2
sage: (x + log(x)/2 + O(log(x)/x)).exact_part()
x + 1/2*log(x)

Python

>>> from sage.all import *
>>> R = AsymptoticRing('x^QQ * log(x)^QQ', QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> (x**Integer(2) + O(x)).exact_part()
x^2
>>> (x + log(x)/Integer(2) + O(log(x)/x)).exact_part()
x + 1/2*log(x)

exp(precision=None)[source]¶

Return the exponential of (i.e., the power of \(e\) to) this asymptotic expansion.

INPUT:

precision – the precision used for truncating the expansion. If None (default value) is used, the default precision of the parent is used.

OUTPUT: an asymptotic expansion

Note

The exponential function of this expansion can only be computed exactly if the respective growth element can be constructed in the underlying growth group.

ALGORITHM:

If the corresponding growth can be constructed, return the exact exponential function. Otherwise, if this term is \(o(1)\), try to expand the series and truncate according to the given precision.

Todo

As soon as \(L\)-terms are implemented, this implementation has to be adapted as well in order to yield correct results.

EXAMPLES:

Sage

sage: A.<x> = AsymptoticRing('(e^x)^ZZ * x^ZZ * log(x)^ZZ', SR)
sage: exp(x)
e^x
sage: exp(2*x)
(e^x)^2
sage: exp(x + log(x))
e^x*x

Python

>>> from sage.all import *
>>> A = AsymptoticRing('(e^x)^ZZ * x^ZZ * log(x)^ZZ', SR, names=('x',)); (x,) = A._first_ngens(1)
>>> exp(x)
e^x
>>> exp(Integer(2)*x)
(e^x)^2
>>> exp(x + log(x))
e^x*x

Sage

sage: (x^(-1)).exp(precision=7)
1 + x^(-1) + 1/2*x^(-2) + 1/6*x^(-3) + ... + O(x^(-7))

Python

>>> from sage.all import *
>>> (x**(-Integer(1))).exp(precision=Integer(7))
1 + x^(-1) + 1/2*x^(-2) + 1/6*x^(-3) + ... + O(x^(-7))

factorial()[source]¶

Return the factorial of this asymptotic expansion.

OUTPUT: an asymptotic expansion

EXAMPLES:

Sage

sage: A.<n> = AsymptoticRing(growth_group='n^ZZ * log(n)^ZZ', coefficient_ring=ZZ, default_prec=5)
sage: 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))
sage: _.parent()
Asymptotic Ring <(e^(n*log(n)))^QQ * (e^n)^QQ * n^QQ * log(n)^QQ>
over Symbolic Constants Subring

Python

>>> from sage.all import *
>>> A = AsymptoticRing(growth_group='n^ZZ * log(n)^ZZ', coefficient_ring=ZZ, default_prec=Integer(5), names=('n',)); (n,) = A._first_ngens(1)
>>> 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))
>>> _.parent()
Asymptotic Ring <(e^(n*log(n)))^QQ * (e^n)^QQ * n^QQ * log(n)^QQ>
over Symbolic Constants Subring

Catalan numbers \(\frac{1}{n+1}\binom{2n}{n}\):

Sage

sage: (2*n).factorial() / n.factorial()^2 / (n+1)  # long time
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))

Python

>>> from sage.all import *
>>> (Integer(2)*n).factorial() / n.factorial()**Integer(2) / (n+Integer(1))  # long time
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))

Note that this method substitutes the asymptotic expansion into Stirling’s formula. This substitution has to be possible which is not always guaranteed:

Sage

sage: S.<s> = AsymptoticRing(growth_group='s^QQ * log(s)^QQ', coefficient_ring=QQ, default_prec=4)
sage: log(s).factorial()
Traceback (most recent call last):
...
TypeError: Cannot apply the substitution rules {s: log(s)} on
sqrt(2)*sqrt(pi)*e^(s*log(s))*(e^s)^(-1)*s^(1/2)
+ O(e^(s*log(s))*(e^s)^(-1)*s^(-1/2)) in
Asymptotic Ring <(e^(s*log(s)))^QQ * (e^s)^QQ * s^QQ * log(s)^QQ>
over Symbolic Constants Subring.
...

Python

>>> from sage.all import *
>>> S = AsymptoticRing(growth_group='s^QQ * log(s)^QQ', coefficient_ring=QQ, default_prec=Integer(4), names=('s',)); (s,) = S._first_ngens(1)
>>> log(s).factorial()
Traceback (most recent call last):
...
TypeError: Cannot apply the substitution rules {s: log(s)} on
sqrt(2)*sqrt(pi)*e^(s*log(s))*(e^s)^(-1)*s^(1/2)
+ O(e^(s*log(s))*(e^s)^(-1)*s^(-1/2)) in
Asymptotic Ring <(e^(s*log(s)))^QQ * (e^s)^QQ * s^QQ * log(s)^QQ>
over Symbolic Constants Subring.
...

See also

Stirling()

has_same_summands(other)[source]¶

Return whether this asymptotic expansion and other have the same summands.

INPUT:

other – an asymptotic expansion

OUTPUT: boolean

Note

While for example O(x) == O(x) yields False, these expansions do have the same summands and this method returns True.

Moreover, this method uses the coercion model in order to find a common parent for this asymptotic expansion and other.

EXAMPLES:

Sage

sage: R_ZZ.<x_ZZ> = AsymptoticRing('x^ZZ', ZZ)
sage: R_QQ.<x_QQ> = AsymptoticRing('x^ZZ', QQ)
sage: sum(x_ZZ^k for k in range(5)) == sum(x_QQ^k for k in range(5))  # indirect doctest
True
sage: O(x_ZZ) == O(x_QQ)
False

Python

>>> from sage.all import *
>>> R_ZZ = AsymptoticRing('x^ZZ', ZZ, names=('x_ZZ',)); (x_ZZ,) = R_ZZ._first_ngens(1)
>>> R_QQ = AsymptoticRing('x^ZZ', QQ, names=('x_QQ',)); (x_QQ,) = R_QQ._first_ngens(1)
>>> sum(x_ZZ**k for k in range(Integer(5))) == sum(x_QQ**k for k in range(Integer(5)))  # indirect doctest
True
>>> O(x_ZZ) == O(x_QQ)
False

invert(precision=None)[source]¶

Return the multiplicative inverse of this element.

INPUT:

precision – the precision used for truncating the expansion. If None (default value) is used, the default precision of the parent is used.

OUTPUT: an asymptotic expansion

Warning

Due to truncation of infinite expansions, the element returned by this method might not fulfill el * ~el == 1.

Todo

As soon as \(L\)-terms are implemented, this implementation has to be adapted as well in order to yield correct results.

EXAMPLES:

Sage

sage: R.<x> = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=QQ, default_prec=4)
sage: ~x
x^(-1)
sage: ~(x^42)
x^(-42)
sage: ex = ~(1 + x); ex
x^(-1) - x^(-2) + x^(-3) - x^(-4) + O(x^(-5))
sage: ex * (1+x)
1 + O(x^(-4))
sage: ~(1 + O(1/x))
1 + O(x^(-1))

Python

>>> from sage.all import *
>>> R = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=QQ, default_prec=Integer(4), names=('x',)); (x,) = R._first_ngens(1)
>>> ~x
x^(-1)
>>> ~(x**Integer(42))
x^(-42)
>>> ex = ~(Integer(1) + x); ex
x^(-1) - x^(-2) + x^(-3) - x^(-4) + O(x^(-5))
>>> ex * (Integer(1)+x)
1 + O(x^(-4))
>>> ~(Integer(1) + O(Integer(1)/x))
1 + O(x^(-1))

is_exact()[source]¶

Return whether all terms of this expansion are exact.

OUTPUT: boolean

EXAMPLES:

Sage

sage: A.<x> = AsymptoticRing('x^QQ * log(x)^QQ', QQ)
sage: (x^2 + O(x)).is_exact()
False
sage: (x^2 - x).is_exact()
True

Python

>>> from sage.all import *
>>> A = AsymptoticRing('x^QQ * log(x)^QQ', QQ, names=('x',)); (x,) = A._first_ngens(1)
>>> (x**Integer(2) + O(x)).is_exact()
False
>>> (x**Integer(2) - x).is_exact()
True

is_little_o_of_one()[source]¶

Return whether this expansion is of order \(o(1)\).

OUTPUT: boolean

EXAMPLES:

Sage

sage: A.<x> = AsymptoticRing('x^ZZ * log(x)^ZZ', QQ)
sage: (x^4 * log(x)^(-2) + x^(-4) * log(x)^2).is_little_o_of_one()
False
sage: (x^(-1) * log(x)^1234 + x^(-2) + O(x^(-3))).is_little_o_of_one()
True
sage: (log(x) - log(x-1)).is_little_o_of_one()
True

Python

>>> from sage.all import *
>>> A = AsymptoticRing('x^ZZ * log(x)^ZZ', QQ, names=('x',)); (x,) = A._first_ngens(1)
>>> (x**Integer(4) * log(x)**(-Integer(2)) + x**(-Integer(4)) * log(x)**Integer(2)).is_little_o_of_one()
False
>>> (x**(-Integer(1)) * log(x)**Integer(1234) + x**(-Integer(2)) + O(x**(-Integer(3)))).is_little_o_of_one()
True
>>> (log(x) - log(x-Integer(1))).is_little_o_of_one()
True

Sage

sage: A.<x, y> = AsymptoticRing('x^QQ * y^QQ * log(y)^ZZ', QQ)
sage: (x^(-1/16) * y^32 + x^32 * y^(-1/16)).is_little_o_of_one()
False
sage: (x^(-1) * y^(-3) + x^(-3) * y^(-1)).is_little_o_of_one()
True
sage: (x^(-1) * y / log(y)).is_little_o_of_one()
False
sage: (log(y-1)/log(y) - 1).is_little_o_of_one()
True

Python

>>> from sage.all import *
>>> A = AsymptoticRing('x^QQ * y^QQ * log(y)^ZZ', QQ, names=('x', 'y',)); (x, y,) = A._first_ngens(2)
>>> (x**(-Integer(1)/Integer(16)) * y**Integer(32) + x**Integer(32) * y**(-Integer(1)/Integer(16))).is_little_o_of_one()
False
>>> (x**(-Integer(1)) * y**(-Integer(3)) + x**(-Integer(3)) * y**(-Integer(1))).is_little_o_of_one()
True
>>> (x**(-Integer(1)) * y / log(y)).is_little_o_of_one()
False
>>> (log(y-Integer(1))/log(y) - Integer(1)).is_little_o_of_one()
True

See also

limit()

limit()[source]¶

Compute the limit of this asymptotic expansion.

OUTPUT: an element of the coefficient ring

EXAMPLES:

Sage

sage: A.<s> = AsymptoticRing("s^ZZ", SR, default_prec=3)
sage: (3 + 1/s + O(1/s^2)).limit()
3
sage: ((1+1/s)^s).limit()
e
sage: (1/s).limit()
0
sage: (s + 3 + 1/s + O(1/s^2)).limit()
Traceback (most recent call last):
...
ValueError: Cannot determine limit of s + 3 + s^(-1) + O(s^(-2))
sage: (O(s^0)).limit()
Traceback (most recent call last):
...
ValueError: Cannot determine limit of O(1)

Python

>>> from sage.all import *
>>> A = AsymptoticRing("s^ZZ", SR, default_prec=Integer(3), names=('s',)); (s,) = A._first_ngens(1)
>>> (Integer(3) + Integer(1)/s + O(Integer(1)/s**Integer(2))).limit()
3
>>> ((Integer(1)+Integer(1)/s)**s).limit()
e
>>> (Integer(1)/s).limit()
0
>>> (s + Integer(3) + Integer(1)/s + O(Integer(1)/s**Integer(2))).limit()
Traceback (most recent call last):
...
ValueError: Cannot determine limit of s + 3 + s^(-1) + O(s^(-2))
>>> (O(s**Integer(0))).limit()
Traceback (most recent call last):
...
ValueError: Cannot determine limit of O(1)

See also

is_little_o_of_one()

log(base=None, precision=None, locals=None)[source]¶

The logarithm of this asymptotic expansion.

INPUT:

base – the base of the logarithm. If None (default value) is used, the natural logarithm is taken.
precision – the precision used for truncating the expansion. If None (default value) is used, the default precision of the parent is used.
locals – dictionary which may contain the following keys and values:
- 'log' – value: a function. If not used, then the usual log is taken.

OUTPUT: an asymptotic expansion

Note

Computing the logarithm of an asymptotic expansion is possible if and only if there is exactly one maximal summand in the expansion.

ALGORITHM:

If the expansion has more than one summand, the asymptotic expansion for \(\log(1+t)\) as \(t\) tends to \(0\) is used.

Todo

As soon as \(L\)-terms are implemented, this implementation has to be adapted as well in order to yield correct results.

EXAMPLES:

Sage

sage: R.<x> = AsymptoticRing(growth_group='x^ZZ * log(x)^ZZ', coefficient_ring=QQ)
sage: log(x)
log(x)
sage: log(x^2)
2*log(x)
sage: log(x-1)
log(x) - x^(-1) - 1/2*x^(-2) - 1/3*x^(-3) - ... + O(x^(-21))

Python

>>> from sage.all import *
>>> R = AsymptoticRing(growth_group='x^ZZ * log(x)^ZZ', coefficient_ring=QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> log(x)
log(x)
>>> log(x**Integer(2))
2*log(x)
>>> log(x-Integer(1))
log(x) - x^(-1) - 1/2*x^(-2) - 1/3*x^(-3) - ... + O(x^(-21))

The coefficient ring is automatically extended if needed:

Sage

sage: R.<x> = AsymptoticRing(growth_group='x^ZZ * log(x)^ZZ', coefficient_ring=ZZ, default_prec=3)
sage: (49*x^3-1).log()
3*log(x) + 2*log(7) - 1/49*x^(-3) - 1/4802*x^(-6) ... + O(x^(-12))
sage: _.parent()
Asymptotic Ring <x^ZZ * log(x)^ZZ> over Symbolic Ring

Python

>>> from sage.all import *
>>> R = AsymptoticRing(growth_group='x^ZZ * log(x)^ZZ', coefficient_ring=ZZ, default_prec=Integer(3), names=('x',)); (x,) = R._first_ngens(1)
>>> (Integer(49)*x**Integer(3)-Integer(1)).log()
3*log(x) + 2*log(7) - 1/49*x^(-3) - 1/4802*x^(-6) ... + O(x^(-12))
>>> _.parent()
Asymptotic Ring <x^ZZ * log(x)^ZZ> over Symbolic Ring

If one wants to avoid this extending to the Symbolic Ring, then the following helps:

Sage

sage: L.<log7> = ZZ[]
sage: def mylog(z, base=None):
....:     try:
....:         if ZZ(z).is_power_of(7):
....:             return log(ZZ(z), 7) * log7
....:     except (TypeError, ValueError):
....:         pass
....:     return log(z, base)
sage: R.<x> = AsymptoticRing(growth_group='x^ZZ * log(x)^ZZ', coefficient_ring=L, default_prec=3)
sage: (49*x^3-1).log(locals={'log': mylog})
3*log(x) + 2*log7 - 1/49*x^(-3) - 1/4802*x^(-6) ... + O(x^(-12))

Python

>>> from sage.all import *
>>> L = ZZ['log7']; (log7,) = L._first_ngens(1)
>>> def mylog(z, base=None):
...     try:
...         if ZZ(z).is_power_of(Integer(7)):
...             return log(ZZ(z), Integer(7)) * log7
...     except (TypeError, ValueError):
...         pass
...     return log(z, base)
>>> R = AsymptoticRing(growth_group='x^ZZ * log(x)^ZZ', coefficient_ring=L, default_prec=Integer(3), names=('x',)); (x,) = R._first_ngens(1)
>>> (Integer(49)*x**Integer(3)-Integer(1)).log(locals={'log': mylog})
3*log(x) + 2*log7 - 1/49*x^(-3) - 1/4802*x^(-6) ... + O(x^(-12))

A log-function can also be specified to always be used with the asymptotic ring:

Sage

sage: R.<x> = AsymptoticRing(growth_group='x^ZZ * log(x)^ZZ', coefficient_ring=L, default_prec=3, locals={'log': mylog})
sage: log(49*x^3-1)
3*log(x) + 2*log7 - 1/49*x^(-3) - 1/4802*x^(-6) - 1/352947*x^(-9) + O(x^(-12))

Python

>>> from sage.all import *
>>> R = AsymptoticRing(growth_group='x^ZZ * log(x)^ZZ', coefficient_ring=L, default_prec=Integer(3), locals={'log': mylog}, names=('x',)); (x,) = R._first_ngens(1)
>>> log(Integer(49)*x**Integer(3)-Integer(1))
3*log(x) + 2*log7 - 1/49*x^(-3) - 1/4802*x^(-6) - 1/352947*x^(-9) + O(x^(-12))

map_coefficients(f, new_coefficient_ring=None)[source]¶

Return the asymptotic expansion obtained by applying f to each coefficient of this asymptotic expansion.

INPUT:

f – a callable; a coefficient \(c\) will be mapped to \(f(c)\)
new_coefficient_ring – (default: None) a ring

OUTPUT: an asymptotic expansion

EXAMPLES:

Sage

sage: A.<n> = AsymptoticRing(growth_group='n^ZZ', coefficient_ring=ZZ)
sage: a = n^4 + 2*n^3 + 3*n^2 + O(n)
sage: a.map_coefficients(lambda c: c+1)
2*n^4 + 3*n^3 + 4*n^2 + O(n)
sage: a.map_coefficients(lambda c: c-2)
-n^4 + n^2 + O(n)

Python

>>> from sage.all import *
>>> A = AsymptoticRing(growth_group='n^ZZ', coefficient_ring=ZZ, names=('n',)); (n,) = A._first_ngens(1)
>>> a = n**Integer(4) + Integer(2)*n**Integer(3) + Integer(3)*n**Integer(2) + O(n)
>>> a.map_coefficients(lambda c: c+Integer(1))
2*n^4 + 3*n^3 + 4*n^2 + O(n)
>>> a.map_coefficients(lambda c: c-Integer(2))
-n^4 + n^2 + O(n)

monomial_coefficient(monomial)[source]¶

Return the coefficient in the base ring of the given monomial in this expansion.

INPUT:

monomial – a monomial element which can be converted into the asymptotic ring of this element

OUTPUT: an element of the coefficient ring

EXAMPLES:

Sage

sage: R.<m, n> = AsymptoticRing("m^QQ*n^QQ", QQ)
sage: ae = 13 + 42/n + 2/n/m + O(n^-2)
sage: ae.monomial_coefficient(1/n)
42
sage: ae.monomial_coefficient(1/n^3)
0
sage: R.<n> = AsymptoticRing("n^QQ", ZZ)
sage: ae.monomial_coefficient(1/n)
42
sage: ae.monomial_coefficient(1)
13

Python

>>> from sage.all import *
>>> R = AsymptoticRing("m^QQ*n^QQ", QQ, names=('m', 'n',)); (m, n,) = R._first_ngens(2)
>>> ae = Integer(13) + Integer(42)/n + Integer(2)/n/m + O(n**-Integer(2))
>>> ae.monomial_coefficient(Integer(1)/n)
42
>>> ae.monomial_coefficient(Integer(1)/n**Integer(3))
0
>>> R = AsymptoticRing("n^QQ", ZZ, names=('n',)); (n,) = R._first_ngens(1)
>>> ae.monomial_coefficient(Integer(1)/n)
42
>>> ae.monomial_coefficient(Integer(1))
13

plot_comparison(variable, function, values, rescaled=True, ring=Real Interval Field with 53 bits of precision, relative_tolerance=0.025, **kwargs)[source]¶

Plot the (rescaled) difference between this asymptotic expansion and the given values.

INPUT:

variable – an asymptotic expansion or a string
function – a callable or symbolic expression giving the comparison values
values – list or iterable of values where the comparison shall be carried out
rescaled – boolean (default: True); determines whether the difference is divided by the error term of the asymptotic expansion
ring – (default: RIF) the parent into which the difference is converted
relative_tolerance – (default: 0.025) raise error when relative error exceeds this tolerance

Other keyword arguments are passed to list_plot().

OUTPUT: a graphics object

Note

If rescaled (i.e. divided by the error term), the output should be bounded.

This method is mainly meant to have an easily usable plausibility check for asymptotic expansion created in some way.

EXAMPLES:

We want to check the quality of the asymptotic expansion of the harmonic numbers:

Sage

sage: A.<n> = AsymptoticRing('n^ZZ * log(n)^ZZ', SR)
sage: def H(n):
....:     return sum(1/k for k in srange(1, n+1))
sage: H_expansion = (log(n) + euler_gamma + 1/(2*n)
....:                - 1/(12*n^2) + O(n^-4))
sage: H_expansion.plot_comparison(n, H, srange(1, 30))
Graphics object consisting of 1 graphics primitive

Python

>>> from sage.all import *
>>> A = AsymptoticRing('n^ZZ * log(n)^ZZ', SR, names=('n',)); (n,) = A._first_ngens(1)
>>> def H(n):
...     return sum(Integer(1)/k for k in srange(Integer(1), n+Integer(1)))
>>> H_expansion = (log(n) + euler_gamma + Integer(1)/(Integer(2)*n)
...                - Integer(1)/(Integer(12)*n**Integer(2)) + O(n**-Integer(4)))
>>> H_expansion.plot_comparison(n, H, srange(Integer(1), Integer(30)))
Graphics object consisting of 1 graphics primitive

Alternatively, the unscaled (absolute) difference can be plotted as well:

Sage

sage: H_expansion.plot_comparison(n, H, srange(1, 30),
....:                             rescaled=False)
Graphics object consisting of 1 graphics primitive

Python

>>> from sage.all import *
>>> H_expansion.plot_comparison(n, H, srange(Integer(1), Integer(30)),
...                             rescaled=False)
Graphics object consisting of 1 graphics primitive

Additional keywords are passed to list_plot():

Sage

sage: H_expansion.plot_comparison(n, H, srange(1, 30),
....:                             plotjoined=True, marker='o',
....:                             color='green')
Graphics object consisting of 1 graphics primitive

Python

>>> from sage.all import *
>>> H_expansion.plot_comparison(n, H, srange(Integer(1), Integer(30)),
...                             plotjoined=True, marker='o',
...                             color='green')
Graphics object consisting of 1 graphics primitive

See also

compare_with_values()

pow(exponent, precision=None)[source]¶

Calculate the power of this asymptotic expansion to the given exponent.

INPUT:

exponent – an element
precision – the precision used for truncating the expansion. If None (default value) is used, the default precision of the parent is used.

OUTPUT: an asymptotic expansion

EXAMPLES:

Sage

sage: Q.<x> = AsymptoticRing(growth_group='x^QQ', coefficient_ring=QQ)
sage: x^(1/7)
x^(1/7)
sage: (x^(1/2) + O(x^0))^15
x^(15/2) + O(x^7)

Python

>>> from sage.all import *
>>> Q = AsymptoticRing(growth_group='x^QQ', coefficient_ring=QQ, names=('x',)); (x,) = Q._first_ngens(1)
>>> x**(Integer(1)/Integer(7))
x^(1/7)
>>> (x**(Integer(1)/Integer(2)) + O(x**Integer(0)))**Integer(15)
x^(15/2) + O(x^7)

Sage

sage: Z.<y> = AsymptoticRing(growth_group='y^ZZ', coefficient_ring=ZZ)
sage: y^(1/7)
y^(1/7)
sage: _.parent()
Asymptotic Ring <y^QQ> over Rational Field
sage: (y^2 + O(y))^(1/2)
y + O(1)
sage: (y^2 + O(y))^(-2)
y^(-4) + O(y^(-5))
sage: (1 + 1/y + O(1/y^3))^pi
1 + pi*y^(-1) + (1/2*pi*(pi - 1))*y^(-2) + O(y^(-3))

Python

>>> from sage.all import *
>>> Z = AsymptoticRing(growth_group='y^ZZ', coefficient_ring=ZZ, names=('y',)); (y,) = Z._first_ngens(1)
>>> y**(Integer(1)/Integer(7))
y^(1/7)
>>> _.parent()
Asymptotic Ring <y^QQ> over Rational Field
>>> (y**Integer(2) + O(y))**(Integer(1)/Integer(2))
y + O(1)
>>> (y**Integer(2) + O(y))**(-Integer(2))
y^(-4) + O(y^(-5))
>>> (Integer(1) + Integer(1)/y + O(Integer(1)/y**Integer(3)))**pi
1 + pi*y^(-1) + (1/2*pi*(pi - 1))*y^(-2) + O(y^(-3))

Sage

sage: B.<z> = AsymptoticRing(growth_group='z^QQ * log(z)^QQ', coefficient_ring=QQ)
sage: (z^2 + O(z))^(1/2)
z + O(1)

Python

>>> from sage.all import *
>>> B = AsymptoticRing(growth_group='z^QQ * log(z)^QQ', coefficient_ring=QQ, names=('z',)); (z,) = B._first_ngens(1)
>>> (z**Integer(2) + O(z))**(Integer(1)/Integer(2))
z + O(1)

Sage

sage: A.<x> = AsymptoticRing('QQ^x * x^SR * log(x)^ZZ', QQ)
sage: x * 2^x
2^x*x
sage: 5^x * 2^x
10^x
sage: 2^log(x)
x^(log(2))
sage: 2^(x + 1/x)
2^x + log(2)*2^x*x^(-1) + 1/2*log(2)^2*2^x*x^(-2) + ... + O(2^x*x^(-20))
sage: _.parent()
Asymptotic Ring <QQ^x * x^SR * log(x)^QQ * Signs^x> over Symbolic Ring

Python

>>> from sage.all import *
>>> A = AsymptoticRing('QQ^x * x^SR * log(x)^ZZ', QQ, names=('x',)); (x,) = A._first_ngens(1)
>>> x * Integer(2)**x
2^x*x
>>> Integer(5)**x * Integer(2)**x
10^x
>>> Integer(2)**log(x)
x^(log(2))
>>> Integer(2)**(x + Integer(1)/x)
2^x + log(2)*2^x*x^(-1) + 1/2*log(2)^2*2^x*x^(-2) + ... + O(2^x*x^(-20))
>>> _.parent()
Asymptotic Ring <QQ^x * x^SR * log(x)^QQ * Signs^x> over Symbolic Ring

Sage

sage: C.<c> = AsymptoticRing(growth_group='QQ^c * c^QQ', coefficient_ring=QQ, default_prec=5)
sage: (3 + 1/c^2)^c
3^c + 1/3*3^c*c^(-1) + 1/18*3^c*c^(-2) - 4/81*3^c*c^(-3)
- 35/1944*3^c*c^(-4) + O(3^c*c^(-5))
sage: _.parent()
Asymptotic Ring <QQ^c * c^QQ * Signs^c> over Rational Field
sage: (2 + (1/3)^c)^c
2^c + 1/2*(2/3)^c*c + 1/8*(2/9)^c*c^2 - 1/8*(2/9)^c*c
+ 1/48*(2/27)^c*c^3 + O((2/27)^c*c^2)
sage: _.parent()
Asymptotic Ring <QQ^c * c^QQ * Signs^c> over Rational Field

Python

>>> from sage.all import *
>>> C = AsymptoticRing(growth_group='QQ^c * c^QQ', coefficient_ring=QQ, default_prec=Integer(5), names=('c',)); (c,) = C._first_ngens(1)
>>> (Integer(3) + Integer(1)/c**Integer(2))**c
3^c + 1/3*3^c*c^(-1) + 1/18*3^c*c^(-2) - 4/81*3^c*c^(-3)
- 35/1944*3^c*c^(-4) + O(3^c*c^(-5))
>>> _.parent()
Asymptotic Ring <QQ^c * c^QQ * Signs^c> over Rational Field
>>> (Integer(2) + (Integer(1)/Integer(3))**c)**c
2^c + 1/2*(2/3)^c*c + 1/8*(2/9)^c*c^2 - 1/8*(2/9)^c*c
+ 1/48*(2/27)^c*c^3 + O((2/27)^c*c^2)
>>> _.parent()
Asymptotic Ring <QQ^c * c^QQ * Signs^c> over Rational Field

rpow(base, precision=None, locals=None)[source]¶

Return the power of base to this asymptotic expansion.

INPUT:

base – an element or 'e'
precision – the precision used for truncating the expansion. If None (default value) is used, the default precision of the parent is used.
locals – dictionary which may contain the following keys and values:
- 'log' – value: a function. If not used, then the usual log is taken.

OUTPUT: an asymptotic expansion

EXAMPLES:

Sage

sage: A.<x> = AsymptoticRing('x^ZZ', QQ)
sage: (1/x).rpow('e', precision=5)
1 + x^(-1) + 1/2*x^(-2) + 1/6*x^(-3) + 1/24*x^(-4) + O(x^(-5))

Python

>>> from sage.all import *
>>> A = AsymptoticRing('x^ZZ', QQ, names=('x',)); (x,) = A._first_ngens(1)
>>> (Integer(1)/x).rpow('e', precision=Integer(5))
1 + x^(-1) + 1/2*x^(-2) + 1/6*x^(-3) + 1/24*x^(-4) + O(x^(-5))

show()[source]¶

Pretty-print this asymptotic expansion.

OUTPUT:

Nothing, the representation is printed directly on the screen.

EXAMPLES:

Sage

sage: A.<x> = AsymptoticRing('QQ^x * x^QQ * log(x)^QQ', SR.subring(no_variables=True))
sage: (pi/2 * 5^x * x^(42/17) - sqrt(euler_gamma) * log(x)^(-7/8)).show()
1/2*pi*5^x*x^(42/17) - sqrt(euler_gamma)*log(x)^(-7/8)

Python

>>> from sage.all import *
>>> A = AsymptoticRing('QQ^x * x^QQ * log(x)^QQ', SR.subring(no_variables=True), names=('x',)); (x,) = A._first_ngens(1)
>>> (pi/Integer(2) * Integer(5)**x * x**(Integer(42)/Integer(17)) - sqrt(euler_gamma) * log(x)**(-Integer(7)/Integer(8))).show()
1/2*pi*5^x*x^(42/17) - sqrt(euler_gamma)*log(x)^(-7/8)

sqrt(precision=None)[source]¶

Return the square root of this asymptotic expansion.

INPUT:

precision – the precision used for truncating the expansion. If None (default value) is used, the default precision of the parent is used.

OUTPUT: an asymptotic expansion

EXAMPLES:

Sage

sage: A.<s> = AsymptoticRing(growth_group='s^QQ', coefficient_ring=QQ)
sage: s.sqrt()
s^(1/2)
sage: a = (1 + 1/s).sqrt(precision=6); a
1 + 1/2*s^(-1) - 1/8*s^(-2) + 1/16*s^(-3)
- 5/128*s^(-4) + 7/256*s^(-5) + O(s^(-6))

Python

>>> from sage.all import *
>>> A = AsymptoticRing(growth_group='s^QQ', coefficient_ring=QQ, names=('s',)); (s,) = A._first_ngens(1)
>>> s.sqrt()
s^(1/2)
>>> a = (Integer(1) + Integer(1)/s).sqrt(precision=Integer(6)); a
1 + 1/2*s^(-1) - 1/8*s^(-2) + 1/16*s^(-3)
- 5/128*s^(-4) + 7/256*s^(-5) + O(s^(-6))

See also

pow(), rpow(), exp().

subs(rules=None, domain=None, **kwds)[source]¶

Substitute the given rules in this asymptotic expansion.

INPUT:

rules – dictionary
kwds – keyword arguments will be added to the substitution rules
domain – (default: None) a parent. The neutral elements \(0\) and \(1\) (rules for the keys '_zero_' and '_one_', see note box below) are taken out of this domain. If None, then this is determined automatically.

OUTPUT: an object

Note

The neutral element of the asymptotic ring is replaced by the value to the key '_zero_'; the neutral element of the growth group is replaced by the value to the key '_one_'.

EXAMPLES:

Sage

sage: A.<x> = AsymptoticRing(growth_group='(e^x)^QQ * x^ZZ * log(x)^ZZ', coefficient_ring=QQ, default_prec=5)

Python

>>> from sage.all import *
>>> A = AsymptoticRing(growth_group='(e^x)^QQ * x^ZZ * log(x)^ZZ', coefficient_ring=QQ, default_prec=Integer(5), names=('x',)); (x,) = A._first_ngens(1)

Sage

sage: (e^x * x^2 + log(x)).subs(x=SR('s'))
s^2*e^s + log(s)
sage: _.parent()
Symbolic Ring

Python

>>> from sage.all import *
>>> (e**x * x**Integer(2) + log(x)).subs(x=SR('s'))
s^2*e^s + log(s)
>>> _.parent()
Symbolic Ring

Sage

sage: (x^3 + x + log(x)).subs(x=x+5).truncate(5)
x^3 + 15*x^2 + 76*x + log(x) + 130 + O(x^(-1))
sage: _.parent()
Asymptotic Ring <(e^x)^QQ * x^ZZ * log(x)^ZZ> over Rational Field

Python

>>> from sage.all import *
>>> (x**Integer(3) + x + log(x)).subs(x=x+Integer(5)).truncate(Integer(5))
x^3 + 15*x^2 + 76*x + log(x) + 130 + O(x^(-1))
>>> _.parent()
Asymptotic Ring <(e^x)^QQ * x^ZZ * log(x)^ZZ> over Rational Field

Sage

sage: (e^x * x^2 + log(x)).subs(x=2*x)
4*(e^x)^2*x^2 + log(x) + log(2)
sage: _.parent()
Asymptotic Ring <(e^x)^QQ * x^QQ * log(x)^QQ> over Symbolic Ring

Python

>>> from sage.all import *
>>> (e**x * x**Integer(2) + log(x)).subs(x=Integer(2)*x)
4*(e^x)^2*x^2 + log(x) + log(2)
>>> _.parent()
Asymptotic Ring <(e^x)^QQ * x^QQ * log(x)^QQ> over Symbolic Ring

Sage

sage: (x^2 + log(x)).subs(x=4*x+2).truncate(5)
16*x^2 + 16*x + log(x) + 2*log(2) + 4 + 1/2*x^(-1) + O(x^(-2))
sage: _.parent()
Asymptotic Ring <(e^x)^QQ * x^ZZ * log(x)^ZZ> over Symbolic Ring

Python

>>> from sage.all import *
>>> (x**Integer(2) + log(x)).subs(x=Integer(4)*x+Integer(2)).truncate(Integer(5))
16*x^2 + 16*x + log(x) + 2*log(2) + 4 + 1/2*x^(-1) + O(x^(-2))
>>> _.parent()
Asymptotic Ring <(e^x)^QQ * x^ZZ * log(x)^ZZ> over Symbolic Ring

Sage

sage: (e^x * x^2 + log(x)).subs(x=RIF(pi))
229.534211738584?
sage: _.parent()
Real Interval Field with 53 bits of precision

Python

>>> from sage.all import *
>>> (e**x * x**Integer(2) + log(x)).subs(x=RIF(pi))
229.534211738584?
>>> _.parent()
Real Interval Field with 53 bits of precision

property summands¶

The summands of this asymptotic expansion stored in the underlying data structure (a MutablePoset).

EXAMPLES:

Sage

sage: R.<x> = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: expr = 7*x^12 + x^5 + O(x^3)
sage: expr.summands
poset(O(x^3), x^5, 7*x^12)

Python

>>> from sage.all import *
>>> R = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> expr = Integer(7)*x**Integer(12) + x**Integer(5) + O(x**Integer(3))
>>> expr.summands
poset(O(x^3), x^5, 7*x^12)

symbolic_expression(R=None)[source]¶

Return this asymptotic expansion as a symbolic expression.

INPUT:

R – (a subring of) the symbolic ring or None. The output will be an element of R. If None, then the symbolic ring is used.

OUTPUT: a symbolic expression

EXAMPLES:

Sage

sage: A.<x, y, z> = AsymptoticRing(growth_group='x^ZZ * y^QQ * log(y)^QQ * (QQ_+)^z * z^QQ', coefficient_ring=QQ)
sage: SR(A.an_element())  # indirect doctest
1/8*(1/8)^z*x^3*y^(3/2)*z^(3/2)*log(y)^(3/2) +
Order((1/2)^z*x*sqrt(y)*sqrt(z)*sqrt(log(y)))

sage: A.<x, y, z> = AsymptoticRing(growth_group='x^ZZ * y^QQ * log(y)^QQ * (QQ_+)^z * z^QQ', coefficient_ring=QQ)
sage: SR(A.an_element())  # indirect doctest
1/8*(1/8)^z*x^3*y^(3/2)*z^(3/2)*log(y)^(3/2) +
Order((1/2)^z*x*sqrt(y)*sqrt(z)*sqrt(log(y)))

Python

>>> from sage.all import *
>>> A = AsymptoticRing(growth_group='x^ZZ * y^QQ * log(y)^QQ * (QQ_+)^z * z^QQ', coefficient_ring=QQ, names=('x', 'y', 'z',)); (x, y, z,) = A._first_ngens(3)
>>> SR(A.an_element())  # indirect doctest
1/8*(1/8)^z*x^3*y^(3/2)*z^(3/2)*log(y)^(3/2) +
Order((1/2)^z*x*sqrt(y)*sqrt(z)*sqrt(log(y)))

>>> A = AsymptoticRing(growth_group='x^ZZ * y^QQ * log(y)^QQ * (QQ_+)^z * z^QQ', coefficient_ring=QQ, names=('x', 'y', 'z',)); (x, y, z,) = A._first_ngens(3)
>>> SR(A.an_element())  # indirect doctest
1/8*(1/8)^z*x^3*y^(3/2)*z^(3/2)*log(y)^(3/2) +
Order((1/2)^z*x*sqrt(y)*sqrt(z)*sqrt(log(y)))

truncate(precision=None)[source]¶

Truncate this asymptotic expansion.

INPUT:

precision – positive integer or None. Number of summands that are kept. If None (default value) is given, then default_prec from the parent is used.

OUTPUT: an asymptotic expansion

Note

For example, truncating an asymptotic expansion with precision=20 does not yield an expansion with exactly 20 summands! Rather than that, it keeps the 20 summands with the largest growth, and adds appropriate \(O\)-Terms.

EXAMPLES:

Sage

sage: R.<x> = AsymptoticRing('x^ZZ', QQ)
sage: ex = sum(x^k for k in range(5)); ex
x^4 + x^3 + x^2 + x + 1
sage: ex.truncate(precision=2)
x^4 + x^3 + O(x^2)
sage: ex.truncate(precision=0)
O(x^4)
sage: ex.truncate()
x^4 + x^3 + x^2 + x + 1

Python

>>> from sage.all import *
>>> R = AsymptoticRing('x^ZZ', QQ, names=('x',)); (x,) = R._first_ngens(1)
>>> ex = sum(x**k for k in range(Integer(5))); ex
x^4 + x^3 + x^2 + x + 1
>>> ex.truncate(precision=Integer(2))
x^4 + x^3 + O(x^2)
>>> ex.truncate(precision=Integer(0))
O(x^4)
>>> ex.truncate()
x^4 + x^3 + x^2 + x + 1

variable_names()[source]¶

Return the names of the variables of this asymptotic expansion.

OUTPUT: a tuple of strings

EXAMPLES:

Sage

sage: A.<m, n> = AsymptoticRing('QQ^m * m^QQ * n^ZZ * log(n)^ZZ', QQ)
sage: (4*2^m*m^4*log(n)).variable_names()
('m', 'n')
sage: (4*2^m*m^4).variable_names()
('m',)
sage: (4*log(n)).variable_names()
('n',)
sage: (4*m^3).variable_names()
('m',)
sage: (4*m^0).variable_names()
()
sage: (4*2^m*m^4 + log(n)).variable_names()
('m', 'n')
sage: (2^m + m^4 + log(n)).variable_names()
('m', 'n')
sage: (2^m + m^4).variable_names()
('m',)

Python

>>> from sage.all import *
>>> A = AsymptoticRing('QQ^m * m^QQ * n^ZZ * log(n)^ZZ', QQ, names=('m', 'n',)); (m, n,) = A._first_ngens(2)
>>> (Integer(4)*Integer(2)**m*m**Integer(4)*log(n)).variable_names()
('m', 'n')
>>> (Integer(4)*Integer(2)**m*m**Integer(4)).variable_names()
('m',)
>>> (Integer(4)*log(n)).variable_names()
('n',)
>>> (Integer(4)*m**Integer(3)).variable_names()
('m',)
>>> (Integer(4)*m**Integer(0)).variable_names()
()
>>> (Integer(4)*Integer(2)**m*m**Integer(4) + log(n)).variable_names()
('m', 'n')
>>> (Integer(2)**m + m**Integer(4) + log(n)).variable_names()
('m', 'n')
>>> (Integer(2)**m + m**Integer(4)).variable_names()
('m',)

class sage.rings.asymptotic.asymptotic_ring.AsymptoticRing(growth_group, coefficient_ring, category, default_prec, term_monoid_factory, locals)[source]¶

Bases: Parent, UniqueRepresentation, WithLocals

A ring consisting of asymptotic expansions.

INPUT:

growth_group – either a partially ordered group (see (Asymptotic) Growth Groups) or a string describing such a growth group (see GrowthGroupFactory).
coefficient_ring – the ring which contains the coefficients of the expansions
default_prec – positive integer; this is the number of summands that are kept before truncating an infinite series
category – the category of the parent can be specified in order to broaden the base structure. It has to be a subcategory of Category of rings. This is also the default category if None is specified.
term_monoid_factory – a TermMonoidFactory. If None, then DefaultTermMonoidFactory is used.
locals – dictionary which may contain the following keys and values:
- 'log' – value: a function. If not given, then the usual log is taken. (See also AsymptoticExpansion.log().)

EXAMPLES:

We begin with the construction of an asymptotic ring in various ways. First, we simply pass a string specifying the underlying growth group:

Sage

sage: R1_x.<x> = AsymptoticRing(growth_group='x^QQ', coefficient_ring=QQ); R1_x
Asymptotic Ring <x^QQ> over Rational Field
sage: x
x

Python

>>> from sage.all import *
>>> R1_x = AsymptoticRing(growth_group='x^QQ', coefficient_ring=QQ, names=('x',)); (x,) = R1_x._first_ngens(1); R1_x
Asymptotic Ring <x^QQ> over Rational Field
>>> x
x

This is equivalent to the following code, which explicitly specifies the underlying growth group:

Sage

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G_QQ = GrowthGroup('x^QQ')
sage: R2_x.<x> = AsymptoticRing(growth_group=G_QQ, coefficient_ring=QQ); R2_x
Asymptotic Ring <x^QQ> over Rational Field

Python

>>> from sage.all import *
>>> from sage.rings.asymptotic.growth_group import GrowthGroup
>>> G_QQ = GrowthGroup('x^QQ')
>>> R2_x = AsymptoticRing(growth_group=G_QQ, coefficient_ring=QQ, names=('x',)); (x,) = R2_x._first_ngens(1); R2_x
Asymptotic Ring <x^QQ> over Rational Field

Of course, the coefficient ring of the asymptotic ring and the base ring of the underlying growth group do not need to coincide:

Sage

sage: R_ZZ_x.<x> = AsymptoticRing(growth_group='x^QQ', coefficient_ring=ZZ); R_ZZ_x
Asymptotic Ring <x^QQ> over Integer Ring

Python

>>> from sage.all import *
>>> R_ZZ_x = AsymptoticRing(growth_group='x^QQ', coefficient_ring=ZZ, names=('x',)); (x,) = R_ZZ_x._first_ngens(1); R_ZZ_x
Asymptotic Ring <x^QQ> over Integer Ring

Note, we can also create and use logarithmic growth groups:

Sage

sage: R_log = AsymptoticRing(growth_group='log(x)^ZZ', coefficient_ring=QQ); R_log
Asymptotic Ring <log(x)^ZZ> over Rational Field

Python

>>> from sage.all import *
>>> R_log = AsymptoticRing(growth_group='log(x)^ZZ', coefficient_ring=QQ); R_log
Asymptotic Ring <log(x)^ZZ> over Rational Field

Other growth groups are available. See Asymptotic Ring for more examples.

Below there are some technical details.

According to the conventions for parents, uniqueness is ensured:

Sage

sage: R1_x is R2_x
True

Python

>>> from sage.all import *
>>> R1_x is R2_x
True

Furthermore, the coercion framework is also involved. Coercion between two asymptotic rings is possible (given that the underlying growth groups and coefficient rings are chosen appropriately):

Sage

sage: R1_x.has_coerce_map_from(R_ZZ_x)
True

Python

>>> from sage.all import *
>>> R1_x.has_coerce_map_from(R_ZZ_x)
True

Additionally, for the sake of convenience, the coefficient ring also coerces into the asymptotic ring (representing constant quantities):

Sage

sage: R1_x.has_coerce_map_from(QQ)
True

Python

>>> from sage.all import *
>>> R1_x.has_coerce_map_from(QQ)
True

It is possible to customize the terms in an asymptotic expansion:

Sage

sage: from sage.rings.asymptotic.term_monoid import ExactTermMonoid, OTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: class MyExactTermMonoid(ExactTermMonoid):
....:     pass
sage: class MyOTermMonoid(OTermMonoid):
....:     pass
sage: MyTermMonoid = TermMonoidFactory('MyTermMonoid',
....:                                  exact_term_monoid_class=MyExactTermMonoid,
....:                                  O_term_monoid_class=MyOTermMonoid)
sage: G = GrowthGroup('x^ZZ')
sage: A.<n> = AsymptoticRing(growth_group=G, coefficient_ring=QQ, term_monoid_factory=MyTermMonoid)
sage: a = A.an_element(); a
1/8*x^3 + O(x)
sage: for t in a.summands.elements_topological(reverse=True):
....:     print(t, type(t))
1/8*x^3 <class '__main__.MyExactTermMonoid_with_category.element_class'>
O(x) <class '__main__.MyOTermMonoid_with_category.element_class'>

Python

>>> from sage.all import *
>>> from sage.rings.asymptotic.term_monoid import ExactTermMonoid, OTermMonoid
>>> from sage.rings.asymptotic.term_monoid import TermMonoidFactory
>>> class MyExactTermMonoid(ExactTermMonoid):
...     pass
>>> class MyOTermMonoid(OTermMonoid):
...     pass
>>> MyTermMonoid = TermMonoidFactory('MyTermMonoid',
...                                  exact_term_monoid_class=MyExactTermMonoid,
...                                  O_term_monoid_class=MyOTermMonoid)
>>> G = GrowthGroup('x^ZZ')
>>> A = AsymptoticRing(growth_group=G, coefficient_ring=QQ, term_monoid_factory=MyTermMonoid, names=('n',)); (n,) = A._first_ngens(1)
>>> a = A.an_element(); a
1/8*x^3 + O(x)
>>> for t in a.summands.elements_topological(reverse=True):
...     print(t, type(t))
1/8*x^3 <class '__main__.MyExactTermMonoid_with_category.element_class'>
O(x) <class '__main__.MyOTermMonoid_with_category.element_class'>

static B(expression, valid_from=0)[source]¶

Create a B-term.

INPUT:

valid_from – dictionary mapping variable names to lower bounds for the corresponding variable. The bound implied by this term is valid when all variables are at least their corresponding lower bound. If a number is passed to valid_from, then the lower bounds for all variables of the asymptotic expansion are set to this number

OUTPUT: a B-term

EXAMPLES:

Sage

sage: A.<x> = AsymptoticRing(growth_group='x^ZZ * QQ^y', coefficient_ring=QQ)
sage: A.B(2*x^3, {x: 5})
B(2*x^3, x >= 5)

Python

>>> from sage.all import *
>>> A = AsymptoticRing(growth_group='x^ZZ * QQ^y', coefficient_ring=QQ, names=('x',)); (x,) = A._first_ngens(1)
>>> A.B(Integer(2)*x**Integer(3), {x: Integer(5)})
B(2*x^3, x >= 5)

Element[source]¶: alias of AsymptoticExpansion

change_parameter(**kwds)[source]¶

Return an asymptotic ring with a change in one or more of the given parameters.

INPUT:

growth_group – (default: None) the new growth group
coefficient_ring – (default: None) the new coefficient ring
category – (default: None) the new category
default_prec – (default: None) the new default precision

OUTPUT: an asymptotic ring

EXAMPLES:

Sage

sage: A = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: A.change_parameter(coefficient_ring=QQ)
Asymptotic Ring <x^ZZ> over Rational Field

Python

>>> from sage.all import *
>>> A = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
>>> A.change_parameter(coefficient_ring=QQ)
Asymptotic Ring <x^ZZ> over Rational Field

property coefficient_ring¶

The coefficient ring of this asymptotic ring.

EXAMPLES:

Sage

sage: AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: AR.coefficient_ring
Integer Ring

Python

>>> from sage.all import *
>>> AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
>>> AR.coefficient_ring
Integer Ring

coefficients_of_generating_function(function, singularities, precision=None, return_singular_expansions=False, error_term=None)[source]¶

Return the asymptotic growth of the coefficients of some generating function by means of Singularity Analysis.

INPUT:

function – a callable function in one variable
singularities – list of dominant singularities of the function
precision – integer (default: None); if None, then the default precision of the asymptotic ring is used
return_singular_expansions – boolean (default: False); if set, the singular expansions are also returned
error_term – (default: None) an asymptotic expansion. If None, then this is interpreted as zero. The contributions of the coefficients are added to error_term during Singularity Analysis.

OUTPUT:

If return_singular_expansions=False: An asymptotic expansion from this ring.
If return_singular_expansions=True: A named tuple with components asymptotic_expansion and singular_expansions. The former contains an asymptotic expansion from this ring, the latter is a dictionary which contains the singular expansions around the singularities.

Todo

Make this method more usable by implementing the processing of symbolic expressions.

EXAMPLES:

Catalan numbers:

Sage

sage: def catalan(z):
....:     return (1-(1-4*z)^(1/2))/(2*z)
sage: B.<n> = AsymptoticRing('QQ^n * n^QQ', QQ)
sage: B.coefficients_of_generating_function(catalan, (1/4,), precision=3)
1/sqrt(pi)*4^n*n^(-3/2) - 9/8/sqrt(pi)*4^n*n^(-5/2)
+ 145/128/sqrt(pi)*4^n*n^(-7/2) + O(4^n*n^(-4))
sage: B.coefficients_of_generating_function(catalan, (1/4,), precision=2,
....:                        return_singular_expansions=True)
SingularityAnalysisResult(asymptotic_expansion=1/sqrt(pi)*4^n*n^(-3/2)
- 9/8/sqrt(pi)*4^n*n^(-5/2) + O(4^n*n^(-3)),
singular_expansions={1/4: 2 - 2*T^(-1/2)
+ 2*T^(-1) - 2*T^(-3/2) + O(T^(-2))})

Python

>>> from sage.all import *
>>> def catalan(z):
...     return (Integer(1)-(Integer(1)-Integer(4)*z)**(Integer(1)/Integer(2)))/(Integer(2)*z)
>>> B = AsymptoticRing('QQ^n * n^QQ', QQ, names=('n',)); (n,) = B._first_ngens(1)
>>> B.coefficients_of_generating_function(catalan, (Integer(1)/Integer(4),), precision=Integer(3))
1/sqrt(pi)*4^n*n^(-3/2) - 9/8/sqrt(pi)*4^n*n^(-5/2)
+ 145/128/sqrt(pi)*4^n*n^(-7/2) + O(4^n*n^(-4))
>>> B.coefficients_of_generating_function(catalan, (Integer(1)/Integer(4),), precision=Integer(2),
...                        return_singular_expansions=True)
SingularityAnalysisResult(asymptotic_expansion=1/sqrt(pi)*4^n*n^(-3/2)
- 9/8/sqrt(pi)*4^n*n^(-5/2) + O(4^n*n^(-3)),
singular_expansions={1/4: 2 - 2*T^(-1/2)
+ 2*T^(-1) - 2*T^(-3/2) + O(T^(-2))})

Unit fractions:

Sage

sage: def logarithmic(z):
....:     return -log(1-z)
sage: B.coefficients_of_generating_function(logarithmic, (1,), precision=5)
n^(-1) + O(n^(-3))

Python

>>> from sage.all import *
>>> def logarithmic(z):
...     return -log(Integer(1)-z)
>>> B.coefficients_of_generating_function(logarithmic, (Integer(1),), precision=Integer(5))
n^(-1) + O(n^(-3))

Harmonic numbers:

Sage

sage: def harmonic(z):
....:     return -log(1-z)/(1-z)
sage: B.<n> = AsymptoticRing('QQ^n * n^QQ * log(n)^QQ', QQ)
sage: ex = B.coefficients_of_generating_function(harmonic, (1,), precision=13); ex
log(n) + euler_gamma + 1/2*n^(-1) - 1/12*n^(-2) + 1/120*n^(-4)
+ O(n^(-6))
sage: ex.has_same_summands(asymptotic_expansions.HarmonicNumber(
....:    'n', precision=5))
True

Python

>>> from sage.all import *
>>> def harmonic(z):
...     return -log(Integer(1)-z)/(Integer(1)-z)
>>> B = AsymptoticRing('QQ^n * n^QQ * log(n)^QQ', QQ, names=('n',)); (n,) = B._first_ngens(1)
>>> ex = B.coefficients_of_generating_function(harmonic, (Integer(1),), precision=Integer(13)); ex
log(n) + euler_gamma + 1/2*n^(-1) - 1/12*n^(-2) + 1/120*n^(-4)
+ O(n^(-6))
>>> ex.has_same_summands(asymptotic_expansions.HarmonicNumber(
...    'n', precision=Integer(5)))
True

Positive and negative singularities:

Sage

sage: def permutations_odd_cycles(z):
....:     return sqrt((1+z) / (1-z))
sage: ex = B.coefficients_of_generating_function(
....:     permutations_odd_cycles, (1, -1,), precision=2,
....: ); ex
sqrt(2)/sqrt(pi)*n^(-1/2) - 1/2*sqrt(1/2)/sqrt(pi)*n^(-3/2)*(-1)^n
+ O(n^(-5/2))

Python

>>> from sage.all import *
>>> def permutations_odd_cycles(z):
...     return sqrt((Integer(1)+z) / (Integer(1)-z))
>>> ex = B.coefficients_of_generating_function(
...     permutations_odd_cycles, (Integer(1), -Integer(1),), precision=Integer(2),
... ); ex
sqrt(2)/sqrt(pi)*n^(-1/2) - 1/2*sqrt(1/2)/sqrt(pi)*n^(-3/2)*(-1)^n
+ O(n^(-5/2))

Warning

Once singular expansions around points other than infinity are implemented (Issue #20050), the output in the case return_singular_expansions will change to return singular expansions around the singularities.

In the following example, the result is an exact asymptotic expression for sufficiently large \(n\) (i.e., there might be finitely many exceptional values). This is encoded by an \(O(0)\) error term:

Sage

sage: def f(z):
....:     return z/(1-z)
sage: B.coefficients_of_generating_function(f, (1,), precision=3)
Traceback (most recent call last):
...
NotImplementedOZero: got 1 + O(0)
The error term O(0) means 0 for sufficiently large n.

Python

>>> from sage.all import *
>>> def f(z):
...     return z/(Integer(1)-z)
>>> B.coefficients_of_generating_function(f, (Integer(1),), precision=Integer(3))
Traceback (most recent call last):
...
NotImplementedOZero: got 1 + O(0)
The error term O(0) means 0 for sufficiently large n.

In this case, we can manually intervene by adding an error term that suits us:

Sage

sage: B.coefficients_of_generating_function(f, (1,), precision=3,
....:                                       error_term=O(n^-100))
1 + O(n^(-100))

Python

>>> from sage.all import *
>>> B.coefficients_of_generating_function(f, (Integer(1),), precision=Integer(3),
...                                       error_term=O(n**-Integer(100)))
1 + O(n^(-100))

construction()[source]¶

Return the construction of this asymptotic ring.

OUTPUT:

A pair whose first entry is an asymptotic ring construction functor and its second entry the coefficient ring.

EXAMPLES:

Sage

sage: A = AsymptoticRing(growth_group='x^ZZ * QQ^y', coefficient_ring=QQ)
sage: A.construction()
(AsymptoticRing<x^ZZ * QQ^y * Signs^y>, Rational Field)

Python

>>> from sage.all import *
>>> A = AsymptoticRing(growth_group='x^ZZ * QQ^y', coefficient_ring=QQ)
>>> A.construction()
(AsymptoticRing<x^ZZ * QQ^y * Signs^y>, Rational Field)

create_summand(type, data=None, **kwds)[source]¶

Create a simple asymptotic expansion consisting of a single summand.

INPUT:

type – ‘O’ or ‘exact’
data – the element out of which a summand has to be created
growth – an element of the growth_group()
coefficient – an element of the coefficient_ring()

Note

Either growth and coefficient or data have to be specified.

OUTPUT: an asymptotic expansion

Note

This method calls the factory TermMonoid with the appropriate arguments.

EXAMPLES:

Sage

sage: R = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: R.create_summand('O', x^2)
O(x^2)
sage: R.create_summand('exact', growth=x^456, coefficient=123)
123*x^456
sage: R.create_summand('exact', data=12*x^13)
12*x^13

Python

>>> from sage.all import *
>>> R = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
>>> R.create_summand('O', x**Integer(2))
O(x^2)
>>> R.create_summand('exact', growth=x**Integer(456), coefficient=Integer(123))
123*x^456
>>> R.create_summand('exact', data=Integer(12)*x**Integer(13))
12*x^13

property default_prec¶

The default precision of this asymptotic ring.

This is the parameter used to determine how many summands are kept before truncating an infinite series (which occur when inverting asymptotic expansions).

EXAMPLES:

Sage

sage: AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: AR.default_prec
20
sage: AR = AsymptoticRing('x^ZZ', ZZ, default_prec=123)
sage: AR.default_prec
123

Python

>>> from sage.all import *
>>> AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
>>> AR.default_prec
20
>>> AR = AsymptoticRing('x^ZZ', ZZ, default_prec=Integer(123))
>>> AR.default_prec
123

gen(n=0)[source]¶

Return the n-th generator of this asymptotic ring.

INPUT:

n – (default: \(0\)) a nonnegative integer

OUTPUT: an asymptotic expansion

EXAMPLES:

Sage

sage: R.<x> = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: R.gen()
x

Python

>>> from sage.all import *
>>> R = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ, names=('x',)); (x,) = R._first_ngens(1)
>>> R.gen()
x

gens()[source]¶

Return a tuple with generators of this asymptotic ring.

OUTPUT: a tuple of asymptotic expansions

Note

Generators do not necessarily exist. This depends on the underlying growth group. For example, monomial growth groups have a generator, and exponential growth groups do not.

EXAMPLES:

Sage

sage: AR.<x> = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: AR.gens()
(x,)
sage: B.<y,z> = AsymptoticRing(growth_group='y^ZZ * z^ZZ', coefficient_ring=QQ)
sage: B.gens()
(y, z)

Python

>>> from sage.all import *
>>> AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ, names=('x',)); (x,) = AR._first_ngens(1)
>>> AR.gens()
(x,)
>>> B = AsymptoticRing(growth_group='y^ZZ * z^ZZ', coefficient_ring=QQ, names=('y', 'z',)); (y, z,) = B._first_ngens(2)
>>> B.gens()
(y, z)

property growth_group¶

The growth group of this asymptotic ring.

EXAMPLES:

Sage

sage: AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: AR.growth_group
Growth Group x^ZZ

Python

>>> from sage.all import *
>>> AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
>>> AR.growth_group
Growth Group x^ZZ

See also

(Asymptotic) Growth Groups

ngens()[source]¶

Return the number of generators of this asymptotic ring.

OUTPUT: integer

EXAMPLES:

Sage

sage: AR.<x> = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: AR.ngens()
1

Python

>>> from sage.all import *
>>> AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ, names=('x',)); (x,) = AR._first_ngens(1)
>>> AR.ngens()
1

some_elements()[source]¶

Return some elements of this term monoid.

See TestSuite for a typical use case.

OUTPUT: an iterator

EXAMPLES:

Sage

sage: from itertools import islice
sage: A = AsymptoticRing(growth_group='z^QQ', coefficient_ring=ZZ)
sage: tuple(islice(A.some_elements(), int(10)))
(z^(3/2) + O(z^(1/2)),
 O(z^(1/2)),
 z^(3/2) + O(z^(-1/2)),
 -z^(3/2) + O(z^(1/2)),
 O(z^(-1/2)),
 O(z^2),
 z^6 + O(z^(1/2)),
 -z^(3/2) + O(z^(-1/2)),
 O(z^2),
 z^(3/2) + O(z^(-2)))

Python

>>> from sage.all import *
>>> from itertools import islice
>>> A = AsymptoticRing(growth_group='z^QQ', coefficient_ring=ZZ)
>>> tuple(islice(A.some_elements(), int(Integer(10))))
(z^(3/2) + O(z^(1/2)),
 O(z^(1/2)),
 z^(3/2) + O(z^(-1/2)),
 -z^(3/2) + O(z^(1/2)),
 O(z^(-1/2)),
 O(z^2),
 z^6 + O(z^(1/2)),
 -z^(3/2) + O(z^(-1/2)),
 O(z^2),
 z^(3/2) + O(z^(-2)))

term_monoid(type)[source]¶

Return the term monoid of this asymptotic ring of specified type.

INPUT:

type – 'O' or 'exact', or an instance of an existing term monoid. See TermMonoidFactory for more details.

OUTPUT:

A term monoid object derived from GenericTermMonoid.

EXAMPLES:

Sage

sage: AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: AR.term_monoid('exact')
Exact Term Monoid x^ZZ with coefficients in Integer Ring
sage: AR.term_monoid('O')
O-Term Monoid x^ZZ with implicit coefficients in Integer Ring
sage: AR.term_monoid(AR.term_monoid('exact'))
Exact Term Monoid x^ZZ with coefficients in Integer Ring

Python

>>> from sage.all import *
>>> AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
>>> AR.term_monoid('exact')
Exact Term Monoid x^ZZ with coefficients in Integer Ring
>>> AR.term_monoid('O')
O-Term Monoid x^ZZ with implicit coefficients in Integer Ring
>>> AR.term_monoid(AR.term_monoid('exact'))
Exact Term Monoid x^ZZ with coefficients in Integer Ring

property term_monoid_factory¶

The term monoid factory of this asymptotic ring.

EXAMPLES:

Sage

sage: AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
sage: AR.term_monoid_factory
Term Monoid Factory 'sage.rings.asymptotic.term_monoid.DefaultTermMonoidFactory'

Python

>>> from sage.all import *
>>> AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ)
>>> AR.term_monoid_factory
Term Monoid Factory 'sage.rings.asymptotic.term_monoid.DefaultTermMonoidFactory'

See also

(Asymptotic) Term Monoids

variable_names()[source]¶

Return the names of the variables.

OUTPUT: a tuple of strings

EXAMPLES:

Sage

sage: A = AsymptoticRing(growth_group='x^ZZ * QQ^y', coefficient_ring=QQ)
sage: A.variable_names()
('x', 'y')

Python

>>> from sage.all import *
>>> A = AsymptoticRing(growth_group='x^ZZ * QQ^y', coefficient_ring=QQ)
>>> A.variable_names()
('x', 'y')

class sage.rings.asymptotic.asymptotic_ring.AsymptoticRingFunctor(growth_group, default_prec=None, category=None, term_monoid_factory=None, locals=None, cls=None)[source]¶

Bases: ConstructionFunctor

A construction functor for asymptotic rings.

INPUT:

growth_group – a partially ordered group (see AsymptoticRing or (Asymptotic) Growth Groups for details).
default_prec – None (default) or integer
category – None (default) or a category
cls – AsymptoticRing (default) or a derived class

EXAMPLES:

Sage

sage: AsymptoticRing(growth_group='x^ZZ', coefficient_ring=QQ).construction()  # indirect doctest
(AsymptoticRing<x^ZZ>, Rational Field)

Python

>>> from sage.all import *
>>> AsymptoticRing(growth_group='x^ZZ', coefficient_ring=QQ).construction()  # indirect doctest
(AsymptoticRing<x^ZZ>, Rational Field)

merge(other)[source]¶

Merge this functor with other if possible.

INPUT:

other – a functor

OUTPUT: a functor or None

EXAMPLES:

Sage

sage: X = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=QQ)
sage: Y = AsymptoticRing(growth_group='y^ZZ', coefficient_ring=QQ)
sage: F_X = X.construction()[0]
sage: F_Y = Y.construction()[0]
sage: F_X.merge(F_X)
AsymptoticRing<x^ZZ>
sage: F_X.merge(F_Y)
AsymptoticRing<x^ZZ * y^ZZ>

Python

>>> from sage.all import *
>>> X = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=QQ)
>>> Y = AsymptoticRing(growth_group='y^ZZ', coefficient_ring=QQ)
>>> F_X = X.construction()[Integer(0)]
>>> F_Y = Y.construction()[Integer(0)]
>>> F_X.merge(F_X)
AsymptoticRing<x^ZZ>
>>> F_X.merge(F_Y)
AsymptoticRing<x^ZZ * y^ZZ>

rank = 13¶

exception sage.rings.asymptotic.asymptotic_ring.NoConvergenceError[source]¶

Bases: RuntimeError

A special RuntimeError which is raised when an algorithm does not converge/stop.

Asymptotic Ring¶

(Informal) Definition¶

Growth Groups and Elements¶

Introductory Examples¶

Two Rings¶

A Univariate Asymptotic Ring¶

A Multivariate Asymptotic Ring¶

Arithmetical Operations¶

The Ring Operations Plus and Times¶

Division¶

Powers, Exponentials and Logarithms¶

Multivariate Arithmetic¶

More Examples¶

The mathematical constant e as a limit¶

Selected Technical Details¶

Coercions and Functorial Constructions¶

Data Structures¶

Various¶

Classes and Methods¶