Add support for homogeneous components of a filtered module

[tscrim]

Separates out functionality of subset(d) for finite dimensional filtered modules with basis and implements a method to get the submodule spanned by a homogeneous piece.

[tscrim]

This will be useful along with the changes I'm making in #6102, which I think will be our first naturally graded finite-dimensional algebra in Sage.

---

Last 10 new commits:

​570bc49	Merge branch 'public/categories/super_categories-18044' into 6.9.b1
​b91cd82	trac #18044 correct one typo in the doc
​7fd1df2	Merge branch 'public/categories/super_categories-18044' of trac.sagemath.org:sage into public/categories/super_categories-18044
​0579337	Some reviewer tweaks and doc additions.
​aec22cc	Added one more test.
​4b2046f	Merge branch 'public/categories/super_categories-18044' into public/categories/filtered_algebras-17096
​3f67b6b	Fixing trivial doctest due to changes in category heirarchy.
​fa476dd	Fixing double-colon in INPUT block.
​6cc8b84	Reviewer changes with Darij.
​9c51a4c	Merge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/graded_components-TBA

[jhpalmieri]

You have the comment starting with

# TODO: which syntax do we prefer?

twice, along with two different basis methods in filtered_modules_with_basis.py.

[git]

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

​ae81aa7

Fixing bad copying.

[jhpalmieri]

Is this a problem?

sage: A = GradedModulesWithBasis(ZZ).example()
sage: A.homogeneous_component(3).an_element()   # not printed like elements of A
3*B[[1, 1, 1]] + 3*B[[2, 1]] + B[[3]]
sage: a = A.homogeneous_component(3).an_element()
sage: a in A
False

Also, A(a) leads to a NotImplementedError. So once you have an element in a homogeneous component, there isn't an obvious way to view it as an element of the whole module.

[tscrim]

I was originally taking care of this on #19359, but I've now moved this to #19448 (which you can set as a dependency if you feel it is warranted).

[jhpalmieri]

Will #19448 also make

list(A.homogeneous_component(4).basis())

and

list(A.homogeneous_component_basis(4))

