Cartesian Products of Growth Groups¶
See (Asymptotic) Growth Groups for a description.
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_cartesian.CartesianProductFactory[source]¶
Bases:
UniqueFactory
Create various types of Cartesian products depending on its input.
INPUT:
growth_groups
– tuple (or other iterable) of growth groupsorder
– (default:None
) if specified, then this order is taken for comparing two Cartesian product elements. Iforder
isNone
this is determined automatically.
Note
The Cartesian product of growth groups is again a growth group. In particular, the resulting structure is partially ordered.
The order on the product is determined as follows:
Cartesian factors with respect to the same variable are ordered lexicographically. This causes
GrowthGroup('x^ZZ * log(x)^ZZ')
andGrowthGroup('log(x)^ZZ * x^ZZ')
to produce two different growth groups.Factors over different variables are equipped with the product order (i.e. the comparison is component-wise).
Also, note that the sets of variables of the Cartesian factors have to be either equal or disjoint.
EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: A = GrowthGroup('x^ZZ'); A Growth Group x^ZZ sage: B = GrowthGroup('log(x)^ZZ'); B Growth Group log(x)^ZZ sage: C = cartesian_product([A, B]); C # indirect doctest Growth Group x^ZZ * log(x)^ZZ sage: C._le_ == C.le_lex True sage: D = GrowthGroup('y^ZZ'); D Growth Group y^ZZ sage: E = cartesian_product([A, D]); E # indirect doctest Growth Group x^ZZ * y^ZZ sage: E._le_ == E.le_product True sage: F = cartesian_product([C, D]); F # indirect doctest Growth Group x^ZZ * log(x)^ZZ * y^ZZ sage: F._le_ == F.le_product True sage: cartesian_product([A, E]); G # indirect doctest Traceback (most recent call last): ... ValueError: The growth groups (Growth Group x^ZZ, Growth Group x^ZZ * y^ZZ) need to have pairwise disjoint or equal variables. sage: cartesian_product([A, B, D]) # indirect doctest Growth Group x^ZZ * log(x)^ZZ * y^ZZ
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> A = GrowthGroup('x^ZZ'); A Growth Group x^ZZ >>> B = GrowthGroup('log(x)^ZZ'); B Growth Group log(x)^ZZ >>> C = cartesian_product([A, B]); C # indirect doctest Growth Group x^ZZ * log(x)^ZZ >>> C._le_ == C.le_lex True >>> D = GrowthGroup('y^ZZ'); D Growth Group y^ZZ >>> E = cartesian_product([A, D]); E # indirect doctest Growth Group x^ZZ * y^ZZ >>> E._le_ == E.le_product True >>> F = cartesian_product([C, D]); F # indirect doctest Growth Group x^ZZ * log(x)^ZZ * y^ZZ >>> F._le_ == F.le_product True >>> cartesian_product([A, E]); G # indirect doctest Traceback (most recent call last): ... ValueError: The growth groups (Growth Group x^ZZ, Growth Group x^ZZ * y^ZZ) need to have pairwise disjoint or equal variables. >>> cartesian_product([A, B, D]) # indirect doctest Growth Group x^ZZ * log(x)^ZZ * y^ZZ
- class sage.rings.asymptotic.growth_group_cartesian.GenericProduct(sets, category, **kwds)[source]¶
Bases:
CartesianProductPoset
,GenericGrowthGroup
A Cartesian product of growth groups.
EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: P = GrowthGroup('x^QQ') sage: L = GrowthGroup('log(x)^ZZ') sage: C = cartesian_product([P, L], order='lex'); C # indirect doctest Growth Group x^QQ * log(x)^ZZ sage: C.an_element() x^(1/2)*log(x)
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> P = GrowthGroup('x^QQ') >>> L = GrowthGroup('log(x)^ZZ') >>> C = cartesian_product([P, L], order='lex'); C # indirect doctest Growth Group x^QQ * log(x)^ZZ >>> C.an_element() x^(1/2)*log(x)
sage: Px = GrowthGroup('x^QQ') sage: Lx = GrowthGroup('log(x)^ZZ') sage: Cx = cartesian_product([Px, Lx], order='lex') # indirect doctest sage: Py = GrowthGroup('y^QQ') sage: C = cartesian_product([Cx, Py], order='product'); C # indirect doctest Growth Group x^QQ * log(x)^ZZ * y^QQ sage: C.an_element() x^(1/2)*log(x)*y^(1/2)
>>> from sage.all import * >>> Px = GrowthGroup('x^QQ') >>> Lx = GrowthGroup('log(x)^ZZ') >>> Cx = cartesian_product([Px, Lx], order='lex') # indirect doctest >>> Py = GrowthGroup('y^QQ') >>> C = cartesian_product([Cx, Py], order='product'); C # indirect doctest Growth Group x^QQ * log(x)^ZZ * y^QQ >>> C.an_element() x^(1/2)*log(x)*y^(1/2)
See also
- CartesianProduct = <sage.rings.asymptotic.growth_group_cartesian.CartesianProductFactory object>[source]¶
- class Element[source]¶
Bases:
Element
- exp()[source]¶
The exponential of this element.
OUTPUT: a growth element
EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: G = GrowthGroup('x^ZZ * log(x)^ZZ * log(log(x))^ZZ') sage: x = G('x') sage: exp(log(x)) x sage: exp(log(log(x))) log(x)
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> G = GrowthGroup('x^ZZ * log(x)^ZZ * log(log(x))^ZZ') >>> x = G('x') >>> exp(log(x)) x >>> exp(log(log(x))) log(x)
sage: exp(x) Traceback (most recent call last): ... ArithmeticError: Cannot construct e^x in Growth Group x^ZZ * log(x)^ZZ * log(log(x))^ZZ > *previous* TypeError: unsupported operand parent(s) for *: 'Growth Group x^ZZ * log(x)^ZZ * log(log(x))^ZZ' and 'Growth Group (e^x)^ZZ'
>>> from sage.all import * >>> exp(x) Traceback (most recent call last): ... ArithmeticError: Cannot construct e^x in Growth Group x^ZZ * log(x)^ZZ * log(log(x))^ZZ > *previous* TypeError: unsupported operand parent(s) for *: 'Growth Group x^ZZ * log(x)^ZZ * log(log(x))^ZZ' and 'Growth Group (e^x)^ZZ'
- factors()[source]¶
Return the atomic factors of this growth element. An atomic factor cannot be split further and is not the identity (\(1\)).
OUTPUT: a tuple of growth elements
EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: G = GrowthGroup('x^ZZ * log(x)^ZZ * y^ZZ') sage: x, y = G.gens_monomial() sage: x.factors() (x,) sage: f = (x * y).factors(); f (x, y) sage: tuple(factor.parent() for factor in f) (Growth Group x^ZZ, Growth Group y^ZZ) sage: f = (x * log(x)).factors(); f (x, log(x)) sage: tuple(factor.parent() for factor in f) (Growth Group x^ZZ, Growth Group log(x)^ZZ)
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> G = GrowthGroup('x^ZZ * log(x)^ZZ * y^ZZ') >>> x, y = G.gens_monomial() >>> x.factors() (x,) >>> f = (x * y).factors(); f (x, y) >>> tuple(factor.parent() for factor in f) (Growth Group x^ZZ, Growth Group y^ZZ) >>> f = (x * log(x)).factors(); f (x, log(x)) >>> tuple(factor.parent() for factor in f) (Growth Group x^ZZ, Growth Group log(x)^ZZ)
sage: G = GrowthGroup('x^ZZ * log(x)^ZZ * log(log(x))^ZZ * y^QQ') sage: x, y = G.gens_monomial() sage: f = (x * log(x) * y).factors(); f (x, log(x), y) sage: tuple(factor.parent() for factor in f) (Growth Group x^ZZ, Growth Group log(x)^ZZ, Growth Group y^QQ)
>>> from sage.all import * >>> G = GrowthGroup('x^ZZ * log(x)^ZZ * log(log(x))^ZZ * y^QQ') >>> x, y = G.gens_monomial() >>> f = (x * log(x) * y).factors(); f (x, log(x), y) >>> tuple(factor.parent() for factor in f) (Growth Group x^ZZ, Growth Group log(x)^ZZ, Growth Group y^QQ)
sage: G.one().factors() ()
>>> from sage.all import * >>> G.one().factors() ()
- is_lt_one()[source]¶
Return whether this element is less than \(1\).
OUTPUT: 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
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> G = GrowthGroup('x^ZZ'); x = G(x) >>> (x**Integer(42)).is_lt_one() # indirect doctest False >>> (x**(-Integer(42))).is_lt_one() # indirect doctest True
- log(base=None)[source]¶
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.
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> G = GrowthGroup('x^ZZ * log(x)^ZZ') >>> x, = G.gens_monomial() >>> log(x) # indirect doctest log(x) >>> log(x**Integer(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
>>> from sage.all import * >>> G = GrowthGroup('(QQ_+)^x * x^ZZ') >>> x, = G.gens_monomial() >>> el = x.rpow(Integer(2)); el 2^x >>> 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. >>> log(el, base=Integer(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.
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GenericGrowthGroup >>> x = GenericGrowthGroup(ZZ).an_element() >>> 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.
>>> from sage.all import * >>> x = GrowthGroup('x^ZZ').an_element() >>> 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)[source]¶
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
– 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)))
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> G = GrowthGroup('(QQ_+)^x * x^ZZ * log(x)^ZZ * y^ZZ * log(y)^ZZ') >>> x, y = G.gens_monomial() >>> (x * y).log_factor() # indirect doctest ((log(x), 1), (log(y), 1)) >>> (x**Integer(123)).log_factor() # indirect doctest ((log(x), 123),) >>> (G('2^x') * x**Integer(2)).log_factor(base=Integer(2)) # indirect doctest ((x, 1), (log(x), 2/log(2)))
sage: G(1).log_factor() ()
>>> from sage.all import * >>> G(Integer(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.
>>> from sage.all import * >>> 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)[source]¶
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
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> G = GrowthGroup('(QQ_+)^x * x^ZZ') >>> x = G('x') >>> x.rpow(Integer(2)) # indirect doctest 2^x >>> x.rpow(Integer(1)/Integer(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)'
>>> from sage.all import * >>> x.rpow(Integer(0)) # indirect doctest Traceback (most recent call last): ... ValueError: 0 is not an allowed base for calculating the power to x. >>> (x**Integer(2)).rpow(Integer(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))
>>> from sage.all import * >>> G = GrowthGroup('QQ^(x*log(x)) * x^ZZ * log(x)^ZZ') >>> x = G('x') >>> (x * log(x)).rpow(Integer(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
>>> from sage.all import * >>> n = GrowthGroup('(QQ_+)^n * n^QQ')('n') >>> n.rpow(Integer(2)) 2^n >>> _.parent() Growth Group QQ^n * n^QQ
sage: n = GrowthGroup('QQ^n * n^QQ')('n') sage: n.rpow(-2) 2^n*(-1)^n
>>> from sage.all import * >>> n = GrowthGroup('QQ^n * n^QQ')('n') >>> n.rpow(-Integer(2)) 2^n*(-1)^n
- variable_names()[source]¶
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('QQ^m * m^QQ * log(n)^ZZ') sage: G('2^m * m^4 * log(n)').variable_names() ('m', 'n') sage: G('2^m * m^4').variable_names() ('m',) sage: G('log(n)').variable_names() ('n',) sage: G('m^3').variable_names() ('m',) sage: G('m^0').variable_names() ()
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> G = GrowthGroup('QQ^m * m^QQ * log(n)^ZZ') >>> G('2^m * m^4 * log(n)').variable_names() ('m', 'n') >>> G('2^m * m^4').variable_names() ('m',) >>> G('log(n)').variable_names() ('n',) >>> G('m^3').variable_names() ('m',) >>> G('m^0').variable_names() ()
- cartesian_injection(factor, element)[source]¶
Inject the given element into this Cartesian product at the given factor.
INPUT:
factor
– a growth group (a factor of this Cartesian product)element
– an element offactor
OUTPUT: an element of this Cartesian product
- gens_monomial()[source]¶
Return a tuple containing monomial generators of this growth group.
OUTPUT: a tuple containing elements of this growth group
Note
This method calls the
gens_monomial()
method on the individual factors of this Cartesian product and concatenates the respective outputs.EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: G = GrowthGroup('x^ZZ * log(x)^ZZ * y^QQ * log(z)^ZZ') sage: G.gens_monomial() (x, y)
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> G = GrowthGroup('x^ZZ * log(x)^ZZ * y^QQ * log(z)^ZZ') >>> G.gens_monomial() (x, y)
- some_elements()[source]¶
Return some elements of this Cartesian product of growth groups.
See
TestSuite
for a typical use case.OUTPUT: an iterator
EXAMPLES:
sage: from itertools import islice sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: G = GrowthGroup('(QQ_+)^y * x^QQ * log(x)^ZZ') sage: tuple(islice(G.some_elements(), 10r)) (x^(1/2)*(1/2)^y, x^(-1/2)*log(x)*2^y, x^2*log(x)^(-1), x^(-2)*log(x)^2*42^y, log(x)^(-2)*(2/3)^y, x*log(x)^3*(3/2)^y, x^(-1)*log(x)^(-3)*(4/5)^y, x^42*log(x)^4*(5/4)^y, x^(2/3)*log(x)^(-4)*(6/7)^y, x^(-2/3)*log(x)^5*(7/6)^y)
>>> from sage.all import * >>> from itertools import islice >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> G = GrowthGroup('(QQ_+)^y * x^QQ * log(x)^ZZ') >>> tuple(islice(G.some_elements(), 10)) (x^(1/2)*(1/2)^y, x^(-1/2)*log(x)*2^y, x^2*log(x)^(-1), x^(-2)*log(x)^2*42^y, log(x)^(-2)*(2/3)^y, x*log(x)^3*(3/2)^y, x^(-1)*log(x)^(-3)*(4/5)^y, x^42*log(x)^4*(5/4)^y, x^(2/3)*log(x)^(-4)*(6/7)^y, x^(-2/3)*log(x)^5*(7/6)^y)
- variable_names()[source]¶
Return the names of the variables.
OUTPUT: a tuple of strings
EXAMPLES:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: GrowthGroup('x^ZZ * log(x)^ZZ * y^QQ * log(z)^ZZ').variable_names() ('x', 'y', 'z')
>>> from sage.all import * >>> from sage.rings.asymptotic.growth_group import GrowthGroup >>> GrowthGroup('x^ZZ * log(x)^ZZ * y^QQ * log(z)^ZZ').variable_names() ('x', 'y', 'z')
- class sage.rings.asymptotic.growth_group_cartesian.MultivariateProduct(sets, category, **kwargs)[source]¶
Bases:
GenericProduct
A Cartesian product of growth groups with pairwise disjoint (or equal) variable sets.
Note
A multivariate product of growth groups is ordered by means of the product order, i.e. component-wise. This is motivated by the assumption that different variables are considered to be independent (e.g.
x^ZZ * y^ZZ
).See also
- class sage.rings.asymptotic.growth_group_cartesian.UnivariateProduct(sets, category, **kwargs)[source]¶
Bases:
GenericProduct
A Cartesian product of growth groups with the same variables.
Note
A univariate product of growth groups is ordered lexicographically. This is motivated by the assumption that univariate growth groups can be ordered in a chain with respect to the growth they model (e.g.
x^ZZ * log(x)^ZZ
: polynomial growth dominates logarithmic growth).See also