Opened 7 years ago

Closed 6 years ago

#19397 closed enhancement (fixed)

Add support for homogeneous components of a filtered module

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-7.2
Component: categories Keywords:
Cc: sage-combinat, darij, nthiery, SimonKing Merged in:
Authors: Travis Scrimshaw Reviewers: John Palmieri
Report Upstream: N/A Work issues:
Branch: f9aaad5 (Commits, GitHub, GitLab) Commit: f9aaad57b8a72530f3950252c443f30c09a4f13b
Dependencies: #17096 Stopgaps:

Status badges

Description

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.

Change History (54)

comment:1 Changed 7 years ago by tscrim

  • Branch set to public/categories/homogeneous_components-19397
  • Commit set to 9c51a4c0984fc70d4a4ca5464621408559640f66
  • Status changed from new to needs_review

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:

570bc49Merge branch 'public/categories/super_categories-18044' into 6.9.b1
b91cd82trac #18044 correct one typo in the doc
7fd1df2Merge branch 'public/categories/super_categories-18044' of trac.sagemath.org:sage into public/categories/super_categories-18044
0579337Some reviewer tweaks and doc additions.
aec22ccAdded one more test.
4b2046fMerge branch 'public/categories/super_categories-18044' into public/categories/filtered_algebras-17096
3f67b6bFixing trivial doctest due to changes in category heirarchy.
fa476ddFixing double-colon in INPUT block.
6cc8b84Reviewer changes with Darij.
9c51a4cMerge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/graded_components-TBA

comment:2 Changed 7 years ago by 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.

comment:3 Changed 7 years ago by git

  • Commit changed from 9c51a4c0984fc70d4a4ca5464621408559640f66 to ae81aa7c64064ba8de5598aa01210efac57088c9

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

ae81aa7Fixing bad copying.

comment:4 Changed 7 years ago by 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.

comment:5 Changed 7 years ago by 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).

Last edited 7 years ago by tscrim (previous) (diff)

comment:6 Changed 7 years ago by 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.)

comment:7 Changed 7 years ago by 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.

comment:8 Changed 7 years ago by 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!).

Last edited 7 years ago by darij (previous) (diff)

comment:9 Changed 7 years ago by 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.

comment:10 Changed 7 years ago by 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.

comment:11 Changed 7 years ago by 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.

comment:12 Changed 7 years ago by git

  • Commit changed from ae81aa7c64064ba8de5598aa01210efac57088c9 to f89275b059b5dee1488feee46090596c157615c0

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

cd186d0Merge branch 'public/categories/homogeneous_components-19397' of trac.sagemath.org:sage into public/categories/homogeneous_components-19397
f89275bRaise a NotImplementedError if the base ring is filtered.

comment:13 Changed 7 years ago by tscrim

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

comment:14 Changed 7 years ago by jhpalmieri

  • Reviewers set to John Palmieri
  • Status changed from needs_review to positive_review

This looks okay to me.

comment:16 Changed 7 years ago by 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?

comment:17 Changed 7 years ago by vbraun

Can you merge in the next beta when its out?

comment:18 Changed 7 years ago by tscrim

This looks like the same issues located on #15536.

comment:19 Changed 7 years ago by jhpalmieri

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

comment:20 follow-up: Changed 7 years ago by tscrim

  • Cc SimonKing added

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.

Last edited 7 years ago by tscrim (previous) (diff)

comment:21 in reply to: ↑ 20 Changed 7 years ago by 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().

comment:22 follow-up: Changed 7 years ago by tscrim

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

comment:23 in reply to: ↑ 22 Changed 7 years ago by 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.

comment:24 Changed 7 years ago by 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.)

comment:25 Changed 7 years ago by 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...

Last edited 7 years ago by tscrim (previous) (diff)

comment:26 Changed 7 years ago by git

  • Commit changed from f89275b059b5dee1488feee46090596c157615c0 to 92380fef1033e35785ce9f5ea21cc2106b8f3e86

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

comment:27 Changed 7 years ago by tscrim

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

comment:28 Changed 6 years ago by tscrim

A more minimal example of the failure is:

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

comment:29 Changed 6 years ago by git

  • Commit changed from 92380fef1033e35785ce9f5ea21cc2106b8f3e86 to 46434a5a7ac5e0cf926e6b18d3e11323ce040e74

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

46434a5Merge branch 'develop' into t/19397/public/categories/homogeneous_components-19397

