Opened 8 years ago
Closed 8 years ago
#14641 closed defect (duplicate)
Does the "promotion" method for tableaux really compute Schuetzenberger promotion?
Reported by: | darij | Owned by: | tbd |
---|---|---|---|
Priority: | trivial | Milestone: | sage-duplicate/invalid/wontfix |
Component: | combinatorics | Keywords: | tableaux, partitions, combinat, jeu de taquin, promotion |
Cc: | sage-combinat, schilling | Merged in: | |
Authors: | Reviewers: | Darij Grinberg | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
IGNORE this ticket: it's all been fixed in #7983.
Both promotion
and promotion_inverse
methods in combinat/tableau.py
take two inputs: the tableau self
and an integer n
.
What exactly does the n
do? While promotion
has some kind of docstring, I fail to understand it. I expected the n
to be the i
in the \delta_i
of Ayyer-Klee-Schilling http://arxiv.org/pdf/1205.7074v2.pdf (identifying standard Young tableaux with saturated chains on the partition lattice), but then I would expect that for X
being a standard tableau, X.promotion(n)
would still be a standard tableau. This is not the case:
sage: X = StandardTableau([[1,2],[3,4],[5]]) sage: X.promotion(1) [[1, 2], [4, 5], [6]]
It seems to me that X.promotion(n-1)
, where n
is the size of the standard tableau X
, computes the good old Schuetzenberger promotion of X
; but I am not quite sure and this seems to contradict the docstring.
When X
is rectangular, the code works very differently and some completely strange things happen:
sage: S = StandardTableau([[1,3,5,6],[2,4,7,8]]) sage: S.promotion(0) # This should make perfect sense going by the docstring... --------------------------------------------------------------------------- IndexError Traceback (most recent call last) <ipython-input-95-23c3eab7210b> in <module>() ----> 1 S.promotion(Integer(0)) # This should make perfect sense going by the docstring... /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/tableau.pyc in promotion(self, n) 1779 t = self.rotate_180() 1780 t = [[n+2-i for i in row] for row in t.to_list()] -> 1781 t = Tableau(t).promotion_inverse(n) 1782 t = [[n+2-i for i in row] for row in t.to_list()] 1783 return Tableau(t).rotate_180() /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/tableau.pyc in promotion_inverse(self, n) 1742 if l<s: 1743 for i in range(l): -> 1744 t[len(t)-1].append(n+1) 1745 else: 1746 t.append([n+1 for i in range(s)]) IndexError: list index out of range sage: S.promotion(1) [[1, 2]] sage: S.promotion(2) --------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-97-6a4133c5e025> in <module>() ----> 1 S.promotion(Integer(2)) /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/tableau.pyc in promotion(self, n) 1779 t = self.rotate_180() 1780 t = [[n+2-i for i in row] for row in t.to_list()] -> 1781 t = Tableau(t).promotion_inverse(n) 1782 t = [[n+2-i for i in row] for row in t.to_list()] 1783 return Tableau(t).rotate_180() /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/tableau.pyc in promotion_inverse(self, n) 1745 else: 1746 t.append([n+1 for i in range(s)]) -> 1747 return Tableau(t) 1748 1749 def promotion(self, n): /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.so in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (sage/misc/classcall_metaclass.c:1208)() /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/tableau.pyc in __classcall_private__(self, t) 258 259 if not map(len,t) in sage.combinat.partition._Partitions: --> 260 raise ValueError("A tableau must be a list of lists of weakly decreasing length.") 261 262 return Tableaux_all().element_class(Tableaux_all(), t) ValueError: A tableau must be a list of lists of weakly decreasing length. sage: S.promotion(3) [[1, 2], [3, 4]] sage: S.promotion(4) --------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-99-9acbfaebd18c> in <module>() ----> 1 S.promotion(Integer(4)) /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/tableau.pyc in promotion(self, n) 1779 t = self.rotate_180() 1780 t = [[n+2-i for i in row] for row in t.to_list()] -> 1781 t = Tableau(t).promotion_inverse(n) 1782 t = [[n+2-i for i in row] for row in t.to_list()] 1783 return Tableau(t).rotate_180() /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/tableau.pyc in promotion_inverse(self, n) 1745 else: 1746 t.append([n+1 for i in range(s)]) -> 1747 return Tableau(t) 1748 1749 def promotion(self, n): /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.so in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (sage/misc/classcall_metaclass.c:1208)() /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/tableau.pyc in __classcall_private__(self, t) 258 259 if not map(len,t) in sage.combinat.partition._Partitions: --> 260 raise ValueError("A tableau must be a list of lists of weakly decreasing length.") 261 262 return Tableaux_all().element_class(Tableaux_all(), t) ValueError: A tableau must be a list of lists of weakly decreasing length. sage: S.promotion(5) [[1, 2, 4], [3, 5, 6]] sage: S.promotion(6) --------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-101-ea0436786e82> in <module>() ----> 1 S.promotion(Integer(6)) /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/tableau.pyc in promotion(self, n) 1781 t = Tableau(t).promotion_inverse(n) 1782 t = [[n+2-i for i in row] for row in t.to_list()] -> 1783 return Tableau(t).rotate_180() 1784 p = self 1785 for c in self.cells_containing(n+1): /home/darij/sage-5.10.beta2/local/lib/python2.7/site-packages/sage/combinat/tableau.pyc in rotate_180(self) 1154 """ 1155 if not self.is_rectangular(): -> 1156 raise TypeError, "the tableau must be rectangular to use verticl_flip()" 1157 1158 return Tableau([ [l for l in reversed(row)] for row in reversed(self) ]) TypeError: the tableau must be rectangular to use verticl_flip() sage: S.promotion(7) [[1, 2, 4, 7], [3, 5, 6, 8]] sage: S.promotion(8) # even fails, odd works? [[2, 4, 6, 7], [3, 5, 8, 9]]
The notion of promotion suffers from a wealth of different meanings, but what I am seeing here doesn't match any I know...
Change History (8)
comment:1 Changed 8 years ago by
- Description modified (diff)
comment:2 Changed 8 years ago by
comment:3 Changed 8 years ago by
Thanks! This looks like a very good guess. I'm wondering why it had to be n+1, not n...
It looks like the doc is the main issue here. I'll take care of this in the next patch I do for tableaux.py
.
comment:4 Changed 8 years ago by
EDIT: ignore me, this one was a non-issue
comment:5 Changed 8 years ago by
This is all in #7983 now.
comment:6 Changed 8 years ago by
- Component changed from PLEASE CHANGE to combinatorics
- Priority changed from major to trivial
- Status changed from new to needs_review
comment:7 Changed 8 years ago by
- Description modified (diff)
- Milestone changed from sage-5.11 to sage-duplicate/invalid/wontfix
- Status changed from needs_review to positive_review
comment:8 Changed 8 years ago by
- Resolution set to duplicate
- Reviewers set to Darij Grinberg
- Status changed from positive_review to closed
Hi Darij,
So I think the 'n' in this promotion operator specifies that the highest entry value we are allowing in the tableau is 'n+1'. Now for standard tableaux, we want 'n' to be the number of boxes minus 1. But when you're working with semistandard tableaux, you really do need to specify this, since it may be that no 'n+1's are present in the tableaux, in which case promotion just increments all the entries.
It would be good to change the code so that if no 'n' is specified, it takes n = (# boxes - 1) by default.
I agree that the code is confusing in the case of rectangular tableaux, but it seems to be working correctly in the rectangular examples I've tried. It's likely just a computational shortcut.
Also, I think the code isn't designed to make sense with 'n' less than the largest entry minus 1. So it gives nonsensical answers. Perhaps the code should check that 'n' is at least as big as the largest entry minus 1.
Jessica