(Asymptotic) Growth Groups

This module provides support for (asymptotic) growth groups.

Such groups are equipped with a partial order: the elements can be seen as functions, and the behavior as their argument (or arguments) gets large (tend to \(\infty\)) is compared.

Growth groups are used for the calculations done in the asymptotic ring. There, take a look at the informal definition, where examples of growth groups and elements are given as well.

Description of Growth Groups

Many growth groups can be described by a string, which can also be used to create them. For example, the string 'x^QQ * log(x)^ZZ * QQ^y * y^QQ' represents a growth group with the following properties:

  • It is a growth group in the two variables \(x\) and \(y\).

  • Its elements are of the form

    \[x^r \cdot \log(x)^s \cdot a^y \cdot y^q\]

    for \(r\in\QQ\), \(s\in\ZZ\), \(a\in\QQ\) and \(q\in\QQ\).

  • The order is with respect to \(x\to\infty\) and \(y\to\infty\) independently of each other.

  • To compare such elements, they are split into parts belonging to only one variable. In the example above,

    \[x^{r_1} \cdot \log(x)^{s_1} \leq x^{r_2} \cdot \log(x)^{s_2}\]

    if \((r_1, s_1) \leq (r_2, s_2)\) lexicographically. This reflects the fact that elements \(x^r\) are larger than elements \(\log(x)^s\) as \(x\to\infty\). The factors belonging to the variable \(y\) are compared analogously.

    The results of these comparisons are then put together using the product order, i.e., \(\leq\) if each component satisfies \(\leq\).

Each description string consists of ordered factors—yes, this means * is noncommutative—of strings describing “elementary” growth groups (see the examples below). As stated in the example above, these factors are split by their variable; factors with the same variable are grouped. Reading such factors from left to right determines the order: Comparing elements of two factors (growth groups) \(L\) and \(R\), then all elements of \(L\) are considered to be larger than each element of \(R\).

Creating a Growth Group

For many purposes the factory GrowthGroup (see GrowthGroupFactory) is the most convenient way to generate a growth group.

sage: from sage.rings.asymptotic.growth_group import GrowthGroup

Here are some examples:

sage: GrowthGroup('z^ZZ')
Growth Group z^ZZ
sage: M = GrowthGroup('z^QQ'); M
Growth Group z^QQ

Each of these two generated groups is a MonomialGrowthGroup, whose elements are powers of a fixed symbol (above 'z'). For the order of the elements it is assumed that \(z\to\infty\).

Note

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

To create elements of \(M\), a generator can be used:

sage: z = M.gen()
sage: z^(3/5)
z^(3/5)

Strings can also be parsed:

sage: M('z^7')
z^7

Similarly, we can construct logarithmic factors by:

sage: GrowthGroup('log(z)^QQ')
Growth Group log(z)^QQ

which again creates a MonomialGrowthGroup. An ExponentialGrowthGroup is generated in the same way. Our factory gives

sage: E = GrowthGroup('QQ^z'); E
Growth Group QQ^z

and a typical element looks like this:

sage: E.an_element()
(1/2)^z

More complex groups are created in a similar fashion. For example

sage: C = GrowthGroup('QQ^z * z^QQ * log(z)^QQ'); C
Growth Group QQ^z * z^QQ * log(z)^QQ

This contains elements of the form

sage: C.an_element()
(1/2)^z*z^(1/2)*log(z)^(1/2)

The group \(C\) itself is a Cartesian product; to be precise a UnivariateProduct. We can see its factors:

sage: C.cartesian_factors()
(Growth Group QQ^z, Growth Group z^QQ, Growth Group log(z)^QQ)

Multivariate constructions are also possible:

sage: GrowthGroup('x^QQ * y^QQ')
Growth Group x^QQ * y^QQ

This gives a MultivariateProduct.

Both these Cartesian products are derived from the class GenericProduct. Moreover all growth groups have the abstract base class GenericGrowthGroup in common.