comment:30 Changed 6 years ago by 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

    diff --git a/src/sage/categories/category.py b/src/sage/categories/category.py
    index 2d50eac..c022b00 100644
    a b class Category(UniqueRepresentation, SageObject): 
    18521852        if join:
    18531853            return Category.join([self, category])
    18541854        else:
    1855             assert category.is_subcategory(self), "Subcategory of `{}` required; got `{}`".format(category, self)
     1855            assert category.is_subcategory(self), "Subcategory of `{}` required; got `{}`".format(self, category)
    18561856            return category
    18571857
    18581858    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

    diff --git a/src/sage/homology/homology_vector_space_with_basis.py b/src/sage/homology/homology_vector_space_with_basis.py
    index 00f8759..8cbf4f6 100644
    a b class CohomologyRing(HomologyVectorSpaceWithBasis): 
    435435            sage: H = RP2.cohomology_ring(GF(5))
    436436            sage: TestSuite(H).run()
    437437        """
    438         cat = Algebras(base_ring).WithBasis().Graded()
     438        cat = Algebras(base_ring).WithBasis().Graded().FiniteDimensional()
    439439        HomologyVectorSpaceWithBasis.__init__(self, base_ring, cell_complex, True, cat)
    440440
    441441    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

    diff --git a/src/sage/homology/homology_vector_space_with_basis.py b/src/sage/homology/homology_vector_space_with_basis.py
    index 00f8759..8cbf4f6 100644
    a b class HomologyVectorSpaceWithBasis(CombinatorialFreeModule): 
    144144        sage: b.cup_product(b)
    145145        h^{2,0}
    146146    """
    147     def __init__(self, base_ring, cell_complex, cohomology=False, cat=None):
     147    def __init__(self, base_ring, cell_complex, cohomology=False, category=None):
    148148        """
    149149        Initialize ``self``.
    150150
    class HomologyVectorSpaceWithBasis(CombinatorialFreeModule): 
    170170            # We only need the rank of M in each degree, and since
    171171            # we're working over a field, we don't need to dualize M
    172172            # if working with cohomology.
    173         cat = Modules(base_ring).WithBasis().Graded().or_subcategory(cat)
     173        category = Modules(base_ring).WithBasis().Graded().FiniteDimensional().or_subcategory(category)
    174174        self._contraction = phi
    175175        self._complex = cell_complex
    176176        self._cohomology = cohomology
    class HomologyVectorSpaceWithBasis(CombinatorialFreeModule): 
    178178                                for deg in range(cell_complex.dimension()+1)}
    179179        indices = [(deg, i) for deg in self._graded_indices
    180180                   for i in self._graded_indices[deg]]
    181         CombinatorialFreeModule.__init__(self, base_ring, indices, category=cat)
     181        CombinatorialFreeModule.__init__(self, base_ring, indices, category=category)
    182182
    183183    def basis(self, d=None):
    184184        """

comment:31 Changed 6 years ago by 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):
                ...

?

comment:32 Changed 6 years ago by jhpalmieri

  • Status changed from needs_work to needs_review

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.

comment:33 Changed 6 years ago by git

  • Commit changed from 46434a5a7ac5e0cf926e6b18d3e11323ce040e74 to 14f6a2843145309abe777e37ac2c96b8e5984d9a

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

2d8e4efMerge branch 'develop' into t/19397/public/categories/homogeneous_components-19397
14f6a28trac 19397: Fix MRO problem, and a few other minor changes.

comment:34 Changed 6 years ago by 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.

comment:35 Changed 6 years ago by 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.

comment:36 Changed 6 years ago by git

  • Commit changed from 14f6a2843145309abe777e37ac2c96b8e5984d9a to 05196437ca8197300162043ae0949c47bb6083ef

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

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

comment:37 follow-up: Changed 6 years ago by 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.

comment:38 in reply to: ↑ 37 Changed 6 years ago by 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.

comment:39 Changed 6 years ago by jhpalmieri

That sounds good, please go ahead.

comment:40 Changed 6 years ago by git

  • Commit changed from 05196437ca8197300162043ae0949c47bb6083ef to 6c0e7bd2744f734f467cdb3535048ffe9e86c754

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

6c0e7bdTrying to avoid infinite lists and adding a TODO comment.

comment:41 follow-up: Changed 6 years ago by jhpalmieri

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

comment:42 Changed 6 years ago by git

  • Commit changed from 6c0e7bd2744f734f467cdb3535048ffe9e86c754 to 068adf38ed5520faa0f31c34e6b3ef636d595bea

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

068adf3Trying to avoid infinite lists and adding a TODO comment.

comment:43 in reply to: ↑ 41 Changed 6 years ago by 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.

comment:44 Changed 6 years ago by jhpalmieri

  • Status changed from needs_review to positive_review

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

comment:45 Changed 6 years ago by tscrim

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

comment:46 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work
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]

comment:47 Changed 6 years ago by 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?

comment:48 Changed 6 years ago by 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...

comment:49 Changed 6 years ago by git

  • Commit changed from 068adf38ed5520faa0f31c34e6b3ef636d595bea to aa85da2896800d78fff84000483c8847fd9c338a

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

13fee78Merge branch 'public/categories/homogeneous_components-19397' of trac.sagemath.org:sage into public/categories/homogeneous_components-19397
aa85da2Fixing change in error message and corresponding documentation.

comment:50 Changed 6 years ago by tscrim

  • Milestone changed from sage-6.10 to sage-7.2
  • Status changed from needs_work to needs_review

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...).

comment:51 Changed 6 years ago by git

  • Commit changed from aa85da2896800d78fff84000483c8847fd9c338a to f9aaad57b8a72530f3950252c443f30c09a4f13b

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

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

comment:52 follow-up: Changed 6 years ago by jhpalmieri

  • Status changed from needs_review to positive_review

Looks good to me. Passes all tests.

comment:53 in reply to: ↑ 52 Changed 6 years ago by tscrim

Replying to jhpalmieri:

Looks good to me. Passes all tests.

Thank you.

comment:54 Changed 6 years ago by vbraun

  • Branch changed from public/categories/homogeneous_components-19397 to f9aaad57b8a72530f3950252c443f30c09a4f13b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.