Opened 17 months ago
Closed 15 months ago
#32272 closed enhancement (fixed)
Graded algebras with maximal degree
Reported by:  Michael Jung  Owned by:  

Priority:  major  Milestone:  sage9.5 
Component:  algebra  Keywords:  
Cc:  Travis Scrimshaw, Matthias Köppe, Trevor Karn, John Palmieri  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 17 months ago by
Branch:  → u/ghmjungmath/finitely_generated_graded_algebras_with_finite_degree 

comment:2 Changed 17 months ago by
Commit:  → 0813d34634788e5e2fc16761fc3e41a1a89ab9ba 

comment:3 Changed 17 months ago by
Commit:  0813d34634788e5e2fc16761fc3e41a1a89ab9ba → 7d54a50203582cb8f73c6e73e90dc73e4dc0659e 

Branch pushed to git repo; I updated commit sha1. New commits:
7d54a50  #32272: rearrange docstring

comment:4 Changed 17 months ago by
Commit:  7d54a50203582cb8f73c6e73e90dc73e4dc0659e → 2915d568cc22490eee28dfdb386540b6605c3f04 

Branch pushed to git repo; I updated commit sha1. New commits:
2915d56  #32272: link to commutative_dga

comment:5 Changed 17 months ago by
Commit:  2915d568cc22490eee28dfdb386540b6605c3f04 → f09f9ec7cc220af2a254fd19b03a55adb66d2611 

comment:6 Changed 17 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 17 months ago by
comment:8 Changed 17 months ago by
Description:  modified (diff) 

comment:9 Changed 17 months ago by
Commit:  f09f9ec7cc220af2a254fd19b03a55adb66d2611 → 188a5d43217b0fd6155bd04555170a746c91c45e 

Branch pushed to git repo; I updated commit sha1. New commits:
188a5d4  Trac #32272: implement supercommutativity + rename file

comment:10 Changed 17 months ago by
Cc:  Trevor Karn added 

comment:11 Changed 17 months ago by
Commit:  188a5d43217b0fd6155bd04555170a746c91c45e → 40d39a1ff88d5fec64788f90cc9a8bd570eff3dd 

Branch pushed to git repo; I updated commit sha1. New commits:
40d39a1  Trac #32272: add more doctests

comment:12 Changed 17 months ago by
Commit:  40d39a1ff88d5fec64788f90cc9a8bd570eff3dd → 0231712c7b072118e1d5043640db0415c138cee3 

Branch pushed to git repo; I updated commit sha1. New commits:
0231712  Trac #32272: docstring extended

comment:13 Changed 17 months ago by
Authors:  → Michael Jung 

Status:  new → needs_review 
Ready for review. If you have more ideas for doctests, please let me know.
comment:14 Changed 17 months ago by
Commit:  0231712c7b072118e1d5043640db0415c138cee3 → 8d641f190c5922ed5381e81a0c6a1149f20981c8 

Branch pushed to git repo; I updated commit sha1. New commits:
8d641f1  Trac #32272: correct path in docstring

comment:15 Changed 17 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 17 months ago by
Dependencies:  → #32315 

comment:17 Changed 17 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 16 months ago by
Commit:  8d641f190c5922ed5381e81a0c6a1149f20981c8 → 6a320a05234d78cf4aea5c8031eb99cab7b18ac9 

comment:20 Changed 16 months ago by
Description:  modified (diff) 

Summary:  Finitely generated graded algebras with finite degree → Graded algebras with maximal degree 
comment:21 Changed 16 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 16 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 16 months ago by
Commit:  6a320a05234d78cf4aea5c8031eb99cab7b18ac9 → c1d4fceb9cffd4236d9ee94282f12d9bb7065529 

Branch pushed to git repo; I updated commit sha1. New commits:
c1d4fce  Trac #32272: fix rst file + rename module

comment:25 Changed 16 months ago by
Commit:  c1d4fceb9cffd4236d9ee94282f12d9bb7065529 → 25e6b1da8a41635449797df1b48990096e03f9f2 

Branch pushed to git repo; I updated commit sha1. New commits:
25e6b1d  Trac #32272: fix doctest

comment:27 Changed 16 months ago by
Cc:  John Palmieri added 

comment:28 followup: 29 Changed 16 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 followup: 30 Changed 16 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 followup: 31 Changed 16 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 Changed 16 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 16 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 16 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 16 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 16 months ago by
Milestone:  sage9.4 → sage9.5 

comment:36 Changed 16 months ago by
Milestone:  sage9.5 → 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 16 months ago by
Milestone:  sage9.4 → sage9.5 

comment:38 Changed 16 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 16 months ago by
Description:  modified (diff) 

comment:40 Changed 16 months ago by
Description:  modified (diff) 

comment:41 Changed 16 months ago by
Commit:  25e6b1da8a41635449797df1b48990096e03f9f2 → 5a4c7acec7fb95fac21a6367b364774215ace3fa 

Branch pushed to git repo; I updated commit sha1. New commits:
5a4c7ac  Trac #32272: narrow to finite dimensions

comment:42 Changed 16 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 16 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 Changed 16 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:46 Changed 16 months ago by
Reviewers:  → 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 16 months ago by
Commit:  5a4c7acec7fb95fac21a6367b364774215ace3fa → 7328d50f792f1a4c964ce9a841b04a3a7dddb311 

Branch pushed to git repo; I updated commit sha1. New commits:
7328d50  Trac #32272: remove unused imports

comment:50 followup: 51 Changed 16 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 Changed 16 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:54 Changed 15 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 15 months ago by
Commit:  7328d50f792f1a4c964ce9a841b04a3a7dddb311 → 970d2950fad3092bb100372e537f73308fb6c978 

Branch pushed to git repo; I updated commit sha1. New commits:
970d295  Trac #30473: unicode > latex for cup product

comment:57 Changed 15 months ago by
Status:  needs_work → needs_review 

comment:58 Changed 15 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 15 months ago by
Status:  needs_review → positive_review 

Perhaps, but that should be its own ticket.
comment:60 Changed 15 months ago by
Branch:  u/ghmjungmath/finitely_generated_graded_algebras_with_finite_degree → 970d2950fad3092bb100372e537f73308fb6c978 

Resolution:  → fixed 
Status:  positive_review → 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