various enhancements for Coxeter and Weyl groups

[sagetrac-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

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

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

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

CC: @nthiery @anneschilling

Component: combinatorics

Keywords: coxeter group, weyl group, days45

Author: Mark Shimozono

Reviewer: Christian Stump, Anne Schilling

Merged: sage-5.8.beta0

Issue created by migration from https://trac.sagemath.org/ticket/12774

[stumpc5]

Changed dependencies from #6588, #12667 to none

[stumpc5]

comment:4

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

[stumpc5]

Reviewer: Christian Stump

[stumpc5]

comment:5

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

[stumpc5]

comment:6

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

[fchapoton]

comment:7

apply trac_12774-coxeter-ms-v2.patch

[fchapoton]

comment:8

apply trac_12774-coxeter-ms-v2.patch

[fchapoton]

comment:9

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 ?

[fchapoton]

comment:10

apply trac_12774-coxeter-ms-v2.patch

I have corrected the deprecations

[anneschilling]

comment:11

Replying to @fchapoton:

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

[nthiery]

comment:12

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

Cheers,
Nicolas

[sagetrac-mshimo]

comment:13

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.

[stumpc5]

comment:14

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

[sagetrac-mshimo]

comment:15

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.

[anneschilling]

Changed reviewer from Christian Stump to Christian Stump, Anne Schilling

[anneschilling]

comment:19

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

[anneschilling]

Changed keywords from coxeter group, weyl group to coxeter group, weyl group, days45

[jdemeyer]

comment:22

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.

[sagetrac-mshimo]

Attachment: trac_12774-coxeter-ms.patch.gz

[anneschilling]

comment:23

Looks good now!

[jdemeyer]

Merged: sage-5.8.beta0