Opened 10 months ago
Closed 8 months ago
#32272 closed enhancement (fixed)
Graded algebras with maximal degree
Reported by:  ghmjungmath  Owned by:  

Priority:  major  Milestone:  sage9.5 
Component:  algebra  Keywords:  
Cc:  tscrim, mkoeppe, tkarn, jhpalmieri  Merged in:  
Authors:  Michael Jung  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  970d295 (Commits, GitHub, GitLab)  Commit:  970d2950fad3092bb100372e537f73308fb6c978 
Dependencies:  #32315  Stopgaps: 
Description (last modified by )
We implement graded algebras with maximal finite degree. That is, each generator has a integer degree, and multiplications exceeding a fixed degree yield zero.
This implementation is for example useful in the case of certain cohomology rings (or subrings of such) over a field of finite dimensional CW or simplicial complexes. See for example #29581.
Followup: #32365
Change History (60)
comment:1 Changed 10 months ago by
 Branch set to u/ghmjungmath/finitely_generated_graded_algebras_with_finite_degree
comment:2 Changed 10 months ago by
 Commit set to 0813d34634788e5e2fc16761fc3e41a1a89ab9ba
comment:3 Changed 10 months ago by
 Commit changed from 0813d34634788e5e2fc16761fc3e41a1a89ab9ba to 7d54a50203582cb8f73c6e73e90dc73e4dc0659e
Branch pushed to git repo; I updated commit sha1. New commits:
7d54a50  #32272: rearrange docstring

comment:4 Changed 10 months ago by
 Commit changed from 7d54a50203582cb8f73c6e73e90dc73e4dc0659e to 2915d568cc22490eee28dfdb386540b6605c3f04
Branch pushed to git repo; I updated commit sha1. New commits:
2915d56  #32272: link to commutative_dga

comment:5 Changed 10 months ago by
 Commit changed from 2915d568cc22490eee28dfdb386540b6605c3f04 to f09f9ec7cc220af2a254fd19b03a55adb66d2611
