2023-06-30
Gelfand–Tsetlin patterns
Gelfand–Tsetlin (sometimes spelled Cetlin or Zetlin) patterns were introduced by I. Gelfand and M. Tsetlin in [GT50], motivated by the close relationship with representation theory of $GL_n.$ A short introduction to GT-patterns can be found in [p.103, Sta01].
For a brief background, see this page on FindStat.
A Gelfand-Tsetlin pattern or GT-pattern is a triangular (or sometimes parallelogram) arrangement of non-negative integers, with certain constraints. The triangular patterns are indexed as follows.
\[ \begin{matrix} x_{n1} & & x_{n2} & & \cdots & & \cdots & & x_{nn} \\ & \ddots & & \ddots & & & \iddots & & & \\ % & & x_{13} & & x_{23} & & x_{33}\\ % & & & x_{12} & & x_{22} \\ & & x_{21} & & x_{22}\\ & & & x_{11} \end{matrix} \]The less common parallelogram patterns are indexed as follows.
\[ \begin{matrix} x_{n1} & & x_{n2} & & \cdots & & \cdots & & x_{nm} \\ & \ddots & & \ddots & & & & & & \ddots \\ % & & x_{13} & & x_{23} & & x_{33} & & \\ % & & & x_{12} & & x_{22} & & & \\ & & x_{11} & & x_{12} & & \cdots & & \cdots & & x_{1m} \\ & & & x_{01} & & x_{02} & & \cdots & & \cdots & & x_{0m} \end{matrix} \]The entries must satisfy the conditions
\begin{equation*} x_{i+1,j} \geq x_{ij} \text{ and } x_{ij} \geq x_{i+1,j+1} \label{eq:gtinequalities} \end{equation*}for all values of $i,$ $j$ where the indexing is defined. The inequalities simply states that horizontal rows are weakly decreasing, down-right diagonals are weakly decreasing and down-left diagonals are weakly increasing.
The weight $w(G) = (w_1,\dotsc,w_n)$ of a GT-pattern $G$ is defined as the vector where $w_i$ is the difference of the sum of row $i$ and $i-1.$ By convention, $x_{0j}=0$ if these entries are not specified.
Bijection with semi-standard Young tableaux
The conditions ensures every row in the pattern defines an integer partition. Furthermore, any two adjacent rows define a skew shape. These properties enables us to biject triangular GT-patterns with Young tableaux and parallelogram GT-patterns with skew Young tableaux.
The skew shape defined by row $j$ and $j+1$ in a GT-pattern $G$ describes which boxes in a tableau $T$ that have content $j.$ In particular, if $T$ has shape $\lambda/\mu$ then the first row in $G$ is $\mu$ and the last row is $\lambda.$
The following triangular GT-pattern
\[ \begin{matrix} 5 & & 4 & & 2 & & 1 & & 1 & & 0\\ & 5 & & 3 & & 2 & & 1 & & 0\\ & & \color{blue} 3 & & \color{blue} 3 & & \color{blue} 2 & & \color{blue} 1 \\ & & & 3 & & 3 & & 1 & \\ & & & & 3 & & 2 & \\ & & & & & 3 & \\ \end{matrix} \]is in bijection with the semi-standard Young tableau below.
$1$ | $1$ | $1$ | $5$ | $5$ |
$2$ | $2$ | $3$ | $6$ | |
$3$ | $4$ | |||
$4$ | ||||
$6$ |
Notice that the fourth row in the GT-pattern is $3321$ and the shape of all entries less than or equal to four in the tableau is also $3321.$
The skew Young tableau
$1$ | $3$ | ||
$1$ | $2$ | ||
$4$ | |||
$2$ |
is in bijection with the GT-pattern
\[ \begin{matrix} 4 & & 3 & & 2 & & 1\\ & 4 & & 3 & & 1 & & 1\\ & & 3 & & 3 & & 1 & & 1\\ & & & 3 & & 2 & & 1 & & 0\\ & & & & 2 & & 1 & & 1 & & 0\\ \end{matrix} \]Observe that in any GT-pattern, $x_{i+1,j} - x_{i,j}$ counts the number of boxes with content $i$ in row $j$ in the corresponding tableau. Thus, the weight of a GT-pattern is the same as the weight of the corresponding tableau.
There is a crystal graph structure on semi-standard Young tableaux. The corresponding crystal graph on GT-patterns is described explicitly in https://arxiv.org/pdf/2005.06639.pdf.
Tokuyama's formula
Let $SGT(\lambda)\subset \gtp(\lambda)$ be the set of strict Gelfand–Tsetlin patterns. This is the subset of patterns where each row is strictly decreasing. Consider tuples $(a,b,c)$ in the pattern arranged as $\begin{smallmatrix} a && b\\ & c \end{smallmatrix}.$ Let $S(G)$ be the number of entries $c$ such that $a\gt c \gt b,$ and let $L(G)$ be the number of entries $c$ such that $a=c.$
Let $\rho = (n-1,n-2,\dotsc,1,0).$ Then (see [Tok88])
\begin{equation*} \schurS_{\lambda}(x_1,\dotsc,x_n) \cdot \prod_{1 \leq i \lt j \leq n} (x_i + t x_j) = \sum_{G \in SGT(\lambda + \rho)} (1+t)^{S(G)} t^{L(G)}\xvec^{w(G)}. \end{equation*}Note that this interpolates between the Weyl character formula, and the SSYT definition of Schur polynomials.
See also [Sta86a] for some special cases, and connection with plane partitions and alternating sign matrices.
Gelfand–Tsetlin polytopes
By specifying the top row in a triangular GT-pattern as $\lambda$ and imposing the inequalities above we get a convex polytope. This is a Geltand–Tsetlin polytope, $\gtp_{\lambda} \subset \setR^{n(n+1)/2}.$ By construction, the integer lattice points in $\gtp_{\lambda}$ is in bijection with $\SSYT(\lambda).$ The analogous statement holds for parallelogram GT-patterns where also the bottom row $\mu$ is a fixed integer partition. These polytopes are denoted $\gtp_{\lambda\mu} \subset \setR^{nm}.$ Below, we use $d$ to denote the dimension ($n(n+1)/2$ or $mn$) of the ambient space.
Unimodular triangulation and marked posets
The polytopes $\gtp_{\lambda\mu}$ admit unimodular triangulations. This means that the polytopes can be decomposed into simplices with integer vertices and normalized volume $1.$ For a short proof, see [Ale19b].
As a consequence, Gelfand–Tsetlin polytopes have integer vertices, and have the integer decomposition property (IDP). This means that if $p$ is a lattice point in $k \gtp_{\lambda\mu}$ for some integer $k\geq 1,$ then $p$ can be expressed as $p_1 + \dotsb + p_k$ where each $p_i$ is a lattice point in $\gtp_{\lambda\mu}.$ This can be proved directly by bijecting to semi-standard tableaux, see [Subsection 2.3, Ale16a].
A. Tsuchiya generalize the notion of IDP to $k$-tuples of polytopes (the $k=2$ case was introduced in [HH17]). The following theorem follows very easy from the bijection with SSYT.
Let $\gtp_{\lambda^1},\dotsc,\gtp_{\lambda^k}$ be GT-polytopes, embedded in the same ambient space by padding the partitions with zeros of needed. Then
\[ \setZ^d \cap \left( \gtp_{\lambda^1} + \dotsb + \gtp_{\lambda^k} \right) = \left( \setZ^d \cap \gtp_{\lambda^1} \right) + \dotsb + \left(\setZ^d \cap \gtp_{\lambda^k} \right). \]By letting all $\lambda^i$ be equal, we recover the usual IDP.
This theorem does not generalize to skew shapes. The pair $\gtp_{3}$ and $\gtp_{2/1}$ yields a counter-example.
Gelfand–Tsetlin polytopes are special cases of so called marked order polytopes, which generalizes order polytopes considered by R. Stanley, [Sta86b]. In [ABS11], the authors generalize the bijection between order polytopes and chain polytopes and give a marked chain polytope analogue of GT-polytopes. In type $A$ these analogues are so called Feigin–Fourier–Littelmann polytopes.
The Gelfand–Tsetlin polytopes are also special cases of so called flow polytopes, see [LMD19a].
Ehrhart polynomials
By definition, it follows that for a partition of length $m,$
\[ \left| \setZ^d \cap \gtp_{\lambda} \right| = \schurS_{\lambda}(1^m) = \prod_{1 \leq i \lt j \leq m } \frac{\lambda_i - \lambda_j + j-i}{j-i}, \]where the last identity is due to Stanley's hook-content formula. Furthermore, the Ehrhart polynomial of $\gtp_{\lambda}$ is given by
\[ Ehr(\gtp_{\lambda};k) = \prod_{1 \leq i \lt j \leq m } \frac{k(\lambda_i - \lambda_j) + j-i}{j-i}. \]We have that \[ 1 + \sum_{n\geq 1} t^n |\schurS_{\lambda/\mu}(1^m)| = \frac{ \sum_{T \in \SYT(\lambda/\mu)} z^{\des(T)} }{(1-t)^{1+|\lambda/\mu|}}. \]
In particular, the $h^*$-polynomial of $\gtp_{a^b}$ is the descent-generating polynomial of rectangular standard Young tableaux; $\sum_{T \in \SYT(a^b)} z^{\des(T)}.$
Use [Eqs. (7.96), (7.108), Sta01], where one needs to note that GT-patterns for rectangular SSYTs can be made in bijection with rectangular plane partitions.
The coefficients of the Ehrhart polynomial of $\gtp_{\lambda\mu}$ has non-negative coefficients. Equivalently, the function
\[ f(k) = \schurS_{k\lambda/k\mu}(1^m) \]is a polynomial in $k$ with non-negative coefficients.
For example, $m=3,$ $\lambda=321$ and $\mu=1$ gives the Ehrhart polynomial
\[ Ehr(\gtp_{321/1},k) = \frac{1}{2} (k^5+6 k^4+14 k^3+16 k^2+9 k+2). \]Do all Kogan faces of Gelfand–Tsetlin polytopes have non-negative Ehrhart polynomial? There is an example (see [Ale19b]) of a (non-Kogan) face where the Ehrhart polynomial has a negative coefficient. However, this polynomial is of degree 20.
Vertices, $f$-vectors and differential equations
Ther has been some effort in counting the number of vertices of GT-polytopes. In [GKT13], the authors describe a generating function that enumerates the vertices of $\gtp_{\lambda}.$
Let $V(1^{i_1},2^{i_2},\dotsc,k^{i_k})$ denote the number of vertices of $\gtp_{\lambda}$ where $\lambda$ is the partition with type $(i_1,i_2,\dotsc,i_k).$ Consider the generating function
\[ E_k(z_1,\dotsc,z_k) \coloneqq \sum_{i_1,\dotsc,i_k \geq 0} V(1^{i_1},2^{i_2},\dotsc,k^{i_k}) \frac{z_1^{i_1}}{i_1!} \dotsm \frac{z_k^{i_k}}{i_k!}. \]The formal power series $E_k(z_1,\dotsc,z_k)$ satisfies the partial differential equation
\[ \left( \frac{\partial^k}{\partial z_1 \dotsm \partial z_k} - \left(\frac{\partial}{\partial z_1}-\frac{\partial}{\partial z_2}\right) \dotsm \left(\frac{\partial}{\partial z_{k-1}}-\frac{\partial}{\partial z_k}\right) \right)E_k = 0 \]This result is later improved in [Thm. 1.14, ACK18], where the authors provide a differential equation for the full $f$-vector of GT-polytopes. They consider the generating function
\[ F_k(z_1,\dotsc,z_k;t) \coloneqq \sum_{d\geq 0} \sum_{i_1,\dotsc,i_k \geq 0} t^d f_d(1^{i_1},2^{i_2},\dotsc,k^{i_k}) \frac{z_1^{i_1}}{i_1!} \dotsm \frac{z_k^{i_k}}{i_k!}. \]where $f_d$ is the number of $d$-dimensional faces of $\gtp_{\lambda}.$
Type B and C
There are analogues of GT-polytopes for type $B$ and $C,$ see [ABS11].
Weight-restricted Gelfand–Tsetlin polytopes
Let $\gtp_{\lambda,w}\subseteq \gtp_{\lambda}$ be the Gelfand–Tsetlin polytope defined as $\gtp_{\lambda}$ but with the additional constraint that the difference of the row row sums of row $j+1$ and $j$ is exactly $w_j.$
By construction, lattice points in $\gtp_{\lambda,w}$ are in bijection with $\SSYT(\lambda,w).$ Therefore, the number of lattice points in $\gtp_{\lambda,w}$ is given by the Kostka coefficient $K_{\lambda w}.$
We do the analogous definitions for parallelogram GT-patterns and skew shapes.
Non-integrality and vertices
Contrary to $\gtp_{\lambda},$ the polytopes (also called Gelfand–Tsetlin polytopes) $\gtp_{\lambda,w}$ are not always integral. In fact, the denominators of the vertices can get arbitrary large, see [DLM04a].
In [Ale16a], we prove that for $\lambda \vdash n,$ the polytope $\gtp_{\lambda,1^n}$ is non-integral unless $\lambda=(2,2)$ or a hook shape.
Saturation theorem
The following theorem is a GT-polytope analogue of the celebrated Saturation theorem, proved by A. Knutson and T. Tau, [KT99KTW04]. They proved a similar statement for so called Berenstein–Zelevinsky polytopes.
Every non-empty Gelfand–Tsetlin polytope $\gtp_{\lambda/\mu,w}$ contains at least one vertex with integer coordinates.
Ehrhart polynomials and period collapse
Since the $\gtp_{\lambda/\mu,w}$ are not lattice polytopes, one does not expect the Ehrhart function to be a polynomial. However, these polytopes exhibit a period collapse [HM08] and they do have a polynomial Ehrhart function. See [Ras04a] for a proof of this statement.
The coefficients of the Ehrhart polynomial of $\gtp_{\lambda/\mu,w}$ are non-negative.
See also [Ale15] for related open conjectures.
We could also consider a fixed face of the Gelfand–Tsetlin polytope intersected with the hyperplane defined by a weight. Suppose $P$ is the polytope obtained from the non-skew shape $\lambda = (2,2,2)$ and $w = (1,1,\dotsc,1),$ intersected with the face requiring that there the 3 is not in the first row of the corresponding SSYTs. Then the number of lattice points in $kP$ is
\[ 3, 7, 13, 22, 34, 50, 70, 95, 125, 161, 203 \dotsc, \text{ for } k=1,2,\dotsc, \]which is a quasipolynomial of degree 3 with period 2.
Monotone triangles and alternating sign matrices
Monotone triangles are special types of triangular GT-patterns with additional constraints. First, the top row is $(n,n-1,\dotsc,1)$ and all rows must be strictly decreasing.
Monotone triangles of size $n$ are in bijection with $n \times n$ alternating sign matrices. Alternating sign matrices are matrices with entries in $\{-1,0,1\}$ such that in each row and column, the nonzero elements alternate in sign. Furthermore, the sum of the entries in each row (and column) is $1.$
Consider the following $5\times 5$ alternating sign matrix, where we omit the zeros, and $-1$ is written as $\color{blue}{\overline{1}}.$ The rows are accumulated from the bottom, so that row $k$ from the bottom is the sum of the first $k$ rows.
\[ \begin{bmatrix} &1& & & \\ 1&\color{blue}{\overline{1}}& &1& \\ &1& &\color{blue}{\overline{1}}&1\\ & &1& & \\ & & &1& \end{bmatrix} \to \begin{bmatrix} 1&1&1&1&1 \\ 1& &1&1&1 \\ &1&1& &1 \\ & &1&1& \\ & & &1& \end{bmatrix} \]For each row, we then record the columns that contains a $1$ and write the column indices in a decreasing fashion. The result is a monotone triangle.
\[ \begin{matrix} 5&&4&&3&&2&&1 \\ &5&&4&&3&&1 \\ &&5&&3&&2 \\ &&&4&&3 \\ &&&&4& \\ \end{matrix} \]D. Zeilberger [Zei95] proved that the number of monotone triangles of size $n,$ or equivalently, number of $n\times n$ alternating sign matrices is given by
\[ \prod_{j=0}^{n-1}\frac{(3j+1)!}{(n+j)!}. \]A generalization of this result is given in [Fis06], where difference operators are used in a formula to count the number of monotone triangles with prescribed top row $\lambda.$
Applications
Schur polynomials
The close connection between GT-patterns and Schur polynomials is quite apparent. The Schur polynomial $\schurS_\lambda(x_1,\dotsc,x_n)$ can be expressed as a sum over $GT(\lambda),$ the set of triangular GT-patterns with top row equal to $\lambda.$ We have that
\[ \schurS_\lambda(x_1,\dotsc,x_n) = \sum_{G \in GT(\lambda) } \xvec^{w(G)} \]where $w$ depends on the row-sums of the pattern $G.$
Hall–Littlewood polynomials
The identity for Schur functions can be generalized to Hall–Littlewood polynomials, via a weighted version of Brion's theorem.
Let $\lambda$ be a partition. Then
\begin{equation*} \hallLittlewoodP_\lambda(\xvec;t) = \sum_{G \in GT(\lambda) } p_G(t) \xvec^{w(G)} \end{equation*}where $p_G(t)$ is a certain statistic that depends on $G.$
This theorem can also be proved via other means, see [Mac95].
Key polynomials
The key polynomials generalize the Schur polynomials. In [KST12], a formula for key polynomials is proved, where the sum runs over lattice points in a union of certain faces of $GT(\lambda),$ see key polynomials from GT-patterns for details.
Schubert polynomials
It was recently proved in [LMD19b] that Schubert polynomials can be expressed as a sum over lattice points in a Minkowski-sum of GT-polytopes.
References
- [AA19a] Per Alexandersson and Elie Alhajjar. Ehrhart positivity and Demazure characters. Algebraic and Geometric Combinatorics on Lattice Polytopes. World Scientific, June 2019.
- [ABS11] Federico Ardila, Thomas Bliem and Dido Salazar. Gelfand–Tsetlin polytopes and Feigin–Fourier–Littelmann–Vinberg polytopes as marked poset polytopes. J. Comb. Theory, Ser. A, 118(8):2454–2462, 2011.
- [ACK18] Byung Hee An, Yunhyung Cho and Jang Soo Kim. On the f-vectors of Gelfand–Cetlin polytopes. European Journal of Combinatorics, 67:61–77, January 2018.
- [Ale15] Per Alexandersson. A combinatorial proof of the skew K-saturation theorem. Discrete Mathematics, 338(1):93–102, 2015.
- [Ale16a] Per Alexandersson. Gelfand–Tsetlin polytopes and the integer decomposition property. European Journal of Combinatorics, 54:1–20, May 2016.
- [Ale19b] Per Alexandersson. Polytopes and large counterexamples. Experimental Mathematics, 28(1):115–120, 2019.
- [DLM04a] Jesús A. De Loera and Tyrrell B. McAllister. Vertices of Gelfand–Tsetlin polytopes. Discrete & Computational Geometry, 32(4):459–470, September 2004.
- [Fis06] Ilse Fischer. The number of monotone triangles with prescribed bottom row. Advances in Applied Mathematics, 37(2):249–267, August 2006.
- [FM16] Boris Feigin and Igor Makhlin. A combinatorial formula for affine Hall–Littlewood functions via a weighted Brion theorem. Selecta Mathematica, 22(3):1703–1747, March 2016.
- [GKT13] Pavel Gusev, Valentina A. Kiritchenko and Vladlen A. Timorin. Counting vertices in Gelfand–Zetlin polytopes. J. Comb. Theory, Ser. A, 120(4):960–969, 2013.
- [GT50] Israel M. Gelfand and Michael. L. Tsetlin. Finite dimensional representations of the group of unimodular matrices. Doklady Akad. Nauk SSSR (N.S.), 71:825–828, 1950. (Russian)
- [HH17] Christian Haase and Jan Hofmann. Convex-normal (pairs of) polytopes. Canadian Mathematical Bulletin, 60(03):510–521, September 2017.
- [HM08] Christian Haase and Tyrrell B. McAllister. Quasi-period collapse and $GLn(Z)$-scissors congruence in rational polytopes. Contemporary Mathematic. American Mathematical Society, 452 2008.
- [KST12] Valentina A. Kiritchenko, Evgeny Yu Smirnov and Vladlen A. Timorin. Schubert calculus and Gelfand–Zetlin polytopes. Russian Mathematical Surveys, 67(4):685, 2012.
- [KT99] Allen Knutson and Terence Tao. The honeycomb model of $GL_n(C)$ tensor products I: proof of the saturation conjecture. Journal of the American Mathematical Society, 12(04):1055–1091, October 1999.
- [KTT04] R. C. King, C. Tollu and F. Toumazet. Stretched Littlewood–Richardson coefficients and Kostka coefficients. In Symmetry in Physics: In Memory of Robert T. Sharp. AMS / OUP, 2004.
- [KTW04] Allen Knutson, Terence Tao and Christopher Woodward. The honeycomb model of $GL_n(C)$ tensor products II: puzzles determine facets of the Littlewood–Richardson cone. Journal of the American Mathematical Society, 17(1):19–49, January 2004.
- [LMD19a] Ricky Ini Liu, Karola Mészáros and Avery St. Dizier. Gelfand–Tsetlin polytopes: a story of flow and order polytopes. arXiv e-prints, 2019.
- [LMD19b] Ricky Ini Liu, Karola Mészáros and Avery St. Dizier. Schubert polynomials as projections of Minkowski sums of Gelfand–Tsetlin polytopes. arXiv e-prints, 2019.
- [Mac95] Ian G. Macdonald. Symmetric functions and Hall polynomials. Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, Second edition, 1995. With contributions by A. Zelevinsky, Oxford Science Publications
- [Ras04a] Etienne Rassart. A polynomiality property for Littlewood–Richardson coefficients. J. Comb. Theory Ser. A, 107(2):161–179, August 2004.
- [Sta01] Richard P. Stanley. Enumerative Combinatorics: Volume 2. Cambridge University Press, First edition, 2001.
- [Sta86a] Richard P. Stanley. A Baker's dozen of conjectures concerning plane partitions. Combinatoire {\'e}num{\'e}rative. Springer Berlin Heidelberg, 1986.
- [Sta86b] Richard P. Stanley. Two poset polytopes. Discrete & Computational Geometry, 1(1):9–23, 1986.
- [Tok88] Takeshi Tokuyama. A generating function of strict Gelfand patterns and some formulas on characters of general linear groups. Journal of the Mathematical Society of Japan, 40(4):671–685, October 1988.
- [Zei95] Doron Zeilberger. Proof of the alternating sign matrix conjecture. The Electronic Journal of Combinatorics, 3(2), July 1995.