Make subword complexes compatible with real reflection groups

[stumpc5]

The subword complex code was written and optimized for real reflection groups, but then made its way into Sage for Coxeter groups. This ticket is to make it handle both.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​2d70fab	trac #11187 more doc tuning
​a04b9c8	Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​9c96d33	added ST type casting for real groups + documentation of crg's
​5b1f2b0	Merge branch 'u/stumpc5/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​d4e7a61	working through the doctests for complex groups
​d7b8c7d	fixing all doctests
​7c9d700	Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
​85d0ce1	fixed a typo in the doc
​521d50b	Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
​5ae3b7f	marked a missing doctest + fixed a bug to show type C2

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​72082b1	fixed a bug in noncrossing partition lattice and reflection/absolute order
​844f450	Merge branch 'u/stumpc5/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​d425669	Fixing failures and some other things.
​87cd989	fixed one doctest in category complex reflection group
​05a8ab4	11187: fixed trivial doctest failures
​32bf1ae	11187: cleanup of the organization of the various axioms (WellGenerated, ...) for complex/generalized reflection groups + documentation improvements
​73276ca	Merge branch 'u/tscrim/11187' of trac.sagemath.org:sage into t/11187/11187
​e074050	merged
​b572c74	fixed a missing doctest
​df55cdd	merged the newest version of 11187

[git]

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

​1927151

fixed a bug in simple_root_index

[stumpc5]

This ticket seems to be ready once #11187 has positive review.

[chapoton]

This is failing:

sage: a3r=ReflectionGroup(['A',3], base_ring=QQ)
sage: sr=SubwordComplex([1,3,2,1,3,2,1,3,2],a3r.w0)
sage: fr=sr.greedy_facet()
sage: fr.extended_weight_configuration()

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​0becba3	Merge branch 'public/11187' of git://trac.sagemath.org/sage into u/stumpc5/20396
​8927ab9	matrix action is on the right!
​eb2ea75	cleaned the reduced word code
​6fbba18	undo the change to repr methods
​8497f5d	first try to skip elements in the iteration, too slow
​def7015	reorganized the invariant form (still missing an improvement) + fixed two doctests
​ab73bc3	Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
​b5a2c8d	moved all examles back to ReflectionGroup
​e36ddad	added fundamental_weight to coxetergroup implementation
​d6bc459	made all doctests work, but I used a dirty hack to solve the weight configuration

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​dc01066	started to add 'optional - gap3'
​fd0c9cc	added optional gap3
​1537a79	added optional gap3
​a60cf31	added some missing optional gap3
​feebf97	finalized the invariant form
​4955d68	added the missing optional gap3 in the cython file
​c5c43bc	the next round of optional gap3 insertions
​244e6ff	Merge branch 'public/11187' of trac.sagemath.org:sage into public/reflection_groups-11187
​f541349	Some last little beautification.
​a1b3d3b	Merge branch 'u/stumpc5/11187' into u/stumpc5/20402

[git]

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

​0db28d6	fixed doctests that have not been run last week!
​7afc02c	Fixing doctests in combinat/root_system/coxeter_group.py.
​0269425	Blanket fix bare except block.
​9b0ef92	Making it an AttributeError.
​87cdde0	Merge branch 'public/11187' into u/stumpc5/20402
​8d76520	using a cached version self._number_of_reflections to avoid computing it again and again, expecially important in has_descent
​0b6d895	Merge branch 'develop' into public/11187
​e63d2ec	Merge branch 'public/11187' into u/stumpc5/20402

[git]

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

​4bacaea	trivial typo
​fc8a0aa	replaced the wrongly assumed right action by a left action
​ef6dbac	fixed the action on root indices with left and right version
​308f26b	added optional gap3 everywhere
​0b81cd6	added a few missing optional gap3

[stumpc5]

I think this is ready to go once the patchbots are happy!

[git]

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

​0ee1f3b

added a few more missing optional gap3

[tscrim]

-1 to changing all of the examples to only using GAP3/reflection groups. Until GAP3 becomes an optional spkg, it means they become completely untested. Moreover, it is good to make sure the functionality works between different implementations.

I think there are a few things in here which need to be abstracted up to the category, root system code, and/or Coxeter type code. For example, is_crystallographic should be called on the Coxeter type, of which ReflectionGroup does not have and should (or perhaps the Coxeter matrix).

