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: sage-8.8
Component: combinatorics Keywords: Coxeter group
Cc: sage-combinat, 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:

Status badges

Description (last modified by tscrim)

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.

Change History (23)

comment:1 Changed 3 years ago by tscrim

  • Cc jeremy.l.martin added

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:

2273223Making 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:

c822b3fMerge branch 'public/combinat/fix_weak_order_permutations-27467' of git://trac.sagemath.org/sage into public/combinat/fix_weak_order_permutations-27467
c54aef5Updating 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:

295c517Fixing Yokonuma-Hecke algebras.

comment:9 Changed 3 years ago by tscrim

Green patchbot.

comment:10 follow-up: 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:

0af471bAdding deprecation doctest and fixing docstring.

comment:12 in reply to: ↑ 10 Changed 3 years ago by tscrim

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 follow-up: 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

Replying to chapoton:

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

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:

25f8655Merge 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:

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