AsymptoticTerm

[behackl]

Asymptotic terms are expressions like O(n²), 7 * n * 2ⁿ, or 42 * n * log(n). They build upon the asymptotic growth elements from #17600, which are elements like n², n*2ⁿ and n * log(n) (that is, they handle only the asymptotic growth).

All asymptotic terms have an attribute 'growth' (which is some growth element), and then they may have additional information (like, for example, a coefficient in the case of exact terms).

Currently, we implemented the following asymptotic terms (plus their monoid parents):

GenericTerm

Implements the base structure of asymptotic terms.

OTerm

Class for big O terms. These terms may "absorb" other asymptotic terms with weaker or equal growth.

TermWithCoefficient

Generic base class for asymptotic terms with coefficient. Base class for asymptotic exact terms and asymptotic L terms.

ExactTerm

Class for asymptotic exact terms. These terms correspond to symbolic expressions like, for example, 2 * x³, 7 * x^-2/5, or 42 * x^1/3 * log(x).

Asymptotic terms may be multiplied and absorbed; addition will be handled by AsymptoticExpression.

See meta-ticket #17601 for the planned structure.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​016db34	added the copyright header.
​feadcae	fixed author date in copyright header.
​92b1720	fixed coercion error: coercion happens now only when bases coerce into
​a4e5018	initial commit: structure fixed, coercion implemented
​2a92578	fixed some minor documentation issues
​49db4b8	implemented absorption for OTerm and ExactTerm, and multiplication for LTermGeneric
​7d96970	coefficient 0 is not allowed
​eacb0e9	_le_ for TermWithCoefficient
​0d8b99a	can_absorb always returns a boolean
​7ef7cb4	improved documentation

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0a603f3	import have_same_parent from sage.structure.element instead of .sage_object
​1eef695	merge fix of import deprecation (have_same_parent) for asy/growthElement into asy/asymptoticTerm
​eb4c8af	import have_same_parent from sage.structure.element

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​4e80522	repr: checking for integers with isinstance introduces problems with
​4207fce	a base is valid, if it inherits from Parent
​e48afc9	minor documentation improvements
​73017ab	conversion from multivariate polynomial rings and multivariate power
​167dec3	merge the clean and cross-reviewed version of asy/growthGroup into asy/asymptoticTerm
​ae273d8	fixed doctests due to changes to asy/growthGroup
​ea07028	growth group has to be specified; choice no longer defaults to GenericGrowthGroup.
​8a206a3	replaced most double quotes by single quotes (consistency with asy/growthGroup)
​1ee90ea	improved and simplified documentation (consistency with asy/growthGroup)
​042e9c1	coefficients have to be specified explicitly; no default values.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​2dfe905	added a factory for asymptotic terms
​234945c	adapted import statements (consistency with asy/growthGroup)
​5f513a7	module description added
​cc6a431	_mul_ calls the parent to construct a new element
​414a2c6	simplified documentation of _repr_
​95f98c8	various improvements of the documentation.
​ce7a2a3	reworked the element constructor and added doctests for growth group conversion
​a589d8d	generation of L terms using the factory documented

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a2840b3	fixed can_absorb for generic L terms
​a4d5c5f	_coerce_map_from_ --> has_coerce_map_from in doctests
​ee8272c	fixed conversion from multivariate power series rings; replaced PolynomialRing and PowerSeriesRing in doc by bracket-notation
​fde1604	Merge branch 'asy/growthGroup' into asy/asymptoticTerm
​66e4d4e	can_absorb now calls helper functions _can_absorb_
​c7ef699	implemented the conversion of suitable monomials with coefficient to terms with coefficient
​a5b0ba0	postponed the implementation of L terms after having a minimal working example
​0c8099e	implemented a flag for can_absorb

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​3cbeac3	helper methods for asymptotic expressions added
​676c3d8	fixed a bug with conversion of the variable without powers
​0d7ce6b	adapted representation of exact terms to the representation of

[dkrenn]

Last 10 new commits:

