Finitely presented graded modules over graded connected algebras

jhpalmieri commented 3 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 8e54829 to db79c13

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

`c0ebfa1`	`trac 32505: rename kernel_morphism to kernel_inclusion,`
`db79c13`	`trac 32505: comments about submodules`

jhpalmieri commented 2 years ago

comment:38

Replying to @tscrim:

I know what the problem is. The TestSuite is very useful:
-element_class = FPElement
+Element = FPElement
I will push a fix along with some other miscellaneous doc fixes one I make my way through all of the code.

Thanks for figuring that out!

One this that I do not like is submodule returning a morphism. This is very counterintuitive to me. I propose we rename this submodule_inclusion or submodule_embedding (other names welcome). Same for kernel. I know this is meant for homological algebra (+1 for that), but the method names should reflect their behavior IMO.

Fixed. I also suggested in a private email that another option would be to have a new class FpMorphismKernel which would inherit from FPModule but would also remember ambient module and the inclusion map. In the particular setting here, I think that the morphism is going to be used more than the kernel, so using f.kernel_inclusion() and occasionally f.kernel_inclusion().domain() looks better to me than f.kernel().inclusion() and occasionally f.kernel().

jhpalmieri commented 2 years ago

comment:39

Replying to @tscrim:

I also have some thoughts about the construction hooks. These do not necessarily need to be address on this ticket, but it might be good to do it here. I think we should have some method added to the category of GradedAlgebrasWithBasis called free_graded_module and possibly add FreeGradedModule to the global namespace. This would serve as the main entry point.

This may require some other changes; in particular, every algebra (with basis? or every algebra?) should have a free_module method, but the free_module method for Clifford/exterior algebras just gives a rank 1 free module, the module underlying the algebra itself. Searching for free_module methods suggests that some behave this way while some allow the user to specify a basis. We should probably have something like underlying_free_module(self) and free_module(self, basis=...). The version in categories/rings.py, which might be viewed as the default method, is a little strange, since it returns not just a free module V over the ring R but also maps R -> V and V -> R. Such maps are not particularly canonical, so I don't know why they are part of the structure. Actually, it looks like this may only return a free module of rank 1. I don't know why it doesn't just call CombinatorialFreeModule(R, basis, ...) and allow for higher rank modules.

Maybe my point is, this looks messy enough that it should be deferred to another ticket. Alternatively we could ignore the mess and just add a free_graded_module method as you suggest, and try to clean up the ungraded case later. It will be a little awkward if free_module and graded_free_module behave so differently.

Next, to construct a finitely presented module, I am thinking we should implement a quotient method or some other natural method to compute finitely presented modules as a 2-step procedure. Of course, we can easily add a finitely_presented_graded_module() or similar such method to allow a direct construction.

The current code allows for the construction of a finitely presented module from a morphism between two free modules (mor.to_fp_module()). That could also be turned into a method for free modules, accepting a morphism and returning an f.p. module.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from db79c13 to 2e9b692

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

2e9b692 trac 32505: fix some comparisons to None

jhpalmieri commented 2 years ago

comment:41

We could do this, for example:

diff --git a/src/sage/categories/graded_algebras_with_basis.py b/src/sage/categories/graded_algebras_with_basis.py
index e7ae68328e..8af922cd31 100644
--- a/src/sage/categories/graded_algebras_with_basis.py
+++ b/src/sage/categories/graded_algebras_with_basis.py
@@ -84,6 +84,45 @@ class GradedAlgebrasWithBasis(GradedModulesCategory):
         # Also, ``projection`` could be overridden by, well, a
         # projection.

+        def free_graded_module(self, generator_degrees, names=None):
+            """
+            Create a finitely generated free graded module over ``self``
+
+            This is only implemented when the ground ring is a field.
+
+            INPUTS:
+
+            - ``generator_degrees`` -- tuple of integers defining the
+              number of generators of the module, and their degrees
+
+            - ``names`` -- optional, the names of the generators. If
+              ``names`` is a comma-separated string like ``'a, b,
+              c'``, then those will be the names. Otherwise, for
+              example if ``names`` is ``abc``, then the names will be
+              ``abc_{d,i}``.
+
+            By default, if all generators are in distinct degrees,
+            then the ``names`` of the generators will have the form
+            ``g_{d}`` where ``d`` is the degree of the generator. If
+            the degrees are not distinct, then the generators will be
+            called ``g_{d,i}`` where ``d`` is the degree and ``i`` is
+            its index in the list of generators in that degree.
+
+            See :mod:`sage.modules.fp_graded.free_module` for more
+            examples and details.
+
+            EXAMPLES::
+
+                sage: Q = QuadraticForm(QQ, 3, [1,2,3,4,5,6])
+                sage: Cl = CliffordAlgebra(Q)
+                sage: M = Cl.free_graded_module((0, 2, 3))
+                sage: M.gens()
+                (g_{0}, g_{2}, g_{3})
+            """
+            from sage.modules.fp_graded.free_module import FreeGradedModule
+            return FreeGradedModule(self, generator_degrees, names)
+
+
     class ElementMethods:
         pass

