(Asymptotic) Growth Groups¶
This module provides support for (asymptotic) growth groups.
Such groups are equipped with a partial order: the elements can be seen as functions, and the behavior as their argument (or arguments) gets large (tend to \(\infty\)) is compared.
Growth groups are used for the calculations done in the asymptotic ring. There, take a look at the informal definition, where examples of growth groups and elements are given as well.
Description of Growth Groups¶
Many growth groups can be described by a string, which can also be used to
create them. For example, the string 'x^QQ * log(x)^ZZ * QQ^y * y^QQ'
represents a growth group with the following properties:
It is a growth group in the two variables \(x\) and \(y\).
Its elements are of the form
\[x^r \cdot \log(x)^s \cdot a^y \cdot y^q\]for \(r\in\QQ\), \(s\in\ZZ\), \(a\in\QQ\) and \(q\in\QQ\).
The order is with respect to \(x\to\infty\) and \(y\to\infty\) independently of each other.
To compare such elements, they are split into parts belonging to only one variable. In the example above,
\[x^{r_1} \cdot \log(x)^{s_1} \leq x^{r_2} \cdot \log(x)^{s_2}\]if \((r_1, s_1) \leq (r_2, s_2)\) lexicographically. This reflects the fact that elements \(x^r\) are larger than elements \(\log(x)^s\) as \(x\to\infty\). The factors belonging to the variable \(y\) are compared analogously.
The results of these comparisons are then put together using the product order, i.e., \(\leq\) if each component satisfies \(\leq\).
Each description string consists of ordered factors—yes, this means
*
is noncommutative—of strings describing “elementary” growth
groups (see the examples below). As stated in the example above, these
factors are split by their variable; factors with the same variable are
grouped. Reading such factors from left to right determines the order:
Comparing elements of two factors (growth groups) \(L\) and \(R\), then all
elements of \(L\) are considered to be larger than each element of \(R\).
Creating a Growth Group¶
For many purposes the factory GrowthGroup
(see
GrowthGroupFactory
) is the most convenient way to generate a
growth group.
sage: from sage.rings.asymptotic.growth_group import GrowthGroup
Here are some examples:
sage: GrowthGroup('z^ZZ')
Growth Group z^ZZ
sage: M = GrowthGroup('z^QQ'); M
Growth Group z^QQ
Each of these two generated groups is a MonomialGrowthGroup
,
whose elements are powers of a fixed symbol (above 'z'
).
For the order of the elements it is assumed that \(z\to\infty\).
Note
Growth groups where the variable tend to some value distinct from \(\infty\) are not yet implemented.
To create elements of \(M\), a generator can be used:
sage: z = M.gen()
sage: z^(3/5)
z^(3/5)
Strings can also be parsed:
sage: M('z^7')
z^7
Similarly, we can construct logarithmic factors by:
sage: GrowthGroup('log(z)^QQ')
Growth Group log(z)^QQ
which again creates a
MonomialGrowthGroup
. An ExponentialGrowthGroup
is generated in the same way. Our factory gives
sage: E = GrowthGroup('(QQ_+)^z'); E
Growth Group QQ^z
and a typical element looks like this:
sage: E.an_element()
(1/2)^z
More complex groups are created in a similar fashion. For example
sage: C = GrowthGroup('(QQ_+)^z * z^QQ * log(z)^QQ'); C
Growth Group QQ^z * z^QQ * log(z)^QQ
This contains elements of the form
sage: C.an_element()
(1/2)^z*z^(1/2)*log(z)^(1/2)
The group \(C\) itself is a Cartesian product; to be precise a
UnivariateProduct
. We
can see its factors:
sage: C.cartesian_factors()
(Growth Group QQ^z, Growth Group z^QQ, Growth Group log(z)^QQ)
Multivariate constructions are also possible:
sage: GrowthGroup('x^QQ * y^QQ')
Growth Group x^QQ * y^QQ
This gives a
MultivariateProduct
.
Both these Cartesian products are derived from the class
GenericProduct
. Moreover
all growth groups have the abstract base class
GenericGrowthGroup
in common.
Some Examples¶
sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: G_x = GrowthGroup('x^ZZ'); G_x
Growth Group x^ZZ
sage: G_xy = GrowthGroup('x^ZZ * y^ZZ'); G_xy
Growth Group x^ZZ * y^ZZ
sage: G_xy.an_element()
x*y
sage: x = G_xy('x'); y = G_xy('y')
sage: x^2
x^2
sage: elem = x^21*y^21; elem^2
x^42*y^42
A monomial growth group itself is totally ordered, all elements are comparable. However, this does not hold for Cartesian products:
sage: e1 = x^2*y; e2 = x*y^2
sage: e1 <= e2 or e2 <= e1
False
In terms of uniqueness, we have the following behaviour:
sage: GrowthGroup('x^ZZ * y^ZZ') is GrowthGroup('y^ZZ * x^ZZ')
True
The above is True
since the order of the factors does not play a role here; they use different variables. But when using the same variable, it plays a role:
sage: GrowthGroup('x^ZZ * log(x)^ZZ') is GrowthGroup('log(x)^ZZ * x^ZZ')
False
In this case the components are ordered lexicographically, which
means that in the second growth group, log(x)
is assumed to
grow faster than x
(which is nonsense, mathematically). See
CartesianProduct
for more details or see above
for a more extensive description.
Short notation also allows the construction of more complicated growth groups:
sage: G = GrowthGroup('(QQ_+)^x * x^ZZ * log(x)^QQ * y^QQ')
sage: G.an_element()
(1/2)^x*x*log(x)^(1/2)*y^(1/2)
sage: x, y = var('x y')
sage: G(2^x * log(x) * y^(1/2)) * G(x^(-5) * 5^x * y^(1/3))
10^x*x^(-5)*log(x)*y^(5/6)
AUTHORS:
Benjamin Hackl (2015)
Daniel Krenn (2015)
Clemens Heuberger (2016)
ACKNOWLEDGEMENT:
Benjamin Hackl, Clemens Heuberger and Daniel Krenn are supported by the Austrian Science Fund (FWF): P 24644-N26.
Benjamin Hackl is supported by the Google Summer of Code 2015.
Classes and Methods¶
- class sage.rings.asymptotic.growth_group.AbstractGrowthGroupFunctor(var, domain)¶
Bases:
sage.categories.pushout.ConstructionFunctor
A base class for the functors constructing growth groups.
INPUT:
var
– a string or list of strings (or anything elseVariable
accepts).domain
– a category.
EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: GrowthGroup('z^QQ').construction()[0] # indirect doctest MonomialGrowthGroup[z]
See also
Asymptotic Ring,
ExponentialGrowthGroupFunctor
,MonomialGrowthGroupFunctor
,sage.rings.asymptotic.asymptotic_ring.AsymptoticRingFunctor
,sage.categories.pushout.ConstructionFunctor
.- merge(other)¶
Merge this functor with
other
of possible.INPUT:
other
– a functor.
OUTPUT:
A functor or
None
.EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: F = GrowthGroup('(QQ_+)^t').construction()[0] sage: G = GrowthGroup('t^QQ').construction()[0] sage: F.merge(F) ExponentialGrowthGroup[t] sage: F.merge(G) is None True
- class sage.rings.asymptotic.growth_group.ExponentialGrowthElement(parent, raw_element)¶
Bases:
sage.rings.asymptotic.growth_group.GenericGrowthElement
An implementation of exponential growth elements.
INPUT:
parent
– anExponentialGrowthGroup
.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)¶
Bases:
sage.rings.asymptotic.growth_group.GenericGrowthGroup
A growth group dealing with expressions involving a fixed variable/symbol as the exponent.
The elements
ExponentialGrowthElement
of this group represent exponential functions with bases from a fixed base ring; the group law is the multiplication.INPUT:
base
– one of SageMath’s parents, out of which the elements get their data (raw_element
).As exponential expressions are represented by this group, the elements in
base
are the bases of these exponentials.var
– an object.The string representation of
var
acts as an exponent of the elements represented by this group.category
– (default:None
) the category of the newly created growth group. It has to be a subcategory ofJoin of Category of groups and Category of posets
. This is also the default category ifNone
is specified.
EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import ExponentialGrowthGroup sage: P = ExponentialGrowthGroup(QQ, 'x'); P Growth Group QQ^x
See also
- DivisionRings¶
- Element¶
alias of
ExponentialGrowthElement
- Groups¶
alias of
sage.categories.groups.Groups
- Magmas¶
alias of
sage.categories.magmas.Magmas
- Posets¶
alias of
sage.categories.posets.Posets
- Sets¶
alias of
sage.categories.sets_cat.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; seeExponentialGrowthGroup
for details.extend_by_non_growth_group
– a boolean (defaultTrue
). 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:
sage.rings.asymptotic.growth_group.AbstractGrowthGroupFunctor
A
construction functor
forexponential growth groups
.INPUT:
var
– a string or list of strings (or anything elseVariable
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:
sage.rings.asymptotic.growth_group.GenericNonGrowthElement
,sage.rings.asymptotic.growth_group.ExponentialGrowthElement
An element of
ExponentialNonGrowthGroup
.
- class sage.rings.asymptotic.growth_group.ExponentialNonGrowthGroup(base, *args, **kwds)¶
Bases:
sage.rings.asymptotic.growth_group.GenericNonGrowthGroup
,sage.rings.asymptotic.growth_group.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:
sage.rings.asymptotic.growth_group.ExponentialGrowthGroupFunctor
- class sage.rings.asymptotic.growth_group.GenericGrowthElement(parent, raw_element)¶
Bases:
sage.structure.element.MultiplicativeGroupElement
A basic implementation of a generic growth element.
Growth elements form a group by multiplication, and (some of) the elements can be compared to each other, i.e., all elements form a poset.
INPUT:
parent
– aGenericGrowthGroup
.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. IfNone
(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. IfNone
(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 usuallog
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)¶
Bases:
sage.structure.unique_representation.UniqueRepresentation
,sage.structure.parent.Parent
,sage.rings.asymptotic.misc.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 ofJoin of Category of groups and Category of posets
. This is also the default category ifNone
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)
See also
- AdditiveMagmas¶
- Element¶
alias of
GenericGrowthElement
- Magmas¶
alias of
sage.categories.magmas.Magmas
- Posets¶
alias of
sage.categories.posets.Posets
- Sets¶
alias of
sage.categories.sets_cat.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
hasx
as a monomial generator, whilelog(x)^ZZ
oricecream(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 ofright
.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:
sage.rings.asymptotic.growth_group.GenericGrowthElement
An element of
GenericNonGrowthGroup
.
- class sage.rings.asymptotic.growth_group.GenericNonGrowthGroup(base, var, category)¶
Bases:
sage.rings.asymptotic.growth_group.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¶
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:
sage.structure.factory.UniqueFactory
A factory creating asymptotic growth groups.
INPUT:
specification
– a string.keyword arguments are passed on to the growth group constructor. If the keyword
ignore_variables
is not specified, thenignore_variables=('e',)
(to ignoree
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:
sage.rings.asymptotic.growth_group.GenericGrowthElement
An implementation of monomial growth elements.
INPUT:
parent
– aMonomialGrowthGroup
.raw_element
– an element from the base ring of the parent.This
raw_element
is the exponent of the created monomial growth element.
A monomial growth element represents a term of the type \(\operatorname{variable}^{\operatorname{exponent}}\). The multiplication corresponds to the addition of the exponents.
EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup sage: P = MonomialGrowthGroup(ZZ, 'x') sage: e1 = P(1); e1 1 sage: e2 = P(raw_element=2); e2 x^2 sage: e1 == e2 False sage: P.le(e1, e2) True sage: P.le(e1, P.gen()) and P.le(P.gen(), e2) True
- exponent¶
The exponent of this growth element.
EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: P = GrowthGroup('x^ZZ') sage: P(x^42).exponent 42
- class sage.rings.asymptotic.growth_group.MonomialGrowthGroup(base, var, category)¶
Bases:
sage.rings.asymptotic.growth_group.GenericGrowthGroup
A growth group dealing with powers of a fixed object/symbol.
The elements
MonomialGrowthElement
of this group represent powers of a fixed base; the group law is the multiplication, which corresponds to the addition of the exponents of the monomials.INPUT:
base
– one of SageMath’s parents, out of which the elements get their data (raw_element
).As monomials are represented by this group, the elements in
base
are the exponents of these monomials.var
– an object.The string representation of
var
acts as a base of the monomials represented by this group.category
– (default:None
) the category of the newly created growth group. It has to be a subcategory ofJoin of Category of groups and Category of posets
. This is also the default category ifNone
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
- AdditiveMagmas¶
- Element¶
alias of
MonomialGrowthElement
- Magmas¶
alias of
sage.categories.magmas.Magmas
- Posets¶
alias of
sage.categories.posets.Posets
- Sets¶
alias of
sage.categories.sets_cat.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; seeMonomialGrowthGroup
for details.extend_by_non_growth_group
– a boolean (defaultFalse
). 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, whilelog(x)^ZZ
haslog(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
hasx
as a monomial generator, whilelog(x)^ZZ
oricecream(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)¶
Bases:
sage.rings.asymptotic.growth_group.AbstractGrowthGroupFunctor
A
construction functor
formonomial growth groups
.INPUT:
var
– a string or list of strings (or anything elseVariable
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:
sage.rings.asymptotic.growth_group.GenericNonGrowthElement
,sage.rings.asymptotic.growth_group.MonomialGrowthElement
An element of
MonomialNonGrowthGroup
.
- class sage.rings.asymptotic.growth_group.MonomialNonGrowthGroup(base, var, category)¶
Bases:
sage.rings.asymptotic.growth_group.GenericNonGrowthGroup
,sage.rings.asymptotic.growth_group.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:
sage.rings.asymptotic.growth_group.MonomialGrowthGroupFunctor
- class sage.rings.asymptotic.growth_group.PartialConversionElement(growth_group, raw_element)¶
Bases:
sage.structure.sage_object.SageObject
A not converted element of a growth group.
INPUT:
growth_group
– a group groupraw_element
– an object
A
PartialConversionElement
is an elementgrowth_group(raw_element)
which usually appears in conjunction withPartialConversionValueError
. 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 forMonomialGrowthElement
or a base forExponentialGrowthElement
) 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’sGrowthGroup._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 (<type '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
– aPartialConversionElement
The remaining argument passed on to ValueError.
- class sage.rings.asymptotic.growth_group.Variable(var, repr=None, latex_name=None, ignore=None)¶
Bases:
sage.structure.unique_representation.CachedRepresentation
,sage.structure.sage_object.SageObject
A class managing the variable of a growth group.
INPUT:
var
– an object whose representation string is used as the variable. It has to be a valid Python identifier.var
can also be a tuple (or other iterable) of such objects.repr
– (default:None
) if specified, then this string will be displayed instead ofvar
. 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 ofvar
.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',)