​28dc2a8	moved _can_absorb_ in code directly below can_absorb
​3546ed4	docstring enhancements in GenericTerm
​4f53a8b	improve docstrings of term monoid
​5128036	remove default None from constructor of generic term monoid
​16c407e	simplify code of _coerce_map_from_
​ae361b5	remove else branch and move block to the left (_element_constructor_) to increase readability
​f6799c5	improve docstrings
​f189e1c	some minor code rewritings
​253556f	add an additional doctest
​373dda9	fixed broken doctests

[behackl]

Last 10 new commits:

​a4d5c5f	_coerce_map_from_ --> has_coerce_map_from in doctests
​ee8272c	fixed conversion from multivariate power series rings; replaced PolynomialRing and PowerSeriesRing in doc by bracket-notation
​fde1604	Merge branch 'asy/growthGroup' into asy/asymptoticTerm
​66e4d4e	can_absorb now calls helper functions _can_absorb_
​c7ef699	implemented the conversion of suitable monomials with coefficient to terms with coefficient
​a5b0ba0	postponed the implementation of L terms after having a minimal working example
​0c8099e	implemented a flag for can_absorb
​3cbeac3	helper methods for asymptotic expressions added
​676c3d8	fixed a bug with conversion of the variable without powers
​0d7ce6b	adapted representation of exact terms to the representation of

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​dadef25	_base_ring --> _base_ring_ + property
​65301c7	changed representation string of TermWithCoefficientMonoid and
​710f54f	refactored comparison for TermWithCoefficient and GenericTerm
​5a4b631	fixed some typos
​d73ce3e	added docstring for create_object
​38b8836	specified exceptions caught in _element_constructor_
​172824a	improved doctests: avoided tuple assignments
​aa68142	O term(s) et al --> `O`-terms
​1712037	improved documentation: simplified variable names in doctests
​7f2c584	links repaired and header modified

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​5538893	added @experimental to parents
​9a89bca	Merge branch 'asy/growthGroup' into asy/asymptoticTerm
​e6101a9	added @experimental to the term monoids

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​42b45b8

fixed helper function can_absorb

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​907e82d	docstrings for _repr*_ methods
​6c8b543	changed default representation to short representation
​2903a9a	helper method for short representation implemented
​c916514	implemented a helper method for the growth group factory
​ae0fff3	factory for growth groups implemented
​9c3a08e	Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
​2010268	fixed doctest in can_absorb + improved documentation
​a5fd74d	introduction of short notation for growth groups + factory
​6e9652b	comparison with mul_vararg
​637d4cb	header modified

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​371a53a

representation: 1*x --> x; -1*x --> -x etc.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​655ec12	rename to repr_short_to_parent
​e60a325	rewrite growth group factory
​ea8ae66	repr-option to suppress words "Growth Group"
​b7f5c73	rename repr-option-keyword and minor change in output
​c0ec9fd	minor change in output of repr
​f141775	typos in module description fixed
​62d824f	Merge branch 'asy/growthGroup' into asy/growthGroup-factory
​116ab14	Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
​164e39c	experimental warning: refer to #17601
​7eecfe2	improved representation strings

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​fcf9581

minor simplification for the term factory

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​164d21e	compare exponents directly instead with is_le_one
​baa8f7c	implemented gens_monomial and adapted gen, gens, ngens
​b477c62	merge branch 'asy/growthGroup' into asy/growthGroup-factory and resolve a minor conflict
​c98eaee	Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
​d92d3ec	parsing of log-operands fixed
​3749fa1	refactored handling of generators
​ba16c0f	Merge branch 'asy/growthGroup' into asy/growthGroup-factory
​4616535	Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​c6d8584	error with the element constructor fixed, doctest added
​3564d23	Merge branch 'asy/growthGroup' into asy/growthGroup-factory
​0b53b76	Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm

[dkrenn]

During the project #17601 (the last months in course of GSOC2015 as mentor) I did a very careful reviewing of all code. This includes the code of this ticket. Now this is clearly a positive_review from my side.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​e8662cd	collect asymptotic code in one directory
​c5f0dac	Merge branch 'asy/growthGroup' into asy/growthGroup-factory
​7fba1fe	Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
​7774ff2	fixed doctests
​878ef2a	fixed documentation build
​5fd9662	Merge branch 'asy/growthGroup' into asy/growthGroup-factory
​f20c42e	fixing doctests
​38e73c8	Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
​ae6a9bb	fixed doctests
​79be7d6	documentation builds again

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7b8c1a0

