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:  sage8.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: 
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) <ipythoninput4bf146b40c359> in <module>() > 1 A.construction() /Applications/SageMath/local/lib/python2.7/sitepackages/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) <ipythoninput50087fe7abde8> in <module>() > 1 matrix(Integer(4), [A.an_element()] * Integer(16)).determinant() /Applications/SageMath/local/lib/python2.7/sitepackages/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/sitepackages/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/sitepackages/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 ** (n1p) 2524 2525 return f /Applications/SageMath/local/lib/python2.7/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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
Authors:  → Markus Wageringel 

Branch:  → u/ghmwageringel/27937 
Commit:  → 8858cdc4415e47997b546c85c1998bf307716579 
Status:  new → needs_review 
comment:2 Changed 4 years ago by
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
Reviewers:  → Vincent Delecroix 

Status:  needs_review → needs_work 
comment:4 Changed 4 years ago by
Commit:  8858cdc4415e47997b546c85c1998bf307716579 → 825966a43cfdbc24f3c5d45d2bef6559b3aadb0a 

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

comment:6 Changed 4 years ago by
Status:  needs_work → needs_review 

comment:7 Changed 4 years ago by
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
Commit:  825966a43cfdbc24f3c5d45d2bef6559b3aadb0a → 5b97d033101ef58e190943f1b590444852d1c316 

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

comment:9 Changed 3 years ago by
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
Milestone:  sage8.8 → sage8.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:12 Changed 3 years ago by
Authors:  Markus Wageringel → Markus Wageringel, Frédéric Chapoton 

Status:  needs_review → positive_review 
comment:13 Changed 3 years ago by
Branch:  u/ghmwageringel/27937 → 5b97d033101ef58e190943f1b590444852d1c316 

Resolution:  → fixed 
Status:  positive_review → closed 
It seems more appropriate to return an
AlgebraFunctor
instead of aGroupAlgebraFunctor
, in this case, as we are not dealing with groups.New commits:
trac #27937. fix functorial construction of monoid algebras