AsymptoticGrowthElement

[behackl]

Hold one order of magnitude for asymptotic terms and expressions. Such a term could be, e.g. n² or k/n or n*log(n).

AsymptoticGrowthElements can be compared, multiplied, etc., but have no coefficient. Here, only the order of magnitude shall be managed.

See #17601 for the planned structure.

[git]

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

​485502b

added the copyright header.

[git]

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

​492679e	fixed author date in copyright header.
​278c1f7	fixed coercion error: coercion happens now only when bases coerce into

[vdelecroix]

Hello,

The "planned structure" at #17601 does not motivates any choice. In particular, the branch attached to this ticket makes me sceptical since it implements a completely broken version of a multiplicative group isomorphic to RR (which is also slower and less usable than the original one).

Why is it a group and not a ring? Why should there be, if any, a dedicated parent to an asymptotic term? Do you really intend to implement a parent for each kind of asymptotic you have in mind?

What I see in the branch is only code that is working for itself which is not very interesting and not very useful. You can not start building a cathedral without any serious roadmap.

Vincent

[cheuberg]

Replying to vdelecroix:

Why is it a group and not a ring?

The AsymptoticGrowthGroup is only planned to handle the multiplicative structure. Instead of the simplest example here, think about asymptotics involving powers of n and log(n) for n -> infinity. Then this group will be isomorphic to a cartesian product of RR with itself with lexicographic order. In another example, where |h|<= n^(3/4) and n->infinity, this group will again be a cartesian product of RR with itself, but the partial order of the lexicographic order will be refined by the additional rule, but not yet be a linear order because some of these terms cannot be compared.

