Opened 8 years ago
Closed 7 years ago
#17096 closed enhancement (fixed)
Implement categories for filtered algebras
Reported by:  tscrim  Owned by:  tscrim 

Priority:  major  Milestone:  sage6.10 
Component:  categories  Keywords:  filtered algebras 
Cc:  nthiery, darij, days64, sd67  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  6cc8b84 (Commits, GitHub, GitLab)  Commit:  6cc8b8460dfe5a05380e73e667dc7294e4369774 
Dependencies:  #18044  Stopgaps: 
Change History (99)
comment:1 followup: ↓ 2 Changed 8 years ago by
 Branch set to public/categoires/filtered_algebras17096
 Commit set to ad184efacc9ceabfb1179ccd4d677786f4713b01
 Status changed from new to needs_review
comment:2 in reply to: ↑ 1 ; followup: ↓ 3 Changed 8 years ago by
Replying to tscrim:
 Every graded algebra is a filtered algebra under the "natural" filtration of summing over (weakly) smaller degrees (assuming total ordering on the grading group). This is implicit in the category structure; nothing specific is implemented.
Of course, depending on the context, the converse convention can also sense; but maybe that's ok because eventually we will have both filtered and descendingFiltered (or something similar) categories.
http://en.wikipedia.org/wiki/Filtration_%28mathematics%29
 Every
graded_*
category hasfiltered_*
as an immediate super category. In particular, this is needed forGradedAlgebrasWithBasis
not picking upFilteredAlgebrasWithBasis
in its super categories otherwise.
This seems like the same situation as for quotients
w.r.t. subquotients. So the same mechanism should do the job (see
sage.categories.quotients.Quotients.default_super_categories
). Please
confirm!
 Homogeneous elements for filtered algebras are elements in F_{i} not in F_{i1}. I don't know if this is a standard definition, but it allowed extensions of methods from graded to filtered.
I see the point. The inconvenient is of course that this makes the set of homogeneous elements for a given i not be a vector space. What do you do with 0 btw?
Cheers,
Nicolas
comment:3 in reply to: ↑ 2 Changed 8 years ago by
 Branch changed from public/categoires/filtered_algebras17096 to public/categories/filtered_algebras17096
 Commit changed from ad184efacc9ceabfb1179ccd4d677786f4713b01 to bb234ec71d1276c6cc14320074b3de6fdc606192
Replying to nthiery:
Of course, depending on the context, the converse convention can also sense; but maybe that's ok because eventually we will have both filtered and descendingFiltered (or something similar) categories.
True, but I figured we'd cross that bridge when we have a need/desire for it.
This seems like the same situation as for quotients w.r.t. subquotients. So the same mechanism should do the job (see
sage.categories.quotients.Quotients.default_super_categories
). Please confirm!
Thanks. Done.
I see the point. The inconvenient is of course that this makes the set of homogeneous elements for a given i not be a vector space. What do you do with 0 btw?
Raise an error as previously for graded objects saying it doesn't have a well defined degree.
New commits:
bb234ec  Use default_super_categories instead of extra_super_categories.

