Fix inconsistency in `Modules.FiniteDimensional.extra_super_categories`

[nthiery]

Finite dimensional modules over a finite field are known to Sage to be finite:

    sage: Modules(GF(3)).FiniteDimensional().is_subcategory(Sets().Finite())
    True

However this piece of knowledge was ignored if a base ring category instead of a base ring was passed to Modules:

    sage: Modules(Field().Finite()).FiniteDimensional().is_subcategory(Sets().Finite())
    True

This ticket fixes this.

Comments

This is yet another avatar of the current lack of robustness of categories over base rings. With #20962 which will make module categories singletons, this kind of inconsistency won't be possible anymore.

This issue was discovered while tracking a bug in #18700 which implemented a new category AdditiveGroups.Finite, which triggered the following doctest failure:

sage: K = simplicial_complexes.Simplex(2)
sage: H = Hom(K,K)
sage: id = H.identity()
sage: id.induced_homology_morphism(GF(13)).base_ring()
Traceback (most recent call last)
.../opt/sage-git2/src/sage/misc/c3_controlled.pyx in sage.misc.c3_controlled.C3_sorted_merge (/opt/sage-git2/src/build/cythonized/sage/misc/c3_controlled.c:5151)()
    936                     heads[j] = X
    937                     tailset = tailsets[j]
--> 938                     tailset.remove(key(X))
    939                 else:
    940                     del heads[j]

KeyError: (258, 65)

Detailed analysis

Recall that:

• categories are endowed with a total order which is used to ensure that the Method Resolution Orders chosen by Python are always consistent. This total order shall refine the subcategory relation. This is achieved by assigning a comparison key to each category according to the order in which they are created (and some further data)

• To avoid creating many copies of the same hierarchy of classes, parametrized categories may share their parent/element/... classes, and therefore the same comparison key.

