Implement GradedModulesWithBasis(R).Subobjects() and FilteredModulesWithBasis(R).Subobjects()

[louisng114]

Currently, graded submodules do not inherit grading from its ambient:

sage: M = ModulesWithBasis(QQ).Graded().example()
sage: M(Partition((4,2,1,1,1,1))).degree()
10
sage: N = M.submodule([M(Partition((4,2,1,1,1,1)))], category=GradedModulesWithBasis(QQ).Subobjects())
sage: n = N.basis()
sage: n[0].degree()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
...
AttributeError: 'SubmoduleWithBasis_with_category' object has no attribute 'degree_on_basis'

We implement this by fulfilling the regressive category construction requirement for the GradedModules().Subobjects() category. We also do this for filtered modules (every submodule of a filtered module has a natural filtration inherited from the ambient module).

Want: In the case where the generators are not from homogeneous but can made homogeneous by row reducing, it inherits its degrees. If the basis elements cannot be made homogeneous by row reduction, raise an error when trying to use graded_submodule. For example,

sage: M = ModulesWithBasis(QQ).Graded().example()
sage: N = M.graded_submodule([M(Partition((4,2,1,1,1,1))) - M(Partition((5,3))),
      M(Partition((5,3)))])
sage: n = N.basis()
sage: (n[0].lift(), n[1].lift())
(P[4, 2, 1, 1, 1, 1], P[5,3])
sage: (n[0].degree(), n[1].degree())
(10, 8)
sage: K = M.graded_submodule([M(Partition((4,2,1,1,1,1))) - M(Partition((5,3))),
      M(Partition((5,3)) - M(Partition((4,3)))])
Traceback (most recent call last):
...
ValueError: element is not homogeneous

CC: @mkoeppe @tscrim @jhpalmieri

Component: categories

Keywords: submodule

Author: Louis Ng, Travis Scrimshaw

Branch/Commit: e5901b5

Reviewer: Matthias Koeppe

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

[mkoeppe]

comment:2

Can you please add some examples that illustrate what you would like to happen?
Should submodules of graded modules always/sometimes/never be graded by default?

[tscrim]

comment:3

The current behavior is correct because there is no guarantee that an arbitrary submodule is spanned by homogeneous elements. For a simple example, take the submodule spanned by f = 1 + x in the polynomial ring with the natural degree grading. (There are more pathological examples for the counterarguments I can see for this.)

Now we could do something where we check to see if the spanning elements are homogeneous and then use the ambient grading. This then likely has a solution at the category level by creating the category of subobjects of graded modules with basis and graded modules (with basis). (Note as I argue above, this is a strict subcategory of subobjects of graded modules with basis.) This might be slightly subtle as, in principle, by saying an object is graded, you are suppose to specify what graded structure you want. Thus doing it automatically is perhaps not quite mathematically valid.

Perhaps the better solution would be to provide a graded_submodule method that returns a specially implemented GradedSubmoduleWithBasis class (as a subclass of SubmoduleWithBasis) that does all of this. This has the advantage of being explicit about the grading structure you want (the inherited one), not having to be very careful about adding the new category, and will likely be faster. It also means we don't have to add checks for homogeneity when someone might not want/need it.

For your immediate computational purposes, you can monkey patch in a degree by

def degree(self):
    return self.lift().degree()

Note, as mentioned above, you have told the object that it is a graded module without specifying what the graded structure is. So this is a reasonable hack until a more long-term solution is implemented.

The situation for filtered modules is perhaps easier as we do not need to contend with homogeneity issues.

[mkoeppe]

comment:4

+1 on developing it both for filtered and for graded modules

[louisng114]

comment:5

Replying to @tscrim:

The current behavior is correct because there is no guarantee that an arbitrary submodule is spanned by homogeneous elements. For a simple example, take the submodule spanned by f = 1 + x in the polynomial ring with the natural degree grading. (There are more pathological examples for the counterarguments I can see for this.)

Now we could do something where we check to see if the spanning elements are homogeneous and then use the ambient grading. This then likely has a solution at the category level by creating the category of subobjects of graded modules with basis and graded modules (with basis). (Note as I argue above, this is a strict subcategory of subobjects of graded modules with basis.) This might be slightly subtle as, in principle, by saying an object is graded, you are suppose to specify what graded structure you want. Thus doing it automatically is perhaps not quite mathematically valid.

Perhaps the better solution would be to provide a graded_submodule method that returns a specially implemented GradedSubmoduleWithBasis class (as a subclass of SubmoduleWithBasis) that does all of this. This has the advantage of being explicit about the grading structure you want (the inherited one), not having to be very careful about adding the new category, and will likely be faster. It also means we don't have to add checks for homogeneity when someone might not want/need it.

For your immediate computational purposes, you can monkey patch in a degree by

def degree(self):
    return self.lift().degree()

Note, as mentioned above, you have told the object that it is a graded module without specifying what the graded structure is. So this is a reasonable hack until a more long-term solution is implemented.

The situation for filtered modules is perhaps easier as we do not need to contend with homogeneity issues.

Would it make sense to use 'maximal_degree' for the grading for the submodule by default?

[tscrim]

comment:7

Replying to @louisng114:

Replying to @tscrim:

The situation for filtered modules is perhaps easier as we do not need to contend with homogeneity issues.

Would it make sense to use 'maximal_degree' for the grading for the submodule by default?

Not for graded modules: take 1 / (1 - x) in the ring of formal power series considered as a graded module by degree. There is no reasonable way to do this mathematically I believe.

[tscrim]

comment:9

I am still -1 on having by default a submodule inherit a grading. There is no reason to slow down code to test for homogeneity. If you want to inherit a grading, it should be a separate method (which returns a separate (sub)class). I would be very upset if I couldn't build a submodule of a graded module of nonhomogeneous elements as this is a natural thing to do.

[louisng114]

comment:10

Replying to @tscrim:

I am still -1 on having by default a submodule inherit a grading. There is no reason to slow down code to test for homogeneity. If you want to inherit a grading, it should be a separate method (which returns a separate (sub)class). I would be very upset if I couldn't build a submodule of a graded module of nonhomogeneous elements as this is a natural thing to do.

But this is only for when we specify the category of the submodule to be graded.

[tscrim]

comment:11

Replying to @louisng114:

Replying to @tscrim:

I am still -1 on having by default a submodule inherit a grading. There is no reason to slow down code to test for homogeneity. If you want to inherit a grading, it should be a separate method (which returns a separate (sub)class). I would be very upset if I couldn't build a submodule of a graded module of nonhomogeneous elements as this is a natural thing to do.

But this is only for when we specify the category of the submodule to be graded.

Still -1 because passing that category means I am promising to provide a grading, not have it inherited. Basically I could not create a submodue of nonhomogeneous elements that I provide a different grading to. Again, it does not make sense mathematically to do this. Thinking about how it would be coded further reinforces that to me. It also makes it easier to construct the object you want as you don't have to pass the category.

For free modules over a graded algebra, we also have different constructions if we want the module to be graded or not (although this was very recently merged #32505 and should appear in the next beta).

[louisng114]

Branch: public/33321

[louisng114]

New commits:

cf788b3

removing unintentionally added method from another branch

[louisng114]

Commit: cf788b3

[mkoeppe]

comment:13

In this docstring (and the next):

+        def filtered_submodule(self, gens):
+            r"""
+            Create a graded submodule by referencing the grading of
+            ``self``. The generators have to be each homogeneous.

it should say "filtered". Is the condition of being homogeneous needed in this case?

[tscrim]

comment:14

You have a contradiction: the category has a default grading and a special method saying inherit the grading. This is telling you that the category should not have the default grading. Let me again say that you need to create a separate class for the graded module and for filtered modules you can do this at the category level.

However, I was thinking a bit more, and there is a subtle issue with my example in comment:7. That is in the direct product, but the standard graded module is a direct sum. So there is a way to define a grading by the minimal or maximal degree of any element. However, because there are two incompatible ways of doing it, we should not do it in general for the graded case. A particular class/method is different than at the category level because you are explicitly saying "I want this specific object in the category."

Note that formal power series is still a filtered module. For filtered modules, there is a unique way to do this because for any x there is a unique minimal (or maximal for a descending filteration) index i such that x \in S_i. Contrast this with the graded case.

[mkoeppe]

comment:15

Replying to @tscrim:

You have a contradiction: the category has a default grading and a special method saying inherit the grading. This is telling you that the category should not have the default grading.

You are saying that a parent in the category of subobjects of graded modules is not necessarily graded as it is in Louis' code?

[tscrim]

comment:16

In the generic case, that is correct. Restricting to the homogeneously generated case, it is, but that is an additional restriction that would need an additional category. Although it is such a special case that IMO it is easier to understand and maintain as a particular parent class in the categories we already have.

[tscrim]

comment:17

Well, more precisely it is graded (since it is a direct sum), but not in a canonical way.

[mkoeppe]

comment:18

Isn't it the very definition of a graded submodule that the elements of the submodule have the same degree as upstairs?

[mkoeppe]

comment:19

I also don't know what you mean by "generic".

[mkoeppe]

comment:20

In fact, I don't think there's such a thing as a graded submodule that cannot be generated by homogeneous generators.

[tscrim]

comment:21

As a concrete example, take a polynomial ring as a graded module over its ground ring. Then take the submodule spanned by 1 + x. This is a submodule that has 2 natural gradings (that also extends to rings), one where it has degree 0 (min deg) and the other has degree 1 (max deg). This is a graded submodule in the sense that it is a submodule and it is graded, but not one that respects the ambient space grading. This is a natural submodule to construct IMO and needs to be supported.

However, I see the point you are making, and there seems to be an ambiguity in the definition. We need to be very precise about what category we are in. We need to allow the construction above, and so I would not want the subobjects of a graded category to have to respect the ambient grading. I think we should have an explicit hook when we want to have something that respects the ambient grading.

[mkoeppe]

comment:22

Replying to @tscrim:

[...] This is a graded submodule in the sense that it is a submodule and it is graded, but not one that respects the ambient space grading. This is a natural submodule to construct IMO

Yes, but it is in the join category of "subobjects of modules with basis" and "graded modules", not in the category that we're talking about.

[jhpalmieri]

comment:35

I'm not sure I can process all of the discussion right now, but given that disclaimer, here is my take: if you are explicitly working with an instance of ModulesWithBasis(QQ).Graded() and ask for a submodule, then you are in a graded setting and the submodule should be graded. (Should the code test for that or just assume that it's okay? I don't know.) Mathematically if you want to define the submodule of k[x] generated by 1+x, then you should apply a forgetful functor to pass to the category of ungraded modules first, and then define the submodule. Within Sage, I think the process in the previous sentence should be explicit: if you want to define the submodule generated by 1+x, you need to explicitly say that you are not going work in the graded setting any more.

I think this is consistent with the recent comments.

[sagetrac-git]

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

ef0227c	Merge branch 'public/33321' of git://trac.sagemath.org/sage into public/33321
edc6a03	Support for graded submodules and quotients of graded modules.

[sagetrac-git]

Changed commit from cf788b3 to edc6a03

[tscrim]

comment:37

Here is my proposal based upon our discussion. I decided to let the specified category override the filtered default in case someone wants to consider the object without the filtration (say, for doing morphisms). I also extended the allowed input for echelon_form and submodule so it was more natural. I also wasn't completely sure for the filtered quotients, so I just left that alone and only did things for graded modules.

[tscrim]

Author: Louis Ng, Travis Scrimshaw

[mkoeppe]

comment:38

Great!

In this doctest:

If ``category`` is specified, then it does not give any extra
+            structure to the submodule (we can think of this as applying
+            the forgetful functor)::
+
+                sage: SM = E.submodule([x + y, x*y - y*z], category=ModulesWithBasis(QQ))
+                sage: SM.category()
+                Join of Category of finite dimensional modules with basis over Rational Field
+                 and Category of vector spaces with basis over Rational Field
+                 and Category of subobjects of sets
+                sage: FM = E.submodule([x + 1, x*y - x*y*z], category=ModulesWithBasis(QQ))
+                sage: FM.category()
+                Join of Category of finite dimensional modules with basis over Rational Field
+                 and Category of vector spaces with basis over Rational Field
+                 and Category of subobjects of sets
+

it looks like the category is not quite right yet. Apart from the confusion with "Join of ... finite-dimensional modules, vector spaces" that is unrelated to this ticket, shouldn't it be at least in the category of subobjects of modules?

[tscrim]

comment:39

The subobjects of modules is the join of subobjects of sets and vector spaces. We just do not have that specific category defined (hence the join of those two). Likewise for adding the finite dimensional axiom. I added this doctest to show that it does not automatically inherent the graded/filtered structure when the category passed does not include it.

[mkoeppe]

comment:40

Replying to @tscrim:

The subobjects of modules is the join of subobjects of sets and vector spaces. We just do not have that specific category defined (hence the join of those two).

OK, that makes sense.

[tscrim]

comment:41

sage -t --long src/sage/graphs/graph.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/k_dual.py  # 1 doctest failed
sage -t --long src/sage/combinat/sf/new_kschur.py  # 1 doctest failed
sage -t --long src/sage/matrix/matrix_space.py  # 4 doctests failed
sage -t --long src/sage/algebras/orlik_terao.py  # 21 doctests failed
sage -t --long src/sage/matroids/matroid.pyx  # 4 doctests failed
sage -t --long src/sage/categories/modules_with_basis.py  # 5 doctests failed
sage -t --long src/sage/algebras/orlik_solomon.py  # 30 doctests failed
sage -t --long src/sage/matroids/linear_matroid.pyx  # 4 doctests failed
sage -t --long src/sage/categories/filtered_modules_with_basis.py  # 2 doctests failed
sage -t --long src/sage/categories/graded_modules_with_basis.py  # 6 doctests failed

There are a number of trivial doctest failures that I will need to fix from the change in categories. However, some non-trivial ones from the invariant rings of Orlik-!Solomon/Terao algebras from the input-standardization change. I will have to look more closely. (The graph.py failure is unrelated IIRC.)

[sagetrac-git]

Changed commit from edc6a03 to 0d93b11

[sagetrac-git]

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

73660b4	Remove unnecessary filtered_* methods; fixing submodule gens Family input.
6a3b6bf	Correcting one doctest and trivial output updates.
0d93b11	Change doctest to work around MRO resolution in matrix_space.py file.

[tscrim]

comment:43

I fixed the bug, which came down to not getting the correct type for the generator input to submodule.

Most of the other doctests are trivial updating. I think there are some new doctests added since beta1 (which is what I am currently using to work on this branch) to update. I still need to do that, which I probably won't do until tomorrow. However, two notable changes:

• I believe the change in modules_with_basis.py was needed from a doctest copy/paste that was not fully updated. I think that kind of input is an abuse and the user should explicitly change the ring of the element as there is no, a priori, relation between the two modules.

• The change of the base ring of Sym in matrix_space.py is because I was getting an unable-to-resolve-MRO issue that I could not reproduce in a more isolated example:

  TypeError: Cannot create a consistent method resolution order (MRO) for bases
   VectorSpaces.subcategory_class, GradedModules.subcategory_class
  

  This doesn't change the content of that doctest, but allows us to continue to sidestep this MRO resolution issue (see, e.g., Toward singleton categories: subcategories of Modules #22962).

[mkoeppe]

comment:44

Replying to @tscrim:

• I believe the change in modules_with_basis.py was needed from a doctest copy/paste that was not fully updated.

Yes, I agree

[sagetrac-git]

Changed commit from 0d93b11 to e5901b5

[sagetrac-git]

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

fe7924f	Merge branch 'public/33321' of https://github.com/sagemath/sagetrac-mirror into public/33321
e5901b5	Fixing doctest output from category changes.

[tscrim]

comment:46

Here are the fixes.

[tscrim]

comment:47

Bot was morally green using beta3 and passes all tests (other than known failures) run on my machine for beta4.

[mkoeppe]

comment:48

Looks good to me. Refinements and generalizations can be done in follow-up tickets. Thanks for this work!

[mkoeppe]

Reviewer: Matthias Koeppe

[tscrim]

comment:49

Thank you.

I hope this also works for the application you have in mind Louis. If not or if you have other questions, feel free to email me directly to discuss things further.

[vbraun]

Changed branch from public/33321 to e5901b5