The symmetric functions catalog

An overview of symmetric functions and related topics

2021-09-21

LLT polynomials

LLT polynomials were originally introduced by Lascoux, Leclerc and Thibon in [LLT97]. It is a large family of symmetric functions, and can be seen as a $q$-deformations of products of skew Schur functions. This family contains the usual Schur polynomials, the skew Schur functions and contain the family of transformed Hall–Littlewood polynomials. The original motivation for LLT polynomials was to study certain plethysm coefficients, and a relationship with the Fock space representation of the quantum affine algebra $U_q(\widehat{sl_n}).$ There are generalizations to other types, see C. Lecouvey [Lec09], and also (a different generalization) by Grojnowski and Haiman [GH06].

The original definition expresses the LLT polynomials (called spin LLT polynomials) as a sum over so called ribbon tableaux, weighted with a spin statistic. The authors originally named them ribbon Schur functions, but they are now referred to as LLT polynomials.

In [LT00] it is proved that the coefficients in the Schur basis of spin LLT polynomials are parabolic Kazhdan–Lusztig polynomials. For the connection with Kazhdan–Luztig polynomials and the more representation-theoretical connection, see [LR19a].

LLT polynomials have a prominent role in the study of diagonal harmonics. See [BHMPS21] for recent results in this area.

Definition (ribbons)

The original definition is given in [LT00]. A modern reference is [Iij13].

Let $\SSYT^{(k)}(\lambda/\mu)$ be the set of $k$-ribbon tableaux of shape $\lambda/\mu.$ Then the spin LLT polynomial is defined as

\[ \LLTG^{(k)}_{\lambda/\mu}(\xvec;q) \coloneqq \sum_{T \in \SSYT^{(k)}(\lambda/\mu)} \xvec_T q^{spin(T)}. \]

Definition (tuples)

M. Bylund and M. Haiman discovered an alternative way to model LLT polynomials. These are indexed by $k$-tuples $\nuvec$ of skew Young diagrams. When $k=1,$ we recover a single skew Schur function. The Bylund–Haimain model is described in [HHL05] where it is proved that the two models are equivalent. The proof uses using a version of the Littlewood map, which sends ribbon tableaux to tuples of semi-standard Young tableaux.

Given a $k$-tuple of skew-shapes $\nuvec,$ let

\[ \SSYT(\nuvec) = \SSYT(\nuvec^1) \times \SSYT(\nuvec^2)\times \dotsm \times \SSYT(\nuvec^k) \]

where $\SSYT(\lambda)$ is the set of skew semi-standard Young tableaux of shape $\lambda.$ For $T = (T^1,T^2,\dotsc,T^k) \in \SSYT(\nuvec),$ let $\xvec^T$ denote the product $\xvec_{T^1}\dotsm \xvec_{T^k}$ where $\xvec_{T^i}$ is the usual weight of the semi-standard Young tableau $T^i.$ Given a cell $u = (r,c)$ (row, column) in a skew diagram, the content of $u$ is defined as $c(u)\coloneqq c-r.$

Entries $T^i(u) \gt T^j(v)$ in a tuple form an inversion if either

  • $i\lt j$ and $c(u) = c(v),$ or
  • $i \gt j$ and $c(u) = c(v)-1.$

Finally, we can define the LLT polynomial

\[ \LLT_\nuvec(\xvec;q) = \sum_{T \in \SSYT(\nuvec)} q^{\inv(T)} \xvec_T \]

where $\inv(T)$ is the total number of inversions appearing in $T.$ When all shapes in $\nuvec$ consist of single boxes, we get the family of unicellular LLT polyomials. Note that $\LLT_\nuvec(\xvec;1) = \prod_{i} \schurS_{\nuvec^i}(\xvec),$ a product of skew Schur polynomials.

Example.

Tuples $\nuvec$ are traditionally illustrated in the French notation when dealing with LLT polynomials. Below, the $3$-tuple $32/1,$ $31,$ $33/21$ of skew shapes is illustrated. Note that boxes with same content are placed on the same diagonal (oriented up-right). The numbers indicate the reading order which has a certain significance.

If $F$ is a filling of the diagram, we have for example inversions if $F(1)\lt F(2)$ or $F(2)\lt F(3).$

      $\square$$5$$8$
      $\square$$\square$$11$
         
   $2$     
   $4$$7$$10$   
         
$1$$3$       
$\square$$6$$9$      

The skew boxes have been marked with $\square.$

