weak order of permutations broken #27467

tscrim · 2019-03-11T23:43:03Z

From https://groups.google.com/forum/#!topic/sage-support/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 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.

CC: @sagetrac-sage-combinat @nthiery @fchapoton @darijgr @sagetrac-jeremy-l-martin

Component: combinatorics

Keywords: Coxeter group

Author: Travis Scrimshaw

Branch/Commit: fa0450e

Reviewer: Frédéric Chapoton, Darij Grinberg

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

The text was updated successfully, but these errors were encountered:

tscrim · 2019-03-11T23:52:34Z

comment:2

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.

tscrim · 2019-03-12T00:21:41Z

Branch: public/combinat/fix_weak_order_permutations-27467

tscrim · 2019-03-12T00:21:41Z

Author: Travis Scrimshaw

tscrim · 2019-03-12T00:21:41Z

comment:3

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

tscrim · 2019-03-12T00:21:41Z

Commit: 2273223

embray · 2019-03-25T10:41:19Z

comment:5

Moving all blocker/critical issues from 8.7 to 8.8.

tscrim · 2019-05-24T22:55:51Z

comment:6

Can someone review this?

sagetrac-git · 2019-05-24T23:11:19Z

Changed commit from 2273223 to c54aef5

sagetrac-git · 2019-05-24T23:11:19Z

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

sagetrac-git · 2019-05-24T23:16:25Z

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

`295c517`	`Fixing Yokonuma-Hecke algebras.`

sagetrac-git · 2019-05-24T23:16:25Z

Changed commit from c54aef5 to 295c517

tscrim · 2019-05-25T23:21:27Z

comment:9

Green patchbot.

fchapoton · 2019-05-26T05:57:32Z

comment:10

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 ?

sagetrac-git · 2019-06-05T00:36:00Z

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

`0af471b`	`Adding deprecation doctest and fixing docstring.`

sagetrac-git · 2019-06-05T00:36:00Z

Changed commit from 295c517 to 0af471b

tscrim · 2019-06-05T00:37:36Z

comment:12

Replying to @fchapoton:

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.

fchapoton · 2019-06-05T08:43:01Z

comment:13

ok, then.

One should suggest somewhere loudly to use SymmetricGroup(n) instead of Permutations(n) when doing Coxeter-related work.

fchapoton · 2019-06-05T08:43:01Z

Reviewer: Frédéric Chapoton

tscrim · 2019-06-05T09:04:43Z

comment:14

Replying to @fchapoton:

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.

tscrim · 2019-06-05T09:04:43Z

Changed reviewer from Frédéric Chapoton to Frédéric Chapoton, Darij Grinberg

vbraun · 2019-06-05T22:25:58Z

comment:15

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 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 --warn-long 57.2 src/sage/combinat/dyck_word.py  # 3 doctests failed
----------------------------------------------------------------------

fchapoton · 2019-06-06T05:58:25Z

comment:16

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

tscrim · 2019-06-06T07:20:34Z

comment:17

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.

sagetrac-git · 2019-06-10T23:46:32Z

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`

sagetrac-git · 2019-06-10T23:46:32Z

Changed commit from 0af471b to 25f8655

sagetrac-git · 2019-06-10T23:47:25Z

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

`fa0450e`	`Fixing left-right convention difference.`

sagetrac-git · 2019-06-10T23:47:25Z

Changed commit from 25f8655 to fa0450e

tscrim · 2019-06-10T23:48:51Z

comment:20

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.

fchapoton · 2019-06-11T07:23:38Z

comment:21

set to positive again

vbraun · 2019-06-12T21:41:43Z

Changed branch from public/combinat/fix_weak_order_permutations-27467 to fa0450e

sagemathgh-39262: Add script for checking for old deprecations       To find deprecations that can now safely removed. Example: ``` python tools/check_deprecations.py src/sage/combinat Found 9 deprecations. 100%| Deprecations over one year ago: File: src\sage\combinat\permutation.py, PR: sagemath#26810, Closed Date: 2019-01-23 File: src\sage\combinat\permutation.py, PR: sagemath#27467, Closed Date: 2019-06-12 File: src\sage\combinat\words\finite_word.py, PR: sagemath#30187, Closed Date: 2020-09-15 File: src\sage\combinat\designs\difference_family.py, PR: sagemath#35211, Closed Date: 2023-04-01 ``` ### 📝 Checklist  - [ ] The title is concise and informative. - [ ] The description explains in detail what this PR is about. - [ ] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation and checked the documentation preview. ### ⌛ Dependencies    URL: sagemath#39262 Reported by: Tobias Diez Reviewer(s): Frédéric Chapoton, Tobias Diez

tscrim added this to the sage-8.7 milestone Mar 11, 2019

tscrim added c: combinatorics labels Mar 11, 2019

This comment has been minimized.

Sign in to view

tscrim added the s: needs review label Mar 12, 2019

This comment has been minimized.

Sign in to view

embray modified the milestones: sage-8.7, sage-8.8 Mar 25, 2019

fchapoton added s: positive review and removed s: needs review labels Jun 5, 2019

vbraun added s: needs work and removed s: positive review labels Jun 5, 2019

tscrim added s: needs review and removed s: needs work labels Jun 10, 2019

fchapoton added s: positive review and removed s: needs review labels Jun 11, 2019

vbraun added p: blocker / 1 and removed p: critical / 2 labels Jun 11, 2019

vbraun removed the s: positive review label Jun 12, 2019

vbraun closed this as completed in 8555a05 Jun 12, 2019

Uh oh!

weak order of permutations broken #27467

weak order of permutations broken #27467

Comments

tscrim commented Mar 11, 2019

This comment has been minimized.

tscrim commented Mar 11, 2019

Uh oh!

tscrim commented Mar 12, 2019

Uh oh!

tscrim commented Mar 12, 2019

Uh oh!

tscrim commented Mar 12, 2019

Uh oh!

tscrim commented Mar 12, 2019

Uh oh!

This comment has been minimized.

embray commented Mar 25, 2019

Uh oh!

tscrim commented May 24, 2019

Uh oh!

sagetrac-git mannequin commented May 24, 2019

Uh oh!

sagetrac-git mannequin commented May 24, 2019

Uh oh!

sagetrac-git mannequin commented May 24, 2019

Uh oh!

sagetrac-git mannequin commented May 24, 2019

Uh oh!

tscrim commented May 25, 2019

Uh oh!

fchapoton commented May 26, 2019

Uh oh!

sagetrac-git mannequin commented Jun 5, 2019

Uh oh!

sagetrac-git mannequin commented Jun 5, 2019

Uh oh!

tscrim commented Jun 5, 2019

Uh oh!

fchapoton commented Jun 5, 2019

Uh oh!

fchapoton commented Jun 5, 2019

Uh oh!

tscrim commented Jun 5, 2019

Uh oh!

tscrim commented Jun 5, 2019

Uh oh!

vbraun commented Jun 5, 2019

Uh oh!

fchapoton commented Jun 6, 2019

Uh oh!

tscrim commented Jun 6, 2019

Uh oh!

sagetrac-git mannequin commented Jun 10, 2019

Uh oh!

sagetrac-git mannequin commented Jun 10, 2019

Uh oh!

sagetrac-git mannequin commented Jun 10, 2019

Uh oh!

sagetrac-git mannequin commented Jun 10, 2019

Uh oh!

tscrim commented Jun 10, 2019

Uh oh!

fchapoton commented Jun 11, 2019

Uh oh!

vbraun commented Jun 12, 2019

Uh oh!