center_basis for group algebra works for one group but not isomorphic copy

[a202b734-ed91-4b19-86b2-d3b6d5b55df3]

Running sage 9.5.

This works:

Gfail=PermutationGroup([(1,2,3),(2,3,4)])
Gworks=AlternatingGroup(4)
Rfail=GroupAlgebra(Gfail,QQ)
Rworks=GroupAlgebra(Gworks,QQ)
Rworks.center_basis()

This fails:

Rfail.center_basis()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
<ipython-input-3-a6beb598037d> in <module>
----> 1 Rfail.center_basis()

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13041)()
   2308         if self.cache is None:
   2309             f = self.f
-> 2310             self.cache = f(self._instance)
   2311         return self.cache
   2312 

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/categories/group_algebras.py in center_basis(self)
    204                 - :meth:`Monoids.Algebras.ElementMethods.is_central`
    205             """
--> 206             return tuple([self.sum_of_monomials(conj) for conj  in
    207                           self.basis().keys().conjugacy_classes()])
    208 

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/categories/group_algebras.py in <listcomp>(.0)
    204                 - :meth:`Monoids.Algebras.ElementMethods.is_central`
    205             """
--> 206             return tuple([self.sum_of_monomials(conj) for conj  in
    207                           self.basis().keys().conjugacy_classes()])
    208 

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/categories/poor_man_map.py in __call__(self, *args)
    258         """
    259         for function in reversed(self._functions):
--> 260             args = [function(*args)]
    261         return args[0]
    262 

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/combinat/free_module.py in _sum_of_monomials(self, indices)
   1041         """
   1042         R = self.base_ring()
-> 1043         ret = blas.sum_of_monomials(indices, R.one())
   1044         return self.element_class(self, ret)
   1045 

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/data_structures/blas_dict.pyx in sage.data_structures.blas_dict.sum_of_monomials (build/cythonized/sage/data_structures/blas_dict.c:3796)()
    356     return remove_zeros(result)
    357 
--> 358 cpdef dict sum_of_monomials(monomials, scalar):
    359     r"""
    360     Return the pointwise addition of ``monomials``.

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/data_structures/blas_dict.pyx in sage.data_structures.blas_dict.sum_of_monomials (build/cythonized/sage/data_structures/blas_dict.c:3614)()
    377     cdef dict result = {}
    378     cdef object m
--> 379     for m in monomials:
    380         if m in result:
    381             result[m] += scalar

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/sets/recursively_enumerated_set.pyx in breadth_first_search_iterator (build/cythonized/sage/sets/recursively_enumerated_set.c:6352)()
    835             for x in current_level:
    836                 for y in self.successors(x):
--> 837                     if y is None or y in known:
    838                         continue
    839                     yield y

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/structure/element.pyx in sage.structure.element.Element.__richcmp__ (build/cythonized/sage/structure/element.c:10513)()
   1110             return (<Element>self)._richcmp_(other, op)
   1111         else:
-> 1112             return coercion_model.richcmp(self, other, op)
   1113 
   1114     cpdef _richcmp_(left, right, int op):

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.richcmp (build/cythonized/sage/structure/coerce.c:20599)()
   1971         # Coerce to a common parent
   1972         try:
-> 1973             x, y = self.canonical_coercion(x, y)
   1974         except (TypeError, NotImplementedError):
   1975             pass

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.canonical_coercion (build/cythonized/sage/structure/coerce.c:12619)()
   1330                 if x_elt._parent is y_elt._parent:
   1331                     return x_elt,y_elt
-> 1332             self._coercion_error(x, x_map, x_elt, y, y_map, y_elt)
   1333 
   1334         cdef bint x_numeric = isinstance(x, (int, long, float, complex))

~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel._coercion_error (build/cythonized/sage/structure/coerce.c:21354)()
   2029             <class 'str'> 'g'
   2030         """
