Opened 4 years ago

Closed 2 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: sage-combinat
Priority: major Milestone: sage-8.0
Component: coercion Keywords: group algebras
Cc: sage-combinat, 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) Commit: 3160e26eb25eb09fc7164f020783da2122b18ffd
Dependencies: #23000 #23211 Stopgaps:

Description (last modified by tscrim)

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 4 years ago by tscrim

Actually, GroupAlgebra already has this behavior. However algebra() does not return the group algebra by default. I think we need 2 changes:

1 - algebra() checks if self is a group (it already checks for inclusion in finite groups). 2 - We need a subclass of CombinatorialFreeModule which inherits the coercions in general, say a SemigroupAlgebra.

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/harder-than-I-thought, then we should just do 1 here as we need this for #18453 and do a followup for 2.

comment:2 Changed 4 years ago by tscrim

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 3 years ago by tscrim

  • Branch set to public/groups/standardize_group_algebras-18700
  • Cc chapoton added
  • Commit set to 5e9420816a245339735f51d0958b06eed509cbd2
  • Milestone changed from sage-6.8 to sage-8.0
  • Status changed from new to needs_review

This goes through and redirects group algebra construction through GroupAlgebra, as well as cleans up how the categories are constructed.


New commits:

5e94208Standardizing group algebras through GroupAlgebra.

comment:4 Changed 3 years ago by bsalisbury1

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 3 years ago by tscrim

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 3 years ago by git

  • Commit changed from 5e9420816a245339735f51d0958b06eed509cbd2 to 39800cc553693c20e460f16f009a185f2baeebdf

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

39800ccFixing doctests and some conversion behavior changes.

comment:7 Changed 3 years ago by tscrim

  • Summary changed from Group algebras should have a coercion inherited from coercions of the underlying groups to 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 3 years ago by bsalisbury1

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/sage-git/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 509, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/Users/Ben/sage-git/local/lib/python2.7/site-packages/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/sage-git/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/sage-git/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/sage-git/src/build/cythonized/sage/structure/coerce_maps.c:4762)
        return C._element_constructor(x)
      File "/Users/Ben/sage-git/local/lib/python2.7/site-packages/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 3 years ago by git

  • Commit changed from 39800cc553693c20e460f16f009a185f2baeebdf to 2ef2208407ec7edfbe03a8c9980741f25fc2db2a

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

2ef2208We have a unit, so we can use that in coercion.

comment:10 Changed 3 years ago by tscrim

This was me being stupid. Fixed.

comment:11 Changed 3 years ago by bsalisbury1

  • Reviewers set to Ben Salisbury
  • Status changed from needs_review to 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 3 years ago by nthiery

  • Status changed from positive_review to 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 follow-up: Changed 3 years ago by nthiery

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 3 years ago by nthiery

  • Status changed from needs_review to needs_info