Some Examples

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G_x = GrowthGroup('x^ZZ'); G_x
Growth Group x^ZZ
sage: G_xy = GrowthGroup('x^ZZ * y^ZZ'); G_xy
Growth Group x^ZZ * y^ZZ
sage: G_xy.an_element()
x*y
sage: x = G_xy('x'); y = G_xy('y')
sage: x^2
x^2
sage: elem = x^21*y^21; elem^2
x^42*y^42

A monomial growth group itself is totally ordered, all elements are comparable. However, this does not hold for Cartesian products:

sage: e1 = x^2*y; e2 = x*y^2
sage: e1 <= e2 or e2 <= e1
False

In terms of uniqueness, we have the following behaviour:

sage: GrowthGroup('x^ZZ * y^ZZ') is GrowthGroup('y^ZZ * x^ZZ')
True

The above is True since the order of the factors does not play a role here; they use different variables. But when using the same variable, it plays a role:

sage: GrowthGroup('x^ZZ * log(x)^ZZ') is GrowthGroup('log(x)^ZZ * x^ZZ')
False

In this case the components are ordered lexicographically, which means that in the second growth group, log(x) is assumed to grow faster than x (which is nonsense, mathematically). See CartesianProduct for more details or see above for a more extensive description.

Short notation also allows the construction of more complicated growth groups:

sage: G = GrowthGroup('QQ^x * x^ZZ * log(x)^QQ * y^QQ')
sage: G.an_element()
(1/2)^x*x*log(x)^(1/2)*y^(1/2)
sage: x, y = var('x y')
sage: G(2^x * log(x) * y^(1/2)) * G(x^(-5) * 5^x * y^(1/3))
10^x*x^(-5)*log(x)*y^(5/6)

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.growth_group.AbstractGrowthGroupFunctor(var, domain)

Bases: sage.categories.pushout.ConstructionFunctor

A base class for the functors constructing growth groups.

INPUT:

  • var – a string or list of strings (or anything else Variable accepts).
  • domain – a category.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('z^QQ').construction()[0]  # indirect doctest
MonomialGrowthGroup[z]
merge(other)

Merge this functor with other of possible.

INPUT:

  • other – a functor.

OUTPUT:

A functor or None.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: F = GrowthGroup('QQ^t').construction()[0]
sage: G = GrowthGroup('t^QQ').construction()[0]
sage: F.merge(F)
ExponentialGrowthGroup[t]
sage: F.merge(G) is None
True
class sage.rings.asymptotic.growth_group.ExponentialGrowthElement(parent, raw_element)

Bases: sage.rings.asymptotic.growth_group.GenericGrowthElement

An implementation of exponential growth elements.

INPUT:

  • parent – an ExponentialGrowthGroup.

  • raw_element – an element from the base ring of the parent.

    This raw_element is the base of the created exponential growth element.

An exponential growth element represents a term of the type \(\operatorname{base}^{\operatorname{variable}}\). The multiplication corresponds to the multiplication of the bases.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: P = GrowthGroup('ZZ^x')
sage: e1 = P(1); e1
1
sage: e2 = P(raw_element=2); e2
2^x
sage: e1 == e2
False
sage: P.le(e1, e2)
True
sage: P.le(e1, P(1)) and P.le(P(1), e2)
True
base

The base of this exponential growth element.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: P = GrowthGroup('ZZ^x')
sage: P(42^x).base
42
class sage.rings.asymptotic.growth_group.ExponentialGrowthGroup(base, var, category)

Bases: sage.rings.asymptotic.growth_group.GenericGrowthGroup

A growth group dealing with expressions involving a fixed variable/symbol as the exponent.

The elements ExponentialGrowthElement of this group represent exponential functions with bases from a fixed base ring; the group law is the multiplication.

INPUT:

  • base – one of SageMath’s parents, out of which the elements get their data (raw_element).

    As exponential expressions are represented by this group, the elements in base are the bases of these exponentials.

  • var – an object.

    The string representation of var acts as an exponent of the elements represented by this group.

  • category – (default: None) the category of the newly created growth group. It has to be a subcategory of Join of Category of groups and Category of posets. This is also the default category if None is specified.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import ExponentialGrowthGroup