-> 2031         raise RuntimeError("""There is a bug in the coercion code in Sage.
   2032 Both x (=%r) and y (=%r) are supposed to have identical parents but they don't.
   2033 In fact, x has parent '%s'

RuntimeError: There is a bug in the coercion code in Sage.
Both x (=()) and y (=()) are supposed to have identical parents but they don't.
In fact, x has parent 'Permutation Group with generators [(2,3,4), (1,2,3)]'
whereas y has parent 'Permutation Group with generators [(2,3,4), (1,2,3)]'
Original elements () (parent Permutation Group with generators [(2,3,4), (1,2,3)]) and () (parent Permutation Group with generators [(2,3,4), (1,2,3)]) and maps
<class 'NoneType'> None
<class 'sage.structure.coerce_maps.DefaultConvertMap_unique'> (map internal to coercion system -- copy before use)
Coercion map:
  From: Permutation Group with generators [(2,3,4), (1,2,3)]
  To:   Permutation Group with generators [(2,3,4), (1,2,3)]

CC: @nbruin @videlec @fchapoton

Component: coercion

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

[tscrim]

comment:1

Interesting. This is coming from the fact that generic permutation groups are not unique parents:

sage: G2 = PermutationGroup([(1,2,3),(2,3,4)])
sage: Gfail is G2
False
sage: Gfail == G2
True

The quick fix would be making PermutationGroup always return a UniqueRepresentation subclass as my guess is it comes from this:

sage: R2 = GroupAlgebra(G2, QQ)
sage: R2 is Rfail
True

Now we could make the group algebra code only be unique if the input group is unique, but that would require some major modifications to how things are implemented I think.

I don't think we want PermutationGroup_generic to be a subclass of UniqueRepresentation because of the equality check. Could making it a subclass of CachedRepresentation maybe fix this problem? Although I don't exactly understand why the code is failing in the first place...

[tscrim]

Description changed:

--- 
+++ 
@@ -13,8 +13,103 @@

Rfail.center_basis() +--------------------------------------------------------------------------- +RuntimeError Traceback (most recent call last) + in +----> 1 Rfail.center_basis() + +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.call (build/cythonized/sage/misc/cachefunc.c:13041)()

• 2308 if self.cache is None:
• 2309 f = self.f +-> 2310 self.cache = f(self._instance)
• 2311 return self.cache
• 2312

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/categories/group_algebras.py in center_basis(self)

• 204 - :meth:Monoids.Algebras.ElementMethods.is_central
• 205 """ +--> 206 return tuple([self.sum_of_monomials(conj) for conj in
• 207 self.basis().keys().conjugacy_classes()])
• 208

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/categories/group_algebras.py in (.0)

• 204 - :meth:Monoids.Algebras.ElementMethods.is_central
• 205 """ +--> 206 return tuple([self.sum_of_monomials(conj) for conj in
• 207 self.basis().keys().conjugacy_classes()])
• 208

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/categories/poor_man_map.py in call(self, *args)

• 258 """
• 259 for function in reversed(self._functions): +--> 260 args = [function(*args)]
• 261 return args[0]
• 262

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/combinat/free_module.py in _sum_of_monomials(self, indices)

• 1041 """
• 1042 R = self.base_ring() +-> 1043 ret = blas.sum_of_monomials(indices, R.one())
• 1044 return self.element_class(self, ret)
• 1045

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/data_structures/blas_dict.pyx in sage.data_structures.blas_dict.sum_of_monomials (build/cythonized/sage/data_structures/blas_dict.c:3796)()

• 356 return remove_zeros(result)
• 357 +--> 358 cpdef dict sum_of_monomials(monomials, scalar):
• 359 r"""
• 360 Return the pointwise addition of monomials.

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/data_structures/blas_dict.pyx in sage.data_structures.blas_dict.sum_of_monomials (build/cythonized/sage/data_structures/blas_dict.c:3614)()

• 377 cdef dict result = {}
• 378 cdef object m +--> 379 for m in monomials:
• 380 if m in result:
• 381 result[m] += scalar

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/sets/recursively_enumerated_set.pyx in breadth_first_search_iterator (build/cythonized/sage/sets/recursively_enumerated_set.c:6352)()

• 835 for x in current_level:
• 836 for y in self.successors(x): +--> 837 if y is None or y in known:
• 838 continue
• 839 yield y

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/structure/element.pyx in sage.structure.element.Element.richcmp (build/cythonized/sage/structure/element.c:10513)()

• 1110 return (self).richcmp(other, op)
• 1111 else: +-> 1112 return coercion_model.richcmp(self, other, op)
• 1113
• 1114 cpdef richcmp(left, right, int op):

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.richcmp (build/cythonized/sage/structure/coerce.c:20599)()

• 1971 # Coerce to a common parent
• 1972 try: +-> 1973 x, y = self.canonical_coercion(x, y)
• 1974 except (TypeError, NotImplementedError):
• 1975 pass

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.canonical_coercion (build/cythonized/sage/structure/coerce.c:12619)()

• 1330 if x_elt._parent is y_elt._parent:
• 1331 return x_elt,y_elt +-> 1332 self._coercion_error(x, x_map, x_elt, y, y_map, y_elt)
• 1333
• 1334 cdef bint x_numeric = isinstance(x, (int, long, float, complex))

• +~/sage/local/var/lib/sage/venv-python3.10/lib/python3.10/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel._coercion_error (build/cythonized/sage/structure/coerce.c:21354)()

• 2029 <class 'str'> 'g'
• 2030 """ +-> 2031 raise RuntimeError("""There is a bug in the coercion code in Sage.
• 2032 Both x (=%r) and y (=%r) are supposed to have identical parents but they don't.
• 2033 In fact, x has parent '%s'

• +RuntimeError: There is a bug in the coercion code in Sage. +Both x (=()) and y (=()) are supposed to have identical parents but they don't. +In fact, x has parent 'Permutation Group with generators [(2,3,4), (1,2,3)]' +whereas y has parent 'Permutation Group with generators [(2,3,4), (1,2,3)]' +Original elements () (parent Permutation Group with generators [(2,3,4), (1,2,3)]) and () (parent Permutation Group with generators [(2,3,4), (1,2,3)]) and maps +<class 'NoneType'> None +<class 'sage.structure.coerce_maps.DefaultConvertMap_unique'> (map internal to coercion system -- copy before use) +Coercion map:

• From: Permutation Group with generators [(2,3,4), (1,2,3)]
• To: Permutation Group with generators [(2,3,4), (1,2,3)]

• -Pertinent part of error message: -RuntimeError: There is a bug in the coercion code in Sage.

[videlec]

comment:2

Possibly related to

sage: p1 = PermutationGroup([(1,2),(1,2,3,4)]).an_element()
sage: p2 = SymmetricGroup(4).an_element()
sage: parent(coercion_model.canonical_coercion(p1, p2)[0])
Permutation Group with generators [(1,2), (1,2,3,4)]
sage: parent(coercion_model.canonical_coercion(p2, p1)[0])
Symmetric group of order 4! as a permutation group

See #28544

[tscrim]

comment:3

Quite likely. Non-unique-representation parents make coercion difficult, and from comment:2, likely even CachedRepresentation won't improve the situation. We might have to explicitly convert some elements in the GroupAlgebra code to fix this. It should at least fix the symptom, but that is likely just a hack solution with other issues popping up elsewhere...