(Asymptotic) Term Monoids

This module implements asymptotic term monoids. The elements of these monoids are used behind the scenes when performing calculations in an asymptotic ring.

The monoids build upon the (asymptotic) growth groups. While growth elements only model the growth of a function as it tends towards infinity (or tends towards another fixed point; see (Asymptotic) Growth Groups for more details), an asymptotic term additionally specifies its “type” and performs the actual arithmetic operations (multiplication and partial addition/absorption of terms).

Besides an abstract base term GenericTerm, this module implements the following types of terms:

• OTerm – \(O\)-terms at infinity, see Wikipedia article Big_O_notation.
• TermWithCoefficient – abstract base class for asymptotic terms with coefficients.
• ExactTerm – this class represents a growth element multiplied with some non-zero coefficient from a coefficient ring.

A characteristic property of asymptotic terms is that some terms are able to “absorb” other terms (see absorb()). For instance, \(O(x^2)\) is able to absorb \(O(x)\) (with result \(O(x^2)\)), and \(3\cdot x^5\) is able to absorb \(-2\cdot x^5\) (with result \(x^5\)). Essentially, absorption can be interpreted as the addition of “compatible” terms (partial addition).

Absorption of Asymptotic Terms

A characteristic property of asymptotic terms is that some terms are able to “absorb” other terms. This is realized with the method absorb().

For instance, \(O(x^2)\) is able to absorb \(O(x)\) (with result \(O(x^2)\)). This is because the functions bounded by linear growth are bounded by quadratic growth as well. Another example would be that \(3x^5\) is able to absorb \(-2x^5\) (with result \(x^5\)), which simply corresponds to addition.

Essentially, absorption can be interpreted as the addition of “compatible” terms (partial addition).

We want to show step by step which terms can be absorbed by which other terms. We start by defining the necessary term monoids and some terms:

sage: from sage.rings.asymptotic.term_monoid import OTermMonoid, ExactTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G = GrowthGroup('x^ZZ'); x = G.gen()
sage: OT = OTermMonoid(TermMonoid, growth_group=G, coefficient_ring=QQ)
sage: ET = ExactTermMonoid(TermMonoid, growth_group=G, coefficient_ring=QQ)
sage: ot1 = OT(x); ot2 = OT(x^2)
sage: et1 = ET(x^2, 2)

• Because of the definition of \(O\)-terms (see Wikipedia article Big_O_notation), OTerm are able to absorb all other asymptotic terms with weaker or equal growth. In our implementation, this means that OTerm is able to absorb other OTerm, as well as ExactTerm, as long as the growth of the other term is less than or equal to the growth of this element:

  sage: ot1, ot2
  (O(x), O(x^2))
  sage: ot1.can_absorb(ot2), ot2.can_absorb(ot1)
  (False, True)
  sage: et1
  2*x^2
  sage: ot1.can_absorb(et1)
  False
  sage: ot2.can_absorb(et1)
  True
  

  The result of this absorption always is the dominant (absorbing) OTerm:

  sage: ot1.absorb(ot1)
  O(x)
  sage: ot2.absorb(ot1)
  O(x^2)
  sage: ot2.absorb(et1)
  O(x^2)
  

  These examples correspond to \(O(x) + O(x) = O(x)\), \(O(x^2) + O(x) = O(x^2)\), and \(O(x^2) + 2x^2 = O(x^2)\).

• ExactTerm can only absorb another ExactTerm if the growth coincides with the growth of this element:

  sage: et1.can_absorb(ET(x^2, 5))
  True
  sage: any(et1.can_absorb(t) for t in [ot1, ot2])
  False
  

  As mentioned above, absorption directly corresponds to addition in this case:

  sage: et1.absorb(ET(x^2, 5))
  7*x^2
  

  When adding two exact terms, they might cancel out. For technical reasons, None is returned in this case:

  sage: ET(x^2, 5).can_absorb(ET(x^2, -5))
  True
  sage: ET(x^2, 5).absorb(ET(x^2, -5)) is None
  True
  

• The abstract base terms GenericTerm and TermWithCoefficient can neither absorb any other term, nor be absorbed by any other term.

If absorb is called on a term that cannot be absorbed, an ArithmeticError is raised:

sage: ot1.absorb(ot2)
Traceback (most recent call last):
...
ArithmeticError: O(x) cannot absorb O(x^2)

This would only work the other way around:

sage: ot2.absorb(ot1)
O(x^2)

Comparison

The comparison of asymptotic terms with \(\leq\) is implemented as follows:

• When comparing t1 <= t2, the coercion framework first tries to find a common parent for both terms. If this fails, False is returned.

• In case the coerced terms do not have a coefficient in their common parent (e.g. OTerm), the growth of the two terms is compared.

