Opened 3 years ago
Closed 3 years ago
#27467 closed defect (fixed)
weak order of permutations broken
Reported by:  tscrim  Owned by:  

Priority:  blocker  Milestone:  sage8.8 
Component:  combinatorics  Keywords:  Coxeter group 
Cc:  sagecombinat, nthiery, chapoton, darij, jeremy.l.martin  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Frédéric Chapoton, Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  fa0450e (Commits, GitHub, GitLab)  Commit:  fa0450ecb592385c795af1e916ea18fca65608b7 
Dependencies:  Stopgaps: 
Description (last modified by )
From https://groups.google.com/forum/#!topic/sagesupport/6kuvliWzi84:
sage: for w in Permutations(3): ....: w, w.weak_covers() ....: ([1, 2, 3], []) ([1, 3, 2], [[1, 2, 3]]) ([2, 1, 3], [[1, 2, 3]]) ([2, 3, 1], [[3, 2, 1]]) ([3, 1, 2], [[3, 2, 1]]) ([3, 2, 1], [[3, 1, 2], [2, 3, 1]]) The fourth and fifth lines of the output are incorrect. The correct values should be ([2, 3, 1], [[2, 1, 3]]) ([3, 1, 2], [[1, 3, 2]])
This manifests also in creating the weak order poset:
sage: Permutations(3).weak_poset() ... ValueError: Hasse diagram contains cycles
This is a leftvsright issue and Permutation
multiplication being a little strange with respect to that. We also remove the multiplication argument and convention effects from has_*_descent
.
Change History (23)
comment:1 Changed 3 years ago by
 Cc jeremy.l.martin added
comment:2 Changed 3 years ago by
 Description modified (diff)
comment:3 Changed 3 years ago by
 Branch set to public/combinat/fix_weak_order_permutations27467
 Commit set to 22732230664fc213b76e30da3d8c0988dc0139ee
 Status changed from new to needs_review
So the only way forward that I could see to make this work is to gut out the multiplication option for has_*_descent
. With this, I do not think anything for Coxeter combiantorics now uses the multiplication convention.
New commits:
2273223  Making apply_simple_reflection_* and has_*_descent not use the permutation multiplication convention.

comment:4 Changed 3 years ago by
 Description modified (diff)
comment:5 Changed 3 years ago by
 Milestone changed from sage8.7 to sage8.8
Moving all blocker/critical issues from 8.7 to 8.8.
comment:6 Changed 3 years ago by
Can someone review this?
comment:7 Changed 3 years ago by
 Commit changed from 22732230664fc213b76e30da3d8c0988dc0139ee to c54aef5f24af419293c8fe7c4d8b7d3c4dbabec1
comment:8 Changed 3 years ago by
 Commit changed from c54aef5f24af419293c8fe7c4d8b7d3c4dbabec1 to 295c5178bb99e77b18961996fec91eed90e57995
Branch pushed to git repo; I updated commit sha1. New commits:
295c517  Fixing YokonumaHecke algebras.

comment:9 Changed 3 years ago by
Green patchbot.
comment:10 followup: ↓ 12 Changed 3 years ago by
 deprecation should appear in doctests, no ?
 "switching the entries i and i+1" (remove "equal" ?) in the doc of apply_simple_reflection_right
 I am worried that this seems to be a source of incoherence.. But maybe the situation gets no worse than what it is right now ?
comment:11 Changed 3 years ago by
 Commit changed from 295c5178bb99e77b18961996fec91eed90e57995 to 0af471b6ae8b256a41045ad3a1be9dfdb056c61f
Branch pushed to git repo; I updated commit sha1. New commits:
0af471b  Adding deprecation doctest and fixing docstring.

comment:12 in reply to: ↑ 10 Changed 3 years ago by
Replying to chapoton:
 deprecation should appear in doctests, no ?
Added.
 "switching the entries i and i+1" (remove "equal" ?) in the doc of apply_simple_reflection_right
Fixed.
 I am worried that this seems to be a source of incoherence.. But maybe the situation gets no worse than what it is right now ?
It is at least no worse than what it is currently, but I think this makes it more consistent overall. Plus it fixes a definite bug.
comment:13 followup: ↓ 14 Changed 3 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, then.
One should suggest somewhere loudly to use SymmetricGroup(n)
instead of Permutations(n)
when doing Coxeterrelated work.
comment:14 in reply to: ↑ 13 Changed 3 years ago by
 Reviewers changed from Frédéric Chapoton to Frédéric Chapoton, Darij Grinberg
