Reenable broken doctests in #15473 and #15476 when #10963 is merged

[darijgr]

This branch activates two combinat doctests which were disabled due to unexplainable bugs that were fixed in #10963:

            The following doctest is disabled pending :trac:`10963`::

                sage: s = SymmetricFunctions(Zmod(14)).s() # not tested
                sage: s.is_integral_domain() # not tested
                False

and

                    sage: def descent_test(n):
                    ....:     DA = DescentAlgebra(QQ, n)
                    ....:     NSym = NonCommutativeSymmetricFunctions(QQ)
                    ....:     S = NSym.S()
                    ....:     DAD = DA.D()
                    ....:     w_n = DAD(set(range(1, n)))
                    ....:     for I in Compositions(n):
                    ....:         if not (S[I].star_involution()
                    ....:                 == w_n * S[I].to_descent_algebra(n) * w_n):
                    ....:             return False
                    ....:         return True
                    sage: all( descent_test(i) for i in range(4) ) # not tested
                    True
                    sage: all( descent_test(i) for i in range(6) ) # not tested
                    True

                .. TODO::

                    Once :trac:`10963` is in, remove the first "not tested" above,
                    and replace the second one by "long time".

Also, a few typos in the c3_controlled doc are fixed.

Disregard the attachment.

Depends on #10963 Depends on #15473 Depends on #15476 Depends on #16678

CC: @nthiery @simon-king-jena @tscrim @sagetrac-sage-combinat

Component: categories

Keywords: 10963, c3, transitivity, descent algebras, symmetric functions

Branch/Commit: public/categories/15475 @ bf34154

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

[nthiery]

comment:35

On u/nthiery/15475-sym_in_categories_over_base_ring is a tentative workaround the MRO crash by making sym's category more independent of the base ring. Almost all tests pass in sage.combinat.sf, except for trivialities and a test involving QSym (which should probably get the same treatment).

[tscrim]

comment:36

Darij, would you be okay separating the current fixes of the descent and symmetric group algebras off as another ticket so we can get that in (everything up to ​ff4e546)?

[darijgr]

comment:37

Definitely. Are you also planning to fix the bugs recently posted on sage-devel?

[tscrim]

comment:38

Replying to @darijgr:

Definitely. Are you also planning to fix the bugs recently posted on sage-devel?

Yes; I did so on #16678.

[tscrim]

Changed dependencies from #10963, #15473, #15476 to #10963, #15473, #15476, #16678

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

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

7e564f2	Merge branch 'public/categories/15475' of trac.sagemath.org:sage into public/categories/15475
b3d98ba	Merge commit 'ff4e546a838e9e9a4be86b3a89d8596658beb3f4' into public/coercions/fix_sga_coercions-16678
31c8ac9	Additional fixes noted on sage-devel thread.
e1ff769	Fixed stupid mistake.
bf34154	Merge branch 'public/coercion/fix_sga_coercions-16678' into public/categories/15475

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

Changed commit from da61e19 to bf34154

[a-andre]

comment:41

Currently, the branch public/categories/15475 doesn't contain any changes compared with origin/develop.

[tscrim]

comment:42

Replying to @a-andre:

Currently, the branch public/categories/15475 doesn't contain any changes compared with origin/develop.

Yes it does, it removes the # not tested. However we do still need to make this handle the category refinement.

[darijgr]

comment:43

Another path-dependent MRO fail related to Hopf algebras over Zmod(n) observed in #11979. This shows that we should fix the category framework or our C3, or whatever else is at fault, rather than try to change Sym into a different category. (Are we actually using our controlled C3 here, or Python's old C3?)

[tscrim]

comment:44

We might be able to get a good workaround by finishing #15229.

[darijgr]

comment:45

That's good news! #15229 might actually be a fix for the root cause, not a workaround:

sage: SymmetricFunctions(Zmod(14))
Symmetric Functions over Ring of integers modulo 14
sage: Zmod(13) in Fields() # if not for this "check", then the following would break
True
sage: SymmetricFunctions(Zmod(13))
Symmetric Functions over Ring of integers modulo 13

and, for #11979:

sage: from sage.algebras.divided_power_algebra import UnivariateDividedPowerAlgebra
sage: A = UnivariateDividedPowerAlgebra(Zmod(9)); A
The divided power algebra over Ring of integers modulo 9
sage: Zmod(5) in Fields() # if not for this "check", then the following would break
True
sage: A = UnivariateDividedPowerAlgebra(Zmod(5)); A
The divided power algebra over Ring of integers modulo 5

So my guess would be that category refinement doesn't like it when a category changes in the midst of it, and the category of Zmod(n) does change when Zmod(n) is tested for fieldness:

sage: Zmod(17).category()
Join of Category of finite commutative rings and Category of subquotients of monoids and Category of quotients of semigroups
sage: Zmod(17) in Fields()
True
sage: Zmod(17).category()
Join of Category of finite fields and Category of subquotients of monoids and Category of quotients of semigroups

With #15229 fixing this, I think we can hope to see the end of this issue.

Is this pattern, where an object lazily starts off with a broad category and then refines in when the user checks for properties, common in Sage? Should we get rid of that or tweak the code to allow it? If we are to allow it, we would probably need to establish a hierarchy of categories or classes such that refining a category of some object can only trigger refinements of categories of lower-class objects in its process, and said refinements should be made sure not to interfere or run races with each other?

EDIT: I also wanted to add that this whole tradeoff between "allow several instances of ZZ/nZZ with different properties, and try to somehow ensure that they behave like they are equal, e.g., providing automatic coercion between their polynomial rings" and "force all instances of ZZ/nZZ to be identical, at the cost of having to update and mutate this single instance long after it is created, and try to somehow ensure that these mutations do not break consistency" reminds me a lot of the constructivity problem of Voevodsky's univalent foundations. Looks like equality is the trickiest thing to formalize...

[tscrim]

comment:46

This is great to hear. I've rebased #15229, so hopefully that will get in soon so we can (finally) close this.

[darijgr]

comment:47

OK, this actually didn't help. :/ What I meant by #15229 fixing this is that the source of this bug was discussed in the #15229 thread. But it wasn't solved there, because with #15229 I still have:

sage: len(Zmod(5).categories())
42
sage: Zmod(5).is_field()
True
sage: len(Zmod(5).categories())
51

Either this lazy discovery of categories has to be removed, or the category refinement and MRO routines must be hardened against it.