dcd5aadc-0ad9-429b-81d8-3f4b6e693475 commented 2 years ago

comment:42

Replying to @jhpalmieri:

Finally, I am not happy with how elements are printed. Rather than <x, y>, I would rather see x*g_0 + y*g_1. Users should be allowed to name their generators, so you could also do
sage: M.<a,b,c> = FPModule(...)
sage: x*a + y*b
x*a + y*b
or
sage: M = FPModule(..., name='b', ...)  # not sure about this syntax
sage: x*M.gen(0)
x*b_0
gh-sverre320, kvanwoerden, gh-rrbruner: any comments?

We like the printing and naming mechanism you propose, jhpalmieri!

tscrim commented 2 years ago

comment:44

Sorry for being slow about this.

I like your idea in comment:41.

Now for something closer to bikeshedding. I think we should print the elements as, e.g., g[0] following CFM. In addition, we could just pass everything off to IndexedGenerators (via CFM) and let that handle everything. This makes it more customizable. In order to do so, we would extend that to support the names option. How does this sound? I can take care of this if you want.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 2e9b692 to c3bf4b8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

c3bf4b8 trac 32505: add free_graded_module method to GradedAlgebrasWithBasis

jhpalmieri commented 2 years ago

comment:46

Here is a branch with comment:41 incorporated. If you can push a branch with names etc., that would be great!

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

8435c78 Reformatting output, simplifying basis construction, other misc changes.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from c3bf4b8 to 8435c78

tscrim commented 2 years ago

comment:48

I have pushed the changes with names (we will want the patchbot to get around to it to see if there are other (almost certainly trivial) doctests breaking across Sage from the internal changes).

I also made a number of other changes and improvements. One important one is I changed the internal representation of basis elements to match the "generic" (i.e., no names specified) printing indices. This is the most natural way to associate data to the basis element (IMO the only other natural way would just be to just use {0, ..., k} to index the basis elements). I also directly links the FP module to the free module's indices. This was also very useful for setting up the element printing.

I renamed the to_fp_module to as_fp_module for modules and fp_module for morphisms. If it was to_fp_module, I would expect some kind of map to be returned. I wanted the different names both to reflect the English and that modules and morphism are fundamentally different objects.

I have some design questions:

I think we should have the FPModule construction be based on the morphism since that is the data that is actually stored. The __classcall_private__ would then preparse the input data as needed.
We should remove the __contains__ of FPModule. I think this is suppressing an issue with comparing elements. Contrast this code with
```
sage: Z4 = Zmod(4)
sage: Z5 = Zmod(5)
sage: Z5(3) in Z4
False
sage: Z5(3) == Z4(3)
False
```
which is using the generic __contains__. Right now I can't provide any advice on how to fix this as I haven't looked at this too closely yet.

I also have some questions regarding the formatting that are easy enough to fix/change, but I wanted to be set on them before updating the remaining doctests (there will be some trivial failures in the added files):

What do we want the default prefix to be? Previously it was g, but I was thinking G to reflect that it should be an element of the module G. Pure bikeshedding, and I don't care. I just chose something that I thought was reasonable, but I should poll for other opinions before setting everything.
How do we want to print when the generator degrees? Right now the unique are G[0] and the non-unique are G(0, 0) because that was the easiest to do. I can easily change the unique to G(0), and it is also relatively easy to change G(0, 0) to, e.g., G[0,0].
I propose changing the morphism output to match that of ring morphisms:
```
sage: R.<x> = ZZ[]
sage: S.<y> = ZZ[]
sage: R.hom([y])
Ring morphism:
From: Univariate Polynomial Ring in x over Integer Ring
To:   Univariate Polynomial Ring in y over Integer Ring
Defn: x |--> y
```
This is better when there are a lot of elements, it is consistent with other parts of Sage, no tuple-vs-list printing issues, and we likely can take advantage of other morphism display code.

jhpalmieri commented 2 years ago

comment:49

Replying to @tscrim:

I have pushed the changes with names (we will want the patchbot to get around to it to see if there are other (almost certainly trivial) doctests breaking across Sage from the internal changes).

Great, thank you!

I think we should have the FPModule construction be based on the morphism since that is the data that is actually stored. The __classcall_private__ would then preparse the input data as needed.

