Opened 15 months ago
Closed 15 months ago
#26603 closed defect (fixed)
Bugfix in bruhat_lower_covers
Reported by:  bump  Owned by:  

Priority:  major  Milestone:  sage8.5 
Component:  combinatorics  Keywords:  
Cc:  nthiery, tscrim, sagecombinat  Merged in:  
Authors:  Daniel Bump  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  d566ab9 (Commits)  Commit:  d566ab92d5ec09abe5a08b60a7fef049b01049a9 
Dependencies:  Stopgaps: 
Description (last modified by )
Creating a Weyl group with the option implementation="permutation"
is much faster, but unfortunately the KazhdanLusztig polynomials are not computed correctly. Debugging this led to the discovery that the side of a descent is implemented inconsistently in the bruhat_lower_covers
Element method of Coxeter groups.
sage: W = WeylGroup("A3",prefix="s",implementation="permutation") sage: [s1,s2,s3]=W.simple_reflections() sage: (s1*s2*s3*s1).bruhat_lower_covers() [s2*s1*s3, s1*s2*s3]
This is wrong since it omits s1*s2*s1
.
The culprit is the has_descent
method that has different default sides for the two implementations.
sage: W = WeylGroup("A2",prefix="s") sage: [s1,s2]=W.simple_reflections() sage: (s1*s2).has_descent(1) False sage: sage: W = WeylGroup("A2",prefix="s",implementation="permutation") sage: [s1,s2]=W.simple_reflections() sage: (s1*s2).has_descent(1) True
The patch fixes KazhdanLusztig polynomials by mandating side="right"
where needed but doesn't address the underlying inconsistency.
Change History (11)
comment:1 followup: ↓ 5 Changed 15 months ago by
comment:2 Changed 15 months ago by
 Description modified (diff)
comment:3 Changed 15 months ago by
 Branch set to public/bruhat_order26603
 Commit set to fe420705f98a69ecbfec8b6bf36cb0008e6f7cc2
New commits:
fe42070  specify side in bruhat_lower_covers

comment:4 Changed 15 months ago by
 Commit changed from fe420705f98a69ecbfec8b6bf36cb0008e6f7cc2 to a2410dd49c27a29c878cd277052ff631a736983f
Branch pushed to git repo; I updated commit sha1. New commits:
a2410dd  revert SAGE_ROOT/sage which was accidentally modified by the last commit

comment:5 in reply to: ↑ 1 Changed 15 months ago by
comment:6 Changed 15 months ago by
I would not mind merging this portion first. Although we probably should do the same fix for the upper Bruhat covers.
comment:7 Changed 15 months ago by
 Commit changed from a2410dd49c27a29c878cd277052ff631a736983f to b4f56515e70e84ac1f6eb2581be39222a6f19210
Branch pushed to git repo; I updated commit sha1. New commits:
b4f5651  specify side to use for bruhat upper covers.

comment:8 Changed 15 months ago by
 Status changed from new to needs_review
comment:9 Changed 15 months ago by
 Commit changed from b4f56515e70e84ac1f6eb2581be39222a6f19210 to d566ab92d5ec09abe5a08b60a7fef049b01049a9
Branch pushed to git repo; I updated commit sha1. New commits:
d566ab9  also mandate side=right for bruhat_upper_covers in finite_coxeter_groups.py

comment:10 Changed 15 months ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
 Work issues decide whether default for has_descent should be left or right deleted
This fixes the immediate bug, so let us get this in. Thank you.
comment:11 Changed 15 months ago by
 Branch changed from public/bruhat_order26603 to d566ab92d5ec09abe5a08b60a7fef049b01049a9
 Resolution set to fixed
 Status changed from positive_review to closed
See #23299.