Opened 8 years ago
Closed 6 years ago
#18700 closed enhancement (fixed)
Have GroupAlgebra(Q, R) and G.algebra(R) return the same standard class for group algebras
Reported by:  tscrim  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage8.0 
Component:  coercion  Keywords:  group algebras 
Cc:  sagecombinat, aschilling, nthiery, bsalisbury1, chapoton  Merged in:  
Authors:  Travis Scrimshaw, Nicolas M. Thiéry  Reviewers:  Ben Salisbury 
Report Upstream:  N/A  Work issues:  
Branch:  3160e26 (Commits, GitHub, GitLab)  Commit:  3160e26eb25eb09fc7164f020783da2122b18ffd 
Dependencies:  #23000 #23211  Stopgaps: 
Description (last modified by )
Consider the following situation:
sage: P = RootSystem(['A',2,1]).weight_lattice() sage: W = RootSystem(['A',2,1]).weight_space() sage: W.has_coerce_map_from(P) True sage: PA = P.algebra(QQ) sage: WA = W.algebra(QQ) sage: WA.has_coerce_map_from(PA) False
The last line should be True
. This comes from the fact that GroupAlgebra
implements some extra coercion logic and G.algebra(R)
does not return an instance of this class.
To remedy this, we lift a good portion of the GroupAlgebra
code to the appropriate categories, where we impose the restriction that a (Semi)Group.Algebra
must have a basis indexed by elements of the (semi)group, and have all group algebras redirect to the now (lightweight) class GroupAlgebra_class
in order to implement coercions.
Change History (84)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
Also as a little side bug:
sage: P.algebra(QQ) Group algebra of the Weight lattice of the Root system of type ['A', 2, 1] over Rational Field sage: _.category() Category of root lattice realizations over Integer Rin algebras over Rational Field
Notice the missing g
, same thing for W
(except there it's ...Fiel algebras over...
).
comment:3 Changed 6 years ago by
Branch:  → public/groups/standardize_group_algebras18700 

Cc:  chapoton added 
Commit:  → 5e9420816a245339735f51d0958b06eed509cbd2 
Milestone:  sage6.8 → sage8.0 
Status:  new → needs_review 
This goes through and redirects group algebra construction through GroupAlgebra
, as well as cleans up how the categories are constructed.
New commits:
5e94208  Standardizing group algebras through GroupAlgebra.

comment:4 Changed 6 years ago by
Hi Travis,
There are doctest failures in a lot of difference places. For example:
 sage t long src/sage/combinat/root_system/non_symmetric_macdonald_polynomials.py # 94 doctests failed sage t long src/sage/plot/plot.py # 1 doctest failed sage t long src/sage/plot/graphics.py # 2 doctests failed sage t long src/sage/misc/sagedoc.py # 3 doctests failed sage t long src/sage/combinat/crystals/littelmann_path.py # 6 doctests failed sage t long src/sage/combinat/rigged_configurations/rigged_configurations.py # 13 doctests failed sage t long src/sage/combinat/root_system/root_lattice_realization_algebras.py # 89 doctests failed sage t long src/sage/combinat/posets/posets.py # 1 doctest failed sage t long src/sage/combinat/root_system/hecke_algebra_representation.py # 33 doctests failed sage t long src/sage/categories/finite_dimensional_algebras_with_basis.py # 2 doctests failed sage t long src/sage/combinat/crystals/tensor_product.py # 5 doctests failed sage t long src/sage/repl/rich_output/pretty_print.py # 1 doctest failed sage t long src/doc/en/thematic_tutorials/lie/affine_finite_crystals.rst # 1 doctest failed sage t long src/sage/modules/with_basis/representation.py # 13 doctests failed sage t long src/sage/categories/sets_cat.py # 4 doctests failed sage t long src/sage/algebras/lie_algebras/lie_algebra.py # 2 doctests failed sage t long src/sage/categories/semisimple_algebras.py # 1 doctest failed 
So many, in fact, that I'm wondering if I did something wrong! Did you get this same failures before you pushed the latest merge to the branch?
comment:5 Changed 6 years ago by
Those are probably trivial doctest failures because of the change in the how the group algebra elements are printed and I didn't test as well as I thought. I will fix them shortly.
comment:6 Changed 6 years ago by
Commit:  5e9420816a245339735f51d0958b06eed509cbd2 → 39800cc553693c20e460f16f009a185f2baeebdf 

Branch pushed to git repo; I updated commit sha1. New commits:
39800cc  Fixing doctests and some conversion behavior changes.

comment:7 Changed 6 years ago by
Summary:  Group algebras should have a coercion inherited from coercions of the underlying groups → Use GroupAlgebra as the standard class for group algebras 

This should fix all of the doctest failures that were introduced on this ticket. I did a little bit of a hack for algebras of a module with a basis to wrap them as B[x + y]
. Some of the other doctest failures I get on develop
(in particular, the failure in posets.py
) or cannot reproduce (e.g., the ones in plot).
comment:8 Changed 6 years ago by
Still getting a doctest failure...
sage t src/sage/algebras/group_algebra.py ********************************************************************** File "src/sage/algebras/group_algebra.py", line 696, in sage.algebras.group_algebra.GroupAlgebra._element_constructor_ Failed example: OG(2) Exception raised: Traceback (most recent call last): File "/Users/Ben/sagegit/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 509, in _run self.compile_and_execute(example, compiler, test.globs) File "/Users/Ben/sagegit/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 872, in compile_and_execute exec(compiled, globs) File "<doctest sage.algebras.group_algebra.GroupAlgebra._element_constructor_[11]>", line 1, in <module> OG(Integer(2)) File "sage/structure/parent.pyx", line 941, in sage.structure.parent.Parent.__call__ (/Users/Ben/sagegit/src/build/cythonized/sage/structure/parent.c:9839) return mor._call_(x) File "sage/structure/coerce_maps.pyx", line 110, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (/Users/Ben/sagegit/src/build/cythonized/sage/structure/coerce_maps.c:4895) raise File "sage/structure/coerce_maps.pyx", line 105, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (/Users/Ben/sagegit/src/build/cythonized/sage/structure/coerce_maps.c:4762) return C._element_constructor(x) File "/Users/Ben/sagegit/local/lib/python2.7/sitepackages/sage/algebras/group_algebra.py", line 720, in _element_constructor_ raise TypeError("do not know how to make x (= %s) an element of %s"%(x, self)) TypeError: do not know how to make x (= 2) an element of Group algebra of General Linear Group of degree 2 over Finite Field of size 7 over Order in Number Field in sqrt5 with defining polynomial x^2  5 ********************************************************************** 1 item had failures: 1 of 16 in sage.algebras.group_algebra.GroupAlgebra._element_constructor_ [132 tests, 1 failure, 6.13 s]
comment:9 Changed 6 years ago by
Commit:  39800cc553693c20e460f16f009a185f2baeebdf → 2ef2208407ec7edfbe03a8c9980741f25fc2db2a 

Branch pushed to git repo; I updated commit sha1. New commits:
2ef2208  We have a unit, so we can use that in coercion.

comment:11 Changed 6 years ago by
Reviewers:  → Ben Salisbury 

Status:  needs_review → positive_review 
All tests passed on my machine, the html doc builds, and so does the pdf doc. Moreover:
sage: P = RootSystem(['A',2,1]).weight_lattice() sage: W = RootSystem(['A',2,1]).weight_space() sage: W.has_coerce_map_from(P) True sage: PA = P.algebra(QQ) sage: WA = W.algebra(QQ) sage: WA.has_coerce_map_from(PA) True
comment:12 Changed 6 years ago by
Status:  positive_review → needs_review 

Hi,
Sorry for the interuption; I'd like to have a look at this one. If you don't hear from me in the next day, please set it back to positive review.
comment:13 followup: 15 Changed 6 years ago by
Merging GroupAlgebra(G)
and G.algebra()
has been on the pile for such a long while. Thank you so much for working on it!
So far I have always wanted to make GroupAlgebra
as thin as possible by lifting stuff to the categories, and if at all possible get rid of it (up to possibly keeping a trivial redirect GroupAlgebra(G)
> G.algebra()
for user convenience and backward compatibility). This is much more generic/flexible: for example, the feature at hand (lifting coercions from XXX to XXX algebras) is not specific to multiplicative groups, right? We would want to have the same feature for semigroups or additive groups, right?
The current implementation of this ticket tends to go the other way around.
So, the core question is: is there any feature in GroupAlgebra
that really requires a concrete parent? Or could we just lift everything to categories.
Doing it in two steps, first this ticket as is, and then a latter ticket has the inconvenient to change lots of outputs while we may actually want to standardize the outputs the other way around.
What do you think?
Cheers,
comment:14 Changed 6 years ago by
Status:  needs_review → needs_info 

