Young tableaux as lattice points in order cones: promotion, fiber-flipping 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 (fiber-flipping) underlies both the Bender-Knuth approach to promotion of tableaux and Striker and Williams' toggle-group, 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, Gelfand-Tsetlin 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 one-to-one 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 non-standard.) 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 Bender-Knuth 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 RC-embedded 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) -> (i-1,j-1) or (i+1,j-1). 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? Gelfand-Tsetlin triangles. III. GT triangles See Kirillov and Berenstein's "Groups generated by involutions, Gelfand-Tsetlin patterns, and combinatorics of Young tableaux". An example of an integral Gelfand-Tsetlin 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 row-lengths in the kth row of the Gelfand-Tsetlin 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 n-A 0's. Recall that B_i denotes the ith Bender-Knuth 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 1-dimensional 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 Gelfand-Tsetlin triangle with all entries between 0 and n, scaled down by n, is a point in the "Gelfand-Tsetlin 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 "Gelfand-Tsetlin cone", and the Gelfand-Tsetlin 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) order-reversing functions from the poset P into {0,1}. Define the (reverse) order polytope O^{op}(P) of P as the set of (weakly) order-reversing functions from the poset P into [0,1]. Then toggling can be seen as a form of fiber-flipping in the (reverse) order polytope of P. Define PL toggles (apply fiber-flipping in the direction associated with a particular element of P). If P has an RC-embedding, 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 P-partitions (order-reversing 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 Einstein-Propp 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 [n-A]. Under the above-described 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 piecewise-linear promotion operator on the rational points in the (reverse) order polytope of P with denominator dividing B, or (equivalently) to the action of the piecewise-linear promotion operator on the set of P-partitions with entries between 0 and B. VI. The single-column 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 piecewise-linear promotion operator on the vertices of the order polytope of [A] × [n-A]. 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 P-partition as a triple consisting of a P-partition and two numbers (called the floor and the ceiling) such that every entry in the P-partition lies weakly between the floor and the ceiling. For fixed P, consider the set of augmented P-partitions 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 q-enumerate 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 q-Ehrhart 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 "q-CSP" 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 q-CSP's as well. What happens when P is a more general RC-embedded 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 non-zero value as n goes to infinity. Moreover, there are interesting number-theoretic regularities in the orbit structure. For one poset P related to 4-by-4 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!