comment:6 Changed 10 months ago by
(for the following see also https://groups.google.com/g/sagedevel/c/z5Y7BMwEUVk)
I have troubles constructing a quotient. Here is what happens without a ngens
method:
sage: from sage.algebras.commutative_graded_algebra_finite import FiniteGCAlgebra sage: A.<x,y,z> = FiniteGCAlgebra(QQ, degrees=(1,2,3), max_degree=6) sage: I = A.ideal(y^2) sage: A.quotient(I) Traceback (most recent call last) ... RuntimeError: Graded commutative algebra with generators ('x', 'y', 'z') in degrees (1, 2, 3) with maximal finite degree 6 still using old coercion framework
Adding a ngens
method on the other hand causes the quotients not to function properly:
sage: from sage.algebras.commutative_graded_algebra_finite import FiniteGCAlgebra sage: A.<x,y,z> = FiniteGCAlgebra(QQ, degrees=(1,2,3), max_degree=6) sage: I = A.ideal(y^2) sage: Q = A.quotient(I) sage: Q.gen(1)^2 ybar^2
The result, however, should be zero.
What am I doing wrong?
comment:7 Changed 10 months ago by
comment:8 Changed 10 months ago by
 Description modified (diff)
comment:9 Changed 10 months ago by
 Commit changed from f09f9ec7cc220af2a254fd19b03a55adb66d2611 to 188a5d43217b0fd6155bd04555170a746c91c45e
Branch pushed to git repo; I updated commit sha1. New commits:
188a5d4  Trac #32272: implement supercommutativity + rename file

comment:10 Changed 10 months ago by
 Cc tkarn added
comment:11 Changed 10 months ago by
 Commit changed from 188a5d43217b0fd6155bd04555170a746c91c45e to 40d39a1ff88d5fec64788f90cc9a8bd570eff3dd
Branch pushed to git repo; I updated commit sha1. New commits:
40d39a1  Trac #32272: add more doctests

comment:12 Changed 10 months ago by
 Commit changed from 40d39a1ff88d5fec64788f90cc9a8bd570eff3dd to 0231712c7b072118e1d5043640db0415c138cee3
Branch pushed to git repo; I updated commit sha1. New commits:
0231712  Trac #32272: docstring extended

comment:13 Changed 10 months ago by
 Status changed from new to needs_review
Ready for review. If you have more ideas for doctests, please let me know.
comment:14 Changed 10 months ago by
 Commit changed from 0231712c7b072118e1d5043640db0415c138cee3 to 8d641f190c5922ed5381e81a0c6a1149f20981c8
Branch pushed to git repo; I updated commit sha1. New commits:
8d641f1  Trac #32272: correct path in docstring

comment:15 Changed 10 months ago by
It would be better to have the keys be a filter applied to WeightedIntegerVectors
, so it returns a parent rather than the explicit list. That way you do not need to create this list upon creation of the parent nor store it in memory. You can use ConditionSet
from #32089 with a small extension to handle the case when its ambient set is a (finite?) enumerated set, or as a more stopgap that is already has what you need: FilteredCombinatorialClass
. (Note that ConditionSet
should be used as the replacement of this, which is de facto deprecated.)
This line is unnecessary:
Element = CombinatorialFreeModule.Element
comment:16 Changed 10 months ago by
 Dependencies set to #32315
comment:17 Changed 10 months ago by
With your proposal, it is a very small step to a general implementation, i.e. including the nonbounded case.
But then we would have two different implementations of the same algebra. How do we wanna deal with it? In particular, what should the globally available GradedCommutativeAlgebra
constructor return?
comment:18 Changed 10 months ago by
 Commit changed from 8d641f190c5922ed5381e81a0c6a1149f20981c8 to 6a320a05234d78cf4aea5c8031eb99cab7b18ac9
comment:19 Changed 10 months ago by
Ready for review again.
comment:20 Changed 10 months ago by
 Description modified (diff)
 Summary changed from Finitely generated graded algebras with finite degree to Graded algebras with maximal degree
comment:21 Changed 10 months ago by
The function GradedCommutativeAlgebra
returns this implementation if max_degree
is passed (including infinity) and the other implementation otherwise.
Moreover, I am a bit uncertain about the names of the file and the class. Better ideas are most welcome.
comment:22 Changed 10 months ago by
Coercions from infinite to finite maximal degrees, and coercions between both different implementations will be done in a followup.
comment:23 Changed 10 months ago by
 Commit changed from 6a320a05234d78cf4aea5c8031eb99cab7b18ac9 to c1d4fceb9cffd4236d9ee94282f12d9bb7065529
Branch pushed to git repo; I updated commit sha1. New commits:
c1d4fce  Trac #32272: fix rst file + rename module

comment:24 Changed 10 months ago by
This should fix the patchbot complaints.
comment:25 Changed 10 months ago by
 Commit changed from c1d4fceb9cffd4236d9ee94282f12d9bb7065529 to 25e6b1da8a41635449797df1b48990096e03f9f2
Branch pushed to git repo; I updated commit sha1. New commits:
25e6b1d  Trac #32272: fix doctest

comment:26 Changed 10 months ago by
Patchbot is morally green now. :)
comment:27 Changed 10 months ago by
 Cc jhpalmieri added
