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 24644N26.
 Benjamin Hackl is supported by the Google Summer of Code 2015.
Classes and Methods¶

class
sage.rings.asymptotic.growth_group_cartesian.
CartesianProductFactory
¶ Bases:
sage.structure.factory.UniqueFactory
Create various types of Cartesian products depending on its input.
INPUT:
growth_groups
– a tuple (or other iterable) of growth groups.order
– (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 componentwise).
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

create_key_and_extra_args
(growth_groups, category, **kwds)¶ Given the arguments and keywords, create a key that uniquely determines this object.

create_object
(version, args, **kwds)¶ Create an object from the given arguments.

class
sage.rings.asymptotic.growth_group_cartesian.
GenericProduct
(sets, category, **kwds)¶ Bases:
sage.combinat.posets.cartesian_product.CartesianProductPoset
,sage.rings.asymptotic.growth_group.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)
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)
See also

class
Element
¶ Bases:
sage.combinat.posets.cartesian_product.CartesianProductPoset.Element

exp
()¶ The exponential of this element.
INPUT:
Nothing.
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)
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'

factors
()¶ Return the atomic factors of this growth element. An atomic factor cannot be split further and is not the identity (\(1\)).
INPUT:
Nothing.
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)
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)
sage: G.one().factors() ()

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


cartesian_injection
(factor, element)¶ 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
()¶ Return a tuple containing monomial generators of this growth group.
INPUT:
Nothing.
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)

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

variable_names
()¶ 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')

class

class
sage.rings.asymptotic.growth_group_cartesian.
MultivariateProduct
(sets, category, **kwargs)¶ Bases:
sage.rings.asymptotic.growth_group_cartesian.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. componentwise. 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)¶ Bases:
sage.rings.asymptotic.growth_group_cartesian.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