Categories over a base ring category

[nthiery]

Currently, to construct a category of algebras, we need to specify the
base ring:

    sage: Algebras(QQ)

A side effect is that the construction of e.g. GF(p)['x'] for a
lot of p's in number theoretic calculations triggers the
construction of many parallel hierarchies of categories.

This is a waste because in most situations only the category of the
base ring is relevant. In particular, the generic code provided to
parents/elements/... only depends on the latter.

The purpose of this ticket is to allow for only specifying the
category of the base ring, as in:

    sage: Algebras(Fields())

with

    sage: Algebras(QQ)

constructing a subcategory of the former. Then go trough the code,
decide in each case whether we want to use Algebras(QQ) or
Algebras(Fields()), and update the doctests accordingly. In most
case, the latter idiom will be preferable, unless we need some
operation on the category itself.

This would fix the regression noted on #15792 and made worse by
#10963.

Further features for this ticket or follow-up tickets would be to:

• make Modules(...) into a covariant functorial
  constructions. This would give a proper framework for the feature
  Modules(QQ) -> VectorSpaces(QQ) instead of having to
  tackle it with a special hack.

• implement a PolynomialRings(...) covariant functorial
  construction.

Depends on #10963
Depends on #16275

CC: @sagetrac-sage-combinat @vbraun @simon-king-jena @darijgr

Component: categories

Author: Nicolas M. Thiéry

Branch/Commit: 15658bd

Reviewer: Travis Scrimshaw

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

[simon-king-jena]

comment:1

As commented on #10963, I see some questions to be addressed.

If I understand correctly, we sometimes do want to specify the base ring/field, and Volker says that this should be by a "mixin" category (lets call it FixedBaseRing(...)) that simply is joined with the non-specific category, say, Algebras(Fields()).

First complication: We not only have base rings, but (for bimodules) left and right base rings. Should this be reflected in the "FixedBaseBla" categories as well?

And another complication: We want to have categories expressing the fact that a field (not just a ring) is acting on the objects, and then want to compute the join. Is there an easy programmatic way to let an error be raised when someone tries to compute the join "Algebras(Fields()) & FixedBaseRing(ZZ)"?

[nthiery]

comment:2

Replying to @simon-king-jena:

So, the strategy would be this: The current "Category over base ring" should accept as input no a ring, but a subcategory of the category of rings.

Or more precisely, it would accept both kinds of input.

A polynomial ring should be initialised in the category of "commutative algebras over Category of quotient fields" (say), and should of course have its own reference to the base ring (say, the rational field).

Yup. And later in the category of "polynomial rings over a quotient field."

Since the parent and element classes only depend on the category of the base ring (by the current implementation), a category refinement would probably not be needed.

Yes.

But if needed, it would amount to take the join with the category "FixedBaseField(QQ), perhaps with super-categories "FixedBaseRing(QQ)".

Yes, though I would write it as taking the join with Algebras(QQ).

Additional technical problem: We not only have base rings, but (for bimodules) left and right base rings. Should this be reflected in the "FixedBaseBla" categories as well?

We will want to accept both:

    Bimodules(Fields(), Fields())

and

    Bimodules(QQ, QQ)

In a first step, I would not bother about mixed calls likes Bimodules(QQ, Fields)/

And another complication: We want to have categories expressing the fact that a field (not just a ring) is acting on the objects, and then want to compute the join. Is there an easy programmatic way to let an error be raised when someone tries to compute the join "Algebras(Fields()) & FixedBaseRing(ZZ)"?

I don't see a trivial way to do it at this point. It certainly would
be a nice feature to bark upon such constructions, but not having it
is not really worst than the current situation where we have:

sage: Algebras(QQ) & Algebras(GF(3))
Join of Category of algebras over Finite Field of size 3 and Category of algebras over Rational Field

So this issue should not prevent us to proceed even if we don't find a good way out.

[simon-king-jena]

comment:3

OK, that's the other possibility: Rather than having a separate mix-in category FixedBaseRing(...), we would allow both Algebras(Fields()) and Algebras(QQ).