sage: P = ExponentialGrowthGroup(QQ, 'x'); P
Growth Group QQ^x
DivisionRings

alias of DivisionRings

Element

alias of ExponentialGrowthElement

Groups

alias of Groups

Magmas

alias of Magmas

Posets

alias of Posets

Sets

alias of Sets

construction()

Return the construction of this growth group.

OUTPUT:

A pair whose first entry is an exponential construction functor and its second entry the base.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('QQ^x').construction()
(ExponentialGrowthGroup[x], Rational Field)
gens()

Return a tuple of all generators of this exponential growth group.

INPUT:

Nothing.

OUTPUT:

An empty tuple.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: E = GrowthGroup('ZZ^x')
sage: E.gens()
()
some_elements()

Return some elements of this exponential growth group.

See TestSuite for a typical use case.

INPUT:

Nothing.

OUTPUT:

An iterator.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: tuple(GrowthGroup('QQ^z').some_elements())
((1/2)^z, (-1/2)^z, 2^z, (-2)^z, 1, (-1)^z,
 42^z, (2/3)^z, (-2/3)^z, (3/2)^z, (-3/2)^z, ...)
class sage.rings.asymptotic.growth_group.ExponentialGrowthGroupFunctor(var)

Bases: sage.rings.asymptotic.growth_group.AbstractGrowthGroupFunctor

A construction functor for exponential growth groups.

INPUT:

  • var – a string or list of strings (or anything else Variable accepts).

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup, ExponentialGrowthGroupFunctor
sage: GrowthGroup('QQ^z').construction()[0]
ExponentialGrowthGroup[z]
class sage.rings.asymptotic.growth_group.GenericGrowthElement(parent, raw_element)

Bases: sage.structure.element.MultiplicativeGroupElement

A basic implementation of a generic growth element.

Growth elements form a group by multiplication, and (some of) the elements can be compared to each other, i.e., all elements form a poset.

INPUT:

  • parent – a GenericGrowthGroup.
  • raw_element – an element from the base of the parent.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import (GenericGrowthGroup,
....:                                                 GenericGrowthElement)
sage: G = GenericGrowthGroup(ZZ)
sage: g = GenericGrowthElement(G, 42); g
GenericGrowthElement(42)
sage: g.parent()
Growth Group Generic(ZZ)
sage: G(raw_element=42) == g
True
factors()

Return the atomic factors of this growth element. An atomic factor cannot be split further.

INPUT:

Nothing.

OUTPUT:

A tuple of growth elements.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G = GrowthGroup('x^ZZ')
sage: G.an_element().factors()
(x,)
is_lt_one()

Return whether this element is less than \(1\).

INPUT:

Nothing.

OUTPUT:

A boolean.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G = GrowthGroup('x^ZZ'); x = G(x)
sage: (x^42).is_lt_one()  # indirect doctest
False
sage: (x^(-42)).is_lt_one()  # indirect doctest
True
log(base=None)

Return the logarithm of this element.

INPUT:

  • base – the base of the logarithm. If None (default value) is used, the natural logarithm is taken.

OUTPUT:

