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:  sagecombinat 

Priority:  major  Milestone:  sage7.2 
Component:  categories  Keywords:  
Cc:  sagecombinat, 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: 
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
 Branch set to public/categories/homogeneous_components19397
 Commit set to 9c51a4c0984fc70d4a4ca5464621408559640f66
 Status changed from new to needs_review
comment:2 Changed 7 years ago by
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
 Commit changed from 9c51a4c0984fc70d4a4ca5464621408559640f66 to ae81aa7c64064ba8de5598aa01210efac57088c9
Branch pushed to git repo; I updated commit sha1. New commits:
ae81aa7  Fixing bad copying.

comment:4 Changed 7 years ago by
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
comment:6 Changed 7 years ago by
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
One mathematical issue: in defining homogeneous_component
, you have
category = ModulesWithBasis(self.category().base_ring())
A homogeneous component of an Rmodule need not be an Rmodule 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 Rmodule, 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
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 defacto 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!).
comment:9 Changed 7 years ago by
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
However there is a technical problem with doing that in the shortterm 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
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
 Commit changed from ae81aa7c64064ba8de5598aa01210efac57088c9 to f89275b059b5dee1488feee46090596c157615c0
comment:13 Changed 7 years ago by
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
 Reviewers set to John Palmieri
 Status changed from needs_review to positive_review
This looks okay to me.
comment:15 Changed 7 years ago by
 Status changed from positive_review to needs_work
comment:16 Changed 7 years ago by
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
Can you merge in the next beta when its out?
comment:18 Changed 7 years ago by
This looks like the same issues located on #15536.
comment:19 Changed 7 years ago by
With the latest beta, I see these failures. I don't know what to make of them, though.
comment:20 followup: ↓ 21 Changed 7 years ago by
 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/test19397
. <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.
comment:21 in reply to: ↑ 20 Changed 7 years ago by
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 fromFilteredModulesCategory
by following whatGradedHopfAlgebrasWithBasis
does). This now does not set the correct category assage: (ModulesWithBasis(ZZ).Filtered().FiniteDimesnional() ....: != ModulesWithBasis(ZZ).FiniteDimesnional().Filtered()) False
Why is that not correct? If I understand correctly, one metaaxiom (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 followup: ↓ 23 Changed 7 years ago by
Sorry, that was a copy error, it should have be checking ==
.
comment:23 in reply to: ↑ 22 Changed 7 years ago by
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
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
Somehow it is caused by the addition of the new explicit (nonjoin) 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...
comment:26 Changed 7 years ago by
 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
Sorry about the last push, I messed up using git.
comment:28 Changed 6 years ago by
A more minimal example of the failure is:
sage: Algebras(GF(2)).WithBasis().Graded().FiniteDimensional()
comment:29 Changed 6 years ago by
 Commit changed from 92380fef1033e35785ce9f5ea21cc2106b8f3e86 to 46434a5a7ac5e0cf926e6b18d3e11323ce040e74
Branch pushed to git repo; I updated commit sha1. New commits:
46434a5  Merge branch 'develop' into t/19397/public/categories/homogeneous_components19397

comment:30 Changed 6 years ago by
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): 1852 1852 if join: 1853 1853 return Category.join([self, category]) 1854 1854 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) 1856 1856 return category 1857 1857 1858 1858 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): 435 435 sage: H = RP2.cohomology_ring(GF(5)) 436 436 sage: TestSuite(H).run() 437 437 """ 438 cat = Algebras(base_ring).WithBasis().Graded() 438 cat = Algebras(base_ring).WithBasis().Graded().FiniteDimensional() 439 439 HomologyVectorSpaceWithBasis.__init__(self, base_ring, cell_complex, True, cat) 440 440 441 441 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): 144 144 sage: b.cup_product(b) 145 145 h^{2,0} 146 146 """ 147 def __init__(self, base_ring, cell_complex, cohomology=False, cat =None):147 def __init__(self, base_ring, cell_complex, cohomology=False, category=None): 148 148 """ 149 149 Initialize ``self``. 150 150 … … class HomologyVectorSpaceWithBasis(CombinatorialFreeModule): 170 170 # We only need the rank of M in each degree, and since 171 171 # we're working over a field, we don't need to dualize M 172 172 # 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) 174 174 self._contraction = phi 175 175 self._complex = cell_complex 176 176 self._cohomology = cohomology … … class HomologyVectorSpaceWithBasis(CombinatorialFreeModule): 178 178 for deg in range(cell_complex.dimension()+1)} 179 179 indices = [(deg, i) for deg in self._graded_indices 180 180 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) 182 182 183 183 def basis(self, d=None): 184 184 """
comment:31 Changed 6 years ago by
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
 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
 Commit changed from 46434a5a7ac5e0cf926e6b18d3e11323ce040e74 to 14f6a2843145309abe777e37ac2c96b8e5984d9a