fixed a conversion issue for terms with coefficient

[dkrenn]

Merge 6.9.beta5

---

New commits:

​1c81c12	language oddities fixed
​032d8b8	Merge branch 'asy/growthGroup' into asy/growthGroup-factory
​3a05be7	Merge tag '6.9.beta5' into t/17600/asy/growthGroup
​58f931d	add asymptotic_expansions index
​9d6f2da	Merge branch 't/17600/asy/growthGroup' into t/18930/asy/growthGroup-factory
​6da5ade	Merge branch 't/18930/asy/growthGroup-factory' into t/17715/asy/asymptoticTerm

[cheuberg]

$ ./sage -docbuild -u file=src/sage/rings/asymptotic/term_monoid.py html
...
Error building the documentation.
...
Traceback (most recent call last):
...
OSError: [html     ] /home/sci/cheuberg/.sage/docbuild/term_monoid/source/term_monoid.py:docstring of term_monoid.OTermMonoid._coerce_map_from_:33: WARNING: Inline interpreted text or phrase reference start-string without end-string.

[behackl]

Fixed the docbuild-issue, made some small documentation-related changes, and merged the latest version of #18930 into this branch. Back to needs_review.

---

Last 10 new commits:

​3f88a9a	duplicate doctest removed
​9489bad	element_constructor: input clarification; doctests marked as indirect
​053ee33	type(...) == ... --> isinstance(...)
​7b49489	clarification gens vs. gens_monomial
​2bf6868	prevent strange NotImplementedError from PowerSeriesRing
​4f99031	Merge branch 'asy/growthGroup' into asy/growthGroup-factory
​7c3f6b8	Merge branch 'asy/growthGroup-factory' into asy/asymptoticTerm
​6f251fd	fixed typo
​dfb8d41	fixed formatting issue
​cc55be7	fixed indentation of one block

[cheuberg]

I reviewed this ticket, added a few reviewer commits and have a few comments:

• absorption: One-Sentence-Description should describe what this function does. What happens if the elements are not comparable (documentation; probably only possible in a follow-up ticket)?
• can_absorb: One-Sentence-Description, then NOTE section would be superfluous.
• GenericTerm.__init__: Provide doctests for error conditions
• GenericTerm.can_absorb and GenericTerm._can_absorb_: Why two methods?
• GenericTerm.absorb: what happens if check is not set? Why would one want to call that?
• GenericTerm.absorb, last 3 lines of code: isn't it quite confusing to override self and other in the lambda expression?
• GenericTerm._absorb_: the method is never called in the doctests, in particular, the NotImplementedError does not show up.
• GenericTermMonoid.__init__: see ​#17600, comment 40: handling of tuples as parameter category, __classcall__ for parameter category; same question for derived classes?
• GenericTermMonoid.__init__: documentation says that growth_group has to be a "partially ordered group" with a GenericGrowthGroup only listed as an example; code explicitly requires a GenericGrowthGroup.
• GenericTermMonoid._element_constructor_: why example T_QQ.coerce(term1) instead of T_QQ(term1)?
• GenericTermMonoid._element_constructor_: why type(data) == self.element_class and not isinstance(data, self.element_class) ? Similarly for other parents.
• OTermMonoid._coerce_map_from_: documentation does not agree with code: according to the documentation, S must be an OTermMonoid or an ExactTermMonoid. However, the code does not enforce the former.
• TermWithCoefficient._le_: The comparison of coefficients is not documented. Apart from that, do we really want that x <= 2*I*x when the coefficient ring is complex?
• TermWithCoefficientMonoid._init_: check error condition
• TermWithCoefficientMonoid.base_ring: why is this a property instead of a function? Compare with ring of polynomials.
• TermWithCoefficientMonoid._coerce_map_from_: documentation mentions "this exact term monoid", but this is a TermWithCoefficientMonoid.
• ExactTerm._repr_: I do not like the check self.growth._raw_element_ == 0, self.growth is the identity element of that group, so we should check for that.
• I'd prefer .is_zero() over == 0.
• TermMonoidFactory.create_key_and_extra_args: test error conditions

---

New commits:

