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.
Warning
As this code is experimental, warnings are thrown when a growth
group is created for the first time in a session (see
sage.misc.superseded.experimental
).
TESTS:
sage: from sage.rings.asymptotic.growth_group import GenericGrowthGroup, GrowthGroup
sage: GenericGrowthGroup(ZZ)
doctest:...: FutureWarning: This class/method/function is marked as
experimental. It, its functionality or its interface might change
without a formal deprecation.
See http://trac.sagemath.org/17601 for details.
Growth Group Generic(ZZ)
TESTS:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup
sage: A = GrowthGroup('QQ^x * x^ZZ'); A
Growth Group QQ^x * x^ZZ
sage: A.construction()
(The cartesian_product functorial construction,
(Growth Group QQ^x, Growth Group x^ZZ))
sage: A.construction()[1][0].construction()
(ExponentialGrowthGroup[x], Rational Field)
sage: A.construction()[1][1].construction()
(MonomialGrowthGroup[x], Integer Ring)
sage: B = GrowthGroup('x^ZZ * y^ZZ'); B
Growth Group x^ZZ * y^ZZ
sage: B.construction()
(The cartesian_product functorial construction,
(Growth Group x^ZZ, Growth Group y^ZZ))
sage: C = GrowthGroup('x^ZZ * log(x)^ZZ * y^ZZ'); C
Growth Group x^ZZ * log(x)^ZZ * y^ZZ
sage: C.construction()
(The cartesian_product functorial construction,
(Growth Group x^ZZ * log(x)^ZZ, Growth Group y^ZZ))
sage: C.construction()[1][0].construction()
(The cartesian_product functorial construction,
(Growth Group x^ZZ, Growth Group log(x)^ZZ))
sage: C.construction()[1][1].construction()
(MonomialGrowthGroup[y], Integer Ring)
sage: cm = sage.structure.element.get_coercion_model()
sage: D = GrowthGroup('QQ^x * x^QQ')
sage: cm.common_parent(A, D)
Growth Group QQ^x * x^QQ
sage: E = GrowthGroup('ZZ^x * x^QQ')
sage: cm.record_exceptions() # not tested, see #19411
sage: cm.common_parent(A, E)
Growth Group QQ^x * x^QQ
sage: for t in cm.exception_stack(): # not tested, see #19411
....: print(t)
sage: A.an_element()
(1/2)^x*x
sage: tuple(E.an_element())
(1, x^(1/2))
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
TESTS:
sage: from sage.rings.asymptotic.growth_group_cartesian import CartesianProductFactory sage: CartesianProductFactory('factory')([A, B], category=Groups() & Posets()) Growth Group x^ZZ * log(x)^ZZ sage: CartesianProductFactory('factory')([], category=Sets()) Traceback (most recent call last): ... TypeError: Cannot create Cartesian product without factors.
-
create_key_and_extra_args
(growth_groups, category, **kwds)¶ Given the arguments and keywords, create a key that uniquely determines this object.
TESTS:
sage: from sage.rings.asymptotic.growth_group_cartesian import CartesianProductFactory sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: A = GrowthGroup('x^ZZ') sage: CartesianProductFactory('factory').create_key_and_extra_args( ....: [A], category=Sets(), order='blub') (((Growth Group x^ZZ,), Category of sets), {'order': 'blub'})
-
create_object
(version, args, **kwds)¶ Create an object from the given arguments.
TESTS:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: cartesian_product([GrowthGroup('x^ZZ')]) # indirect doctest Growth Group x^ZZ
-
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'
TESTS:
sage: E = GrowthGroup("(e^y)^QQ * y^QQ * log(y)^QQ") sage: y = E('y') sage: log(exp(y)) y sage: exp(log(y)) y
-
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.
TESTS:
sage: G = GrowthGroup("(e^x)^QQ * x^ZZ") sage: x, = G.gens_monomial() sage: log(exp(x)) # indirect doctest x sage: G.one().log() # indirect doctest Traceback (most recent call last): ... ArithmeticError: log(1) is zero, which is not contained in Growth Group (e^x)^QQ * x^ZZ.
sage: G = GrowthGroup("(e^x)^ZZ * x^ZZ") sage: x, = G.gens_monomial() sage: log(exp(x)) # indirect doctest x sage: G.one().log() # indirect doctest Traceback (most recent call last): ... ArithmeticError: log(1) is zero, which is not contained in Growth Group (e^x)^ZZ * x^ZZ.
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() # indirect doctest Traceback (most recent call last): ... ArithmeticError: Calculating log(x*y) results in a sum, which is not contained in Growth Group QQ^x * x^ZZ * log(x)^ZZ * y^ZZ * log(y)^ZZ.
-
log_factor
(base=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.
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.
TESTS:
sage: G = GrowthGroup("(e^x)^ZZ * x^ZZ * log(x)^ZZ") sage: x, = G.gens_monomial() sage: (exp(x) * x).log_factor() # indirect doctest ((x, 1), (log(x), 1))
-
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
-
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() ()
-
-
GenericProduct.
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.
TESTS:
sage: from sage.rings.asymptotic.growth_group import GrowthGroup sage: G = GrowthGroup('x^ZZ * y^QQ') sage: G.cartesian_injection(G.cartesian_factors()[1], 'y^7') y^7
-
GenericProduct.
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)
TESTS:
sage: all(g.parent() == G for g in G.gens_monomial()) True
-
GenericProduct.
some_elements
()¶ Return some elements of this Cartesian product of growth groups.
See
TestSuite
for a typical use case.INPUT:
Nothing.
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(), 10)) (x^(1/2)*(1/2)^y, x^(-1/2)*log(x)*(-1/2)^y, x^2*log(x)^(-1)*2^y, x^(-2)*log(x)^2*(-2)^y, log(x)^(-2), x*log(x)^3*(-1)^y, x^(-1)*log(x)^(-3)*42^y, x^42*log(x)^4*(2/3)^y, x^(2/3)*log(x)^(-4)*(-2/3)^y, x^(-2/3)*log(x)^5*(3/2)^y)
-
GenericProduct.
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