#32272 closed enhancement (fixed)

Graded algebras with maximal degree

Reported by: Michael Jung Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description (last modified by Michael Jung)

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

Change History (60)

comment:1 Changed 17 months ago by Michael Jung

Branch: u/gh-mjungmath/finitely_generated_graded_algebras_with_finite_degree

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:

0813d34Trac #32272: add commutative graded algebras with finite degree

comment:3 Changed 17 months ago by git

Commit: 0813d34634788e5e2fc16761fc3e41a1a89ab9ba7d54a50203582cb8f73c6e73e90dc73e4dc0659e

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

7d54a50#32272: rearrange docstring

comment:4 Changed 17 months ago by git

Commit: 7d54a50203582cb8f73c6e73e90dc73e4dc0659e2915d568cc22490eee28dfdb386540b6605c3f04

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

Commit: 2915d568cc22490eee28dfdb386540b6605c3f04f09f9ec7cc220af2a254fd19b03a55adb66d2611

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

8d2874eTrac #32272: extend docstring
28c9889Trac #32272: add super-algebra structure
f09f9ecTrac #32272: add ngens method

comment:6 Changed 17 months ago by Michael Jung

(for the following see also https://groups.google.com/g/sage-devel/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?

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

Commit: f09f9ec7cc220af2a254fd19b03a55adb66d2611188a5d43217b0fd6155bd04555170a746c91c45e

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

188a5d4Trac #32272: implement super-commutativity + rename file

comment:10 Changed 17 months ago by Michael Jung

Cc: Trevor Karn added

comment:11 Changed 17 months ago by git

Commit: 188a5d43217b0fd6155bd04555170a746c91c45e40d39a1ff88d5fec64788f90cc9a8bd570eff3dd

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

40d39a1Trac #32272: add more doctests

comment:12 Changed 17 months ago by git

Commit: 40d39a1ff88d5fec64788f90cc9a8bd570eff3dd0231712c7b072118e1d5043640db0415c138cee3

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

0231712Trac #32272: docstring extended

comment:13 Changed 17 months ago by Michael Jung

Authors: Michael Jung
Status: newneeds_review

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

comment:14 Changed 17 months ago by git

Commit: 0231712c7b072118e1d5043640db0415c138cee38d641f190c5922ed5381e81a0c6a1149f20981c8

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

8d641f1Trac #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: 8d641f190c5922ed5381e81a0c6a1149f20981c86a320a05234d78cf4aea5c8031eb99cab7b18ac9

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

d22ee9aTrac #32315: support iteration and enumerated sets
16c4737Trac #32272: allow infinite max degree
6a320a0Trac #32272: fix docstring

comment:19 Changed 16 months ago by Michael Jung

Ready for review again.

comment:20 Changed 16 months ago by Michael Jung

Description: modified (diff)
Summary: Finitely generated graded algebras with finite degreeGraded 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: 6a320a05234d78cf4aea5c8031eb99cab7b18ac9c1d4fceb9cffd4236d9ee94282f12d9bb7065529

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

c1d4fceTrac #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: c1d4fceb9cffd4236d9ee94282f12d9bb706552925e6b1da8a41635449797df1b48990096e03f9f2

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

25e6b1dTrac #32272: fix doctest

comment:26 Changed 16 months ago by Michael Jung

Patchbot is morally green now. :)

comment:27 Changed 16 months ago by Michael Jung

Cc: John Palmieri added

comment:28 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 ; Changed 16 months ago by Michael Jung

Replying to jhpalmieri:

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

Replying to gh-mjungmath:

Replying to jhpalmieri:

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

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/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
  • no multigrading
  • 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.4sage-9.5

comment:36 Changed 16 months ago by John Palmieri

Milestone: sage-9.5sage-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.4sage-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: 25e6b1da8a41635449797df1b48990096e03f9f25a4c7acec7fb95fac21a6367b364774215ace3fa

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

5a4c7acTrac #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 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

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.

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: 5a4c7acec7fb95fac21a6367b364774215ace3fa7328d50f792f1a4c964ce9a841b04a3a7dddb311

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

7328d50Trac #32272: remove unused imports

comment:48 Changed 16 months ago by Travis Scrimshaw

Status: needs_reviewpositive_review

Thank you.

comment:49 Changed 16 months ago by Michael Jung

Thank you for the review.

comment:50 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

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

Status: positive_reviewneeds_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

Commit: 7328d50f792f1a4c964ce9a841b04a3a7dddb311970d2950fad3092bb100372e537f73308fb6c978

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

970d295Trac #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_workneeds_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_reviewpositive_review

Perhaps, but that should be its own ticket.

comment:60 Changed 15 months ago by Volker Braun

Branch: u/gh-mjungmath/finitely_generated_graded_algebras_with_finite_degree970d2950fad3092bb100372e537f73308fb6c978
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.