comment:15 followup: 16 Changed 6 years ago by
Replying to nthiery:
So far I have always wanted to make
GroupAlgebra
as thin as possible by lifting stuff to the categories, and if at all possible get rid of it (up to possibly keeping a trivial redirectGroupAlgebra(G)
>G.algebra()
for user convenience and backward compatibility). This is much more generic/flexible: for example, the feature at hand (lifting coercions from XXX to XXX algebras) is not specific to multiplicative groups, right? We would want to have the same feature for semigroups or additive groups, right?
We can definitely lift many methods up to the category. Some of them are even unnecessary, e.g., is_finite
is handled by the FiniteDimensionalModules.extra_super_categories
(or something like that) by adding the Finite
axiom.
The current implementation of this ticket tends to go the other way around.
I would say it is mostly neutral to this. The part that goes the other way is moving the addition of the semisimple axiom check, but I feel the code in Sets.ParentMethods.algebra
is largely a hack and probably should be distributed to the appropriate subcategories. For now, this is a common point of intersection that is cleaner IMO.
So, the core question is: is there any feature in
GroupAlgebra
that really requires a concrete parent? Or could we just lift everything to categories.
While it may not be quite what you mean, I'm considering CFM not as a concrete parent below.
One thing that could be important is the coercion into the basis index set. This would be possible to do in CFM, but it probably is not a feature we want in general because it might cause further ambiguities (e.g., a Qmodule whose basis index set is Z). IMO, we definitely want this for group algebras.
The other coercion that I think we absolutely need a concrete parent is for R[G] > R[H] when there is a coercion G > H. Granted, this is something that could be done at a functor level, but I don't think this is possible currently.
Doing it in two steps, first this ticket as is, and then a latter ticket has the inconvenient to change lots of outputs while we may actually want to standardize the outputs the other way around.
The biggest thing is the default output for group elements, which is something that we can (maybe should) decide here. If we decide to keep this output but go to a generic CFM with category implementation, then we can pass the appropriate parameters during the construction. So the output is an independent question.
I'm in favor of the output of GroupAlgebra
, and in an ideal world, it would check the repr atomicness of the basis keys. However, this is not done properly for a number of groups and would likely be ineffective. Actually, we probably should lift element_ascii_art
of _repr_options
from the basis keys in CFM (separate ticket).
comment:16 followup: 17 Changed 6 years ago by
Replying to tscrim:
We can definitely lift many methods up to the category. Some of them are even unnecessary, e.g.,
is_finite
is handled by theFiniteDimensionalModules.extra_super_categories
(or something like that) by adding theFinite
axiom.
Ok; that was my impression too. Glad this is confirmed by someone who actually manipulated the code recently :)
I would say it is mostly neutral to this.
I mostly meant: it increases the usage of GroupAlgebra? rather than decreasing it.
The part that goes the other way is moving the addition of the semisimple axiom check, but I feel the code in
Sets.ParentMethods.algebra
is largely a hack and probably should be distributed to the appropriate subcategories.
Agreed! For this use case and others, I have been wishing for a hook in the category infrastructure enabling a category C to inspect parent upon their initalization and provide additional categories they should be endowed with.
Maybe we don't actually need new infrastructure, and could just use init_extra and _refine_category():
def Groups.Finite.Algebras.ParentMethods?.init_extra(self)
G = ... R = ... if ... non modular ...:
self._refine_category(...SemiSimple?())
Bearing that in mind, we may not want to move the code to an intermediate spot when it's plausibly going to move again later.
While it may not be quite what you mean
Sorry for the ambiguity. Let me try to clarify:
 Indeed we don't want a coercion F > R.F for a general CFM R.F. Most likely we don't want a conversion either.
 For a group algebra, the conversion G > R.G indeed sounds reasonable. I am unsure at this stage about a coercion; in such doubt my usual approach is to not put a coercion in such a case; later it's harder to remove a coercion than add one.
We don't need to have a concrete class GroupAlgebra? for this. Such a coercion could be declared in
Groups.Algebra.ParentMethods.__init__extra
. Presumably we could generalize it toMagmas.Unital.ParentMethods.__init_extra
and its additive equivalent.
 The lifting of a coercion G> H to R[G] > R[H] for group algebras
