(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: 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

rank = 13#

exception sage.rings.asymptotic.growth_group.DecreasingGrowthElementError(element, *args, **kwds)#

Bases: ValueError

A special ValueError which is raised when a growth element is less than one.

INPUT:

element – a GenericGrowthElement

The remaining arguments are passed on to ValueError.

class sage.rings.asymptotic.growth_group.ExponentialGrowthElement(parent, raw_element)#

Bases: 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

property 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, *args, **kwds)#

Bases: 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

See also

GenericGrowthGroup

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)

classmethod factory(base, var, extend_by_non_growth_group=True, return_factors=False, **kwds)#

Create an exponential growth group.

This factory takes care of the splitting of the bases into their absolute values and arguments.

INPUT:

base, var, keywords – use in the initialization of the exponential growth group; see ExponentialGrowthGroup for details.
extend_by_non_growth_group – a boolean (default True). If set, then the growth group consists of two parts, one part dealing with the absolute values of the bases and one for their arguments.
return_factors – a boolean (default: False). If set, then a tuple of the (cartesian) factors of this growth group is returned.

OUTPUT:

A growth group or tuple of growth groups.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import ExponentialGrowthGroup
sage: ExponentialGrowthGroup.factory(QQ, 'n')
Growth Group QQ^n * Signs^n

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

non_growth_group()#

Return a non-growth group (with an argument group, e.g. roots of unity, as base) compatible with this exponential growth group.

OUTPUT:

A group group.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('(QQ_+)^x').non_growth_group()
Growth Group Signs^x
sage: GrowthGroup('(RR_+)^x').non_growth_group()
Growth Group Signs^x
sage: GrowthGroup('(RIF_+)^x').non_growth_group()
Growth Group Signs^x
sage: GrowthGroup('(RBF_+)^x').non_growth_group()
Growth Group Signs^x
sage: GrowthGroup('(CC_+)^x').non_growth_group()
Growth Group UU_RR^x
sage: GrowthGroup('(CIF_+)^x').non_growth_group()
Growth Group UU_RIF^x
sage: GrowthGroup('(CBF_+)^x').non_growth_group()
Growth Group UU_RBF^x

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, 2^z, 1, 42^z, (2/3)^z, (3/2)^z, ...)

class sage.rings.asymptotic.growth_group.ExponentialGrowthGroupFunctor(var)#

Bases: 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.ExponentialNonGrowthElement(parent, raw_element)#

Bases: GenericNonGrowthElement, ExponentialGrowthElement

An element of ExponentialNonGrowthGroup.

class sage.rings.asymptotic.growth_group.ExponentialNonGrowthGroup(base, *args, **kwds)#

Bases: GenericNonGrowthGroup, ExponentialGrowthGroup

A growth group whose base is an argument group.

EXAMPLES:

sage: from sage.groups.misc_gps.argument_groups import RootsOfUnityGroup
sage: from sage.rings.asymptotic.growth_group import ExponentialNonGrowthGroup
sage: UU = ExponentialNonGrowthGroup(RootsOfUnityGroup(), 'n')
sage: UU(raw_element=-1)
(-1)^n

Element#: alias of ExponentialNonGrowthElement

construction()#

Return the construction of this growth group.

OUTPUT:

A pair whose first entry is an ExponentialNonGrowthGroupFunctor and its second entry the base.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('UU^x').construction()
(ExponentialNonGrowthGroup[x], Group of Roots of Unity)

class sage.rings.asymptotic.growth_group.ExponentialNonGrowthGroupFunctor(var)#

Bases: ExponentialGrowthGroupFunctor

A construction functor for ExponentialNonGrowthGroup.

class sage.rings.asymptotic.growth_group.GenericGrowthElement(parent, raw_element)#

Bases: 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.