• Otherwise, if the coerced terms have a coefficient (e.g. ExactTerm), we compare whether t1 has a growth that is strictly weaker than the growth of t2. If so, we return True. If the terms have equal growth, then we return True if and only if the coefficients coincide as well.

  In all other cases, we return False.

Long story short: we consider terms with different coefficients that have equal growth to be incomparable.

Various

Todo

• Implementation of more term types (e.g. \(L\) terms, \(\Omega\) terms, \(o\) terms, \(\Theta\) terms).

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

sage.rings.asymptotic.term_monoid.DefaultTermMonoidFactory = Term Monoid Factory 'sage.rings.asymptotic.term_monoid.DefaultTermMonoidFactory'

A factory for asymptotic term monoids. This is an instance of TermMonoidFactory whose documentation provides more details.

class sage.rings.asymptotic.term_monoid.ExactTerm(parent, growth, coefficient)

Bases: sage.rings.asymptotic.term_monoid.TermWithCoefficient

Class for asymptotic exact terms. These terms primarily consist of an asymptotic growth element as well as a coefficient specifying the growth of the asymptotic term.

INPUT:

• parent – the parent of the asymptotic term.
• growth – an asymptotic growth element from parent.growth_group.
• coefficient – an element from parent.coefficient_ring.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import (ExactTermMonoid, TermMonoidFactory)
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: G = GrowthGroup('x^ZZ'); x = G.gen()
sage: ET = ExactTermMonoid(TermMonoid, G, QQ)

Asymptotic exact terms may be multiplied (with the usual rules applying):

sage: ET(x^2, 3) * ET(x, -1)
-3*x^3
sage: ET(x^0, 4) * ET(x^5, 2)
8*x^5

They may also be multiplied with \(O\)-terms:

sage: OT = TermMonoid('O', G, QQ)
sage: ET(x^2, 42) * OT(x)
O(x^3)

Absorption for asymptotic exact terms relates to addition:

sage: ET(x^2, 5).can_absorb(ET(x^5, 12))
False
sage: ET(x^2, 5).can_absorb(ET(x^2, 1))
True
sage: ET(x^2, 5).absorb(ET(x^2, 1))
6*x^2

Note that, as for technical reasons, \(0\) is not allowed as a coefficient for an asymptotic term with coefficient. Instead None is returned if two asymptotic exact terms cancel out each other during absorption:

sage: ET(x^2, 42).can_absorb(ET(x^2, -42))
True
sage: ET(x^2, 42).absorb(ET(x^2, -42)) is None
True

Exact terms can also be created by converting monomials with coefficient from the symbolic ring, or a suitable polynomial or power series ring:

sage: x = var('x'); x.parent()
Symbolic Ring
sage: ET(5*x^2)
5*x^2

can_absorb(other)

Check whether this exact term can absorb other.

INPUT:

• other – an asymptotic term.

OUTPUT:

A boolean.

Note

For ExactTerm, absorption corresponds to addition. This means that an exact term can absorb only other exact terms with the same growth.

See the module description for a detailed explanation of absorption.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: ET = TermMonoid('exact', GrowthGroup('x^ZZ'), ZZ)
sage: t1 = ET(x^21, 1); t2 = ET(x^21, 2); t3 = ET(x^42, 1)
sage: t1.can_absorb(t2)
True
sage: t2.can_absorb(t1)
True
sage: t1.can_absorb(t3) or t3.can_absorb(t1)
False

is_constant()

Return whether this term is an (exact) constant.

INPUT:

Nothing.

OUTPUT:

A boolean.

Note

Only ExactTerm with constant growth (\(1\)) are constant.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('exact', GrowthGroup('x^ZZ * log(x)^ZZ'), QQ)
sage: T('x * log(x)').is_constant()
False
sage: T('3*x').is_constant()
False
sage: T(1/2).is_constant()
True
sage: T(42).is_constant()
True

is_exact()

Return whether this term is an exact term.

OUTPUT:

A boolean.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('exact', GrowthGroup('x^ZZ * log(x)^ZZ'), QQ)
sage: T('x * log(x)').is_exact()
True
sage: T('3 * x^2').is_exact()
True

is_little_o_of_one()

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

INPUT:

Nothing.

OUTPUT:

A boolean.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('exact', GrowthGroup('x^ZZ'), QQ)
sage: T(x).is_little_o_of_one()
False
sage: T(1).is_little_o_of_one()
False
sage: T(x^(-1)).is_little_o_of_one()
True

sage: T = TermMonoid('exact', GrowthGroup('x^ZZ * y^ZZ'), QQ)
sage: T('x * y^(-1)').is_little_o_of_one()
False
sage: T('x^(-1) * y').is_little_o_of_one()
False
sage: T('x^(-2) * y^(-3)').is_little_o_of_one()
True