A growth element.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G = GrowthGroup('x^ZZ * log(x)^ZZ')
sage: x, = G.gens_monomial()
sage: log(x)  # indirect doctest
log(x)
sage: log(x^5)  # indirect doctest
Traceback (most recent call last):
...
ArithmeticError: When calculating log(x^5) a factor 5 != 1 appeared,
which is not contained in Growth Group x^ZZ * log(x)^ZZ.
sage: G = GrowthGroup('QQ^x * x^ZZ')
sage: x, = G.gens_monomial()
sage: el = x.rpow(2); el
2^x
sage: log(el)  # indirect doctest
Traceback (most recent call last):
...
ArithmeticError: When calculating log(2^x) a factor log(2) != 1
appeared, which is not contained in Growth Group QQ^x * x^ZZ.
sage: log(el, base=2)  # indirect doctest
x
sage: from sage.rings.asymptotic.growth_group import GenericGrowthGroup
sage: x = GenericGrowthGroup(ZZ).an_element()
sage: log(x)  # indirect doctest
Traceback (most recent call last):
...
NotImplementedError: Cannot determine logarithmized factorization of
GenericGrowthElement(1) in abstract base class.
sage: x = GrowthGroup('x^ZZ').an_element()
sage: log(x)  # indirect doctest
Traceback (most recent call last):
...
ArithmeticError: Cannot build log(x) since log(x) is not in
Growth Group x^ZZ.
sage: G = GrowthGroup("(e^x)^ZZ * x^ZZ")
sage: x, = G.gens_monomial()
sage: log(exp(x))  # indirect doctest
x
sage: G.one().log()  # indirect doctest
Traceback (most recent call last):
...
ArithmeticError: log(1) is zero, which is not contained in
Growth Group (e^x)^ZZ * x^ZZ.
sage: G = GrowthGroup('QQ^x * x^ZZ * log(x)^ZZ * y^ZZ * log(y)^ZZ')
sage: x, y = G.gens_monomial()
sage: (x * y).log()  # indirect doctest
Traceback (most recent call last):
...
ArithmeticError: Calculating log(x*y) results in a sum,
which is not contained in
Growth Group QQ^x * x^ZZ * log(x)^ZZ * y^ZZ * log(y)^ZZ.
log_factor(base=None)

Return the logarithm of the factorization of this element.

INPUT:

  • base – the base of the logarithm. If None (default value) is used, the natural logarithm is taken.

OUTPUT:

A tuple of pairs, where the first entry is a growth element and the second a multiplicative coefficient.

ALGORITHM:

This function factors the given element and calculates the logarithm of each of these factors.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G = GrowthGroup('QQ^x * x^ZZ * log(x)^ZZ * y^ZZ * log(y)^ZZ')
sage: x, y = G.gens_monomial()
sage: (x * y).log_factor()  # indirect doctest
((log(x), 1), (log(y), 1))
sage: (x^123).log_factor()  # indirect doctest
((log(x), 123),)
sage: (G('2^x') * x^2).log_factor(base=2)  # indirect doctest
((x, 1), (log(x), 2/log(2)))
sage: G(1).log_factor()
()
sage: log(x).log_factor()  # indirect doctest
Traceback (most recent call last):
...
ArithmeticError: Cannot build log(log(x)) since log(log(x)) is
not in Growth Group QQ^x * x^ZZ * log(x)^ZZ * y^ZZ * log(y)^ZZ.

See also

factors(), log().

rpow(base)

Calculate the power of base to this element.

INPUT:

  • base – an element.

OUTPUT:

A growth element.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G = GrowthGroup('QQ^x * x^ZZ')
sage: x = G('x')
sage: x.rpow(2)  # indirect doctest
2^x
sage: x.rpow(1/2)  # indirect doctest
(1/2)^x
sage: x.rpow(0)  # indirect doctest
Traceback (most recent call last):
...
ValueError: 0 is not an allowed base for calculating the power to x.
sage: (x^2).rpow(2)  # indirect doctest
Traceback (most recent call last):
...
ArithmeticError: Cannot construct 2^(x^2) in Growth Group QQ^x * x^ZZ
> *previous* TypeError: unsupported operand parent(s) for *:
'Growth Group QQ^x * x^ZZ' and 'Growth Group ZZ^(x^2)'
sage: G = GrowthGroup('QQ^(x*log(x)) * x^ZZ * log(x)^ZZ')
sage: x = G('x')
sage: (x * log(x)).rpow(2)  # indirect doctest
2^(x*log(x))
sage: n = GrowthGroup('QQ^n * n^QQ')('n')
sage: n.rpow(2)
2^n
sage: _.parent()
Growth Group QQ^n * n^QQ
variable_names()