log_factor(base=None, locals=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.
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 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

sage: n = GrowthGroup('QQ^n * n^QQ')('n')
sage: n.rpow(-2)
2^n*(-1)^n

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: UniqueRepresentation, Parent, WithLocals

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

CartesianProduct = <sage.rings.asymptotic.growth_group_cartesian.CartesianProductFactory object>#

Element#: alias of GenericGrowthElement

Magmas#: alias of Magmas

Posets#: alias of Posets

Sets#: alias of Sets

extended_by_non_growth_group()#

Extend to a cartesian product of this growth group and a suitable non growth group.

OUTPUT:

A group group.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('(QQ_+)^x').extended_by_non_growth_group()
Growth Group QQ^x * Signs^x
sage: GrowthGroup('(RR_+)^x').extended_by_non_growth_group()
Growth Group RR^x * Signs^x
sage: GrowthGroup('(RIF_+)^x').extended_by_non_growth_group()
Growth Group RIF^x * Signs^x
sage: GrowthGroup('(RBF_+)^x').extended_by_non_growth_group()
Growth Group RBF^x * Signs^x
sage: GrowthGroup('(CC_+)^x').extended_by_non_growth_group()
Growth Group CC^x * UU_RR^x
sage: GrowthGroup('(CIF_+)^x').extended_by_non_growth_group()
Growth Group CIF^x * UU_RIF^x
sage: GrowthGroup('(CBF_+)^x').extended_by_non_growth_group()
Growth Group CBF^x * UU_RBF^x

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.

is_compatible(other)#

Return whether this growth group is compatible with other meaning that both are of the same type and have the same variables, but maybe a different base.

INPUT:

other – a growth group

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import ExponentialGrowthGroup, ExponentialNonGrowthGroup
sage: from sage.groups.misc_gps.argument_groups import RootsOfUnityGroup
sage: EQ = ExponentialGrowthGroup(QQ, 'n')
sage: EZ = ExponentialGrowthGroup(ZZ, 'n')
sage: UU = ExponentialNonGrowthGroup(RootsOfUnityGroup(), 'n')
sage: for a in (EQ, EZ, UU):
....:     for b in (EQ, EZ, UU):
....:         print('{} is {}compatible with {}'.format(
....:             a, '' if a.is_compatible(b) else 'not ', b))
Growth Group QQ^n is compatible with Growth Group QQ^n
Growth Group QQ^n is compatible with Growth Group ZZ^n
Growth Group QQ^n is compatible with Growth Group UU^n
Growth Group ZZ^n is compatible with Growth Group QQ^n
Growth Group ZZ^n is compatible with Growth Group ZZ^n
Growth Group ZZ^n is compatible with Growth Group UU^n
Growth Group UU^n is not compatible with Growth Group QQ^n
Growth Group UU^n is not compatible with Growth Group ZZ^n
Growth Group UU^n is compatible with Growth Group UU^n

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

non_growth_group()#

Return a non-growth group compatible with this growth group.

OUTPUT:

A group group.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GenericGrowthGroup
sage: GenericGrowthGroup(ZZ, 'n').non_growth_group()
Traceback (most recent call last):
...
NotImplementedError: only implemented in concrete realizations

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

class sage.rings.asymptotic.growth_group.GenericNonGrowthElement(parent, raw_element)#

Bases: GenericGrowthElement

An element of GenericNonGrowthGroup.

class sage.rings.asymptotic.growth_group.GenericNonGrowthGroup(base, var, category)#

Bases: GenericGrowthGroup

A (abstract) growth group whose elements are all of the same growth \(1\).

See ExponentialNonGrowthGroup for a concrete realization.

sage.rings.asymptotic.growth_group.GrowthGroup = <sage.rings.asymptotic.growth_group.GrowthGroupFactory object>#: A factory for growth groups. This is an instance of GrowthGroupFactory whose documentation provides more details.

class sage.rings.asymptotic.growth_group.GrowthGroupFactor(cls, base, var, extend_by_non_growth_group)#

Bases: tuple

base#: Alias for field number 1

cls#: Alias for field number 0

extend_by_non_growth_group#: Alias for field number 3

var#: Alias for field number 2

class sage.rings.asymptotic.growth_group.GrowthGroupFactory#

Bases: 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('QQ^x * x^ZZ * y^QQ * QQ^z')
Growth Group QQ^x * x^ZZ * Signs^x * y^QQ * QQ^z * Signs^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: GrowthGroup('QQ^n * n^ZZ')
Growth Group QQ^n * n^ZZ * Signs^n
sage: GrowthGroup('(QQ_+)^n * n^ZZ * UU^n')
Growth Group QQ^n * n^ZZ * UU^n
sage: GrowthGroup('(QQ_+)^n * n^ZZ')
Growth Group QQ^n * n^ZZ

sage: GrowthGroup('n^(ZZ)')
Growth Group n^ZZ
sage: GrowthGroup('n^(ZZ[I])')
Growth Group n^ZZ * n^(ZZ*I)
sage: GrowthGroup('n^(I*ZZ)')
Growth Group n^(ZZ*I)
sage: GrowthGroup('n^(ZZ*I)')
Growth Group n^(ZZ*I)

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

property 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: 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

See also

GenericGrowthGroup

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)

