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

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:

The remaining arguments are passed on to ValueError.

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

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
Element
Groups
Magmas
Posets
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)

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

An element of ExponentialNonGrowthGroup.

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

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

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.


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)

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)

Element

alias of GenericGrowthElement

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

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)

An element of GenericNonGrowthGroup.

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

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

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

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)

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

Element

alias of MonomialGrowthElement

Magmas
Posets
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

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.

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)

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

An element of MonomialNonGrowthGroup.

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

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
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)
class sage.rings.asymptotic.growth_group.PartialConversionElement(growth_group, raw_element)

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:

The remaining argument passed on to ValueError.

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.

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