#26603 closed defect (fixed)

Bugfix in bruhat_lower_covers

Reported by: bump Owned by:
Priority: major Milestone: sage-8.5
Component: combinatorics Keywords:
Cc: nthiery, tscrim, sage-combinat 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 bump)

Creating a Weyl group with the option implementation="permutation" is much faster, but unfortunately the Kazhdan-Lusztig 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 Kazhdan-Lusztig polynomials by mandating side="right" where needed but doesn't address the underlying inconsistency.

Change History (11)

comment:1 follow-up: Changed 15 months ago by tscrim

See #23299.

comment:2 Changed 15 months ago by bump

  • Description modified (diff)

comment:3 Changed 15 months ago by bump

  • Branch set to public/bruhat_order-26603
  • Commit set to fe420705f98a69ecbfec8b6bf36cb0008e6f7cc2

New commits:

fe42070specify side in bruhat_lower_covers

comment:4 Changed 15 months ago by git

  • Commit changed from fe420705f98a69ecbfec8b6bf36cb0008e6f7cc2 to a2410dd49c27a29c878cd277052ff631a736983f

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

a2410ddrevert SAGE_ROOT/sage which was accidentally modified by the last commit

comment:5 in reply to: ↑ 1 Changed 15 months ago by bump

Replying to tscrim:

See #23299.

So there is already a patch to fix this problem. It would be good if it can get merged.

comment:6 Changed 15 months ago by tscrim

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 git

  • Commit changed from a2410dd49c27a29c878cd277052ff631a736983f to b4f56515e70e84ac1f6eb2581be39222a6f19210

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

b4f5651specify side to use for bruhat upper covers.

comment:8 Changed 15 months ago by bump

  • Status changed from new to needs_review

comment:9 Changed 15 months ago by git

  • Commit changed from b4f56515e70e84ac1f6eb2581be39222a6f19210 to d566ab92d5ec09abe5a08b60a7fef049b01049a9

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

d566ab9also mandate side=right for bruhat_upper_covers in finite_coxeter_groups.py

comment:10 Changed 15 months ago by tscrim

  • Authors changed from bump to Daniel Bump
  • 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 vbraun

  • Branch changed from public/bruhat_order-26603 to d566ab92d5ec09abe5a08b60a7fef049b01049a9
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.