Implement categories for filtered algebras

[tscrim]

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]

Author: Travis Scrimshaw

[tscrim]

Branch: public/categoires/filtered_algebras-17096

[tscrim]

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]

Commit: ad184ef

[nthiery]

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]

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]

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

[tscrim]

Changed commit from ad184ef to bb234ec

[darijgr]

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]

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]

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]

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]

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.

[sagetrac-git]

Changed commit from bb234ec to 5f63379

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from 5f63379 to 2aec8bd

[sagetrac-git]

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

2aec8bd

Fixing some typos.

[tscrim]

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]

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]

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.

[sagetrac-git]

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.

[sagetrac-git]

Changed commit from 2aec8bd to 592ba11

[sagetrac-git]

Changed commit from 592ba11 to 60beb17

[sagetrac-git]

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

60beb17

More explicit documentation.

[sagetrac-git]

Changed commit from 1404ad0 to f219ce3

[sagetrac-git]

Changed commit from f219ce3 to ebc2a65

[sagetrac-git]

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

e9bcfda	Merge branch 'public/categories/filtered_algebras-17096' into 6.7.rc0
ebc2a65	trac #17096 fixing two doctests

[fchapoton]

comment:89

see also #15328

[videlec]

comment:90

Patchbot is not yet happy (but for very stupid reasons).

[sagetrac-git]

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

9cf5607	Merge branch 'public/categories/filtered_algebras-17096' of trac.sagemath.org:sage into public/categories/filtered_algebras-17096
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_categories-18044' into 6.9.b1
b91cd82	trac #18044 correct one typo in the doc
7fd1df2	Merge branch 'public/categories/super_categories-18044' of trac.sagemath.org:sage into public/categories/super_categories-18044
0579337	Some reviewer tweaks and doc additions.
aec22cc	Added one more test.
4b2046f	Merge branch 'public/categories/super_categories-18044' into public/categories/filtered_algebras-17096

[sagetrac-git]

Changed commit from ebc2a65 to 4b2046f

[sagetrac-git]

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

3f67b6b

Fixing trivial doctest due to changes in category heirarchy.

[sagetrac-git]

Changed commit from 4b2046f to 3f67b6b

[sagetrac-git]

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

fa476dd

Fixing double-colon in INPUT block.

[sagetrac-git]

Changed commit from 3f67b6b to fa476dd

[darijgr]

Reviewer: Darij Grinberg

[sagetrac-git]

Changed commit from fa476dd to 589b501

[sagetrac-git]

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

589b501

Reviewer changes with Darij.

[sagetrac-git]

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

6cc8b84

Reviewer changes with Darij.

[sagetrac-git]

Changed commit from 589b501 to 6cc8b84

[darijgr]

comment:98

After a harrowing hour of discussing the category framework, I found myself agreeing with this ticket. Thanks Travis for the changes!

[vbraun]

Changed branch from public/categories/filtered_algebras-17096 to 6cc8b84