Opened 4 months ago

Closed 3 months ago

#32272 closed enhancement (fixed)

Graded algebras with maximal degree

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

Status badges

Description (last modified by gh-mjungmath)

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 4 months ago by gh-mjungmath

  • Branch set to u/gh-mjungmath/finitely_generated_graded_algebras_with_finite_degree

comment:2 Changed 4 months ago by git

  • Commit set to 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 4 months ago by git

  • Commit changed from 0813d34634788e5e2fc16761fc3e41a1a89ab9ba to 7d54a50203582cb8f73c6e73e90dc73e4dc0659e

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

7d54a50#32272: rearrange docstring

comment:4 Changed 4 months ago by git

  • 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 4 months ago by git

  • Commit changed from 2915d568cc22490eee28dfdb386540b6605c3f04 to f09f9ec7cc220af2a254fd19b03a55adb66d2611

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 4 months ago by gh-mjungmath

(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 4 months ago by gh-mjungmath (previous) (diff)

comment:8 Changed 4 months ago by gh-mjungmath

  • Description modified (diff)

comment:9 Changed 4 months ago by git

  • Commit changed from f09f9ec7cc220af2a254fd19b03a55adb66d2611 to 188a5d43217b0fd6155bd04555170a746c91c45e

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

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

comment:10 Changed 4 months ago by gh-mjungmath

  • Cc tkarn added

comment:11 Changed 4 months ago by git

  • Commit changed from 188a5d43217b0fd6155bd04555170a746c91c45e to 40d39a1ff88d5fec64788f90cc9a8bd570eff3dd

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

40d39a1Trac #32272: add more doctests

comment:12 Changed 4 months ago by git

  • Commit changed from 40d39a1ff88d5fec64788f90cc9a8bd570eff3dd to 0231712c7b072118e1d5043640db0415c138cee3

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

0231712Trac #32272: docstring extended

comment:13 Changed 4 months ago by gh-mjungmath

  • Authors set to Michael Jung
  • Status changed from new to needs_review

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

comment:14 Changed 4 months ago by git

  • Commit changed from 0231712c7b072118e1d5043640db0415c138cee3 to 8d641f190c5922ed5381e81a0c6a1149f20981c8

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

8d641f1Trac #32272: correct path in docstring

comment:15 Changed 4 months ago by tscrim

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 4 months ago by gh-mjungmath

  • Dependencies set to #32315

comment:17 Changed 4 months ago by gh-mjungmath

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 4 months ago by gh-mjungmath (previous) (diff)

comment:18 Changed 4 months ago by git

  • Commit changed from 8d641f190c5922ed5381e81a0c6a1149f20981c8 to 6a320a05234d78cf4aea5c8031eb99cab7b18ac9

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 4 months ago by gh-mjungmath

Ready for review again.

comment:20 Changed 4 months ago by gh-mjungmath

  • Description modified (diff)
  • Summary changed from Finitely generated graded algebras with finite degree to Graded algebras with maximal degree

comment:21 Changed 4 months ago by gh-mjungmath

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 4 months ago by gh-mjungmath

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

Last edited 4 months ago by gh-mjungmath (previous) (diff)

comment:23 Changed 4 months ago by git

  • Commit changed from 6a320a05234d78cf4aea5c8031eb99cab7b18ac9 to c1d4fceb9cffd4236d9ee94282f12d9bb7065529

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

c1d4fceTrac #32272: fix rst file + rename module

comment:24 Changed 4 months ago by gh-mjungmath

This should fix the patchbot complaints.

comment:25 Changed 4 months ago by git

  • Commit changed from c1d4fceb9cffd4236d9ee94282f12d9bb7065529 to 25e6b1da8a41635449797df1b48990096e03f9f2

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

25e6b1dTrac #32272: fix doctest

comment:26 Changed 4 months ago by gh-mjungmath

Patchbot is morally green now. :)

comment:27 Changed 4 months ago by gh-mjungmath

  • Cc jhpalmieri added

comment:28 follow-up: Changed 4 months ago by 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"? 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: Changed 4 months ago by 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.

(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: Changed 4 months ago by jhpalmieri

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 4 months ago by gh-mjungmath

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 4 months ago by gh-mjungmath (previous) (diff)

comment:32 Changed 4 months ago by gh-mjungmath

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 4 months ago by gh-mjungmath (previous) (diff)

comment:33 Changed 4 months ago by gh-mjungmath

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 4 months ago by gh-mjungmath (previous) (diff)

comment:34 Changed 4 months ago by gh-mjungmath

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 4 months ago by gh-mjungmath (previous) (diff)

comment:35 Changed 4 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:36 Changed 4 months ago by jhpalmieri

  • Milestone changed from sage-9.5 to 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 4 months ago by jhpalmieri

  • Milestone changed from sage-9.4 to sage-9.5

comment:38 Changed 4 months ago by gh-mjungmath

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 4 months ago by gh-mjungmath

  • Description modified (diff)

comment:40 Changed 4 months ago by gh-mjungmath

  • Description modified (diff)

comment:41 Changed 4 months ago by git

  • Commit changed from 25e6b1da8a41635449797df1b48990096e03f9f2 to 5a4c7acec7fb95fac21a6367b364774215ace3fa

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

5a4c7acTrac #32272: narrow to finite dimensions

comment:42 Changed 4 months ago by gh-mjungmath

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: Changed 4 months ago by 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).

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 4 months ago by gh-mjungmath

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 4 months ago by gh-mjungmath (previous) (diff)

comment:45 Changed 4 months ago by gh-mjungmath

Patchbot seems okay.

comment:46 Changed 4 months ago by tscrim

  • 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 4 months ago by git

  • Commit changed from 5a4c7acec7fb95fac21a6367b364774215ace3fa to 7328d50f792f1a4c964ce9a841b04a3a7dddb311

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

7328d50Trac #32272: remove unused imports

comment:48 Changed 4 months ago by tscrim

  • Status changed from needs_review to positive_review

Thank you.

comment:49 Changed 4 months ago by gh-mjungmath

Thank you for the review.

comment:50 follow-up: Changed 4 months ago by 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.

comment:51 in reply to: ↑ 50 Changed 4 months ago by gh-mjungmath

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 3 months ago by vbraun

  • Status changed from positive_review to needs_work

PDF docs don't build

comment:53 Changed 3 months ago by gh-mjungmath

Weird. What's the issue here?

comment:54 Changed 3 months ago by tscrim

Perhaps its the $ in the \text with an autoreplace done to a backtick `? Are you able to build the PDF docs?

comment:55 Changed 3 months ago by git

  • Commit changed from 7328d50f792f1a4c964ce9a841b04a3a7dddb311 to 970d2950fad3092bb100372e537f73308fb6c978

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

970d295Trac #30473: unicode -> latex for cup product

comment:56 Changed 3 months ago by gh-mjungmath

That should be it.

comment:57 Changed 3 months ago by gh-mjungmath

  • Status changed from needs_work to needs_review

comment:58 Changed 3 months ago by gh-mjungmath

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 3 months ago by tscrim

  • Status changed from needs_review to positive_review

Perhaps, but that should be its own ticket.

comment:60 Changed 3 months ago by vbraun

  • Branch changed from u/gh-mjungmath/finitely_generated_graded_algebras_with_finite_degree to 970d2950fad3092bb100372e537f73308fb6c978
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.