The original spin LLT polynomials and the modern LLT polynomials are related as follows. If $\nuvec$ is the $k$-tuple obtained as the $k$-quotient of $\lambda/\mu,$ then there is some $e,$ depending only on $\lambda/\mu,$ such that

\[ q^e \LLT_\nuvec(\xvec;q^{-2}) = \LLTG^{(k)}_{\lambda/\mu}(\xvec;q). \]

See [Prop. 6.17, GH06].

Vertex-model

It has recently been shown that LLT polynomials can be realized as the partition functions of certain colored fermionic vertex models, see [CGKM20] and [ABW21]. For connection with fermionic vertex models, see [BBBG20].

Properties

Murnaghan–Nakayama rule

Pieri rule

Cauchy Identity

A Cauchy identity for the spin LLT polynomials was first given in [Lam05], and a combinatorial proof is given in [van05].

In [CGKM20], the authors describe a Yang–Baxter integrable vertex model for LLT polynomials, and prove a Cauchy-identity. Here, the sum is taken over $k$-tuples of integer partitions,

\[ \sum_{\nuvec} \LLT_\nuvec(x_1,\dotsc,x_n;q) \LLT_{\nuvec^\textrm{rot}}(y_1,\dotsc,y_n;q) = \prod_{i=1}^n \prod_{j=1}^n \prod_{m=0}^{k-1} \frac{1}{1-x_iy_j t^m } \]

where $\nuvec^\textrm{rot}$ rotates each partition 180 degrees, and reverses the order of the tuple.

Fundamental quasisymmetric expansion

It is fairly straightforward from the tuples definition to recover the expansion in the fundamental quasisymmetric basis. This is done in [HHL05] and we have that

\[ \LLT_\nuvec(\xvec;q) = \sum_{T \in \SYT(\nuvec)} q^{\inv(T)} \gessel_{D(T)}(\xvec). \]

The set $\SYT(\nuvec)$ consists of all fillings of $\nuvec$ using entries $1,2,\dotsc,$ so that each shape has increasing rows and columns. The descent set $D(T)$ is computed with respect to the reading word. That is, $i$ is a descent if $i+1$ appear before $i$ when reading the boxes of $\nuvec$ in the reading order.

Schur positity

It is proved in [LT00] that $\LLT_\nuvec(\xvec;q)$ is Schur-positive whenever $\nuvec$ is a $k$-tuple of straight shapes. The proof uses the Fock space representation of $U_q(\widehat{sl}_n),$ see [Iij13] for some background.

I. Grojnowski and M. Haiman proves in an unpublished preprint, [GH06], that all LLT polynomials $\LLT_\nuvec(\xvec;q)$ for arbitrary tuples of skew shapes, are Schur positive. They use Hecke algebras and deep representation theory — their proof does not give a combinatorial formula for the Schur coefficients.

Some partial progress on a combinatorial proof of Schur positity is given in [Rob13].

The case when the tuple consists of $k\leq 3$ ribbons is considered by J. Blasiak [Bla16], and and explicit Schur expansion is given. Note that the ribbons need not be connected. This result is used to show that Macdonald polynomials indexed with shapes that have at most three columns, are Schur positive.

In [Tom20], F. Tom gives a combinatorial formula for the Schur expansion of certain vertical-strip LLT polynomials, whenever the underlying unit-interval graph is triangle-free (see the section on unicellular LLT polynomials). He uses a generalization of cocharge. This generalizes an earlier result by Alexandersson and Uhlin, [AU20].

Unicellular LLT polynomials

The unicellular LLT polynomials is a subset of LLT polynomials indexed by tuples of skew shapes, such that each shape is a single box. In [CM17] and [AP18] it is observed that there is a more convenient way to describe unicellular LLT polynomials, by using unit interval graphs.

Definition

The unicellular LLT polynomials indexed by an area sequence $\avec$ of length $n$ is defined as

\[ \LLT_\avec(\xvec;q) \coloneqq \sum_{\kappa : [n]\to \setP } x_{\kappa(1)}\dotsm x_{\kappa(n)} q^{\asc(\kappa)}. \]

Here we use the same notation as for the chromatic quasisymmetric functions and we recommend the reader to first consult this text.

Example (Bijection between tuples and Dyck diagrams).

The 3-tuple of skew shapes $3211/211,$ $4221/321,$ $421/31$ is a unicellular LLT polynomial. The boxes have been labeled in reading order. The corresponding boxes are labeled in the Dyck diagram which has area sequence $011101012.$ See [AP18] for the explicit bijection.

        $ 3$   
         $ 5$  
           $ 9$
    $ 1$       
     $ 4$      
            
       $ 8$    
