# Graded algebras with maximal degree

Reported by: Owned by: Michael Jung major sage-9.5 algebra Travis Scrimshaw, Matthias Köppe, Trevor Karn, John Palmieri Michael Jung Travis Scrimshaw N/A 970d295 970d2950fad3092bb100372e537f73308fb6c978 #32315

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.

Follow-up: #32365

### comment:2 Changed 17 months ago by git

Commit: → 0813d34634788e5e2fc16761fc3e41a1a89ab9ba

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

 ​0813d34 Trac #32272: add commutative graded algebras with finite degree

### comment:3 Changed 17 months ago by git

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 git

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 git

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

 ​8d2874e Trac #32272: extend docstring ​28c9889 Trac #32272: add super-algebra structure ​f09f9ec Trac #32272: add ngens method

### comment:6 Changed 17 months ago by Michael Jung

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?

Last edited 17 months ago by Michael Jung (previous) (diff)

### comment:8 Changed 17 months ago by Michael Jung

Description: modified (diff)

### comment:9 Changed 17 months ago by git

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

 ​188a5d4 Trac #32272: implement super-commutativity + rename file

### comment:11 Changed 17 months ago by git

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 git

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 Michael Jung

Authors: → Michael Jung new → needs_review

Ready for review. If you have more ideas for doctests, please let me know.

### comment:14 Changed 17 months ago by git

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 Travis Scrimshaw

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 Michael Jung

Dependencies: → #32315

### comment:17 Changed 17 months ago by Michael Jung

With your proposal, it is a very small step to a general implementation, i.e. including the non-bounded 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?

Last edited 17 months ago by Michael Jung (previous) (diff)

### comment:18 Changed 16 months ago by git

Commit: 8d641f190c5922ed5381e81a0c6a1149f20981c8 → 6a320a05234d78cf4aea5c8031eb99cab7b18ac9

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

 ​d22ee9a Trac #32315: support iteration and enumerated sets ​16c4737 Trac #32272: allow infinite max degree ​6a320a0 Trac #32272: fix docstring

### comment:20 Changed 16 months ago by Michael Jung

Description: modified (diff) Finitely generated graded algebras with finite degree → Graded algebras with maximal degree

### comment:21 Changed 16 months ago by Michael Jung

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 Michael Jung

Coercions from infinite to finite maximal degrees, and coercions between both different implementations will be done in a follow-up.

Last edited 16 months ago by Michael Jung (previous) (diff)

### comment:23 Changed 16 months ago by git

Commit: 6a320a05234d78cf4aea5c8031eb99cab7b18ac9 → c1d4fceb9cffd4236d9ee94282f12d9bb7065529

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

 ​c1d4fce Trac #32272: fix rst file + rename module

### comment:24 Changed 16 months ago by Michael Jung

This should fix the patchbot complaints.

### comment:25 Changed 16 months ago by git

Commit: c1d4fceb9cffd4236d9ee94282f12d9bb7065529 → 25e6b1da8a41635449797df1b48990096e03f9f2

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

 ​25e6b1d Trac #32272: fix doctest

### comment:26 Changed 16 months ago by Michael Jung

Patchbot is morally green now. :)

### comment:28 follow-up:  29 Changed 16 months ago by John Palmieri

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 ; follow-up:  30 Changed 16 months ago by Michael Jung

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"?

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 ; follow-up:  31 Changed 16 months ago by John Palmieri

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"?

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.

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 16 months ago by Michael Jung

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/quotients-of-exterior-algebras/.

Last edited 16 months ago by Michael Jung (previous) (diff)

### comment:32 Changed 16 months ago by Michael Jung

In summary, the main differences to the other implementation are:

• not possible to define (working) relations and quotients
• no differentials
• support for SR and other arbitrary fields
• maximal degree (relation)
Last edited 16 months ago by Michael Jung (previous) (diff)

### comment:33 Changed 16 months ago by Michael Jung

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.

Last edited 16 months ago by Michael Jung (previous) (diff)

### comment:34 Changed 16 months ago by Michael Jung

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.

Last edited 16 months ago by Michael Jung (previous) (diff)

### comment:35 Changed 16 months ago by Matthias Köppe

Milestone: sage-9.4 → sage-9.5

### comment:36 Changed 16 months ago by John Palmieri

Milestone: sage-9.5 → sage-9.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 John Palmieri

Milestone: sage-9.4 → sage-9.5

### comment:38 Changed 16 months ago by Michael Jung

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 Michael Jung

Description: modified (diff)

### comment:40 Changed 16 months ago by Michael Jung

Description: modified (diff)

### comment:41 Changed 16 months ago by git

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 Michael Jung

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 follow-up:  44 Changed 16 months ago by Travis Scrimshaw

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 16 months ago by Michael Jung

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.

Last edited 16 months ago by Michael Jung (previous) (diff)

### comment:45 Changed 16 months ago by Michael Jung

Patchbot seems okay.

### comment:46 Changed 16 months ago by Travis Scrimshaw

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 git

Commit: 5a4c7acec7fb95fac21a6367b364774215ace3fa → 7328d50f792f1a4c964ce9a841b04a3a7dddb311

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

 ​7328d50 Trac #32272: remove unused imports

### comment:48 Changed 16 months ago by Travis Scrimshaw

Status: needs_review → positive_review

Thank you.

### comment:49 Changed 16 months ago by Michael Jung

Thank you for the review.

### comment:50 follow-up:  51 Changed 16 months ago by Samuel Lelièvre

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 16 months ago by Michael Jung

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 15 months ago by Volker Braun

Status: positive_review → needs_work

PDF docs don't build

### comment:53 Changed 15 months ago by Michael Jung

Weird. What's the issue here?

### comment:54 Changed 15 months ago by Travis Scrimshaw

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 git

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

 ​970d295 Trac #30473: unicode -> latex for cup product

### comment:56 Changed 15 months ago by Michael Jung

That should be it.

### comment:57 Changed 15 months ago by Michael Jung

Status: needs_work → needs_review

### comment:58 Changed 15 months ago by Michael Jung

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 Travis Scrimshaw

Status: needs_review → positive_review

Perhaps, but that should be its own ticket.