sage: T = TermMonoid('exact', GrowthGroup('x^QQ * log(x)^QQ'), QQ)
sage: T('x * log(x)^2').is_little_o_of_one()
False
sage: T('x^2 * log(x)^(-1234)').is_little_o_of_one()
False
sage: T('x^(-1) * log(x)^4242').is_little_o_of_one()
True
sage: T('x^(-1/100) * log(x)^(1000/7)').is_little_o_of_one()
True

log_term(base=None, locals=None)

Determine the logarithm of this exact term.

INPUT:

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

OUTPUT:

A tuple of terms.

Note

This method returns a tuple with the summands that come from applying the rule \(\log(x\cdot y) = \log(x) + \log(y)\).

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('exact', GrowthGroup('x^ZZ * log(x)^ZZ'), SR)
sage: T(3*x^2).log_term()
(log(3), 2*log(x))
sage: T(x^1234).log_term()
(1234*log(x),)
sage: T(49*x^7).log_term(base=7)
(2, 7/log(7)*log(x))

sage: T = TermMonoid('exact', GrowthGroup('x^ZZ * log(x)^ZZ * y^ZZ * log(y)^ZZ'), SR)
sage: T('x * y').log_term()
(log(x), log(y))
sage: T('4 * x * y').log_term(base=2)
(2, 1/log(2)*log(x), 1/log(2)*log(y))

See also

OTerm.log_term().

rpow(base)

Return the power of base to this exact term.

INPUT:

• base – an element or 'e'.

OUTPUT:

A term.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('exact', GrowthGroup('QQ^x * x^ZZ * log(x)^ZZ'), QQ)
sage: T('x').rpow(2)
2^x
sage: T('log(x)').rpow('e')
x
sage: T('42*log(x)').rpow('e')
x^42
sage: T('3*x').rpow(2)
8^x

sage: T('3*x^2').rpow(2)
Traceback (most recent call last):
...
ArithmeticError: Cannot construct 2^(x^2) in
Growth Group QQ^x * x^ZZ * log(x)^ZZ * Signs^x
> *previous* TypeError: unsupported operand parent(s) for *:
'Growth Group QQ^x * x^ZZ * log(x)^ZZ * Signs^x' and
'Growth Group ZZ^(x^2)'

sage: T = TermMonoid('exact', GrowthGroup('(QQ_+)^n * n^QQ'), SR)
sage: n = T('n')
sage: n.rpow(2)
2^n
sage: _.parent()
Exact Term Monoid QQ^n * n^QQ with coefficients in Symbolic Ring

class sage.rings.asymptotic.term_monoid.ExactTermMonoid(term_monoid_factory, growth_group, coefficient_ring, category)

Bases: sage.rings.asymptotic.term_monoid.TermWithCoefficientMonoid

Parent for asymptotic exact terms, implemented in ExactTerm.

INPUT:

• growth_group – a growth group.
• category – The category of the parent can be specified in order to broaden the base structure. It has to be a subcategory of Join of Category of monoids and Category of posets. This is also the default category if None is specified.
• coefficient_ring – the ring which contains the coefficients of the elements.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import ExactTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: G_ZZ = GrowthGroup('x^ZZ'); x_ZZ = G_ZZ.gen()
sage: G_QQ = GrowthGroup('x^QQ'); x_QQ = G_QQ.gen()
sage: ET_ZZ = ExactTermMonoid(TermMonoid, G_ZZ, ZZ); ET_ZZ
Exact Term Monoid x^ZZ with coefficients in Integer Ring
sage: ET_QQ = ExactTermMonoid(TermMonoid, G_QQ, QQ); ET_QQ
Exact Term Monoid x^QQ with coefficients in Rational Field
sage: ET_QQ.coerce_map_from(ET_ZZ)
Coercion map:
  From: Exact Term Monoid x^ZZ with coefficients in Integer Ring
  To:   Exact Term Monoid x^QQ with coefficients in Rational Field

Exact term monoids can also be created using the term factory:

sage: TermMonoid('exact', G_ZZ, ZZ) is ET_ZZ
True
sage: TermMonoid('exact', GrowthGroup('x^ZZ'), QQ)
Exact Term Monoid x^ZZ with coefficients in Rational Field

Element

alias of ExactTerm

class sage.rings.asymptotic.term_monoid.GenericTerm(parent, growth)

Bases: sage.structure.element.MultiplicativeGroupElement

Base class for asymptotic terms. Mainly the structure and several properties of asymptotic terms are handled here.

INPUT:

• parent – the parent of the asymptotic term.
• growth – an asymptotic growth element.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import GenericTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: G = GrowthGroup('x^ZZ'); x = G.gen()
sage: T = GenericTermMonoid(TermMonoid, G, QQ)
sage: t1 = T(x); t2 = T(x^2); (t1, t2)
(Generic Term with growth x, Generic Term with growth x^2)
sage: t1 * t2
Generic Term with growth x^3
sage: t1.can_absorb(t2)
False
sage: t1.absorb(t2)
Traceback (most recent call last):
...
ArithmeticError: Generic Term with growth x cannot absorb Generic Term with growth x^2
sage: t1.can_absorb(t1)
False