$2$           
            
 $ 6$          
  $ 7$         
        $ 9$
       $ 8$ 
      $ 7$  
     $ 6$   
    $ 5$    
   $ 4$     
  $ 3$      
 $ 2$       
$ 1$        

In general, if the $k$-tuple consists of (disconnected) ribbons, then the entries in the area sequence are less than $k.$

Properties

The complete graphs on $n$ vertices are unit-interval graphs. We have that

\[ \LLT_{K_n}(\xvec;q) = \macdonaldH_{(n)}(\xvec;q,t) = \sum_{T \in \SYT(n)} q^{\cocharge(T)}\schurS_{\lambda(T)}(\xvec). \]

Note thata $\macdonaldH_{(n)}(\xvec;q,t)$ is a modified Macdonald polynomial and the last sum is a modified Hall–Littlewood polynomial.

In [AP18], it is proved that for any area sequence $\avec$ of length $n,$

\[ \omega \LLT_{\avec}(\xvec;q) = q^{(a_1+a+2+\dotsb+a_n)} \LLT_{\avec^T}(\xvec;1/q) \]

where $\avec^T$ denotes the transpose of the Dyck diagram. From the definition, it is clear that

\[ \LLT_{\avec^T}(x_1,x_2,\dotsc,x_n;q) = \LLT_{\avec}(x_n,x_{n-1},\dotsc,x_1;q) \]

and since the polynomials are symmetric it follows that $\LLT_{\avec^T}(\xvec;q) = \LLT_{\avec}(\xvec;q).$

Relation with chromatic quasisymmetric functions

See the page on chromatic quasisymmetric functions.

We have that $\LLT_{\avec}(\xvec;q)$ is the graded Frobenius characteristic of an $n!$-dimensional space, see [Gua16]. In particular, the Hilbert series is given by

\[ \langle \LLT_{\avec}(\xvec;q), \completeH_{1^n} \rangle = \sum_{\sigma \in \symS_n} q^{\asc(\sigma)}. \]

Recursions

There are a few recursions and linear relations related to unicellular LLT polynomials. For example, Lee's three term recursion in [Lee18]. We provide short bijective proofs of Lee's recursions in [Ale20].

Lee's recursions are generalized further by C. Miller, see [Eq. (2.2), Mil19]. For more generalizations and results on linear relations between LLT polynomials, see [Tom20] and [Kea21].

Schur expansion

It is a major open problem to find a combinatorial rule for the Schur expansion of $\LLT_\avec(\xvec;q).$ For so called melting lollipop graphs, a combinatorial formula for the Schur expansion is given in [HNY20].

Example.

We have the following Schur expansions for area sequences of length $3$:

\begin{align*} \LLT_{000}(\xvec;q)&=\schurS_{3}+2\schurS_{21}+\schurS_{111} \\ \LLT_{001}(\xvec;q)&=\schurS_{3}+(1+q)\schurS_{21}+q \schurS_{111} \\ \LLT_{011}(\xvec;q)&=\schurS_{3}+2q \schurS_{21}+q^2 \schurS_{111} \\ \LLT_{012}(\xvec;q)&=\schurS_{3}+(q+q^2)\schurS_{21}+q^3 \schurS_{111} \end{align*}

Since LLT polynomials are $q$-deformations of Littlewood–Richardson coefficients, see [LT00], it is straightforward to see that in the special case of unicellular LLT polynomials (a $q$-deformation of a product of $n$ single-box skew Schur functions) we have the following.

Conjecture (See [LT00]).

There is a statistic $c_\avec(T)$ on standard Young tableaux depending on $\avec,$ such that

\[ \LLT_{\avec}(\xvec;q) = \sum_{T \in \SYT(n)} q^{c_\avec(T)} \schurS_{\lambda(T)}. \]

By comparing the coefficients of $x_1 x_2\dotsm x_m$ on both sides, it follows that we must have the following relationship

\[ \sum_{\kappa \in \symS_n } q^{\asc_\avec(\kappa)} = \sum_{\lambda \vdash n} f^\lambda \sum_{T \in \SYT(\lambda)} q^{c_\avec(T)} \]

where in the left hand side we sum over all vertex-colorings of $\Gamma_\avec$ using the $n$ different colors $1,\dotsc,n$ and $f^\lambda$ is the number of standard Young tableaux of shape $\lambda.$

Theorem (See J. Blasiak [Bla16]).

