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

darijgr · 2013-12-01T01:34:54Z

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

The text was updated successfully, but these errors were encountered:

darijgr · 2013-12-01T01:35:14Z

just documentation typos that i fixed when i was reading it

darijgr · 2013-12-01T06:58:58Z

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

darijgr · 2013-12-01T06:58:58Z

comment:1

Attachment: cat-fixes.patch.gz

darijgr · 2013-12-10T16:34:28Z

comment:2

[obsolete]

darijgr · 2014-05-25T16:24:13Z

Branch: public/combinat/15475

darijgr · 2014-05-25T16:24:13Z

Commit: a3c4cf3

darijgr · 2014-05-25T16:25:22Z

comment:7

Needs_review now (finally). The review is really trivial.

darijgr · 2014-05-25T16:26:06Z

Changed branch from public/combinat/15475 to public/categories/15475

darijgr · 2014-05-25T16:26:06Z

Changed commit from a3c4cf3 to none

sagetrac-git · 2014-05-25T16:26:22Z

Commit: a3c4cf3

sagetrac-git · 2014-05-25T16:26:22Z

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

darijgr · 2014-05-25T16:30:53Z

comment:10

Branch fixed, but more bughuntery in progress.

darijgr · 2014-05-25T16:30:53Z

Changed branch from public/categories/15475 to public/combinat/15475

darijgr · 2014-05-25T16:33:29Z

Changed branch from public/combinat/15475 to public/categories/15475

darijgr · 2014-05-25T16:33:29Z

New commits:

`ef918e3`	`#15475: doc fixes after #10963`

darijgr · 2014-05-25T16:33:29Z

Changed commit from a3c4cf3 to ef918e3

darijgr · 2014-06-26T11:10:08Z

comment:32

OUCH. I just realized that I forgot to reenable the symmetric functions doctest, and not unexpectedly it is still broken. OK, this thing must be unrelated to #10963 after all. Simon, can you make sense of this?

Doctesting 1 file.
sage -t src/sage/combinat/sf/sfa.py
**********************************************************************
File "src/sage/combinat/sf/sfa.py", line 752, in sage.combinat.sf.sfa.SymmetricFunctionsBases.ParentMethods.corresponding_basis_over
Failed example:
    s.corresponding_basis_over(Integers(13))
Exception raised:
    Traceback (most recent call last):
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.combinat.sf.sfa.SymmetricFunctionsBases.ParentMethods.corresponding_basis_over[5]>", line 1, in <module>
        s.corresponding_basis_over(Integers(Integer(13)))
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/combinat/sf/sfa.py", line 814, in corresponding_basis_over
        return attrcall(self._basis)(SymmetricFunctions(R))
      File "classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1282)
      File "cachefunc.pyx", line 1077, in sage.misc.cachefunc.WeakCachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6486)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/unique_representation.py", line 1021, in __classcall__
        instance = typecall(cls, *args, **options)
      File "classcall_metaclass.pyx", line 518, in sage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:1665)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/combinat/sf/sf.py", line 763, in __init__
        Parent.__init__(self, category = GradedHopfAlgebras(R).WithRealizations())
      File "parent.pyx", line 358, in sage.structure.parent.Parent.__init__ (build/cythonized/sage/structure/parent.c:4247)
      File "parent.pyx", line 418, in sage.structure.parent.Parent._init_category_ (build/cythonized/sage/structure/parent.c:4797)
      File "lazy_attribute.pyx", line 127, in sage.misc.lazy_attribute._lazy_attribute.__get__ (build/cythonized/sage/misc/lazy_attribute.c:1353)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 1298, in parent_class
        return self._make_named_class('parent_class', 'ParentMethods')
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 2568, in _make_named_class
        cache=cache, **options)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 1221, in _make_named_class
        reduction = reduction, cache = cache)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/dynamic_class.py", line 316, in dynamic_class
        return dynamic_class_internal.f(name, bases, cls, reduction, doccls, prepend_cls_bases)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/dynamic_class.py", line 411, in dynamic_class_internal
        return metaclass(name, bases, methods)
    TypeError: Cannot create a consistent method resolution
    order (MRO) for bases Algebras.parent_class, Monoids.WithRealizations.parent_class, Bialgebras.parent_class, Coalgebras.WithRealizations.parent_class
**********************************************************************
File "src/sage/combinat/sf/sfa.py", line 758, in sage.combinat.sf.sfa.SymmetricFunctionsBases.ParentMethods.corresponding_basis_over
Failed example:
    mj.corresponding_basis_over(Integers(13))