absorb(other, check=True)

Absorb the asymptotic term other and return the resulting asymptotic term.

INPUT:

• other – an asymptotic term.
• check – a boolean. If check is True (default), then can_absorb is called before absorption.

OUTPUT:

An asymptotic term or None if a cancellation occurs. If no absorption can be performed, an ArithmeticError is raised.

Note

Setting check to False is meant to be used in cases where the respective comparison is done externally (in order to avoid duplicate checking).

For a more detailed explanation of the absorption of asymptotic terms see the module description.

EXAMPLES:

We want to demonstrate in which cases an asymptotic term is able to absorb another term, as well as explain the output of this operation. We start by defining some parents and elements:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: G_QQ = GrowthGroup('x^QQ'); x = G_QQ.gen()
sage: OT = TermMonoid('O', G_QQ, coefficient_ring=ZZ)
sage: ET = TermMonoid('exact', G_QQ, coefficient_ring=QQ)
sage: ot1 = OT(x); ot2 = OT(x^2)
sage: et1 = ET(x, 100); et2 = ET(x^2, 2)
sage: et3 = ET(x^2, 1); et4 = ET(x^2, -2)

\(O\)-Terms are able to absorb other \(O\)-terms and exact terms with weaker or equal growth.

sage: ot1.absorb(ot1)
O(x)
sage: ot1.absorb(et1)
O(x)
sage: ot1.absorb(et1) is ot1
True

ExactTerm is able to absorb another ExactTerm if the terms have the same growth. In this case, absorption is nothing else than an addition of the respective coefficients:

sage: et2.absorb(et3)
3*x^2
sage: et3.absorb(et2)
3*x^2
sage: et3.absorb(et4)
-x^2

Note that, for technical reasons, the coefficient \(0\) is not allowed, and thus None is returned if two exact terms cancel each other out:

sage: et2.absorb(et4)
sage: et4.absorb(et2) is None
True

can_absorb(other)

Check whether this asymptotic term is able to absorb the asymptotic term other.

INPUT:

• other – an asymptotic term.

OUTPUT:

A boolean.

Note

A GenericTerm cannot absorb any other term.

See the module description for a detailed explanation of absorption.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GenericGrowthGroup
sage: from sage.rings.asymptotic.term_monoid import GenericTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: G = GenericGrowthGroup(ZZ)
sage: T = GenericTermMonoid(TermMonoid, G, QQ)
sage: g1 = G(raw_element=21); g2 = G(raw_element=42)
sage: t1 = T(g1); t2 = T(g2)
sage: t1.can_absorb(t2)  # indirect doctest
False
sage: t2.can_absorb(t1)  # indirect doctest
False

is_constant()

Return whether this term is an (exact) constant.

INPUT:

Nothing.

OUTPUT:

A boolean.

Note

Only ExactTerm with constant growth (\(1\)) are constant.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import (GenericTermMonoid, TermMonoidFactory)
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = GenericTermMonoid(TermMonoid, GrowthGroup('x^ZZ * log(x)^ZZ'), QQ)
sage: t = T.an_element(); t
Generic Term with growth x*log(x)
sage: t.is_constant()
False

sage: T = TermMonoid('O', GrowthGroup('x^ZZ'), QQ)
sage: T('x').is_constant()
False
sage: T(1).is_constant()
False

is_exact()

Return whether this term is an exact term.

OUTPUT:

A boolean.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import GenericTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = GenericTermMonoid(TermMonoid, GrowthGroup('x^ZZ * log(x)^ZZ'), QQ)
sage: T.an_element().is_exact()
False

is_little_o_of_one()

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

INPUT:

Nothing.

OUTPUT:

A boolean.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import (GenericTermMonoid,
....:                                                TermWithCoefficientMonoid)
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: T = GenericTermMonoid(TermMonoid, GrowthGroup('x^ZZ'), QQ)
sage: T.an_element().is_little_o_of_one()
Traceback (most recent call last):
...
NotImplementedError: Cannot check whether Generic Term with growth x is o(1)
in the abstract base class
Generic Term Monoid x^ZZ with (implicit) coefficients in Rational Field.
sage: T = TermWithCoefficientMonoid(TermMonoid, GrowthGroup('x^ZZ'), QQ)
sage: T.an_element().is_little_o_of_one()
Traceback (most recent call last):
...
NotImplementedError: Cannot check whether Term with coefficient 1/2 and growth x
is o(1) in the abstract base class
Generic Term Monoid x^ZZ with (implicit) coefficients in Rational Field.

log_term(base=None, locals=None)

Determine the logarithm of this term.

INPUT:

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

OUTPUT:

A tuple of terms.

Note