Replying to chapoton:
ok, then.
Thank you.
One should suggest somewhere loudly to use
SymmetricGroup(n)
instead ofPermutations(n)
when doing Coxeterrelated work.
Also referencing CoxeterGroup
or WeylGroup
as well. Another ticket.
I am adding Darij as a reviewer since he gave me some comments on the ticket.
comment:15 Changed 3 years ago by
 Status changed from positive_review to needs_work
Possibly due to #27899, I'm getting
sage t warnlong 57.2 src/sage/combinat/dyck_word.py ********************************************************************** File "src/sage/combinat/dyck_word.py", line 1997, in sage.combinat.dyck_word.DyckWord_complete.to_312_avoiding_permutation Failed example: p = DyckWord([1,1,0,1,0,0,1,1,0,1,0,1,0,0]).to_312_avoiding_permutation(); p Expected: [2, 3, 1, 5, 6, 7, 4] Got: [3, 1, 2, 7, 4, 5, 6] ********************************************************************** File "src/sage/combinat/dyck_word.py", line 2007, in sage.combinat.dyck_word.DyckWord_complete.to_312_avoiding_permutation Failed example: all(pi.avoids([3,1,2]) for pi in PD) Expected: True Got: False ********************************************************************** File "src/sage/combinat/dyck_word.py", line 2197, in sage.combinat.dyck_word.DyckWord_complete.to_permutation Failed example: D.to_permutation(map="BandlowKillpatrick") Expected: [3, 4, 2, 1] Got: [4, 3, 1, 2] ********************************************************************** 2 items had failures: 2 of 9 in sage.combinat.dyck_word.DyckWord_complete.to_312_avoiding_permutation 1 of 7 in sage.combinat.dyck_word.DyckWord_complete.to_permutation [581 tests, 3 failures, 1.27 s]  sage t warnlong 57.2 src/sage/combinat/dyck_word.py # 3 doctests failed 
comment:16 Changed 3 years ago by
Yes, probably correlated to this replacement in #27899 :
n = self.semilength() area = self.to_area_sequence()  from sage.groups.perm_gps.permgroup_named import SymmetricGroup  pi = SymmetricGroup(n).one() + pi = Permutations(n).one() for j in range(n): for i in range(area[j]):  pi = pi.apply_simple_reflection(ji)  return Permutation(~pi) + pi = pi.apply_simple_reflection(j  i) + return ~pi
comment:17 Changed 3 years ago by
I concur, and it should just be a matter of swapping the left/right convention (which I guess should just mean returning pi
instead of ~pi
). I can do this tomorrow.
comment:18 Changed 3 years ago by
 Commit changed from 0af471b6ae8b256a41045ad3a1be9dfdb056c61f to 25f865556eed7f2afc420fa5d1b757c32d101fa9
Branch pushed to git repo; I updated commit sha1. New commits:
25f8655  Merge branch 'public/combinat/fix_weak_order_permutations27467' of git://trac.sagemath.org/sage into public/combinat/fix_weak_order_permutations27467

comment:19 Changed 3 years ago by
 Commit changed from 25f865556eed7f2afc420fa5d1b757c32d101fa9 to fa0450ecb592385c795af1e916ea18fca65608b7
Branch pushed to git repo; I updated commit sha1. New commits:
fa0450e  Fixing leftright convention difference.

comment:20 Changed 3 years ago by
 Status changed from needs_work to needs_review
Sorry, I got sidetracked from this and forgot to do this last week. This is now fixed (although unfortunately we might have missed the next release cutoff...). Volker, it would be really nice if this could slip in to 8.8 since this is a relatively big bug in the combinatorics code.
comment:21 Changed 3 years ago by
 Status changed from needs_review to positive_review
set to positive again
comment:22 Changed 3 years ago by
 Priority changed from critical to blocker
comment:23 Changed 3 years ago by
 Branch changed from public/combinat/fix_weak_order_permutations27467 to fa0450ecb592385c795af1e916ea18fca65608b7
 Resolution set to fixed
 Status changed from positive_review to closed
The problem is the multiplication for a permutation seems to have the oppose effect (by default):
So we need to override
apply_simple_reflection_*
forPermutation
.