equal? (Can they be equal? The elements in the first are elements in a particular homogeneous component. The elements in the second are elements in the whole module. At least they should look the same when you print them, and I think #19448 should take care of that.)

[jhpalmieri]

One mathematical issue: in defining homogeneous_component, you have

category = ModulesWithBasis(self.category().base_ring())

A homogeneous component of an R-module need not be an R-module itself in a natural way: for example, if the base ring is the graded ring R=k[x, x^-1] with x in some nonzero degree, then for any homogeneous component of any graded R-module, x would have to act trivially (because x has nonzero degree). On the other hand, x is supposed to be invertible.

It will always be a module over the degree 0 part of the base ring, though.

[darij]

John: I fear that this notion of grading is not currently implemented in Sage (again, hardly anyone's deliberate design choice, but an artifact of ungraded base rings being the de-facto standard in combinatorics). Almost all of the current code in FilteredModulesWithBasis currently assumes that the base ring is ungraded :(

Incidentally, IMHO this issue shows that we are mistaken in the assumption that in order to equip an algebra with a grading, we should add degree and similar functions to the class. Many algebras have several natural gradings, and each of them comes with its own notion of a graded module. When you speak of a "graded R[x]-module", you have to specify whether x has degree 1 or 0 (or anything else); even in combinatorics, both of these cases happen. So if/when we make R[x] into a graded ring, what should its grading be? I think it shouldn't. There should be a two graded rings, called PolynomialRing(QQ).trivial_grading() and PolynomialRing().degree_grading() or something like this, while PolynomialRing(QQ) itself should just be a QQ-algebra. Actually the trivial_grading() function should be defined generically on any module and return the corresponding graded module with trivial grading. And there can be further gradings and filtrations likewise (I can see good uses for filtered the tensor algebra by word length, number of distinct letters, maximal multiplicity of a letter, etc. -- there is no way the code should decide between them for the user!).

[jhpalmieri]

For this situation, what about code like

try:
    R = self.base_ring().homogeneous_component(0)
    # or R = self.base_ring().base_ring()??
except AttributeError:
    R = self.base_ring()
category = ModulesWithBasis(self.category().R)

This may end up calling homogeneous_component recursively, but eventually that should end with an ungraded base ring.

Yes, I also agree that we need to allow for multiple possible gradings. I think this has been discussed before. To construct a graded ring you should specify a ring and a grading on it, and different gradings give different graded rings.

[tscrim]

However there is a technical problem with doing that in the short-term in that submodule currently does not differentiate between coordinate rings and base rings (think ZZ-submodule in a QQ-module). See also Jeroen's comments in #18310.

So if we were decided to do do the above, then we should add coordinate ring support in #19448 and make that a dependency of this one.

Alternatively we could just raise a NotImplementedError for now if the module and base ring are both graded.

[jhpalmieri]

I think we should do something, just to acknowledge that it is an issue that we might address later. A NotImplementedError sounds fine to me. Whatever is simplest, I think.

[git]

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

​cd186d0	Merge branch 'public/categories/homogeneous_components-19397' of trac.sagemath.org:sage into public/categories/homogeneous_components-19397
​f89275b	Raise a NotImplementedError if the base ring is filtered.

[tscrim]

The simple way is to raise a NotImplementedError for now. Although now I find myself wishing for filtered magmas...

[jhpalmieri]

This looks okay to me.

[vbraun]

Doctests fail:

​http://build.sagedev.org/release/builders/%20%20slow%20AIMS%20%20%28Debian%207%2064%20bit%29%20incremental/builds/152/steps/shell_4/logs/stdio

[jhpalmieri]

All tests passed for me on one machine (before I gave a positive review) and on another machine now. Any suggestions about how we can recreate these doctest failures to try to diagnose them?

[vbraun]

Can you merge in the next beta when its out?

[tscrim]

This looks like the same issues located on #15536.

[jhpalmieri]

With the latest beta, I see these failures. I don't know what to make of them, though.

[tscrim]

I can also reproduce this by just running the tests on modules_with_basis.py.

I tried the same hack on #15536 and I got errors. To the extreme, I made the prime check on the input for Zmod and removed the category refinement, and I still got errors.

I am strongly inclined to believe that it is not an issue with category refinement, but instead something is wrong with how the category MRO is being constructed. I would want to simultaneously fix for both #15536 and this, but I'm fairly convinced they are different issues.

Yet another data point. I created a separate class and file for the new category, and then set FiniteDimensionalModulesWithBasis.Filtered to this new class (also now inheriting from FilteredModulesCategory by following what GradedHopfAlgebrasWithBasis does). This now does not set the correct category as

sage: (ModulesWithBasis(ZZ).Filtered().FiniteDimensional()
....:  == ModulesWithBasis(ZZ).FiniteDimensional().Filtered())
False

This is on u/tscrim/test-19397. <edit>Fix bad copying</edit>

I have absolutely no idea what is going on. I would appreciate some comments from those that implemented how the category code handles these things.

[SimonKing]

Replying to tscrim:

Yet another data point. I created a separate class and file for the new category, and then set FiniteDimensionalModulesWithBasis.Filtered to this new class (also now inheriting from FilteredModulesCategory by following what GradedHopfAlgebrasWithBasis does). This now does not set the correct category as

sage: (ModulesWithBasis(ZZ).Filtered().FiniteDimesnional()
....:  != ModulesWithBasis(ZZ).FiniteDimesnional().Filtered())
False

Why is that not correct? If I understand correctly, one meta-axiom (i.e., an axiom for our axiom framework) is that application of axioms commutes. Thus, if you have a category C and axioms A and B, then C.A().B() will always be identical with C.B().A().

[tscrim]

Sorry, that was a copy error, it should have be checking ==.

[SimonKing]

Replying to tscrim:

Sorry, that was a copy error, it should have be checking ==.

OK, if it says that the two categories are not identical then it is a bug.

[jhpalmieri]

It looks like this is caused by the combination of this ticket and #18066. (That is, if I take 6.10.beta1 and merge those two branches, I get doctest failures.)

[tscrim]

Somehow it is caused by the addition of the new explicit (non-join) category and that standard free modules are now in FreeModules(R).FiniteDimensional(), whereas before they were just FreeModules(R) (which is an alias for Modules(R).WithBasis()). Reverting back this change from #18066

+category = FreeModules(base_ring.category()).FiniteDimensional()
-category = FreeModules(base_ring.category())

then all tests pass...but I don't want to do this...

[git]

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

[tscrim]

Sorry about the last push, I messed up using git.

[tscrim]

A more minimal example of the failure is:

sage: Algebras(GF(2)).WithBasis().Graded().FiniteDimensional()

[git]

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

​46434a5

Merge branch 'develop' into t/19397/public/categories/homogeneous_components-19397

[jhpalmieri]

I don't know how to fix the underlying problem, but I have a few other small changes to suggest. First, correct an error message:

src/sage/categories/category.py

@@ -1852 +1852 @@
         if join:
             return Category.join([self, category])
         else:
-            assert category.is_subcategory(self), "Subcategory of `{}` required; got `{}`".format(category, self)
+            assert category.is_subcategory(self), "Subcategory of `{}` required; got `{}`".format(self, category)
             return category
 
     def _is_subclass(self, c):

Second, fix a category (if we fix the MRO problem, this misdefined category causes problems):

src/sage/homology/homology_vector_space_with_basis.py

@@ -435 +435 @@
             sage: H = RP2.cohomology_ring(GF(5))
             sage: TestSuite(H).run()
         """
-        cat = Algebras(base_ring).WithBasis().Graded()
+        cat = Algebras(base_ring).WithBasis().Graded().FiniteDimensional()
         HomologyVectorSpaceWithBasis.__init__(self, base_ring, cell_complex, True, cat)
 
     def _repr_(self):

Finally, this one is cosmetic, but makes the signature of the method agree with the docstring:

src/sage/homology/homology_vector_space_with_basis.py

@@ -144 +144 @@
         sage: b.cup_product(b)
         h^{2,0}
     """
-    def __init__(self, base_ring, cell_complex, cohomology=False, cat=None):
+    def __init__(self, base_ring, cell_complex, cohomology=False, category=None):
         """
         Initialize ``self``.
 
@@ -170 +170 @@
             # We only need the rank of M in each degree, and since
             # we're working over a field, we don't need to dualize M
             # if working with cohomology.
-        cat = Modules(base_ring).WithBasis().Graded().or_subcategory(cat)
+        category = Modules(base_ring).WithBasis().Graded().FiniteDimensional().or_subcategory(category)
         self._contraction = phi
         self._complex = cell_complex
         self._cohomology = cohomology
@@ -178 +178 @@
                                 for deg in range(cell_complex.dimension()+1)}
         indices = [(deg, i) for deg in self._graded_indices
                    for i in self._graded_indices[deg]]
-        CombinatorialFreeModule.__init__(self, base_ring, indices, category=cat)
+        CombinatorialFreeModule.__init__(self, base_ring, indices, category=category)
 
     def basis(self, d=None):
         """

[jhpalmieri]

What do we lose if we delete the last part of the changes to filtered_modules_with_basis.py, that is,

class FiniteDimensional(CategoryWithAxiom_over_base_ring):
        class ParentMethods:
            def homogeneous_component_basis(self, d):
                ...

?

[jhpalmieri]

Indeed, if I delete that and change the earlier definition of homogeneous_component_basis, then all doctests pass. Here is a branch with these changes. Feel free to revert if these are bad ideas.

[git]

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

​2d8e4ef	Merge branch 'develop' into t/19397/public/categories/homogeneous_components-19397
​14f6a28	trac 19397: Fix MRO problem, and a few other minor changes.

[jhpalmieri]

Oh, and in the doctest I moved from the now deleted part, I changed cat from GradedModulesWithBasis(ZZ).FiniteDimensional() to GradedModulesWithBasis(ZZ). We can restore the FiniteDimensional() part if you want.

[tscrim]

This will definitely do as a workaround. We should add an additional check to make sure self._indices is finite and raise an error if not, otherwise the fallback for homogeneous_component_basis will run forever.

Although if we are changing error messages, I think we should also change that assert to raise a ValueError on input because it is checking user input (and I like the convention that an assert is something that is expected to always be true).

Minor point, but I don't think this import is needed anymore

from sage.categories.category_with_axiom import CategoryWithAxiom_over_base_ring

We will also need a follow-up ticket creating the proper (sub)category with an explanation that it causes an MRO failure.

[git]

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

​0519643

trac 19397: change assertion to a try/except block. Remove an unneeded import.

[jhpalmieri]

Replying to tscrim:

This will definitely do as a workaround. We should add an additional check to make sure self._indices is finite and raise an error if not, otherwise the fallback for homogeneous_component_basis will run forever.

I guess I don't know the best way to go about this. If there is no subset method (for example), then check self._indices.is_finite(). If this fails, what error should we raise -- the lack of subset or the failure of finiteness? Or just a general error about the set of indices not being well enough implemented? We can break things down into lots of cases, but that seems like overkill for this piece of error-checking.

Although if we are changing error messages, I think we should also change that assert to raise a ValueError on input because it is checking user input (and I like the convention that an assert is something that is expected to always be true).

I agree.

Minor point, but I don't think this import is needed anymore

from sage.categories.category_with_axiom import CategoryWithAxiom_over_base_ring

Fixed.

[tscrim]

Replying to jhpalmieri:

Replying to tscrim:

This will definitely do as a workaround. We should add an additional check to make sure self._indices is finite and raise an error if not, otherwise the fallback for homogeneous_component_basis will run forever.

I guess I don't know the best way to go about this. If there is no subset method (for example), then check self._indices.is_finite(). If this fails, what error should we raise -- the lack of subset or the failure of finiteness? Or just a general error about the set of indices not being well enough implemented? We can break things down into lots of cases, but that seems like overkill for this piece of error-checking.

I have found that calling list can very often catch infinite sets. So I would do this change

-S = [i for i in self._indices if self.degree_on_basis(i) == d]
+S = [i for i in list(self._indices) if self.degree_on_basis(i) == d]

If this sounds good to you, I can do it as I also want to add a comment saying this will be moved once MRO issues are fixed when creating a the finite-dimensional category.

[jhpalmieri]

That sounds good, please go ahead.

[git]

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

​6c0e7bd

Trying to avoid infinite lists and adding a TODO comment.

[jhpalmieri]

I think there is a word ("when"?) missing in the "TODO" comment.

[git]

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

​068adf3

Trying to avoid infinite lists and adding a TODO comment.

[tscrim]

Replying to jhpalmieri:

I think there is a word ("when"?) missing in the "TODO" comment.

True. I also was able to make it so the text ended at the same position. :P FYI - I decided to amend my previous commit instead of a new one.

[jhpalmieri]

Okay, I'm happy with this now. If you think it's not ready, revert my positive review.

[tscrim]

It is good. Thank you. MRO issue is now #20460.

[vbraun]

sage -t --long src/sage/categories/filtered_modules_with_basis.py
**********************************************************************
File "src/sage/categories/filtered_modules_with_basis.py", line 160, in sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.ParentMethods.basis
Failed example:
    A.basis(4)
Expected:
    Traceback (most recent call last):
    ...
    AttributeError: 'IndexedFreeAbelianMonoid_with_category' object has no attribute 'list'
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.ParentMethods.basis[5]>", line 1, in <module>
        A.basis(Integer(4))
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/categories/filtered_modules_with_basis.py", line 186, in basis
        return self.homogeneous_component_basis(d)
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/categories/filtered_modules_with_basis.py", line 215, in homogeneous_component_basis
        S = [i for i in list(self._indices) if self.degree_on_basis(i) == d]
      File "sage/structure/parent.pyx", line 1548, in sage.structure.parent.Parent.__len__ (/mnt/disk/home/buildslave-sage/slave/sage_git/build/src/build/cythonized/sage/structure/parent.c:12470)
        return len(self.list())
      File "/mnt/disk/home/buildslave-sage/slave/sage_git/build/local/lib/python2.7/site-packages/sage/categories/infinite_enumerated_sets.py", line 76, in list
        raise NotImplementedError("infinite list")
    NotImplementedError: infinite list
**********************************************************************
1 item had failures:
   1 of  10 in sage.categories.filtered_modules_with_basis.FilteredModulesWithBasis.ParentMethods.basis
    [214 tests, 1 failure, 0.75 s]

[jhpalmieri]

Volker, I don't see this failure when I run doctests or when I do it by hand, and I don't see it on the patchbots, either. Do you have any ideas why?

[tscrim]

I also don't get the failure. Maybe something changed with the example implementation in another (already closed) ticket? I certainly can see why this failure might occur...and it is an easy enough fix...

[git]

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

​13fee78	Merge branch 'public/categories/homogeneous_components-19397' of trac.sagemath.org:sage into public/categories/homogeneous_components-19397
​aa85da2	Fixing change in error message and corresponding documentation.

[tscrim]

The problem occurred in beta5 (in fact, I believe I know exactly which ticket caused it...). I fixed the error message and the documentation (I am pretty sure a NotImplementedError will be more common with this change anyways...).

[git]

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

​f9aaad5

Fixing docstring (which should have been on the last commit).

[jhpalmieri]

Looks good to me. Passes all tests.

[tscrim]

Replying to jhpalmieri:

Looks good to me. Passes all tests.

Thank you.