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 groups

  • order – (default: None) if specified, then this order is taken for comparing two Cartesian product elements. If order is None 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') and GrowthGroup('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
create_key_and_extra_args(growth_groups, category, **kwds)[source]

Given the arguments and keywords, create a key that uniquely determines this object.

create_object(version, args, **kwds)[source]

Create an object from the given arguments.

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, CartesianProductPoset.

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

>>> 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. If None (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 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)))

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

See also

factors(), log().

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 of factor

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

UnivariateProduct, GenericProduct.

CartesianProduct = <sage.rings.asymptotic.growth_group_cartesian.CartesianProductFactory object>[source]
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

MultivariateProduct, GenericProduct.

CartesianProduct = <sage.rings.asymptotic.growth_group_cartesian.CartesianProductFactory object>[source]