comment:15 in reply to: ↑ 13 ; follow-up: Changed 3 years ago by tscrim

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

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 Q-module 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 in reply to: ↑ 15 ; follow-up: Changed 3 years ago by nthiery

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 the FiniteDimensionalModules.extra_super_categories (or something like that) by adding the Finite 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 to Magmas.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 to Groups.ParentMethods, and update the functor to call G.algebra(R) rather than GroupAlgebra(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 in reply to: ↑ 16 ; follow-up: Changed 3 years ago by tscrim

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 to Magmas.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 to Groups.ParentMethods, and update the functor to call G.algebra(R) rather than GroupAlgebra(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 in reply to: ↑ 17 Changed 3 years ago by nthiery

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 utilize GroupAlgebra 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 to Magmas.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 semi-explicitly 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])` 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 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 follow-ups: Changed 3 years ago by tscrim

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 follow-up tickets.

comment:20 Changed 3 years ago by git

  • Commit changed from 2ef2208407ec7edfbe03a8c9980741f25fc2db2a to 647264f6107ad29f987821e4a585c36215e49e40

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

c173ff8Merge branch 'public/groups/standardize_group_algebras-18700' of git://trac.sagemath.org/sage into public/groups/standardize_group_algebras-18700
647264fLifing some methods up to the category.

comment:21 Changed 3 years ago by tscrim

  • Status changed from needs_info to needs_review

comment:22 in reply to: ↑ 19 ; follow-up: Changed 3 years ago by 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.

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 in Parent is to return 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 speed-critical 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 :-)

Last edited 3 years ago by nthiery (previous) (diff)

comment:23 in reply to: ↑ 19 ; follow-up: Changed 3 years ago by 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?

comment:24 Changed 3 years ago by nthiery

Fore reference, #11318 is the ticket suggesting to get rid of GroupAlgebra?.

comment:25 in reply to: ↑ 23 ; follow-up: Changed 3 years ago by tscrim

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 in reply to: ↑ 22 ; follow-up: Changed 3 years ago by tscrim

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 non-initiated.

construction cannot be lifted because the default in Parent is to return 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 speed-critical 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 in reply to: ↑ 25 Changed 3 years ago by nthiery

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 3 years ago by git

  • Commit changed from 647264f6107ad29f987821e4a585c36215e49e40 to 23772ed94b1f063091a3ab54f55dc8d56abba5e7

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

23772edBetter handling additive groups.

comment:29 follow-up: Changed 3 years ago by 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 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 in reply to: ↑ 29 Changed 3 years ago by nthiery

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

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:

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.

Last edited 3 years ago by nthiery (previous) (diff)

comment:31 in reply to: ↑ 26 Changed 3 years ago by nthiery

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 non-initiated.

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 non-initiated.

construction cannot be lifted because the default in Parent is to return 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 from GroupAlgebra 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 follow-up: Changed 3 years ago by tscrim

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 ill-specified 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 in reply to: ↑ 32 ; follow-up: Changed 3 years ago by 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.

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 ill-specified 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 3 years ago by git

  • Commit changed from 23772ed94b1f063091a3ab54f55dc8d56abba5e7 to 9e77b87f234377b3d72f94abd293af15cfc7a22c

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

ee8b0c1Moving more stuff from GroupAlgebra to the categories.
427179aMoving generic construction to the category.
9e77b87Trying to move things up to the category as much as possible. Still WIP.

comment:35 in reply to: ↑ 33 Changed 3 years ago by tscrim

  • Status changed from needs_review to 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 ill-specified 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 as-is (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:36 Changed 3 years ago by nthiery

Will have a look now.

comment:37 Changed 3 years ago by nthiery

Still working on it :-)

comment:38 Changed 3 years ago by tscrim

Thanks. :)

comment:39 Changed 3 years ago by git

  • Commit changed from 9e77b87f234377b3d72f94abd293af15cfc7a22c to d55147b6a79289df93453fdc763a8a143e86cdac

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

d55147bbackup

comment:40 Changed 3 years ago by nthiery

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

Last edited 3 years ago by nthiery (previous) (diff)

comment:41 Changed 3 years ago by git

  • Commit changed from d55147b6a79289df93453fdc763a8a143e86cdac to 045367eeb1323944891aa78de1eecb3ec9b443cd

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

045367ebackup2

comment:42 Changed 3 years ago by nthiery

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 3 years ago by nthiery

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

Last edited 3 years ago by nthiery (previous) (diff)

comment:44 follow-up: Changed 3 years ago by chapoton

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 in reply to: ↑ 44 Changed 3 years ago by nthiery

Replying to chapoton:

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.

Good to know. Thanks for the info!

comment:46 follow-up: Changed 3 years ago by nthiery

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 as G.algebra? when the user has a group G under hand.

What do you think?

GroupAlgebra would also be a fairly natural entry point; but I would tend to encourage the user of G.algebra() and eventually deprecate GroupAlgebra 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 of SymmetricGroupAlgebra(3,Q). Given that SymmetricGroupAlgebra 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 QQ

instead 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 to Sets.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 in reply to: ↑ 46 ; follow-up: Changed 3 years ago by tscrim

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 as G.algebra? when the user has a group G 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 module-level 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 of G.algebra() and eventually deprecate GroupAlgebra 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 of SymmetricGroupAlgebra(3,Q). Given that SymmetricGroupAlgebra 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

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 QQ

instead of

    Group algebra of XXX group over QQ

Opinions?

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 to Sets.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 follow-up: Changed 3 years ago by 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.

comment:49 in reply to: ↑ 48 Changed 3 years ago by nthiery

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 implementation-specific 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 follow-up: Changed 3 years ago by tscrim

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 in reply to: ↑ 50 ; follow-up: Changed 3 years ago by 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 MuPAD-Combinat) 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_ from Parent to Sets.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:52 Changed 3 years ago by nthiery

See #23000

comment:53 in reply to: ↑ 51 ; follow-up: Changed 3 years ago by tscrim

  • Dependencies set to #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 MuPAD-Combinat) 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_ from Parent to Sets.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 in reply to: ↑ 53 ; follow-up: Changed 3 years ago by nthiery

Replying to tscrim:

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.

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 MuPAD-Combinat. 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 in reply to: ↑ 54 ; follow-up: Changed 3 years ago by 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. 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 3 years ago by git

  • Commit changed from 045367eeb1323944891aa78de1eecb3ec9b443cd to b462163f82c48c622be1b10993e21de5b881c405

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

1d1a40618700: let Parent and Module cooperate with super classes for coercion lookup with _coerce_map_from_
210e94518700: lift all features of the GroupAlgebra class to the algebra functor and categories + doc
588e9ee18700: lift CombinatorialFreeModule.gens to Modules.WithBasis.FiniteDimensional
7bb569a18700: conversion from formal sums to CombinatorialFreeModule
d6441b018700: Implement Permutations.degree, for consistency with SymmetricGroup
b8be30f18700: Implement PermutationGroup.ngens, for consistency with its gen(i), ngens, ...
88f5c8418700: Symmetric group algebra: better support for SymmetricGroupAlgebra(0, QQ)
63a2bba18700: lift group-algebra related methods up the categories
e2ab56f18700: follow up on getting rid of GroupAlgebra + documentation cleanup from previous commit
b46216318700: trivial documentation updates

comment:57 Changed 3 years ago by nthiery

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,

Last edited 3 years ago by nthiery (previous) (diff)

comment:58 in reply to: ↑ 47 Changed 3 years ago by nthiery

Replying to tscrim:

... About documentation ...

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 module-level 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.

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 YYY

as 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:59 Changed 3 years ago by tscrim

Sounds like a good plan.

comment:60 in reply to: ↑ 55 ; follow-up: Changed 3 years ago by nthiery

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

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 concrete-class-less approach, in particular because the later transition will be transparent to subclasses.

Cheers,

Nicolas

comment:61 in reply to: ↑ 60 Changed 3 years ago by tscrim

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 short-term 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 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.

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_ in Parent 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) and AlgebraFunctor(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 concrete-class-less 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 2 years ago by git

  • Commit changed from b462163f82c48c622be1b10993e21de5b881c405 to a1431e0256ed3eb1071e0ddeda1497810be7efdc

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

a1431e018700: fix generalization of Modules.WithBasis.random_element

comment:63 Changed 2 years ago by nthiery

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.

Last edited 2 years ago by nthiery (previous) (diff)

comment:64 Changed 2 years ago by git

  • Commit changed from a1431e0256ed3eb1071e0ddeda1497810be7efdc to 64e9cd0f7aad5509ad47dad542f238eac9a119c9

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

e4f7d47Merge branch 'public/groups/standardize_group_algebras-18700' of git://trac.sagemath.org/sage into public/groups/standardize_group_algebras-18700
64e9cd0Removing _coerce_map_from_ from the category implementation.

comment:65 Changed 2 years ago by tscrim

  • Status changed from needs_work to 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 2 years ago by tscrim

  • Authors changed from Travis Scrimshaw to 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 double-check my changes, then we can set a positive review.

comment:67 Changed 2 years ago by git

  • Commit changed from 64e9cd0f7aad5509ad47dad542f238eac9a119c9 to 4e9200251bfe9c2828d22cb4337b4984ef188bb6

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

4e92002Merge branch 'develop' into t/18700/public/groups/standardize_group_algebras-18700

comment:68 Changed 2 years ago by bsalisbury1

I merged the latest develop branch. All tests passed but documentation doesn't build.

comment:69 Changed 2 years ago by git

  • Commit changed from 4e9200251bfe9c2828d22cb4337b4984ef188bb6 to c2e1c053fcd363569ca0ec6d7e781a61e1445031

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

1586d65Merge branch 'develop' into public/groups/standardize_group_algebras-18700
e6ef3c1Doc fixes.
c2e1c05Merge branch 'public/groups/standardize_group_algebras-18700' of git://trac.sagemath.org/sage into public/groups/standardize_group_algebras-18700

comment:70 Changed 2 years ago by tscrim

This fixes the docbuild issues for me (plus a few other misc doc issues I noticed while trying to fix it).

comment:71 Changed 2 years ago by bsalisbury1

  • Status changed from needs_review to positive_review

Looks good now. Thanks!

comment:72 Changed 2 years ago by tscrim

  • Authors changed from TravisScrimshaw, Nicolas M. Thiéry to Travis Scrimshaw, Nicolas M. Thiéry

comment:73 Changed 2 years ago by vbraun

Search for algerbas in the patch, obvious typo. There should be a test that catches that

sage -t --long --warn-long 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 2 years ago by vbraun

  • Status changed from positive_review to needs_work

comment:75 Changed 2 years ago by git

  • Commit changed from c2e1c053fcd363569ca0ec6d7e781a61e1445031 to a93b1e9f5b3f989c67e433e043b616073861502e

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

6be53f3Move _is_coercion from DefaultConvertMap to Map and make it accurate
7dac7e2Fix doctest
9a9e437Print default "coerce" maps as "Coercion"
d8eec2dFixed doctests
2fa81a7Fix doctests to print exactly as they show up on screen
b483c8eMerge branch 'develop' into t/23211/mark_morphisms_as_coercions
78807fafix doctest errors
8c67163Merge branch 'u/saraedum/mark_morphisms_as_coercions' of git://trac.sagemath.org/sage into public/groups/standardize_group_algebras-18700
a93b1e9Fixing typo and rebasing over #23211.

comment:76 Changed 2 years ago by tscrim

  • Dependencies changed from #23000 to #23000 #23211
  • Status changed from needs_work to 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 non-trivial rebase before the next beta round.

comment:77 Changed 2 years ago by tscrim

Perhaps we could sneak this into 8.0? This simplifies a lot of things when working with group algebras.

comment:78 Changed 2 years ago by git

  • Commit changed from a93b1e9f5b3f989c67e433e043b616073861502e to a18c48c7e4a8f3ee08851c6fd437f29aab364013

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

70c7280Merge branch 'develop' into public/groups/standardize_group_algebras-18700
e613a51Merge branch 'public/groups/standardize_group_algebras-18700' of git://trac.sagemath.org/sage into public/groups/standardize_group_algebras-18700
a18c48cAdding test for old pickle.

comment:79 Changed 2 years ago by git

  • Commit changed from a18c48c7e4a8f3ee08851c6fd437f29aab364013 to 3160e26eb25eb09fc7164f020783da2122b18ffd

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

3160e26Adding test for old pickle.

comment:80 Changed 2 years ago by tscrim

I've added a test with an old pickle to make sure it works.

comment:81 Changed 2 years ago by bsalisbury1

  • Status changed from needs_review to positive_review

comment:82 Changed 2 years ago by nthiery

Hi!

Could you update the title and summary to briefly describe what was actually implemented in this ticket?

Thanks,

Nicolas

comment:83 Changed 2 years ago by tscrim

  • Description modified (diff)
  • Summary changed from Use GroupAlgebra as the standard class for group algebras to Have GroupAlgebra(Q, R) and G.algebra(R) return the same standard class for group algebras

comment:84 Changed 2 years ago by vbraun

  • Branch changed from public/groups/standardize_group_algebras-18700 to 3160e26eb25eb09fc7164f020783da2122b18ffd
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.