Finitely presented graded modules over graded connected algebras

[jhpalmieri]

This is a precursor to #30680, laying out the framework for finitely presented modules over graded connected algebras. #30680 will focus on the case of the Steenrod algebra, with specific applications in mind.

CC: @sverre320 @sagetrac-kvanwoerden @jhpalmieri @tscrim @rrbruner @cnassau

Component: algebra

Author: Bob Bruner, Michael Catanzaro, Sverre Lunøe-Nielsen, Koen van Woerden, John Palmieri, Travis Scrimshaw

Branch/Commit: a1a9467

Reviewer: John Palmieri, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/32505

[jhpalmieri]

comment:1

I will quote from the TODO list in the forthcoming __init__.py:

1. Why do we need to define __bool__ and __eq__ in element.py? They should be taken care of automatically, once we define __nonzero__.
2. inhheritance: free modules, elements, etc., should perhaps inherit from fp versions, or maybe both should inherit from generic classes, to consolidate some methods (like degree, _repr_, others?)
3. Test with graded modules over other graded rings. (Should be okay, but add some doctests.)
   In __classcall__/__init__ for FP_Modules, allow as input a free module or a morphism of free modules? Or just leave it as is, with methods in FP_Modules, morphisms, and free modules for these constructions. (See the pre-existing FP_Modules.from_free_module etc., and also new methods morphism.to_fp_module() and free_module.to_fp_module().)

Question 1 is bugging me the most: I get doctest failures if I don't define __bool__ and __eq__, but according to structure/element.pyx, I shouldn't have to do this: the documentation there for __nonzero__ says:

        Note that this is automatically called when converting to
        boolean, as in the conditional of an if or while statement.

which really sounds like I shouldn't have to define __bool__.

[jhpalmieri]

Branch: u/jhpalmieri/free-graded-modules

[jhpalmieri]

Commit: fa91596

[jhpalmieri]

comment:3

This is not the final draft — I'd like to resolve at least some of the "TODO"s — but I'll mark it as "needs review".

---

New commits:

fa91596

trac 32505: finitely presented graded modules

[jhpalmieri]

comment:4

Structurally, the starting place for a review perhaps should be the free_* files; the others are built on top of those.

[sagetrac-git]

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

fd8545b

trac 32505: clear out __init__.py

[sagetrac-git]

Changed commit from fa91596 to fd8545b

[jhpalmieri]

comment:6

In order to follow #32501, __init__.py should be empty, so I changed it, moving the TODO list to module.py.

[tscrim]

comment:7

Thank you for separating this ticket out. It will make it easier to focus on the general functionality here. I finally have gotten back around to this. Sorry it took so long (but I have now finally moved to Japan).

I think we should change the name FP_Element and similar to FPElement to match PEP8.

There are many places where TESTS: should be TESTS::.

Let's get rid of the is_FreeGradedModuleHomspace and just replace it with the isinstance call.

I don't like the name free_element(). Perhaps free_module_representative()?

The mathematical description does not quite seem to match the implementation. Your basis elements are not a basis over the F-algebra A but over F. This needs to be very carefully explained in the documentation.