comment:28 followup: ↓ 29 Changed 10 months ago by
In the file commutative_graded_algebra.py
, the first line of the docstring for GCAlgebraWithMaxDegree
says "Graded commutative algebras." Shouldn't it say "Graded commutative algebras with a maximum degree"? Should this class inherit from GCAlgebra
? (GCAlgebra
would be my answer to your last question in comment:17.)
I notice that you mentioned ideals in a previous comment; was that issue ever resolved? If so, it would be good to add some examples. If not, if there are no ideals or relations possible with these, the documentation should say that. "The only relation in such an algebra is that any product above max_degree
is zero."
comment:29 in reply to: ↑ 28 ; followup: ↓ 30 Changed 10 months ago by
Replying to jhpalmieri:
In the file
commutative_graded_algebra.py
, the first line of the docstring forGCAlgebraWithMaxDegree
says "Graded commutative algebras." Shouldn't it say "Graded commutative algebras with a maximum degree"?
Yes, I think so. Though this implementation supports general graded commutative algebras.
Should this class inherit from
GCAlgebra
?
I don't think so. This implementation is basically different from what is done in commutative_dga
. This implementation now offers two benefits: it supports SR
as base field and a maximal degree.
(
GCAlgebra
would be my answer to your last question in comment:17.)
GCAlgebra
would be the same name as in commutative_dga
. So you think this is a good idea?
I notice that you mentioned ideals in a previous comment; was that issue ever resolved? If so, it would be good to add some examples. If not, if there are no ideals or relations possible with these, the documentation should say that.
No, the algebra apparently needs its own implementation of an ideal. A first lead into this direction yields #32249.
"The only relation in such an algebra is that any product above
max_degree
is zero."
What are you referring to?
comment:30 in reply to: ↑ 29 ; followup: ↓ 31 Changed 10 months ago by
Replying to ghmjungmath:
Replying to jhpalmieri:
In the file
commutative_graded_algebra.py
, the first line of the docstring forGCAlgebraWithMaxDegree
says "Graded commutative algebras." Shouldn't it say "Graded commutative algebras with a maximum degree"?Yes, I think so. Though this implementation supports general graded commutative algebras.
Should this class inherit from
GCAlgebra
?I don't think so. This implementation is basically different from what is done in
commutative_dga
. This implementation now offers two benefits: it supportsSR
as base field and a maximal degree.
I'm confused: are you creating a new class that duplicates and then enhances an existing class? Why not rewrite the old class instead? In other words, why have two implementations of graded commutative algebras?
I notice that you mentioned ideals in a previous comment; was that issue ever resolved? If so, it would be good to add some examples. If not, if there are no ideals or relations possible with these, the documentation should say that.
No, the algebra apparently needs its own implementation of an ideal. A first lead into this direction yields #32249.
"The only relation in such an algebra is that any product above
max_degree
is zero."What are you referring to?
I was suggesting documentation in case it is not possible to impose relations on your class of algebras.
comment:31 in reply to: ↑ 30 Changed 10 months ago by
Replying to jhpalmieri:
I'm confused: are you creating a new class that duplicates and then enhances an existing class? Why not rewrite the old class instead? In other words, why have two implementations of graded commutative algebras?
First of all, this was not planned. I only wanted to implement gc algebras with finite degree. But it turned out that together with #32315, it was a small step to infinite degrees.
Imho, rewriting would be way too much work for a questionable benefit. Both classes have different advantages and disadvantages.
If I'm not mistaken, different implementations of the same mathematical objects are not uncommon in Sage...
I'm open to suggestions though, because I agree that this is not optimal.
I was suggesting documentation in case it is not possible to impose relations on your class of algebras.
Well, here it gets strange. You can define ideals by default, ie relations. But then the generic implementation of the quotient just gives nonsense.
This is not the only class having this problem. In other classes, this is also undocumented. See #32291 and https://ask.sagemath.org/question/56243/quotientsofexterioralgebras/.
comment:32 Changed 10 months ago by
In summary, the main differences to the other implementation are:
 not possible to define (working) relations and quotients
 no differentials
 no multigrading
 support for
SR
and other arbitrary fields  maximal degree (relation)
comment:33 Changed 10 months ago by
Alternatively, we should add SR
support, which currently produces the following error:
sage: A.<x,y,z> = GradedCommutativeAlgebra(SR, degrees=(1,2,3)) Traceback (most recent call last): ... TypeError: Cannot call Singular function 'nc_algebra' with ring parameter of type '<class 'sage.rings.polynomial.multi_polynomial_ring.MPolynomialRing_polydict_with_category'>'
and getting finite degrees using ideals. But honestly, I don't see how to use ideals in an efficient fashion this way; especially since Groebner bases are not supported so far. But even with Groebner bases, the list of generators of that ideal is not easy to create (without redundancies) and can get very long.
comment:34 Changed 9 months ago by
How do we want to proceed now?
If this ticket is on hold, I would like to proceed in #29581 with a tentative version of this code restricted only to characteristic cohomology classes.
comment:35 Changed 9 months ago by
 Milestone changed from sage9.4 to sage9.5
comment:36 Changed 9 months ago by
 Milestone changed from sage9.5 to sage9.4
Changing the milestone gives us some more time to think about it. I personally would prefer a more narrow use of this, and then we can try to find a unified approach for graded commutative algebras that combines the features of both.
comment:37 Changed 9 months ago by
 Milestone changed from sage9.4 to sage9.5
comment:38 Changed 9 months ago by
Thank you for the feedback. Then let's restrict this class to finite degrees only and think about the rest later.
I'll make the changes accordingly.
Otherwise, do you have further suggestions?
comment:39 Changed 9 months ago by
 Description modified (diff)
comment:40 Changed 9 months ago by
 Description modified (diff)
comment:41 Changed 9 months ago by
 Commit changed from 25e6b1da8a41635449797df1b48990096e03f9f2 to 5a4c7acec7fb95fac21a6367b364774215ace3fa
Branch pushed to git repo; I updated commit sha1. New commits:
5a4c7ac  Trac #32272: narrow to finite dimensions