classmethod factory(base, var, extend_by_non_growth_group=False, return_factors=False, **kwds)#

Create a monomial growth group.

INPUT:

base, var, keywords – use in the initialization of the exponential growth group; see MonomialGrowthGroup for details.
extend_by_non_growth_group – a boolean (default False). If set, then the growth group consists of two parts, one part dealing with the absolute values of the bases and one for their arguments.
return_factors – a boolean (default: False). If set, then a tuple of the (cartesian) factors of this growth group is returned.

OUTPUT:

A growth group or tuple of growth groups.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup
sage: from sage.groups.misc_gps.imaginary_groups import ImaginaryGroup
sage: MonomialGrowthGroup.factory(ZZ, 'n')
Growth Group n^ZZ
sage: MonomialGrowthGroup.factory(ImaginaryGroup(ZZ), 'n')
Growth Group n^(ZZ*I)

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

non_growth_group()#

Return a non-growth group (with an imaginary group as base) compatible with this monomial growth group.

OUTPUT:

A group group.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('n^ZZ').non_growth_group()
Growth Group n^(ZZ*I)

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

Bases: 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.MonomialNonGrowthElement(parent, raw_element)#

Bases: GenericNonGrowthElement, MonomialGrowthElement

An element of MonomialNonGrowthGroup.

class sage.rings.asymptotic.growth_group.MonomialNonGrowthGroup(base, var, category)#

Bases: GenericNonGrowthGroup, MonomialGrowthGroup

A growth group whose base is an imaginary group.

EXAMPLES:

sage: from sage.groups.misc_gps.imaginary_groups import ImaginaryGroup
sage: from sage.rings.asymptotic.growth_group import MonomialNonGrowthGroup
sage: J = MonomialNonGrowthGroup(ImaginaryGroup(ZZ), 'n')
sage: J.an_element()
n^I

Element#: alias of MonomialNonGrowthElement

construction()#

Return the construction of this growth group.

OUTPUT:

A pair whose first entry is an MonomialNonGrowthGroupFunctor and its second entry the base.

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: GrowthGroup('x^(QQ*I)').construction()
(MonomialNonGrowthGroup[x], Imaginary Group over Rational Field)

class sage.rings.asymptotic.growth_group.MonomialNonGrowthGroupFunctor(var)#

Bases: MonomialGrowthGroupFunctor

A construction functor for MonomialNonGrowthGroup.

class sage.rings.asymptotic.growth_group.PartialConversionElement(growth_group, raw_element)#

Bases: SageObject

A not converted element of a growth group.

INPUT:

growth_group – a group group
raw_element – an object

A PartialConversionElement is an element growth_group(raw_element) which usually appears in conjunction with PartialConversionValueError. In this case, it was to possible to create that element, although the conversion went partially well in the sense that a \(raw_element`\) (e.g. an exponent for MonomialGrowthElement or a base for ExponentialGrowthElement) could be extracted.

Its main purpose is to carry data used during the creation of elements of cartesian products of growth groups.

is_compatible(other)#: Wrapper to GenericGrowthGroup.is_compatible().

split()#

Split the contained raw_element according to the growth group’s GrowthGroup._split_raw_element_().

EXAMPLES:

sage: from sage.rings.asymptotic.growth_group import ExponentialGrowthGroup, PartialConversionValueError
sage: E = ExponentialGrowthGroup(ZZ, 'x')
sage: try:
....:     E((-2)^x)
....: except PartialConversionValueError as e:
....:     e.element.split()
(2^x, element with parameter -1 (<class 'int'>) in Growth Group ZZ^x)

exception sage.rings.asymptotic.growth_group.PartialConversionValueError(element, *args, **kwds)#

Bases: ValueError

A special ValueError which is raised when (partial) conversion fails.

INPUT:

element – a PartialConversionElement

The remaining argument passed on to ValueError.

class sage.rings.asymptotic.growth_group.Variable(var, repr=None, latex_name=None, ignore=None)#

Bases: CachedRepresentation, 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.

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