looks reasonable indeed. Wouldn't be enough to move the
construction
method toGroups.ParentMethods
, and update the functor to callG.algebra(R)
rather thanGroupAlgebra(G,R)
? (I haven't tried).
This could actually be lifted to
Magmas.ParentMethods
and its additive counterpart.
With that, the concrete class "GroupAlgebra?" could be replaced by a
simple alias GroupAlgebra(G,R)
> G.algebra(R)
, right?
The biggest thing is the default output for group elements, which is something that we can (maybe should) decide here.
+1
If we decide to keep this output but go to a generic CFM with category implementation, then we can pass the appropriate parameters during the construction. So the output is an independent question.
+1. This could be done in Magmas.Algebras.initextra_ with set_options. Or we could overwrite the _repr methods in MagmaAlgebra?.ElementMethods?.
I'm in favor of the output of
GroupAlgebra
I agree that the repr of GroupAlgebra? is nicely concise and close to usual math notations; so that could be a good option.
Opinions anyone? Are there are cases where there could be ambiguity and we would want something slightly more verbose?
and in an ideal world, it would check the repr atomicness of the basis keys.
Not sure what you mean, but that's fine :)
comment:17 followup: 18 Changed 6 years ago by
Replying to nthiery:
Replying to tscrim:
I would say it is mostly neutral to this.
I mostly meant: it increases the usage of GroupAlgebra? rather than decreasing it.
Well, I am not sure we are going to be able to escape the coercion issue. At least for now, because GroupAlgebra
will be a small extra layer over CFM and there could be other thorny issues with getting the functionality we'd want, I think we should utilize GroupAlgebra
for now.
The part that goes the other way is moving the addition of the semisimple axiom check, but I feel the code in
Sets.ParentMethods.algebra
is largely a hack and probably should be distributed to the appropriate subcategories.Agreed! For this use case and others, I have been wishing for a hook in the category infrastructure enabling a category C to inspect parent upon their initalization and provide additional categories they should be endowed with.
Maybe we don't actually need new infrastructure, and could just use init_extra and _refine_category():
def Groups.Finite.Algebras.ParentMethods.__init_extra__(self) G = ... R = ... if ... non modular ...: self._refine_category(...SemiSimple())Bearing that in mind, we may not want to move the code to an intermediate spot when it's plausibly going to move again later.
__init_extra__
is run after __init__
, correct? So it would be safe to assume the category has been initialized and _refine_category
is suppose to play nicely in regards to UniqueRepresentation
. So this should work and improve things.
While it may not be quite what you mean
Sorry for the ambiguity. Let me try to clarify:
 Indeed we don't want a coercion F > R.F for a general CFM R.F. Most likely we don't want a conversion either.
 For a group algebra, the conversion G > R.G indeed sounds reasonable. I am unsure at this stage about a coercion; in such doubt my usual approach is to not put a coercion in such a case; later it's harder to remove a coercion than add one.
Well, there is an ambiguity for additive groups for coercions, even if we consider it as an action. However, it would be strange to have notation using the group elements and not having a coercion, likely leading to bug reports. I am strongly in favor of groups having coercion and for additive groups +
being addition of two elements in the algebra.
We don't need to have a concrete class GroupAlgebra? for this. Such a coercion could be declared in
Groups.Algebra.ParentMethods.__init__extra
. Presumably we could generalize it toMagmas.Unital.ParentMethods.__init_extra
and its additive equivalent.
I think there would need to be an assumption that the group elements are the indexing set of the basis, which means we need a concrete class. While this is a very reasonable assumption, it does place a restriction. Also, we are not really getting rid of a concrete class, just splitting it between CFM and the category. I feel like this obfuscates the code for little to no gain.
 The lifting of a coercion G> H to R[G] > R[H] for group algebras looks reasonable indeed. Wouldn't be enough to move the
construction
method toGroups.ParentMethods
, and update the functor to callG.algebra(R)
rather thanGroupAlgebra(G,R)
? (I haven't tried).
I don't know. I would have to experiment. However, I agree that that does sound like a plausible approach.
This could actually be lifted to
Magmas.ParentMethods
and its additive counterpart.With that, the concrete class "GroupAlgebra?" could be replaced by a simple alias
GroupAlgebra(G,R)
>G.algebra(R)
, right?
If we decide to keep this output but go to a generic CFM with category implementation, then we can pass the appropriate parameters during the construction. So the output is an independent question.
+1. This could be done in Magmas.Algebras.initextra_ with set_options. Or we could overwrite the _repr methods in MagmaAlgebra?.ElementMethods?.
That is just getting more complicated and starts having a code smell, with the additional assumption that group algebra elements should be written as sums over the group elements. While it is not implemented yet, we could have a subalgebra of a matrix algebra being a group algebra for a matrix group.
I'm in favor of the output of
GroupAlgebra
I agree that the repr of GroupAlgebra? is nicely concise and close to usual math notations; so that could be a good option.
Opinions anyone? Are there are cases where there could be ambiguity and we would want something slightly more verbose?
and in an ideal world, it would check the repr atomicness of the basis keys.
Not sure what you mean, but that's fine :)
For example, the algebra for the weight lattice, the element La[1] + La[2]
is ambiguous. Is it 1 * (La[1]) + 1*(La[2])
or 1*(La[1]+La[2])
. I hack around this currently by going back to the old notation when the group is in ModulesWithBasis
.
I feel that ideally this would be done by using _repr_options('element_is_atomic')
, but that might be quite the correct hook.
comment:18 Changed 6 years ago by
Replying to tscrim:
Well, I am not sure we are going to be able to escape the coercion issue. At least for now, because
GroupAlgebra
will be a small extra layer over CFM and there could be other thorny issues with getting the functionality we'd want, I think we should utilizeGroupAlgebra
for now.
Ok, let's see.
__init_extra__
is run after__init__
, correct? So it would be safe to assume the category has been initialized
It's run just at the end of Parent.__init__()
. So indeed, the
category should be initalized then.
Well, there is an ambiguity for additive groups for coercions, even if we consider it as an action. However, it would be strange to have notation using the group elements and not having a coercion, likely leading to bug reports. I am strongly in favor of groups having coercion and for additive groups
+
being addition of two elements in the algebra.
Good point. So we absolutely don't want coercion in the additive case. conversion is probably fine. Remains to decide whether we want just conversion or also coercoin for
In any cases, we can just choose between the various options in the
__init_extra__
of Magmas.ParentMethods
and
AdditiveMagmas.ParentMethods
. So no issue here beside deciding what
we want.
We don't need to have a concrete class GroupAlgebra? for this. Such a coercion could be declared in
Groups.Algebra.ParentMethods.__init__extra
. Presumably we could generalize it toMagmas.Unital.ParentMethods.__init_extra
and its additive equivalent.
I think there would need to be an assumption that the group elements are the indexing set of the basis, which means we need a concrete class. While this is a very reasonable assumption, it does place a restriction. Also, we are not really getting rid of a concrete class, just splitting it between CFM and the category. I feel like this obfuscates the code for little to no gain.
In fact the code of Groups.Algebras already makes in a couple places the assumption that the canonical basis is indexed by the group. This is specified semiexplicitly in the documentation:
XXX.Algebras: Return the category of objects constructed as algebras of objects of ``self`` over ``base_ring``.
The important part is "constructed as", the more specific definition of it being given in xxx.algebra().
We can discuss the merit of having this assumption. I believe we definitely need a category for "group algebras over their canonical basis". Arguably it could possibly be useful to also have a more general category for just "group algebras"; and then it's debatable whether Groups.Algebras should be the former or the latter. I would tend to just keep the current assumption for now.
That is just getting more complicated and starts having a code smell, with the additional assumption that group algebra elements should be written as sums over the group elements. While it is not implemented yet, we could have a subalgebra of a matrix algebra being a group algebra for a matrix group.
Does your perspective change with the above precision about what
the category Group.Algebras
is about?
For example, the algebra for the weight lattice, the element `La[1] + La[2]
is ambiguous. Is it
1 * (La[1]) + 1*(La[2])` or1*(La[1]+La[2])
. I hack around this currently by going back to the old notation when the group is inModulesWithBasis
.
I see. We could also get away with it with some "in doubt add
parenthesis" heuristic; E.g. if the string repr of term contains a
+
. Not great, but simple and safe (for output purposes).
I feel that ideally this would be done by using
_repr_options('element_is_atomic')
, but that might be quite the correct hook.
Ok.
comment:19 followups: 22 23 Changed 6 years ago by
Okay, there is a technical limitation to using the __init_extra__
: percolating calls up through the category methods.
I don't quite agree with "constructed as" meaning the basis must be indexed by the group. I also don't think we should enforce that, and only place I currently see that assumption used is the default implementation of group
. I also do not want a category for a single object in a more natural category: it should be a concrete class. Although right now, this is moot (see below).
I've moved the methods that I could up to the category. construction
cannot be lifted because the default in Parent
is to return None
. Similar for is_exact
. So I believe we need a concrete class
So I think at this point, this is the best we are really going to get. We can address some of these issues on some followup tickets.
comment:20 Changed 6 years ago by
Commit:  2ef2208407ec7edfbe03a8c9980741f25fc2db2a → 647264f6107ad29f987821e4a585c36215e49e40 

comment:21 Changed 6 years ago by
Status:  needs_info → needs_review 

comment:22 followup: 26 Changed 6 years ago by
Replying to tscrim:
I don't quite agree with "constructed as" meaning the basis must be indexed by the group. I also don't think we should enforce that, and only place I currently see that assumption used is the default implementation of
group
. I also do not want a category for a single object in a more natural category: it should be a concrete class. Although right now, this is moot (see below).
That's the same with other functorial constructions like cartesian product. It gives you the cartesian product in its canonical representation.
Here are other methods (or to be implemented methods) that use the assumption that the group algebra is represented in its canonical basis:
 default implementation of algebra_generators
 center_basis
 multiplication
 coproduct, antipode, counit,
 stuff about representation theory of monoids
 construction of the Jucys Murphy elements for the symmetric group
Note that those live at different levels (magmas, monoids, groups, specific groups). So if really want to support both "constructed as" and "isomorphic to", a functorial construction and a concrete class won't be enough. We need two functorial constructions.
I've moved the methods that I could up to the category.
Cool, thanks!
construction
cannot be lifted because the default inParent
is toreturn None
.
This is just the usual artifact that for historical reasons, there is
too much stuff in Parent, which prevents categories to provide default
implementations. construction
being a non speedcritical method, I
foresee no obstruction to moving it to Sets (but need to double check
the code first).
Similar for
is_exact
.
This one is a bit more annoying since it's a cpdef method. Worst comes to worst, we could do as for getitem.
So I believe we need a concrete class
Not yet clear :)
comment:23 followup: 25 Changed 6 years ago by
Replying to tscrim:
Okay, there is a technical limitation to using the
__init_extra__
: percolating calls up through the category methods.
Ok. Could you elaborate?
comment:24 Changed 6 years ago by
Fore reference, #11318 is the ticket suggesting to get rid of GroupAlgebra?.
comment:25 followup: 27 Changed 6 years ago by
Replying to nthiery:
Replying to tscrim:
Okay, there is a technical limitation to using the
__init_extra__
: percolating calls up through the category methods.Ok. Could you elaborate?
I could not use super
to make the calls without getting either an infinite recursion or errors from Python. I also think we should not force a direct call to the unital algebra's __init_extra__
in case one of the other base categories ends up having an __init_extra__
.
comment:26 followup: 31 Changed 6 years ago by
Replying to nthiery:
Replying to tscrim:
I don't quite agree with "constructed as" meaning the basis must be indexed by the group. I also don't think we should enforce that, and only place I currently see that assumption used is the default implementation of
group
. I also do not want a category for a single object in a more natural category: it should be a concrete class. Although right now, this is moot (see below).
That's the same with other functorial constructions like cartesian product. It gives you the cartesian product in its canonical representation.
In that case, it creates an instance of a specific concrete class.
Here are other methods (or to be implemented methods) that use the assumption that the group algebra is represented in its canonical basis:
 default implementation of algebra_generators
 center_basis
 multiplication
 coproduct, antipode, counit,
 stuff about representation theory of monoids
 construction of the Jucys Murphy elements for the symmetric group
I believe all of those either depend on group
, just need a basis, or need a concrete implementation.
Note that those live at different levels (magmas, monoids, groups, specific groups). So if really want to support both "constructed as" and "isomorphic to", a functorial construction and a concrete class won't be enough. We need two functorial constructions.
Hmm...I think that for construction
and for our concrete implementation of that functor, that we need to make assumptions about the image. However, I think the category should be there for the isomorphic to and the constructed as should be a concrete class. Having a concrete class also makes things easier to maintain and add to for the noninitiated.
construction
cannot be lifted because the default inParent
is toreturn None
.This is just the usual artifact that for historical reasons, there is too much stuff in Parent, which prevents categories to provide default implementations.
construction
being a non speedcritical method, I foresee no obstruction to moving it to Sets (but need to double check the code first).
I agree. However, it is something that is currently a limitation.
Similar for
is_exact
.This one is a bit more annoying since it's a cpdef method. Worst comes to worst, we could do as for getitem.
This might be something we could lift from GroupAlgebra
to CFM.
So I believe we need a concrete class
Not yet clear :)
I suspect if you had your way, nearly everything would be implemented as a category. :P
comment:27 Changed 6 years ago by
Replying to tscrim:
I could not use
super
to make the calls without getting either an infinite recursion or errors from Python. I also think we should not force a direct call to the unital algebra's__init_extra__
in case one of the other base categories ends up having an__init_extra__
.
In principle there is no need for super. By design, C.ParentMethods__init_extra__
is providing *additional* initialization code that should be run for every parent in C or some subcategory. Hence the specific protocol: the __init_extra__
of each and every category is being called, without having to do an explicit super call.
comment:28 Changed 6 years ago by
Commit:  647264f6107ad29f987821e4a585c36215e49e40 → 23772ed94b1f063091a3ab54f55dc8d56abba5e7 