Handling of coefficients, addition of two terms and absorption of O terms are rather independent of the growth group as outlined here. Thus they are planned to be handeled by the AsymptoticTerm (#17715).

High level operations such as addition and multiplication of expressions are still more general and will be part of the (yet unimplemented) AsymptoticExpression (#17716).

Why should there be, if any, a dedicated parent to an asymptotic term?

There is a natural coercion from an AsymptoticGrowthGroup in n to the AsymptoticGrowthGroup in n and log(n), for instance. Thus I think it makes sense to use the coercion framework. This requires to have parents.

What I see in the branch is only code that is working for itself which is not very interesting and not very useful.

Therefore, all these tickets are still in status new and not needs_review, because the AsymptoticExpression is still missing.

You can not start building a cathedral without any serious roadmap.

There is a roadmap and the very brief version is in the meta ticket #17601. The long version are notes made during long oral discussions.

Your comments here and on the meta ticket #17601 make it clear that the abbreviated version is not sufficiently clear. Probably the long version of the road map will also be of interest later on and could live in the documentation of the asymptotic expression.

[behackl]

Rebased to Sage 6.7.

[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

[dkrenn]

Last 10 new commits:

​8b06fa6	cleanup in _convert_
​b746c83	delete unnecessary populate coercion list
​7b1bef5	rewrite class descriptions
​608d524	revise gen & Co methods
​4be8d0d	some new doctests, minor docstring rewritings, small other modifications
​d08e4d2	write docstring-header of module
​160a2d3	add description of exponent-property
​c2a5beb	move _div_ to GenericGrowthElement
​dd1f1de	operations of elements: some small modifications and rewritings
​9fe8bb6	docstrings in elements

[git]

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

​4e80522

repr: checking for integers with isinstance introduces problems with

[git]

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

​4207fce	a base is valid, if it inherits from Parent
​e48afc9	minor documentation improvements
​73017ab	conversion from multivariate polynomial rings and multivariate power

[git]

Branch pushed to git repo; I updated commit sha1. 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

[git]

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

​5538893

added @experimental to parents

[git]

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

​627884c	introduce _repr_short_ for nicer representation
​907e82d	docstrings for _repr*_ methods
​6c8b543	changed default representation to short representation
​2903a9a	helper method for short representation implemented

[git]

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

​30cde4d

extend docstring of parent_to_string

[git]

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

​ed03ca1	rename to parent_to_repr_short
​45a37b8	rewrite docstring

[git]

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

​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

[behackl]

Last 10 new commits:

​29d7479	TESTS-->EXAMPLES
​9ae448c	change repr-string of groups
​a985397	change experimental feature trac number to meta ticket 17601
​30cde4d	extend docstring of parent_to_string
​ed03ca1	rename to parent_to_repr_short
​45a37b8	rewrite docstring
​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

[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
​3749fa1	refactored handling of generators

[git]

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

​c6d8584

error with the element constructor fixed, doctest added

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

[rws]

I found a few language oddities.

functions and their behavior as the
functions, and their behavior as the

It, its functionality or its interface
Either its functionality or its interface

Helper method, which generates
Helper method which generates

Growth elements form a group by multiplication and (some of) the
Growth elements form a group by multiplication, and (some of) the

that this element, as well as ``other`` are of the same type.
that this element is of the same type as ``other``.

This can anything that is valid to be on the right hand side of ``*`` with an elements of the parent's base
This can be anything that is a valid right hand side of ``*`` with elements of the parent's base.
(found twice)

The result of this exponentiation a :class:`MonomialGrowthElement`.
The result of this exponentiation, a :class:`MonomialGrowthElement`.

Return if this growth element is equal to ``other``.
Return True if this growth element is equal to ``other``.

Return if this :class:`GenericGrowthElement` is equal to ``other``.
Return True if this :class:`GenericGrowthElement` is equal to ``other``.
...and similar cases...

Converts given object to this growth group.
Converts a given object to this growth group.

Converts given ``data`` to something...
Converts ``data`` to something...

class and should be overridden in inherited class.
class, and should be overridden in inherited classes.

Takes this growth element to the given ``power``.
Raises this growth element to the given ``power``.

[behackl]

Hi Ralf! Thanks for your remarks; I'm currently fixing these oddities and will push the changes soon. One question: instead of

Return ``True`` if ...

what do you think about:

Return whether ...

Just because we'd like to avoid directly referring to True.

[rws]

Replying to behackl:

Hi Ralf! Thanks for your remarks; I'm currently fixing these oddities and will push the changes soon. One question: instead of

Return ``True`` if ...

what do you think about:

Return whether ...

Well if is a synonym for whether so nothing changed.

Just because we'd like to avoid directly referring to True.

I have no idea why you would want that. Can you please clarify?

[dkrenn]

Replying to rws:

Return ``True`` if ...

what do you think about:

Return whether ...

Well if is a synonym for whether so nothing changed.

Just because we'd like to avoid directly referring to True.

I have no idea why you would want that. Can you please clarify?

The one-liner description should be short; additionally we have an output block saying that the method returns a boolean. Since there also an ongoing discussion in #19041 about such things, I would leave it for now as it is...

Is there a grammatical reason that "Return if..." should be avoided?

[rws]

Replying to dkrenn:

Is there a grammatical reason that "Return if..." should be avoided?

Not at all. I accept your explanation.

[git]

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

​db9ee43	improved __pow__
​2f3d740	improved _element_constructor_
​e8662cd	collect asymptotic code in one directory
​7774ff2	fixed doctests
​878ef2a	fixed documentation build
​1c81c12	language oddities fixed

[dkrenn]

Merged in 6.9.beta5

---

New commits:

​3a05be7	Merge tag '6.9.beta5' into t/17600/asy/growthGroup
​58f931d	add asymptotic_expansions index

[git]

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

​ef5591f	Trac #17600: Minor language adjustments
​ac55417	Trac #17600: Break long line

[cheuberg]

I started reviewing this ticket and added three reviewer commits, one of which is not shown in trac.

Comments so far:

• I think that the following behaviour does not conform to the use of the parameter category in Parent ("If category is a list or tuple, a JoinCategory is created out of them."):

  sage: import sage.rings.asymptotic.growth_group as agg
  sage: agg.GenericGrowthGroup(ZZ, category=(Posets(), Groups()))
  Traceback (most recent call last):
  ...
  ValueError: (Category of posets, Category of groups) is not a subcategory of Join of Category of groups and Category of posets
  

  Compare this with

  sage: Parent(category=(Posets(), Groups())).category()
  Join of Category of groups and Category of posets
  

• GenericGrowthElement - class documentation: "abstract implementation" sounds contradictory.
• GenericGrowthElement.__init__: first and second tests seem to do the same thing.

[git]

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

​83a3905	Trac #17600: Fix ReSt error
​f827b2c	Trac #17600: one-sentence descriptions: command instead of description
​c4dca20	Trac #17600: Punctuation
​1ab1334	Trac #17600: fix incorrect link

[cheuberg]

Here is the remainder of my comments.

• GenericGrowthGroup._element_constructor_: make clear that either data or raw_element has to be given; in the latter case, data has to be 0.
• GenericGrowthGroup._element_constructor_: shouldn't the tests be marked as indirect doctests?
• GenericGrowthGroup._element_constructor_: is there a particular reason for using type(data) == self.element_class in the second line and isinstance(data, self.element_class) in the fourth line of the code?
• GenericGrowthGroup.gens_monomial: it is not clear what the difference between gens and gens_monomial should be.
• MonomialGrowthGroup.__classcall__: The category parameter is not checked, but I can live with that:

  sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup
  sage: G1 = MonomialGrowthGroup(ZZ, 'x')
  sage: G2 = MonomialGrowthGroup(ZZ, 'x', category=Posets() & Groups())
  sage: G1 is G2
  False
  sage: G1.category() == G2.category()
  True
  

• MonomialGrowthGroup.__init__: Please include doctests for the two ValueErrors
• MonomialGrowthGroup._convert_: I think that the error message on variable in a multivariate power series is not instructive in the following example, I'd prefer to see "Cannot convert 2" as in G(2) below.

  sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup
  sage: G = MonomialGrowthGroup(ZZ, 'x')
  sage: R.<x, y> = PowerSeriesRing(ZZ, ['x', 'y'])
  sage: R(2).variables()
  ()
  sage: G(R(2))
  Traceback (most recent call last):
  ...
  NotImplementedError: variable not defined for multivariate power series;
  use 'variables' instead.
  sage: G(2)
  Traceback (most recent call last):
  ...
  ValueError: Cannot convert 2.
  

• MonomialGrowthGroup.gens_monomial: Is this method needed? See the example:

  sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup
  sage: MonomialGrowthGroup(ZZ, 'log(x)').gens_monomial()
  ()
  sage: MonomialGrowthGroup(ZZ, 'exp(x)').gens_monomial()
  (exp(x),)
  

• MonomialGrowthGroup.gens: cf. gens_monomial: I'd move "even if the growth group is logarithmic" from gens to gens_monomial as "except if the growth group is logarithmic"
• parent_to_repr_short: Rewrite INPUT section to standard format

[behackl]

Last 10 new commits:

​f827b2c	Trac #17600: one-sentence descriptions: command instead of description
​c4dca20	Trac #17600: Punctuation
​1ab1334	Trac #17600: fix incorrect link
​1c7a521	corrected INPUT-section of parent_to_repr_short
​6dee8b7	abstract implementation --> basic implementation
​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

[behackl]

Replying to cheuberg:

• I think that the following behaviour does not conform to the use of the parameter category in Parent ("If category is a list or tuple, a JoinCategory is created out of them."):

  sage: import sage.rings.asymptotic.growth_group as agg
  sage: agg.GenericGrowthGroup(ZZ, category=(Posets(), Groups()))
  Traceback (most recent call last):
  ...
  ValueError: (Category of posets, Category of groups) is not a subcategory of Join of Category of groups and Category of posets
  

This is because our code checks, whether at least one argument in the tuple is a subcategory of Join of Category of groups and Category of posets. Of course, this could be relaxed such that we check if there is at least one argument that is a subcategory of Category of groups, and at least one that is a subcategory of Category of posets.

However, we already took care of that in the cleanup ticket #19083. Thus, I'd leave this as it is here.

• GenericGrowthElement - class documentation: "abstract implementation" sounds contradictory.

Rephrased to "basic implementation".

• GenericGrowthElement.__init__: first and second tests seem to do the same thing.

Duplicate removed.

• GenericGrowthGroup._element_constructor_: make clear that either data or raw_element has to be given; in the latter case, data has to be 0.

Done.

• GenericGrowthGroup._element_constructor_: shouldn't the tests be marked as indirect doctests?

Done.

• GenericGrowthGroup._element_constructor_: is there a particular reason for using type(data) == self.element_class in the second line and isinstance(data, self.element_class) in the fourth line of the code?

Not as far as I can remember. I have rewritten this particular part of the element constructor.

• GenericGrowthGroup.gens_monomial: it is not clear what the difference between gens and gens_monomial should be.

I've tried to clarify by extending the documentation.

• MonomialGrowthGroup.__classcall__: The category parameter is not checked, but I can live with that:

Fixed on the cleanup-ticket.

• MonomialGrowthGroup.__init__: Please include doctests for the two ValueErrors

We put the code handling variables in a separate class on the cleanup ticket. Thus, I think that this is not really necessary.

• MonomialGrowthGroup._convert_: I think that the error message on variable in a multivariate power series is not instructive in the following example, I'd prefer to see "Cannot convert 2" as in G(2) below.

  sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup
  sage: G = MonomialGrowthGroup(ZZ, 'x')
  sage: R.<x, y> = PowerSeriesRing(ZZ, ['x', 'y'])
  sage: R(2).variables()
  ()
  sage: G(R(2))
  Traceback (most recent call last):
  ...
  NotImplementedError: variable not defined for multivariate power series;
  use 'variables' instead.
  sage: G(2)
  Traceback (most recent call last):
  ...
  ValueError: Cannot convert 2.
  

Fixed.

• MonomialGrowthGroup.gens_monomial: Is this method needed? See the example:

  sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup
  sage: MonomialGrowthGroup(ZZ, 'log(x)').gens_monomial()
  ()
  sage: MonomialGrowthGroup(ZZ, 'exp(x)').gens_monomial()
  (exp(x),)
  

I've added an additional note to explain what this method should exactly do. Note that while it can only recognize log(...) on this ticket, we have extended the functionality of it (to actually do what it should) on ticket #18587.

• MonomialGrowthGroup.gens: cf. gens_monomial: I'd move "even if the growth group is logarithmic" from gens to gens_monomial as "except if the growth group is logarithmic"

Removed the half-sentence. The additional note for gens_monomial should make the difference clear.

• parent_to_repr_short: Rewrite INPUT section to standard format

Done.

Thank you for your review---this is now ready for a short cross-review.

[cheuberg]

Reviewed your changes.

Doctests pass, documentation builds, code is ok.

Obviously, inclusion of this ticket alone into SageMath is not useful. However, once everything mentioned in the meta ticket #17601 is merged, this should be very useful. It will take some more time to finish and then review all those tickets.

Despite all that, a first step has to be made, so I set this to positive_review.