Group algebra bug

41 views

Skip to first unread message

Trevor Karn

unread,

Aug 6, 2022, 2:53:03 PM8/6/22

to sage-devel

The following bug was reported on sage-support, which I was able to reproduce on 9.7.beta7.

sage: H = PermutationGroup([[(1,2), (3,4)], [(5,6,7),(12,14,18)]])
sage: kH = H.algebra(GF(2))
sage: H.gens()
((5,6,7)(12,14,18), (1,2)(3,4))
sage: a, b = H.gens()
sage: x = kH(a) + kH(b) + kH.one(); x
(5,6,7)(12,14,18) + (1,2)(3,4) + ()
sage: x*x
Traceback (most recent call last):
...

RuntimeError: There is a bug in the coercion code in Sage.
Both x (=()) and y (=(5,6,7)(12,14,18)) are supposed to have identical parents but they don't.
In fact, x has parent 'Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]'
whereas y has parent 'Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]'
Original elements () (parent Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]) and (5,6,7)(12,14,18) (parent Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]) 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 [(5,6,7)(12,14,18), (1,2)(3,4)]
To: Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]

I'm confused about why this is happening because

sage: kH(a).parent()
Algebra of Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)] over Finite Field of size 2
sage: kH.one().parent()
Algebra of Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)] over Finite Field of size 2
sage: kH(a).parent() is kH.one().parent()
True

which I would think should mean that the condition on line 1323 of sage/src/sage/structure/coerce.pyx that the parents are the same should be tripped, but for some reason, it is not. I printed the hash of the parents right before the bug (added it in between lines 1322 and 1323) and they have the same hash (547464660303730434), so I am surprised that they are not considered the same. They are however recognized to be equal, and so the elif statment checking if they are equal (on line 1327) is triggered, but then the coercion of y_elt to parent(x_elt) on line 1329 seems to fail, so that the parent comparison on 1330 still fails, kicking it out to the coercion error.

I'm unsure how to fix this but am willing to do the legwork to fix it if anyone can explain the problem.

Opening https://trac.sagemath.org/ticket/34292.

Full traceback:

sage: H = PermutationGroup([[(1,2), (3,4)], [(5,6,7),(12,14,18)]])

sage: kH = H.algebra(GF(2))

sage: H.gens()

((5,6,7)(12,14,18), (1,2)(3,4))

sage: a, b = H.gens()

sage: x = kH(a) + kH(b) + kH.one(); x

(5,6,7)(12,14,18) + (1,2)(3,4) + ()

sage: x*x

---------------------------------------------------------------------------

RuntimeError Traceback (most recent call last)

Input In [7], in <cell line: 1>()

----> 1 x*x

File ~/Applications/sage/src/sage/structure/element.pyx:1514, in sage.structure.element.Element.__mul__()

1512 cdef int cl = classify_elements(left, right)

1513 if HAVE_SAME_PARENT(cl):

-> 1514 return (<Element>left)._mul_(right)

1515 if BOTH_ARE_ELEMENT(cl):

1516 return coercion_model.bin_op(left, right, mul)

File ~/Applications/sage/src/sage/structure/element.pyx:1560, in sage.structure.element.Element._mul_()

1558 raise bin_op_exception('*', self, other)

1559 else:

-> 1560 return python_op(other)

1561

1562 cdef _mul_long(self, long n):

File ~/Applications/sage/src/sage/categories/coercion_methods.pyx:53, in sage.categories.coercion_methods._mul_parent()

51 True

52 """

---> 53 return (<Element>self)._parent.product(self, other)

File ~/Applications/sage/src/sage/categories/magmatic_algebras.py:215, in MagmaticAlgebras.WithBasis.ParentMethods._product_from_product_on_basis_multiply(self, left, right)

201 def _product_from_product_on_basis_multiply( self, left, right ):

202 r"""

203 Compute the product of two elements by extending

204 bilinearly the method :meth:`product_on_basis`.

(...)

213

214 """

--> 215 return self.linear_combination((self.product_on_basis(mon_left, mon_right), coeff_left * coeff_right )

216 for (mon_left, coeff_left) in left.monomial_coefficients().items()

217 for (mon_right, coeff_right) in right.monomial_coefficients().items() )

File ~/Applications/sage/src/sage/combinat/free_module.py:969, in CombinatorialFreeModule.linear_combination(self, iter_of_elements_coeff, factor_on_left)

945 def linear_combination(self, iter_of_elements_coeff, factor_on_left=True):

946 r"""