I also do not see the reason why this change is needed:

-                Lambda = {li: coeff[li] * Lambda[li] for li in Lambda}
+                Lambda = {li: coeff[li] * Lambda[li] for li in Lambda.keys()}

as the iteration for a dictionary is over its keys (and the former is faster and more memory efficient). With this change:

-                V_weights.append(pi * fund_weight)
+                # TODO: little hack to distinguish the implementations
+                #       for ReflectionGroups and CoxeterGroup
+                from sage.groups.perm_gps.permgroup_element import PermutationGroupElemen
+                if isinstance(pi,PermutationGroupElement):
+                    V_weights.append( sum(fund_weight[j]*Phi[ (~pi)(j+1)-1 ] for j in ran
+                else:
+                    V_weights.append(pi * fund_weight)

I think it would be better to have the fundamental weights handle the action of the reflection group element.

[stumpc5]

Replying to tscrim:

-1 to changing all of the examples to only using GAP3/reflection groups. Moreover, it is good to make sure the functionality works between different implementations.

The header contains tests that the core functionality works for Coxeter groups, maybe one could add a more elaborate example there, providing examples for more functionality.

But I clearly wrote the code the way I did in close relationshiop to the implementation of reflection groups, and I must confess that I prefer the speed (and indeed I need that speed for my research) over the code being usable by other implementations. I think, it is okay to have the code sort of working for CoxeterGroup, but for example the necessity to introduce a method action_on_root_indices for those tells that there is actually more work to be done to make the implementation work with both without giving up the speed on one, and not introducing unnecessary function overhead on the other.

Until GAP3 becomes an optional spkg, it means they become completely untested.

This should be done soon in my eyes, but I understand that so far I am the only one being desperate to have it.

I think there are a few things in here which need to be abstracted up to the category, root system code, and/or Coxeter type code. For example, is_crystallographic should be called on the Coxeter type, of which ReflectionGroup does not have and should (or perhaps the Coxeter matrix).

A reflection group acting on a real vector space can have the property of being crystallographic or not (whether or not it stabilizes a lattice). I thus think the group itself should have this property.

What do you think of (me) adding this method also to Coxeter groups (in this ticket or another)?

I also do not see the reason why this change is needed:

-                Lambda = {li: coeff[li] * Lambda[li] for li in Lambda}
+                Lambda = {li: coeff[li] * Lambda[li] for li in Lambda.keys()}

as the iteration for a dictionary is over its keys (and the former is faster and more memory efficient).

As we have per default that simple reflections are families rather than dicts (so that iterating over them actually iterates over them), the reflection group implementation also have simple roots and fundamental weights as finite families, so iterating goes over the values. That's what the keys is there for.

With this change:

-                V_weights.append(pi * fund_weight)
+                # TODO: little hack to distinguish the implementations
+                #       for ReflectionGroups and CoxeterGroup

I think it would be better to have the fundamental weights handle the action of the reflection group element.

If you mean, one might have a method act on weight, one could think about it, but the point here is that the action on fundamental weights can be quickly understood using the action on roots, while the general action on weights is not as simple.

I can implement a method act_on_fundamental_weight to factor out the hack, but is that what we actually want?

[git]

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

​2c95a41

added a few more test cases for CoxeterGroup to the header

[stumpc5]

A reflection group acting on a real vector space can have the property of being crystallographic or not (whether or not it stabilizes a lattice). I thus think the group itself should have this property.

What do you think of (me) adding this method also to Coxeter groups (in this ticket or another)?

I gonna for now also use

sage: W = ReflectionGroup(['A',3])
sage: W.coxeter_matrix().is_crystallographic()
True
sage: W = CoxeterGroup(['A',3])
sage: W.coxeter_matrix().is_crystallographic()
True

(without giving up the idea that the property is attached to the group itself).

[git]

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

​803d8b9

replace a hack by using G.coxeter_matrix().is_crystallogrphic()

[stumpc5]

If you mean, one might have a method act on weight, one could think about it, but the point here is that the action on fundamental weights can be quickly understood using the action on roots, while the general action on weights is not as simple.

Let me take that back for now, I'll get back to it...

[git]

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

​bc23f81	fixed the action on root indices, roots, and general vectors
​0ecefc2	renamed action_on_root_indices to act_on_root_indices for name unifications
​63639a6	removed a fixed todo
​f12a61e	added method 'act' to CoxeterGroup and used it in the action on weights, also marked a few more doctests as optional gap3
​52c39d9	fixed one broken doctest in coxeter_group.py

[stumpc5]

Hi Travis, I believe I fixed everything you mentioned except for the fact that I almost completely test using ReflectionGroup's. In particular, I fixed a few hacks and todo's.

The changes to reflection_group_real.py and to coxeter_group.py are not strictly there to get subword complexes to work (though the uniformization is done for that reason). Should I extect those changes into a different ticket, or is everyone okay with having it here?

Beside that, I set it back to needs review.

[tscrim]

It's looking a lot better Christian. Thank you.

However, let me be a bit more stern, I will not set this ticket to a positive review when you essentially remove doctest coverage because gap3 is not an optional package yet (although this argument weakens once it is). Moreover, you can test all of the functionality with standard Sage, which such tests should be localized to each method, not (only) in a class-level test which does the "core" functionality.

For the speed issues, how much of this is making a difference? If it does, you can separate out the important functionality into a separate method, and then subclass the general class which special cases the methods when you use ReflectionGroup.

You are right about the issue with Lambda.

By renaming action_on_root_indices, you need to deprecate it.

I am okay with you adding an is_crystallographic to the group here, but it might be a little strange if the crystallographic-ness of a Coxeter group is different than its Coxeter type/matrix.

Also, instead of act, IIRC there is a method, which I believe is _act_on_ (not to be confused with _acted_upon_), that automatically gets checked by the coercion framework. So it gives you w * la essentially for free. Although

[git]

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

​36ea30e	added _act_on_ to reflection_group_real, fixed a confusion about left/right action, fixed a typo
​283ccf5	using _act_on_ in the subword complex code, and remove the act method for CoxeterGroup again

[stumpc5]

Replying to tscrim:

For the speed issues, how much of this is making a difference?

sage: W = ReflectionGroup(['A',5])
sage: c = W.index_set(); Q = c + tuple(W.w0.coxeter_sorting_word(c))
sage: %time S = SubwordComplex(Q,W.w0)
CPU times: user 42.7 ms, sys: 612 µs, total: 43.3 ms
Wall time: 39.5 ms
sage: len(S)
132
sage: W = CoxeterGroup(['A',5])
sage: c = W.index_set(); Q = c + tuple(W.w0.coxeter_sorting_word(c))
sage: %time S = SubwordComplex(Q,W.w0)
CPU times: user 15.1 s, sys: 84.3 ms, total: 15.1 s
Wall time: 15.1 s
sage: len(S)
132

The complete implementation depends on has_descents and multiplication of elements to be fast (and this will get another boost for ReflectionGroup in #20484), when you %prun the code for CoxeterGroup you don't see a single bottleneck but that it is too slow in many parts (I am not complaining about this speed issue in general, this implementation is uniform for all Coxeter systems, finite or infinite, so that's great and the speed is what one gets there!)

If it does, you can separate out the important functionality into a separate method, and then subclass the general class which special cases the methods when you use ReflectionGroup.

This implementation of subword complexes is not a general implementation that could be moved up the hierarchy, and then a few methods could be replaced for concrete implementations. All the internal core methods are written so that internally it only plays with numbers and permutations of numbers, you only see roots popping out when using the API.

Is is indeed possible to write a toy (in terms of speed) implementation for the category of CoxeterGroups, but I am not the one doing that at the moment -- what I provide is a research level implementation for ReflectionGroup.

However, let me be a bit more stern, I will not set this ticket to a positive review when you essentially remove doctest coverage because gap3 is not an optional package yet (although this argument weakens once it is). Moreover, you can test all of the functionality with standard Sage, which such tests should be localized to each method, not (only) in a class-level test which does the "core" functionality.

Hm -- you see my complaints about that above. On the other hand, I also see your point of getting rotten untested code after a while, and I don't really care if we pollute the documentation with more tests.

By renaming action_on_root_indices, you need to deprecate it.

It was only there for a few months, see #11010, and this method is almost surely not used by anyone so far. You still think it should be deprecated ?

I am okay with you adding an is_crystallographic to the group here, but it might be a little strange if the crystallographic-ness of a Coxeter group is different than its Coxeter type/matrix.

How could crystallographic-ness being different for the group and for its Coxeter type ? See Section 2.8 in Humphreys Coxeter group book for a "proof" that the two are the same. Or am I overseeing something?

[stumpc5]

Also, instead of act, IIRC there is a method, which I believe is _act_on_ (not to be confused with _acted_upon_), that automatically gets checked by the coercion framework. So it gives you w * la essentially for free.

Done, I must admit that I like that way of having an element w in W act on vectors, while I am nervous about this implicitness in the construction that will likely result in bugs.

Although

missing sentence?

[nthiery]

Replying to stumpc5:

Also, instead of act, IIRC there is a method, which I believe is _act_on_ (not to be confused with _acted_upon_), that automatically gets checked by the coercion framework. So it gives you w * la essentially for free.

Done, I must admit that I like that way of having an element w in W act on vectors, while I am nervous about this implicitness in the construction that will likely result in bugs.

Same here; it's nice to have a short hand for actions (and to benefit from coercion!), but I am also uncomfortable giving yet another meaning to the operator '*'.

In any cases, we should keep consistency with Weyl groups. It's currently w.action(l) there (not w.act(l) btw); if we switch to _act_on_, then we should do it consistently everywhere.

Cheers,

[nthiery]

Replying to stumpc5:

How could crystallographic-ness being different for the group and for its Coxeter type ? See Section 2.8 in Humphreys Coxeter group book for a "proof" that the two are the same.

I guess that's Travis's point: mathematically, they two should be the same. If there are two methods implementing this fact, then we need to make sure that they remain consistent.

[stumpc5]

Replying to nthiery:

In any cases, we should keep consistency with Weyl groups. It's currently w.action(l) there (not w.act(l) btw); if we switch to _act_on_, then we should do it consistently everywhere.

Term-wise, I think that w acts on l, while there is an action of W on l. But I am equally okay to use w.action(l) for consistency.

I don't get your point of switching: what is wrong with having the method action and then using this method in the body of _act_on_?

[git]

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

​295d784

replace act* by action*

[nthiery]

Replying to stumpc5:

I don't get your point of switching: what is wrong with having the method action and then using this method in the body of _act_on_?

Just that I am not sure that we want to overload/polute '*' with this; and if we do, it should be done consistently for Weyl groups as well.

Cheers

[stumpc5]

Replying to nthiery:

Replying to stumpc5:

I don't get your point of switching: what is wrong with having the method action and then using this method in the body of _act_on_?

Just that I am not sure that we want to overload/polute '*' with this; and if we do, it should be done consistently for Weyl groups as well.

One reason in favour is that elements in CoxeterGroup are matrices, so they use '*' anyways. Otherwise, I would have to re-enable the method action there which is simply using '*'.

One reason against is that for complex reflection groups, the action on the space and on its dual are different. And since both are represented by vectors (in the dual bases {ei} and {xi}), the '*' does not see this for now. But one could have an optional argument in_dual for action.

[nthiery]

Oh, I had not noticed that CoxeterMatrixGroup were acting on plain vectors with '*'. As you mention this is very ambiguous. For a Weyl group this is even worst: is the vector interpreted as in the span of the (co)roots? of the (co)weights? in the ambient space?

For now, I'd rather keep the notations as explicit as possible (in particular, it's easier to document a method .action than an overloaded operator). And leave us room in the future to overload '*', either by default, or upon explicit request from the user.

[stumpc5]

Replying to nthiery:

Oh, I had not noticed that CoxeterMatrixGroup were acting on plain vectors with '*'.

Yes, the elements are matrices which act on vectors :-)

As you mention this is very ambiguous. For a Weyl group this is even worst: is the vector interpreted as in the span of the (co)roots? of the (co)weights? in the ambient space?

I agree.

For now, I'd rather keep the notations as explicit as possible (in particular, it's easier to document a method .action than an overloaded operator). And leave us room in the future to overload '*', either by default, or upon explicit request from the user.

