Young tableaux as lattice points in order cones:
promotion, fiberflipping and cyclic sieving
Jim Propp
MIT Combinatorics Seminar
March 11, 2015
I will show how the promotion operation of Berenstein and Kirillov,
acting on semistandard Young tableaux, relates to the more recent
promotion operation of Striker and Williams, acting on order ideals
of posets. An elementary geometric construction (fiberflipping)
underlies both the BenderKnuth approach to promotion of tableaux
and Striker and Williams' togglegroup, and gives us a way to relate
them. This talk is based on work with David Einstein and Tom Roby.
I'm not sure how new this is:
From Kirillov and Berenstein's article "Groups generated by
involutions, GelfandTsetlin patterns, and combinatorics of
Young tableaux" (1995):
"It is well known that the integral points set, (K_n)_Z, of the
cone K_n is in a onetoone correspondence with the set STY(n)
of standard Young tableaux, having all entries not exceeding n."
But it is still not as well known as it should be.
(Note: K and B's use of the word "standard" is nonstandard.)
I suspect some of this material is covered in Sam Hopkins' notes
http://web.mit.edu/~shopkins/docs/rsk.pdf which treat connections
with RSK.
I. Young tableaux
See Stanley's "Promotion and Evacuation"
A SSYT is a tableau that is weakly increasing from left to right
and strictly increasing from top to bottom.
A SSYT with floor a and ceiling b is one in which all entries
are greater than or equal to a and less than or equal to b.
Promotion a la Schutzenberger (Stembridge? Shimozono?) is
an operation on SSYT's with a specified floor and ceiling.
Here is the way Bender and Knuth implement it:
The ith BenderKnuth involution B_i , which I might call a BK toggle.
turns a tableau T into a tableau T' with the property that
the number of i's in T
equals
the number of i+1's in T'
and
the number of i+1's in T
equals
the number of i's in T'.
Specifically, call an i _fixed_ if it has an i+1 below it,
and _free_ otherwise,
and call an i+1 _fixed_ if it has an i above it,
and _free_ otherwise.
In each row, wherever we see r free i's followed by s free i+1's,
replace it by s i's followed by r i+1's.
(Special cases:
if r=1 and s=0, we're just replacing an i by an i+1, and
if r=0 and s=1, we're just replacing an i+1 by an i.)
Example:
1 2 2 1 1 2 1 1 3 1 1 4 1 1 4
3 5 5 3 5 5 2 5 5 2 5 5 2 4 5
Theorem: For SSYT's with A rows, B columns, floor 1, and ceiling n,
the order of the promotion map is n.
Note that for general SSYT's, performing promotion n times
gives a SSYT with the same number of 1's, 2's, ... and n's
respectively, but it need not be the same SSYT.
With rectangles, and a few other special shapes, it's the same SSYT.
II. Order ideals
See Striker and Williams's "Promotion and Rowmotion"
Definition of RCembedded posets:
a poset P equipped with a projection into Z x Z
such that each downward edge x > y in the Hasse diagram of P
projects to an edge of the form (i,j) > (i1,j1) or (i+1,j1).
We'll focus on [a]x[b] with its usual Hasse diagram embedding.
An order ideal of P is a subset I of P
such that for all x in I, if y < x then y is in I.
Given x in P, we define "toggling at x" to be the operation
that sends each order ideal I to the order ideal I'
where I' is the symmetric difference of I and {x}
provided that this set is an order ideal,
and I' = I otherwise.
Promotion is given by toggling from left to right
(it doesn't matter how you break the ties).
E.g. (representing an order ideal by its indicator function):
0 0
0 0 0 0
1 0 0 > 0 0 0
1 1 0 0
1 1
Theorem: When P = [a]x[b], promotion is of order a+b.
What's the connection between sections I and II?
GelfandTsetlin triangles.
III. GT triangles
See Kirillov and Berenstein's "Groups generated by involutions,
GelfandTsetlin patterns, and combinatorics of Young tableaux".
An example of an integral GelfandTsetlin triangle is
3 3 0 0 0
3 1 0 0
3 1 0
3 0
1
Entries are required to be weakly decreasing from left to right
along sloping diagonals.
There's a procedure for encoding SSYT's by triangles:
1 2 2
3 5 5
3 3 0 0 0 < shape of original tableau
3 1 0 0 < shape of subtableau formed by entries leq 4
3 1 0 < shape of subtableau formed by entries leq 3
3 0 < shape of subtableau formed by entries leq 2
1 < shape of subtableau formed by entries leq 1
Note that the subtableau formed by entries less than or equal to k
has at most k rows, so we only list k subtableau rowlengths in
the kth row of the GelfandTsetlin triangle.
SSYT's with A rows, B columns, floor 1, and ceiling n
are in bijection with
GTT's with top row B ... B 0 ... 0, with A B's and nA 0's.
Recall that B_i denotes the ith BenderKnuth involution.
1 2 2 B_1 1 1 2 B_2 1 1 3 B_3 1 1 4 B_4 1 1 4
3 5 5 > 3 5 5 > 2 5 5 > 2 5 5 > 2 4 5
3 3 0 0 0 3 3 0 0 0 3 3 0 0 0 3 3 0 0 0 3 3 0 0 0
3 1 0 0 3 1 0 0 3 1 0 0 3 1 0 0 3!2!0!0!
3 1 0 3 1 0 3 1 0 2!1!0! 2 1 0
3 0 3 0 2!1! 2 1 2 1
1 2! 2 2 2
To apply promotion to a GT triangle, update entries from
bottom to top (leaving the top row alone) according to the rule
v y v y
x > x'
w z w z
where x+x' = min(v,w) + max(y,z).
If w is outside of the triangle, take min(v,w) = v.
If z is outside of the triangle, take max(y,z) = y.
Note that if we just erased x and asked
"What values can we insert without violating the
inequalities that govern the set of GT triangles?",
it would be the interval [max(y,z), min(v,w)].
The map that sends x to x' = max(y,z) + min(v,w)  x
is the unique linear map that exchanges the endpoints
of this interval (check: it's linear, and the endpoints
get swapped, and there's only one such map).
That is: we dissect the GT cone into 1dimensional fibers
running in a particular direction
(each location within the triangle is associated
with its own coordinate direction),
and "flip" each of these fibers
(via the unique rigid motion that exchanges the endpoints).
Two ways to view this:
(1) Rescaled.
(2) Unrescaled.
A GelfandTsetlin triangle with all entries between 0 and n,
scaled down by n, is a point in the "GelfandTsetlin
polytope", with coordinates in (1/n)Z.
Or, letting n vary (and not scaling down),
we can view all these polytopes as
parallel slices of the "GelfandTsetlin cone", and
the GelfandTsetlin triangles are lattice points in that cone.
IV. PL promotion
Represent an order ideal of a poset P by its indicator function.
In this way order ideals of P correspond to (weakly) orderreversing
functions from the poset P into {0,1}.
Define the (reverse) order polytope O^{op}(P) of P as the set of
(weakly) orderreversing functions from the poset P into [0,1].
Then toggling can be seen as a form of fiberflipping
in the (reverse) order polytope of P.
Define PL toggles (apply fiberflipping in the direction
associated with a particular element of P).
If P has an RCembedding, we can define PL promotion
(toggle all the elements of P from left to right).
E.g., take P = [2] x [3]:
(0/3)

0/3
/ \
1/3 1/3
\ / \
3/3 1/3
\ /
3/3

(3/3)
It's convenient to switch to Ppartitions (orderreversing
maps from P to {0,1,...,n}) and get rid of denominators:
(0)

0
/ \
1 1
\ / \
3 1
\ /
3

(3)
Toggle from left to right:
0 0 1 1 1
1 1 > 2 1 > 2 1 > 2 1 > 2 1
3 1 3 1 2 1 2 1 2 2
3 3 3 2 2
V. Tying it together
[Draw commuting diagram between SSYT[3^2] and O^{op}([2]x[3]).]
The map is gotten by taking the tableau, finding the associated
GT triangle, throwing out the triangle of B's and the triangle of 0's
at the top so that what remains is a rectangle, and flipping that
rectangle across a line that goes from southeast to northwest.
See:
3 3 0 0 0 0
1 2 2 3 1 0 0 1 1
3 5 5 3 1 0 3 1
3 0 3
1
toggles to
3 3 0 0 0 0
1 1 2 3 1 0 0 2!1
3 5 5 3 1 0 3 1
3 0 3
2
toggles to
3 3 0 0 0 1!
1 1 3 3 1 0 0 2 1
2 5 5 3 1 0 2!1
2 1 3
2
toggles to
3 3 0 0 0 1
1 1 4 3 1 0 0 2 1!
2 5 5 2 1 0 2 1
2 1 2!
2
toggles to
3 3 0 0 0 1
1 1 4 3 2 0 0 2 1
2 4 5 2 1 0 2 2!
2 1 2
2
This is just an example; one thing that the longer EinsteinPropp
article needs to contain is a general proof of this.
(How do you write proofs of things like this that will be
at least as instructive for the reader as the writer?)
Theorem: Fix A, B, and n, and let P = [A] x [nA].
Under the abovedescribed bijection between tableaux and order ideals,
the action of the Schutzenberger promotion operator
on the set of semistandard Young tableaux of rectangular shape
with A rows and B columns having entries between 1 and n is
naturally conjugate to the action of the piecewiselinear
promotion operator on the rational points in the (reverse)
order polytope of P with denominator dividing B, or (equivalently)
to the action of the piecewiselinear promotion operator on
the set of Ppartitions with entries between 0 and B.
VI. The singlecolumn case
The case B=1: Promotion on semistandard Young tableaux of
rectangular shape with 1 column of length A having entries
between 1 and n is naturally conjugate to the action of
the piecewiselinear promotion operator on the vertices of
the order polytope of [A] × [nA].
A = 3, n = 6:
1 2 3 3 3 3
4 > 4 > 4 > 4 > 5 > 5
6 6 6 6 6 6
1 1 1 0 0 0 1 1 1 0 0 0
1 1 0 0 0 1 1 0 0 0
1 1 0 0 > 1 0 0 0
1 0 0 1 0 0
1 0 0 0
1 0
0 0
0 0 0 0
1 0 0 > 0 0 0
1 1 0 0
1 1
A more direct bijection between the two pictures going
in the other direction comes from counting the 0's in
the respective downward sloping diagonals, and adjusting
by adding 1,2,3,...:
0 1 1 2 1 3
2 + 2 = 4 3 + 2 = 5
3 3 6 3 3 6
An easy way to implement promotion when representing
the order ideals as tuples is to reduce each entry
by 1 mod n and cyclically shifting the entries so
that they are in increasing order.
1 0 6 3
4 > 3 > 3 > 5
6 5 5 6
This picture makes it clear that the nth power of promotion
is the identity map in this case.
VII. Cyclic sieving
Here we take the unrescaled point of view.
Define an augmented Ppartition as a triple consisting of
a Ppartition and two numbers (called the floor and the ceiling)
such that every entry in the Ppartition lies weakly between
the floor and the ceiling.
For fixed P, consider the set of augmented Ppartitions
with floor 0 and ceiling n, with n = 0, 1, 2, ...;
these form a cone, which might call the (reverse) "order cone".
We can think of promotion as acting on the whole cone,
not just its slices.
When P = [a] x [b], the action of promotion on the order cone
has order a+b.
If we try to do naive cyclic sieving on the lattice points
in the order cone by counting fixed points, we get nonsense,
because there are infinitely many points
fixed by every power of the promotion map.
But if we qenumerate the lattice points according to
which slice they're in, then everything is finite
(since there are only finitely many points in each slice).
Then we can do cyclic sieving with enumeration in Z[q]
instead of Z. This works out very nicely,
and lets us formulate a CSP in which the sieving polynomial
is nothing other than the qEhrhart polynomial of the cone
in the sense of Chapoton.
This result isn't new  it's just a packaging of a CSP
due to Rhoades  but the viewpoint may prove productive.
VIII. Horizons
I don't know how this picture lifts to the birational realm
(which I don't have time to define), but I'm sure that it does,
and that it has links to the octahedron recurrence.
When P is the root poset of type A, there seems to be
a "qCSP" in the order cone, but I haven't worked it out.
I haven't looked at other root posets or minuscule posets,
but they probably yield qCSP's as well.
What happens when P is a more general RCembedded poset,
and we look at promotion on the order cone?
Each orbit is finite, because promotion sends each point
to another point in the same slice, and each slice is finite.
But the order of the map can be infinite, and often is!
When promotion has infinite order, it's a priori possible
that "most" orbits in the order cone are large.
That is, for fixed k, the proportion of points in the nth layer
belonging to orbits of size k could go to zero as n goes to infinity.
But what we tend to see is that, for specific values of k,
the proportion of points in the nth layer that belong to orbits
of size k goes to a nonzero value as n goes to infinity.
Moreover, there are interesting numbertheoretic regularities
in the orbit structure. For one poset P related to 4by4 ASMs,
and an action that's analogous to promotion
(one composes all the toggle operations in a particular order),
there are lots of points of period 8, and lots of points
of period 24, but essentially none of period 16.
So toggle group actions on the order cone of a poset
can exhibit many interesting dynamical phenomena.
Stay tuned!