[Sage] #14641: Does the "promotion" method for tableaux really compute Schuetzenberger promotion?
Sage
promotion?
-----------------------------+----------------------------------------------
Reporter: darij | Owner: tbd
Type: defect | Status: new
Priority: major | Milestone: sage-5.10
Component: PLEASE CHANGE | Keywords: tableaux, partitions, combinat, jeu de taquin, promotion
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies:
Stopgaps: |
-----------------------------+----------------------------------------------
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. The notion of promotion has an
unfortunate wealth of different meanings, but I can't recognize any of
them in what Sage computes. 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...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14641>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB
Sage
promotion?
Type: defect | Status: new
Priority: major | Milestone: sage-5.10
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
Description changed by darij:
Old description:
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
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14641#comment:1>
Sage
promotion?
Type: defect | Status: new
Priority: major | Milestone: sage-5.10
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
Comment (by jessicapalencia):
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
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14641#comment:2>
Sage
promotion?
Type: defect | Status: new
Priority: major | Milestone: sage-5.10
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
Comment (by darij):
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}}}.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14641#comment:3>
Sage
promotion?
Type: defect | Status: new
Component: PLEASE CHANGE | Resolution:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
Comment (by darij):
There's still something I don't like:
{{{
for c in self.cells_containing(n+1):
p = p._slide_up(c)
}}}
This is from the source code of {{{promotion}}}. But sliding up cells
containing the maximum entry in a semistandard tableau is not commutative:
{{{
sage: t = Tableau([[1,2,2,3],[2,3,3]])
sage: t._slide_up((0,3))._slide_up((1,2))
[[0, 1, 2, 2], [0, 2, 3]]
sage: t._slide_up((1,2))._slide_up((0,3))
[[0, 0, 1, 2], [2, 2, 3]]
}}}
Obviously the method is meant for some specific cases in which this
doesn't go wrong, but I'd like to see that in the doc...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14641#comment:4>
Sage
promotion?
Type: defect | Status: new
Component: PLEASE CHANGE | Resolution:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
Comment (by darij):
This is all in #7983 now.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14641#comment:5>
Sage
promotion?
Reporter: darij | Owner: tbd
Type: defect | Status: needs_review
Priority: trivial | Milestone: sage-5.11
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
Changes (by darij):
* priority: major => trivial
* status: new => needs_review
* component: PLEASE CHANGE => combinatorics
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14641#comment:6>
Sage
promotion?
Reporter: darij | Owner: tbd
Type: defect | Status: positive_review
Priority: trivial | Milestone: sage-duplicate/invalid/wontfix
Component: combinatorics | Resolution:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
Changes (by darij):
* status: needs_review => positive_review
* milestone: sage-5.11 => sage-duplicate/invalid/wontfix
Old description:
> 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
New description:
**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
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14641#comment:7>