​88b9294	Trac #19237: Fix ReSt errors in reference/rings
​a7361b2	Trac #17715: Merge #19237 to ease review
​148b0b8	Trac #17715: minor documentation issues
​9f8a248	Trac #17715: remove duplicate line in doctest
​d870c90	Trac #17715: Documentation: language
​d4c2b0a	Trac #17715: Fix/insert links
​a2dfd22	Trac #17715: ReSt error
​f6882fe	Trac #17715: additional doctest for explanation
​347f080	Trac #17715: emphasize that 'O' is capital letter and not digit

[behackl]

Hello Clemens!

Replying to cheuberg:

I reviewed this ticket, added a few reviewer commits and have a few comments:

• absorption: One-Sentence-Description should describe what this function does. What happens if the elements are not comparable (documentation; probably only possible in a follow-up ticket)?

I adapted the short description and slightly adapted the code, such that a different ArithmeticError is raised. (This should not introduce a merge conflict, this code did not change up to (and including) the cleanup ticket #19083.)

• can_absorb: One-Sentence-Description, then NOTE section would be superfluous.

Done.

• GenericTerm.__init__: Provide doctests for error conditions

I did introduce some tests -- however, only for those errors that are also raised on the cleanup ticket #19083 (... one less thing to think about when merging the changes into there). If you would prefer a full error coverage on this ticket as well, let me know.

• GenericTerm.can_absorb and GenericTerm._can_absorb_: Why two methods?

As far as I can remember, we wanted can_absorb to be a publicly accessible function, but in the documentation it should not apper too often. Thus, we wrote one public (well-documented) function that calls _can_absorb_, and implemented _can_absorb_ in the derived classes only.

In any case, I suppose we could change that, as we documented all the "technical" _can_absorb_-functions also quite well. What do you think would be cleaner?

• GenericTerm.absorb: what happens if check is not set? Why would one want to call that?

At some point we wanted an option to surpress this check because in the AsymptoticRing, the MutablePoset calls can_absorb really very often, which makes it a bottleneck, up to some degree. In certain cases, for example when adding an O-term into a MutablePoset, then the poset first needs to do some comparisons in order to place the O-term correctly---and then, in a second step, the O-term absorbs all predecessors (without additional comparison!), because O-terms can absorb anything with weaker growth.

This was the motivation to have some option that allows to skip the test. Actually doing this optimization is--however--still on our TODO-list.

• GenericTerm.absorb, last 3 lines of code: isn't it quite confusing to override self and other in the lambda expression?

Yes, it really is. Changed to left and right.

• GenericTerm._absorb_: the method is never called in the doctests, in particular, the NotImplementedError does not show up.

Added a doctest that directly calls GenericTerm._absorb_.

• GenericTermMonoid.__init__: see ​#17600, comment 40: handling of tuples as parameter category, __classcall__ for parameter category; same question for derived classes?

Like with the GrowthGroup, this is already fixed in #19083. Thus, I'd leave this as is.

• GenericTermMonoid.__init__: documentation says that growth_group has to be a "partially ordered group" with a GenericGrowthGroup only listed as an example; code explicitly requires a GenericGrowthGroup.

This has been partially changed in #19083. There, the growth group only has to be a parent -- but we should probably also check, whether the category of the passed growth group is a subcategory of Posets(). This would also fit to the suggested changes in #18223.

In any case, as this ticket enforces the growth group to be derived from GenericGrowthGroup, the category is also a subcategory of Posets(). Thus, I'd also vote for leaving this as is.

• GenericTermMonoid._element_constructor_: why example T_QQ.coerce(term1) instead of T_QQ(term1)?

Changed.

• GenericTermMonoid._element_constructor_: why type(data) == self.element_class and not isinstance(data, self.element_class) ? Similarly for other parents.

Changed.

• OTermMonoid._coerce_map_from_: documentation does not agree with code: according to the documentation, S must be an OTermMonoid or an ExactTermMonoid. However, the code does not enforce the former.

Yes, it does---however, it's not really obvious. Calling

super(OTermMonoid, self)._coerce_map_from_(S)

enforces this, as we check isinstance(S, self.__class__) there.

• TermWithCoefficient._le_: The comparison of coefficients is not documented. Apart from that, do we really want that x <= 2*I*x when the coefficient ring is complex?

This is problematic. For now, I've included a check for the imaginary part---but if the coefficient ring is not ordered, this still causes problems.

I suppose that we could discuss removing _le_ for these terms altogether, or make terms of equal growth always incomparable: terms of equal growth are not handled via comparison, but via absorption...

• TermWithCoefficientMonoid._init_: check error condition

Rewritten. Now checks whether base_ring is in Rings().

• TermWithCoefficientMonoid.base_ring: why is this a property instead of a function? Compare with ring of polynomials.

I believe that this makes some of the code in #19083 that handles the pushout-stuff (... changing the base ring ...) easier. Also, I think that having this as a property is overall cleaner.

Let me know if you think that we should enforce consistency with the PolynomialRing.

• TermWithCoefficientMonoid._coerce_map_from_: documentation mentions "this exact term monoid", but this is a TermWithCoefficientMonoid.

Fixed.

• ExactTerm._repr_: I do not like the check self.growth._raw_element_ == 0, self.growth is the identity element of that group, so we should check for that.

Fixed in #19083.

• I'd prefer .is_zero() over == 0.

Changed everywhere in #19083.

• TermMonoidFactory.create_key_and_extra_args: test error conditions

Added some more tests.

I pushed my changes to this ticket; please cross-review them and let me know how you want to proceed regarding the open questions.

Thanks for the review!

Benjamin

---

Last 10 new commits:

​3b0a678	improve absorb, can_absorb
​5aa190e	test for checking parent of growth in __init__
​ea89a53	lambda: self, other --> left, right
​d6de96c	test _absorb_
​cf9f007	use call instead of .coerce(..)
​6bfb92f	type(..) == ... --> isinstance(...)
​483f6b9	fix comparison of terms with complex coefficients
​1920865	fix docstring of _coerce_map_from_ from term with coefficient monoid
​1217348	improve handling of base_ring for term with coefficient monoid
​0bac3bb	add more tests for TermMonoidFactory

[cheuberg]

Replying to behackl:

• GenericTerm.can_absorb and GenericTerm._can_absorb_: Why two methods?

As far as I can remember, we wanted can_absorb to be a publicly accessible function, but in the documentation it should not apper too often. Thus, we wrote one public (well-documented) function that calls _can_absorb_, and implemented _can_absorb_ in the derived classes only.

In any case, I suppose we could change that, as we documented all the "technical" _can_absorb_-functions also quite well. What do you think would be cleaner?

My impression when reviewing this ticket was that absorption is explained many times. Perhaps these explanations and examples could have been collected in one place (either in the module documentation or in the relevant methods in the base class). Then the documentation of all overriden classes could have included a link to the general explanation and only explain the particularities of the respective class. Having the explanation in the docstring of a method of the base class would have the advantage that users of method? could also access it.

This module is of rather technical nature anyway and the end user will hopefully rarely look into it. Thus reducing the number of occurrences of can_absorb in the reference manual does not concern me too much.

IMHO, having can_absorb as a trivial wrapper around _can_absorb_ has a (very slight) performance penalty and makes future reading of the code somewhat harder.

• GenericTerm.absorb: what happens if check is not set? Why would one want to call that?

At some point we wanted an option to surpress this check because in the AsymptoticRing, the MutablePoset calls can_absorb really very often, which makes it a bottleneck, up to some degree. In certain cases, for example when adding an O-term into a MutablePoset, then the poset first needs to do some comparisons in order to place the O-term correctly---and then, in a second step, the O-term absorbs all predecessors (without additional comparison!), because O-terms can absorb anything with weaker growth.

This was the motivation to have some option that allows to skip the test. Actually doing this optimization is--however--still on our TODO-list.

Could you add one sentence to the documentation? Something like "Setting check=False is meant to be used in cases where the truth of can_absorb has been checked in advance to avoid duplicate checking."

• GenericTermMonoid.__init__: documentation says that growth_group has to be a "partially ordered group" with a GenericGrowthGroup only listed as an example; code explicitly requires a GenericGrowthGroup.

This has been partially changed in #19083. There, the growth group only has to be a parent -- but we should probably also check, whether the category of the passed growth group is a subcategory of Posets(). This would also fit to the suggested changes in #18223.

In any case, as this ticket enforces the growth group to be derived from GenericGrowthGroup, the category is also a subcategory of Posets(). Thus, I'd also vote for leaving this as is.

I think that if the current code expects the growth group to be a GenericGrowthGroup, then the documentation should state that.

• GenericTermMonoid._element_constructor_: why example T_QQ.coerce(term1) instead of T_QQ(term1)?

Changed.

The attached comment should also be changed. Having a look again, I now partially understand why coerce was called in the first place: it seems to explain why comparison in the line above could work. However, in the _element_constructor_ method, I expected to see an example of conversion. Perhaps both could be included: first conversion, then comparison and the explanation that coercion did actually work.

• TermWithCoefficient._le_: The comparison of coefficients is not documented. Apart from that, do we really want that x <= 2*I*x when the coefficient ring is complex?

This is problematic. For now, I've included a check for the imaginary part---but if the coefficient ring is not ordered, this still causes problems.

I suppose that we could discuss removing _le_ for these terms altogether, or make terms of equal growth always incomparable: terms of equal growth are not handled via comparison, but via absorption...

I do not know yet what the usecase for comparison of elements of equal growth was supposed to be. For me, only comparing the growth would be sufficient. Mixing the order of the growth group and the order of the base ring seems to be some kind of overkill, if at all possible.

I am not sure, though, whether x <= 2*x and 2*x <= x should hold. Or what about mixing exact terms and O terms.

Are distinct conventions for _le_ and can_absorb necessary?

• TermWithCoefficientMonoid.base_ring: why is this a property instead of a function? Compare with ring of polynomials.

I believe that this makes some of the code in #19083 that handles the pushout-stuff (... changing the base ring ...) easier.

Could someone elaborate on that?

Also, I think that having this as a property is overall cleaner.

Why?

Including this ticket, we have 74 classes with base_ring,

$rgrep 'def base_ring' | wc
     74     230    4186

and one of them (this ticket) has it as a property:

$ rgrep -C1 'def base_ring' . |grep property
./rings/asymptotic/term_monoid.py-    @property

Let me know if you think that we should enforce consistency with the PolynomialRing.

I'd like to see more convincing arguments before breaking consistency with 73 other sage modules.

I pushed my changes to this ticket; please cross-review them and let me know how you want to proceed regarding the open questions.

done.

I have one further question not discussed so far:

• absorb uses the coercion framework before calling _absorb_ with guaranteed equal parents. can_absorb does not. Is there a reason for that? Does only the growth group play a role here, so that different parents do not really matter?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​0da8a7a	improved module documentation
​3964eae	_can_absorb_ --> can_absorb
​820e310	base_ring is now a function, not a property
​4afce6c	removed TermWithCoefficient._le_, improved documentation of __le__ and _le_
​6d23773	clarification of growth_group in GenericTermMonoid.__init__
​ad0754c	shifted documentation of absorption towards module description
​0eaa472	remark regarding keyword check in GenericTerm.absorb
​67a73ca	improved some doctests

[behackl]

Replying to cheuberg:

My impression when reviewing this ticket was that absorption is explained many times. Perhaps these explanations and examples could have been collected in one place (either in the module documentation or in the relevant methods in the base class). Then the documentation of all overriden classes could have included a link to the general explanation and only explain the particularities of the respective class. Having the explanation in the docstring of a method of the base class would have the advantage that users of method? could also access it.

This module is of rather technical nature anyway and the end user will hopefully rarely look into it. Thus reducing the number of occurrences of can_absorb in the reference manual does not concern me too much.

IMHO, having can_absorb as a trivial wrapper around _can_absorb_ has a (very slight) performance penalty and makes future reading of the code somewhat harder.

I think that you are right. I've collected the documentation for absorb and can_absorb and put it in a section of the module description. The respective methods now only have a short documentation (explaining their own behavior), and a reference to that section.

• GenericTerm.absorb: what happens if check is not set? Why would one want to call that?

At some point we wanted an option to surpress this check because in the AsymptoticRing, the MutablePoset calls can_absorb really very often, which makes it a bottleneck, up to some degree. In certain cases, for example when adding an O-term into a MutablePoset, then the poset first needs to do some comparisons in order to place the O-term correctly---and then, in a second step, the O-term absorbs all predecessors (without additional comparison!), because O-terms can absorb anything with weaker growth.

This was the motivation to have some option that allows to skip the test. Actually doing this optimization is--however--still on our TODO-list.

Could you add one sentence to the documentation? Something like "Setting check=False is meant to be used in cases where the truth of can_absorb has been checked in advance to avoid duplicate checking."

Done.

• GenericTermMonoid.__init__: documentation says that growth_group has to be a "partially ordered group" with a GenericGrowthGroup only listed as an example; code explicitly requires a GenericGrowthGroup.

This has been partially changed in #19083. There, the growth group only has to be a parent -- but we should probably also check, whether the category of the passed growth group is a subcategory of Posets(). This would also fit to the suggested changes in #18223.

In any case, as this ticket enforces the growth group to be derived from GenericGrowthGroup, the category is also a subcategory of Posets(). Thus, I'd also vote for leaving this as is.

I think that if the current code expects the growth group to be a GenericGrowthGroup, then the documentation should state that.

It does so now.

• GenericTermMonoid._element_constructor_: why example T_QQ.coerce(term1) instead of T_QQ(term1)?

Changed.

The attached comment should also be changed. Having a look again, I now partially understand why coerce was called in the first place: it seems to explain why comparison in the line above could work. However, in the _element_constructor_ method, I expected to see an example of conversion. Perhaps both could be included: first conversion, then comparison and the explanation that coercion did actually work.

I don't think that conversion is at work in this particular section---in any case, I've rewritten these doctests slightly in order to better reflect what we want to demonstrate.

• TermWithCoefficient._le_: The comparison of coefficients is not documented. Apart from that, do we really want that x <= 2*I*x when the coefficient ring is complex?

This is problematic. For now, I've included a check for the imaginary part---but if the coefficient ring is not ordered, this still causes problems.

I suppose that we could discuss removing _le_ for these terms altogether, or make terms of equal growth always incomparable: terms of equal growth are not handled via comparison, but via absorption...

I do not know yet what the usecase for comparison of elements of equal growth was supposed to be. For me, only comparing the growth would be sufficient. Mixing the order of the growth group and the order of the base ring seems to be some kind of overkill, if at all possible.

I am not sure, though, whether x <= 2*x and 2*x <= x should hold. Or what about mixing exact terms and O terms.

Are distinct conventions for _le_ and can_absorb necessary?

In fact, we only need the comparison of the underlying growth. I've deleted TermWithCoefficient._le_ and rewritten the documentation of GenericTerm.__le__ and GenericTerm._le_ in order to reflect that.

As this is--as you already said--a rather technical class, I think that it can be justified if <= only compares growth. However, if we follow this approach, then x <= 2*x and 2*x <= x would both yield True, but x == 2*x would be false (because as far as I can remember, we need == to actually check if the coefficients are the same too, somewhere in the AsymptoticRing). Any thoughts?

• TermWithCoefficientMonoid.base_ring: why is this a property instead of a function? Compare with ring of polynomials.

I believe that this makes some of the code in #19083 that handles the pushout-stuff (... changing the base ring ...) easier.

Could someone elaborate on that?

Also, I think that having this as a property is overall cleaner.

Why?

Including this ticket, we have 74 classes with base_ring,

$rgrep 'def base_ring' | wc
     74     230    4186

and one of them (this ticket) has it as a property:

$ rgrep -C1 'def base_ring' . |grep property
./rings/asymptotic/term_monoid.py-    @property

Let me know if you think that we should enforce consistency with the PolynomialRing.

I'd like to see more convincing arguments before breaking consistency with 73 other sage modules.

Mea culpa, I was wrong. Later on, we renamed base_ring to coefficient_ring---but as far as I've looked up, we never acutally set the property outside of initialization. So this could easily become a function (which is what I also changed here).

I pushed my changes to this ticket; please cross-review them and let me know how you want to proceed regarding the open questions.

done.

I have one further question not discussed so far:

• absorb uses the coercion framework before calling _absorb_ with guaranteed equal parents. can_absorb does not. Is there a reason for that? Does only the growth group play a role here, so that different parents do not really matter?

Well, we currently only have three cases when t1.can_absorb(t2) is called:

• t1 is a term from an abstract base class. These cannot absorb anything, so False is returned. No need to ask the coercion framework.
• t1 is an O-term. In this case, can_absorb tests t1 <= t2, which in turn asks the coercion framework for help.
• t1 is an exact term. Here, t2 can be absorbed if and only if t2 is an exact term as well, and the growth needs to coincide as well. I don't think that the coercion framework should be involved in this case.

Benjamin

[cheuberg]

Replying to behackl:

In fact, we only need the comparison of the underlying growth. I've deleted TermWithCoefficient._le_ and rewritten the documentation of GenericTerm.__le__ and GenericTerm._le_ in order to reflect that.

As this is--as you already said--a rather technical class, I think that it can be justified if <= only compares growth. However, if we follow this approach, then x <= 2*x and 2*x <= x would both yield True, but x == 2*x would be false (because as far as I can remember, we need == to actually check if the coefficients are the same too, somewhere in the AsymptoticRing). Any thoughts?

First, I do not know what the next tickets want to see, whether <= has to be antisymmetric or not. On the other hand, elements of equal growth will always absorb each other and not be elements of the same asymptotic expansion, anyway?

Second, where is the implementation of equality of growth terms?

If in doubt, I would say that x and 2x are incomparable in order to save antisymmetry.

Apart from that, I reviewed your changes, added a few reviewer commits (please cross-review).

---

New commits:

​ce7e2a3	Trac #17715: avoid the use of repr in doctest
​7b29b28	Trac #17715: do not include "the" in internal link texts
​b22a24b	Trac #17715: Fix ReSt error

[behackl]

Replying to cheuberg:

Replying to behackl:

In fact, we only need the comparison of the underlying growth. I've deleted TermWithCoefficient._le_ and rewritten the documentation of GenericTerm.__le__ and GenericTerm._le_ in order to reflect that.

As this is--as you already said--a rather technical class, I think that it can be justified if <= only compares growth. However, if we follow this approach, then x <= 2*x and 2*x <= x would both yield True, but x == 2*x would be false (because as far as I can remember, we need == to actually check if the coefficients are the same too, somewhere in the AsymptoticRing). Any thoughts?

First, I do not know what the next tickets want to see, whether <= has to be antisymmetric or not. On the other hand, elements of equal growth will always absorb each other and not be elements of the same asymptotic expansion, anyway?

I agree, once again. We should preserve that <= is antisymmetric, and I propose the following:

• For terms without coefficient, we simply compare the growth with <= like we do now.
• For terms with coefficient, we check if term1.growth < term.growth (still like above), and in case we have term1.growth == term2.growth, we return True if and only if the terms are the same, i.e. if the coefficient coincides. Otherwise, the terms are incomparable.

I've added this, as well as a short note in the module description how terms are compared.

Second, where is the implementation of equality of growth terms?

If in doubt, I would say that x and 2x are incomparable in order to save antisymmetry.

Ah! These did not exist on this ticket -- I have added them as well, as they logically belong here.

Apart from that, I reviewed your changes, added a few reviewer commits (please cross-review).

I reviewed your changes, and added the points from above (please cross-review again :-)).

Benjamin

---

Last 10 new commits:

​ad0754c	shifted documentation of absorption towards module description
​0eaa472	remark regarding keyword check in GenericTerm.absorb
​67a73ca	improved some doctests
​fe906ca	reintroduce _le_ for TermWithCoefficient
​5cb54ae	equality comparison for terms
​14e3e63	improve documentation: information on comparison
​ce7e2a3	Trac #17715: avoid the use of repr in doctest
​7b29b28	Trac #17715: do not include "the" in internal link texts
​b22a24b	Trac #17715: Fix ReSt error
​abc6a16	Merge branch 'u/cheuberg/asy/asymptoticTerm' of git://trac.sagemath.org/sage into asy/asymptoticTerm

[cheuberg]

I added one more trivial language-related commit. Everything is fine for me now. Doctests pass, documentation builds.

Again, the module will only become useful only once at least #17716 is merged.

---

New commits:

​aea0ae8

Trac #17715: Minor language adjustments