Asymptotic Ring¶
This module provides a ring (called AsymptoticRing
) for
computations with asymptotic expansions.
(Informal) Definition¶
An asymptotic expansion is a sum such as
as \(z \to \infty\) or
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
orz^QQ
), - elements of the form \(\log(z)^q\) for some integer or rational \(q\)
(growth groups
log(z)^ZZ
orlog(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
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.
Warning
As this code is experimental, a warning is thrown when an
asymptotic ring (or an associated structure) is created for the
first time in a session (see
sage.misc.superseded.experimental
).
TESTS:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G = GrowthGroup('x^ZZ')
doctest:...: 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.
Introductory Examples¶
We start this series of examples by defining two asymptotic rings.
Two Rings¶
A Univariate Asymptotic Ring¶
First, we construct the following (very simple) asymptotic ring in the variable \(z\):
sage: A.<z> = AsymptoticRing(growth_group='z^QQ', coefficient_ring=ZZ); A
Asymptotic Ring <z^QQ> over Integer Ring
A typical element of this ring is
sage: A.an_element()
z^(3/2) + O(z^(1/2))
This element consists of two summands: the exact term with coefficient \(1\) and growth \(z^{3/2}\) and the \(O\)-term \(O(z^{1/2})\). Note that the growth of \(z^{3/2}\) is larger than the growth of \(z^{1/2}\) as \(z\to\infty\), thus this expansion cannot be simplified (which would be done automatically, see below).
Elements can be constructed via the generator \(z\) and the function
O()
, for example
sage: 4*z^2 + O(z)
4*z^2 + O(z)
A Multivariate Asymptotic Ring¶
Next, we construct a more sophisticated asymptotic ring in the variables \(x\) and \(y\) by
sage: B.<x, y> = AsymptoticRing(growth_group='x^QQ * log(x)^ZZ * QQ^y * y^QQ', coefficient_ring=QQ); B
Asymptotic Ring <x^QQ * log(x)^ZZ * QQ^y * y^QQ> over Rational Field
Again, we can look at a typical (nontrivial) element:
sage: B.an_element()
1/8*x^(3/2)*log(x)^3*(1/8)^y*y^(3/2) + O(x^(1/2)*log(x)*(1/2)^y*y^(1/2))
Again, elements can be created using the generators \(x\) and \(y\), as well as
the function O()
:
sage: log(x)*y/42 + O(1/2^y)
1/42*log(x)*y + O((1/2)^y)
Arithmetical Operations¶
In this section we explain how to perform various arithmetical operations with the elements of the asymptotic rings constructed above.
The Ring Operations Plus and Times¶
We start our calculations in the ring
sage: A
Asymptotic Ring <z^QQ> over Integer Ring
Of course, we can perform the usual ring operations \(+\) and \(*\):
sage: z^2 + 3*z*(1-z)
-2*z^2 + 3*z
sage: (3*z + 2)^3
27*z^3 + 54*z^2 + 36*z + 8
In addition to that, special powers—our growth group z^QQ
allows
the exponents to be out of \(\QQ\)—can also be computed:
sage: (z^(5/2)+z^(1/7)) * z^(-1/5)
z^(23/10) + z^(-2/35)
The central concepts of computations with asymptotic expansions is that the \(O\)-notation can be used. For example, we have
sage: z^3 + z^2 + z + O(z^2)
z^3 + O(z^2)
where the result is simplified automatically. A more sophisticated example is
sage: (z+2*z^2+3*z^3+4*z^4) * (O(z)+z^2)
4*z^6 + O(z^5)
Division¶
The asymptotic expansions support division. For example, we can expand \(1/(z-1)\) to a geometric series:
sage: 1 / (z-1)
z^(-1) + z^(-2) + z^(-3) + z^(-4) + ... + z^(-20) + O(z^(-21))
A default precision (parameter default_prec
of
AsymptoticRing
) is predefined. Thus, only the first \(20\)
summands are calculated. However, if we only want the first \(5\) exact
terms, we cut of the rest by using
sage: (1 / (z-1)).truncate(5)
z^(-1) + z^(-2) + z^(-3) + z^(-4) + z^(-5) + O(z^(-6))
or
sage: 1 / (z-1) + O(z^(-6))
z^(-1) + z^(-2) + z^(-3) + z^(-4) + z^(-5) + O(z^(-6))
Of course, we can work with more complicated expansions as well:
sage: (4*z+1) / (z^3+z^2+z+O(z^0))
4*z^(-2) - 3*z^(-3) - z^(-4) + O(z^(-5))
Not all elements are invertible, for instance,
sage: 1 / O(z)
Traceback (most recent call last):
...
ZeroDivisionError: Cannot invert O(z).
is not invertible, since it includes \(0\).
Powers, Expontials and Logarithms¶
It works as simple as it can be; just use the usual operators ^
,
exp
and log
. For example, we obtain the usual series expansion
of the logarithm
sage: -log(1-1/z)
z^(-1) + 1/2*z^(-2) + 1/3*z^(-3) + ... + O(z^(-21))
as \(z \to \infty\).
Similarly, we can apply the exponential function of an asymptotic expansion:
sage: exp(1/z)
1 + z^(-1) + 1/2*z^(-2) + 1/6*z^(-3) + 1/24*z^(-4) + ... + O(z^(-20))
Arbitrary powers work as well; for example, we have
sage: (1 + 1/z + O(1/z^5))^(1 + 1/z)
1 + z^(-1) + z^(-2) + 1/2*z^(-3) + 1/3*z^(-4) + O(z^(-5))
Note
In the asymptotic ring
sage: M.<n> = AsymptoticRing(growth_group='QQ^n * n^QQ', coefficient_ring=ZZ)
the operation
sage: (1/2)^n
Traceback (most recent call last):
...
ValueError: 1/2 is not in Exact Term Monoid QQ^n * n^QQ
with coefficients in Integer Ring. ...
fails, since the rational \(1/2\) is not contained in \(M\). You can use
sage: n.rpow(1/2)
(1/2)^n
instead. (See also the examples in
ExactTerm.rpow()
for a detailed explanation.)
Another way is to use a larger coefficient ring:
sage: M_QQ.<n> = AsymptoticRing(growth_group='QQ^n * n^QQ', coefficient_ring=QQ)
sage: (1/2)^n
(1/2)^n
Multivariate Arithmetic¶
Now let us move on to arithmetic in the multivariate ring
sage: B
Asymptotic Ring <x^QQ * log(x)^ZZ * QQ^y * y^QQ> over Rational Field
Todo
write this part
More Examples¶
The mathematical constant e as a limit¶
The base of the natural logarithm \(e\) satisfies the equation
By using asymptotic expansions, we obtain the more precise result
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))
Selected Technical Details¶
Coercions and Functorial Constructions¶
The AsymptoticRing
fully supports
coercion. For example, the coefficient ring is automatically extended when needed:
sage: A
Asymptotic Ring <z^QQ> over Integer Ring
sage: (z + 1/2).parent()
Asymptotic Ring <z^QQ> over Rational Field
Here, the coefficient ring was extended to allow \(1/2\) as a coefficient. Another example is
sage: C.<c> = AsymptoticRing(growth_group='c^ZZ', coefficient_ring=ZZ['e'])
sage: C.an_element()
e^3*c^3 + O(c)
sage: C.an_element() / 7
1/7*e^3*c^3 + O(c)
Here the result’s coefficient ring is the newly found
sage: (C.an_element() / 7).parent()
Asymptotic Ring <c^ZZ> over
Univariate Polynomial Ring in e over Rational Field
Not only the coefficient ring can be extended, but the growth group as
well. For example, we can add/multiply elements of the asymptotic
rings A
and C
to get an expansion of new asymptotic ring:
sage: r = c*z + c/2 + O(z); r
c*z + 1/2*c + O(z)
sage: r.parent()
Asymptotic Ring <c^ZZ * z^QQ> over
Univariate Polynomial Ring in e over Rational Field
Data Structures¶
The summands of an
asymptotic expansion
are wrapped
growth group elements.
This wrapping is done by the
term monoid module.
However, inside an
asymptotic expansion
these summands
(terms) are stored together with their growth-relationship, i.e., each
summand knows its direct predecessors and successors. As a data
structure a special poset (namely a
mutable poset
)
is used. We can have a look at this:
sage: b = x^3*y + x^2*y + x*y^2 + O(x) + O(y)
sage: print(b.summands.repr_full(reverse=True))
poset(x*y^2, x^3*y, x^2*y, O(x), O(y))
+-- oo
| +-- no successors
| +-- predecessors: x*y^2, x^3*y
+-- x*y^2
| +-- successors: oo
| +-- predecessors: O(x), O(y)
+-- x^3*y
| +-- successors: oo
| +-- predecessors: x^2*y
+-- x^2*y
| +-- successors: x^3*y
| +-- predecessors: O(x), O(y)
+-- O(x)
| +-- successors: x*y^2, x^2*y
| +-- predecessors: null
+-- O(y)
| +-- successors: x*y^2, x^2*y
| +-- predecessors: null
+-- null
| +-- successors: O(x), O(y)
| +-- no predecessors
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)¶ Bases:
sage.structure.element.CommutativeAlgebraElement
Class for asymptotic expansions, i.e., the elements of an
AsymptoticRing
.INPUT:
parent
– the parent of the asymptotic expansion.summands
– the summands as aMutablePoset
, which represents the underlying structure.simplify
– a boolean (default:True
). It controls automatic simplification (absorption) of the asymptotic expansion.convert
– a boolean (default:True
). If set, then thesummands
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: 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
At this point, \(x\) and \(y\) are already asymptotic expansions:
sage: 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: 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
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: (x+2*x^2+3*x^3+4*x^4) * (O(x)+x^2) 4*x^6 + O(x^5)
In particular,
O()
can be used to construct the asymptotic expansions. With the help of thesummands()
, we can also have a look at the inner structure of an asymptotic expansion: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
In addition to the monomial growth elements from above, we can also compute with logarithmic terms (simply by constructing the appropriate growth group):
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)
-
O
()¶ Convert all terms in this asymptotic expansion to \(O\)-terms.
INPUT:
Nothing.
OUTPUT:
An asymptotic expansion.
EXAMPLES:
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)
See also
sage.rings.power_series_ring.PowerSeriesRing()
,sage.rings.laurent_series_ring.LaurentSeriesRing()
.TESTS:
sage: AR(0).O() Traceback (most recent call last): ... NotImplementedOZero: The error term in the result is O(0) which means 0 for sufficiently large x.
-
compare_with_values
(variable, function, values, rescaled=True, ring=Real Interval Field with 53 bits of precision)¶ 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
– a list or iterable of values where the comparison shall be carried out.rescaled
– (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: 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.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)]
Instead of a symbolic expression, a callable function can be specified as well:
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?)]
See also
TESTS:
sage: A.<x, y> = AsymptoticRing('x^ZZ*y^ZZ', QQ) sage: expansion = x^2 + O(x) + O(y) sage: expansion.compare_with_values(y, lambda z: z^2, srange(20, 30)) Traceback (most recent call last): .... NotImplementedError: exactly one error term required sage: expansion = x^2 sage: expansion.compare_with_values(y, lambda z: z^2, srange(20, 30)) Traceback (most recent call last): .... NotImplementedError: exactly one error term required sage: expansion = x^2 + O(x) sage: expansion.compare_with_values(y, lambda z: z^2, srange(20, 30)) Traceback (most recent call last): .... NameError: name 'x' is not defined sage: expansion.compare_with_values(x, lambda z: z^2, srange(20, 30)) [(20, 0), (21, 0), ..., (29, 0)] sage: expansion.compare_with_values(x, SR('x*y'), srange(20, 30)) Traceback (most recent call last): .... NotImplementedError: expression x*y has more than one variable
-
exact_part
()¶ Return the expansion consisting of all exact terms of this expansion.
INPUT:
Nothing
OUTPUT:
An asymptotic expansion.
EXAMPLES:
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)
TESTS:
sage: R.<x, y> = AsymptoticRing('x^QQ * y^QQ', QQ) sage: (x + y + O(1/(x*y))).exact_part() x + y sage: O(x).exact_part() 0
-
exp
(precision=None)¶ Return the exponential of (i.e., the power of \(e\) to) this asymptotic expansion.
INPUT:
precision
– the precision used for truncating the expansion. IfNone
(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: 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
sage: (x^(-1)).exp(precision=7) 1 + x^(-1) + 1/2*x^(-2) + 1/6*x^(-3) + ... + O(x^(-7))
TESTS:
sage: A.<x> = AsymptoticRing('(e^x)^ZZ * x^QQ * log(x)^QQ', SR) sage: exp(log(x)) x sage: log(exp(x)) x
sage: exp(x+1) e*e^x
See trac ticket #19521:
sage: A.<n> = AsymptoticRing('n^ZZ', SR.subring(no_variables=True)) sage: exp(O(n^(-3))).parent() Asymptotic Ring <n^ZZ> over Symbolic Constants Subring
-
factorial
()¶ Return the factorial of this asymptotic expansion.
OUTPUT:
An asymptotic expansion.
EXAMPLES:
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)))^(Symbolic Constants Subring) * (e^n)^(Symbolic Constants Subring) * n^(Symbolic Constants Subring) * log(n)^(Symbolic Constants Subring)> over Symbolic Constants Subring
Catalan numbers \(\frac{1}{n+1}\binom{2n}{n}\):
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))
Note that this method substitutes the asymptotic expansion into Stirling’s formula. This substitution has to be possible which is not always guaranteed:
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. ...
See also
TESTS:
sage: A.<m> = AsymptoticRing(growth_group='m^ZZ * log(m)^ZZ', coefficient_ring=QQ, default_prec=5) sage: m.factorial() sqrt(2)*sqrt(pi)*e^(m*log(m))*(e^m)^(-1)*m^(1/2) + 1/12*sqrt(2)*sqrt(pi)*e^(m*log(m))*(e^m)^(-1)*m^(-1/2) + 1/288*sqrt(2)*sqrt(pi)*e^(m*log(m))*(e^m)^(-1)*m^(-3/2) + O(e^(m*log(m))*(e^m)^(-1)*m^(-5/2))
sage: A(1/2).factorial() 1/2*sqrt(pi) sage: _.parent() Asymptotic Ring <m^ZZ * log(m)^ZZ> over Symbolic Ring
sage: B.<a, b> = AsymptoticRing('a^ZZ * b^ZZ', QQ, default_prec=3) sage: b.factorial() O(e^(b*log(b))*(e^b)^(-1)*b^(1/2)) sage: (a*b).factorial() Traceback (most recent call last): ... ValueError: Cannot build the factorial of a*b since it is not univariate.
-
has_same_summands
(other)¶ Return whether this asymptotic expansion and
other
have the same summands.INPUT:
other
– an asymptotic expansion.
OUTPUT:
A boolean.
Note
While for example
O(x) == O(x)
yieldsFalse
, these expansions do have the same summands and this method returnsTrue
.Moreover, this method uses the coercion model in order to find a common parent for this asymptotic expansion and
other
.EXAMPLES:
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
TESTS:
sage: x_ZZ.has_same_summands(None) False
-
invert
(precision=None)¶ Return the multiplicative inverse of this element.
INPUT:
precision
– the precision used for truncating the expansion. IfNone
(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: 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))
TESTS:
sage: A.<a> = AsymptoticRing(growth_group='a^ZZ', coefficient_ring=ZZ) sage: (1 / a).parent() Asymptotic Ring <a^ZZ> over Rational Field sage: (a / 2).parent() Asymptotic Ring <a^ZZ> over Rational Field
sage: ~A(0) Traceback (most recent call last): ... ZeroDivisionError: Cannot invert 0 in Asymptotic Ring <a^ZZ> over Integer Ring.
sage: B.<s, t> = AsymptoticRing(growth_group='s^ZZ * t^ZZ', coefficient_ring=QQ) sage: ~(s + t) Traceback (most recent call last): ... ValueError: Cannot determine main term of s + t since there are several maximal elements s, t.
-
is_exact
()¶ Return whether all terms of this expansion are exact.
OUTPUT:
A boolean.
EXAMPLES:
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
TESTS:
sage: A(0).is_exact() True sage: A.one().is_exact() True
-
is_little_o_of_one
()¶ Return whether this expansion is of order \(o(1)\).
INPUT:
Nothing.
OUTPUT:
A boolean.
EXAMPLES:
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
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
-
log
(base=None, precision=None)¶ The logarithm of this asymptotic expansion.
INPUT:
base
– the base of the logarithm. IfNone
(default value) is used, the natural logarithm is taken.precision
– the precision used for truncating the expansion. IfNone
(default value) is used, the default precision of the parent is used.
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: 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))
TESTS:
sage: log(R(1)) 0 sage: log(R(0)) Traceback (most recent call last): ... ArithmeticError: Cannot compute log(0) in Asymptotic Ring <x^ZZ * log(x)^ZZ> over Rational Field. sage: C.<s, t> = AsymptoticRing(growth_group='s^ZZ * t^ZZ', coefficient_ring=QQ) sage: log(s + t) Traceback (most recent call last): ... ValueError: Cannot determine main term of s + t since there are several maximal elements s, t.
-
map_coefficients
(f, new_coefficient_ring=None)¶ 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: 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)
TESTS:
sage: a.map_coefficients(lambda c: 1/c, new_coefficient_ring=QQ) n^4 + 1/2*n^3 + 1/3*n^2 + O(n) sage: _.parent() Asymptotic Ring <n^ZZ> over Rational Field sage: a.map_coefficients(lambda c: 1/c) Traceback (most recent call last): ... ValueError: ... is not a coefficient in Exact Term Monoid n^ZZ with coefficients in Integer Ring.
-
plot_comparison
(variable, function, values, rescaled=True, ring=Real Interval Field with 53 bits of precision, relative_tolerance=0.025, **kwargs)¶ 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
– a list or iterable of values where the comparison shall be carried out.rescaled
– (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 plausability check for asymptotic expansion created in some way.
EXAMPLES:
We want to check the quality of the asymptotic expansion of the harmonic numbers:
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
Alternatively, the unscaled (absolute) difference can be plotted as well:
sage: H_expansion.plot_comparison(n, H, srange(1, 30), ....: rescaled=False) Graphics object consisting of 1 graphics primitive
Additional keywords are passed to
list_plot()
:sage: H_expansion.plot_comparison(n, H, srange(1, 30), ....: plotjoined=True, marker='o', ....: color='green') Graphics object consisting of 1 graphics primitive
See also
TESTS:
sage: H_expansion.plot_comparison(n, H, [600]) Traceback (most recent call last): ... ValueError: Numerical noise is too high, the comparison is inaccurate sage: H_expansion.plot_comparison(n, H, [600], relative_tolerance=2) Graphics object consisting of 1 graphics primitive
-
pow
(exponent, precision=None)¶ Calculate the power of this asymptotic expansion to the given
exponent
.INPUT:
exponent
– an element.precision
– the precision used for truncating the expansion. IfNone
(default value) is used, the default precision of the parent is used.
OUTPUT:
An asymptotic expansion.
EXAMPLES:
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)
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))
sage: B.<z> = AsymptoticRing(growth_group='z^QQ * log(z)^QQ', coefficient_ring=QQ) sage: (z^2 + O(z))^(1/2) z + O(1)
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> over Symbolic Ring
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> 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> over Rational Field
TESTS:
See trac ticket #19110:
sage: O(x)^(-1) Traceback (most recent call last): ... ZeroDivisionError: Cannot take O(x) to exponent -1. > *previous* ZeroDivisionError: rational division by zero
sage: B.<z> = AsymptoticRing(growth_group='z^QQ * log(z)^QQ', coefficient_ring=QQ, default_prec=5) sage: z^(1+1/z) z + log(z) + 1/2*z^(-1)*log(z)^2 + 1/6*z^(-2)*log(z)^3 + 1/24*z^(-3)*log(z)^4 + O(z^(-4)*log(z)^5) sage: _.parent() Asymptotic Ring <z^QQ * log(z)^QQ> over Rational Field
sage: B(0)^(-7) Traceback (most recent call last): ... ZeroDivisionError: Cannot take 0 to the negative exponent -7. sage: B(0)^SR.var('a') Traceback (most recent call last): ... NotImplementedError: Taking 0 to the exponent a not implemented.
sage: C.<s, t> = AsymptoticRing(growth_group='s^QQ * t^QQ', coefficient_ring=QQ) sage: (s + t)^s Traceback (most recent call last): ... ValueError: Cannot take s + t to the exponent s. > *previous* ValueError: Cannot determine main term of s + t since there are several maximal elements s, t.
Check that trac ticket #19946 is fixed:
sage: A.<n> = AsymptoticRing('QQ^n * n^QQ', SR) sage: e = 2^n; e 2^n sage: e.parent() Asymptotic Ring <SR^n * n^SR> over Symbolic Ring sage: e = A(e); e 2^n sage: e.parent() Asymptotic Ring <QQ^n * n^QQ> over Symbolic Ring
-
rpow
(base, precision=None)¶ Return the power of
base
to this asymptotic expansion.INPUT:
base
– an element or'e'
.precision
– the precision used for truncating the expansion. IfNone
(default value) is used, the default precision of the parent is used.
OUTPUT:
An asymptotic expansion.
EXAMPLES:
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))
TESTS:
sage: x.rpow(SR.var('y')) Traceback (most recent call last): ... ArithmeticError: Cannot construct y^x in Growth Group x^ZZ > *previous* TypeError: unsupported operand parent(s) for '*': 'Growth Group x^ZZ' and 'Growth Group SR^x'
Check that trac ticket #19946 is fixed:
sage: A.<n> = AsymptoticRing('QQ^n * n^QQ', SR) sage: n.rpow(2) 2^n sage: _.parent() Asymptotic Ring <QQ^n * n^SR> over Symbolic Ring
-
show
()¶ Pretty-print this asymptotic expansion.
OUTPUT:
Nothing, the representation is printed directly on the screen.
EXAMPLES:
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() <html><script type="math/tex">\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{2} \, \pi 5^{x} x^{\frac{42}{17}} - \sqrt{\gamma_E} \log\left(x\right)^{-\frac{7}{8}}</script></html>
TESTS:
sage: A.<x> = AsymptoticRing('(e^x)^QQ * x^QQ', SR.subring(no_variables=True)) sage: (zeta(3) * (e^x)^(-1/2) * x^42).show() <html><script type="math/tex">\newcommand{\Bold}[1]{\mathbf{#1}}\zeta(3) \left(e^{x}\right)^{-\frac{1}{2}} x^{42}</script></html>
-
sqrt
(precision=None)¶ Return the square root of this asymptotic expansion.
INPUT:
precision
– the precision used for truncating the expansion. IfNone
(default value) is used, the default precision of the parent is used.
OUTPUT:
An asymptotic expansion.
EXAMPLES:
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))
TESTS:
sage: P.<p> = PowerSeriesRing(QQ, default_prec=6) sage: bool(SR(a.exact_part()).subs(s=1/x) - ....: SR((1+p).sqrt().polynomial()).subs(p=x) == 0) True
-
subs
(rules=None, domain=None, **kwds)¶ Substitute the given
rules
in this asymptotic expansion.INPUT:
rules
– a dictionary.kwds
– keyword arguments will be added to the substitutionrules
.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. IfNone
, 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: A.<x> = AsymptoticRing(growth_group='(e^x)^QQ * x^ZZ * log(x)^ZZ', coefficient_ring=QQ, default_prec=5)
sage: (e^x * x^2 + log(x)).subs(x=SR('s')) s^2*e^s + log(s) sage: _.parent() Symbolic Ring
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
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
sage: (x^2 + log(x)).subs(x=4*x+2).truncate(5) 16*x^2 + 16*x + log(x) + log(4) + 4 + 1/2*x^(-1) + O(x^(-2)) sage: _.parent() Asymptotic Ring <(e^x)^QQ * x^ZZ * log(x)^ZZ> over Symbolic Ring
sage: (e^x * x^2 + log(x)).subs(x=RIF(pi)) 229.534211738584? sage: _.parent() Real Interval Field with 53 bits of precision
TESTS:
sage: x.subs({'y': -1}) Traceback (most recent call last): ... ValueError: Cannot substitute y in x since it is not a generator of Asymptotic Ring <(e^x)^QQ * x^ZZ * log(x)^ZZ> over Rational Field. sage: B.<u, v, w> = AsymptoticRing(growth_group='u^QQ * v^QQ * w^QQ', coefficient_ring=QQ) sage: (1/u).subs({'u': 0}) Traceback (most recent call last): ... TypeError: Cannot apply the substitution rules {u: 0} on u^(-1) in Asymptotic Ring <u^QQ * v^QQ * w^QQ> over Rational Field. > *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Asymptotic Ring <u^QQ * v^QQ * w^QQ> over Rational Field. >> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Exact Term Monoid u^QQ * v^QQ * w^QQ with coefficients in Rational Field. >...> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Growth Group u^QQ * v^QQ * w^QQ. >...> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Growth Group u^QQ. >...> *previous* ZeroDivisionError: rational division by zero sage: (1/u).subs({'u': 0, 'v': SR.var('v')}) Traceback (most recent call last): ... TypeError: Cannot apply the substitution rules {u: 0, v: v} on u^(-1) in Asymptotic Ring <u^QQ * v^QQ * w^QQ> over Rational Field. > *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Asymptotic Ring <u^QQ * v^QQ * w^QQ> over Rational Field. >> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Exact Term Monoid u^QQ * v^QQ * w^QQ with coefficients in Rational Field. >...> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Growth Group u^QQ * v^QQ * w^QQ. >...> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Growth Group u^QQ. >...> *previous* ZeroDivisionError: rational division by zero
sage: u.subs({u: 0, 'v': SR.var('v')}) 0 sage: v.subs({u: 0, 'v': SR.var('v')}) v sage: _.parent() Symbolic Ring
sage: u.subs({SR.var('u'): -1}) Traceback (most recent call last): ... TypeError: Cannot substitute u in u since it is neither an asymptotic expansion nor a string (but a <type 'sage.symbolic.expression.Expression'>).
sage: u.subs({u: 1, 'u': 1}) 1 sage: u.subs({u: 1}, u=1) 1 sage: u.subs({u: 1, 'u': 2}) Traceback (most recent call last): ... ValueError: Cannot substitute in u: duplicate key u. sage: u.subs({u: 1}, u=3) Traceback (most recent call last): ... ValueError: Cannot substitute in u: duplicate key u.
-
substitute
(rules=None, domain=None, **kwds)¶ Substitute the given
rules
in this asymptotic expansion.INPUT:
rules
– a dictionary.kwds
– keyword arguments will be added to the substitutionrules
.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. IfNone
, 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: A.<x> = AsymptoticRing(growth_group='(e^x)^QQ * x^ZZ * log(x)^ZZ', coefficient_ring=QQ, default_prec=5)
sage: (e^x * x^2 + log(x)).subs(x=SR('s')) s^2*e^s + log(s) sage: _.parent() Symbolic Ring
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
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
sage: (x^2 + log(x)).subs(x=4*x+2).truncate(5) 16*x^2 + 16*x + log(x) + log(4) + 4 + 1/2*x^(-1) + O(x^(-2)) sage: _.parent() Asymptotic Ring <(e^x)^QQ * x^ZZ * log(x)^ZZ> over Symbolic Ring
sage: (e^x * x^2 + log(x)).subs(x=RIF(pi)) 229.534211738584? sage: _.parent() Real Interval Field with 53 bits of precision
TESTS:
sage: x.subs({'y': -1}) Traceback (most recent call last): ... ValueError: Cannot substitute y in x since it is not a generator of Asymptotic Ring <(e^x)^QQ * x^ZZ * log(x)^ZZ> over Rational Field. sage: B.<u, v, w> = AsymptoticRing(growth_group='u^QQ * v^QQ * w^QQ', coefficient_ring=QQ) sage: (1/u).subs({'u': 0}) Traceback (most recent call last): ... TypeError: Cannot apply the substitution rules {u: 0} on u^(-1) in Asymptotic Ring <u^QQ * v^QQ * w^QQ> over Rational Field. > *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Asymptotic Ring <u^QQ * v^QQ * w^QQ> over Rational Field. >> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Exact Term Monoid u^QQ * v^QQ * w^QQ with coefficients in Rational Field. >...> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Growth Group u^QQ * v^QQ * w^QQ. >...> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Growth Group u^QQ. >...> *previous* ZeroDivisionError: rational division by zero sage: (1/u).subs({'u': 0, 'v': SR.var('v')}) Traceback (most recent call last): ... TypeError: Cannot apply the substitution rules {u: 0, v: v} on u^(-1) in Asymptotic Ring <u^QQ * v^QQ * w^QQ> over Rational Field. > *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Asymptotic Ring <u^QQ * v^QQ * w^QQ> over Rational Field. >> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Exact Term Monoid u^QQ * v^QQ * w^QQ with coefficients in Rational Field. >...> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Growth Group u^QQ * v^QQ * w^QQ. >...> *previous* ZeroDivisionError: Cannot substitute in u^(-1) in Growth Group u^QQ. >...> *previous* ZeroDivisionError: rational division by zero
sage: u.subs({u: 0, 'v': SR.var('v')}) 0 sage: v.subs({u: 0, 'v': SR.var('v')}) v sage: _.parent() Symbolic Ring
sage: u.subs({SR.var('u'): -1}) Traceback (most recent call last): ... TypeError: Cannot substitute u in u since it is neither an asymptotic expansion nor a string (but a <type 'sage.symbolic.expression.Expression'>).
sage: u.subs({u: 1, 'u': 1}) 1 sage: u.subs({u: 1}, u=1) 1 sage: u.subs({u: 1, 'u': 2}) Traceback (most recent call last): ... ValueError: Cannot substitute in u: duplicate key u. sage: u.subs({u: 1}, u=3) Traceback (most recent call last): ... ValueError: Cannot substitute in u: duplicate key u.
-
summands
¶ The summands of this asymptotic expansion stored in the underlying data structure (a
MutablePoset
).EXAMPLES:
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)
-
symbolic_expression
(R=None)¶ Return this asymptotic expansion as a symbolic expression.
INPUT:
R
– (a subring of) the symbolic ring orNone
. The output is will be an element ofR
. IfNone
, then the symbolic ring is used.
OUTPUT:
A symbolic expression.
EXAMPLES:
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)))
TESTS:
sage: a = A.an_element(); a 1/8*x^3*y^(3/2)*log(y)^(3/2)*(1/8)^z*z^(3/2) + O(x*y^(1/2)*log(y)^(1/2)*(1/2)^z*z^(1/2)) sage: a.symbolic_expression() 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: _.parent() Symbolic Ring
sage: from sage.symbolic.ring import SymbolicRing sage: class MySymbolicRing(SymbolicRing): ....: pass sage: mySR = MySymbolicRing() sage: a.symbolic_expression(mySR).parent() is mySR True
-
truncate
(precision=None)¶ Truncate this asymptotic expansion.
INPUT:
precision
– a positive integer orNone
. Number of summands that are kept. IfNone
(default value) is given, thendefault_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: 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
-
variable_names
()¶ Return the names of the variables of this asymptotic expansion.
OUTPUT:
A tuple of strings.
EXAMPLES:
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',)
-
class
sage.rings.asymptotic.asymptotic_ring.
AsymptoticRing
(growth_group, coefficient_ring, category, default_prec)¶ Bases:
sage.rings.ring.Algebra
,sage.structure.unique_representation.UniqueRepresentation
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 (seeGrowthGroupFactory
).coefficient_ring
– the ring which contains the coefficients of the expansions.default_prec
– a 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 ofCategory of rings
. This is also the default category ifNone
is specified.
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: R1_x.<x> = AsymptoticRing(growth_group='x^QQ', coefficient_ring=QQ); R1_x Asymptotic Ring <x^QQ> over Rational Field sage: x x
This is equivalent to the following code, which explicitly specifies the underlying growth group:
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
Of course, the coefficient ring of the asymptotic ring and the base ring of the underlying growth group do not need to coincide:
sage: R_ZZ_x.<x> = AsymptoticRing(growth_group='x^QQ', coefficient_ring=ZZ); R_ZZ_x Asymptotic Ring <x^QQ> over Integer Ring
Note, we can also create and use logarithmic growth groups:
sage: 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: 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: 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: R1_x.has_coerce_map_from(QQ) True
TESTS:
sage: from sage.rings.asymptotic.asymptotic_ring import AsymptoticRing as AR_class sage: class AR(AR_class): ....: class Element(AR_class.Element): ....: __eq__ = AR_class.Element.has_same_summands sage: A = AR(growth_group='z^QQ', coefficient_ring=QQ) sage: from itertools import islice sage: TestSuite(A).run( # not tested # long time # see #19424 ....: verbose=True, ....: elements=tuple(islice(A.some_elements(), 10)), ....: skip=('_test_some_elements', # to many elements ....: '_test_distributivity')) # due to cancellations: O(z) != O(z^2)
-
Element
¶ alias of
AsymptoticExpansion
-
change_parameter
(**kwds)¶ 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: A = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ) sage: A.change_parameter(coefficient_ring=QQ) Asymptotic Ring <x^ZZ> over Rational Field
TESTS:
sage: A.change_parameter(coefficient_ring=ZZ) is A True sage: A.change_parameter(coefficient_ring=None) is A True
-
coefficient_ring
¶ The coefficient ring of this asymptotic ring.
EXAMPLES:
sage: AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ) sage: AR.coefficient_ring Integer Ring
-
coefficients_of_generating_function
(function, singularities, precision=None, return_singular_expansions=False)¶ 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
– (default:None
) an integer. IfNone
, then the default precision of the asymptotic ring is used.return_singular_expansions
– (default:False
) a boolean. If set, the singular expansions are also returned.
OUTPUT:
- If
return_singular_expansions=False
: An asymptotic expansion from this ring. - If
return_singular_expansions=True
: A named tuple with componentsasymptotic_expansion
andsingular_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: 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))})
Unit fractions:
sage: def logarithmic(z): ....: return -log(1-z) sage: B.coefficients_of_generating_function(logarithmic, (1,), precision=5) n^(-1) + O(n^(-3))
Harmonic numbers:
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
Warning
Once singular expansions around points other than infinity are implemented (trac ticket #20050), the output in the case
return_singular_expansions
will change to return singular expansions around the singularities.TESTS:
sage: def f(z): ....: return z/(1-z) sage: B.coefficients_of_generating_function(f, (1,), precision=3) Traceback (most recent call last): ... NotImplementedOZero: The error term in the result is O(0) which means 0 for sufficiently large n.
-
construction
()¶ 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: A = AsymptoticRing(growth_group='x^ZZ * QQ^y', coefficient_ring=QQ) sage: A.construction() (AsymptoticRing<x^ZZ * QQ^y>, Rational Field)
See also
-
create_summand
(type, data=None, **kwds)¶ 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 thegrowth_group()
.coefficient
– an element of thecoefficient_ring()
.
Note
Either
growth
andcoefficient
ordata
have to be specified.OUTPUT:
An asymptotic expansion.
Note
This method calls the factory
TermMonoid
with the appropriate arguments.EXAMPLES:
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
TESTS:
sage: R.create_summand('exact', data='12*x^13') 12*x^13 sage: R.create_summand('exact', data='x^13 * 12') 12*x^13 sage: R.create_summand('exact', data='x^13') x^13 sage: R.create_summand('exact', data='12') 12 sage: R.create_summand('exact', data=12) 12
sage: Z = R.change_parameter(coefficient_ring=Zmod(3)) sage: Z.create_summand('exact', data=42) 0
sage: R.create_summand('O', growth=42*x^2, coefficient=1) Traceback (most recent call last): ... ValueError: Growth 42*x^2 is not in O-Term Monoid x^ZZ with implicit coefficients in Integer Ring. > *previous* ValueError: 42*x^2 is not in Growth Group x^ZZ.
sage: AR.<z> = AsymptoticRing('z^QQ', QQ) sage: AR.create_summand('exact', growth='z^2') Traceback (most recent call last): ... TypeError: Cannot create exact term: only 'growth' but no 'coefficient' specified.
-
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: 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
-
gen
(n=0)¶ Return the
n
-th generator of this asymptotic ring.INPUT:
n
– (default: \(0\)) a non-negative integer.
OUTPUT:
An asymptotic expansion.
EXAMPLES:
sage: R.<x> = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ) sage: R.gen() x
-
gens
()¶ Return a tuple with generators of this asymptotic ring.
INPUT:
Nothing.
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: 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)
-
growth_group
¶ The growth group of this asymptotic ring.
EXAMPLES:
sage: AR = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ) sage: AR.growth_group Growth Group x^ZZ
See also
-
ngens
()¶ Return the number of generators of this asymptotic ring.
INPUT:
Nothing.
OUTPUT:
An integer.
EXAMPLES:
sage: AR.<x> = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ) sage: AR.ngens() 1
-
some_elements
()¶ Return some elements of this term monoid.
See
TestSuite
for a typical use case.INPUT:
Nothing.
OUTPUT:
An iterator.
EXAMPLES:
sage: from itertools import islice sage: A = AsymptoticRing(growth_group='z^QQ', coefficient_ring=ZZ) sage: tuple(islice(A.some_elements(), 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)))
-
variable_names
()¶ Return the names of the variables.
OUTPUT:
A tuple of strings.
EXAMPLES:
sage: A = AsymptoticRing(growth_group='x^ZZ * QQ^y', coefficient_ring=QQ) sage: A.variable_names() ('x', 'y')
-
class
sage.rings.asymptotic.asymptotic_ring.
AsymptoticRingFunctor
(growth_group)¶ Bases:
sage.categories.pushout.ConstructionFunctor
A
construction functor
forasymptotic rings
.INPUT:
growth_group
– a partially ordered group (seeAsymptoticRing
or (Asymptotic) Growth Groups for details).
EXAMPLES:
sage: AsymptoticRing(growth_group='x^ZZ', coefficient_ring=QQ).construction() # indirect doctest (AsymptoticRing<x^ZZ>, Rational Field)
See also
Asymptotic Ring,
AsymptoticRing
,sage.rings.asymptotic.growth_group.AbstractGrowthGroupFunctor
,sage.rings.asymptotic.growth_group.ExponentialGrowthGroupFunctor
,sage.rings.asymptotic.growth_group.MonomialGrowthGroupFunctor
,sage.categories.pushout.ConstructionFunctor
.TESTS:
sage: X = AsymptoticRing(growth_group='x^ZZ', coefficient_ring=QQ) sage: Y = AsymptoticRing(growth_group='y^ZZ', coefficient_ring=QQ) sage: cm = sage.structure.element.get_coercion_model() sage: cm.record_exceptions() sage: cm.common_parent(X, Y) Asymptotic Ring <x^ZZ * y^ZZ> over Rational Field sage: sage.structure.element.coercion_traceback() # not tested
sage: from sage.categories.pushout import pushout sage: pushout(AsymptoticRing(growth_group='x^ZZ', coefficient_ring=ZZ), QQ) Asymptotic Ring <x^ZZ> over Rational Field
-
merge
(other)¶ Merge this functor with
other
if possible.INPUT:
other
– a functor.
OUTPUT:
A functor or
None
.EXAMPLES:
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>
-
exception
sage.rings.asymptotic.asymptotic_ring.
NoConvergenceError
¶ Bases:
exceptions.RuntimeError
A special RuntimeError which is raised when an algorithm does not converge/stop.