Opened 4 years ago

Closed 3 years ago

#27937 closed defect (fixed)

Fix for functorial construction of monoid algebras

Reported by: Markus Wageringel Owned by:
Priority: major Milestone: sage-8.9
Component: categories Keywords: coercion, algebra
Cc: Merged in:
Authors: Markus Wageringel, Frédéric Chapoton Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: 5b97d03 (Commits, GitHub, GitLab) Commit: 5b97d033101ef58e190943f1b590444852d1c316
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (13)

comment:1 Changed 4 years ago by Markus Wageringel

Authors: Markus Wageringel
Branch: u/gh-mwageringel/27937
Commit: 8858cdc4415e47997b546c85c1998bf307716579
Status: newneeds_review

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


New commits:

8858cdctrac #27937. fix functorial construction of monoid algebras

comment:2 Changed 4 years ago by Vincent Delecroix

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.

comment:3 Changed 4 years ago by Vincent Delecroix

Reviewers: Vincent Delecroix
Status: needs_reviewneeds_work

comment:4 Changed 4 years ago by git

Commit: 8858cdc4415e47997b546c85c1998bf307716579825966a43cfdbc24f3c5d45d2bef6559b3aadb0a

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

825966atrac #27937. fix functorial construction of monoid algebras

comment:5 Changed 4 years ago by Markus Wageringel

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

comment:6 Changed 4 years ago by Markus Wageringel

Status: needs_workneeds_review

comment:7 Changed 4 years ago by Vincent Delecroix

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

comment:8 Changed 3 years ago by git

Commit: 825966a43cfdbc24f3c5d45d2bef6559b3aadb0a5b97d033101ef58e190943f1b590444852d1c316

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

5b97d03trac #27937. fix functorial construction of monoid algebras

comment:9 Changed 3 years ago by Markus Wageringel

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

comment:10 Changed 3 years ago by Erik Bray

Milestone: sage-8.8sage-8.9

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

comment:11 Changed 3 years ago by Frédéric Chapoton

Looks good to me. Vincent, do you approve ?

comment:12 in reply to:  11 Changed 3 years ago by Vincent Delecroix

Authors: Markus WageringelMarkus Wageringel, Frédéric Chapoton
Status: needs_reviewpositive_review

Replying to chapoton:

Looks good to me. Vincent, do you approve ?

Sorry. It got off my radar.

comment:13 Changed 3 years ago by Volker Braun

Branch: u/gh-mwageringel/279375b97d033101ef58e190943f1b590444852d1c316
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.