Opened 4 years ago

Closed 4 years ago

#20402 closed enhancement (fixed)

Make subword complexes compatible with real reflection groups

Reported by: stumpc5 Owned by:
Priority: major Milestone: sage-7.2
Component: combinatorics Keywords: reflection group, coxeter group, subword complex, days80
Cc: tscrim, chapoton, nthiery, vripoll Merged in:
Authors: Christian Stump Reviewers: Frédéric Chapoton, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 71eba72 (Commits) Commit: 71eba72e896ba17314bcab6965f33005d02a26e4
Dependencies: #20521 Stopgaps:

Description

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.

Change History (67)

comment:1 Changed 4 years ago by stumpc5

  • Dependencies set to #11187

comment:2 Changed 4 years ago by stumpc5

  • Branch set to u/stumpc5/20402

comment:3 Changed 4 years ago by git

  • Commit set to 5ae3b7f793ad96f9f39999b158398434009435da

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

2d70fabtrac #11187 more doc tuning
a04b9c8Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
9c96d33added ST type casting for real groups + documentation of crg's
5b1f2b0Merge branch 'u/stumpc5/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
d4e7a61working through the doctests for complex groups
d7b8c7dfixing all doctests
7c9d700Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
85d0ce1fixed a typo in the doc
521d50bMerge branch 'u/stumpc5/11187' into u/stumpc5/20402
5ae3b7fmarked a missing doctest + fixed a bug to show type C2

comment:4 Changed 4 years ago by git

  • Commit changed from 5ae3b7f793ad96f9f39999b158398434009435da to df55cdd653d443594a0726b4e1e6e97c539fb0e9

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

72082b1fixed a bug in noncrossing partition lattice and reflection/absolute order
844f450Merge branch 'u/stumpc5/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
d425669Fixing failures and some other things.
87cd989fixed one doctest in category complex reflection group
05a8ab411187: fixed trivial doctest failures
32bf1ae11187: cleanup of the organization of the various axioms (WellGenerated, ...) for complex/generalized reflection groups + documentation improvements
73276caMerge branch 'u/tscrim/11187' of trac.sagemath.org:sage into t/11187/11187
e074050merged
b572c74fixed a missing doctest
df55cddmerged the newest version of 11187

comment:5 Changed 4 years ago by git

  • Commit changed from df55cdd653d443594a0726b4e1e6e97c539fb0e9 to 19271510dd0f4b3ea6480fb9e6d15d70383440fc

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

1927151fixed a bug in simple_root_index

comment:6 Changed 4 years ago by stumpc5

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

comment:7 Changed 4 years ago by 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()

comment:8 Changed 4 years ago by git

  • Commit changed from 19271510dd0f4b3ea6480fb9e6d15d70383440fc to d6bc459825560776ea95c8d3e34d32b2fb78d059

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

0becba3Merge branch 'public/11187' of git://trac.sagemath.org/sage into u/stumpc5/20396
8927ab9matrix action is on the right!
eb2ea75cleaned the reduced word code
6fbba18undo the change to repr methods
8497f5dfirst try to skip elements in the iteration, too slow
def7015reorganized the invariant form (still missing an improvement) + fixed two doctests
ab73bc3Merge branch 'u/stumpc5/11187' into u/stumpc5/20402
b5a2c8dmoved all examles back to ReflectionGroup
e36ddadadded fundamental_weight to coxetergroup implementation
d6bc459made all doctests work, but I used a dirty hack to solve the weight configuration

comment:9 Changed 4 years ago by git

  • Commit changed from d6bc459825560776ea95c8d3e34d32b2fb78d059 to a1b3d3ba5055e4217d8cecd5b09bd51b078802f2

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

dc01066started to add 'optional - gap3'
fd0c9ccadded optional gap3
1537a79added optional gap3
a60cf31added some missing optional gap3
feebf97finalized the invariant form
4955d68added the missing optional gap3 in the cython file
c5c43bcthe next round of optional gap3 insertions
244e6ffMerge branch 'public/11187' of trac.sagemath.org:sage into public/reflection_groups-11187
f541349Some last little beautification.
a1b3d3bMerge branch 'u/stumpc5/11187' into u/stumpc5/20402

comment:10 Changed 4 years ago by git

  • Commit changed from a1b3d3ba5055e4217d8cecd5b09bd51b078802f2 to e63d2ece579d1afd1df9c4afcf951407e6fbe36d

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

0db28d6fixed doctests that have not been run last week!
7afc02cFixing doctests in combinat/root_system/coxeter_group.py.
0269425Blanket fix bare except block.
9b0ef92Making it an AttributeError.
87cdde0Merge branch 'public/11187' into u/stumpc5/20402
8d76520using a cached version self._number_of_reflections to avoid computing it again and again, expecially important in has_descent
0b6d895Merge branch 'develop' into public/11187
e63d2ecMerge branch 'public/11187' into u/stumpc5/20402

