Implement categories for filtered algebras

tscrim commented 9 years ago

There are some upcoming algebras in Sage (Clifford algebras in #15300, Yangians in #15484, and orthogonal/symplectic basis for Sym #15536; likely others) that would benefit from having a category with common methods.

Depends on #18044

CC: @nthiery @darijgr days64 sd67

Component: categories

Keywords: filtered algebras

Author: Travis Scrimshaw

Branch/Commit: 6cc8b84

Reviewer: Darij Grinberg

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

tscrim commented 9 years ago

Author: Travis Scrimshaw

tscrim commented 9 years ago

Branch: public/categoires/filtered_algebras-17096

tscrim commented 9 years ago

comment:1

Some design decisions:

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.
Every graded_* category has filtered_* as an immediate super category. In particular, this is needed for GradedAlgebrasWithBasis not picking up FilteredAlgebrasWithBasis in its super categories otherwise.
Homogeneous elements for filtered algebras are elements in F_i not in F_i-1. I don't know if this is a standard definition, but it allowed extensions of methods from graded to filtered.

Needs review.

New commits:

ad184ef Implemented filtered modules/algebras and associated graded algebras.

tscrim commented 9 years ago

Commit: ad184ef

nthiery commented 9 years ago

comment:2

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 has filtered_* as an immediate super category. In particular, this is needed for GradedAlgebrasWithBasis not picking up FilteredAlgebrasWithBasis 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_i-1. 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

tscrim commented 9 years ago

comment:3

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.

http://en.wikipedia.org/wiki/Filtration_%28mathematics%29

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.

tscrim commented 9 years ago

Changed branch from public/categoires/filtered_algebras-17096 to public/categories/filtered_algebras-17096

tscrim commented 9 years ago

Changed commit from ad184ef to bb234ec

darijgr commented 9 years ago

comment:4

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 (n-1)-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 ill-behaved.

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?

tscrim commented 9 years ago

comment:5

Replying to @darijgr:

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 (n-1)-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 ill-behaved.

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 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?

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

darijgr commented 9 years ago

comment:6

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.

tscrim commented 9 years ago

comment:7

Replying to @darijgr:

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_d-1. 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 non-standard 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.

darijgr commented 9 years ago

comment:8

Replying to @tscrim:

Replying to @darijgr:

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?

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 degree i.

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from bb234ec to 5f63379

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`2ff607a`	`Merge branch 'develop' into public/categories/filtered_algebras-17096`
`5f63379`	`Addressing Darij's comments.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 5f63379 to 2aec8bd

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

2aec8bd Fixing some typos.

tscrim commented 9 years ago

comment:11

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_{i-1} (since I require each F_i to be a module. Perhaps I'm missing something subtle (and I can't really think in coordinate-free terms very well).

darijgr commented 9 years ago

comment:12

I think your doc is inconsistent. This can't be:

+We require all `F_i \setminus F_{i-1}` 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_{i-1} \oplus G_i where G_i is the submodule spanned by the degree i-basis elements.

tscrim commented 9 years ago

comment:13

For filtered algebras, we (only) have F₀ <= F₁ <= ..., so for graded modules, we'd have G_i = F_i - F_i-1 because we want that construction of F_i = F_i-1 (+) G_i (starting with F₀ = G₀). Actually, there is something that is wrong; the setminus isn't correct because it removes 0. It should be a quotient F_i / F_i-1, but other than that, it's consistent.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`598f3c8`	`Merge branch 'develop' into public/categories/filtered_algebras-17096`
`592ba11`	`Some minor doc tweaks.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 2aec8bd to 592ba11

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 592ba11 to 60beb17

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

60beb17 More explicit documentation.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`d75c90c`	`Merge branch 'public/categories/filtered_algebras-17096' of git://trac.sagemath.org/sage into filter`
`9d567ea`	`clarifying doc, or maybe obscuring it -- needs to be proofread`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 60beb17 to 9d567ea

darijgr commented 9 years ago

comment:17

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 one-stop 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 method-level and maybe even in the class-level 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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 9d567ea to a11c501

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`403b6ad`	`Merge branch 'develop' into public/categories/filtered_algebras-17096`
`198537c`	`Merge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/filtered_algebras-17096`
`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.`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from a11c501 to 8e586e2

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

8e586e2 Merge branch 'develop' into public/categories/filtered_algebras-17096

tscrim commented 9 years ago

comment:20

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.

darijgr commented 9 years ago

comment:21

Can you go skype-on?

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

45aca1b Changed some doc from conversation with Darij.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 8e586e2 to 45aca1b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

fe0e481 fixes to associated_graded.py

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 45aca1b to fe0e481

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

b2bc6f5 self.base_one removed

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from fe0e481 to b2bc6f5

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

b32aaf2 further review changes

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from b2bc6f5 to b32aaf2

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

68b47a8 Better return of algebra_generators for filtered alg w/ basis example.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from b32aaf2 to 68b47a8

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from 68b47a8 to c3b2950

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

c3b2950 enough for today

darijgr commented 9 years ago

comment:28

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

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

`2d29296`	`Added option to consider the clifford algebra as filtered or graded.`
`b29f67e`	`Merge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/filtered_algebras-17096`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 9 years ago

Changed commit from c3b2950 to b29f67e

darijgr commented 9 years ago

comment:30

[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?

tscrim commented 9 years ago

comment:31

Replying to @darijgr:

[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?

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

sagemath / sage

Implement categories for filtered algebras #17096