Branch pushed to git repo; I updated commit sha1. New commits:
23772ed  Better handling additive groups.

comment:29 followup: 30 Changed 6 years ago by
I first tried that, and I must have mistested something. I was able to use __init_extra__
to refine the category and looked like a good hook to do similar things in the future.
However, I decided not to do that because we would have to duplicate it between Groups
and AdditiveGroups
. Perhaps that will be one of the best arguments to you for not moving everything to the category. Now I'm considering pulling back the methods I lifted to the category for this reason. Thoughts?
comment:30 Changed 6 years ago by
Replying to tscrim:
I first tried that, and I must have mistested something. I was able to use
__init_extra__
to refine the category and looked like a good hook to do similar things in the future.However, I decided not to do that because we would have to duplicate it between
Groups
andAdditiveGroups
. Perhaps that will be one of the best arguments to you for not moving everything to the category. Now I'm considering pulling back the methods I lifted to the category for this reason. Thoughts?
The duplication between Groups
and AdditiveGroups
here and for all the rest is annoying, but at this stage this is the price we pay. I am actually investigating with colleagues ways to avoid this; see:
 http://opendreamkit.org/2016/08/01/CICM/
 http://opendreamkit.org/2016/08/01/CICM/#theadditivestructureshierarchyfromitsmultiplicativecounterpart