This abstract method raises a NotImplementedError. See ExactTerm and OTerm for a concrete implementation.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import GenericTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: T = GenericTermMonoid(TermMonoid, GrowthGroup('x^ZZ'), QQ)
sage: T.an_element().log_term()
Traceback (most recent call last):
...
NotImplementedError: This method is not implemented in
this abstract base class.

sage: from sage.rings.asymptotic.term_monoid import TermWithCoefficientMonoid
sage: T = TermWithCoefficientMonoid(TermMonoid, GrowthGroup('x^ZZ'), QQ)
sage: T.an_element().log_term()
Traceback (most recent call last):
...
NotImplementedError: This method is not implemented in
this abstract base class.

See also

ExactTerm.log_term(), OTerm.log_term().

rpow(base)

Return the power of base to this generic term.

INPUT:

• base – an element or 'e'.

OUTPUT:

A term.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import GenericTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: T = GenericTermMonoid(TermMonoid, GrowthGroup('x^ZZ * log(x)^ZZ'), QQ)
sage: T.an_element().rpow('e')
Traceback (most recent call last):
...
NotImplementedError: Cannot take e to the exponent
Generic Term with growth x*log(x) in the abstract base class
Generic Term Monoid x^ZZ * log(x)^ZZ with (implicit) coefficients in Rational Field.

variable_names()

Return the names of the variables of this term.

OUTPUT:

A tuple of strings.

EXAMPLES:

sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('exact', 'QQ^m * m^QQ * log(n)^ZZ', QQ)
sage: T('4 * 2^m * m^4 * log(n)').variable_names()
('m', 'n')
sage: T('4 * 2^m * m^4').variable_names()
('m',)
sage: T('4 * log(n)').variable_names()
('n',)
sage: T('4 * m^3').variable_names()
('m',)
sage: T('4 * m^0').variable_names()
()

class sage.rings.asymptotic.term_monoid.GenericTermMonoid(term_monoid_factory, growth_group, coefficient_ring, category)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent, sage.rings.asymptotic.misc.WithLocals

Parent for generic asymptotic terms.

INPUT:

• growth_group – a growth group (i.e. an instance of GenericGrowthGroup).
• coefficient_ring – a ring which contains the (maybe implicit) coefficients of the elements.
• category – The category of the parent can be specified in order to broaden the base structure. It has to be a subcategory of Join of Category of Monoids and Category of posets. This is also the default category if None is specified.

In this class the base structure for asymptotic term monoids will be handled. These monoids are the parents of asymptotic terms (for example, see GenericTerm or OTerm). Basically, asymptotic terms consist of a growth (which is an asymptotic growth group element, for example MonomialGrowthElement); additional structure and properties are added by the classes inherited from GenericTermMonoid.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import GenericTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: G_x = GrowthGroup('x^ZZ'); x = G_x.gen()
sage: G_y = GrowthGroup('y^QQ'); y = G_y.gen()
sage: T_x_ZZ = GenericTermMonoid(TermMonoid, G_x, QQ)
sage: T_y_QQ = GenericTermMonoid(TermMonoid, G_y, QQ)
sage: T_x_ZZ
Generic Term Monoid x^ZZ with (implicit) coefficients in Rational Field
sage: T_y_QQ
Generic Term Monoid y^QQ with (implicit) coefficients in Rational Field

Element

alias of GenericTerm

change_parameter(growth_group=None, coefficient_ring=None)

Return a term monoid 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.

OUTPUT:

A term monoid.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: E = TermMonoid('exact', GrowthGroup('n^ZZ'), ZZ)
sage: E.change_parameter(coefficient_ring=QQ)
Exact Term Monoid n^ZZ with coefficients in Rational Field
sage: E.change_parameter(growth_group=GrowthGroup('n^QQ'))
Exact Term Monoid n^QQ with coefficients in Integer Ring

coefficient_ring

The coefficient ring of this term monoid, i.e. the ring where the coefficients are from.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import GenericTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: GenericTermMonoid(TermMonoid, GrowthGroup('x^ZZ'), ZZ).coefficient_ring
Integer Ring

growth_group

The growth group underlying this term monoid.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: TermMonoid('exact', GrowthGroup('x^ZZ'), ZZ).growth_group
Growth Group x^ZZ

le(left, right)

Return whether the term left is at most (less than or equal to) the term right.

INPUT:

• left – an element.
• right – an element.

OUTPUT:

A boolean.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import GenericTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: G = GrowthGroup('x^ZZ'); x = G.gen()
sage: T = GenericTermMonoid(TermMonoid, G, QQ)
sage: t1 = T(x); t2 = T(x^2)
sage: T.le(t1, t2)
True

some_elements()

Return some elements of this term monoid.

See TestSuite for a typical use case.

INPUT:

Nothing.

OUTPUT:

An iterator.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: G = GrowthGroup('x^ZZ')
sage: tuple(TermMonoid('O', G, QQ).some_elements())
(O(1), O(x), O(x^(-1)), O(x^2), O(x^(-2)), O(x^3), ...)

term_monoid(type)

Return the term monoid 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: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: E = TermMonoid('exact', GrowthGroup('x^ZZ'), ZZ); E
Exact Term Monoid x^ZZ with coefficients in Integer Ring
sage: E.term_monoid('O')
O-Term Monoid x^ZZ with implicit coefficients in Integer Ring

term_monoid_factory

The term monoid factory capable of creating this term monoid.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: TermMonoid('exact', GrowthGroup('x^ZZ'), ZZ).term_monoid_factory
Term Monoid Factory '__main__.TermMonoid'

class sage.rings.asymptotic.term_monoid.OTerm(parent, growth)

Bases: sage.rings.asymptotic.term_monoid.GenericTerm

Class for an asymptotic term representing an \(O\)-term with specified growth. For the mathematical properties of \(O\)-terms see Wikipedia article Big_O_Notation.

\(O\)-terms can absorb terms of weaker or equal growth.

INPUT:

• parent – the parent of the asymptotic term.
• growth – a growth element.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import OTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: G = GrowthGroup('x^ZZ'); x = G.gen()
sage: OT = OTermMonoid(TermMonoid, G, QQ)
sage: t1 = OT(x^-7); t2 = OT(x^5); t3 = OT(x^42)
sage: t1, t2, t3
(O(x^(-7)), O(x^5), O(x^42))
sage: t1.can_absorb(t2)
False
sage: t2.can_absorb(t1)
True
sage: t2.absorb(t1)
O(x^5)
sage: t1 <= t2 and t2 <= t3
True
sage: t3 <= t1
False

The conversion of growth elements also works for the creation of \(O\)-terms:

sage: x = SR('x'); x.parent()
Symbolic Ring
sage: OT(x^17)
O(x^17)

can_absorb(other)

Check whether this \(O\)-term can absorb other.

INPUT:

• other – an asymptotic term.

OUTPUT:

A boolean.

Note

An OTerm can absorb any other asymptotic term with weaker or equal growth.

See the module description for a detailed explanation of absorption.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: OT = TermMonoid('O', GrowthGroup('x^ZZ'), QQ)
sage: t1 = OT(x^21); t2 = OT(x^42)
sage: t1.can_absorb(t2)
False
sage: t2.can_absorb(t1)
True

is_little_o_of_one()

Return whether this O-term is of order \(o(1)\).

INPUT:

Nothing.

OUTPUT:

A boolean.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('O', GrowthGroup('x^ZZ'), QQ)
sage: T(x).is_little_o_of_one()
False
sage: T(1).is_little_o_of_one()
False
sage: T(x^(-1)).is_little_o_of_one()
True

sage: T = TermMonoid('O', GrowthGroup('x^ZZ * y^ZZ'), QQ)
sage: T('x * y^(-1)').is_little_o_of_one()
False
sage: T('x^(-1) * y').is_little_o_of_one()
False
sage: T('x^(-2) * y^(-3)').is_little_o_of_one()
True

sage: T = TermMonoid('O', GrowthGroup('x^QQ * log(x)^QQ'), QQ)
sage: T('x * log(x)^2').is_little_o_of_one()
False
sage: T('x^2 * log(x)^(-1234)').is_little_o_of_one()
False
sage: T('x^(-1) * log(x)^4242').is_little_o_of_one()
True
sage: T('x^(-1/100) * log(x)^(1000/7)').is_little_o_of_one()
True

log_term(base=None, locals=None)

Determine the logarithm of this O-term.

INPUT:

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

OUTPUT:

A tuple of terms.

Note

This method returns a tuple with the summands that come from applying the rule \(\log(x\cdot y) = \log(x) + \log(y)\).

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('O', GrowthGroup('x^ZZ * log(x)^ZZ'), QQ)
sage: T(x^2).log_term()
(O(log(x)),)
sage: T(x^1234).log_term()
(O(log(x)),)

sage: from sage.rings.asymptotic.term_monoid import TermWithCoefficientMonoid
sage: T = TermMonoid('O', GrowthGroup('x^ZZ * log(x)^ZZ * y^ZZ * log(y)^ZZ'), QQ)
sage: T('x * y').log_term()
(O(log(x)), O(log(y)))

See also

ExactTerm.log_term().

rpow(base)

Return the power of base to this O-term.

INPUT:

• base – an element or 'e'.

OUTPUT:

A term.

Note

For OTerm, the powers can only be constructed for exponents \(O(1)\) or if base is \(1\).

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('O', GrowthGroup('x^ZZ * log(x)^ZZ'), QQ)
sage: T(1).rpow('e')
O(1)
sage: T(1).rpow(2)
O(1)

sage: T.an_element().rpow(1)
1
sage: T('x^2').rpow(1)
1