comment:11 Changed 4 years ago by stumpc5

  • Summary changed from Make real reflection group compatible with subword complex to Make subword complexes compatible with real reflection groups

comment:12 Changed 4 years ago by git

  • Commit changed from e63d2ece579d1afd1df9c4afcf951407e6fbe36d to 0b81cd6ccf77c652672ca75aa693123ca77bd93c

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

4bacaeatrivial typo
fc8a0aareplaced the wrongly assumed right action by a left action
ef6dbacfixed the action on root indices with left and right version
308f26badded optional gap3 everywhere
0b81cd6added a few missing optional gap3

comment:13 Changed 4 years ago by stumpc5

  • Status changed from new to needs_review

comment:14 Changed 4 years ago by stumpc5

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

comment:15 Changed 4 years ago by stumpc5

  • Keywords reflection days80 added

comment:16 Changed 4 years ago by git

  • Commit changed from 0b81cd6ccf77c652672ca75aa693123ca77bd93c to 0ee1f3bf9c772352b9a7994afc7f4359e618b309

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

0ee1f3badded a few more missing optional gap3

comment:17 follow-up: Changed 4 years ago by tscrim

  • Status changed from needs_review to needs_work

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

comment:18 in reply to: ↑ 17 ; follow-ups: Changed 4 years ago by 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?

comment:19 Changed 4 years ago by git

  • Commit changed from 0ee1f3bf9c772352b9a7994afc7f4359e618b309 to 2c95a41c537c6625ed6abdf03fd5bbedc9da21cb

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

2c95a41added a few more test cases for CoxeterGroup to the header

comment:20 in reply to: ↑ 18 Changed 4 years ago by 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).

comment:21 Changed 4 years ago by git

  • Commit changed from 2c95a41c537c6625ed6abdf03fd5bbedc9da21cb to 803d8b9226e376cbd777f4bb1d1ef67342d289fd

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

803d8b9replace a hack by using G.coxeter_matrix().is_crystallogrphic()

comment:22 in reply to: ↑ 18 Changed 4 years ago by 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...

comment:23 Changed 4 years ago by git

  • Commit changed from 803d8b9226e376cbd777f4bb1d1ef67342d289fd to 52c39d9ef149ee6826cb3f8f06b7aa7582d49f14

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

bc23f81fixed the action on root indices, roots, and general vectors
0ecefc2renamed action_on_root_indices to act_on_root_indices for name unifications
63639a6removed a fixed todo
f12a61eadded method 'act' to CoxeterGroup and used it in the action on weights, also marked a few more doctests as optional gap3
52c39d9fixed one broken doctest in coxeter_group.py

comment:24 Changed 4 years ago by stumpc5

  • Status changed from needs_work to needs_review

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.

comment:25 Changed 4 years ago by tscrim

  • Status changed from needs_review to needs_work

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

comment:26 Changed 4 years ago by git

  • Commit changed from 52c39d9ef149ee6826cb3f8f06b7aa7582d49f14 to 283ccf598079150e16406adc6a5a55b519f8ec26

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

36ea30eadded _act_on_ to reflection_group_real, fixed a confusion about left/right action, fixed a typo
283ccf5using _act_on_ in the subword complex code, and remove the act method for CoxeterGroup again

comment:27 follow-ups: Changed 4 years ago by 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?

comment:28 follow-up: Changed 4 years ago by 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?

comment:29 in reply to: ↑ 28 ; follow-up: Changed 4 years ago by 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,

Last edited 4 years ago by stumpc5 (previous) (diff)

comment:30 in reply to: ↑ 27 ; follow-up: Changed 4 years ago by 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.

comment:31 in reply to: ↑ 29 ; follow-up: Changed 4 years ago by 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_?

Last edited 4 years ago by stumpc5 (previous) (diff)

comment:32 Changed 4 years ago by git

  • Commit changed from 283ccf598079150e16406adc6a5a55b519f8ec26 to 295d784db0ae24bed97ed7b4d3777df9dbd652c2

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

295d784replace act* by action*

comment:33 in reply to: ↑ 31 ; follow-ups: Changed 4 years ago by 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

comment:34 in reply to: ↑ 33 Changed 4 years ago by 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.

comment:35 follow-ups: Changed 4 years ago by 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.

Last edited 4 years ago by stumpc5 (previous) (diff)

comment:36 in reply to: ↑ 35 Changed 4 years ago by 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.

