#14641: Does the "promotion" method for tableaux really compute Schuetzenberger
promotion?
----------------------------------------------------------------------------+
Reporter: darij |
Owner: tbd
Type: defect |
Status: positive_review
Priority: trivial |
Milestone: sage-duplicate/invalid/wontfix
Component: combinatorics |
Resolution:
Keywords: tableaux, partitions, combinat, jeu de taquin, promotion |
Work issues:
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
> {{{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...
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
{{{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#comment:7>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