I have already done some experiments in that direction. We certainly want Algebras(R.category()) among the super-categories of Algebras(R). But if C is a category, do we want that Algebras(D) is among the super-categories of Algebras(C), for all D in C.super_categories()?

When I tried it yesterday, Nicolas' bounded C3 algorithm barked at me. Reason (if I recall correctly, I can't use my laptop right now): We want that Algebras(QQ) and Algebras(QQ.category() have the same parent and element classes, hence, _make_named_class_key returns the same, and thus they also share the cmp-key used in the C3 algorithm. But the C3 algorithm expects that the items on the given lists (here: the list of all super categories) have distinct keys.

One possible approach to solve that problem: The strict super-categories of a category with fixed base ring should all be categories with unspecified base rings. Hence, Algebras(R) should not have the super-categories Rings() and Modules(R), but Algebras(R.category()).

[nthiery]

comment:4

Replying to @simon-king-jena:

OK, that's the other possibility: Rather than having a separate mix-in category FixedBaseRing(...), we would allow both Algebras(Fields()) and Algebras(QQ).

I have already done some experiments in that direction. We certainly want Algebras(R.category()) among the super-categories of Algebras(R). But if C is a category, do we want that Algebras(D) is among the super-categories of Algebras(C), for all D in C.super_categories()?

When I tried it yesterday, Nicolas' bounded C3 algorithm barked at me. Reason (if I recall correctly, I can't use my laptop right now): We want that Algebras(QQ) and Algebras(QQ.category() have the same parent and element classes, hence, _make_named_class_key returns the same, and thus they also share the cmp-key used in the C3 algorithm. But the C3 algorithm expects that the items on the given lists (here: the list of all super categories) have distinct keys.

One possible approach to solve that problem: The strict super-categories of a category with fixed base ring should all be categories with unspecified base rings. Hence, Algebras(R) should not have the super-categories Rings() and Modules(R), but Algebras(R.category()).

This sounds reasonable. A variant would be, for a category over base
ring C, to set C(R).parent_class explicitly to
C(R.category()).parent_class, bypassing the
_make_named_class_key business since it won't really be needed
anymore anyway (and similarly for the element class and so on).

I'd say that we certainly want Algebras(R) to be a subcategory
of Modules(R), as tested by is_subcategory. But we could
imagine doing like for joins, and not put Modules(R) in
Algebras(R).<all_>super_categories().

In fact, maybe Algebras(R) should really be a join category:
that of Algebras(Fields()) & Modules(R).

Here Modules(R) would play a role similar to the category
with axiom C().A() associated to the category C defining
the axiom A. We would not have the option to define the analogue
of a category with axioms for a subcategory, but at this point I
don't foresee a use for it either.

Cheers,
Nicolas

[simon-king-jena]

Dependencies: 10963

[simon-king-jena]

comment:5

We want to build on top of #10963, right?

Replying to @nthiery:

One possible approach to solve that problem: The strict super-categories of a category with fixed base ring should all be categories with unspecified base rings. Hence, Algebras(R) should not have the super-categories Rings() and Modules(R), but Algebras(R.category()).

This sounds reasonable. A variant would be, for a category over base
ring C, to set C(R).parent_class explicitly to
C(R.category()).parent_class, bypassing the
_make_named_class_key business since it won't really be needed
anymore anyway (and similarly for the element class and so on).

I think _make_named_class_key would still be make sense: We need to distinguish the element and parent classes of Algebras(Fields()) from Algebras(Rings()), but probably not from Algebras(QuotientFields()). And in particular (when following your suggestion below) we would still want that Modules(GF(5)) and Modules(GF(7)) have the same parent and element classes.

I'd say that we certainly want Algebras(R) to be a subcategory
of Modules(R), as tested by is_subcategory. But we could
imagine doing like for joins, and not put Modules(R) in
Algebras(R).<all_>super_categories().

Yes, but then one needs a category FixedBase(R) to be joined with! And I think that's not so nice, as pointed out in comment:1. Or so I thought. But:

In fact, maybe Algebras(R) should really be a join category:
that of Algebras(Fields()) & Modules(R).

Hmmm. Yes, in that case one wouldn't need an ugly FixedBase(R) category...

Here Modules(R) would play a role similar to the category
with axiom C().A() associated to the category C defining
the axiom A. We would not have the option to define the analogue
of a category with axioms for a subcategory, but at this point I
don't foresee a use for it either.

Well, that's what I commented on at #10963: I was playing with the idea of an axiom WithFixedBase, accepting an argument, but Volker has cut the argument short ;-).

[simon-king-jena]

Changed dependencies from 10963 to #10963

[nthiery]

comment:7

Replying to @simon-king-jena:

We want to build on top of #10963, right?

Definitely.

Replying to @nthiery:
I think _make_named_class_key would still be make sense: We need to distinguish the element and parent classes of Algebras(Fields()) from Algebras(Rings()), but probably not from Algebras(QuotientFields()).

That would be for free if we make Algebras a functorial construction:
if a category, say QuotientFields(), says nothing about algebras
over itself, then Algebras(QuotientFields()) will actually
return Algebras(Fields()).

And in particular (when following your suggestion below) we would still want that Modules(GF(5)) and Modules(GF(7)) have the same parent and element classes.

Right, if we go the join way, we will need to handle the base case of
Modules and have a make_named_class_key mechanism there.

[nbruin]

comment:8

Just a little note. In [#10963 comment:261] it was noted that base categories are referenced strongly by a global cache, and hence are prone to cause "memory leaks". This was rebutted there by noting that the number of categories created is uniformly bounded, so the memory use is manageable. This is clearly not true for these parametrized "categories with fixed base".

The work on this ticket will improve the situation, because categories parametrized by elements from an infinite set will be less often created, but it's worthwhile to try and think of what to do if they do get created. Perhaps we should really try and avoid them completely? Certainly the infrastructure requirements to support them is radically different, because such parametrized categories need to be deallocatable (I'm impressed that Firefox's spell checker accepts that word and not Firefox).

[nbruin]

comment:9

A simple test that detects some of the problems #10963 presently causes:

while True: k=random_matrix(Rationals(),30,20).echelon_form()

On 6.2beta4 this happily runs with constant memory footprint and about constant time per iteration.

With #10963 applied, it gradually eats memory. The reason is that "integers mod p" and their categories pile up in memory. The iterations also take about twice as long and they slow down over time (as one would expect with memory use increasing).

(see #13925 for why the choice of algorithm might not be so sensible, but it's a useful test for our purposes here)

[nthiery]

comment:10

Hi!

I started to work on this. We can now do:

    sage: Algebras(Fields())
    Category of algebras over Category of fields

(TODO: would be nicer as Category of algebras over fields)

and by default, polynomial rings are created in such categories:

    sage: QQ['x'].category()
    Join of Category of euclidean domains and Category of commutative algebras over Category of quotient fields

All tests pass in the sage/rings/polynomial.

Here are the new timing for Simon's benchmark about creating lots of
polynomial rings:

With Sage 5.0.1:

sage: %time test()
CPU times: user 7.38 s, sys: 0.08 s, total: 7.46 s
Wall time: 7.48 s

With develop (6.2.beta7):

sage: %time test()
CPU times: user 9.31 s, sys: 125 ms, total: 9.44 s
Wall time: 9.47 s

With #10963:

sage: %time test()
CPU times: user 17.6 s, sys: 288 ms, total: 17.9 s
Wall time: 17.8 s

With #10963 and this ticket:

sage: def test():
....:     for p in prime_range(10000):
....:         P = GF(p)['t','x','z']
sage: %time test()
CPU times: user 2.99 s, sys: 127 ms, total: 3.11 s
Wall time: 3.03 s

Sounds like the time-performance issue for polynomials is indeed fixed for polynomials :-)

Now, on to matrices!

[nthiery]

Branch: refs/heads/public/categories/over-a-base-ring-category-15801

[nthiery]

Changed branch from refs/heads/public/categories/over-a-base-ring-category-15801 to public/categories/over-a-base-ring-category-15801

[nthiery]

comment:13

Replying to @nbruin:

A simple test that detects some of the problems #10963 presently causes:

while True: k=random_matrix(Rationals(),30,20).echelon_form()

On 6.2beta4 this happily runs with constant memory footprint and about constant time per iteration.

With #10963 applied, it gradually eats memory. The reason is that "integers mod p" and their categories pile up in memory. The iterations also take about twice as long and they slow down over time (as one would expect with memory use increasing).

(see #13925 for why the choice of algorithm might not be so sensible, but it's a useful test for our purposes here)

For the record: I just checked, and with the current version of this
ticket on top of #10963, this runs with constant memory footprint and
about constant time per iteration.

Cheers,
Nicolas

---

Last 10 new commits:

1b93d6e	Merge branch 'public/ticket/10963-doc-distributive' of trac.sagemath.org:sage into public/ticket/10963-doc-distributive
28b39a2	Merge branch 'develop' into public/ticket/10963-doc-distributive
70972db	Merge branch 'develop' into public/ticket/10963-doc-distributive
e1110da	Trac 10963: added little note in Category._super_categories
ad718de	Trac 10963: added mathematical definitions to the documentation of a bunch of axioms
d24a3d5	Trac 15801: enable categories over a base ring category and use them in polynomials
6bf3893	Trac 15801: improved repr for categories over base ring categories and fixed doctest
7db4ef0	Trac 10963: Fixed repr for the symmetric group algebra by improving a bit the generic repr methods in the categories
1116ef5	Merge branch 'categories/axioms-10963' into categories/over_a_base_category-15801
3a63847	Trac 15801: updated doctest

[nthiery]

Commit: 3a63847

[nthiery]

comment:14

Replying to nbruin:

There are some performance and leaking issues with the proposed code here. They
have been mentioned before, but they got swamped in more theoretical design
discussions. Consider for instance with sage 6.2.beta4:

...

As you can see, much slower execution and much leakier behaviour (even without
the patch this kind of stuff is very liable to leak but as you can see, this
patch makes it much worse). Note that we have to sort types by their string
representation, because for each of these ..._with_category types, the 5000 instances are in fact unique types with identical print names. So the memory load is even higher (types are fairly heavy data structures). As you can see, categories are eternal (they get cached) and since they store a reference to their base, they nail the base ring in memory too. We'll have to merge this ticket together with a ticket that moves base ring references out of the categories, since the constructions introduced in this ticket make the problem urgent.

For the record, here is what I currently get on my machine:

With this ticket applied on top of #10963:

sage: import gc
sage: from collections import Counter
sage: before={id(c) for c in gc.get_objects()}
sage: %time for n in [1..5000]: x=(matrix(Integers(n),2,2,1))
CPU times: user 3.83 s, sys: 41.2 ms, total: 3.87 s
Wall time: 3.84 s
sage: sage: gc.collect()
17047
sage: sage: gc.collect()
864
sage: sage: after=[c for c in gc.get_objects() if id(c) not in before]
sage: sage: [c for c in Counter([str(type(a)) for a in after]).items() if c[1] > 4000]
[]

Same, without systematic full category initialization for matrices:

CPU times: user 3.49 s, sys: 52.8 ms, total: 3.54 s
Wall time: 3.49 s
sage: sage: sage: sage: gc.collect()
18836
sage: sage: sage: sage: gc.collect()
1344

With vanilla 6.2.beta6 (no systematic full category initialization for matrices):

CPU times: user 2.89 s, sys: 33.6 ms, total: 2.92 s
Wall time: 2.88 s
sage: sage: sage: gc.collect()
5032
sage: sage: sage: gc.collect()
704

Hence #15801 as is seems to be going a long way toward fixing this
issue. It's still non negligibly slower than develop on this very
tight loop (and apparently more objects get
allocated/deallocated). But in exchange we are back to systematic full
category initialization which I believe is much nicer to the user.

What do you think?

On to the elliptic curve benchmarks.

Cheers,
Nicolas

[nthiery]

comment:15

On the benchmark from #11900, I get significantly the same timing with develop and #10963+#15801:

sage: E = J0(46).endomorphism_ring()
sage: %time g = E.gens()
CPU times: user 3.63 s, sys: 94.9 ms, total: 3.73 s
Wall time: 3.90 s    #develop     
Wall time: 3.98 s    #10963
Wall time: 3.86 s    #10963+#15801   

This, despite the additional full category initialization.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

f44661f	Trac 15801: added repr in HeckeModule_free_module (the generic one in modules with basis can't handle it anymore)
545765a	Merge branch 'categories/axioms-10963' into categories/over_a_base_category-15801
961bfb6	Trac 15801: reinstated test in vector spaces after some mess up in the #10963 branch; updated some doctests
a051864	Trac 15801: deprecates MatrixSpace.full_category_initialisation which is now unneeded
42ab3cd	Trac 15801: update thematic_tutorials/coercion_and_categories.rst w.r.t the full initialization of matrix spaces
9cc7ef4	Trac 15801: little fix in polynomial_default_category, and update doctests involving categories of polynomial rings
3d2ec28	Trac 15801: fixed recent missing import
cf847f8	Trac 15801: use a group algebra rather than a polynomial algebra in an example to keep it interesting
fa60747	Trac 15801: fixed typo in doctest
2121f51	Trac 15801: improved subcategory and containment tests for categories over a base ring category

[sagetrac-git]

Changed commit from 3a63847 to 2121f51

[nthiery]

comment:17

Up to merging in #15919, it's likely that all long test will pass. Running them now.

[sagetrac-git]

Changed commit from 2121f51 to 12afbe4

[sagetrac-git]

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

12afbe4

Trac 15801: fixed ReST typo

[tscrim]

comment:19

So Algebras(Rings()) would cover any algebra (well...any assoc & unital algebra)?

Also I think we should not loose support for having the category of algebras over a fixed base ring. For example, given two representations V, W of a group algebra RG over R, the morphisms from V to W as RG-modules is (significantly) smaller than the morphisms as R-modules. Currently our set of morphisms depends on the category, which if we keep the current setup, would give that Hom(V, W, Modules(RG)) is Hom(V, W, Modules(R)) (well, maybe only ==).

Actually...RG would be the category of group algebras whereas R would be in the category of rings, unless R was also the group algebra of some other group (okay, it's very contrived, but possible). My point is that just passing the category into Modules doesn't always tell us the full structure (of the homset), and is there some way we can work around this?

[nthiery]

comment:20

Replying to @tscrim:

So Algebras(Rings()) would cover any algebra (well...any assoc & unital algebra)?

Yup. And at some point we will want weaker things like Algebras(SemiRings()) and so on.

Also I think we should not loose support for having the category of algebras over a fixed base ring.

I agree with that, though more if we want to manipulate the category
"mathematically". From a code perspective point of view, since #11900,
the provided abstract classes only depends on the category of the base
ring, and this has not been a limitation so far.

For example, given two representations V, W of a group algebra RG over R, the morphisms from V to W as RG-modules is (significantly) smaller than the morphisms as R-modules. Currently our set of morphisms depends on the category, which if we keep the current setup, would give that Hom(V, W, Modules(RG)) is Hom(V, W, Modules(R)) (well, maybe only ==).

Actually...RG would be the category of group algebras whereas R would be in the category of rings, unless R was also the group algebra of some other group (okay, it's very contrived, but possible). My point is that just passing the category into Modules doesn't always tell us the full structure (of the homset), and is there some way we can work around this?

Well, as you say, we have two distinct categories:

    sage: Modules(Rings())

    sage: Modules(GroupAlgebras(Rings()))

so we are fine, aren't we?

Cheers,
Nicolas

[tscrim]

comment:21

Until I make a group ring over a group ring. Actually, maybe a less contrived example of modules over S = R[a,b] / J where R = ZZ[x,y] / I for some ideals I, J. There should be more morphisms as R modules than as S modules. I think this could be a general issue anytime we try to do extension of scalars (or I'm being completely paranoid).

[sagetrac-git]

Changed commit from 281f539 to dcb11d8

[sagetrac-git]

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

96c631f	Merge branch 'develop' into categories/axioms-10963
b1a2aed	Trac 10963: two typo fixes to let the pdf documentation compile
c16f18b	Merge branch 'public/ticket/10963-doc-distributive' of trac.sagemath.org:sage into categories/axioms-10963
dcb11d8	Merge branch 'categories/axioms-10963' into categories/over_a_base_category-15801

[nthiery]

comment:57

Pdf compilation fixed in #10963 and merged here.

[simon-king-jena]

comment:58

I think the quiver issue should be discussed here.

Nicolas, do you agree with Darij that quiver representations over QQ should live in Modules(QQ), not in Modules(QuiverAlgebra)? If this is so, then hopefully it will be easy to switch.

[nthiery]

comment:59

Replying to @simon-king-jena:

I think the quiver issue should be discussed here.

Ok.

Nicolas, do you agree with Darij that quiver representations over QQ should live in Modules(QQ), not in Modules(QuiverAlgebra)? If this is so, then hopefully it will be easy to switch.

No strong opinion either way, but yes, I would lean in this direction
since we don't have yet a proper category hierarchy for
representations. So in the mean time, it makes sense to reserve
Modules(K) for what we have used it so far: doing linear algebra
over K, ...

If it makes it easier to switch, so much the better :-)

Cheers,
Nicolas

[sagetrac-git]

Changed commit from dcb11d8 to 15658bd

[sagetrac-git]

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

15658bd

Trac 15801: fixed merge with #12630

[nthiery]

comment:61

Replying to @simon-king-jena:

Nicolas, do you agree with Darij that quiver representations over QQ should live in Modules(QQ), not in Modules(QuiverAlgebra)? If this is so, then hopefully it will be easy to switch.

Done. Please review! Running all long tests now.

[simon-king-jena]

comment:62

Sorry for my being too slow. I wanted to try and fix it, but was busy with some other tickets. Thank you for doing it, and I'll now try to review.

[simon-king-jena]

comment:63

I read the latest commit, and it seems good. Hence, I wait for the test results...

[simon-king-jena]

comment:64

The pdf does build...

[simon-king-jena]

comment:65

I get numerous errors of the following type:

File "src/sage/dev/sagedev.py", line 4836, in sage.dev.sagedev.SageDev._new_local_branch_for_ticket
Failed example:
    dev, config, UI, server = single_user_setup()
Expected nothing
Got:
    GitError: git exited with a non-zero exit code (1).
    This happened while executing "git -c user.email=doc@test.test -c user.name=doctest pull /home/king/.sage/temp/linux-etl7.site/1419/dir_y4yz1q/repo master".
    git printed nothing to STDOUT.
    git printed the following to STDERR:
    git: 'pull' is not a git command. See 'git --help'.
    <BLANKLINE>
    Did you mean this?
        shell

Never seen such errors before.

[simon-king-jena]

Changed work issues from doc-pdf to none

[simon-king-jena]

comment:66

Is this perhaps an issue of sage-6.3.beta0?

[nthiery]

comment:67

Thanks Simon for reviewing this! Could you have a quick look as well at the small last commit on #10963?

For the git error, IIRC you need a recent version of git for all tests to pass, and doing
sage -i git should do the job.

Cheers,
Nicolas

[darijgr]

comment:68

Simon, are you using sage git? There is always plain git, and I fear that it'll stay the more reliable option for a long time...

[tscrim]

comment:69

Tests pass for me, so I'm going to set this to positive review.

I also only use my system-wide git.

[simon-king-jena]

comment:70

Replying to @tscrim:

I also only use my system-wide git.

Are you sure that you use your system-wide git when you run the tests in sage.dev? Anyway, my system-wide git does know about git pull---only Sage's git doesn't know.

Best regards,
Simon

[simon-king-jena]

comment:71

Replying to @darijgr:

Simon, are you using sage git? There is always plain git, and I fear that it'll stay the more reliable option for a long time...

I am now talking about the git that I use, but about the git that sage -dev uses.

[simon-king-jena]

comment:72

Replying to @nthiery:

For the git error, IIRC you need a recent version of git for all tests to pass, and doing
sage -i git should do the job.

It doesn't, because git is already installed. sage -f git doesn't work either. The resulting git still doesn't know about the pull command.

[vbraun]

Changed branch from public/categories/over-a-base-ring-category-15801 to 15658bd