947 Return the linear combination `\lambda_1 v_1 + \cdots +

948 \lambda_k v_k` (resp. the linear combination `v_1 \lambda_1 +

(...)

967 20*B[1] + 20*B[2]

968 """

--> 969 return self._from_dict(blas.linear_combination(((element._monomial_coefficients, coeff)

970 for element, coeff in iter_of_elements_coeff),

971 factor_on_left=factor_on_left),

972 remove_zeros=False)

File ~/Applications/sage/src/sage/data_structures/blas_dict.pyx:313, in sage.data_structures.blas_dict.linear_combination()

311 return remove_zeros(result)

312

--> 313 cpdef dict linear_combination(dict_factor_iter, bint factor_on_left=True):

314 r"""

315 Return the pointwise addition of dictionaries with coefficients.

File ~/Applications/sage/src/sage/data_structures/blas_dict.pyx:348, in sage.data_structures.blas_dict.linear_combination()

346 cdef dict D

347

--> 348 for D, a in dict_factor_iter:

349 if not a: # We multiply by 0, so nothing to do

350 continue

File ~/Applications/sage/src/sage/combinat/free_module.py:969, in <genexpr>(.0)

945 def linear_combination(self, iter_of_elements_coeff, factor_on_left=True):

946 r"""

947 Return the linear combination `\lambda_1 v_1 + \cdots +

948 \lambda_k v_k` (resp. the linear combination `v_1 \lambda_1 +

(...)

967 20*B[1] + 20*B[2]

968 """

--> 969 return self._from_dict(blas.linear_combination(((element._monomial_coefficients, coeff)

970 for element, coeff in iter_of_elements_coeff),

971 factor_on_left=factor_on_left),

972 remove_zeros=False)

File ~/Applications/sage/src/sage/categories/magmatic_algebras.py:215, in <genexpr>(.0)

201 def _product_from_product_on_basis_multiply( self, left, right ):

202 r"""

203 Compute the product of two elements by extending

204 bilinearly the method :meth:`product_on_basis`.

(...)

213

214 """

--> 215 return self.linear_combination((self.product_on_basis(mon_left, mon_right), coeff_left * coeff_right )

216 for (mon_left, coeff_left) in left.monomial_coefficients().items()

217 for (mon_right, coeff_right) in right.monomial_coefficients().items() )

File ~/Applications/sage/src/sage/categories/semigroups.py:957, in Semigroups.Algebras.ParentMethods.product_on_basis(self, g1, g2)

939 def product_on_basis(self, g1, g2):

940 r"""

941 Product, on basis elements, as per

942 :meth:`MagmaticAlgebras.WithBasis.ParentMethods.product_on_basis()

(...)

955 B['ab'] + B['bdc']

956 """

--> 957 return self.monomial(g1 * g2)

File ~/Applications/sage/src/sage/groups/perm_gps/permgroup_element.pyx:1295, in sage.groups.perm_gps.permgroup_element.PermutationGroupElement.__mul__()

1293 return prod

1294

-> 1295 return coercion_model.bin_op(left, right, operator.mul)

1296

1297 cpdef _mul_(left, _right):

File ~/Applications/sage/src/sage/structure/coerce.pyx:1200, in sage.structure.coerce.CoercionModel.bin_op()

1198 # Now coerce to a common parent and do the operation there

1199 try:

-> 1200 xy = self.canonical_coercion(x, y)

1201 except TypeError:

1202 self._record_exception()

File ~/Applications/sage/src/sage/structure/coerce.pyx:1332, in sage.structure.coerce.CoercionModel.canonical_coercion()

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

File ~/Applications/sage/src/sage/structure/coerce.pyx:2031, in sage.structure.coerce.CoercionModel._coercion_error()

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 (=(5,6,7)(12,14,18)) are supposed to have identical parents but they don't.

In fact, x has parent 'Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]'

whereas y has parent 'Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]'

Original elements () (parent Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]) and (5,6,7)(12,14,18) (parent Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]) 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 [(5,6,7)(12,14,18), (1,2)(3,4)]

To: Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]

Trevor Karn

unread,

Aug 6, 2022, 2:57:59 PM8/6/22

to sage-devel

Sorry of course the parent of kH(a) and kH.one() are the same. We do see that the parents of the indexing elements are different despite being mathematically the same:

sage: a.parent()

sage: list(kH.one().monomial_coefficients())[0].parent()

Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]
Permutation Group with generators [(5,6,7)(12,14,18), (1,2)(3,4)]

sage: list(kH.one().monomial_coefficients())[0].parent() is a.parent()
False

Travis Scrimshaw

unread,

Aug 7, 2022, 3:00:23 AM8/7/22

to sage-devel

I posted on the ticket a long debug of the issue, which comes down to a subtlety with making copies of PermutationGroup_generic and its __dict__.

Best,

Travis

Reply all

Reply to author

Forward

0 new messages