In the case at hand, C1=Modules(Fields().Finite().FiniteDimensional() was created first. Since it was not a subcategory of A=AdditiveGroups().Finite(), there was no constraint on their relative comparison keys; it then turned out that C was assigned a comparison key smaller than that of A.

Later on, when C2=Modules(GF(3)).FiniteDimensional() got created, it got the same comparison key as C1 while simultaneously deriving from A, breaking the assumption.

CC: @tscrim

Component: categories

Author: Nicolas M. Thiéry

Branch/Commit: fc76620

Reviewer: Travis Scrimshaw

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

[nthiery]

Description changed:

--- 
+++ 
@@ -1 +1,56 @@
+#18700 implements a new category `AdditiveGroups.Finite`. Without
+further change, this triggered the following doctest failure:

+```
+sage: K = simplicial_complexes.Simplex(2)
+sage: H = Hom(K,K)
+sage: id = H.identity()
+sage: id.induced_homology_morphism(GF(13)).base_ring()
+Traceback (most recent call last)
+.../opt/sage-git2/src/sage/misc/c3_controlled.pyx in sage.misc.c3_controlled.C3_sorted_merge (/opt/sage-git2/src/build/cythonized/sage/misc/c3_controlled.c:5151)()
+    936                     heads[j] = X
+    937                     tailset = tailsets[j]
+--> 938                     tailset.remove(key(X))
+    939                 else:
+    940                     del heads[j]
+
+KeyError: (258, 65)
+```
+
+This is yet another avatar of lack of robustness of categories over
+base rings, which will be fixed by #20962 when module categories will
+be singleton. To get the ball rolling for #18700 which is otherwise
+ready, this ticket provides a quick workaround which should be robust
+enough for now.
+
+
+## Detailed analysis
+
+Recall that
+
+- categories are endowed with a total order which is used to ensure
+  that the Method Resolution Orders chosen by Python are always
+  consistent. This total order shall refine the subcategory relation.
+  This is achieved by assigning a comparison key to each category
+  according to the order in which they are created.
+
+- To make the total order more reproducible from one session to the
+  other, the first piece of the comparison key is given by a bit array
+  of flags which are set according to whether the category is a
+  subcategory of some "atom categories": `FacadeSets`, `FiniteSets`, ...
+
+- To avoid creating many copies of the same hierarchy of classes,
+  parametrized categories may share their parent/element/... classes,
+  and therefore the same comparison key.
+
+  In the case at hand, depending on the order in which categories were
+  created, the assumption of refining the subcategory relation got
+  broken (I still need to analyze this precisely):
+  `Modules(GF(3)).FiniteDimensional()` got a key smaller than its
+  super category `AdditiveGroup().Finite()`
+
+This risk will vanish by itself when module categories will be
+singleton. In the mean time, adding "Modules" to the list of atom
+categories guarantee that `AdditiveGroups().Finite()` gets a strictly
+smaller key.
+

[nthiery]

Branch: u/nthiery/add_trivial__additivegroups_finitecategoryand_workaround_mro_issue

[nthiery]

comment:3

All tests passed on my machine.

Not yet "needs review" for I want to dig once more in to check a detail I did not quite fully understand yet in the failure.

---

New commits:

da3ddcd

23000: Add trivial category, and workaround MRO issue

[nthiery]

Commit: da3ddcd

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

bc94ce6

23000: Add trivial AdditiveGroups.Finite category, and workaround MRO issue

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from da3ddcd to bc94ce6

[nthiery]

comment:5

(force repushed after fixing the commit message).

[tscrim]

Description changed:

--- 
+++ 
@@ -18,7 +18,7 @@

This is yet another avatar of lack of robustness of categories over -base rings, which will be fixed by #20962 when module categories will +base rings, which will be fixed by #22962 when module categories will be singleton. To get the ball rolling for #18700 which is otherwise ready, this ticket provides a quick workaround which should be robust enough for now.

[tscrim]

comment:6

Okay, I think I understand why this change is needed. Did you manage to track down the detail you mentioned in comment:3?

[nthiery]

Description changed:

--- 
+++ 
@@ -1,5 +1,30 @@
-#18700 implements a new category `AdditiveGroups.Finite`. Without
-further change, this triggered the following doctest failure:
+Finite dimensional modules over a finite field are known to Sage to be finite:
+
+```
+    sage: Modules(GF(3)).FiniteDimensional().is_subcategory(Sets().Finite())
+    True
+```
+
+However this piece of knowledge was ignored if a
+base ring category instead of a base ring was passed to `Modules`:
+
+```
+    sage: Modules(Field().Finite()).FiniteDimensional().is_subcategory(Sets().Finite())
+    True
+```
+
+This ticket fixes this.
+
+## Comments
+
+This is yet another avatar of the current lack of robustness of
+categories over base rings. With #20962 which will make module
+categories singletons, this kind of inconsistency won't be possible
+anymore.
+
+This issue was discovered while tracking a bug in #18700 which
+implemented a new category `AdditiveGroups.Finite`, which triggered
+the following doctest failure:

sage: K = simplicial_complexes.Simplex(2) @@ -17,40 +42,28 @@ KeyError: (258, 65)

-This is yet another avatar of lack of robustness of categories over
-base rings, which will be fixed by #22962 when module categories will
-be singleton. To get the ball rolling for #18700 which is otherwise
-ready, this ticket provides a quick workaround which should be robust
-enough for now.
-
-
 ## Detailed analysis

-Recall that
+Recall that:

 - categories are endowed with a total order which is used to ensure
   that the Method Resolution Orders chosen by Python are always
   consistent. This total order shall refine the subcategory relation.
   This is achieved by assigning a comparison key to each category
-  according to the order in which they are created.
-
-- To make the total order more reproducible from one session to the
-  other, the first piece of the comparison key is given by a bit array
-  of flags which are set according to whether the category is a
-  subcategory of some "atom categories": `FacadeSets`, `FiniteSets`, ...
+  according to the order in which they are created (and some further
+  data)

 - To avoid creating many copies of the same hierarchy of classes,
   parametrized categories may share their parent/element/... classes,
   and therefore the same comparison key.

-  In the case at hand, depending on the order in which categories were
-  created, the assumption of refining the subcategory relation got
-  broken (I still need to analyze this precisely):
-  `Modules(GF(3)).FiniteDimensional()` got a key smaller than its
-  super category `AdditiveGroup().Finite()`
+In the case at hand,
+`C1=Modules(Fields().Finite().FiniteDimensional()` was created first.
+Since it was not a subcategory of `A=AdditiveGroups().Finite()`, there
+was no constraint on their relative comparison keys; it then turned
+out that `C` was assigned a comparison key smaller than that of `A`.

-This risk will vanish by itself when module categories will be
-singleton. In the mean time, adding "Modules" to the list of atom
-categories guarantee that `AdditiveGroups().Finite()` gets a strictly
-smaller key.
+Later on, when `C2=Modules(GF(3)).FiniteDimensional()` got created, it
+got the same comparison key as `C1` while simultaneously deriving from
+`A`, breaking the assumption.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from bc94ce6 to 70e23f4

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

70e23f4

23000: Fix inconsistency in Modules.FiniteDimensional.extra_super_categories

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 70e23f4 to fc76620

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

fc76620

23000: trivial doctest update

[nthiery]

comment:10

My analysis was actually incorrect. The culprit really was in the categories, not the infrastructure, and is fixed now. The infrastructure just made it easy to screw up and hard to track. This later point should be fixed with #22962.

All long tests pass.

[nthiery]

comment:12

I'll now rebase #18700 on top of this one.

[tscrim]

comment:13

Somehow this change and why it wasn't working seems like something we should have realized sooner. I don't think this check is done elsewhere. Positive review.

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

Author: Nicolas M. Thiéry

[nthiery]

comment:14

Thanks for the review!

I had done a quick search for other extra_super_categories where similar checks, and indeed did not find any.

[vbraun]

Changed branch from u/nthiery/add_trivial__additivegroups_finitecategoryand_workaround_mro_issue to fc76620