comment:4 followup: ↓ 5 Changed 8 years ago by
1) What does the _element_constructor_
in associated_graded.py
do? I understand that it constructs an element of gr A from an element a of A, but the way it does this I do not think is correct.
The "right" thing to do is this: For a given pair (a, n)
where n
is a nonnegative integer and a
is an element of the n
th filtered part of A
, the residue class of a
modulo the (n1)
th filtered part of A
is an element of the n
th graded component of \gr A
. The n
is part of the input; you can try to reconstruct it as the smallest i
such that a
lies in the i
th filtered part of A
, but such a definition will be illbehaved.
2) I think you need some requirements on the basis of a FilteredModulesWithBasis? for your code to work. I would guess you want the basis to be a sequence (B_0, B_1, B_2, ...)
of sets such that for every n
, the union B_0 \cup B_1 \cup ...\cup B_n
is a basis of the n
th filtered component. Is it what you want?
comment:5 in reply to: ↑ 4 Changed 8 years ago by
Replying to darij:
1) What does the
_element_constructor_
inassociated_graded.py
do? I understand that it constructs an element of gr A from an element a of A, but the way it does this I do not think is correct.The "right" thing to do is this: For a given pair
(a, n)
wheren
is a nonnegative integer anda
is an element of then
th filtered part ofA
, the residue class ofa
modulo the(n1)
th filtered part ofA
is an element of then
th graded component of\gr A
. Then
is part of the input; you can try to reconstruct it as the smallesti
such thata
lies in thei
th filtered part ofA
, but such a definition will be illbehaved.
Hmmm....maybe this shouldn't be a coercion then since if ab = c1 + c2
(where deg(c1) > deg(c2)
), then G(ab) != G(c1) + G(c2)
. The implementation of _element_constructor_
is definitely the right conversion however (the natural vector space isomorphism). So I'll remove the coercion part but leave the _element_constructor_
.
2) I think you need some requirements on the basis of a FilteredModulesWithBasis? for your code to work. I would guess you want the basis to be a sequence
(B_0, B_1, B_2, ...)
of sets such that for everyn
, the unionB_0 \cup B_1 \cup ...\cup B_n
is a basis of then
th filtered component. Is it what you want?
No, the basis does not have to be ordered with respect to the degree. I also don't see where in the code this is used (I just moved it over from the graded modules, so I may not have looked hard enough).
comment:6 followup: ↓ 7 Changed 8 years ago by
That _element_constructor_
definitely shouldn't be a coercion, but even not being a coercion it should be surrounded with big fat warning signs for not being what one would expect.
I don't understand your answer to 2). Even your own doc says that the basis is graded:
+ def basis(self, d=None): + """ + Return the basis for (an homogeneous component of) ``self``.
This means precisely that the basis elements have nonnegative integers ascribed to them, which stand for something like degree.
Generally, it seems to me that your filtered modules are precisely the same as graded modules, and only the richer "sub"categories (filtered algebras, filtered coalgebras etc.) differ from their graded counterparts. If so, this is a perfectly fine design decision, but it would help to document it explicitly.
comment:7 in reply to: ↑ 6 ; followup: ↓ 8 Changed 8 years ago by
Replying to darij:
That
_element_constructor_
definitely shouldn't be a coercion, but even not being a coercion it should be surrounded with big fat warning signs for not being what one would expect.
You wouldn't expect it to be the canonical linear isomorphism (as modules)? So given some x + y
in the filtered algebra A
, you wouldn't expect it to return x + y
in gr A
? Instead you'd want it to return only x
(assuming it has larger degree)? This would be extremely surprising to me (we have a method to remove the lower order terms too). Or am I not understanding what you're saying?
I don't understand your answer to 2). Even your own doc says that the basis is graded:
+ def basis(self, d=None): + """ + Return the basis for (an homogeneous component of) ``self``.This means precisely that the basis elements have nonnegative integers ascribed to them, which stand for something like degree.
Well, any (additive) abelian group. Yet I'm not requiring that the i
th element of the basis be the only element of degree i
. Again, an element is homogeneous of degree d if it belongs to F_{d} but not F_{d1}. However I am requiring that F_{d} is a subspace.
Generally, it seems to me that your filtered modules are precisely the same as graded modules, and only the richer "sub"categories (filtered algebras, filtered coalgebras etc.) differ from their graded counterparts. If so, this is a perfectly fine design decision, but it would help to document it explicitly.
In my (naive) world, filtrations are not really different than grading for modules. That's not to say they aren't useful though because of things like I
adic topology (TBH, this is wikipedia talking). However I don't think we need doc on this. Nicolas, do you have any thoughts?
I could add something about the terminology for homogeneous in terms of the filtration if that's nonstandard or unclear.
Question, should we make Weyl and Clifford algebras filtered on this ticket or on a followup since that's been closed? Same for group algebras by the length function.
comment:8 in reply to: ↑ 7 Changed 8 years ago by
Replying to tscrim:
Replying to darij:
That
_element_constructor_
definitely shouldn't be a coercion, but even not being a coercion it should be surrounded with big fat warning signs for not being what one would expect.You wouldn't expect it to be the canonical linear isomorphism (as modules)? So given some
x + y
in the filtered algebraA
, you wouldn't expect it to returnx + y
ingr A
? Instead you'd want it to return onlyx
(assuming it has larger degree)? This would be extremely surprising to me (we have a method to remove the lower order terms too). Or am I not understanding what you're saying?
Well, I wouldn't expect to have any map from A
to gr(A)
when A
is a filtered module/algebra, and the closest thing that comes to such a map would be a sequence of maps p_0, p_1, p_2, ...
where p_n
sends degree\leq n elements of A
to the n
th graded component of gr(A)
. However, when A
is a filtered module/algebra *with basis*, then your _element_constructor
can be viewed as a canonical map from A
to gr(A)
indeed (it depends on the basis, but this is no problem because the basis is part of A
's data). You may find this a squeamish distinction, but the way most algebraists think about filtrations is not the way you do. For most algebraists, a filtered algebra has an associated graded algebra even if it does not have a basis or has several natural bases; and when things depend on a choice of basis, one regards these things as properties of the basis rather than properties of the algebra. This is why I want you to document this all so carefully.
Well, any (additive) abelian group. Yet I'm not requiring that the
i
th element of the basis be the only element of degreei
.
Oh! I think we misunderstood each other here.
In my (naive) world, filtrations are not really different than grading for modules.
Once again, this is good (I think this is the best we can do explicitly in a CAS, whereas the algebraists' notion of a filtered algebra would be some indiscrete lazy object)  but this absolutely needs to be doced. This is plainly not the way algebraists think.
Question, should we make Weyl and Clifford algebras filtered on this ticket or on a followup since that's been closed? Same for group algebras by the length function.
Followup, definitely. The ticket has been closed already and I don't think this one will be done too quickly.
comment:9 Changed 8 years ago by
 Commit changed from bb234ec71d1276c6cc14320074b3de6fdc606192 to 5f6337908a43200ef3283e6dd24f4f6c6da66ee9
comment:10 Changed 8 years ago by
 Commit changed from 5f6337908a43200ef3283e6dd24f4f6c6da66ee9 to 2aec8bdaeba3c34478807342b5659b8e8ceca2f4
Branch pushed to git repo; I updated commit sha1. New commits:
2aec8bd  Fixing some typos.

comment:11 Changed 8 years ago by
Okay, I've put in some comments about the translation A <> gr A
(it actually wasn't a coercion to begin with) and defined some terms. If you feel anything more needs to be doc'ed, then could you add it in since I'm not sure what more you think is needed?
Although I think there is still a module isomorphism which sends G_i > F_i  F_{i1}
(since I require each F_i
to be a module. Perhaps I'm missing something subtle (and I can't really think in coordinatefree terms very well).
comment:12 Changed 8 years ago by
I think your doc is inconsistent. This can't be:
+We require all `F_i \setminus F_{i1}` to be modules for all `i`.
What do you want F_i
to be? The span of all elements UP TO degree i
, or the span of all elements that are added by degree i
? So when you consider a graded module as a filtered module, then will F_i
be the i
th graded component or the direct sum of the 0, 1, ..., i
th graded components? In the former case, you don't want a setminus at all. In the latter case, setminus is the right idea but the wrong notation, and you want to say something like F_i = F_{i1} \oplus G_i
where G_i
is the submodule spanned by the degree i
basis elements.
comment:13 Changed 8 years ago by
For filtered algebras, we (only) have F_{0} <= F_{1} <= ..., so for graded modules, we'd have G_{i} = F_{i}  F_{i1} because we want that construction of F_{i} = F_{i1} (+) G_{i} (starting with F_{0} = G_{0}). Actually, there is something that is wrong; the setminus isn't correct because it removes 0. It should be a quotient F_{i} / F_{i1}, but other than that, it's consistent.
comment:14 Changed 8 years ago by
 Commit changed from 2aec8bdaeba3c34478807342b5659b8e8ceca2f4 to 592ba1176ae7a337c40792c0da3d439831ea3dc0
comment:15 Changed 8 years ago by
 Commit changed from 592ba1176ae7a337c40792c0da3d439831ea3dc0 to 60beb17df13f5399d9ce13f21984e903f77d3ea9
Branch pushed to git repo; I updated commit sha1. New commits:
60beb17  More explicit documentation.

comment:16 Changed 8 years ago by
 Commit changed from 60beb17df13f5399d9ce13f21984e903f77d3ea9 to 9d567ea2aaa030f51dbf2e966c8584bd2d8489ee
comment:17 Changed 8 years ago by
I have rewritten the doc to convey *my* understanding of your classes. It will probably have typos and wrong references  sorry for that, I just can't manage to keep looking at sage categories for longer than a couple hours , but if you see something that looks seriously wrong to you, chances are I have misunderstood your code and we need to discuss it over. I suspect I am not done with this patch either way, but I am going to return to tableaux and polytopes for a week or so.
I think there should be a onestop shop in the doc to read up all of the (nonstandard but reasonable!) terminology around filtrations and gradings in Sage. Which should explain what "homogeneous" means for a filtered algebra, etc., and which should be referenced in the methodlevel and maybe even in the classlevel docs. Where do you think such a thing would fit?
Also, there are two doctests failure that this patch incurs for some weird reason:
sage t src/sage/categories/category_with_axiom.py ********************************************************************** File "src/sage/categories/category_with_axiom.py", line 2513, in sage.categories.category_with_axiom.CategoryWithAxiom_singleton Failed example: C.FiniteDimensional() Expected: Category of finite dimensional connected test objects over base ring over Ring of integers modulo 2 Got: Category of finite dimensional test objects over base ring over Ring of integers modulo 2 ********************************************************************** File "src/sage/categories/category_with_axiom.py", line 2515, in sage.categories.category_with_axiom.CategoryWithAxiom_singleton Failed example: C.Connected() Expected: Category of connected test objects over base ring over Ring of integers modulo 2 Got: Category of test objects over base ring over Ring of integers modulo 2 **********************************************************************
Also, an easy one:
sage t src/sage/categories/category.py ********************************************************************** File "src/sage/categories/category.py", line 2627, in sage.categories.category.category_graph Failed example: sage.categories.category.category_graph().plot() Expected: Graphics object consisting of 312 graphics primitives Got: Graphics object consisting of 324 graphics primitives
comment:18 Changed 8 years ago by
 Commit changed from 9d567ea2aaa030f51dbf2e966c8584bd2d8489ee to a11c501518c6785db1a99c78c04a1e38c2daff67
Branch pushed to git repo; I updated commit sha1. New commits:
403b6ad  Merge branch 'develop' into public/categories/filtered_algebras17096

198537c  Merge branch 'public/categories/filtered_algebras17096' of trac.sagemath.org:sage into public/categories/filtered_algebras17096

a4bc65c  Fix failing doctests.

a15a170  Made CliffordAlgebra into a filtered algebra.

41fbe5c  Made Weyl algebra into a filtered algebra.

a11c501  Documentation changes and added to docbuild.

comment:19 Changed 8 years ago by
 Commit changed from a11c501518c6785db1a99c78c04a1e38c2daff67 to 8e586e241a4365f8c21aa9d4f82fdcf920955b0a
Branch pushed to git repo; I updated commit sha1. New commits:
8e586e2  Merge branch 'develop' into public/categories/filtered_algebras17096

comment:20 Changed 8 years ago by
I've fixed some things around, in particular, I made the definitions as general as possible. Because the basis for a filtered module are assumed to be homogeneous elements, the multiplication for the associated graded algebras is independent of the choice of basis. Actually, I'm pretty sure the important chunk of the assoc. graded algebras could be generalized for filtered algebras without a distinguished basis (or when the input is not a CombinatorialFreeModule), but I think that can wait. I also put Clifford and (Diff) Weyl algebras as filtered algebras because it was easy enough to do.
comment:21 Changed 8 years ago by
Can you go skypeon?
comment:22 Changed 8 years ago by
 Commit changed from 8e586e241a4365f8c21aa9d4f82fdcf920955b0a to 45aca1bb8e9492c4b076532a89c9334eec4dc1d2
Branch pushed to git repo; I updated commit sha1. New commits:
45aca1b  Changed some doc from conversation with Darij.

comment:23 Changed 8 years ago by
 Commit changed from 45aca1bb8e9492c4b076532a89c9334eec4dc1d2 to fe0e481ea01cf440ef5841f53ec9cb1a27d36862
Branch pushed to git repo; I updated commit sha1. New commits:
fe0e481  fixes to associated_graded.py

comment:24 Changed 8 years ago by
 Commit changed from fe0e481ea01cf440ef5841f53ec9cb1a27d36862 to b2bc6f59a7daf29f2e55fe0db40a241c06066b6e
Branch pushed to git repo; I updated commit sha1. New commits:
b2bc6f5  self.base_one removed

comment:25 Changed 8 years ago by
 Commit changed from b2bc6f59a7daf29f2e55fe0db40a241c06066b6e to b32aaf289e6a152a8938a87a6865d510d818bfb6
Branch pushed to git repo; I updated commit sha1. New commits:
b32aaf2  further review changes

comment:26 Changed 8 years ago by
 Commit changed from b32aaf289e6a152a8938a87a6865d510d818bfb6 to 68b47a88d9a650d3633f1b4ba3492b8a7bc3dabe
Branch pushed to git repo; I updated commit sha1. New commits:
68b47a8  Better return of algebra_generators for filtered alg w/ basis example.

comment:27 Changed 8 years ago by
 Commit changed from 68b47a88d9a650d3633f1b4ba3492b8a7bc3dabe to c3b29504eb8ec28ec0fe47b82ef59079f8f494c4
Branch pushed to git repo; I updated commit sha1. New commits:
c3b2950  enough for today

comment:28 Changed 8 years ago by
I have left a few TODOs in the doc, which would profit a lot from someone looking into them.
Note to self: I am at filtered_modules_with_basis.py
.
comment:29 Changed 8 years ago by
 Commit changed from c3b29504eb8ec28ec0fe47b82ef59079f8f494c4 to b29f67e46e18721313330d3a6e116cf3df2eaf8e
comment:30 followup: ↓ 31 Changed 8 years ago by
[Only a quick look at Clifford  too swamped with work again.]
You implemented a graded_algebra
method on the Clifford algebra; but does the algebra it return satisfy the contract of an associated graded algebra? Will it have the _element_constructor_
, to_graded_conversion
, from_graded_conversion
and projection
methods that allow one to relate its elements to the elements of the Clifford?
comment:31 in reply to: ↑ 30 Changed 8 years ago by
Replying to darij:
[Only a quick look at Clifford  too swamped with work again.]
You implemented a
graded_algebra
method on the Clifford algebra; but does the algebra it return satisfy the contract of an associated graded algebra? Will it have the_element_constructor_
,to_graded_conversion
,from_graded_conversion
andprojection
methods that allow one to relate its elements to the elements of the Clifford?
Currently there is no such contract (all graded algebras would not satisfy such a contract as well because they return themselves). However the _element_constructor_
and the natural conversion (projection) comes along for free (at least I believe it should, I didn't explicitly check).
comment:32 followup: ↓ 33 Changed 8 years ago by
For the graded algebras returning themselves, this can  and should  be fixed. I think the contract is important  the ass. gr. algebra without it is like a free algebra without a way to access its generators. Is it necessary to define the ass. gr. algebra of a filtered Clifford algebra to be the exterior algebra?
EDIT: On a second thought, maybe it is better to implement the projection and the backandforth isos not as methods on the ass. gr. algebra but as methods on the filtered algebra. This allows one and the same graded algebra to serve as the ass. gr. alegbra for several different filtered algebras. Would this make sense?
comment:33 in reply to: ↑ 32 ; followup: ↓ 77 Changed 8 years ago by
Replying to darij:
For the graded algebras returning themselves, this can  and should  be fixed. I think the contract is important  the ass. gr. algebra without it is like a free algebra without a way to access its generators. Is it necessary to define the ass. gr. algebra of a filtered Clifford algebra to be the exterior algebra?
EDIT: On a second thought, maybe it is better to implement the projection and the backandforth isos not as methods on the ass. gr. algebra but as methods on the filtered algebra. This allows one and the same graded algebra to serve as the ass. gr. alegbra for several different filtered algebras. Would this make sense?
Actually, these were bad ideas. Sorry, I don't think overwriting the graded_algebra
method does any good, unless the return value is a refinement of what it would normally be (i.e., the AssociatedGradedAlgebra
of self
).
For an example why preserving a contract (and having a contract in the first place) is important, let's recall that gr
is a functor. In fact, every filtrationpreserving map f : A > B
of filtered modules induces a graded map gr f : gr A > gr B
of the associated gradeds. This map gr f
sends the residue class of any a \in F_n(A)
(this means the n
th filtered part of A
) to the residue class of f(a) \in F_n(B)
. (This is *not* the map that would be obtained by composing the canonical iso gr A > A
with f : A > B
and then with the canonical iso B > gr B
when A
and B
are graded with basis. It is defined even without bases.) How would we implement this (on filtered modules or algebras with basis)? I would proceed like this:
def induced_graded_map(self, other, f): r""" Return the graded linear map ``self`` `\to` ``other`` canonically induced by a linear map `f` from the filtered module whose associated graded module is ``self`` to the filtered module whose associated graded module is ``other``. [...] """ # not tested A = self._A # This requires ``self`` to have a ``_A`` attribute, # which must be part of the contract. def on_basis(m): i = self.degree_on_basis(m) # This needs a ``degree_on_basis`` method on ``self``. return other.projection(i)(f(A.monomial(m))) # This needs the ``projection`` method to exist on # ``other``. # This assumes that the basis element of ``A`` indexed # by ``m`` is a lift of the basis element of ``self`` # indexed by ``m``. This is a fairly harmless assumption. return self.module_morphism(on_basis=on_basis, codomain=other, category=self.category()) """
This is a piece of code so basic and general that it should be in associated_graded.py
. But if we start redefining graded_algebra
in ways that remove its _A
attribute, its projection
method and whatever else, then this code breaks.
I suck at Python OOP; do you know a way to take an existing instance of AssociatedGraded
and add some methods to it? If this is possible, then I think this is what overrides of graded_algebra
should be doing. For instance, the graded algebra of a Clifford algebra should be its AssociatedGraded
, but with a coercion to and from the exterior algebra.
comment:34 Changed 8 years ago by
Don't forget that code like this (which initializes default categories):
+ if graded: + category = AlgebrasWithBasis(R).Graded() + else: + category = AlgebrasWithBasis(R).Filtered()
should do instead AlgebrasWithBasis(R.category())
to avoid a certain source of memory leaks: categories are immortal, so you should avoid making potentially arbitrarily many of them as much as possible. See:
sage: GF(3)['x'].category() Join of Category of euclidean domains and Category of commutative algebras over (finite fields and subquotients of monoids and quotients of semigroups)
Once someone asks for [AlgebrasWithBasis(GF(p)): p in prime_range(2,100000)]
they're in it by choice, but by default we should not be making categories that explicitly refer to parametrized quantities. We can store those in the parents themselves, where avoiding memory leaks is hard enough. The design of categories simply didn't take into account that they might need to be collected again.
See #17360 for a similar category initialization problem.
comment:35 Changed 8 years ago by
A few questions and comments:
 in
filtered_modules.py
, it talks about modules over a commutative ring, but the word "commutative" can be deleted, I think.  in the same file, it says
.. TODO:: Implement a notion for decreasing filtrations: where `F_j \subseteq F_i`.
If you want to keep this remark, then you should add "when i \leq j". But do you need to keep this? If you want a decreasing filtration, just use the nonpositive integers for your indexing set instead of nonnegative integers. For example, if you have an algebraA
and an idealI
, then you can setF_{n}A
equal to then
th power ofI
. Then you haveF_0 \supseteq F_{1} \supseteq F_{2} \supseteq ...
: a decreasing filtration.  How could we implement an algebra which is both graded and filtered? This is the situation for the Steenrod algebra, for example.
comment:36 Changed 8 years ago by
I have edited my latest reply.
In other news, is it guaranteed that every instance of FilteredAlgebrasWithBasis
is a subcategory of FilteredModulesWithBasis
? If so, I suggest moving the ElementMethods
is_homogeneous
, homogeneous_degree
, degree
and maximal_degree
out of the algebras class and into the modules class (merging their doctests in case both exist).
The associatedgraded construction should also be defined for modules rather than algebras; the algebras version should be a refinement that additionally gives a multiplication and a unity. Can this be implemented easily in your framework, Travis?
comment:37 followups: ↓ 39 ↓ 61 Changed 8 years ago by
@darij
I really don't like the restrictions of this contract you want to impose; it's too restrictive. It should not take a new *class* to do something which is mathematically trivial (by our current implementation of an implicit filtration). IMO, the better way to do things is to implement additional methods in the category for the projections (similar to truncate
) since the methods only use the degree
methods. Also I think requesting a conversion for the returned object graded_algebra
is fine, but not making it a requirement.
As for the induced morphisms, we might actually want to make the method a functor object. This I think will solve many of the issues you want to do with contracts.
All I wanted with the AssociatedGradedAlgebra
class was to prove a generic implementation do to the computations and the method graded_algebra
just to return an object which *is* the associated graded algebra. My implementation of AssociatedGradedAlgebra
just happens to have the need for the extra data.
Every FilteredAlgebrasWithBasis
is a subcategory of FilteredModulesWithBasis
. I'm okay with this move. If we use methods (instead of contracts) at the FilteredModules
level (perhaps WithBasis
), then we could implement a very lightweight class for this, but I'm worried about having the extra burden of methods that only are really useful for modules (and get superseded for "better" named methods). Although if we use a functor to do the construction, then I feel like we get away from all of it.
However I feel that much of this should be done on followup ticket(s) as getting the basic framework into Sage can be split and doesn't need the full features to be useful.
@jhpalmieri
I'll make those changes. However we can't get a descending filtration unless the grading set can be negated. As for algebras that are both filtered and graded, it's the same issue as when an algebra has 2 natural gradings (as we use degree
for both filtration and grading). Although as things evolve and the filtration can be generalized from using degree
, this can be rectified. For now, you have to choose the "best" one for degree
(or have it be an optional arg like how I'm doing for Clifford algebras).
@nbruin Will fix. Forgot that the categories are not collectible.
comment:38 Changed 8 years ago by
I'll make those changes. However we can't get a descending filtration unless the grading set can be negated.
You can get something mathematically equivalent to a descending filtration, though, and maybe that should be good enough?
I wonder if we should use degree
for grading and filtration
for a filtration: x.filtration()
would return n
if x
is in F_n
but not in F_{n1}
. For a filtered object, degree
would default to be filtration
, but you could override it in any specific case. (Maybe these aren't the best names, but you get the idea.)
If this is the first ticket with filtrations, at least in any systematic way, we can decide how to set it up now rather than having to fix it later.
comment:39 in reply to: ↑ 37 ; followup: ↓ 40 Changed 8 years ago by
Replying to tscrim:
@darij I really don't like the restrictions of this contract you want to impose; it's too restrictive. It should not take a new *class* to do something which is mathematically trivial (by our current implementation of an implicit filtration). IMO, the better way to do things is to implement additional methods in the category for the projections (similar to
truncate
) since the methods only use thedegree
methods.
Care to elaborate how this will work?
comment:40 in reply to: ↑ 39 Changed 8 years ago by
Replying to darij:
Care to elaborate how this will work?
Move to_graded_conversion
, from_graded_conversion
, and projection
into FilteredModulesWithBasis
. This would have the effect of reversing the meaning of to/from, but it would make me feel better that the morphisms are tied to the domain (whereas putting them in the graded part, they would be tied to the codomain, making the maps collectible and can cause the coercion issues). Plus it gives a natural extension to GradedModulesWithBasis
and you could use the homogeneous_component
method to construct the projection
method.
In fact, if we do this properly, we can have a category for algebras whose associated graded is commutative (I thought this was called something like virtually commutative, but I can't find where I saw this...) where we can use a faster generic implementation. Again, something for later.
comment:41 followup: ↓ 42 Changed 8 years ago by
Ah! This is a good idea; then induced_graded_map
will also have to be moved to the filtered algebra class. Can you move the three methods you mentioned please? I will then implement induced_graded_map
.
So let me get it right: The class AssociatedGraded
is not going to be a class to be inherited from; it will plainly be the way to construct associated graded algebras if nothing better is known. The data connecting gr(A)
to A
will be stored on A
rather than on gr(A)
. I assume it makes sense to make graded_algebra
a cached method to avoid cases where it is not UniqueRepresentation
?
Also, could you reply to my post 36? I don't see FilteredAlgebrasWithBasis
ever mentioning FilteredModulesWithBasis
as a supercategory, but I guess it should, and I guess its methods should be on FilteredModulesWithBasis
as well.
comment:42 in reply to: ↑ 41 ; followups: ↓ 43 ↓ 44 Changed 8 years ago by
Replying to darij:
Ah! This is a good idea; then
induced_graded_map
will also have to be moved to the filtered algebra class. Can you move the three methods you mentioned please? I will then implementinduced_graded_map
.
Will do tomorrow, but will do (plus incorporate John's and Nils' changes).
So let me get it right: The class
AssociatedGraded
is not going to be a class to be inherited from; it will plainly be the way to construct associated graded algebras if nothing better is known. The data connectinggr(A)
toA
will be stored onA
rather than ongr(A)
. I assume it makes sense to makegraded_algebra
a cached method to avoid cases where it is notUniqueRepresentation
?
Yes, that's correct (although it could be subclasssed but that's not my intent when I designed it). However it doesn't need to be a cached method because everything comes along for the ride from the category (and it should return an equal object every time). Nils, does this lead to a memory leak when a @cached_method
return a UniqueRepresentation
? I think it does but I don't remember...
Also, could you reply to my post 36? I don't see
FilteredAlgebrasWithBasis
ever mentioningFilteredModulesWithBasis
as a supercategory, but I guess it should, and I guess its methods should be onFilteredModulesWithBasis
as well.
I did in comment:37 and said it was okay with me to move the methods. It's the category and axiom magic which makes the supercategory property hold.
comment:43 in reply to: ↑ 42 ; followup: ↓ 46 Changed 8 years ago by
Replying to tscrim:
Yes, that's correct (although it could be subclasssed but that's not my intent when I designed it). However it doesn't need to be a cached method because everything comes along for the ride from the category (and it should return an equal object every time).
Care to explain this? I'm still a newbie to memory handling, so I might be missing more of the context than you expect. My worry was that every time A.graded_algebra()
is called (and it will be called a lot, say, from the to_graded_conversion
and projection
methods), a new instance of this algebra is created, which takes time and space and might require additional work to make these instances coerce to each other nicely (I guess they will do so themselves automatically, but e.g. their polynomial rings might not).
Also, should I then explain in the doc that everybody who overshadows graded_algebra
must also overshadow projection
, to_graded_conversion
and from_graded_conversion
?
I did in comment:37 and said it was okay with me to move the methods. It's the category and axiom magic which makes the supercategory property hold.
Great  as long as this magic doesn't force every algebra which happens to be filtered as a module to automatically be considered a filtered algebra.
comment:44 in reply to: ↑ 42 Changed 8 years ago by
Replying to tscrim:
Yes, that's correct (although it could be subclasssed but that's not my intent when I designed it). However it doesn't need to be a cached method because everything comes along for the ride from the category (and it should return an equal object every time). Nils, does this lead to a memory leak when a
@cached_method
return aUniqueRepresentation
? I think it does but I don't remember...
Quite possibly. See #14356 comment 6 and https://groups.google.com/forum/#!msg/sagedevel/q5uy_lI11jg/CB15fcRmE4cJ
The main thing to watch out for is caching on an object A a UniqueRepresentation object B that has A as a construction parameter.
As pointed out in the referenced comment, one is usually in the clear if the construction parameters of a UniqueRepresentation are fundamentally simpler than the object itself. I'd say that fails for AssociatedGradedAlgebra if that takes an algebra it's isomorphic to as an ungraded algebra as construction parameter! I would consider making it a factory and construct from only the base ring, generator names, grading information etc. and then link it via the coercion framework/cached methods. Then at least it's clear that strong references are held locally. It's important to realize that UniqueRepresentation has a serious cost associated with it.
comment:45 Changed 8 years ago by
 Commit changed from b29f67e46e18721313330d3a6e116cf3df2eaf8e to 096538121130679a55b971d3d3a5626e94b157a5
Branch pushed to git repo; I updated commit sha1. New commits:
0965381  Changes from discussion on trac.

comment:46 in reply to: ↑ 43 ; followup: ↓ 47 Changed 8 years ago by
Replying to darij:
Care to explain this? I'm still a newbie to memory handling, so I might be missing more of the context than you expect. My worry was that every time
A.graded_algebra()
is called (and it will be called a lot, say, from theto_graded_conversion
andprojection
methods), a new instance of this algebra is created, which takes time and space and might require additional work to make these instances coerce to each other nicely (I guess they will do so themselves automatically, but e.g. their polynomial rings might not).
See Nils comment for the memory. Short version is you get a reference loop A > grA
and grA > A
such that A
is stored as a global strong reference (making it uncollectible). I opted to make the output of graded_algebra
be a noncached_method
as the UniqueRepresentation
of AssociatedGradedAlgebra
will make sure it's extremely rarely (re)created (and because I need the filtered algebra to do the computations, so it has to be part of the construction data). As this will likely be what gets created, we don't have to worry about this (and most parents will end up being UR's). If the user creates a nonUR parent for the assoc. gr., then they have to override graded_algebra
anyways and can make it a cached method.
Also, should I then explain in the doc that everybody who overshadows
graded_algebra
must also overshadowprojection
,to_graded_conversion
andfrom_graded_conversion
?
I don't think these methods would need to be overwritten as they are completely generic.
Great  as long as this magic doesn't force every algebra which happens to be filtered as a module to automatically be considered a filtered algebra.
I think that gets into the issue (and is related with John's comment) with what do for filtrations in general. I want to use degree
for the filtration parameter so we don't have to duplicate code, it's natural for graded modules/algebras, and which filtration component is not welldefined (most elements belong to multiple, possibly infinite, F_{i} components). Overall, we will need a framework for construction of general filtrations, but I don't think we can do that at the category level. What will probably be best (a quick thought) is to have a method filtration
which returns the filtration of the module/algebra as a Family
of submodules indexed by I
. However we will still need a method degree
to be computationally quick. This would allow filtrations different from the grading in a way and perhaps we could add a method to the graded categories such as filtration_degree
which by default returns the usual degree. Anyways, I think about more later.
comment:47 in reply to: ↑ 46 ; followup: ↓ 48 Changed 8 years ago by
Replying to tscrim:
Also, should I then explain in the doc that everybody who overshadows
graded_algebra
must also overshadowprojection
,to_graded_conversion
andfrom_graded_conversion
?I don't think these methods would need to be overwritten as they are completely generic.
What do you mean by this?
Anyway, should I continue the review or are you still working on the changes?
comment:48 in reply to: ↑ 47 Changed 8 years ago by
Replying to darij:
Replying to tscrim:
I don't think these methods would need to be overwritten as they are completely generic.
What do you mean by this?
I mean we only need the methods defined in the category, so it's generic in that sense (i.e. independent of implementation).
Anyway, should I continue the review or are you still working on the changes?
I'm done making changes; please continue.
comment:49 Changed 8 years ago by
 Commit changed from 096538121130679a55b971d3d3a5626e94b157a5 to 79894b4c5b248281fbba1b932171b18a59e5b137
comment:50 Changed 8 years ago by
 Commit changed from 79894b4c5b248281fbba1b932171b18a59e5b137 to 25c0fbc2e1c75e4d1a255ca41d4d6235b4571453
Branch pushed to git repo; I updated commit sha1. New commits:
25c0fbc  looked through clifford_algebra and filtered_algebras*; many TODOs left

comment:51 Changed 8 years ago by
 Commit changed from 25c0fbc2e1c75e4d1a255ca41d4d6235b4571453 to 2a62c3b093a2a991422f8c4f261d1a9d5ac6e059
Branch pushed to git repo; I updated commit sha1. New commits:
2a62c3b  lift_* methods in algebras/clifford_algebra.py should remember the gradedfiltered choice

comment:52 Changed 8 years ago by
 Commit changed from 2a62c3b093a2a991422f8c4f261d1a9d5ac6e059 to 15cf0dce22ece06760fdd270257f98757625f0a9
Branch pushed to git repo; I updated commit sha1. New commits:
15cf0dc  fix and a first doctest for induced_graded_map

comment:53 Changed 8 years ago by
 Commit changed from 15cf0dce22ece06760fdd270257f98757625f0a9 to 50299560bf500b649aa5bdc3e7c7690fa09e2fb1
Branch pushed to git repo; I updated commit sha1. New commits:
5029956  another pitfall documented

comment:54 Changed 8 years ago by
 Commit changed from 50299560bf500b649aa5bdc3e7c7690fa09e2fb1 to 292ef5f2a26bff5302a5d97ebf22d34240c78f72
Branch pushed to git repo; I updated commit sha1. New commits:
292ef5f  another doctest

comment:55 Changed 8 years ago by
Done for today. I'll add some more doctests tomorrow and hopefully get to read through the rest of the files, although I'd much prefer if you get rid of some of the TODOs beforehand. I'll then try to generalize graded_algebra
and AssociatedGraded
to filtered modules (not just filtered algebras); IMHO this is a highly natural step to do.
If the Clifford issues become too complicated, what do you think of splitting this patch into a general filtrations one and a Clifford one? I see nontrivial work ahead in both of them, so a split would speed up the merge of the general code.
comment:56 Changed 8 years ago by
 Commit changed from 292ef5f2a26bff5302a5d97ebf22d34240c78f72 to c2e84e1367cbfc47eb7104de654e2ee55caea95d
Branch pushed to git repo; I updated commit sha1. New commits:
c2e84e1  remaining doctests for induced_graded_map

comment:57 Changed 8 years ago by
 Commit changed from c2e84e1367cbfc47eb7104de654e2ee55caea95d to 03bd4cfb53e24b24c65aada21f08850b40fb5c5c
Branch pushed to git repo; I updated commit sha1. New commits:
03bd4cf  possibly controversial: graded_algebra and the three methods forming its interface are now cached_methods

comment:58 Changed 8 years ago by
Another issue with the CliffordWeyl part of this patch: The Clifford algebra is graded by default, whereas the Weyl algebra is graded by default. There is no reason why there should be different behavior here; the Weyl algebra is Z/2graded as much as the Clifford one is.
comment:59 Changed 8 years ago by
 Commit changed from 03bd4cfb53e24b24c65aada21f08850b40fb5c5c to 8a747c073e706950d1b14e77458539e126ff0550
Branch pushed to git repo; I updated commit sha1. New commits:
8a747c0  further edits

comment:60 Changed 8 years ago by
Enough for now (FPSAC deadline is approaching). I have now checked all of the nonClifford/Weyl? part of this patch, and here is all that I'd like to be done before the merge of this part:
 TODO: Formulate an interface and a contract for
FilteredModulesWithBasis
objects. Is aCombinatorialFreeModule
with adegree_on_basis
method enough? Or isbasis
still needed? (See theFIXME
insrc/sage/categories/examples/filtered_modules_with_basis.py
.)
 TODO: Make sense of
A.basis(d)
forA
a filtered module andd
an integer. This has always been broken and we can leave it for later, but it then needs a trac ticket.
 TODO: doctesting
A.basis(d)
forA
graded. Very easy once above is fixed.
 TODO: overriding the
to_graded_conversion
,from_graded_conversion
andprojection
methods on graded algebras for the sake of speed, or deciding not to. [EDIT: This would be difficult with the current design.]
 [DONE:] Generalizing
graded_algebra
to modules. This doesn't seem too difficult; I am in favor of keeping the name "associated graded *algebra*" even for modules, as it seems to have a ring to it that algebraists recognize, but maybe some discussion is in order.
On the Clifford/Weyl? front, I'll review it once you deal with the TODOs and the CliffordWeyl mismatch; the changes IMHO are nontrivial enough (and orthogonal to the categories themselves) to warrant an extra ticket. (I'll need to check through all the methods in the two files.)
comment:61 in reply to: ↑ 37 ; followup: ↓ 62 Changed 8 years ago by
Replying to tscrim:
@jhpalmieri I'll make those changes. However we can't get a descending filtration unless the grading set can be negated. As for algebras that are both filtered and graded, it's the same issue as when an algebra has 2 natural gradings (as we use
degree
for both filtration and grading). Although as things evolve and the filtration can be generalized from usingdegree
, this can be rectified. For now, you have to choose the "best" one fordegree
(or have it be an optional arg like how I'm doing for Clifford algebras).
I still don't understand this design choice. Why not separate filtrations and gradings? A graded object without additional filtration could still be considered to be filtered (by having the filtration method default to calling degree
), but this wouldn't have to be the only choice.
Replying to darij:
Generalizing graded_algebra to modules. This doesn't seem too difficult; I am in favor of keeping the name "associated graded *algebra*" even for modules, as it seems to have a ring to it that algebraists recognize, but maybe some discussion is in order.
"Have a ring to it". Heh.
I would object to calling a module an "algebra" if there is no multiplicative structure. "Associated graded module" is just fine, or "associated graded object" more generally.
comment:62 in reply to: ↑ 61 ; followup: ↓ 65 Changed 8 years ago by
Replying to jhpalmieri:
I still don't understand this design choice. Why not separate filtrations and gradings? A graded object without additional filtration could still be considered to be filtered (by having the filtration method default to calling
degree
), but this wouldn't have to be the only choice.
How do you suggest separating them?
(In a better language, there would be a way to handle this using some kind of aliases. Note that there are many modules and algebras in nature having multiple filtrations, so just creating a slot for a grading and a slot for filtrations doesn't seem like a scalable solution to me.)
@nbruin: I only really digested your post right now. So my changes do cause memleaks. OK, nothing easier than removing some @cached_method decorators. But... can you look at the code for induced_graded_map
and tell me how to avoid having it reconstruct the other.projection(i)
method every time I call its return value? (And while the ass. gr. algebra itself might be UniqueRepresentations?, things like the projection
map are not unless we hash them.)
comment:63 Changed 8 years ago by
When you initialize a filtered object, you could pass an argument saying how it is filtered:
FilteredObject(A, filtration=fcn)
where A
is an object and fcn
is a function which takes an element of A
as input and returns an element of the filtering monoid. (Change 'object' to 'algebra', 'module', 'group', 'ring', throughout if you'd rather.) So a simple example could be
FilteredObject(A, filtration=degree)
but you could also have
FilteredObject(A, filtration=smith_filtration) FilteredObject(A, filtration=lambda x: 2 + 3*x.jones_filtration()) FilteredObject(A, filtration=lambda x: 0 if x.is_zero() else Infinity) ...
One point is that, even if an object has many possible filtrations, when you consider it as a filtered object, you are at that point choosing a filtration. It's like the difference between a Module
and a ModuleWithBasis
. I guess I should have called this ObjectWithFiltration
instead? Anyway, it's not FilterableObject
, allowing for multiple possible filtrations, it's FilteredObject
.
If the filtration
keyword is missing, then perhaps first you see if the Element
class has a filtration
method, and if not, you see if it has a degree
method.
comment:64 followup: ↓ 67 Changed 8 years ago by
How is that any different for objects with multiple natural gradings? The point I'm trying to make is GradedAlgebra
is not an algebra that has some grading (all algebras have a trivial grading), but that they have a distinguished grading, just like (FiniteDimensional
)AlgebrasWithBasis
are algebras with a distinguished basis (can replace grading by filtered).
The main reason why I chose to use grading
is so we don't have to duplicate all of the code for graded algebras but just replacing degree
by smallest_filtered_component
(or whatever name you want to call it).
For the Clifford algebras, we don't yet have the category framework in place (I know how I want to do it, but I haven't done so yet). Perhaps it is a bad choice to give Clifford algebras that option right now for the future outlook. Also now that we have the filtered algebras, we don't need the graded algebras to get extra features.
This relates to John's suggestion, and that we probably need something at the class level, not the category level which is what this ticket is about, which set's the degree function. I want to stress that the category has a distinguished filtration/grading (perhaps I forgot to reflect this in the documentation).
I will take a more detailed look at all of the changes later tonight.
comment:65 in reply to: ↑ 62 Changed 8 years ago by
Replying to darij:
@nbruin: I only really digested your post right now. So my changes do cause memleaks. OK, nothing easier than removing some @cached_method decorators. But... can you look at the code for
induced_graded_map
and tell me how to avoid having it reconstruct theother.projection(i)
method every time I call its return value? (And while the ass. gr. algebra itself might be UniqueRepresentations?, things like theprojection
map are not unless we hash them.)
Yes, that's tricky. I didn't read the code in detail, but in general I would expect that with caching maps on objects that use each other as construction parameters, you do end up with the problematic reference cycles, rooted in a global cache reference.
If your projection can somehow be obtained as a coercion/conversion you may be able to lift on the effort that went in there (internally, those maps drop their reference to the domain now. Since they are normally cached on the codomain, that seems to usually be enough to break cycles).
I don't have a proof of the following, but conceptually it seems reasonable to me that you can choose one of the following approaches, but that mixing them will lead to memory leaks:
 either you express the relation between objects by using one as a UniqueRepresentation parameter for the other and you rely entirely on that relation to tie the objects together
 or you manage the link yourself, by caching stuff on the objects. In the latter case, you should *not* let any of the globally cached construction parameters refer to the objects involved. That will usually mean using UniqueFactory rather than UniqueRepresentation, so that you can process the keys a bit.
I suspect that what we need is that there is a partial ordering on our globally cached objects, where A<B
if A
can occur as part of a construction cache key for B
. Having both A<B
and B<A
would naturally lead to a reference cycle and hence a leak.
Furthermore, if A<B
and A holds a strong reference to B in any form then there's a leak too.
For instance QQ
can be a construction parameter of QQ[x]
because QQ
does not refer to QQ[x]
in any way (the fact that QQ
coerces into QQ[x]
is stored on QQ[x]
).
In the case here, where I think we have things like A=CommutativeAlgebra(QQ,['x','y','z'])
and B=GradedCommutativeAlgebra(QQ,['x','y','z'])
it is not clear if we should have A<B
or B<A
. So I think we should have neither (the constructions above definitely don't need it) and then you're free to cache on these things in either direction, provided you don't coerce (:)) the coercion framework into holding a reference cycle.
In hindsight I really think UniqueRepresentation is a mistaken design decision. We sort of need it for efficient coercion, though.
comment:66 followup: ↓ 68 Changed 8 years ago by
@nbruin: Thanks for the explanations. So it is what I feared. Someone please remove the @cached_methods; it appears there is no easy way to get rid of the performance issues.
Caching these maps relating A to gr(A) on gr(A) was my first idea (and I think Travis wanted to implement them as conversions), but it conflicts with Travis's design decision (which is a good one!) to allow overriding graded_algebra
with simpler stuff than the default AssociatedGraded
construction. Many different complicated algebras A will end up having the same simple gr(A) (for example, for every universal enveloping algebra A = U(g) of a Lie algebra g over a field, we have gr(A) \cong S(g)), and gr(A) is not supposed to "know" anything about A. Overriding _element_constructor
of gr(A) would be messy and unscalable.
comment:67 in reply to: ↑ 64 ; followup: ↓ 69 Changed 8 years ago by
Replying to tscrim:
How is that any different for objects with multiple natural gradings?
It's the same issue.
The main reason why I chose to use
grading
is so we don't have to duplicate all of the code for graded algebras but just replacingdegree
bysmallest_filtered_component
(or whatever name you want to call it).
My main concern is that I want to be able to have a graded algebra with an additional filtration on it (ideally so that the associated graded algebra is bigraded). I think you said (or someone said) that this could be done with some reworking of the code in this branch. If that's accurate, then it seems like it would be better to have more flexible code that could handle this right from the start, instead of implementing it one way and then rewriting it later on.
comment:68 in reply to: ↑ 66 ; followup: ↓ 70 Changed 8 years ago by
Replying to darij:
Caching these maps relating A to gr(A) on gr(A) was my first idea (and I think Travis wanted to implement them as conversions), but it conflicts with Travis's design decision (which is a good one!) to allow overriding
graded_algebra
with simpler stuff than the defaultAssociatedGraded
construction. Many different complicated algebras A will end up having the same simple gr(A) (for example, for every universal enveloping algebra A = U(g) of a Lie algebra g over a field, we have gr(A) \cong S(g)), and gr(A) is not supposed to "know" anything about A. Overriding_element_constructor
of gr(A) would be messy and unscalable.
That suggests that gr(A) should be the simpler object. I'm not sure you want to go as far as having gr(A)<A
, but it does strongly suggest you don't want A<gr(A)
. You're saying yourself that gr(A) is not supposed to "know" about A. That implies that A
is not a construction parameter for gr(A). Instead, gr(A) should be constructed from basic parameters that can be retrieved from A
. Mind you, that doesn't preclude the existence of an interface function GradedAlgebra(A)
, but instead of being a UniqueRepresentation
class constructor, it would be a factory function that creates the relevant object from the relevant parameters from A.
Whether the coercion from A to gr(A) should then be managed by an "embedding" (that's coercion stored on A) is a different question. There is a good potential for creating memory leaks via those too.
comment:69 in reply to: ↑ 67 Changed 8 years ago by
Replying to jhpalmieri:
It's the same issue.
Okay, we're on the same page. I think the solution is the same.
My main concern is that I want to be able to have a graded algebra with an additional filtration on it (ideally so that the associated graded algebra is bigraded). I think you said (or someone said) that this could be done with some reworking of the code in this branch. If that's accurate, then it seems like it would be better to have more flexible code that could handle this right from the start, instead of implementing it one way and then rewriting it later on.
I spoke offhand that there might be a good way to do this as the code evolved. With some more thought, I think if you have degree
return (f, g)
where f
is the filtration and g
the grading, then it should handle things properly in the same was if you were trying to construct a bigraded algebra.
comment:70 in reply to: ↑ 68 Changed 8 years ago by
Replying to nbruin:
Replying to darij:
Caching these maps relating A to gr(A) on gr(A) was my first idea (and I think Travis wanted to implement them as conversions), but it conflicts with Travis's design decision (which is a good one!) to allow overriding
graded_algebra
with simpler stuff than the defaultAssociatedGraded
construction. Many different complicated algebras A will end up having the same simple gr(A) (for example, for every universal enveloping algebra A = U(g) of a Lie algebra g over a field, we have gr(A) \cong S(g)), and gr(A) is not supposed to "know" anything about A. Overriding_element_constructor
of gr(A) would be messy and unscalable.That suggests that gr(A) should be the simpler object. I'm not sure you want to go as far as having
gr(A)<A
, but it does strongly suggest you don't wantA<gr(A)
. You're saying yourself that gr(A) is not supposed to "know" about A. That implies thatA
is not a construction parameter for gr(A). Instead, gr(A) should be constructed from basic parameters that can be retrieved fromA
. Mind you, that doesn't preclude the existence of an interface functionGradedAlgebra(A)
, but instead of being aUniqueRepresentation
class constructor, it would be a factory function that creates the relevant object from the relevant parameters from A.Whether the coercion from A to gr(A) should then be managed by an "embedding" (that's coercion stored on A) is a different question. There is a good potential for creating memory leaks via those too.
It's not true that gr(A)
is (suppose to be) independent of A
. The multiplication of gr(A)
is defined from the multiplication in A
(plus the imposed filtration). However, that's not to say we can't construct the associated graded algebra without appealing to A
, but we're essentially just using specialize code. From that, I strongly believe we want A < gr(A)
, to the point that I'd want to implement gr
as a Functor
instance in a followup (at least, I'm pretty sure it is a functor).
comment:71 Changed 8 years ago by
You can't have A < gr(A)
as long as you choose to identify (say) the ass. gr. of a Clifford algebra with an exterior algebra, and the ass. gr. of a graded algebra with itself.
comment:72 Changed 8 years ago by
Why not? There's nothing wrong with that. Technically we're saying there's no relation, but it's okay to remove relations from this poset.
comment:73 Changed 8 years ago by
When A
is graded, how do you want A < A
?
comment:74 Changed 8 years ago by
A
is constructed from independent data and graded_algebra
in that case does not construct any new objects. So there would be no A < A
.
comment:75 Changed 8 years ago by
What do you mean by "A
is constructed from independent data"? What if A
is UniqueRep? and constructs itself? (Skype?)
comment:76 Changed 7 years ago by
 Commit changed from 8a747c073e706950d1b14e77458539e126ff0550 to 752df7798b2ae6b9afc60528227b4e88c745fae9
Branch pushed to git repo; I updated commit sha1. New commits:
831c269  Merge branch 'public/categories/filtered_algebras17096' of git://trac.sagemath.org/sage into filt

752df77  Revert the cached_method decorators from commit "possibly controversial: graded_algebra and the three methods forming its interface are now cached_methods"

comment:77 in reply to: ↑ 33 Changed 7 years ago by
 Work issues set to comment:60 todo list
About why I think FilteredModulesWithBasis
needs a contract:
Here are the methods on F
that are used in the implementations of the methods of FilteredModulesWithBasis
when F
is cast as a FilteredModulesWithBasis
:
ParentMethods: degree_on_basis sum_of_terms monomial _indices ElementMethods: support leading_support is_homogeneous is_zero
I hear the quacking of a CombinatorialFreeModule
duck here (except for degree_on_basis
which should be explicitly required). Are there any more general categories which offer these methods?
comment:78 Changed 7 years ago by
 Commit changed from 752df7798b2ae6b9afc60528227b4e88c745fae9 to dfaaaeb6d9652e071ea89c9854da984bc8ada319
Branch pushed to git repo; I updated commit sha1. New commits:
dfaaaeb  associatedgraded now also defined for filtered *modules*, although still named 'graded algebra' in this case

comment:79 Changed 7 years ago by
On the subject of associated graded objects of filtered *modules*, they are now implemented (see the doctests for why they are a useful notion  it is really the induced_graded_map
that makes them useful). But naming them graded_algebra
is questionable, and I understand jhpalmieri's objections to it. What about renaming graded_algebra
as associated_graded
(for both modules and algebras)? Nicolas just suggested this and I like the idea.
(We algebraists don't have a good name for this notion. "Associated graded" is too long and an adjective that makes the listener search in vain for a noun. "gr" is too short and hard to pronounce.)
comment:80 Changed 7 years ago by
@Travis: here is the main thing I want you to address before I review the Clifford & Weyl stuff in this ticket:
Another issue with the CliffordWeyl part of this patch: The Clifford algebra is graded by default, whereas the Weyl algebra is graded [oops: I meant filtered here] by default. There is no reason why there should be different behavior here; the Weyl algebra is Z/2graded as much as the Clifford one is.
comment:81 Changed 7 years ago by
 Dependencies set to #18044
As Darij and I discussed today, we should make Weyl and Clifford algebras super filtered algebras, so we need #18044.
comment:82 Changed 7 years ago by
 Commit changed from dfaaaeb6d9652e071ea89c9854da984bc8ada319 to 14e19ba97f1bb096c7614241c9b09c1d0f699a19
Branch pushed to git repo; I updated commit sha1. New commits:
cd6d21a  Created super categories for algebras and modules.

3d33730  Merge branch 'develop' into public/categories/super_categories18044

43a976a  Merge branch 'public/categories/filtered_algebras17096' of trac.sagemath.org:sage into public/categories/filtered_algebras17096

d1d135f  Give Weyl/Clifford/Exterior super powers.

14e19ba  Fixing doctests and updating documentation.

comment:83 Changed 7 years ago by
 Commit changed from 14e19ba97f1bb096c7614241c9b09c1d0f699a19 to 9bc28fd5fdbcb5463703739a9077886a113596a5
Branch pushed to git repo; I updated commit sha1. New commits:
9bc28fd  Changing abstract methods and doc based off talking with Nicolas.

comment:84 Changed 7 years ago by
 Cc days64 added
 Milestone changed from sage6.4 to sage6.6
 Work issues comment:60 todo list deleted
I talk a bit about this ticket with Nicolas tonight, and we decided to not make support
an abstract method right now, but instead leave a message in the category about this. We will fix support
along with many other issues with an object in ModulesWithBasis
being too close to a CombinatorialFreeModule
in the followup #18066. I think with this we've handled everything from comment:60.
comment:85 Changed 7 years ago by
 Commit changed from 9bc28fd5fdbcb5463703739a9077886a113596a5 to 1404ad0e2336eee05877e3e1a434809d437a998d
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
1604162  18174: small doc improvements

710d09e  18174: more doc improvements + uniformization with CategoryWithAxiom

0ce1cad  Changing the wording of the Super method.

b29650b  Made it so you must explicitly designate graded as a super category

f3bdf9b  Merge branch 'public/categories/super_categories18044' of trac.sagemath.org:sage into public/categories/super_categories18044

19c3471  Cleanup from adding #18044.

7554dbd  1 step forward, 2 steps back.

caada13  Going all the way to the finish line like a superstar.

d56ef84  Merge branch 'public/categories/super_categories18044' into public/categories/filtered_algebras17096

1404ad0  Cleanup from merged code.

comment:86 Changed 7 years ago by
 Cc sd67 added
comment:87 Changed 7 years ago by
 Commit changed from 1404ad0e2336eee05877e3e1a434809d437a998d to f219ce3a60512bac0da8c8b05042c4ee02eacf07
comment:88 Changed 7 years ago by
 Commit changed from f219ce3a60512bac0da8c8b05042c4ee02eacf07 to ebc2a65c5d377cc1e7872201709fabcec3e9e4c6
comment:89 Changed 7 years ago by
see also #15328
comment:90 Changed 7 years ago by
Patchbot is not yet happy (but for very stupid reasons).
comment:91 Changed 7 years ago by
 Commit changed from ebc2a65c5d377cc1e7872201709fabcec3e9e4c6 to 4b2046fdfb0545b3b0908f8c3de609becd78bc5f
Branch pushed to git repo; I updated commit sha1. New commits:
9cf5607  Merge branch 'public/categories/filtered_algebras17096' of trac.sagemath.org:sage into public/categories/filtered_algebras17096

26859cb  manual merge with sage 6.7.beta1

6051865  add a doctest which hopefully works (hard to check while compiling)

570bc49  Merge branch 'public/categories/super_categories18044' into 6.9.b1

b91cd82  trac #18044 correct one typo in the doc

7fd1df2  Merge branch 'public/categories/super_categories18044' of trac.sagemath.org:sage into public/categories/super_categories18044

0579337  Some reviewer tweaks and doc additions.

aec22cc  Added one more test.

4b2046f  Merge branch 'public/categories/super_categories18044' into public/categories/filtered_algebras17096

comment:92 Changed 7 years ago by
 Commit changed from 4b2046fdfb0545b3b0908f8c3de609becd78bc5f to 3f67b6b0d0e10c2f4816acc791f6dc2a016eeb8d
Branch pushed to git repo; I updated commit sha1. New commits:
3f67b6b  Fixing trivial doctest due to changes in category heirarchy.

comment:93 Changed 7 years ago by
 Commit changed from 3f67b6b0d0e10c2f4816acc791f6dc2a016eeb8d to fa476ddac910418cb12790af8896154ddca8fd00
Branch pushed to git repo; I updated commit sha1. New commits:
fa476dd  Fixing doublecolon in INPUT block.

comment:94 Changed 7 years ago by
 Milestone changed from sage6.6 to sage6.10
comment:95 Changed 7 years ago by
 Reviewers set to Darij Grinberg
comment:96 Changed 7 years ago by
 Commit changed from fa476ddac910418cb12790af8896154ddca8fd00 to 589b501685ef7e4d07b159d56b1049a1d1e67759
Branch pushed to git repo; I updated commit sha1. New commits:
589b501  Reviewer changes with Darij.

comment:97 Changed 7 years ago by
 Commit changed from 589b501685ef7e4d07b159d56b1049a1d1e67759 to 6cc8b8460dfe5a05380e73e667dc7294e4369774
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
6cc8b84  Reviewer changes with Darij.

comment:98 Changed 7 years ago by
 Status changed from needs_review to positive_review
After a harrowing hour of discussing the category framework, I found myself agreeing with this ticket. Thanks Travis for the changes!
comment:99 Changed 7 years ago by
 Branch changed from public/categories/filtered_algebras17096 to 6cc8b8460dfe5a05380e73e667dc7294e4369774
 Resolution set to fixed
 Status changed from positive_review to closed
Some design decisions:
graded_*
category hasfiltered_*
as an immediate super category. In particular, this is needed forGradedAlgebrasWithBasis
not picking upFilteredAlgebrasWithBasis
in its super categories otherwise.Needs review.
New commits:
Implemented filtered modules/algebras and associated graded algebras.