Opened 4 years ago

Last modified 4 years ago

#23000 closed defect

Fix inconsistency in `Modules.FiniteDimensional.extra_super_categories` — at Version 7

Reported by: nthiery Owned by:
Priority: major Milestone: sage-8.0
Component: categories Keywords:
Cc: tscrim Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: u/nthiery/add_trivial__additivegroups_finite__category__and_workaround_mro_issue (Commits, GitHub, GitLab) Commit: bc94ce675b1b3c380c1aef09cd036f9c41dacef4
Dependencies: Stopgaps:

Status badges

Description (last modified by 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.

Change History (7)

comment:1 Changed 4 years ago by nthiery

  • Description modified (diff)

comment:2 Changed 4 years ago by nthiery

  • Branch set to u/nthiery/add_trivial__additivegroups_finite__category__and_workaround_mro_issue

comment:3 Changed 4 years ago by nthiery

  • Cc tscrim added
  • Commit set to da3ddcd201fd481431881083266cdea0a42c6453
  • Component changed from PLEASE CHANGE to categories
  • Status changed from new to needs_info
  • Type changed from PLEASE CHANGE to defect

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:

da3ddcd23000: Add trivial category, and workaround MRO issue

comment:4 Changed 4 years ago by git

  • Commit changed from da3ddcd201fd481431881083266cdea0a42c6453 to bc94ce675b1b3c380c1aef09cd036f9c41dacef4

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

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

comment:5 Changed 4 years ago by nthiery

(force repushed after fixing the commit message).

comment:6 Changed 4 years ago by tscrim

  • Description modified (diff)

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

comment:7 Changed 4 years ago by nthiery

  • Description modified (diff)
  • Summary changed from Add trivial `AdditiveGroups.Finite` category, and workaround MRO issue to Fix inconsistency in `Modules.FiniteDimensional.extra_super_categories`
Note: See TracTickets for help on using tickets.