comment:37 in reply to: ↑ 27 Changed 4 years ago by 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.

comment:38 in reply to: ↑ 30 Changed 4 years ago by 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.

comment:39 in reply to: ↑ 33 ; follow-up: Changed 4 years ago by 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.

comment:40 in reply to: ↑ 35 Changed 4 years ago by 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)?

comment:41 in reply to: ↑ 39 Changed 4 years ago by 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)

comment:42 follow-up: Changed 4 years ago by 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?

comment:43 in reply to: ↑ 42 Changed 4 years ago by 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...)

comment:44 follow-up: Changed 4 years ago by 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).

Last edited 4 years ago by stumpc5 (previous) (diff)

comment:45 in reply to: ↑ 44 ; follow-up: Changed 4 years ago by 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.

comment:46 in reply to: ↑ 45 ; follow-up: Changed 4 years ago by 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 kn 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 kn has an implicit basis in which the above matrix represents a linear map, but that is not quite adequate since kn 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...

comment:47 Changed 4 years ago by 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}?

Last edited 4 years ago by stumpc5 (previous) (diff)

comment:48 in reply to: ↑ 46 ; follow-up: Changed 4 years ago by tscrim

Replying to stumpc5:

Replying to tscrim: Of course one could say that kn has an implicit basis in which the above matrix represents a linear map, but that is not quite adequate since kn 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.

comment:49 in reply to: ↑ 48 ; follow-up: Changed 4 years ago by 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?

comment:50 in reply to: ↑ 49 Changed 4 years ago by 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,

comment:51 Changed 4 years ago by git

  • Commit changed from 295d784db0ae24bed97ed7b4d3777df9dbd652c2 to 619ba6e8422ce14b34cbfed3d9f982a72cf27183

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

dd4413dedited the reflection representation and its dual -- still to be tested
29842f6still working on the left/right primal/dual repr
619ba6edoubled all doctests to ReflectionGroup and CoxeterGroup

comment:52 Changed 4 years ago by 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...

comment:53 Changed 4 years ago by git

  • Commit changed from 619ba6e8422ce14b34cbfed3d9f982a72cf27183 to f0353a5ff43a9c1c5b113379513350a194416dc8

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

f0353a5working out the left/right action

comment:54 Changed 4 years ago by git

  • Commit changed from f0353a5ff43a9c1c5b113379513350a194416dc8 to 5076f0bfcaae0e7592262d1bddc0df9ff5452230

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

5076f0bMerge branch 'develop' into u/stumpc5/20402

comment:55 Changed 4 years ago by stumpc5

  • Dependencies changed from #11187 to #11187, #20521

comment:56 Changed 4 years ago by git

  • Commit changed from 5076f0bfcaae0e7592262d1bddc0df9ff5452230 to 8ffeaf9449529ed0f1d05007fc16a3ae4c5143f5

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

f25f5d6take over the implementation from #20402
9e557e2fixing a few doctests
c0ebccamerged 20521
b5a56ccadded indirect doctest flags
8ffeaf9Merge branch 'u/stumpc5/20521' into u/stumpc5/20402

comment:57 Changed 4 years ago by stumpc5

  • Dependencies changed from #11187, #20521 to #20521
  • Status changed from needs_work to needs_review

comment:58 Changed 4 years ago by git

  • Commit changed from 8ffeaf9449529ed0f1d05007fc16a3ae4c5143f5 to 03b1ae00fbf0857b4ee29e819008d01f751dbdae

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

eaa9da0Some minor reviewer changes.
e71529eminor improvement of as_matrix + removal of todo note
03b1ae0Merge branch 'u/stumpc5/20521' into u/stumpc5/20402

comment:59 Changed 4 years ago by 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.

comment:60 Changed 4 years ago by 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.

comment:61 Changed 4 years ago by git

  • Commit changed from 03b1ae00fbf0857b4ee29e819008d01f751dbdae to 71eba72e896ba17314bcab6965f33005d02a26e4

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

71eba72using python warnings

comment:62 Changed 4 years ago by stumpc5

  • Reviewers set to Frederic Chapoton, Travis Scrimshaw

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

comment:63 Changed 4 years ago by tscrim

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

comment:64 Changed 4 years ago by tscrim

  • Reviewers changed from Frederic Chapoton, Travis Scrimshaw to Frédéric Chapoton, Travis Scrimshaw

comment:65 Changed 4 years ago by stumpc5

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

comment:66 Changed 4 years ago by tscrim

  • Status changed from needs_review to positive_review

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

comment:67 Changed 4 years ago by vbraun

  • Branch changed from u/stumpc5/20402 to 71eba72e896ba17314bcab6965f33005d02a26e4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.