Return the names of the variables of this growth element.

OUTPUT:

A tuple of strings.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G = GrowthGroup('m^QQ')
sage: G('m^2').variable_names()
('m',)
sage: G('m^0').variable_names()
()
sage: G = GrowthGroup('QQ^m')
sage: G('2^m').variable_names()
('m',)
sage: G('1^m').variable_names()
()
class sage.rings.asymptotic.growth_group.GenericGrowthGroup(base, var, category)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

A basic implementation for growth groups.

INPUT:

  • base – one of SageMath’s parents, out of which the elements get their data (raw_element).
  • category – (default: None) the category of the newly created growth group. It has to be a subcategory of Join of Category of groups and Category of posets. This is also the default category if None is specified.
  • ignore_variables – (default: None) a tuple (or other iterable) of strings. The specified names are not considered as variables.

Note

This class should be derived for concrete implementations.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GenericGrowthGroup
sage: G = GenericGrowthGroup(ZZ); G
Growth Group Generic(ZZ)
AdditiveMagmas

alias of AdditiveMagmas

Element

alias of GenericGrowthElement

Magmas

alias of Magmas

Posets

alias of Posets

Sets

alias of Sets

gen(n=0)

Return the \(n\)-th generator (as a group) of this growth group.

INPUT:

  • n – default: \(0\).

OUTPUT:

A MonomialGrowthElement.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: P = GrowthGroup('x^ZZ')
sage: P.gen()
x
sage: P = GrowthGroup('QQ^x')
sage: P.gen()
Traceback (most recent call last):
...
IndexError: tuple index out of range
gens()

Return a tuple of all generators of this growth group.

INPUT:

Nothing.

OUTPUT:

A tuple whose entries are growth elements.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: P = GrowthGroup('x^ZZ')
sage: P.gens()
(x,)
sage: GrowthGroup('log(x)^ZZ').gens()
(log(x),)
gens_monomial()

Return a tuple containing monomial generators of this growth group.

INPUT:

Nothing.

OUTPUT:

An empty tuple.

Note

A generator is called monomial generator if the variable of the underlying growth group is a valid identifier. For example, x^ZZ has x as a monomial generator, while log(x)^ZZ or icecream(x)^ZZ do not have monomial generators.

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('x^QQ').gens_monomial()
(x,)
sage: GrowthGroup('QQ^x').gens_monomial()
()
le(left, right)

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

INPUT:

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

OUTPUT:

A boolean.

Note

This function uses the coercion model to find a common parent for the two operands.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G = GrowthGroup('x^ZZ')
sage: x = G.gen()
sage: G.le(x, x^2)
True
sage: G.le(x^2, x)
False
sage: G.le(x^0, 1)
True
ngens()

Return the number of generators (as a group) of this growth group.

INPUT:

Nothing.

OUTPUT:

A Python integer.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: P = GrowthGroup('x^ZZ')
sage: P.ngens()
1
sage: GrowthGroup('log(x)^ZZ').ngens()
1
sage: P = GrowthGroup('QQ^x')
sage: P.ngens()
0
some_elements()

Return some elements of this growth group.

See TestSuite for a typical use case.

INPUT:

Nothing.

OUTPUT:

An iterator.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: tuple(GrowthGroup('z^ZZ').some_elements())
(1, z, z^(-1), z^2, z^(-2), z^3, z^(-3),
 z^4, z^(-4), z^5, z^(-5), ...)
sage: tuple(GrowthGroup('z^QQ').some_elements())
(z^(1/2), z^(-1/2), z^2, z^(-2),
 1, z, z^(-1), z^42,
 z^(2/3), z^(-2/3), z^(3/2), z^(-3/2),
 z^(4/5), z^(-4/5), z^(5/4), z^(-5/4), ...)
variable_names()

Return the names of the variables of this growth group.

OUTPUT:

A tuple of strings.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GenericGrowthGroup
sage: GenericGrowthGroup(ZZ).variable_names()
()
sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('x^ZZ').variable_names()
('x',)
sage: GrowthGroup('log(x)^ZZ').variable_names()
('x',)
sage: GrowthGroup('QQ^x').variable_names()
('x',)
sage: GrowthGroup('QQ^(x*log(x))').variable_names()
('x',)
sage.rings.asymptotic.growth_group.GrowthGroup = <class 'sage.rings.asymptotic.growth_group.GrowthGroupFactory'>

A factory for growth groups. This is an instance of GrowthGroupFactory whose documentation provides more details.

class sage.rings.asymptotic.growth_group.GrowthGroupFactory

Bases: sage.structure.factory.UniqueFactory

A factory creating asymptotic growth groups.

INPUT:

  • specification – a string.
  • keyword arguments are passed on to the growth group constructor. If the keyword ignore_variables is not specified, then ignore_variables=('e',) (to ignore e as a variable name) is used.

OUTPUT:

An asymptotic growth group.

Note

An instance of this factory is available as GrowthGroup.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('x^ZZ')
Growth Group x^ZZ
sage: GrowthGroup('log(x)^QQ')
Growth Group log(x)^QQ

This factory can also be used to construct Cartesian products of growth groups:

sage: GrowthGroup('x^ZZ * y^ZZ')
Growth Group x^ZZ * y^ZZ
sage: GrowthGroup('x^ZZ * log(x)^ZZ')
Growth Group x^ZZ * log(x)^ZZ
sage: GrowthGroup('x^ZZ * log(x)^ZZ * y^QQ')
Growth Group x^ZZ * log(x)^ZZ * y^QQ
sage: GrowthGroup('QQ^x * x^ZZ * y^QQ * QQ^z')
Growth Group QQ^x * x^ZZ * y^QQ * QQ^z
sage: GrowthGroup('exp(x)^ZZ * x^ZZ')
Growth Group exp(x)^ZZ * x^ZZ
sage: GrowthGroup('(e^x)^ZZ * x^ZZ')
Growth Group (e^x)^ZZ * x^ZZ
sage: TestSuite(GrowthGroup('QQ^y')).run(verbose=True)  # long time
running ._test_an_element() . . . pass
running ._test_associativity() . . . pass
running ._test_cardinality() . . . pass
running ._test_category() . . . pass
running ._test_elements() . . .
  Running the test suite of self.an_element()
  running ._test_category() . . . pass
  running ._test_eq() . . . pass
  running ._test_new() . . . pass
  running ._test_not_implemented_methods() . . . pass
  running ._test_pickling() . . . pass
  pass
running ._test_elements_eq_reflexive() . . . pass
running ._test_elements_eq_symmetric() . . . pass
running ._test_elements_eq_transitive() . . . pass
running ._test_elements_neq() . . . pass
running ._test_eq() . . . pass
running ._test_inverse() . . . pass
running ._test_new() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_one() . . . pass
running ._test_pickling() . . . pass
running ._test_prod() . . . pass
running ._test_some_elements() . . . pass
sage: TestSuite(GrowthGroup('x^QQ * log(x)^ZZ')).run(verbose=True)  # long time
running ._test_an_element() . . . pass
running ._test_associativity() . . . pass
running ._test_cardinality() . . . pass
running ._test_category() . . . pass
running ._test_elements() . . .
  Running the test suite of self.an_element()
  running ._test_category() . . . pass
  running ._test_eq() . . . pass
  running ._test_new() . . . pass
  running ._test_not_implemented_methods() . . . pass
  running ._test_pickling() . . . pass
  pass
running ._test_elements_eq_reflexive() . . . pass
running ._test_elements_eq_symmetric() . . . pass
running ._test_elements_eq_transitive() . . . pass
running ._test_elements_neq() . . . pass
running ._test_eq() . . . pass
running ._test_inverse() . . . pass
running ._test_new() . . . pass
running ._test_not_implemented_methods() . . . pass
running ._test_one() . . . pass
running ._test_pickling() . . . pass
running ._test_prod() . . . pass
running ._test_some_elements() . . . pass
create_key_and_extra_args(specification, **kwds)

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