One could define _act_on_ in different ways for elements in the root/coroot/weight/coweight space, and not at all for plain vectors. But on the reflection group side there is no class for elements in V and in V^* yet. I am okay with both: considering the action on vectors for now on elements in V, or removing the coercion for now.

[tscrim]

Replying to stumpc5:

Replying to tscrim:

For the speed issues, how much of this is making a difference?

The complete implementation depends on has_descents and multiplication of elements to be fast (and this will get another boost for ReflectionGroup in #20484), when you %prun the code for CoxeterGroup you don't see a single bottleneck but that it is too slow in many parts (I am not complaining about this speed issue in general, this implementation is uniform for all Coxeter systems, finite or infinite, so that's great and the speed is what one gets there!)

That is not answering the question I asked. I asked about having one additional level of indirection to have a specialized function for when the input is an instance of RealReflectionGroup.

If it does, you can separate out the important functionality into a separate method, and then subclass the general class which special cases the methods when you use ReflectionGroup.

This implementation of subword complexes is not a general implementation that could be moved up the hierarchy, and then a few methods could be replaced for concrete implementations. All the internal core methods are written so that internally it only plays with numbers and permutations of numbers, you only see roots popping out when using the API.

I'm sure there are only some key parts of it which are written that strongly depend on the input format. These could be abstracted to work in general with a special subclass which has the specialized method or into the implementations of the Coxeter group. This is a standard design pattern for code that I've seen many times over (we even have the former in Sage's matrix code).

Is is indeed possible to write a toy (in terms of speed) implementation for the category of CoxeterGroups, but I am not the one doing that at the moment -- what I provide is a research level implementation for ReflectionGroup.

In many ways, we are beating a dead horse as you have basically done what I am asking for already (with the specializing being done in the different implementations of a Coxeter group).

However, let me be a bit more stern, I will not set this ticket to a positive review when you essentially remove doctest coverage because gap3 is not an optional package yet (although this argument weakens once it is). Moreover, you can test all of the functionality with standard Sage, which such tests should be localized to each method, not (only) in a class-level test which does the "core" functionality.

Hm -- you see my complaints about that above. On the other hand, I also see your point of getting rotten untested code after a while, and I don't really care if we pollute the documentation with more tests.

Then let's leave those tests in. That is the only thing I am asking for here.

By renaming action_on_root_indices, you need to deprecate it.

It was only there for a few months, see #11010, and this method is almost surely not used by anyone so far. You still think it should be deprecated ?

I am pretty sure it appears in a stable release (i.e., 7.1), so yes.

[tscrim]

Replying to nthiery:

Replying to stumpc5:

How could crystallographic-ness being different for the group and for its Coxeter type ? See Section 2.8 in Humphreys Coxeter group book for a "proof" that the two are the same.

I guess that's Travis's point: mathematically, they two should be the same. If there are two methods implementing this fact, then we need to make sure that they remain consistent.

Well, my interpretation of Christian's first comment was this was a property of the realization of the group, not of the group itself. So the group's is_crystallographic should just call that of its Coxeter type/matrix.

[tscrim]

Replying to nthiery:

Replying to stumpc5:

I don't get your point of switching: what is wrong with having the method action and then using this method in the body of _act_on_?

Just that I am not sure that we want to overload/polute '*' with this; and if we do, it should be done consistently for Weyl groups as well.

I have been told by a few people that they would want this feature (in the finite Coxeter group setting) as it is natural and corresponds to what we would write mathematically.

[tscrim]

Replying to nthiery:

Oh, I had not noticed that CoxeterMatrixGroup were acting on plain vectors with '*'. As you mention this is very ambiguous. For a Weyl group this is even worst: is the vector interpreted as in the span of the (co)roots? of the (co)weights? in the ambient space?

For CoxeterMatrixGroup, it is given as a (faithful) representation, so the basis of a vector space is (implicitly) given, which is the roots. For the Weyl group, it is also given as a representation, so again, we have a basis which we define the action on. So I see no ambiguity, and in fact, I think the Weyl groups are very explicit about this.

For now, I'd rather keep the notations as explicit as possible (in particular, it's easier to document a method .action than an overloaded operator). And leave us room in the future to overload '*', either by default, or upon explicit request from the user.

I agree, that it is easier to document action() than an overloaded operator, but I think it is only marginally easier. The first thing I would (and do) look at is the class-level documentation for what I can do with a particular object. So if we have examples in there that describe the action of *, I think that makes it easily accessible what we are doing, in addition to the naturality of the action. Or am I forgetting something (again, in the [finite] Coxeter group setting)?

[nthiery]

Replying to tscrim:

I have been told by a few people that they would want this feature (in the finite Coxeter group setting) as it is natural and corresponds to what we would write mathematically.

Well, mathematicaly, I tend to write v.s_i, not vs_i, precisely to raise the potential ambiguity (this is an action, not a multiplication)

[stumpc5]

Replying to tscrim:

In many ways, we are beating a dead horse as you have basically done what I am asking for already (with the specializing being done in the different implementations of a Coxeter group).

Well, let's keep it as it is for now then.

Then let's leave those tests in. That is the only thing I am asking for here.

Fine.

I am pretty sure it appears in a stable release (i.e., 7.1), so yes.

After Nicolas' comment that WeylGroup uses .action, I moved it back to action*...

my interpretation of Christian's first comment was this was a property of the realization of the group, not of the group itself. So the group's is_crystallographic should just call that of its Coxeter type/matrix.

Yes, for real groups I only wanted the is_crystallographic of the group to call the one of the Coxeter type/matrix. But complex reflection groups can still be crystallographic (though they only are if they are real and crystallographic), so they deserve the method is_crystallographic without having a Coxeter type/Coxeter matrix attached to them.

So I see no ambiguity, and in fact, I think the Weyl groups are very explicit about this.

But what if w is an element of the group and v is a *Sage vector*. Does it represent an element in the vector space spanned the simple roots, or by the simple coroots, or by the fundamental weights, or by the fundamental coweights? Or does that not matter since the actions are all the same?

[tscrim]

Replying to stumpc5:

Replying to tscrim:

my interpretation of Christian's first comment was this was a property of the realization of the group, not of the group itself. So the group's is_crystallographic should just call that of its Coxeter type/matrix.

Yes, for real groups I only wanted the is_crystallographic of the group to call the one of the Coxeter type/matrix. But complex reflection groups can still be crystallographic (though they only are if they are real and crystallographic), so they deserve the method is_crystallographic without having a Coxeter type/Coxeter matrix attached to them.

Ah, I see. This good.

So I see no ambiguity, and in fact, I think the Weyl groups are very explicit about this.

But what if w is an element of the group and v is a *Sage vector*. Does it represent an element in the vector space spanned the simple roots, or by the simple coroots, or by the fundamental weights, or by the fundamental coweights? Or does that not matter since the actions are all the same?

Sage's vectors exists expressed in some canonical basis, and by doing matrix multiplication, there is an implicit assumption that these bases are the same. In a way, what you are advocating for is that we need to explicitly specify the matrix for any matrix m and v and check those are the same anytime we write m * v. The various subclasses of CombinatorialFreeModule does this by saying the (parent) class corresponds to a choice of basis, but this is not, and really can never be, the case for Sage's vectors, where there is an assumption of a canonical basis. In fact, because these matrices are representations of a vector space given in terms of a basis, that basis is canonical as far as Sage's vectors are concerned. (I hope that makes some sense...)

[stumpc5]

Sage's vectors exists expressed in some canonical basis, and by doing matrix multiplication, there is an implicit assumption that these bases are the same.

I'd say that multiplying a matrix M with a vector v (as a tuple in distinction to vector space elements) is well-defined and completely independent on bases. So that's totally fine to do as M*v.

Only if the matrix is representing a linear map and the tuple represents a vector space element there is an assumption on both being represented in the same basis. When you now represent a Coxeter group element as a matrix you make a choice of basis (which might be the root basis, its dual, some linearly independent vectors of an "ambient space", or any other) This is now what you stick this matrix to, but when you do w*v, one does not specify the matrix that represents w in some basis, so this operation is ambiguous, as it didn't specify on which space w acts here (i.e., it is not clear in which basis you represent w as a matrix for that action.

For ReflectionGroup I just thought that the best is to have the method .action to take two parameters side being "left" or "right" and on_space being "primal" or "dual".

Beside that, I am okay with providing the coercion to act on the primal, but am also okay with removing it again (I am slightly in favour of keeping it though).

[tscrim]

Replying to stumpc5:

Sage's vectors exists expressed in some canonical basis, and by doing matrix multiplication, there is an implicit assumption that these bases are the same.

I'd say that multiplying a matrix M with a vector v (as a tuple in distinction to vector space elements) is well-defined and completely independent on bases. So that's totally fine to do as M*v.

No, that is not true except in the most abstract sense of a linear morphism and an element of a vector space. A matrix comes with an implicit choice of a basis, and when we write vectors as tuples, there is an implicit choice of a basis as well. For example, if M is a diagonalizable matrix acting on a vector space V, we can find some basis such that M can be expressed as acting on scalars on that basis. While the diagonal matrix and M are different matrices, they define the same linear automorphism on V, and hence, have the same action on a vector. Yet, to do the computation, we need to express the vector in terms of our basis.

Only if the matrix is representing a linear map and the tuple represents a vector space element there is an assumption on both being represented in the same basis. When you now represent a Coxeter group element as a matrix you make a choice of basis (which might be the root basis, its dual, some linearly independent vectors of an "ambient space", or any other) This is now what you stick this matrix to, but when you do w*v, one does not specify the matrix that represents w in some basis, so this operation is ambiguous, as it didn't specify on which space w acts here (i.e., it is not clear in which basis you represent w as a matrix for that action.

That is not how a CoxeterMatrixGroup or a WeylGroup is defined. It is given precisely by that choice of representation/matrix, so in a way, it is a Coxeter system along with a specified representation.

Also, any v (implicitly) carries with it a vector space (not up to isomorphism), and we are checking to see if the Coxeter group has a defined action on that vector space. An alternative viewpoint is if v is a Sage vector, in a way, we are only considering that element up to isomorphism, so we have lost some information (but again, that is if we don't fix a representation which makes a canonical choice of basis for the vector space). In contrast, for v being an element of the root/weight/ambient space, we have an explicit basis and we have defined where the roots are in these, so the action is well-defined and explicit.

For ReflectionGroup I just thought that the best is to have the method .action to take two parameters side being "left" or "right" and on_space being "primal" or "dual".

Beside that, I am okay with providing the coercion to act on the primal, but am also okay with removing it again (I am slightly in favour of keeping it though).

In case there is any ambiguity, I'm also only really advocating for using * in the real reflection group setting. Moreover, I think we should avoid using Sage vectors for the roots (at least in the generic parents) because there is some ambiguity about their basis.

[stumpc5]

Replying to tscrim:

No, that is not true except in the most abstract sense of a linear morphism and an element of a vector space. A matrix comes with an implicit choice of a basis, and when we write vectors as tuples, there is an implicit choice of a basis as well.

The point I wanted to make is that given a field k, you can define an nxn matrix M over k as a table of entries in k and you can define an n-tuple to be an n-tuple x of entries in k, and you can multiply them Mx by some explicit row-column definition. At this point, there is no basis involved. One can even enrich the set k^{n with a vector space structure and then see the multiplication by M at a linear map without ever talking about bases. And this multiplication is defined in Sage, even if k is not a field so there is no as simple concept of bases.}

Only if one wants to consider a k-linear map phi : V -> V on a vector space V over k as a matrix, then the basis comes into play.

Of course one could say that k^{n has an implicit basis in which the above matrix represents a linear map, but that is not quite adequate since k}n comes with a canonical standard basis, so there is no choice of an implicit basis.

For example, if M is a diagonalizable matrix acting on a vector space V,

in your argument, you always assume a general vector space V, there I agree that you play with explicit or implicit bases.

That is not how a CoxeterMatrixGroup or a WeylGroup is defined. It is given precisely by that choice of representation/matrix, so in a way, it is a Coxeter system along with a specified representation.

That's right, and I am fine with arguing that this action of the group should be used when doing w*v. But there are still other spaces involved on which the group also acts, so if you do not specify which space v lives in one has to implicitly assume it to be this representation.

In case there is any ambiguity, I'm also only really advocating for using * in the real reflection group setting.

My proposition for reflection groups at the moment is

• have a method .action(vec, side="left", on_space="primal") that does the appropriate action, and
• have ._act_on_(vec, self_on_left) defined as .action(vec, side=side, on_space="primal") where the side is set depending on self_on_left being True or False.

Moreover, I think we should avoid using Sage vectors for the roots (at least in the generic parents) because there is some ambiguity about their basis.

I agree, but I have not yet implemented root spaces and coroot spaces for crg's. So I don't have anything better to provide for now than vectors. But that's on the todo list...

[stumpc5]

One quick question outside of finite type Weyl and Coxeter groups W: is it correct that the actions of W on V and on V^* are the same. This is, the image of (x1,...,xn) under w is the same for (x1,...,xn) being a vector in V expressed in the basis {ei} and being a vector in V^* expressed in the dual basis {xi}?

[tscrim]

Replying to stumpc5:

Replying to tscrim: Of course one could say that kⁿ has an implicit basis in which the above matrix represents a linear map, but that is not quite adequate since kⁿ comes with a canonical standard basis, so there is no choice of an implicit basis.

There is a standard basis, but it is not canonical.

That is not how a CoxeterMatrixGroup or a WeylGroup is defined. It is given precisely by that choice of representation/matrix, so in a way, it is a Coxeter system along with a specified representation.

That's right, and I am fine with arguing that this action of the group should be used when doing w*v. But there are still other spaces involved on which the group also acts, so if you do not specify which space v lives in one has to implicitly assume it to be this representation.

This is no more implicit than the relationship with the chosen basis of a matrix and a vector. I still contend that by fixing a representation, we now have a canonical basis for V (and we implicitly assume v is an element of V). For good reasons, we can't tell if v is to be considered an element in the representation or some other (isomorphic) vector space.

In case there is any ambiguity, I'm also only really advocating for using * in the real reflection group setting.

My proposition for reflection groups at the moment is

• have a method .action(vec, side="left", on_space="primal") that does the appropriate action, and
• have ._act_on_(vec, self_on_left) defined as .action(vec, side=side, on_space="primal") where the side is set depending on self_on_left being True or False.

That is good with me.

[stumpc5]

Replying to tscrim:

There is a standard basis, but it is not canonical.

Okay, let's agree that we both know the situation, but that we do not agree which structure to emphasize...

• have a method .action(vec, side="left", on_space="primal") that does the appropriate action, and
• have ._act_on_(vec, self_on_left) defined as .action(vec, side=side, on_space="primal") where the side is set depending on self_on_left being True or False.

That is good with me.

Good!

@Nicolas, do you agree this to be reasonable or do even not like this usage of the coercion?

[nthiery]

Replying to stumpc5:

@Nicolas, do you agree this to be reasonable or do even not like this usage of the coercion?

When in doubt, I tend to take the path that is easier to change in the future in case one change one's mind after gaining more experience. In this case, it's easier to add the coercion later on than to remove it, or replace it by something else.

But that's no strong opinion. Proceed as you believe is right.

Cheers,

[git]

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

​dd4413d	edited the reflection representation and its dual -- still to be tested
​29842f6	still working on the left/right primal/dual repr
​619ba6e	doubled all doctests to ReflectionGroup and CoxeterGroup

[stumpc5]

I am still struggling with the left/right action -- here, we want left actions (i.e., matrix*vector), but the standard for reflection groups is right action. I know how to turn left to right action for real and for well-generated groups, but still don't get it right to have it for the badly generated groups.

Actually, this shouldn't hold this ticket of, but I haven't resorted things yet...

[git]

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

​f0353a5

working out the left/right action

[git]

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

​5076f0b

Merge branch 'develop' into u/stumpc5/20402

[git]

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

​f25f5d6	take over the implementation from #20402
​9e557e2	fixing a few doctests
​c0ebcca	merged 20521
​b5a56cc	added indirect doctest flags
​8ffeaf9	Merge branch 'u/stumpc5/20521' into u/stumpc5/20402

[git]

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

​eaa9da0	Some minor reviewer changes.
​e71529e	minor improvement of as_matrix + removal of todo note
​03b1ae0	Merge branch 'u/stumpc5/20521' into u/stumpc5/20402

[stumpc5]

I just rechecked -- beside the changes now moved to #20521 and the few changes in coxeter_groups.py, there are almost entirely newly added doctests for ReflectionGroup.

[tscrim]

Instead of

print "Caution: the Minkowski summands are build with rational vertices."

(which it should be print("foo") to be Python3 compatible) you should use Sage's warning mechanism:

from warnings import warn
warn("foo", RuntimeWarning)

Otherwise LGTM.

[git]

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

​71eba72

using python warnings

[stumpc5]

Done, thx also here! -- more improvements to come hopefully soon...

[tscrim]

Frédéric, Nicolas, anything else before setting this to a positive review?

[stumpc5]

A quick *ping* here to check whether we can get this ticket merged...

[tscrim]

If there is possibly anything else, then they can set this back from a positive review.