but let's not hold our breaths on this.
In the meantime, we can reduce the duplication to a minima by using an alias:
class AdditiveGroups: class Algebras: class ParentMethods: __init_extra__ = Groups.Algebras.ParentMethods.__init_extra__.im_func
Also: we may want to treat additive and multiplicative slightly differently, since coercion is plausible in the latter but not the former case. So maybe it won't be exact duplication.
comment:31 Changed 6 years ago by
Replying to tscrim:
In that case, it creates an instance of a specific concrete class.
Yes because the cartesian product construction requires a specific
data structure. Note that there is no concrete class
CartesianProduct
for e.g. groups. Just one for sets (and one for
modules since we use a different data structure then).
In our case we don't have to define a new datastructure since we can just use that of e.g. CFM.
I believe all of those either depend on
group
, just need a basis, or need a concrete implementation.
Their current implementation all require the algebra to be expressed in its canonical basis. Yes that's pretty specific. Yet not quite concrete. We currently are using CombinatorialFreeModule? for the concrete data structure, but could switch to any other ModulesWithBasis? implementation.
I think the category should be there for the "isomorphic to" and the "constructed as" should be a concrete class. Having a concrete class also makes things easier to maintain and add to for the noninitiated.
But then almost all the methods I mentioned above need to go down in the concrete class. And then we actually need several concrete classes: MagmaAlgebra?, SemigroupAlgebra?, MonoidAlgebra?, GroupAlgebra?, JTrivialMonoidAlgebra, all with appropriate inheritance. Thus just redoing by hand what categories do for us, and not really making life simpler for the noninitiated.
construction
cannot be lifted because the default inParent
is toreturn None
.I agree. However, it is something that is currently a limitation.
Right, we have to do something. Let's just move the default
construction
from Parent
to Sets
. I am happy giving it a shot.
... about
is_exact
. This might be something we could lift fromGroupAlgebra
to CFM.
Very good point. It really would belong go Modules.WithBasis?, but CFM is a pretty good approximation for now.
I suspect if you had your way, nearly everything would be implemented as a category. :P
:)
You know, the category infrastructure grew out of struggling with concrete use cases (e.g. when implementing cartesian products), seeing the same specific pattern come again and again, and redoing by hand the same stuff that did not scale. And having in mind what other had done in other systems to tackle the same pattern. I invested two years worth of coding into that, not to have to struggle again. So yes, when I see the specific pattern, I am motivated to use the infrastructure!
Cheers,
comment:32 followup: 33 Changed 6 years ago by
It will be very good if you're able to remove the duplication between +
and *
groups. :)
*sigh* too much is already shoved up with assumptions into the categories. I really do not like this fragmented code; I have a hard time figuring out what is doing what where. In addition, I see the requirement for a specific basis as being a concrete class, and we have illspecified things between the abstract class and the concrete class. I also believe that by having GroupAlgebra
for now makes dealing with the code duplication between +
/*
groups much better (we don't have to worry about making an alias for everything). At this point, we do not have a need for a hierarchy of *Algebra
, but that could eventually be a problem.
At this point, I will just lift everything up to the category under strong objections, but I would rather see this ticket get merged then left in limbo as it fixes a number of things with group algebras.
comment:33 followup: 35 Changed 6 years ago by
Replying to tscrim:
I really do not like this fragmented code;
I see your point. But that's not the code, it's just the math behind. When writing a math book, each theorem comes with its own combination of hypotheses. The author can simplify the reader's life by taking some common strong assumption for all theorems in the book (e.g. all fields are algebraicall closed and of char 0). But that's at the price of generality.
That's what's happening to us. For a long time, systems afforded to make strong assumptions (like all rings are commutative). But Sage aims beyond and enable the study of a much wider variety of objects.
I have a hard time figuring out what is doing what where.
Given a specific method, it's relatively straightforward with the current infrastructure to decide where to put it (figuring the hypotheses of the theorem). I agree that getting the big picture is hard. We need better tools to explore and visualize what's implemented.
In addition, I see the requirement for a specific basis as being a concrete class, and we have illspecified things between the abstract class and the concrete class.
Somehow, putting everything about xxx algebras in the category simplifies things. No need to worry anymore where things should be :)
I also believe that by having
GroupAlgebra
for now makes dealing with the code duplication between+
/*
groups much better (we don't have to worry about making an alias for everything).
Let's see how it goes. Before the ticket, GroupAlgebra
only really supported multiplicative groups, right? If we only lift its features to multiplicative structures for now, that's ok.
At this point, we do not have a need for a hierarchy of
*Algebra
, but that could eventually be a problem.
If the aim is only to support group algebras, we indeed don't need that hierarchy. Strangely enough, I very much care about supporting semigroups and monoids of all sorts :)
At this point, I will just lift everything up to the category under strong objections, but I would rather see this ticket get merged then left in limbo as it fixes a number of things with group algebras.
Ok, thanks. Sorry for twisting your arm. I need to improve my arguments to be more convincing :)
Let me know if there is anything I can do to help.
Cheers,
comment:34 Changed 6 years ago by
Commit:  23772ed94b1f063091a3ab54f55dc8d56abba5e7 → 9e77b87f234377b3d72f94abd293af15cfc7a22c 

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

Replying to nthiery:
Replying to tscrim:
I really do not like this fragmented code;
I see your point. But that's not the code, it's just the math behind. When writing a math book, each theorem comes with its own combination of hypotheses. The author can simplify the reader's life by taking some common strong assumption for all theorems in the book (e.g. all fields are algebraicall closed and of char 0). But that's at the price of generality.
That's what's happening to us. For a long time, systems afforded to make strong assumptions (like all rings are commutative). But Sage aims beyond and enable the study of a much wider variety of objects.
However, in math books/papers, we do not require the same amount of specificity that code needs for computations nor the distinction between isomorphism and equality.
In addition, I see the requirement for a specific basis as being a concrete class, and we have illspecified things between the abstract class and the concrete class.
Somehow, putting everything about xxx algebras in the category simplifies things. No need to worry anymore where things should be :)
I also believe that by having
GroupAlgebra
for now makes dealing with the code duplication between+
/*
groups much better (we don't have to worry about making an alias for everything).Let's see how it goes. Before the ticket,
GroupAlgebra
only really supported multiplicative groups, right? If we only lift its features to multiplicative structures for now, that's ok.
Yes, but everything still worked with additive groups once algebras
redirected to construct them in that case.
At this point, we do not have a need for a hierarchy of
*Algebra
, but that could eventually be a problem.If the aim is only to support group algebras, we indeed don't need that hierarchy. Strangely enough, I very much care about supporting semigroups and monoids of all sorts :)
I never, ever would have guessed. :P
At this point, I will just lift everything up to the category under strong objections, but I would rather see this ticket get merged then left in limbo as it fixes a number of things with group algebras.
Ok, thanks. Sorry for twisting your arm. I need to improve my arguments to be more convincing :)
It's not that your arguments are not valid with lots of experience, but I see things from a slightly different perspective. I appreciate your point of view and find these debates productive and beneficial (if slightly frustrating at times :P).
Let me know if there is anything I can do to help.
I've done what I could for right now. I've pushed my current WIP. If you could finish up getting the coercion working, it didn't work for me asis (with renaming GroupAlgebra._coerce_map_from_
). I think the _element_constructor_
is close enough to the CFM that we can remove it, but I haven't tried it yet. The only other thing is moving some documentation and tests around to get this done. Thanks.
comment:39 Changed 6 years ago by
Commit:  9e77b87f234377b3d72f94abd293af15cfc7a22c → d55147b6a79289df93453fdc763a8a143e86cdac 

Branch pushed to git repo; I updated commit sha1. New commits:
d55147b  backup

comment:40 Changed 6 years ago by
For info: I pushed my current branch if you want to have a look and for backup. But please don't build on it: I *will* rewrite history (I should have done it on a private branch but screwed up. It's over time to go to bed!).
comment:41 Changed 6 years ago by
Commit:  d55147b6a79289df93453fdc763a8a143e86cdac → 045367eeb1323944891aa78de1eecb3ec9b443cd 

Branch pushed to git repo; I updated commit sha1. New commits:
045367e  backup2

comment:42 Changed 6 years ago by
All right: the scary failures I was getting are now fixed (or worked around for one of them). More details later on. Unless I accidently broke new files (I only checked with failed), most tests should now pass.
So long GroupAlgebra
, and thanks for the fish!
Again, don't build on the current commits: I just stuffed everything in there for backup and early release purposes. I am now planning to rewrite history to split the stuff in intelligible chunks to ease the review. Hopefully tonight, but no promise; nice weather here, time for a family walk on Mont Royal!
Cheers,
comment:43 Changed 6 years ago by
For the record, here is the outcome of make ptestlong
:
 sage t long src/sage/categories/semigroups.py # 3 doctests failed sage t long src/sage/algebras/quatalg/quaternion_algebra.py # 1 doctest failed sage t long src/sage/calculus/calculus.py # 1 doctest failed sage t long src/sage/groups/perm_gps/permgroup_named.py # 1 doctest failed sage t long src/sage/combinat/permutation.py # 1 doctest failed sage t long src/sage/combinat/symmetric_group_algebra.py # 3 doctests failed sage t long src/sage/categories/modules_with_basis.py # 1 doctest failed sage t long src/sage/categories/modules.py # 1 doctest failed sage t long src/sage/categories/monoids.py # 2 doctests failed sage t long src/sage/combinat/species/series.py # 1 doctest failed sage t long src/sage/categories/category_with_axiom.py # 1 doctest failed
I glanced through them, and most seem trivial output updates; the one in calculus is unrelated (fails for me also on develop).
comment:44 followup: 45 Changed 6 years ago by
The calculus one is related to a french locale LANG and giac changing its keywords to French in that context. It can be made silent by changing the locale. See #22833.
comment:45 Changed 6 years ago by
comment:46 followup: 47 Changed 6 years ago by
Before I proceed to finalization, I have a few questions:
 We currently have tutorial material about group algebras (and more generally XXX algebras) in several locations: Groups.Algebras, Sets.ParentMethods?.algebra, GroupAlgebras?. Possibly even in the group algebra functor. Each tutorial is more or less complete, and there is quite some duplication. Instead, it would be best to have a single tutorial that would take the best of each of the current ones, and have all other locations refer to it. And we could by the way refer to from the index of thematic tutorials.
In which of the locations do we want to put that tutorial? I would tend to choose
Sets.ParentMethods.algebra
, as it feel the easiest to discover asG.algebra?
when the user has a groupG
under hand.
What do you think?
GroupAlgebra
would also be a fairly natural entry point; but I would tend to encourage the user ofG.algebra()
and eventually deprecateGroupAlgebra
at some point to remove one more thing from the global name space. This later point is subject to debate though.
 Due to the change of perspective in the middle of the development of this ticket (my fault), there is a bit of back and forth in the history, which makes it hard to get an overview of what's going on. Also there are quite a few changes that end up being undone later on which increases the risks of conflicts with other branches.
Since this branch is based on a single develop, I am tempted to not only rewrite the history of my latest changes, but rewrite the complete history (squashing it all, and then redoing commits per topic: preliminary changes like for "Parent.construction", moving GroupAlgebra?'s content to the categories, trivial documentation updates, ...).
. Presumably no one other than us has been working on this branch, so
this should be safe even if the branch has been published. Rewriting history is not yet usual practice in Sage (but very much is in other projects), so I am hesitating.
Note: this would also mean that the commits would be under my name. That's unfair in the git history. On the other hand, our practice is to track credit through the trac author/reviewer fields, so that should be alright.
What do you think?
 With this ticket,
GroupAlgebra(SymmetricGroup(3),QQ)
now properly constructs an instance ofSymmetricGroupAlgebra(3,Q)
. Given thatSymmetricGroupAlgebra
has a custom_repr_
, this induces quite a few trivial doctest updates, from:Group algebra of Symmetric group of order 3! as a permutation group over Rational Field
to:Symmetric group algebra of order 3 over Rational Field
. While we are at it, I was wondering whether we did not want to use
the occasion to remove that custom repr for consistency, especially since the that custom repr hides which specific implementation of the symmetric group algebra it used:
sage: SymmetricGroupAlgebra(QQ, WeylGroup(["A",3])) Symmetric group algebra of order 4 over Rational Field
Maybe we would want to also change the generic repr to produce:
XXX group algebra over QQinstead of
Group algebra of XXX group over QQ
Opinions?
 We have been struck once again in this ticket by the dreaded
category MRO issue. I have one commit in
sage.misc.c3_controlled
which makes things more robust in waiting for a proper implementation of #22962.
Should I move this commit to a separate ticket?
 Lifting
Parent.construction
toSets.ParentMethods
forced me to fix a couple parents to properly initialize their categories (that's a good thing!). Should I move this, and the lifting of "construction", to a separate ticket?
Cheers,
Nicolas
comment:47 followup: 58 Changed 6 years ago by
Replying to nthiery:
 We currently have tutorial material about group algebras (and more generally XXX algebras) in several locations: Groups.Algebras, Sets.ParentMethods?.algebra, GroupAlgebras?. Possibly even in the group algebra functor. Each tutorial is more or less complete, and there is quite some duplication. Instead, it would be best to have a single tutorial that would take the best of each of the current ones, and have all other locations refer to it. And we could by the way refer to from the index of thematic tutorials.
In which of the locations do we want to put that tutorial? I would tend to choose
Sets.ParentMethods.algebra
, as it feel the easiest to discover asG.algebra?
when the user has a groupG
under hand.What do you think?
Well, none of this will be available from G?
, so I would put it in GroupAlgebra
. However, there are two slightly different topics. The first would be basic usage and properties, the other would be provide doctests of functionality. What used to be in the modulelevel doc of algebras/group_algebra.py
is the latter. For this, a natural place is where we provide the majority of the implementation: the Groups.Algebras
category. In Sets.ParentMethods.algebra
, we should give the necessary information to construct the object as it is a generic method.
GroupAlgebra
would also be a fairly natural entry point; but I would tend to encourage the user ofG.algebra()
and eventually deprecateGroupAlgebra
at some point to remove one more thing from the global name space. This later point is subject to debate though.
 Due to the change of perspective in the middle of the development of this ticket (my fault), there is a bit of back and forth in the history, which makes it hard to get an overview of what's going on. Also there are quite a few changes that end up being undone later on which increases the risks of conflicts with other branches.
This will not cause any conflicts if you do a merge as git tries the final version, not each individual commit. It is only a potential problem if you do a rebase. IMO, it is better to have the history where you make the first attempt in case there is something we might want to salvage from it later on down the road.
Since this branch is based on a single develop, I am tempted to not only rewrite the history of my latest changes, but rewrite the complete history (squashing it all, and then redoing commits per topic: preliminary changes like for "Parent.construction", moving GroupAlgebra?'s content to the categories, trivial documentation updates, ...).
We might have to do some rewriting for moving the Parent.construction
. Although we could just make those changes on a separate branch and then merge that into here.
 With this ticket,
GroupAlgebra(SymmetricGroup(3),QQ)
now properly constructs an instance ofSymmetricGroupAlgebra(3,Q)
. Given thatSymmetricGroupAlgebra
has a custom_repr_
, this induces quite a few trivial doctest updates, from:Group algebra of Symmetric group of order 3! as a permutation group over Rational Fieldto:Symmetric group algebra of order 3 over Rational FieldWhile we are at it, I was wondering whether we did not want to use the occasion to remove that custom repr for consistency, especially since the that custom repr hides which specific implementation of the symmetric group algebra it used:
sage: SymmetricGroupAlgebra(QQ, WeylGroup(["A",3])) Symmetric group algebra of order 4 over Rational Field
I like the compactness of the current representation. Plus the actual group that is used I see of as more of an implementation detail.
Maybe we would want to also change the generic repr to produce:
XXX group algebra over QQinstead of
Group algebra of XXX group over QQOpinions?
I think the latter is better, but it is slightly redundant. I would say
Algebra of XXX over YYY
as it is more compatible when we expand to, e.g., monoids and it contains enough information to explain the object. Although it
 We have been struck once again in this ticket by the dreaded category MRO issue. I have one commit in
sage.misc.c3_controlled
which makes things more robust in waiting for a proper implementation of #22962.Should I move this commit to a separate ticket?
Yes, please. I don't understand this change and having an explanation for future reference would be beneficial.
 Lifting
Parent.construction
toSets.ParentMethods
forced me to fix a couple parents to properly initialize their categories (that's a good thing!). Should I move this, and the lifting of "construction", to a separate ticket?
Probably; it is good practice.
comment:48 followup: 49 Changed 6 years ago by
Looking at the current code, I really do not like the hack in _coerce_map_from_
. IMO, we should never have a _coerce_map_from_
in the category as any such coercions should be defined using functors. If you need to have _coerce_map_from_
, then we need a concrete class as you are doing something that is implementation specific.
comment:49 Changed 6 years ago by
Hi Travis,
Thanks for the feedback.
Replying to tscrim:
Looking at the current code, I really do not like the hack in
_coerce_map_from_
. IMO, we should never have a_coerce_map_from_
in the category as any such coercions should be defined using functors. If you need to have_coerce_map_from_
, then we need a concrete class as you are doing something that is implementation specific.
I agree that a conversion in a category would be dubious. But here we are speaking about coercions that implement canonical embeddings.
Look at the coercion from the base ring into a unital algebra. There is nothing implementationspecific in it. It's all about mathematics, and it belongs to the category of unital algebras.
Here again it's about the mathematical fact that "the embedding of G into G' lifts to an embedding of KG into KG'"; there is no need to know the specifics of the data structure for KG' to implement that fact. Therefore I see no reason why some concrete class should be involved. It just turns out that our functor is actually a functorial construction and requires a "split implementation" (see http://opendreamkit.org/2016/08/01/CICM/#terminology by lack of better terminology). Hence its implementation ends up being in the functorial construction categories.
Cheers,
Nicolas
comment:50 followup: 51 Changed 6 years ago by
I didn't say anything about conversions, which is even worse. Yet, I agree that the mathematics are there, but you have a specific implementation of _coerce_map_from_
in the category. That is something that should be handled by the construction functor. The other place that we could do this is register a coercion in the __init_extra__
. The last option would be to lift _coerce_map_from_
from Parent
to Sets.ParentMethods
, but I want to keep an idiom for concrete implementations.
comment:51 followup: 53 Changed 6 years ago by
Replying to tscrim:
The other place that we could do this is register a coercion in the
__init_extra__
.
Alas, this does not work: there are many K'[G'] that could coerce in K[G], and we can't explicitly register conversions for all of them.
I have been dreaming for a long time (already in MuPADCombinat) of
having a way to register a single "conversion pattern" that would
later get lazily instantiated as needed. _coerce_map_from
is kind of
doing that job.
but you have a specific implementation of
_coerce_map_from_
in the category. The last option would be to lift_coerce_map_from_
fromParent
toSets.ParentMethods
, but I want to keep an idiom for concrete implementations.
Hmm, are you worried that, if we implement a _coerce_map_from
in
some category C, then we are forcing each of its concrete parent to
make a choice between either restraining itself from implementing a
custom _coerce_map_from
method, or not benefiting from the generic
coercions provided by C?
If yes, I believe we are fine: both can implement _coerce_map_from
methods as long as they play cooperatively with super calls. That's
what I have done here.
It's not yet common practice. However if, as I would tend to foresee,
it becomes a common situations to have both a parent and several of
its categories implement _coerce_map_from
methods, we could better
support this idiom by:
 Changing Parent's default implementation to do a super call
 Encourage if not enforce in the documentation that any
implementation of
_coerce_map_from
should end with a super call.
Granted, super calls within the categories are somewhat inconvenient due to recovering the relevant class; it should get better with singleton categories.
Cheers,
Nicolas
comment:53 followup: 54 Changed 6 years ago by
Dependencies:  → #23000 

Replying to nthiery:
Replying to tscrim:
The other place that we could do this is register a coercion in the
__init_extra__
.Alas, this does not work: there are many K'[G'] that could coerce in K[G], and we can't explicitly register conversions for all of them.
I have been dreaming for a long time (already in MuPADCombinat) of having a way to register a single "conversion pattern" that would later get lazily instantiated as needed.
_coerce_map_from
is kind of doing that job.
Yes and no. My strong opinion is that when you have a construction
that returns a ConstructionFunctor
, then that functor should be able to set. This is both a natural place and should be simple to implement. Unfortunately, we don't have such a hook yet. I would much rather have a concrete class with a _coerce_map_from_
in the meantime than the hack around as a (lightweight) concrete class is easier to get rid of in the future.
but you have a specific implementation of
_coerce_map_from_
in the category. The last option would be to lift_coerce_map_from_
fromParent
toSets.ParentMethods
, but I want to keep an idiom for concrete implementations.Hmm, are you worried that, if we implement a
_coerce_map_from
in some category C, then we are forcing each of its concrete parent to make a choice between either restraining itself from implementing a custom_coerce_map_from
method, or not benefiting from the generic coercions provided by C?If yes, I believe we are fine: both can implement
_coerce_map_from
methods as long as they play cooperatively with super calls. That's what I have done here.
That is part of my concern, as it can require some finesse to get around it as you have done. However, that is not my biggest worry (see below).
It's not yet common practice. However if, as I would tend to foresee, it becomes a common situations to have both a parent and several of its categories implement
_coerce_map_from
methods, we could better support this idiom by:
 Changing Parent's default implementation to do a super call
 Encourage if not enforce in the documentation that any implementation of
_coerce_map_from
should end with a super call.
I do not think this is a good idea to recommend super calls on _coerce_map_from_
as they could go to a category with less structure, allowing more permissive coercions (e.g., graded algebras to algebras). I also think that _coerce_map_from_
should be reserved for concrete implementations, where specific information about the data structure can be used for a similar reason.
Granted, super calls within the categories are somewhat inconvenient due to recovering the relevant class; it should get better with singleton categories.
I am not completely convinced of this, as it should be determined by the hierarchy of the categories. I think the biggest technical limitation is the Python2 version of super
.
comment:54 followup: 55 Changed 6 years ago by
Replying to tscrim:
Yes and no. My strong opinion is that when you have a
construction
that returns aConstructionFunctor
, then that functor should be able to set. This is both a natural place and should be simple to implement. Unfortunately, we don't have such a hook yet. I would much rather have a concrete class with a_coerce_map_from_
in the meantime than the hack around as a (lightweight) concrete class is easier to get rid of in the future.
A lightweight concrete class also has its downside: Let's say Alice wants to implement a monoid algebra A, but using a different data structure than Combinatorial Free Module. Maybe someone wanting to endow the existing polynomial rings with their natural monoid algebra structure. If there is a lightweight concrete class C, then Alice is forced to chose to either have A inherit from C (which may conflict with the existing data structure), or to not benefit from the features of C.
For cartesian products, there already are at least two concrete implementations.
As for the "hack around": maybe the infrastructure could streamline further the process, but I do not see it as a hack: there are several players that together provide the features of group algebras, and this is just making them cooperate also on the coercion definitions.
I do not think this is a good idea to recommend super calls on
_coerce_map_from_
as they could go to a category with less structure, allowing more permissive coercions (e.g., graded algebras to algebras).
There is a point here: Sage has always been fuzzy about its definition of coercions which should be "morphisms for whatever the structure the objects could have", and we are hitting on that fuzz. I believe this should be in the contract: "by declaring yourself in that category (especially a functorial construction category), you accept that there will be a coercion from XXX".
My approach to that has always be to minimize the number of coercions defined by default :)
I also think that
_coerce_map_from_
should be reserved for concrete implementations, where specific information about the data structure can be used for a similar reason.
Good point: a concrete implementation may want to exploit the internal data structure to provide a more efficient implementation of the morphism. Hence we should separate the implementation of the morphism from its declaration as coercion, so that the implementation can be overridden in subclass. That's what we already do for "from_base_ring", and did in similar situations in MuPADCombinat. I'll implement that here.
I am not completely convinced of this, as it should be determined by the hierarchy of the categories. I think the biggest technical limitation is the Python2 version of
super
.
Quite true! I guess I am just not yet in the frame of mind "Python 3 will come soon enough that I can start dreaming about all the good use we could make of its features" :) I am not sure though Python3 with help with super and categories for Cython classes. Let's see.
Cheers,
Nicolas
comment:55 followup: 60 Changed 6 years ago by
Replying to nthiery:
Replying to tscrim: A lightweight concrete class also has its downside: Let's say Alice wants to implement a monoid algebra A, but using a different data structure than Combinatorial Free Module. Maybe someone wanting to endow the existing polynomial rings with their natural monoid algebra structure. If there is a lightweight concrete class C, then Alice is forced to chose to either have A inherit from C (which may conflict with the existing data structure), or to not benefit from the features of C.
That feels like a fallacy to me. I am saying we keep the current concrete implementation as light as possible as a placeholder until we put the hook in the correct place.
As for the "hack around": maybe the infrastructure could streamline further the process, but I do not see it as a hack: there are several players that together provide the features of group algebras, and this is just making them cooperate also on the coercion definitions.
You're circumventing the MRO with the second call to _coerce_map_from_
, which has to possible catch an AttributeError
. So if you want to do this at the category level, then you should define the generic call at that category level. However, this could have speed implications as it is a cpdef
method currently, in addition to the other problems we are discussing.
I do not think this is a good idea to recommend super calls on
_coerce_map_from_
as they could go to a category with less structure, allowing more permissive coercions (e.g., graded algebras to algebras).There is a point here: Sage has always been fuzzy about its definition of coercions which should be "morphisms for whatever the structure the objects could have", and we are hitting on that fuzz. I believe this should be in the contract: "by declaring yourself in that category (especially a functorial construction category), you accept that there will be a coercion from XXX".
I feel like that is a something that would come from registering coercions using a ConstructionFunctor
and making that the default result of construction
. However, don't think we should have that be (one of) the defining condition of a coercion as it is too strong, but instead a condition on objects the category, as your statement makes.
comment:56 Changed 6 years ago by
Commit:  045367eeb1323944891aa78de1eecb3ec9b443cd → b462163f82c48c622be1b10993e21de5b881c405 

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
1d1a406  18700: let Parent and Module cooperate with super classes for coercion lookup with _coerce_map_from_

210e945  18700: lift all features of the GroupAlgebra class to the algebra functor and categories + doc

588e9ee  18700: lift CombinatorialFreeModule.gens to Modules.WithBasis.FiniteDimensional

7bb569a  18700: conversion from formal sums to CombinatorialFreeModule

d6441b0  18700: Implement Permutations.degree, for consistency with SymmetricGroup

b8be30f  18700: Implement PermutationGroup.ngens, for consistency with its gen(i), ngens, ...

88f5c84  18700: Symmetric group algebra: better support for SymmetricGroupAlgebra(0, QQ)

63a2bba  18700: lift groupalgebra related methods up the categories

e2ab56f  18700: follow up on getting rid of GroupAlgebra + documentation cleanup from previous commit

b462163  18700: trivial documentation updates

comment:57 Changed 6 years ago by
With that current version, all tests pass, and the commits are reasonably clean.
Now it's way time to go to bed. I'll discuss here tomorrow the state of affair, and in particular which comments I have taken into account, or not, or not yet.
Cheers,
comment:58 Changed 6 years ago by
Replying to tscrim:
... About documentation ...
Well, none of this will be available from
G?
, so I would put it inGroupAlgebra
. However, there are two slightly different topics. The first would be basic usage and properties, the other would be provide doctests of functionality. What used to be in the modulelevel doc ofalgebras/group_algebra.py
is the latter. For this, a natural place is where we provide the majority of the implementation: theGroups.Algebras
category. InSets.ParentMethods.algebra
, we should give the necessary information to construct the object as it is a generic method.
Right, it's indeed a shame that G?
did not bring anything useful. I
fixed this by setting its __doc__
attribute in
Sets.ParentMethods.algebra
.
After moving things around while merging all the pieces together, I ended up adopting the following plan:
 Have the module
sage.categories.algebra_functor
start with a tutorial on "group algebras and generalizations", introducing as its name suggests the topic with group algebras and then generalizing.
 Link this tutorial from the thematic tutorials
 Proceed after the tutorial with a test section containing all tests that did not have a natural location elsewhere (e.g. in the docstring of a method).
 For each of
Sets.ParentMethods.algebra
,GroupAlgebra
,GroupAlgebras
and the group algebra functor, have a short doc with the minimum definition, examples and specifications that are specific to each, and a proeminent link to the tutorial.
IMO, it is better to have the history where you make the first attempt in case there is something we might want to salvage from it later on down the road.
Good point. I kept the history as is for your first implementation and only rewrote history for my own changes (no intermediate point was of particular value).
... about repr ...
I would say
Algebra of XXX over YYYas it is more compatible when we expand to, e.g., monoids and it contains enough information to explain the object.
I like it as well. Done.
about moving some stuff to separate tickets.
Yes, please / probably; it is good practice.
Done.
comment:60 followup: 61 Changed 6 years ago by
Replying to tscrim:
Replying to nthiery:
Replying to tscrim: A lightweight concrete class also has its downside: Let's say Alice wants to implement a monoid algebra A, but using a different data structure than Combinatorial Free Module. Maybe someone wanting to endow the existing polynomial rings with their natural monoid algebra structure. If there is a lightweight concrete class C, then Alice is forced to chose to either have A inherit from C (which may conflict with the existing data structure), or to not benefit from the features of C.
That feels like a fallacy to me.
In my world it's a genuine comment originating from being struck by similar situations several times :)
As for the "hack around": maybe the infrastructure could streamline further the process, but I do not see it as a hack: there are several players that together provide the features of group algebras, and this is just making them cooperate also on the coercion definitions.
You're circumventing the MRO with the second call to
_coerce_map_from_
, which has to possible catch anAttributeError
. So if you want to do this at the category level, then you should define the generic call at that category level. However, this could have speed implications as it is acpdef
method currently, in addition to the other problems we are discussing.
Oh, I see: I had forgotten I had not finished the work: the code back
then was indeed a hack in CFM to circumvent the implementation in
Module
. I have reworked this so that the default implementation
really is in Sets.ParentMethods
, and both Module
and Parent
play
cooperatively by ending with a super call instead of returning None
if they have nothing to offer.
This does not close the discussion on whether we want
_coerce_map_from_
play cooperatively along the hierarchy of classes.
But if we do, the above implementation sounds clean to me. Having the
cpdef _coerce_map_from_
in Parent
enables subclasses to implement
cpdef _coerce_map_from_
that are fast when they succeed, which I
believe is the most important.
It would be nice to have the coercion be tied to the construction
functor. And incidentally it would be nice to have a bivariate functor
rather than our two "curried" univariate ones (GroupAlgebra(G)(Q)
and AlgebraFunctor(Q)(G)
).
In the mean time, I aiming right now for the concreteclassless approach, in particular because the later transition will be transparent to subclasses.
Cheers,
Nicolas
comment:61 Changed 6 years ago by
Replying to nthiery:
Replying to tscrim:
That feels like a fallacy to me.
In my world it's a genuine comment originating from being struck by similar situations several times :)
I know we've come across it in the past, but the fallacy comes from the fact it might be a problem in the future and that there are other solutions (e.g., code duplication, which wouldn't be much since it is lightweight). Plus, this is only meant to be there shortterm while we implement a more general framework.
Oh, I see: I had forgotten I had not finished the work: the code back then was indeed a hack in CFM to circumvent the implementation in
Module
. I have reworked this so that the default implementation really is inSets.ParentMethods
, and bothModule
andParent
play cooperatively by ending with a super call instead of returningNone
if they have nothing to offer.
Yes, this is much better.
This does not close the discussion on whether we want
_coerce_map_from_
play cooperatively along the hierarchy of classes. But if we do, the above implementation sounds clean to me. Having the cpdef_coerce_map_from_
inParent
enables subclasses to implement cpdef_coerce_map_from_
that are fast when they succeed, which I believe is the most important.
I don't like this as it means coercion testing has an extra level of an MRO lookup plus a python call. So it ends up adding a bit of extra overhead. Granted, this is not a huge difference as coercions are cached, and this is rarely called (relatively speaking). So it is not a strong argument. However, I'm still very worried about incidentally allowing coercions between weakened structures by enforcing _coerce_map_from_
to make super calls. Plus there are the technical limitations.
However, we need a better mechanism for putting category level information into the coercion framework as this is essentially duplicating information (in a private method) that would be available from the functor.
It would be nice to have the coercion be tied to the construction functor.
I can do this on a followup ticket. At least I have a good idea about how this should be done. Although, thinking about it, it might have a similar sort of slowdown as lifting up the _coerce_map_from_
. However, it is something that we should do IMO.
And incidentally it would be nice to have a bivariate functor rather than our two "curried" univariate ones (
GroupAlgebra(G)(Q)
andAlgebraFunctor(Q)(G)
).
There is a problem with resolving this due to ambiguities with the codomain category. One possibility is that we have a category with either a single object (up to isomorphism), the group algebra R[G]
for a fixed group G
and ring R
. Another possibility is that we allow the ring R
to vary. The last is we allow G
to vary. The former is either the single object category or allows R
to vary. The latter is either the single object category or allows G
to vary.
Part of this might come from current technical limitations, i.e., CovariantFunctorialConstruction
versus ConstructionFunctor
. I would probably say that by moving so much up to the category, we have made this problem worse to almost forcing the category to have a single object, which is not what we want.
In the mean time, I aiming right now for the concreteclassless approach, in particular because the later transition will be transparent to subclasses.
I still have my strong reservations with not allowing a concrete class (at this point) in general. I am willing to bend very far, but not all the way at this point. As a compromise, could we have the lightweight concrete class for now until we implement a better infrastructure for the coercion maps? It does not make anything worse (from your POV) than what we currently have.
comment:62 Changed 6 years ago by
Commit:  b462163f82c48c622be1b10993e21de5b881c405 → a1431e0256ed3eb1071e0ddeda1497810be7efdc 

Branch pushed to git repo; I updated commit sha1. New commits:
a1431e0  18700: fix generalization of Modules.WithBasis.random_element

comment:63 Changed 6 years ago by
Brief summary of the phone call we had together with Travis today (Thanks Travis for relaunching the discussion!): this ticket is basically ready to go (up to rebasing, and possibly fixing a few more doctests). We did not come to an agreement on whether to use a concrete class or not. I still believe that using one instead of enabling coerce_map_from
in the categories is limiting the flexibility without a compelling safety reason.
That being said, we need to move on and the design decision is fairly easy to revert. So I gave my green light for switching back to a very minimal concrete class whose role is only to handle the coercions.
I asked Travis to create a ticket with the current branch to keep the code around in case later insights or use cases makes us rethink the decision.
comment:64 Changed 6 years ago by
Commit:  a1431e0256ed3eb1071e0ddeda1497810be7efdc → 64e9cd0f7aad5509ad47dad542f238eac9a119c9 

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

I've done the partial revert. The previous code is on #23252. Needs double check. More comments likely to follow later.
comment:66 Changed 6 years ago by
Authors:  Travis Scrimshaw → TravisScrimshaw, Nicolas M. Thiéry 

Thank you for the productive discussion(s) Nicolas.
Okay, now I have a little more time for a detailed reply. I've added back in a small concrete class to handle the coercion until we have a better mechanism for coercion at the level of categories. However, we can continue that discussion on #23252. I also scrubbed the _coerce_map_from_
calls up through the category as I'm still not convinced this is the way forward.
The version before my changes is on that ticket, which I rebased to 8.0.beta10
as a way to try and ensure they won't accidentally get overwritten by my last commit. If someone could just doublecheck my changes, then we can set a positive review.
comment:67 Changed 6 years ago by
Commit:  64e9cd0f7aad5509ad47dad542f238eac9a119c9 → 4e9200251bfe9c2828d22cb4337b4984ef188bb6 

Branch pushed to git repo; I updated commit sha1. New commits:
4e92002  Merge branch 'develop' into t/18700/public/groups/standardize_group_algebras18700

comment:68 Changed 6 years ago by
I merged the latest develop branch. All tests passed but documentation doesn't build.
comment:69 Changed 6 years ago by
Commit:  4e9200251bfe9c2828d22cb4337b4984ef188bb6 → c2e1c053fcd363569ca0ec6d7e781a61e1445031 

Branch pushed to git repo; I updated commit sha1. New commits:
1586d65  Merge branch 'develop' into public/groups/standardize_group_algebras18700

e6ef3c1  Doc fixes.

c2e1c05  Merge branch 'public/groups/standardize_group_algebras18700' of git://trac.sagemath.org/sage into public/groups/standardize_group_algebras18700

comment:70 Changed 6 years ago by
This fixes the docbuild issues for me (plus a few other misc doc issues I noticed while trying to fix it).
comment:72 Changed 6 years ago by
Authors:  TravisScrimshaw, Nicolas M. Thiéry → Travis Scrimshaw, Nicolas M. Thiéry 

comment:73 Changed 6 years ago by
Search for algerbas
in the patch, obvious typo. There should be a test that catches that
sage t long warnlong 67.9 src/sage/algebras/group_algebra.py ********************************************************************** File "src/sage/algebras/group_algebra.py", line 138, in sage.algebras.group_algebra.GroupAlgebra_class._coerce_map_from_ Failed example: ZG.coerce_map_from(H) Expected: Conversion map: From: Cyclic group of order 3 as a permutation group To: Algebra of Dihedral group of order 6 as a permutation group over Integer Ring Got: Coercion map: From: Cyclic group of order 3 as a permutation group To: Algebra of Dihedral group of order 6 as a permutation group over Integer Ring
comment:74 Changed 6 years ago by
Status:  positive_review → needs_work 

comment:75 Changed 6 years ago by
Commit:  c2e1c053fcd363569ca0ec6d7e781a61e1445031 → a93b1e9f5b3f989c67e433e043b616073861502e 

Branch pushed to git repo; I updated commit sha1. New commits:
6be53f3  Move _is_coercion from DefaultConvertMap to Map and make it accurate

7dac7e2  Fix doctest

9a9e437  Print default "coerce" maps as "Coercion"

d8eec2d  Fixed doctests

2fa81a7  Fix doctests to print exactly as they show up on screen

b483c8e  Merge branch 'develop' into t/23211/mark_morphisms_as_coercions

78807fa  fix doctest errors

8c67163  Merge branch 'u/saraedum/mark_morphisms_as_coercions' of git://trac.sagemath.org/sage into public/groups/standardize_group_algebras18700

a93b1e9  Fixing typo and rebasing over #23211.

comment:76 Changed 6 years ago by
Dependencies:  #23000 → #23000 #23211 

Status:  needs_work → needs_review 
I've fixed the typo, but we don't explicitly test register_unpickle_override
anywhere else. The failure is from #23211, but it is good to know that we have a nontrivial rebase before the next beta round.
comment:77 Changed 6 years ago by
Perhaps we could sneak this into 8.0? This simplifies a lot of things when working with group algebras.
comment:78 Changed 6 years ago by
Commit:  a93b1e9f5b3f989c67e433e043b616073861502e → a18c48c7e4a8f3ee08851c6fd437f29aab364013 

Branch pushed to git repo; I updated commit sha1. New commits:
70c7280  Merge branch 'develop' into public/groups/standardize_group_algebras18700

e613a51  Merge branch 'public/groups/standardize_group_algebras18700' of git://trac.sagemath.org/sage into public/groups/standardize_group_algebras18700

a18c48c  Adding test for old pickle.

comment:79 Changed 6 years ago by
Commit:  a18c48c7e4a8f3ee08851c6fd437f29aab364013 → 3160e26eb25eb09fc7164f020783da2122b18ffd 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
3160e26  Adding test for old pickle.

comment:81 Changed 6 years ago by
Status:  needs_review → positive_review 

comment:82 Changed 6 years ago by
Hi!
Could you update the title and summary to briefly describe what was actually implemented in this ticket?
Thanks,
Nicolas
comment:83 Changed 6 years ago by
Description:  modified (diff) 

Summary:  Use GroupAlgebra as the standard class for group algebras → Have GroupAlgebra(Q, R) and G.algebra(R) return the same standard class for group algebras 
comment:84 Changed 6 years ago by
Branch:  public/groups/standardize_group_algebras18700 → 3160e26eb25eb09fc7164f020783da2122b18ffd 

Resolution:  → fixed 
Status:  positive_review → closed 
Actually,
GroupAlgebra
already has this behavior. Howeveralgebra()
does not return the group algebra by default. I think we need 2 changes:1 
algebra()
checks ifself
is a group (it already checks for inclusion in finite groups). 2  We need a subclass ofCombinatorialFreeModule
which inherits the coercions in general, say aSemigroupAlgebra
.I think both changes are relatively easy since for the second we can canabalize a good part of the
GroupAlgebra
code. However if 2 is contraversal/harderthanIthought, then we should just do 1 here as we need this for #18453 and do a followup for 2.