comment:34 Changed 6 years ago by
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
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 followup ticket creating the proper (sub)category with an explanation that it causes an MRO failure.
comment:36 Changed 6 years ago by
 Commit changed from 14f6a2843145309abe777e37ac2c96b8e5984d9a to 05196437ca8197300162043ae0949c47bb6083ef
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.

comment:37 followup: ↓ 38 Changed 6 years ago by
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 forhomogeneous_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 errorchecking.
Although if we are changing error messages, I think we should also change that
assert
to raise aValueError
on input because it is checking user input (and I like the convention that anassert
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
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 forhomogeneous_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 checkself._indices.is_finite()
. If this fails, what error should we raise  the lack ofsubset
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 errorchecking.
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 finitedimensional category.
comment:39 Changed 6 years ago by
That sounds good, please go ahead.
comment:40 Changed 6 years ago by
 Commit changed from 05196437ca8197300162043ae0949c47bb6083ef to 6c0e7bd2744f734f467cdb3535048ffe9e86c754
Branch pushed to git repo; I updated commit sha1. New commits:
6c0e7bd  Trying to avoid infinite lists and adding a TODO comment.

comment:41 followup: ↓ 43 Changed 6 years ago by
I think there is a word ("when"?) missing in the "TODO" comment.
comment:42 Changed 6 years ago by
 Commit changed from 6c0e7bd2744f734f467cdb3535048ffe9e86c754 to 068adf38ed5520faa0f31c34e6b3ef636d595bea
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.

comment:43 in reply to: ↑ 41 Changed 6 years ago by
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
 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
It is good. Thank you. MRO issue is now #20460.
comment:46 Changed 6 years ago by
 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/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 496, in _run self.compile_and_execute(example, compiler, test.globs) File "/mnt/disk/home/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/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/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/sage/categories/filtered_modules_with_basis.py", line 186, in basis return self.homogeneous_component_basis(d) File "/mnt/disk/home/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/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/buildslavesage/slave/sage_git/build/src/build/cythonized/sage/structure/parent.c:12470) return len(self.list()) File "/mnt/disk/home/buildslavesage/slave/sage_git/build/local/lib/python2.7/sitepackages/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
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
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
 Commit changed from 068adf38ed5520faa0f31c34e6b3ef636d595bea to aa85da2896800d78fff84000483c8847fd9c338a
comment:50 Changed 6 years ago by
 Milestone changed from sage6.10 to sage7.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
 Commit changed from aa85da2896800d78fff84000483c8847fd9c338a to f9aaad57b8a72530f3950252c443f30c09a4f13b
Branch pushed to git repo; I updated commit sha1. New commits:
f9aaad5  Fixing docstring (which should have been on the last commit).

comment:52 followup: ↓ 53 Changed 6 years ago by
 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
comment:54 Changed 6 years ago by
 Branch changed from public/categories/homogeneous_components19397 to f9aaad57b8a72530f3950252c443f30c09a4f13b
 Resolution set to fixed
 Status changed from positive_review to closed
This will be useful along with the changes I'm making in #6102, which I think will be our first naturally graded finitedimensional algebra in Sage.
Last 10 new commits:
Merge branch 'public/categories/super_categories18044' into 6.9.b1
trac #18044 correct one typo in the doc
Merge branch 'public/categories/super_categories18044' of trac.sagemath.org:sage into public/categories/super_categories18044
Some reviewer tweaks and doc additions.
Added one more test.
Merge branch 'public/categories/super_categories18044' into public/categories/filtered_algebras17096
Fixing trivial doctest due to changes in category heirarchy.
Fixing doublecolon in INPUT block.
Reviewer changes with Darij.
Merge branch 'public/categories/filtered_algebras17096' of trac.sagemath.org:sage into public/categories/graded_componentsTBA