Sounds okay to me, but I don't a strong opinion about it.

We should remove the __contains__ of FPModule. I think this is suppressing an issue with comparing elements.

I'll try it and see what happens, then get back to you.

What do we want the default prefix to be? Previously it was g, but I was thinking G to reflect that it should be an element of the module G. Pure bikeshedding, and I don't care. I just chose something that I thought was reasonable, but I should poll for other opinions before setting everything.

I think lowercase is better: g[0] looks more like an element to me than G[0].

How do we want to print when the generator degrees? Right now the unique are G[0] and the non-unique are G(0, 0) because that was the easiest to do. I can easily change the unique to G(0), and it is also relatively easy to change G(0, 0) to, e.g., G[0,0].

I don't care too much, but I have a slight preference for uniformity: square brackets in both cases?

I propose changing the morphism output to match that of ring morphisms:

Yes, sounds good.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

`a556c49`	`Merge branch 'develop' into t/32505/public/modules/free_graded_modules-32505`
`d745357`	`trac 32505: fix doctests, change print representation for morphisms`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 8435c78 to d745357

jhpalmieri commented 2 years ago

comment:51

I changed G[0] to g[0] but also changed G(0, 0) to g(0, 0) — it wasn't clear how to get brackets in the second case. I also changed the print representation for morphisms. I think I fixed all of the doctests, too.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from d745357 to a73519c

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

a73519c trac 32505: delete the method "__contains__" for FPModules

jhpalmieri commented 2 years ago

comment:53

Replying to @tscrim:

I think we should have the FPModule construction be based on the morphism since that is the data that is actually stored. The __classcall_private__ would then preparse the input data as needed.

I would be happy for you to take care of this. I ran into problems because I want to use generators and relations as arguments (as is currently done) but then have __classcall_private__ convert to a morphism and pass that to __init__, and I couldn't figure out a clean way to do that. I didn't try that hard, but it seems that __classcall_private__ and __init__ should have the same arguments, so they both need morphism, generators, and relations? I guess we could switch to using a factory to construct these modules instead, but I didn't try that.

I removed the __contains__ method, but I didn't know what you were referring to with "I think this is suppressing an issue with comparing elements."

With elements, it's easy for me to switch to g(0) and keep the current g(0, 0), but I can't figure out how to instead switch the second one to g[0, 0].

Otherwise, I'm happy with this.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from a73519c to ebcae24

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

ebcae24 trac 32505: fix a doctest

tscrim commented 2 years ago

comment:55