sage: T.an_element().rpow('e')
Traceback (most recent call last):
...
ValueError: Cannot take e to the exponent O(x*log(x)) in
O-Term Monoid x^ZZ * log(x)^ZZ with implicit coefficients in Rational Field
sage: T('log(x)').rpow('e')
Traceback (most recent call last):
...
ValueError: Cannot take e to the exponent O(log(x)) in
O-Term Monoid x^ZZ * log(x)^ZZ with implicit coefficients in Rational Field

class sage.rings.asymptotic.term_monoid.OTermMonoid(term_monoid_factory, growth_group, coefficient_ring, category)

Bases: sage.rings.asymptotic.term_monoid.GenericTermMonoid

Parent for asymptotic big \(O\)-terms.

INPUT:

• growth_group – a growth group.
• category – The category of the parent can be specified in order to broaden the base structure. It has to be a subcategory of Join of Category of monoids and Category of posets. This is also the default category if None is specified.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import OTermMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: G_x_ZZ = GrowthGroup('x^ZZ')
sage: G_y_QQ = GrowthGroup('y^QQ')
sage: OT_x_ZZ = OTermMonoid(TermMonoid, G_x_ZZ, QQ); OT_x_ZZ
O-Term Monoid x^ZZ with implicit coefficients in Rational Field
sage: OT_y_QQ = OTermMonoid(TermMonoid, G_y_QQ, QQ); OT_y_QQ
O-Term Monoid y^QQ with implicit coefficients in Rational Field

\(O\)-term monoids can also be created by using the term factory:

sage: TermMonoid('O', G_x_ZZ, QQ) is OT_x_ZZ
True
sage: TermMonoid('O', GrowthGroup('x^QQ'), QQ)
O-Term Monoid x^QQ with implicit coefficients in Rational Field

Element

alias of OTerm

class sage.rings.asymptotic.term_monoid.TermMonoidFactory(name, exact_term_monoid_class=None, O_term_monoid_class=None)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.factory.UniqueFactory

Factory for asymptotic term monoids. It can generate the following term monoids:

• OTermMonoid,
• ExactTermMonoid.

Note

An instance of this factory is available as TermMonoid.

INPUT:

• term_monoid – the kind of terms held in the new term monoid. Either a string 'exact' or 'O' (capital letter O), or an existing instance of a term monoid.
• growth_group – a growth group or a string describing a growth group.
• coefficient_ring – a ring.
• asymptotic_ring – if specified, then growth_group and coefficient_ring are taken from this asymptotic ring.

OUTPUT:

An asymptotic term monoid.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: G = GrowthGroup('x^ZZ')
sage: TermMonoid('O', G, QQ)
O-Term Monoid x^ZZ with implicit coefficients in Rational Field
sage: TermMonoid('exact', G, ZZ)
Exact Term Monoid x^ZZ with coefficients in Integer Ring

sage: R = AsymptoticRing(growth_group=G, coefficient_ring=QQ)
sage: TermMonoid('exact', asymptotic_ring=R)
Exact Term Monoid x^ZZ with coefficients in Rational Field
sage: TermMonoid('O', asymptotic_ring=R)
O-Term Monoid x^ZZ with implicit coefficients in Rational Field

sage: TermMonoid('exact', 'QQ^m * m^QQ * log(n)^ZZ', ZZ)
Exact Term Monoid QQ^m * m^QQ * Signs^m * log(n)^ZZ
with coefficients in Integer Ring

create_key_and_extra_args(term_monoid, growth_group=None, coefficient_ring=None, asymptotic_ring=None, **kwds)

Given the arguments and keyword, create a key that uniquely determines this object.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: G = GrowthGroup('x^ZZ')
sage: TermMonoid.create_key_and_extra_args('O', G, QQ)
((<class 'sage.rings.asymptotic.term_monoid.OTermMonoid'>,
  Growth Group x^ZZ, Rational Field), {})
sage: TermMonoid.create_key_and_extra_args('exact', G, ZZ)
((<class 'sage.rings.asymptotic.term_monoid.ExactTermMonoid'>,
  Growth Group x^ZZ, Integer Ring), {})
sage: TermMonoid.create_key_and_extra_args('exact', G)
Traceback (most recent call last):
...
ValueError: A coefficient ring has to be specified
to create a term monoid of type 'exact'

create_object(version, key, **kwds)

Create a object from the given arguments.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: G = GrowthGroup('x^ZZ')
sage: TermMonoid('O', G, QQ)  # indirect doctest
O-Term Monoid x^ZZ with implicit coefficients in Rational Field
sage: TermMonoid('exact', G, ZZ)  # indirect doctest
Exact Term Monoid x^ZZ with coefficients in Integer Ring

class sage.rings.asymptotic.term_monoid.TermWithCoefficient(parent, growth, coefficient)

Bases: sage.rings.asymptotic.term_monoid.GenericTerm