Whenever $\nuvec = (\nu^1,\nu^2,\nu^3)$ is a $3$-tuple of (possibly disconnected) skew shapes, $\LLT_{(\nu^1,\nu^2,\nu^3)}(\xvec;q)$ is Schur-positive with an explicit combinatorial formula.

In the unicellular case, this corresponds to the case $\max_i a_i \leq 2$ for the area sequence indexing $\LLT_{\avec}(\xvec;q).$

In his PhD thesis [Mil19], C. Miller shows that LLT-polyomials with bandwidth at most $3$ is $3$-Schur positive, which is stronger than Schur positivity. The bandwith of size at most two was done earlier by Lee, [Lee18].

In [CH19b], a combinatorial formula for the hook coefficients, that is, coefficients of $\schurS_{\lambda}$ where $\lambda$ is a hook.

Power-sum expansion

From the power-sum expansion of the chromatic quasisymmetric functions, it is fairly easy to derive a formula for $\LLT_\avec(\xvec;q)$ in the power-sum basis. Alternatively, one can use the general machinery in [AS19b], to get the power-sum expansion, see the related result on P-partitions.

Given a poset $P$ on $n$ elements, let $\opsurj(P)$ be the set of order-preserving surjections $f: P\to [k]$ for some $k.$ The type of a surjection $f$ is defined as

\[ \alpha(f) \coloneqq (|f^{-1}(1)|,|f^{-1}(2)|,\dotsc,|f^{-1}(k)|). \]

Let $\opsurj_\alpha(P) \subseteq \opsurj(P)$ be the set of surjections of type $\alpha$ and let $\opsurj^\ast_\alpha(P) \subseteq \opsurj_\alpha(P)$ be the set of surjections $f \in \opsurj_\alpha(P)$ such that for each $j \in [k],$ $f^{-1}(j)$ is an induced subposet of $P$ with a unique minimal element.

In [AS19b], we prove the following.

Theorem (Alexandersson–Sulzgruber (2018)).

Let $O(\avec)$ denote the set of orientations of the unit interval graph given by $\avec.$ Then \begin{equation*} \omega \LLT_{\avec}(\xvec;q+1) = \sum_{\theta \in O(\avec)} q^{\asc(\theta)} \sum_{\lambda \vdash n} \frac{\powerSum_\lambda(\xvec)}{z_\lambda} |\opsurj^\ast_\lambda(P(\theta))| \end{equation*}

where $P(\theta)$ is the poset on $[n]$ given by the transitive closure of the ascending edges in $\theta.$

Example (Powersum expansion for $\avec=0121$ with orientations).

The area sequence $\avec = (0,1,2,1)$ gives the power-sum expansion

\begin{align*} \omega \LLT_{0121}(\xvec;q+1) = &(2 q^3 + q^4) \frac{\powerSum_{4}}{z_4} + (4 q^2 + 4 q^3 + q^4) \frac{\powerSum_{31}}{z_{31}} + \\ &(2 q^2 + 2 q^3 + q^4) \frac{\powerSum_{22}}{z_{22}} + (8 q + 12 q^2 + 6 q^3 + q^4) \frac{\powerSum_{211}}{z_{211}} + \\ &(24 + 48 q + 34 q^2 + 10 q^3 + q^4) \frac{\powerSum_{1111}}{z_{1111}}. \end{align*}

The following two orientations $\theta_1,$ $\theta_2$ contribute to $2 q^3 \powerSum_{22}/z_{22}.$ By convention, only the ascending edges are shown — illustrated as arrows.

  $\to$$ 4$
 $\to$$ 3$ 
$\to$$ 2$  
$ 1$   
  $\to$$ 4$
$\to$ $ 3$ 
$\to$$ 2$  
$ 1$   

For each orientation, the order-preserving surjection $f$ defined by $f(1)=f(2)=1,$ $f(3)=f(4)=2$ is the only one that fulfills all requirements of being in $\opsurj^\ast_{22}(P(\theta)).$ Here, the minimal elements of $f^{-1}(1)$ and $f^{-1}(2)$ are $1$ and $3,$ respectively.

Note that for $\theta_2,$ $g(1)=g(3)=1,$ $g(2)=g(4)=2$ is also an order-preserving surjection of type $(2,2),$ but the induced subposet $g^{-1}(2)\subset P(\theta_2)$ has both elements as minimal elements. The surjection $g$ therefore not an element in $\opsurj^\ast_{22}(P(\theta_2)).$

A similar-looking formula for the chromatic symmetric functions is provided in [Prop. 5.2, BN19a].

Elementary symmetric expansion