comment:42 Changed 9 months ago by
Here we go. Ready for review again.
Though we have some time now, I'd appreciate a positive review soon, so that I can proceed working on #29581. The latter ticket is necessary for a project I'm currently running.
comment:43 followup: ↓ 44 Changed 9 months ago by
At some point, this (and perhaps its unbounded degree variant) should have a more optimized version of the multiplication done in Cython rather than relying on plural or product_on_basis
framework (there are a lot of extra intermediate function calls being done).
I suspect the exterior algebra implementation will remain faster (which could be meld together with a purely odd degree version) because of the data structure for encoding the elements. Nevertheless, it would be interesting to compare with a "natural" encoding of the monomials by the degree of the generators. Perhaps the ideal way to do this would be to encode a basis element by a pair of the degrees of the evens with a subset of the odd indices (ordered as a tuple; cf. the exterior algebra implementation).
However, all of that is for another ticket.
comment:44 in reply to: ↑ 43 Changed 9 months ago by
Replying to tscrim:
At some point, this (and perhaps its unbounded degree variant) should have a more optimized version of the multiplication done in Cython rather than relying on plural or
product_on_basis
framework (there are a lot of extra intermediate function calls being done).
Indeed!
I suspect the exterior algebra implementation will remain faster (which could be meld together with a purely odd degree version) because of the data structure for encoding the elements. Nevertheless, it would be interesting to compare with a "natural" encoding of the monomials by the degree of the generators. Perhaps the ideal way to do this would be to encode a basis element by a pair of the degrees of the evens with a subset of the odd indices (ordered as a tuple; cf. the exterior algebra implementation).
Separating the generators into odd and even degree, and performing the computations on those sounds like the most optimal solution to me. Besides, together with Cythonizing, this could give an extremely efficient implementation. I can imagine that all those ideals and relations currently used in commutative_dga
slow down computations a bit.
However, all of that is for another ticket.
Exactly.
comment:45 Changed 9 months ago by
Patchbot seems okay.
comment:46 Changed 9 months ago by
 Reviewers set to Travis Scrimshaw
Since this functionality is distinct from the general cga code, I think for now we can go ahead with this ticket.
One trivial pyflakes thing before a positive review:
src/sage/algebras/finite_gca.py:28:1 'sage.rings.infinity.infinity' imported but unused
Once fixed, you can set a positive review unless somebody else objects.
comment:47 Changed 9 months ago by
 Commit changed from 5a4c7acec7fb95fac21a6367b364774215ace3fa to 7328d50f792f1a4c964ce9a841b04a3a7dddb311
Branch pushed to git repo; I updated commit sha1. New commits:
7328d50  Trac #32272: remove unused imports

comment:49 Changed 9 months ago by
Thank you for the review.
comment:50 followup: ↓ 51 Changed 9 months ago by
Nitpicking suggestion, feel free to ignore.
Please remove trailing blank lines at the end of docstrings.
While reST blocks usually need a final blank line, it is not the case at the end of a docstring.
See the template at:
where the final TESTS block is followed
directly by """
with no extra blank line.
comment:51 in reply to: ↑ 50 Changed 9 months ago by
Replying to slelievre:
Nitpicking suggestion, feel free to ignore.
Please remove trailing blank lines at the end of docstrings.
While reST blocks usually need a final blank line, it is not the case at the end of a docstring.
See the template at:
where the final TESTS block is followed directly by
"""
with no extra blank line.
Thank you! That is good to know. I will keep an eye on this in the future!
comment:52 Changed 9 months ago by
 Status changed from positive_review to needs_work
PDF docs don't build
comment:53 Changed 9 months ago by
Weird. What's the issue here?
comment:54 Changed 9 months ago by
Perhaps its the $
in the \text
with an autoreplace done to a backtick `
? Are you able to build the PDF docs?
comment:55 Changed 9 months ago by
 Commit changed from 7328d50f792f1a4c964ce9a841b04a3a7dddb311 to 970d2950fad3092bb100372e537f73308fb6c978
Branch pushed to git repo; I updated commit sha1. New commits:
970d295  Trac #30473: unicode > latex for cup product

comment:56 Changed 9 months ago by
That should be it.
comment:57 Changed 9 months ago by
 Status changed from needs_work to needs_review
comment:58 Changed 9 months ago by
Patchbot is green except for unrelated pyflakes errors in src/sage/docs/conf.py
. Those imports should be removed at some point, no?
comment:59 Changed 9 months ago by
 Status changed from needs_review to positive_review
Perhaps, but that should be its own ticket.
comment:60 Changed 8 months ago by
 Branch changed from u/ghmjungmath/finitely_generated_graded_algebras_with_finite_degree to 970d2950fad3092bb100372e537f73308fb6c978
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
Trac #32272: add commutative graded algebras with finite degree