Opened 3 years ago

Closed 3 years ago

# weak order of permutations broken

Reported by: Owned by: tscrim blocker sage-8.8 combinatorics Coxeter group sage-combinat, nthiery, chapoton, darij, jeremy.l.martin Travis Scrimshaw Frédéric Chapoton, Darij Grinberg N/A fa0450e fa0450ecb592385c795af1e916ea18fca65608b7

```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 left-vs-right issue and `Permutation` multiplication being a little strange with respect to that. We also remove the multiplication argument and convention effects from `has_*_descent`.

### comment:2 Changed 3 years ago by tscrim

• Description modified (diff)

The problem is the multiplication for a permutation seems to have the oppose effect (by default):

```sage: W = Permutations(3)
sage: w = W([2,3,1])
sage: w.reduced_word()
[1, 2]
sage: w.descents(side='right')
[2]
sage: w.apply_simple_reflection_right(2)
[3, 2, 1]
```

So we need to override `apply_simple_reflection_*` for `Permutation`.

### comment:3 Changed 3 years ago by tscrim

• Authors set to Travis Scrimshaw
• Branch set to public/combinat/fix_weak_order_permutations-27467
• 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 tscrim

• Description modified (diff)

### comment:5 Changed 3 years ago by embray

• Milestone changed from sage-8.7 to sage-8.8

Moving all blocker/critical issues from 8.7 to 8.8.

### comment:6 Changed 3 years ago by tscrim

Can someone review this?

### comment:7 Changed 3 years ago by git

• Commit changed from 22732230664fc213b76e30da3d8c0988dc0139ee to c54aef5f24af419293c8fe7c4d8b7d3c4dbabec1

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

 ​c822b3f `Merge branch 'public/combinat/fix_weak_order_permutations-27467' of git://trac.sagemath.org/sage into public/combinat/fix_weak_order_permutations-27467` ​c54aef5 `Updating docstring based on comments by Darij.`

### comment:8 Changed 3 years ago by git

• Commit changed from c54aef5f24af419293c8fe7c4d8b7d3c4dbabec1 to 295c5178bb99e77b18961996fec91eed90e57995

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

 ​295c517 `Fixing Yokonuma-Hecke algebras.`

Green patchbot.

### comment:10 follow-up: ↓ 12 Changed 3 years ago by chapoton

• 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 git

• 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 tscrim

• deprecation should appear in doctests, no ?

• "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 follow-up: ↓ 14 Changed 3 years ago by chapoton

• 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 Coxeter-related work.

### comment:14 in reply to: ↑ 13 Changed 3 years ago by tscrim

• Reviewers changed from Frédéric Chapoton to Frédéric Chapoton, Darij Grinberg

ok, then.

Thank you.

One should suggest somewhere loudly to use `SymmetricGroup(n)` instead of `Permutations(n)` when doing Coxeter-related 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 vbraun

• Status changed from positive_review to needs_work

Possibly due to #27899, I'm getting

```sage -t --warn-long 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="Bandlow-Killpatrick")
Expected:
[3, 4, 2, 1]
Got:
[4, 3, 1, 2]
**********************************************************************
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 --warn-long 57.2 src/sage/combinat/dyck_word.py  # 3 doctests failed
----------------------------------------------------------------------
```

### comment:16 Changed 3 years ago by chapoton

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(j-i)
-        return Permutation(~pi)
+                pi = pi.apply_simple_reflection(j - i)
+        return ~pi
```

### comment:17 Changed 3 years ago by tscrim

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 git

• 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_permutations-27467' of git://trac.sagemath.org/sage into public/combinat/fix_weak_order_permutations-27467`

### comment:19 Changed 3 years ago by git

• Commit changed from 25f865556eed7f2afc420fa5d1b757c32d101fa9 to fa0450ecb592385c795af1e916ea18fca65608b7

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

 ​fa0450e `Fixing left-right convention difference.`

### comment:20 Changed 3 years ago by tscrim

• 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 chapoton

• Status changed from needs_review to positive_review

set to positive again

### comment:22 Changed 3 years ago by vbraun

• Priority changed from critical to blocker

### comment:23 Changed 3 years ago by vbraun

• Branch changed from public/combinat/fix_weak_order_permutations-27467 to fa0450ecb592385c795af1e916ea18fca65608b7
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.