Opened 4 years ago

Closed 4 years ago

#23000 closed defect (fixed)

Fix inconsistency in `Modules.FiniteDimensional.extra_super_categories`

Reported by: nthiery Owned by:
Priority: major Milestone: sage-8.0
Component: categories Keywords:
Cc: tscrim Merged in:
Authors: Nicolas M. Thiéry Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: fc76620 (Commits) Commit: fc766203eaecbbf86767571c68dc569a02b2582c
Dependencies: Stopgaps:

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 (15)

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`

comment:8 Changed 4 years ago by git

  • Commit changed from bc94ce675b1b3c380c1aef09cd036f9c41dacef4 to 70e23f4c5f769dd6ce8dc9502e8ecfdb5f5ff15e

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

70e23f423000: Fix inconsistency in Modules.FiniteDimensional.extra_super_categories

comment:9 Changed 4 years ago by git

  • Commit changed from 70e23f4c5f769dd6ce8dc9502e8ecfdb5f5ff15e to fc766203eaecbbf86767571c68dc569a02b2582c

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

fc7662023000: trivial doctest update

comment:10 Changed 4 years ago by nthiery

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.

comment:11 Changed 4 years ago by nthiery

  • Status changed from needs_info to needs_review

comment:12 Changed 4 years ago by nthiery

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

comment:13 Changed 4 years ago by tscrim

  • Authors set to Nicolas M. Thiéry
  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

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.

comment:14 Changed 4 years ago by nthiery

Thanks for the review!

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

comment:15 Changed 4 years ago by vbraun

  • Branch changed from u/nthiery/add_trivial__additivegroups_finite__category__and_workaround_mro_issue to fc766203eaecbbf86767571c68dc569a02b2582c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.