Exception raised:
    Traceback (most recent call last):
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run
        self.execute(example, compiled, test.globs)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute
        exec compiled in globs
      File "<doctest sage.combinat.sf.sfa.SymmetricFunctionsBases.ParentMethods.corresponding_basis_over[9]>", line 1, in <module>
        mj.corresponding_basis_over(Integers(Integer(13)))
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/combinat/sf/sfa.py", line 814, in corresponding_basis_over
        return attrcall(self._basis)(SymmetricFunctions(R))
      File "classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1282)
      File "cachefunc.pyx", line 1077, in sage.misc.cachefunc.WeakCachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6486)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/unique_representation.py", line 1021, in __classcall__
        instance = typecall(cls, *args, **options)
      File "classcall_metaclass.pyx", line 518, in sage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:1665)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/combinat/sf/sf.py", line 763, in __init__
        Parent.__init__(self, category = GradedHopfAlgebras(R).WithRealizations())
      File "parent.pyx", line 358, in sage.structure.parent.Parent.__init__ (build/cythonized/sage/structure/parent.c:4247)
      File "parent.pyx", line 418, in sage.structure.parent.Parent._init_category_ (build/cythonized/sage/structure/parent.c:4797)
      File "lazy_attribute.pyx", line 127, in sage.misc.lazy_attribute._lazy_attribute.__get__ (build/cythonized/sage/misc/lazy_attribute.c:1353)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 1298, in parent_class
        return self._make_named_class('parent_class', 'ParentMethods')
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 2568, in _make_named_class
        cache=cache, **options)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 1221, in _make_named_class
        reduction = reduction, cache = cache)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/dynamic_class.py", line 316, in dynamic_class
        return dynamic_class_internal.f(name, bases, cls, reduction, doccls, prepend_cls_bases)
      File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/dynamic_class.py", line 411, in dynamic_class_internal
        return metaclass(name, bases, methods)
    TypeError: Cannot create a consistent method resolution
    order (MRO) for bases Algebras.parent_class, Monoids.WithRealizations.parent_class, Bialgebras.parent_class, Coalgebras.WithRealizations.parent_class
**********************************************************************
1 item had failures:
   2 of  43 in sage.combinat.sf.sfa.SymmetricFunctionsBases.ParentMethods.corresponding_basis_over
    [881 tests, 2 failures, 19.17 s]
----------------------------------------------------------------------
sage -t src/sage/combinat/sf/sfa.py  # 2 doctests failed
----------------------------------------------------------------------

New commits:

`da61e19`	`reenable SymmetricFunctions doctest`

simon-king-jena · 2014-06-26T13:15:18Z

comment:33

Replying to @darijgr:

OUCH. I just realized that I forgot to reenable the symmetric functions doctest, and not unexpectedly it is still broken. OK, this thing must be unrelated to #10963 after all. Simon, can you make sense of this?
    TypeError: Cannot create a consistent method resolution
    order (MRO) for bases Algebras.parent_class, Monoids.WithRealizations.parent_class, Bialgebras.parent_class, Coalgebras.WithRealizations.parent_class

Does that mean that the controlled C3 algorithm is not bullet proof, resp. that the global ordering imposed on the categories is not as it should be? Nicolas?

tscrim · 2014-06-26T14:03:52Z

comment:34

I'm pretty sure it's related to the category refinement that occurs for Zmod(13):

sage: SymmetricFunctions(Zmod(14))
Symmetric Functions over Ring of integers modulo 14
sage: SymmetricFunctions(Zmod(12)) # This isn't needed to reproduce the error
Symmetric Functions over Ring of integers modulo 12
sage: SymmetricFunctions(Zmod(13))
   # Boom
sage: Rp = Zmod(13)
sage: Rp.category()
Join of Category of finite commutative rings and Category of subquotients of monoids and Category of quotients of semigroups
sage: Rp in Fields()
True
sage: Rp.category()
Join of Category of finite fields and Category of subquotients of monoids and Category of quotients of semigroups
sage: SymmetricFunctions(Rp)
Symmetric Functions over Ring of integers modulo 13

(You can remove the Rp.category() and it will still work.) Compare this with

sage: SymmetricFunctions(Zmod(12))
Symmetric Functions over Ring of integers modulo 12
sage: SymmetricFunctions(GF(13))
Symmetric Functions over Finite Field of size 13

However, in a fresh Sage:

sage: Rp = Zmod(13)
sage: SymmetricFunctions(Rp)
Symmetric Functions over Ring of integers modulo 13
sage: Rp.category()
Join of Category of finite fields and Category of subquotients of monoids and Category of quotients of semigroups

This might be useful info (also in a fresh Sage):