I think more things should be using the category framework (unless this becomes a significant bottleneck in #30680) Mainly I am looking at degree() by using degree_on_basis, but there is a mismatch with what this is a module over. Actually, this is more like the cartesian_product with some additional functionality. I might need to think a bit more about how this will all fit together.

[sagetrac-git]

Changed commit from fd8545b to 5153c6f

[sagetrac-git]

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

20aba35	trac 32505: finitely presented graded modules
1ab07ab	trac 32505: clear out __init__.py
5153c6f	trac 32505:

[jhpalmieri]

comment:9

Here are some of the changes: everything you suggested except for the category framework and changing the documentation to reflect what we mean by basis. (I thought I would take care of the easy things first.)

If you have more thoughts about how to use the category framework, I would be happy to hear them.

[tscrim]

comment:10

To utilize the degree() from the category framework, we only need to implement a degree_on_basis() method in the parent. This would mean less repeated code, although it might be slightly slower in the computation. Of course, the current version works and is fine to do things this way.

We also don't need the __nonzero__ anymore because __bool__ is Python3.

Right now, I feel like this is violating some internal assumptions of CFM because of the basis mismatch. So it should not inherit from CFM, but some other class, perhaps CombinatorialFreeModule_CartesianProduct as we realize it as A^k but are considering it to be an F-module from the implementation point of view. If we really want to think of it as an A-module, then internally we need to extract the F-basis coefficients from the values of the element dict (and we might want to think a bit about how we name our methods). This should be fairly simple to do, but requires some minor refactoring.

Based upon the code and its intended use, you are converting things a lot to/from (dense) vectors in F^d, so the Cartesian product approach with an entirely new element class might be the best option, where elements is stored as a dict of (degree, vector) pairs. I guess it depends on how much time is spent doing element manipulations like this, but the caching suggests this is a time-critical operation.

[jhpalmieri]

comment:11

First, FreeGradedModule is indeed an honest free module, and I think it should be okay to use CombinatorialFreeModule for it. The "basis" in this case is explicitly the basis as a module over algebra; it is not a vector space basis. As a result, the degree_on_basis() setup won't work, because it assumes that you're working with graded modules over an ungraded ring, and so it doesn't take into account the possible degree of the coefficients. At least that's my reading of the homogeneous_degree method in categories/filtered_modules_with_basis.py.

I don't really see how using Cartesian products will help: A^k is just a free module, so we should be able to use the free module class for it. I don't think the code will use the projection and inclusion maps that are provided by the Cartesian product class.

FPModule is trickier: it is not free as a module over algebra, but of course it is free over the ground field. I don't know of a suitable class in Sage for it, but CombinatorialFreeModule kind of works. One problem is that the basis keys correspond to the given choice of generators, and since the module need not be free, it need not be a basis. Another problem is that there is an actual vector space basis in each degree and we want to compute it, but we can't just deduce it from the "basis" for this CombinatorialFreeModule.

It's a good idea to maybe cache dense_coefficient_list for these elements, and maybe while we're at it, give the method for this class of elements a different name.

[tscrim]

comment:12

Replying to @jhpalmieri:

First, FreeGradedModule is indeed an honest free module, and I think it should be okay to use CombinatorialFreeModule for it. The "basis" in this case is explicitly the basis as a module over algebra; it is not a vector space basis. As a result, the degree_on_basis() setup won't work, because it assumes that you're working with graded modules over an ungraded ring, and so it doesn't take into account the possible degree of the coefficients. At least that's my reading of the homogeneous_degree method in categories/filtered_modules_with_basis.py.

Ah, right, because we are considering it over a graded ring, which we do not have a mechanism to take that into account. That is a missing feature of the categories that probably needs to be addressed at some point. However, then the category of GradedModulesWithBasis(R) is wrong, and instead it should be in GradedModules(R).WithBasis(). These are not the same

sage: GradedModulesWithBasis(QQ) == GradedModules(QQ).WithBasis()
False

as the latter is just saying there is a distinguished basis in a graded module, but not that the basis respects the grading. This allows us to circumvent this issue of the grading of the base ring (at least for now).

I don't really see how using Cartesian products will help: A^k is just a free module, so we should be able to use the free module class for it. I don't think the code will use the projection and inclusion maps that are provided by the Cartesian product class.

From the above, I agree that CFM is fine. So we don't have to use this.

FPModule is trickier: it is not free as a module over algebra, but of course it is free over the ground field. I don't know of a suitable class in Sage for it, but CombinatorialFreeModule kind of works. One problem is that the basis keys correspond to the given choice of generators, and since the module need not be free, it need not be a basis. Another problem is that there is an actual vector space basis in each degree and we want to compute it, but we can't just deduce it from the "basis" for this CombinatorialFreeModule.

We can weaken this to be a subclass of IndexedGenerators, Module, and UniqueRepresentation, which are the base classes of CFM and has mos of the desired features. There might be some features we might want to abstract from CFM to some intermediate ABC to also use in this class to remove code duplication. This will probably be the best way forward for FPModule.

It's a good idea to maybe cache dense_coefficient_list for these elements, and maybe while we're at it, give the method for this class of elements a different name.

If we are going to cache it, then we might as well only store that and reimplement the module structure following my proposal at the end of in comment:10. IIRC, it is faster to go from the dense list to the indexed free module element than the other way around.

[sagetrac-git]

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

b3816f9

trac 32505: minor cleanup

[sagetrac-git]

Changed commit from 5153c6f to b3816f9

[jhpalmieri]

comment:14

Replying to @tscrim:

Ah, right, because we are considering it over a graded ring, which we do not have a mechanism to take that into account. That is a missing feature of the categories that probably needs to be addressed at some point. However, then the category of GradedModulesWithBasis(R) is wrong, and instead it should be in GradedModules(R).WithBasis(). These are not the same

sage: GradedModulesWithBasis(QQ) == GradedModules(QQ).WithBasis()
False

as the latter is just saying there is a distinguished basis in a graded module, but not that the basis respects the grading. This allows us to circumvent this issue of the grading of the base ring (at least for now).

First, it is unfortunate that these are not the same, but that's not something to be fixed here. What differences does it make in this particular case to use GradedModules(algebra).WithBasis()?

Re FPModule:

We can weaken this to be a subclass of IndexedGenerators, Module, and UniqueRepresentation, which are the base classes of CFM and has mos of the desired features. There might be some features we might want to abstract from CFM to some intermediate ABC to also use in this class to remove code duplication. This will probably be the best way forward for FPModule.

I'll work on this.

[sagetrac-git]

Changed commit from b3816f9 to ca45b2b

[sagetrac-git]

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

1612a41	trac 32505: change category for free modules
a569bf0	trac 32505: use `__bool__` instead of __nonzero__
ca45b2b	trac 32505: change inheritance for FPModule, first pass

[jhpalmieri]

comment:16

Here are a bunch of changes in response to Travis' suggestions:

• use __bool__ instead of __nonzero__
• change the category for free modules to GradedModules(algebra).WithBasis(). I have not tested whether this allows me to get away with just defining degree_on_basis.
• change the class for FPModule to inherit from IndexedGenerators, Module, and UniqueRepresentation.

I still need to add some doctests for methods copied over from CombinatorialFreeModule and other places, but this works as is. (So feel free to look at the changes, but I will be adding more doctests, if nothing else.) I have not created any intermediate classes in an attempt to remove any code duplication.

[sagetrac-git]

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

46ef922

trac 32505: change inheritance for FPModule

[sagetrac-git]

Changed commit from ca45b2b to 46ef922

[jhpalmieri]

comment:18

Now including doctest coverage for everything.

[jhpalmieri]

comment:19

I think this all works. We can use the suggestion at the end of comment:10 now or defer to another ticket. I think I would prefer to wait and see where the real bottlenecks are.

[sagetrac-git]

Changed commit from 11b3725 to 6c1ab8d

[jhpalmieri]

comment:74

Fixed a few more things: the free_graded_module method for algebras with basis wasn't handling the names argument correctly, and a few doctests were failing. I changed some of the documentation, too.

[tscrim]

comment:75

I was just running into that problem in comment:74 and about to fix it. Thanks. I will be pushing a bunch of changes shortly too.

[sagetrac-git]

Changed commit from 6c1ab8d to 5074464

[sagetrac-git]

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

72e455e	We do not require the base algebra's base ring to be a field.
fcce24d	Merge branch 'public/modules/free_graded_modules-32505' of git://trac.sagemath.org/sage into public/modules/free_graded_modules-32505
2e0518f	Using free modules where possible and improved compatibility.
6cf6d14	Merge branch 'public/modules/free_graded_modules-32505' of git://trac.sagemath.org/sage into public/modules/free_graded_modules-32505
5074464	Some last fixes and removing redundancy.

[tscrim]

comment:77

I took this a bit further and made everything in the resolution a FreeGradedModule. As I suspected, there were some compatibility issues to sort out, but I took care of all of the ones that came up in doctests (and a few others I saw along the way). There might be a few others (which will show up as missing methods), but we can fix them as we come across them.

Towards this, I made the free module morphism/homspace a subclass of the respective non-free version. This required some slight workaround, but the code is much cleaner IMO because there are no duplicated methods and the subclassing makes mathematical sense.

I tweaked the documentation to say "free module" basically everywhere we use "vector space" because we are not using the field properties AFAICS.

As of right now, I am happy with the code. Please check my changes. If they are good, then go ahead and set a positive review.

[jhpalmieri]

comment:78

I saw that you replaced PlusInfinity() with infinity, so I made the same change a few other places. I also removed a "todo" about dealing with finite dimensionality rather than just finiteness, handling it the same way we did elsewhere in the code. If someone gets motivated (on another ticket), they can try to handle the case where self.base_ring().dimension() is not defined.

[sagetrac-git]

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

ffe7179

trac 32505: replace "PlusInfinity()" with "infinity"

[sagetrac-git]

Changed commit from 5074464 to ffe7179

[jhpalmieri]

Changed author from Bob Bruner, Michael Catanzaro, Sverre Lunøe-Nielsen, Koen van Woerden, John Palmieri to Bob Bruner, Michael Catanzaro, Sverre Lunøe-Nielsen, Koen van Woerden, John Palmieri, Travis Scrimshaw

[tscrim]

comment:81

Replying to @jhpalmieri:

I saw that you replaced PlusInfinity() with infinity, so I made the same change a few other places.

Indeed, this is a micro-optimization since they are the same object, but infinity is already created (and nailed in memory).

I also removed a "todo" about dealing with finite dimensionality rather than just finiteness, handling it the same way we did elsewhere in the code.

Thank you. I had made that note for myself, but I forgot about it.

If someone gets motivated (on another ticket), they can try to handle the case where self.base_ring().dimension() is not defined.

I concur.

Thank you.

[sverre320]

comment:82

Good question. Comments from the original authors? Why not just use free modules in resolution?

In the original version, the free module class was not intended for public use.

[vbraun]

comment:83

[sagemath_doc_html-none] [modules  ] The inventory files are in local/share/doc/sage/inventory/en/reference/modules.
[sagemath_doc_html-none] Error building the documentation.
[sagemath_doc_html-none] Traceback (most recent call last):
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/runpy.py", line 197, in _run_module_as_main
[sagemath_doc_html-none]     return _run_code(code, main_globals, None,
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/runpy.py", line 87, in _run_code
[sagemath_doc_html-none]     exec(code, run_globals)
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage_docbuild/__main__.py", line 2, in <module>
[sagemath_doc_html-none]     main()
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage_docbuild/__init__.py", line 1731, in main
[sagemath_doc_html-none]     builder()
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage_docbuild/__init__.py", line 776, in _wrapper
[sagemath_doc_html-none]     getattr(DocBuilder, build_type)(self, *args, **kwds)
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage_docbuild/__init__.py", line 136, in f
[sagemath_doc_html-none]     runsphinx()
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage_docbuild/sphinxbuild.py", line 323, in runsphinx
[sagemath_doc_html-none]     sys.stderr.raise_errors()
[sagemath_doc_html-none]   File "/home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage_docbuild/sphinxbuild.py", line 258, in raise_errors
[sagemath_doc_html-none]     raise OSError(self._error)
[sagemath_doc_html-none] OSError: /home/release/Sage/local/var/lib/sage/venv-python3.9.9/lib/python3.9/site-packages/sage/modules/fp_graded/free_homspace.py:docstring of sage.modules.fp_graded.free_homspace.FreeGradedModuleHomspace.identity:4: WARNING: Literal block expected; none found.
[sagemath_doc_html-none] 
[sagemath_doc_html-none]     Note: incremental documentation builds sometimes cause spurious
[sagemath_doc_html-none]     error messages. To be certain that these are real errors, run
[sagemath_doc_html-none]     "make doc-clean doc-uninstall" first and try again.

[jhpalmieri]

comment:84

Travis, was your intention to delete the identity method from free_homspace? Perhaps also remove zero?

[tscrim]

comment:85

Replying to @jhpalmieri:

Travis, was your intention to delete the identity method from free_homspace? Perhaps also remove zero?

Yes it was. They are now inherited as they had (effectively) the same code as the not-necessarily-free homspace.

[sagetrac-git]

Changed commit from ffe7179 to a1a9467

[sagetrac-git]

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

a1a9467

trac 32505: remove redundant "zero" and "identity" methods

[tscrim]

comment:88

Thank you.

[jhpalmieri]

comment:89

Followup in #33275.

[vbraun]

Changed branch from public/modules/free_graded_modules-32505 to a1a9467