# (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)

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)

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)

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
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)

INPUT:

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)

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:

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.


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)

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:

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

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)

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)

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)

INPUT:

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)

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',)