Opened 6 years ago

Closed 6 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 darij)

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 6 years ago by darij

  • Description modified (diff)

comment:2 Changed 6 years ago 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

comment:3 Changed 6 years ago 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.

comment:4 Changed 6 years ago by darij

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

Last edited 6 years ago by darij (previous) (diff)

comment:5 Changed 6 years ago by darij

This is all in #7983 now.

comment:6 Changed 6 years ago by darij

  • Component changed from PLEASE CHANGE to combinatorics
  • Priority changed from major to trivial
  • Status changed from new to needs_review

comment:7 Changed 6 years ago by darij

  • 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 6 years ago by jdemeyer

  • Resolution set to duplicate
  • Reviewers set to Darij Grinberg
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.