sage: GradedHopfAlgebras(Zmod(14))
Join of Category of hopf algebras over Ring of integers modulo 14 and Category of graded algebras over Ring of integers modulo 14
sage: Rp = Zmod(13)
sage: GradedHopfAlgebras(Rp)
/home/travis/sage/local/lib/python2.7/site-packages/sage/categories/category.py:858: UserWarning: Inconsistent sorting results for all super categories of <class 'sage.categories.category.JoinCategory'>
  self.__class__))
/home/travis/sage/local/lib/python2.7/site-packages/sage/categories/category.py:858: UserWarning: Inconsistent sorting results for all super categories of <class 'sage.categories.hopf_algebras.HopfAlgebras_with_category'>
  self.__class__))
Join of Category of hopf algebras over Ring of integers modulo 13 and Category of graded algebras over Ring of integers modulo 13
sage: Rp.category()
Join of Category of finite fields and Category of subquotients of monoids and Category of quotients of semigroups

nthiery · 2014-07-02T16:27:01Z

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 · 2014-07-18T01:09:56Z

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 · 2014-07-18T11:06:22Z

comment:37

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

tscrim · 2014-07-18T18:23:09Z

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 · 2014-07-18T18:23:09Z

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

sagetrac-git · 2014-07-18T18:24:23Z

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`

sagetrac-git · 2014-07-18T18:24:23Z

Changed commit from da61e19 to bf34154

a-andre · 2014-08-28T15:47:53Z

comment:41

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

tscrim · 2014-08-28T23:26:39Z

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 · 2014-11-06T20:59:21Z

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 · 2014-11-06T21:18:12Z

comment:44

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

darijgr · 2014-11-06T21:41:19Z

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 · 2014-11-07T06:16:25Z

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 · 2014-11-07T15:28:17Z

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.

@darijgr

### 📚 Description    Rebased an ancient ticket branch from @darijgr: - Fixes #15475  ### 📝 Checklist  - [x] The title is concise, informative, and self-explanatory. - [ ] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies   URL: #35521 Reported by: Matthias Köppe Reviewer(s): Frédéric Chapoton

darijgr added this to the sage-6.1 milestone Dec 1, 2013

darijgr added c: categories labels Dec 1, 2013

This comment has been minimized.

Sign in to view

darijgr changed the title ~~Reenable broken doctest in #15473 when #10963 is merged~~ Reenable broken doctests in #15473 and #15476 when #10963 is merged Dec 1, 2013

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.2, sage-6.3 May 6, 2014

This comment has been minimized.

Sign in to view

darijgr added t: bug labels May 25, 2014

darijgr removed the s: needs review label May 25, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.3, sage-6.4 Aug 10, 2014

a-andre added s: needs work and removed s: needs review labels Aug 28, 2014

mkoeppe removed this from the sage-6.4 milestone Dec 29, 2022

This was referenced Dec 29, 2022

Weak morphism created with register_coercion can result in invalid coercion #16532

Open

Fix coercions for descent and symmetric group algebras #16678

Closed

Fix MRO issues with categories #20460

Open

nthiery mentioned this issue Dec 29, 2022

Toward singleton categories: subcategories of Modules #22962

Open

vbraun closed this as completed in #35521 Apr 23, 2023

mkoeppe added this to the sage-10.0 milestone Apr 23, 2023

mkoeppe removed the s: needs work label Apr 23, 2023

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

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

Comments

darijgr commented Dec 1, 2013

darijgr commented Dec 1, 2013

This comment has been minimized.

darijgr commented Dec 1, 2013

darijgr commented Dec 1, 2013

darijgr commented Dec 10, 2013

darijgr commented May 25, 2014

darijgr commented May 25, 2014

This comment has been minimized.

darijgr commented May 25, 2014

darijgr commented May 25, 2014

darijgr commented May 25, 2014

sagetrac-git mannequin commented May 25, 2014

sagetrac-git mannequin commented May 25, 2014

darijgr commented May 25, 2014

darijgr commented May 25, 2014

darijgr commented May 25, 2014

darijgr commented May 25, 2014

darijgr commented May 25, 2014

darijgr commented Jun 26, 2014

simon-king-jena commented Jun 26, 2014

tscrim commented Jun 26, 2014

nthiery commented Jul 2, 2014

tscrim commented Jul 18, 2014

darijgr commented Jul 18, 2014

tscrim commented Jul 18, 2014

tscrim commented Jul 18, 2014

sagetrac-git mannequin commented Jul 18, 2014

sagetrac-git mannequin commented Jul 18, 2014

a-andre commented Aug 28, 2014

tscrim commented Aug 28, 2014

darijgr commented Nov 6, 2014

tscrim commented Nov 6, 2014

darijgr commented Nov 6, 2014

tscrim commented Nov 7, 2014

darijgr commented Nov 7, 2014