create_object(version, factors, **kwds)

Create an object from the given arguments.

class sage.rings.asymptotic.growth_group.MonomialGrowthElement(parent, raw_element)

Bases: sage.rings.asymptotic.growth_group.GenericGrowthElement

An implementation of monomial growth elements.

INPUT:

  • parent – a MonomialGrowthGroup.

  • raw_element – an element from the base ring of the parent.

    This raw_element is the exponent of the created monomial growth element.

A monomial growth element represents a term of the type \(\operatorname{variable}^{\operatorname{exponent}}\). The multiplication corresponds to the addition of the exponents.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup
sage: P = MonomialGrowthGroup(ZZ, 'x')
sage: e1 = P(1); e1
1
sage: e2 = P(raw_element=2); e2
x^2
sage: e1 == e2
False
sage: P.le(e1, e2)
True
sage: P.le(e1, P.gen()) and P.le(P.gen(), e2)
True
exponent

The exponent of this growth element.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: P = GrowthGroup('x^ZZ')
sage: P(x^42).exponent
42
class sage.rings.asymptotic.growth_group.MonomialGrowthGroup(base, var, category)

Bases: sage.rings.asymptotic.growth_group.GenericGrowthGroup

A growth group dealing with powers of a fixed object/symbol.

The elements MonomialGrowthElement of this group represent powers of a fixed base; the group law is the multiplication, which corresponds to the addition of the exponents of the monomials.

INPUT:

  • base – one of SageMath’s parents, out of which the elements get their data (raw_element).

    As monomials are represented by this group, the elements in base are the exponents of these monomials.

  • var – an object.

    The string representation of var acts as a base of the monomials represented by this group.

  • category – (default: None) the category of the newly created growth group. It has to be a subcategory of Join of Category of groups and Category of posets. This is also the default category if None is specified.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup
sage: P = MonomialGrowthGroup(ZZ, 'x'); P
Growth Group x^ZZ
sage: MonomialGrowthGroup(ZZ, log(SR.var('y')))
Growth Group log(y)^ZZ
AdditiveMagmas

alias of AdditiveMagmas

Element

alias of MonomialGrowthElement

Magmas

alias of Magmas

Posets

alias of Posets

Sets

alias of Sets

construction()

Return the construction of this growth group.

OUTPUT:

A pair whose first entry is a monomial construction functor and its second entry the base.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('x^ZZ').construction()
(MonomialGrowthGroup[x], Integer Ring)
gens_logarithmic()

Return a tuple containing logarithmic generators of this growth group.

INPUT:

Nothing.

OUTPUT:

A tuple containing elements of this growth group.

Note

A generator is called logarithmic generator if the variable of the underlying growth group is the logarithm of a valid identifier. For example, x^ZZ has no logarithmic generator, while log(x)^ZZ has log(x) as logarithmic generator.

gens_monomial()

Return a tuple containing monomial generators of this growth group.

INPUT:

Nothing.

OUTPUT:

A tuple containing elements of this growth group.

Note

A generator is called monomial generator if the variable of the underlying growth group is a valid identifier. For example, x^ZZ has x as a monomial generator, while log(x)^ZZ or icecream(x)^ZZ do not have monomial generators.

class sage.rings.asymptotic.growth_group.MonomialGrowthGroupFunctor(var)

Bases: sage.rings.asymptotic.growth_group.AbstractGrowthGroupFunctor

A construction functor for monomial growth groups.

INPUT:

  • var – a string or list of strings (or anything else Variable accepts).

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup, MonomialGrowthGroupFunctor
sage: GrowthGroup('z^QQ').construction()[0]
MonomialGrowthGroup[z]
class sage.rings.asymptotic.growth_group.Variable(var, repr=None, latex_name=None, ignore=None)