Base class for asymptotic terms possessing a coefficient. For example, ExactTerm directly inherits from this class.

INPUT:

• parent – the parent of the asymptotic term.
• growth – an asymptotic growth element of the parent’s growth group.
• coefficient – an element of the parent’s coefficient ring.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermWithCoefficientMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: G = GrowthGroup('x^ZZ'); x = G.gen()
sage: CT_ZZ = TermWithCoefficientMonoid(TermMonoid, G, ZZ)
sage: CT_QQ = TermWithCoefficientMonoid(TermMonoid, G, QQ)
sage: CT_ZZ(x^2, 5)
Term with coefficient 5 and growth x^2
sage: CT_QQ(x^3, 3/8)
Term with coefficient 3/8 and growth x^3

class sage.rings.asymptotic.term_monoid.TermWithCoefficientMonoid(term_monoid_factory, growth_group, coefficient_ring, category)

Bases: sage.rings.asymptotic.term_monoid.GenericTermMonoid

This class implements the base structure for parents of asymptotic terms possessing a coefficient from some coefficient ring. In particular, this is also the parent for TermWithCoefficient.

INPUT:

• growth_group – a growth group.
• category – The category of the parent can be specified in order to broaden the base structure. It has to be a subcategory of Join of Category of monoids and Category of posets. This is also the default category if None is specified.
• coefficient_ring – the ring which contains the coefficients of the elements.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import TermWithCoefficientMonoid
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')

sage: G_ZZ = GrowthGroup('x^ZZ'); x_ZZ = G_ZZ.gen()
sage: G_QQ = GrowthGroup('x^QQ'); x_QQ = G_QQ.gen()
sage: TC_ZZ = TermWithCoefficientMonoid(TermMonoid, G_ZZ, QQ); TC_ZZ
Generic Term Monoid x^ZZ with (implicit) coefficients in Rational Field
sage: TC_QQ = TermWithCoefficientMonoid(TermMonoid, G_QQ, QQ); TC_QQ
Generic Term Monoid x^QQ with (implicit) coefficients in Rational Field
sage: TC_ZZ == TC_QQ or TC_ZZ is TC_QQ
False
sage: TC_QQ.coerce_map_from(TC_ZZ)
Coercion map:
  From: Generic Term Monoid x^ZZ with (implicit) coefficients in Rational Field
  To:   Generic Term Monoid x^QQ with (implicit) coefficients in Rational Field

Element

alias of TermWithCoefficient

some_elements()

Return some elements of this term with coefficient monoid.

See TestSuite for a typical use case.

INPUT:

Nothing.

OUTPUT:

An iterator.

EXAMPLES:

sage: from itertools import islice
sage: from sage.rings.asymptotic.term_monoid import TermMonoidFactory
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G = GrowthGroup('z^QQ')
sage: T = TermMonoid('exact', G, ZZ)
sage: tuple(islice(T.some_elements(), int(10)))
(z^(1/2), z^(-1/2), -z^(1/2), z^2, -z^(-1/2), 2*z^(1/2),
 z^(-2), -z^2, 2*z^(-1/2), -2*z^(1/2))

exception sage.rings.asymptotic.term_monoid.ZeroCoefficientError

Bases: exceptions.ValueError

sage.rings.asymptotic.term_monoid.absorption(left, right)

Let one of the two passed terms absorb the other.

Helper function used by AsymptoticExpansion.

Note

If neither of the terms can absorb the other, an ArithmeticError is raised.

See the module description for a detailed explanation of absorption.

INPUT:

• left – an asymptotic term.
• right – an asymptotic term.

OUTPUT:

An asymptotic term or None.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import (TermMonoidFactory, absorption)
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('O', GrowthGroup('x^ZZ'), ZZ)
sage: absorption(T(x^2), T(x^3))
O(x^3)
sage: absorption(T(x^3), T(x^2))
O(x^3)

sage: T = TermMonoid('exact', GrowthGroup('x^ZZ'), ZZ)
sage: absorption(T(x^2), T(x^3))
Traceback (most recent call last):
...
ArithmeticError: Absorption between x^2 and x^3 is not possible.

sage.rings.asymptotic.term_monoid.can_absorb(left, right)

Return whether one of the two input terms is able to absorb the other.

Helper function used by AsymptoticExpansion.

INPUT:

• left – an asymptotic term.
• right – an asymptotic term.

OUTPUT:

A boolean.

Note

See the module description for a detailed explanation of absorption.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: from sage.rings.asymptotic.term_monoid import (TermMonoidFactory, can_absorb)
sage: TermMonoid = TermMonoidFactory('__main__.TermMonoid')
sage: T = TermMonoid('O', GrowthGroup('x^ZZ'), ZZ)
sage: can_absorb(T(x^2), T(x^3))
True
sage: can_absorb(T(x^3), T(x^2))
True