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