Bases: sage.structure.unique_representation.CachedRepresentation, sage.structure.sage_object.SageObject

A class managing the variable of a growth group.

INPUT:

  • var – an object whose representation string is used as the variable. It has to be a valid Python identifier. var can also be a tuple (or other iterable) of such objects.
  • repr – (default: None) if specified, then this string will be displayed instead of var. Use this to get e.g. log(x)^ZZ: var is then used to specify the variable \(x\).
  • latex_name – (default: None) if specified, then this string will be used as LaTeX-representation of var.
  • ignore – (default: None) a tuple (or other iterable) of strings which are not variables.
sage: v = Variable(('x', 'y')); repr(v), v.variable_names()
('x, y', ('x', 'y'))
sage: v = Variable(('x', 'log(y)')); repr(v), v.variable_names()
('x, log(y)', ('x', 'y'))
sage: v = Variable(('x', 'log(x)')); repr(v), v.variable_names()
Traceback (most recent call last):
...
ValueError: Variable names ('x', 'x') are not pairwise distinct.
sage: v = Variable('log(x)'); repr(v), v.variable_names()
('log(x)', ('x',))
sage: v = Variable('log(log(x))'); repr(v), v.variable_names()
('log(log(x))', ('x',))
sage: v = Variable('x', repr='log(x)'); repr(v), v.variable_names()
('log(x)', ('x',))
sage: v = Variable('e^x', ignore=('e',)); repr(v), v.variable_names()
('e^x', ('x',))
sage: v = Variable('(e^n)', ignore=('e',)); repr(v), v.variable_names()
('e^n', ('n',))
sage: v = Variable('(e^(n*log(n)))', ignore=('e',)); repr(v), v.variable_names()
('e^(n*log(n))', ('n',))
static extract_variable_names(s)

Determine the name of the variable for the given string.

INPUT:

  • s – a string.

OUTPUT:

A tuple of strings.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import Variable
sage: Variable.extract_variable_names('')
()
sage: Variable.extract_variable_names('x')
('x',)
sage: Variable.extract_variable_names('exp(x)')
('x',)
sage: Variable.extract_variable_names('sin(cos(ln(x)))')
('x',)
sage: Variable.extract_variable_names('log(77w)')
('w',)
sage: Variable.extract_variable_names('log(x')
Traceback (most recent call last):
....
TypeError: Bad function call: log(x !!!
sage: Variable.extract_variable_names('x)')
Traceback (most recent call last):
....
TypeError: Malformed expression: x) !!!
sage: Variable.extract_variable_names('log)x(')
Traceback (most recent call last):
....
TypeError: Malformed expression: log) !!! x(
sage: Variable.extract_variable_names('log(x)+y')
('x', 'y')
sage: Variable.extract_variable_names('icecream(summer)')
('summer',)
sage: Variable.extract_variable_names('a + b')
('a', 'b')
sage: Variable.extract_variable_names('a+b')
('a', 'b')
sage: Variable.extract_variable_names('a +b')
('a', 'b')
sage: Variable.extract_variable_names('+a')
('a',)
sage: Variable.extract_variable_names('a+')
Traceback (most recent call last):
...
TypeError: Malformed expression: a+ !!!
sage: Variable.extract_variable_names('b!')
('b',)
sage: Variable.extract_variable_names('-a')
('a',)
sage: Variable.extract_variable_names('a*b')
('a', 'b')
sage: Variable.extract_variable_names('2^q')
('q',)
sage: Variable.extract_variable_names('77')
()
sage: Variable.extract_variable_names('a + (b + c) + d')
('a', 'b', 'c', 'd')
is_monomial()

Return whether this is a monomial variable.

OUTPUT:

A boolean.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import Variable
sage: Variable('x').is_monomial()
True
sage: Variable('log(x)').is_monomial()
False
variable_names()

Return the names of the variables.

OUTPUT:

A tuple of strings.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import Variable
sage: Variable('x').variable_names()
('x',)
sage: Variable('log(x)').variable_names()
('x',)