Does the "promotion" method for tableaux really compute Schuetzenberger promotion?

[darijgr]

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

CC: @sagetrac-sage-combinat @anneschilling

Component: combinatorics

Keywords: tableaux, partitions, combinat, jeu de taquin, promotion

Reviewer: Darij Grinberg

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

[jessicapalencia]

comment:2

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

[darijgr]

comment:3

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.

[darijgr]

comment:4

EDIT: ignore me, this one was a non-issue

[darijgr]

comment:5

This is all in #7983 now.

[jdemeyer]

Reviewer: Darij Grinberg