cartesian products of growth groups

[dkrenn]

This implements cartesian products (via #18223) of growth groups (see #17600; or meta ticket #17601).

In particular, the factory for growth groups introduced in #18930 is extended such that cartesian products can also be generated.

[behackl]

Last 10 new commits:

​5b12589	Merge branch 'asy/growthGroup-factory' into asy/growth-group-cartesian
​0532942	GrowthGroupFactory extension: construction of cartesian products
​c547712	header modified
​3af46e7	no unneccessary cartesian products
​7e0fb9e	representation of cartesian product elements improved
​ca73a61	module description improved
​ab9bcaf	element constructor of monomial growth groups also try to parse the
​a899bb7	element constructor for cartesian product elements implemented
​537f22c	problem with parsing of strings fixed
​327d7ca	module documentation: added some doctests

[git]

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

​96435ce	Merge branch 'asy/6.7/growthGroup' into asy/group-factory
​b7d2273	repair
​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
​eb317b1	Merge branch 'asy/growthGroup-factory' into asy/growth-group-cartesian;

[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
​016d1f0	merge branch 'asy/growthGroup-factory' into asy/growth-group-cartesian and resolve minor conflict
​3749fa1	refactored handling of generators
​ba16c0f	Merge branch 'asy/growthGroup' into asy/growthGroup-factory
​b18f319	Merge branch 'asy/growthGroup-factory' into asy/growth-group-cartesian

[git]

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

​f4d16c2	gens_monomial for cartesian products implemented
​f33ba27	fixed an issue with conversion of log(var)
​c6d8584	error with the element constructor fixed, doctest added
​3564d23	Merge branch 'asy/growthGroup' into asy/growthGroup-factory
​dfbe937	Merge branch 'asy/growthGroup-factory' into asy/growth-group-cartesian
​8352429	element constructor of cartesian products simplified; helper method implemented

[git]

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

​1815847	two minor modifications of docstrings
​6e33615	modify to to make things running...
​62fc735	write docstings of cartesian factory

[git]

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

​b634767	change output of extract_variable_names
​9c59fe1	lazy import instead of import
​3fe816a	extend extraction of variable names
​9f65f8b	delete .one, since provided by categories
​08f10df	inherite cartesian product from growth group as well
​f67cb03	simplify and adapt gens_monomial()
​925d700	pass flags of repr
​68643c4	better parsing variables
​58dbda7	better parsing growth group factory
​b7bb595	rewrite factory to use previous enhancements

[git]

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

​8c8c1b5

fix doctest coverage

[git]

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

​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
​ca5da4a	Merge branch 't/18930/asy/growthGroup-factory' into t/18587/asy/growth-group-cartesian
​ac80aeb	add growth_group_cartesian to index

[dkrenn]

Merge in 6.9.beta5

[behackl]

Merged latest positively reviewed dependencies (#17600, #18930) into this branch and resolved some small merge conflicts.

---

Last 10 new commits:

​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
​4f99031	Merge branch 'asy/growthGroup' into asy/growthGroup-factory
​55c78e2	Merge branch 'asy/growthGroup-factory' into asy/growth-group-cartesian
​4a6174f	improved a short description

[cheuberg]

I reviewed this ticket, but without reviewing the dependency on #18223, so consider this as a conditional review.

I added a few reviewer commits. There is still a merge conflict with 6.9.rc0 caused by #17715.

Here are my other comments.

1. Introduction
   • I suggest to add a section heading before the note box (e.g. "Creation of Growth Groups") and to downgrade the note box to be an introductory paragraph of this section.
   • Last sentence: "It is mathematically nonsense": explain how the order of factors of a single variable matters.
2. Variable.__init__: ValueError "is not a valid name": not tested
3. Variable.extract_variable_names:
   • I am surprised that a more or less complete symbolic expression parser is needed here. Would it not be simpler to use SR(s) and then call .variables(), possibly on subexpressions in order to detect duplicates? It seems that SR(s) would create the symbolic variables on the fly, but does not inject them into the global name space, so this seems to be what is needed here.
   • I do not think the following is intentional:

     sage: Variable.extract_variable_names('a + (b + c) + d')
     ('b', 'c', 'd')
     

   • Why does the regular expression for number contain a $ but no ^?
4. GenericGrowthGroup.gens_monomial: Replace "is only implemented for" by "must be implemented in"
5. MonomialGrowthGroup: Is the following intentionally allowed:

   sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup
   sage: MonomialGrowthGroup(ZZ, 'x+y')
   Growth Group x+y^ZZ
   

6. MonomialGrowthGroup._convert_:
   • Is the following intentional:

     sage: import sage.rings.asymptotic.growth_group as agg
     sage: P = agg.MonomialGrowthGroup(ZZ, 'x')
     sage: P(1)
     1
     sage: P('x^2')
     x^2
     sage: P('1')
     Traceback (most recent call last):
     ...
     ValueError: Cannot convert 1.
     sage: G('x^)42(')
     x^42
     

   • As in 3a, couldn't the string parsing be done by the symbolic ring?
7. GrowthGroupFactory.create_key_and_extra_argument: Again, my suggestion is to delegate the string parsing to the symbolic ring. Note that SR('x^ZZ') happily accepts ZZ as a variable, so I imagine that postprocessing here would not involve big problems. I do not read this string parser here before the decision on its eventual fate.
8. Add one or more links from growth_group.py to growth_group_cartesian.py.
9. CartesianProductFactory:
   • indicate (somewhere, probably at a more prominent place) what order is chosen automatically (apparently, lexicographic if the variables are equal, component-wise otherwise). That would also explain why order does matter (cf. 1b).
   • the example with "do not have disjoint variables" is somewhat puzzeling, because the cartesian product of A and B was allowed.
   • (continuation of b while reading the code): apparently, sets of variables of the factors must be equal or disjoint.
   • mark doctests as indirect
10. GenericProduct: mark doctests as indirect.
11. Check links ~sage.sets.cartesian_product.CartesianProductPosets and sage.sets.cartesian_product.CartesianProductPosets.Element (do not work for me, possibly time intensive recreation of documentation would help).
12. GenericProduct._coerce_map_from_: don't the factors coerce into the product?

    sage: from sage.rings.asymptotic.growth_group import GrowthGroup
    sage: G = GrowthGroup('x^ZZ')
    sage: H = GrowthGroup('log(x)^ZZ')
    sage: K = cartesian_product([G, H])
    sage: K.has_coerce_map_from(G)
    False
    sage: K.has_coerce_map_from(H)
    False
    

13. Expand documentation of UnivariateProduct and MultivariateProduct: at least, include a link to GenericProduct and explain the choice of order.

---

New commits:

​59430d8	Trac #18587: remove redundant doctest
​f11377d	Trac #18587: minor language issues
​894e3a8	Trac #18587: Fix ReSt errors
​61085d0	Trac #18587: add heading "Classes and Methods"
​6fefead	Trac #18587: Fix minor errors

[behackl]

Merged 6.9.rc0 into this branch.

---

Last 10 new commits:

​ca5da4a	Merge branch 't/18930/asy/growthGroup-factory' into t/18587/asy/growth-group-cartesian
​ac80aeb	add growth_group_cartesian to index
​55c78e2	Merge branch 'asy/growthGroup-factory' into asy/growth-group-cartesian
​4a6174f	improved a short description
​59430d8	Trac #18587: remove redundant doctest
​f11377d	Trac #18587: minor language issues
​894e3a8	Trac #18587: Fix ReSt errors
​61085d0	Trac #18587: add heading "Classes and Methods"
​6fefead	Trac #18587: Fix minor errors
​f7e917f	Merge tag '6.9.rc0' into asy/growth-group-cartesian

[git]

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

​d34fa05	Merge branch 'cat/cartesian-product-posets' into asy/growth-group-cartesian
​9fcf771	extended introduction (comment 1)
​125c0c4	fix imports and take care of changes in #18223
​dc2504d	cartesian_product doctests: indirect (comments 9/10)
​665f2ba	improve documentation (CartesianProductFactory,
​26eb89c	remove unreachable ValueError (comment 2)
​0887284	extract_variable_names: let SR parse (comment 3)
​d35c406	fix doctest
​9528dfe	language (comment 4)
​f88d3ea	MonomialGrowthGroup._convert_: let SR parse string + take care of '1' (comment 6)

[behackl]

Replying to cheuberg:

I reviewed this ticket, but without reviewing the dependency on #18223, so consider this as a conditional review.

I added a few reviewer commits. There is still a merge conflict with 6.9.rc0 caused by #17715.

Hello Clemens! Thank you for your review!

The merge conflict with 6.9.rc0 has been resolved.

Here are my other comments.

1. Introduction
   • I suggest to add a section heading before the note box (e.g. "Creation of Growth Groups") and to downgrade the note box to be an introductory paragraph of this section.
   • Last sentence: "It is mathematically nonsense": explain how the order of factors of a single variable matters.

Done and done.

2. Variable.__init__: ValueError "is not a valid name": not tested

Removed this particular piece of code; the check is not necessary: the parser only allows strings that are valid identifiers (see my answer to 3.).

3. Variable.extract_variable_names:
   • I am surprised that a more or less complete symbolic expression parser is needed here. Would it not be simpler to use SR(s) and then call .variables(), possibly on subexpressions in order to detect duplicates? It seems that SR(s) would create the symbolic variables on the fly, but does not inject them into the global name space, so this seems to be what is needed here.

Changed this parser to the symbolic ring.

• I do not think the following is intentional:

  sage: Variable.extract_variable_names('a + (b + c) + d')
  ('b', 'c', 'd')
  

Indeed, this was not intentional. With the symbolic ring as the variable parser, this does not happen. I've added this as a doctest.

• Why does the regular expression for number contain a $ but no ^?

This is now irrelevant.

4. GenericGrowthGroup.gens_monomial: Replace "is only implemented for" by "must be implemented in"

Done.

5. MonomialGrowthGroup: Is the following intentionally allowed:

   sage: from sage.rings.asymptotic.growth_group import MonomialGrowthGroup
   sage: MonomialGrowthGroup(ZZ, 'x+y')
   Growth Group x+y^ZZ
   

Yes, this is intentional. On this ticket, the representation is ugly, but this is fixed in #19083.

6. MonomialGrowthGroup._convert_:
   • Is the following intentional:

     sage: import sage.rings.asymptotic.growth_group as agg
     sage: P = agg.MonomialGrowthGroup(ZZ, 'x')
     sage: P(1)
     1
     sage: P('x^2')
     x^2
     sage: P('1')
     Traceback (most recent call last):
     ...
     ValueError: Cannot convert 1.
     sage: G('x^)42(')
     x^42
     

The first two statements work as intended. The others are fixed here.

• As in 3a, couldn't the string parsing be done by the symbolic ring?

Yes. Done.

7. GrowthGroupFactory.create_key_and_extra_argument: Again, my suggestion is to delegate the string parsing to the symbolic ring. Note that SR('x^ZZ') happily accepts ZZ as a variable, so I imagine that postprocessing here would not involve big problems. I do not read this string parser here before the decision on its eventual fate.

Unfortunately, I think that this should not be parsed by the symbolic ring: the cartesian product which we model with * is not commutative: if the same variable is used, the growth groups are ordered lexicographically. By using the symbolic ring, the input order might be destroyed/ignored.

8. Add one or more links from growth_group.py to growth_group_cartesian.py.

We took extensive care with respect to the documentation on #19083. There, some links have been added.

9. CartesianProductFactory:
   • indicate (somewhere, probably at a more prominent place) what order is chosen automatically (apparently, lexicographic if the variables are equal, component-wise otherwise). That would also explain why order does matter (cf. 1b).

I've added a note-block to the docstring of the class.

• the example with "do not have disjoint variables" is somewhat puzzeling, because the cartesian product of A and B was allowed.

I understand the confusion. However, I think that the error message is quite helpful in this case:

sage: cartesian_product([A, E]); G
Traceback (most recent call last):
...
ValueError: Growth groups (Growth Group x^ZZ, Growth Group x^ZZ * y^ZZ) do not have pairwise disjoint variables.

Mainly, this is because the cartesian product cannot decide which order to use in this case. Also, I think that we should restrict building cartesian products of growth groups such that a factor may only occur once (currently, x^ZZ * x^ZZ is possible). I'll discuss this with Daniel.

• (continuation of b while reading the code): apparently, sets of variables of the factors must be equal or disjoint.

I've added this remark to the note-block in the docstring of the factory.

• mark doctests as indirect

Done.

10. GenericProduct: mark doctests as indirect.

Done.

11. Check links ~sage.sets.cartesian_product.CartesianProductPosets and sage.sets.cartesian_product.CartesianProductPosets.Element (do not work for me, possibly time intensive recreation of documentation would help).

I corrected the links (we shifted some code in #18223), they work for me now -- however, that should not have affected you. (Sometimes, the documentation really wants to be built from scratch. :-))

12. GenericProduct._coerce_map_from_: don't the factors coerce into the product?

    sage: from sage.rings.asymptotic.growth_group import GrowthGroup
    sage: G = GrowthGroup('x^ZZ')
    sage: H = GrowthGroup('log(x)^ZZ')
    sage: K = cartesian_product([G, H])
    sage: K.has_coerce_map_from(G)
    False
    sage: K.has_coerce_map_from(H)
    False
    

No, not in general. However, due to our special structure (and as soon as we actually disallow copies of the same growth group in a cartesian product) this can be implemented. This should be handled in our coercion ticket, #19073.

13. Expand documentation of UnivariateProduct and MultivariateProduct: at least, include a link to GenericProduct and explain the choice of order.

Done.

[cheuberg]

Replying to behackl:

Replying to cheuberg:

2. Variable.__init__: ValueError "is not a valid name": not tested

Removed this particular piece of code; the check is not necessary: the parser only allows strings that are valid identifiers (see my answer to 3.).

I do not think so: extract_variable_names is only called when repr is None, the removed code was only called when repr is not None. Indeed, the following does now work:

sage: from sage.rings.asymptotic.growth_group import Variable
sage: Variable("(:-)", repr="icecream").var_bases
('(:-)',)

7. GrowthGroupFactory.create_key_and_extra_argument: Again, my suggestion is to delegate the string parsing to the symbolic ring. Note that SR('x^ZZ') happily accepts ZZ as a variable, so I imagine that postprocessing here would not involve big problems. I do not read this string parser here before the decision on its eventual fate.

Unfortunately, I think that this should not be parsed by the symbolic ring: the cartesian product which we model with * is not commutative: if the same variable is used, the growth groups are ordered lexicographically. By using the symbolic ring, the input order might be destroyed/ignored.

I see.

The current code makes some effort to recognize ** in create_key_and_extra_args, but ** is not recognized in create_object.

9. CartesianProductFactory:
   • the example with "do not have disjoint variables" is somewhat puzzeling, because the cartesian product of A and B was allowed.

I understand the confusion. However, I think that the error message is quite helpful in this case:

sage: cartesian_product([A, E]); G
Traceback (most recent call last):
...
ValueError: Growth groups (Growth Group x^ZZ, Growth Group x^ZZ * y^ZZ) do not have pairwise disjoint variables.

Mainly, this is because the cartesian product cannot decide which order to use in this case.

perhaps rephrase error message along the lines of "factors must have equal or disjoint variables"?

Also, I think that we should restrict building cartesian products of growth groups such that a factor may only occur once (currently, x^ZZ * x^ZZ is possible). I'll discuss this with Daniel.

that might be hard.

[git]

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

​dea3c96	Trac #18587: additional doctest
​6d3e4f4	Trac #18587: nicer output of one link target

[behackl]

Replying to cheuberg:

Replying to behackl:

Replying to cheuberg:

2. Variable.__init__: ValueError "is not a valid name": not tested

Removed this particular piece of code; the check is not necessary: the parser only allows strings that are valid identifiers (see my answer to 3.).

I do not think so: extract_variable_names is only called when repr is None, the removed code was only called when repr is not None. Indeed, the following does now work:

sage: from sage.rings.asymptotic.growth_group import Variable
sage: Variable("(:-)", repr="icecream").var_bases
('(:-)',)

Mea culpa, I misread the code. I've reverted the commit.

7. GrowthGroupFactory.create_key_and_extra_argument: Again, my suggestion is to delegate the string parsing to the symbolic ring. Note that SR('x^ZZ') happily accepts ZZ as a variable, so I imagine that postprocessing here would not involve big problems. I do not read this string parser here before the decision on its eventual fate.

Unfortunately, I think that this should not be parsed by the symbolic ring: the cartesian product which we model with * is not commutative: if the same variable is used, the growth groups are ordered lexicographically. By using the symbolic ring, the input order might be destroyed/ignored.

I see.

The current code makes some effort to recognize ** in create_key_and_extra_args, but ** is not recognized in create_object.

Minor discrepancies like this are fixed on the cleanup ticket #19083. No need to introduce additional merge conflicts here.

9. CartesianProductFactory:
   • the example with "do not have disjoint variables" is somewhat puzzeling, because the cartesian product of A and B was allowed.

I understand the confusion. However, I think that the error message is quite helpful in this case:

sage: cartesian_product([A, E]); G
Traceback (most recent call last):
...
ValueError: Growth groups (Growth Group x^ZZ, Growth Group x^ZZ * y^ZZ) do not have pairwise disjoint variables.

Mainly, this is because the cartesian product cannot decide which order to use in this case.

perhaps rephrase error message along the lines of "factors must have equal or disjoint variables"?

Done; improved the error message.

Also, I think that we should restrict building cartesian products of growth groups such that a factor may only occur once (currently, x^ZZ * x^ZZ is possible). I'll discuss this with Daniel.

that might be hard.

Turns out that this is very true. We will start with disallowing certain products like x^ZZ * x^ZZ and x^ZZ * x^QQ in the cleanup ticket. Altering the factory here only produces more merge conflicts with #19083 (the entire factory is rewritten there, meaning that the code would have to be written twice).

---

New commits:

​66759bb	Revert "remove unreachable ValueError (comment 2)"
​0642564	doctest added
​7f209ea	improved error message (equal or disjoint var.)

[cheuberg]

Replying to behackl:

Replying to cheuberg:

The current code makes some effort to recognize ** in create_key_and_extra_args, but ** is not recognized in create_object.

Minor discrepancies like this are fixed on the cleanup ticket #19083. No need to introduce additional merge conflicts here.

ok.

Also, I think that we should restrict building cartesian products of growth groups such that a factor may only occur once (currently, x^ZZ * x^ZZ is possible). I'll discuss this with Daniel.

that might be hard.

Turns out that this is very true. We will start with disallowing certain products like x^ZZ * x^ZZ and x^ZZ * x^QQ in the cleanup ticket. Altering the factory here only produces more merge conflicts with #19083 (the entire factory is rewritten there, meaning that the code would have to be written twice).

ok.

This is a conditional positive review from my side: conditional on the dependency #18223.

[dkrenn]

Replying to cheuberg:

This is a conditional positive review from my side: conditional on the dependency #18223.

Merged in #18223 and adapted code. Please cross-review...and set it to positive ;)

---

New commits:

​70aa9c4	rename CartesianProductPosets to CartesianProductPoset
​f21990d	code-simplify CartesianProduct assignment
​8f9a619	add a doctest dealing with coercion while comparing
​3b923b7	Merge branch 'u/dkrenn/cat/cartesian-product-posets' of trac.sagemath.org:sage into t/18587/asy/growth-group-cartesian
​74547e6	fix code after changes by previous merge

[cheuberg]

Replying to dkrenn:

Replying to cheuberg:

This is a conditional positive review from my side: conditional on the dependency #18223.

Merged in #18223 and adapted code. Please cross-review...and set it to positive ;)

Done.

[vbraun]

This ticket depends on a "duplicate" ticket. It will not be merged until #18586 is merged, i.e. most likely never.