Together with G. Panova, we conjecture that for any unit-interval graph $\avec,$ the polynomial $\LLT_\avec(\xvec;q+1)$ is positive in the elementary symmetric function basis, see [AP18]. In spring 2017, I managed to find a precise formula for the $\elementaryE$-expansion, and it was made publicly available on arxiv in March 2019, [Ale20]. In June 2019, Michele D'Adderio [D'A19] posted a proof of $\elementaryE$-positivity for vertical-strip LLT polynomials on arxiv. The proof uses the machinery developed in [CM17]. Together with R. Sulzgruber, we proved the combinatorial formula below.

We need some more notation first in order to state the combinatorial formula. Let $\theta \in O(\avec)$ and for each $i \in [n],$ let the highest reachable vertex be defined as

\[ \mathrm{hrv}(i) \coloneqq \max\; \{ j \in [n] : i \leq_{P(\theta)} j \}. \]

Note that $\mathrm{hrv}(i) \geq i$ for all $i \in [n].$ Finally let $\pi(\theta) = (|\mathrm{hrv}^{-1}(1)|,\dotsc,|\mathrm{hrv}^{-1}(n)|).$ Thus, $\pi(\theta)$ is an integer composition of $n.$

In [AS20] we prove the following:

Theorem (Alexandersson–Sulzgruber, 2020).

For any unit-interval graph $\avec$ with $n$ vertices we have the expansion

\[ \LLT_\avec(\xvec;q+1) = \sum_{\theta \in O(\avec)} q^{\asc(\theta)}\elementaryE_{\pi(\theta)}(\xvec). \]

Notice that this result is an analog of the Stanley–Stembridge conjecture for the chromatic quasisymmetric functions.

In fact, we prove a similar formula for the vertical-strip LLT polynomials.

The path graph case was proved already in [AP18], and the complete graph case can be proved by using a certain recursion. For the class of melting lollipop graphs, a similar-looking $\elementaryE$-expansion formula is proved in [Ale20].

Example.

In the following diagram with $\avec=012223,$ we illustrate an orientation $\theta$ in $O(\avec)$ by marking the ascending edges with $\to.$

    $\to$$ 6$
    $ 5$ 
  $\to$$ 4$  
$\to$ $ 3$   
$\to$$ 2$    
$ 1$     

The highest reachable vertex for $1,2,\dotsc,6$ are $4,2,4,4,6,6,$ respectively. This is computed by simply following the marked edges as high as possible. Hence $\pi(\theta) = (0,0,1,0,3,0,2)$ and this orientation contributes with $q^5 \elementaryE_{321}(\xvec)$ to $\LLT_{012223}(\xvec;q+1).$

The full expansion is in this case

\begin{align*} \LLT_{012223}(\xvec;q+1) &=(24 q^5+60 q^6+62 q^7+33 q^8+9 q^9+q^10) \elementaryE_6 + \\ &(8 q^4+12 q^5+6 q^6+q^7) \elementaryE_{33} + \\ &(20 q^4+36 q^5+25 q^6+8 q^7+q^8) \elementaryE_{42} + \\ &(40 q^4+96 q^5+94 q^6+46 q^7+11 q^8+q^9) \elementaryE_{51} + \\ &(4 q^3+4 q^4+q^5)\elementaryE_{222} + \\ &(36 q^3+50 q^4+24 q^5+4 q^6) \elementaryE_{321} + \\ &(34 q^3+69 q^4+56 q^5+21 q^6+3 q^7) \elementaryE_{411} + \\ &(19 q^2+17 q^3+4 q^4) \elementaryE_{2211} + \\ &(20 q^2+28 q^3+15 q^4+3 q^5) \elementaryE_{3111} + \\ &(10 q+6 q^2+q^3) \elementaryE_{21111} + \\ &\elementaryE_{111111} \end{align*}

A recent paper, https://arxiv.org/pdf/2011.15080.pdf, refines this result to the case of so-called LLT cumulants, where certain connectivity requirements are imposed.

Non-commutative unicellular LLT polynomials

J.-C. Novelli and J.-Y. Thibon [Thm. 6.2, NT19] introduce a non-commutative lift of the unicellular LLT polynomials. They show that these are positive in a non-commutative analogue of the Gessel quasisymmetric basis, as well as a (non-commutative) plethystic relation that with chromatic quasisymmetric functions.

Supersymmetric LLT polynomials

There is a notion of supersymmetric LLT polynomials introduced by T. Lam. See also [BBBG20] where metaplectic symmetric functions are introduced.

See [ABW21] for the definition of factorial LLT polynomials.

References