Fix for functorial construction of monoid algebras

[mwageringel]

The GroupAlgebraFunctor is general enough to support algebras over structures that are not groups, such as monoids, so the following should either return None or a functorial construction.

sage: A = FreeAbelianMonoid('x,y').algebra(QQ)
sage: A.construction()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-4-bf146b40c359> in <module>()
----> 1 A.construction()

/Applications/SageMath/local/lib/python2.7/site-packages/sage/categories/sets_cat.pyc in construction(self)
   2465                 """
   2466                 from sage.categories.algebra_functor import GroupAlgebraFunctor
-> 2467                 return GroupAlgebraFunctor(self.group()), self.base_ring()
   2468
   2469             def _repr_(self):

...

AttributeError: 'GroupAlgebra_class_with_category' object has no attribute 'group'

In the case of groups this works, but for monoids it does not since A.group() is not defined. This ticket fixes that by calling A.basis().keys() instead, which is the default implementation of group() in sage.categories.group_algebras.

---

The above issue also causes this seemingly unrelated problem for computing 4×4 determinants over A.

sage: matrix(4, [A.an_element()] * 16).determinant()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-5-0087fe7abde8> in <module>()
----> 1 matrix(Integer(4), [A.an_element()] * Integer(16)).determinant()

/Applications/SageMath/local/lib/python2.7/site-packages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix.determinant (build/cythonized/sage/matrix/matrix2.c:15477)()
   1701         var = 'A0123456789' if is_SymbolicExpressionRing(R) else 'x'
   1702         try:
-> 1703             c = self.charpoly(var, algorithm="df")[0]
   1704         except ValueError:
   1705             # Division free algorithm not supported, so we use whatever the default algorithm is.

/Applications/SageMath/local/lib/python2.7/site-packages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix.charpoly (build/cythonized/sage/matrix/matrix2.c:20090)()
   2360                 f = self._charpoly_hessenberg(var)
   2361             else:
-> 2362                 f = self._charpoly_df(var)
   2363
   2364         # Cache the result, and return it.

/Applications/SageMath/local/lib/python2.7/site-packages/sage/matrix/matrix2.pyx in sage.matrix.matrix2.Matrix._charpoly_df (build/cythonized/sage/matrix/matrix2.c:21592)()
   2521         f = X ** n
   2522         for p in xrange(n):
-> 2523             f = f + F[p] * X ** (n-1-p)
   2524
   2525         return f

/Applications/SageMath/local/lib/python2.7/site-packages/sage/structure/element.pyx in sage.structure.element.Element.__mul__ (build/cythonized/sage/structure/element.c:12016)()
   1517             return (<Element>left)._mul_(right)
   1518         if BOTH_ARE_ELEMENT(cl):
-> 1519             return coercion_model.bin_op(left, right, mul)
   1520
   1521         cdef long value

/Applications/SageMath/local/lib/python2.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.bin_op (build/cythonized/sage/structure/coerce.c:9927)()
   1151             action = self._action_maps.get(xp, yp, op)
   1152         except KeyError:
-> 1153             action = self.get_action(xp, yp, op, x, y)
   1154         if action is not None:
   1155             if (<Action>action)._is_left:

/Applications/SageMath/local/lib/python2.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.get_action (build/cythonized/sage/structure/coerce.c:16714)()
   1679         except KeyError:
   1680             pass
-> 1681         action = self.discover_action(R, S, op, r, s)
   1682         action = self.verify_action(action, R, S, op)
   1683         self._action_maps.set(R, S, op, action)

/Applications/SageMath/local/lib/python2.7/site-packages/sage/structure/coerce.pyx in sage.structure.coerce.CoercionModel.discover_action (build/cythonized/sage/structure/coerce.c:18132)()
   1810         """
   1811         if isinstance(R, Parent):
-> 1812             action = (<Parent>R).get_action(S, op, True, r, s)
   1813             if action is not None:
   1814                 return action

/Applications/SageMath/local/lib/python2.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.get_action (build/cythonized/sage/structure/parent.c:19985)()
   2482         action = self._get_action_(S, op, self_on_left)
   2483         if action is None:
-> 2484             action = self.discover_action(S, op, self_on_left, self_el, S_el)
   2485
   2486         if action is not None:

/Applications/SageMath/local/lib/python2.7/site-packages/sage/structure/parent.pyx in sage.structure.parent.Parent.discover_action (build/cythonized/sage/structure/parent.c:21272)()
   2587                 # detect actions defined by _rmul_, _lmul_, _act_on_, and _acted_upon_ methods
   2588                 from .coerce_actions import detect_element_action