Sorry, I have been busy this past week. I should be able to do this today. It is simply a matter of adding a layer in the _repr_term method to convert the input to a list and then passing it up. Although I am thinking a better (long term) solution is to add another hook in IndexedGenerators for more broadly handling iterable input and use the general mechanics (so if someone wants to change the brackets to, say, {, it becomes a simple changing of the print options). This should also be quick to do.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from ebcae24 to 6b84071

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

`4599fb5`	`Merge branch 'develop' into public/modules/free_graded_modules-32505`
`7d6bdf9`	`Merge branch 'public/modules/free_graded_modules-32505' of git://trac.sagemath.org/sage into public/modules/free_graded_modules-32505`
`6b84071`	`Adding additional print option to IndexedGenerators for iterating through keys.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

d6f67cf Fix containment issues and add some more doctests.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 6b84071 to d6f67cf

tscrim commented 2 years ago

comment:58

Replying to @jhpalmieri:

Replying to @tscrim:

I think we should have the FPModule construction be based on the morphism since that is the data that is actually stored. The __classcall_private__ would then preparse the input data as needed.

I would be happy for you to take care of this. I ran into problems because I want to use generators and relations as arguments (as is currently done) but then have __classcall_private__ convert to a morphism and pass that to __init__, and I couldn't figure out a clean way to do that. I didn't try that hard, but it seems that __classcall_private__ and __init__ should have the same arguments, so they both need morphism, generators, and relations? I guess we could switch to using a factory to construct these modules instead, but I didn't try that.

A factory is overkill. The only thing needed is checking if the __classcall_private__ input is a morphism or not. Well, I am feeling lazy (forgive me!) and don't really care too much to simplify the input as the current version works albeit somewhat inefficiently since it converts from the morphism data and then reconstructs said morphism. Anyways, this isn't anything that needs to be done right now. If you want to do this, please go ahead.

I removed the __contains__ method, but I didn't know what you were referring to with "I think this is suppressing an issue with comparing elements."

I was getting errors for those doctest you removed. Using the default containment, you get this:

sage: from sage.modules.fp_graded.module import FPModule
sage: M = FPModule(SteenrodAlgebra(2), [0,1], [[Sq(4), Sq(3)]])
sage: N = FPModule(SteenrodAlgebra(2), [0], [[Sq(2)]])
sage: y = Sq(2) * N.generator(0)
sage: y in M
True

which I think is wrong as it is checking this:

sage: M(y) == y
True

So either it is the equality or the conversion that has a bug (possibly both). Taking another look, the _element_constructor_ was too permissive in how it was handling elements. I have fixed this, and it seems to resolve other issues I found with testing for this.

With elements, it's easy for me to switch to g(0) and keep the current g(0, 0), but I can't figure out how to instead switch the second one to g[0, 0].

I have done this following what I sketched in comment:55.

Otherwise, I'm happy with this.

I am too if my changes are good.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

f5ec2c1 trac 32505: do not use __class__(...), instead explicitly name the class

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from d6f67cf to f5ec2c1

jhpalmieri commented 2 years ago

comment:60

I tried to modify __classcall_private__ to allow a morphism as input, but I ran into problems, which I have now mostly fixed. One minor problem is that the class is often initialized with the explicit keyword generator_degrees (as in FPModule(..., generator_degrees=...)), but it doesn't make sense to use that name for the argument anymore, so I removed those. Now we can easily change the name of the argument. Another problem is that some objects were constructed by calling self.__class__(...), and this usage seems to bypass __classcall_private__ and go straight to __init__. It seems like a bad idea anyway, so I changed those to just use FPModule(...).

I may try later to implement a morphism as input, but this will do for now.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from f5ec2c1 to ca9cdf0

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

ca9cdf0 trac 32505: fix one doctest

jhpalmieri commented 2 years ago

comment:62

This passes all tests for me now. Let's not worry about allowing a morphism as input to the FPModule constructor. I'd like to be able to move on to #30680. Travis, I'm happy with all of your work on this; thank you. Any objections to my most recent changes?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

7dc9139 trac 32505: remove an unneeded import

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from ca9cdf0 to 7dc9139

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 7dc9139 to b7f9179

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

b7f9179 Adding support for morphism input.

tscrim commented 2 years ago

comment:65

I got out of my laziness and added support for taking a morphism input.

I also changed the FPModule.j parameter to the hidden _j.

Although looking again at the code, I have a few more questions (sorry!):

With allowing both input formats, do we need the from_free_module* methods? They seem more like clutter to me. I propose to remove them.
Related, I don't see why we want to create a free FPModule (instead of FreeGradedModule) in resolution(). Likely this is related to having different APIs, where methods likely just need to be added to the free version or perhaps some ABC needs to be created. We might want to even have the __classcall_private__ redirect to the free module where appropriate.
Should the FPModule belong to the category of ModulesWithBasis? I don't think this is guaranteed (over the base algebra). See also the comment below.
I don't agree with the comment before FPModule "vector spaces" is ill-defined (in particular, we don't require the base ring of the base algebra to be a field). This can be corrected fairly easily. However, I propose removing this as it doesn't contribute anything to (understanding) the code.

jhpalmieri commented 2 years ago

comment:66

Replying to @tscrim:

I got out of my laziness and added support for taking a morphism input.

Great, thanks! I also added code to allow a free module as input, in which case it would return a finitely presented module with no relations. We can revisit this based on how we want to handle your question below about resolution.

I also changed the FPModule.j parameter to the hidden _j.

Good, makes sense.

With allowing both input formats, do we need the from_free_module* methods? They seem more like clutter to me. I propose to remove them.

Done.

Related, I don't see why we want to create a free FPModule (instead of FreeGradedModule) in resolution(). Likely this is related to having different APIs, where methods likely just need to be added to the free version or perhaps some ABC needs to be created. We might want to even have the __classcall_private__ redirect to the free module where appropriate.

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

Should the FPModule belong to the category of ModulesWithBasis? I don't think this is guaranteed (over the base algebra). See also the comment below.

I deleted this.

I don't agree with the comment before FPModule "vector spaces" is ill-defined (in particular, we don't require the base ring of the base algebra to be a field). This can be corrected fairly easily. However, I propose removing this as it doesn't contribute anything to (understanding) the code.

I replaced it with another comment, pointing out that some of the methods assume that there is a vector space structure and a chosen basis.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

5c242e7 trac 32505: remove from_free_module, from_free_module_morphism

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from b7f9179 to 5c242e7

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

5e02153 trac 32505: remove from_free_module, from_free_module_morphism

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 5c242e7 to 5e02153

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

f253e83 trac 32505: allow the resolution to be made up of maps between

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 5e02153 to f253e83

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

11b3725 trac 32505: allow the resolution to be made up of maps between

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from f253e83 to 11b3725

sagemath / sage

Finitely presented graded modules over graded connected algebras #32505