Opened 5 years ago

Closed 4 years ago

#12774 closed enhancement (fixed)

various enhancements for Coxeter and Weyl groups

Reported by: mshimo Owned by: sage-combinat
Priority: major Milestone: sage-5.8
Component: combinatorics Keywords: coxeter group, weyl group, days45
Cc: nthiery, aschilling Merged in: sage-5.8.beta0
Authors: Mark Shimozono Reviewers: Christian Stump, Anne Schilling
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by mshimo)

Various enhancements to Coxeter groups and Weyl groups.

  1. Computes inversions for Coxeter and Weyl groups. They occur in three forms: reflections, roots, and coroots.

New Coxeter group element methods:
categories/coxeter_groups.py

apply_conjugation_by_simple_reflection
inversions_as_reflections
left_inversions_as_reflections

New Weyl group element methods:
categories/weyl_groups.py

reflection_to_root
reflection_to_coroot
inversions

New root space element method:
combinat/root_system/root_space.py

associated_reflection

Bruhat covering relations have an associated inversion. Accordingly, we have added versions of the Coxeter group element methods bruhat_lower_covers and bruhat_upper_covers which incorporate the inversion data:

New Coxeter group element methods:
categories/coxeter_groups.py

bruhat_lower_covers_reflections
bruhat_upper_covers_reflections

New Weyl group element methods:
categories/weyl_groups.py

bruhat_lower_covers_coroots
bruhat_upper_covers_coroots

  1. Installs the Demazure or 0-Hecke product for Coxeter groups

New Coxeter group parent method:
categories/coxeter_groups.py

demazure_product

New Coxeter group element methods:
categories/coxeter_groups.py

apply_demazure_product
min_demazure_product_greater

  1. Computes canonical lifts from quotients by parabolic subgroups.

This requires Deodhar's recovery of the Bruhat order on a Coxeter group from that on a parabolic subgroup and the quotient by that subgroup.

New Coxeter group element methods:
categories/coxeter_groups.py

deodhar_factor_element
deodhar_lift_up
deodhar_lift_down

  1. Small changes for root systems

sage/combinat/root_system/root_lattice_realizations.py:
new parent method:
positive_roots_by_height
modified the calling convention for weyl_action

sage/combinat/root_system/root_space.py:
new element method:
max_coroot_le

Attachments (1)

trac_12774-coxeter-ms.patch (76.9 KB) - added by mshimo 4 years ago.

Download all attachments as: .zip

Change History (26)

comment:1 Changed 5 years ago by mshimo

  • Description modified (diff)

comment:2 Changed 5 years ago by mshimo

  • Cc sage-combinat-devel added
  • Description modified (diff)
  • Status changed from new to needs_review

comment:3 Changed 5 years ago by mshimo

  • Description modified (diff)

comment:4 Changed 5 years ago by stumpc5

  • Dependencies #6588, #12667 deleted
  • Reviewers set to Christian Stump

I went through your changes for Coxeter groups -- it looks nice and clean so far! I attach a review patch with several minor modifications. I used your patch from the combinat queue, so please update the one here if necessary. Also, please update the header of the patch file (concerns auther and dependencies).

Best, Christian

comment:5 Changed 5 years ago by stumpc5

Hi Mark,

I also went through categories/weyl_groups and made some minor changes. The only interesting is: I merged reflection_to_coroot into reflection_to_root and added an optional argument.

I hope to finish my review tonight...

btw: the patch needs to be rebased for sage-5.3.beta0 once we finish it.

Best, Christian

comment:6 Changed 5 years ago by stumpc5

  • Cc nthiery aschilling added; sage-combinat-devel removed

Hi,

concerning the modifications in RootLatticeRealizations:

  • why don't we move this file into categories? (this might be answered somewhere else but I don't remember right now)
  • shouldn't we implement the various methods for roots (roots, positive_roots, negative_roots, -_parabolic, -_nonparabolic, ...) right away as well for general Coxeter groups? It looks like we are not very far from that anyway (I actually do some rudimentary implementation in my other patch on Coxeter groups, but this part would perfectly fit here)

Christian

comment:7 Changed 5 years ago by chapoton

apply trac_12774-coxeter-ms-v2.patch

comment:8 Changed 5 years ago by chapoton

apply trac_12774-coxeter-ms-v2.patch

comment:9 follow-up: Changed 5 years ago by chapoton

apply trac_12774-coxeter-ms-v2.patch

I have just folded and rebased this patch. The bot seems to be green and happy.

This looks good to me. Anne, Nicolas, Christian, do you want to have a look ?

comment:10 Changed 5 years ago by chapoton

apply trac_12774-coxeter-ms-v2.patch

I have corrected the deprecations

comment:11 in reply to: ↑ 9 Changed 5 years ago by aschilling

Replying to chapoton:

apply trac_12774-coxeter-ms-v2.patch

I have just folded and rebased this patch. The bot seems to be green and happy.

This looks good to me. Anne, Nicolas, Christian, do you want to have a look ?

Has Mark answered or taken into account all of Christian's previous comments? If not, that should be done first!

Anne

comment:12 Changed 5 years ago by nthiery

What are cocovers? should the new methods be named instead bruhat_upper_covers_* / bruhat_lower_covers_* for consistency with posets?

Cheers,

Nicolas

comment:13 Changed 4 years ago by mshimo

Regarding Comment 6, first question: I don't know. (Nicolas, can you answer this?) However I tried to put certain things involving root systems into categories and had my first encounter with import loops. Comment 6 second question: Since I don't know how much work it would take (and since my methods use root data, which is more information than the Cartan data needed for a Coxeter group) my vote is to finalize this patch without the extension to Coxeter groups.

Regarding Comment 12: Cocovers are what you are calling "lower covers" and covers are what you are calling "upper covers". I can change the names if you insist.

comment:14 follow-up: Changed 4 years ago by stumpc5

Does the version of the patch here reflection the current status?

comment:15 in reply to: ↑ 14 Changed 4 years ago by mshimo

Replying to stumpc5:

Does the version of the patch here reflection the current status?

I didn't change anything yet. The only additional changes I was planning to make (but have not yet made) were the method renamings that Nicolas suggested.

comment:16 Changed 4 years ago by mshimo

  • Description modified (diff)

comment:17 Changed 4 years ago by mshimo

  • Description modified (diff)

comment:18 follow-up: Changed 4 years ago by aschilling

  • Reviewers changed from Christian Stump to Christian Stump, Anne Schilling
  • Status changed from needs_review to positive_review

comment:19 in reply to: ↑ 18 Changed 4 years ago by aschilling

Mark and I went through the patch at Sage Days 45 and reviewed it together. Everything looks fine!

comment:20 Changed 4 years ago by aschilling

  • Keywords days45 added

comment:21 Changed 4 years ago by aschilling

  • Milestone changed from sage-5.7 to sage-5.8

comment:22 follow-up: Changed 4 years ago by jdemeyer

  • Status changed from positive_review to needs_work

You should not use "assert" for bad user input, only to check for actual bugs. Bad input should probably give a ValueError instead. The correct use for assert is to check for conditions which you know are true if the program wouldn't have bugs.

If there is any way at all to reproduce an AssertionError using documented public functions, that is by definition a bug.

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

Changed 4 years ago by mshimo

comment:23 in reply to: ↑ 22 Changed 4 years ago by aschilling

Looks good now!

comment:24 Changed 4 years ago by aschilling

  • Status changed from needs_work to positive_review

comment:25 Changed 4 years ago by jdemeyer

  • Merged in set to sage-5.8.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.