-> 2589                 action = detect_element_action(self, S, self_on_left, self_el, S_el)
   2590                 if action is not None:
   2591                     return action

/Applications/SageMath/local/lib/python2.7/site-packages/sage/structure/coerce_actions.pyx in sage.structure.coerce_actions.detect_element_action (build/cythonized/sage/structure/coerce_actions.c:5005)()
    213         # Elements defining _lmul_ and _rmul_
    214         try:
--> 215             return (RightModuleAction if X_on_left else LeftModuleAction)(Y, X, y, x)
    216         except CoercionException as msg:
    217             _record_exception()

/Applications/SageMath/local/lib/python2.7/site-packages/sage/structure/coerce_actions.pyx in sage.structure.coerce_actions.ModuleAction.__init__ (build/cythonized/sage/structure/coerce_actions.c:5882)()
    322                 from sage.categories.pushout import pushout
    323                 # this may raise a type error, which we propagate
--> 324                 self.extended_base = pushout(G, S)
    325                 # make sure the pushout actually gave a correct base extension of S
    326                 if self.extended_base.base() != pushout(G, base):

/Applications/SageMath/local/lib/python2.7/site-packages/sage/categories/pushout.pyc in pushout(R, S)
   3927         S = type_to_parent(S)
   3928
-> 3929     R_tower = construction_tower(R)
   3930     S_tower = construction_tower(S)
   3931     Rs = [c[1] for c in R_tower]

/Applications/SageMath/local/lib/python2.7/site-packages/sage/categories/pushout.pyc in construction_tower(R)
   4272         if not isinstance(R, Parent):
   4273             break
-> 4274         c = R.construction()
   4275     return tower
   4276

/Applications/SageMath/local/lib/python2.7/site-packages/sage/categories/sets_cat.pyc in construction(self)
   2465                 """
   2466                 from sage.categories.algebra_functor import GroupAlgebraFunctor
-> 2467                 return GroupAlgebraFunctor(self.group()), self.base_ring()
   2468
   2469             def _repr_(self):

...

AttributeError: 'GroupAlgebra_class_with_category' object has no attribute 'group'

For smaller matrices this works, as determinants are computed explicitly, but for 4×4 matrices and larger, this involves the computation of the characteristic polynomial. However, _charpoly_df is implemented in a way that requires quite complicated coercions, apparently. Therefore, this ticket also adjusts the implementation of _charpoly_df to avoid this, by constructing the polynomial from the list of its coefficients.

Component: categories

Keywords: algebra

Author: Markus Wageringel, Frédéric Chapoton

Branch/Commit: 5b97d03

Reviewer: Vincent Delecroix

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

[mwageringel]

Commit: 8858cdc

[mwageringel]

Branch: u/gh-mwageringel/27937

[mwageringel]

Author: Markus Wageringel

[mwageringel]

comment:1

It seems more appropriate to return an AlgebraFunctor instead of a GroupAlgebraFunctor, in this case, as we are not dealing with groups.

---

New commits:

8858cdc

trac #27937. fix functorial construction of monoid algebras

[videlec]

comment:2

Please replace [R.zero() for i in xrange(n)] by [R.zero()] * n. The second version avoids the usage of xrange (we should avoided as much as possible because of Python3) and is also more efficient.

[videlec]

Reviewer: Vincent Delecroix

[sagetrac-git]

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

825966a

trac #27937. fix functorial construction of monoid algebras

[sagetrac-git]

Changed commit from 8858cdc to 825966a

[mwageringel]

comment:5

I see. Thank you for the feedback. I changed it.

[videlec]

comment:7

In your example, there is no need to check that .group() does raise an error. It would also be good to check the reconstruction

sage: F, arg = A.construction()
sage: F(arg) is A
True

[sagetrac-git]

Changed commit from 825966a to 5b97d03

[sagetrac-git]

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

5b97d03

trac #27937. fix functorial construction of monoid algebras

[mwageringel]

comment:9

Thanks, I applied the suggested changes. I kept the output of .construction() though to distinguish between the two different functors.

[embray]

comment:10

Moving tickets from the Sage 8.8 milestone that have been actively worked on in the last six months to the next release milestone (optimistically).

[fchapoton]

comment:11

Looks good to me. Vincent, do you approve ?

[videlec]

Changed author from Markus Wageringel to Markus Wageringel, Frédéric Chapoton

[videlec]

comment:12

Replying to @fchapoton:

Looks good to me. Vincent, do you approve ?

Sorry. It got off my radar.

[vbraun]

Changed branch from u/gh-mwageringel/27937 to 5b97d03