The symmetric functions catalog

An overview of symmetric functions and related topics

2022-06-09

A nice online introduction is given here.

Crystals on words and semi-standard tableaux

The notion of crystals (in type $A$) refer to a set of raising- and lowering operators that give rise to a certain graph structure on combinatorial objects (words, tableaux) with weights. If the operators satisfy certain axioms, each connected component in the graph is a singe Schur function.

The operators also provide an explicit $\symS_n$-action on the set of objects, thus also providing a representation-theoretic proof of Schur positivity.

A nice introduction to crystals in type $A$ is given in [Shi05]. See also [BS17] for a thorough introduction to crystals.

In this video, J. Blasiak gives a nice overview of crystals in type A, starting at 25:00.

Operators on words

We define two operators, $\cryse_i,$ $\crysf_i : \setN^k \to \setN^k \cup \{ \emptyset \}$ as follows. Given a word $w$ consider the subword $w_i$ consisting only of the letters $i$ and $i+1.$ Replace each instance of $i$ with a right bracket and each $i+1$ with a left bracket. Remove all pairs of matching brackets and consider the remaining unmatched brackets, which is now consists of $a$ right-brackets and $b$ left-brackets. These brackets correspond to a subword $w'$ of the form $i^a (i+1)^b$ in $w.$

The operator $\cryse_i$ acting on $w$ turns the leftmost $i+1$ of $w'$ into $i,$ if such an entry exists, otherwise, $\cryse_i(w)=\emptyset.$ Similarly, $\crysf_i$ acting on $w'$ turns the rightmost $i$ in $w'$ into $i+1,$ if such an entry exists, otherwise, $\crysf_i(w)=\emptyset.$ The operator $\cryse_i$ is a crystal raising operator while $\crysf_i$ is a crystal lowering operator.

We also define crystal reflections $\cryss_i(w)$ by replacing the subword $i^a (i+1)^b$ above with $i^b (i+1)^a.$ Such a reflection can be realized by applying a number of $\cryse_i$ or $\crysf_i$ to the word. The crystal reflection operators $\cryss_1,\dotsc,\cryss_{n-1}$ generate an $\symS_n$ action on words. These crystal reflection operators are also called Lascoux–Schützenberger involutions.

Example.

Let us compute $\crysf_2$ and $\cryse_2$ of the word $213313212131.$ First find the subword consisting of the letters $2$ and $3,$ replace with brackets and remove paired brackets.

\[ \begin{matrix} 2&1&3&3&1&3&2&1&2&1&3&1 \\ 2& &3&3& &3&2& &2& &3& \\ ]& &[&[& &[&]& &]& &[& \\ ]& &[& & & & & & & &[& \end{matrix} \]

We can now see that

\[ \crysf_2(213313212131) = \underline{3}13313212131, \qquad \cryse_2(213313212131) = 31\underline{2}313212131. \]

Strings and graphs

Given a word $w,$ consider the sequence $\dotsc, \cryse^2_i(w), \cryse_i(w), w, \crysf_i(w), \crysf^2_i(w),\dotsc.$ This is referred to an $i$-string. For example,

\[ \emptyset \overset{1}{\rightarrow} 12112111 \overset{1}{\rightarrow} 12112112 \overset{1}{\rightarrow} 12112122 \overset{1}{\rightarrow} 12122122 \overset{1}{\rightarrow} 22122122 \overset{1}{\rightarrow} \emptyset \]

is a $1$-string.

Consider the connected graph consisting of words connected with edges given by $\cryse_i$ and $\crysf_i,$ for all $i.$ This is referred to as a crystal. Each such crystal contains a unique word $w$ of the form $n^{\lambda_n} \dotsm 2^{\lambda_2} 1^{\lambda_1},$ where $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n$ is a partition. Note that for this particular word, $\cryse_i(w)=\emptyset$ for all $i.$ This word is called the highest weight in the crystal and $\lambda$ is the highest weight vector of the crystal.

Crystals on semi-standard tableaux

One can show that all words in a crystal with highest weight vector $\lambda$ are in bijection with semi-standard Young tableaux of shape $\lambda.$ In fact, the set of reading words of tableaux of shape $\lambda$ is closed under $\cryse_i$ and $\crysf_i.$ This can be proved by realizing that an $i+1$ on top of an $i$ in the tableau will always become paired brackets.

In conclusion, if a set of combinatorial objects is closed under the crystal operators, the sum over the weights of these objects is Schur-positive. One way to do this is to exhibit a crystal-preserving bijection with words or SSYTs — a bijection that commutes with the raising and lowering operators.

Note that the crystal operators $\cryse_i,$ $\crysf_i$ and $\cryss_i$ are also defined on skew semi-standard Young tableaux, by acting on the reading word. The crystal graph on $\SSYT(\lambda/\mu)$ is no longer connected — the connected components correspond to the right hand side in the Schur expansion

\[ \schurS_{\lambda/\mu} = \sum_{\nu} c^{\lambda}_{\mu \nu} \schurS_\nu. \]

Here, $c^{\lambda}_{\mu \nu}$ are the Littlewood–Richardson coefficients, and the crystal graph on $\SSYT(\lambda/\mu)$ contains $c^{\lambda}_{\mu \nu}$ connected components isomorphic to the (irreducible) crystal graph on $\SSYT(\nu).$ In other words, crystals can be used to prove the Littlewood–Richardson rule.

One important property of the crystal operators acting on skew shapes is that they are coplactic, meaning that they commute with jeu-de-taqin slides.

Example (Crystal graphs on words and SSYT).

In the following figures, the solid lines are the $\crysf_1$ edges, and the dashed lines are $\crysf_2.$ The two graphs are isomorphic, and they have to be since the highest weight is $\lambda =31$ in both cases.

Crystal on words Crystal on SSYT

Kashiwara crystals

The following definition is taken from [GL19a].

A finite $\GL_n$ Kashiwara crystal is a set $B$ together with raising and lowering operators $\cryse_i,$ $\crysf_i$ on $B$ and length functions $\epsilon_i,$ $\phi_i$ from $B$ to $\setZ,$ and a weight function $w,$ satisfying the following axioms (where $1 \leq i \leq n-1$);

  1. The operators $\cryse_i,$ $\crysf_i$ are partial inverses, and if $Y = \cryse_i(X),$ then \[ \left(\epsilon_i(Y), \phi_i(Y) \right) = \left( \epsilon_i(X)-1, \phi_i(X)+1 \right) \quad \text{and} \quad w(Y) = w(X)+ \alpha_i, \] where $\alpha_i = \evec_i - \evec_{i+1},$ the vector with coordinate $i$ set to $1,$ and coordinate $i+1$ set to $-1.$
  2. For any $i \in [n-1]$ and any $X \in B,$ $\phi_i(X) = \langle w(X), \alpha_i \rangle + \epsilon_i(X).$

The inner product used here is from the root system.

Moreover, a Kashiwara crystal is a type $A$ Stembrige crystal if

  1. If $|i-j| \gt 1$ and $\cryse_i(X),$ $\cryse_j(X)$ are defined, then their compositions are defined and equal, i.e., $\cryse_i \cryse_j(X) = \cryse_j \cryse_i(X).$ Same statement is true for $\crysf_i,$ $\crysf_j.$
  2. If $\crysf_{i \pm 1}(Y) = X,$ then \[ \left(\epsilon_i(Y) - \epsilon_i(X), \phi_i(Y) - \phi_i(X) \right) \in \{ (0,-1), (1,0) \}. \]
  3. Suppose $|i-j|=1$ and $\crysf_i(Z)=X,$ $\crysf_j(Z)=X$ are both defined. Set \[ \Delta \coloneqq \left(\epsilon_i(Z) - \epsilon_i(X), \epsilon_i(Z) - \epsilon_i(Y) \right). \] (By previous axioms, $\Delta \in \{ (1,1), (1,0), (0,1), (0,0) \}.$) If $\Delta \neq (0,0)$ then $\crysf_i \crysf_j(Z) = \crysf_j \crysf_i(Z) \neq \emptyset.$ Otherwise, $\crysf_i \crysf^2_j \crysf_i(Z) = \crysf_j \crysf^2_i \crysf_j(Z) \neq \emptyset.$
  4. We have the dual axiom, where the $\crysf_i$ above are replaced with $\cryse_i,$ and the $\epsilon_i$ are replaced with $\phi_i.$

These are reworded versions of Stembridge's local axioms given in [Ste03].

Demazure crystals

Demazure crystals (in type $A$) are truncated versions of the classical type $A$ crystals. Connected components are now Demazure polynomials.

Some papers using these crystal structures are [Wan20b], [AS18b] and [AG20].

Crystals for type B

In [GHPS20AO18AO20], the authors define crystal operators are defined on skew shifted SSYT. This gives a crystal structure where connected components are Schur P functions.

In [GL19a], a Sembridge-type set of local axioms are used to define a type $B$ crystal structure. The using raising and lowering operators act on shifted tableaux. These operators commute with jeu-de-taquin slides (as in type $A$), making them coplactic. This gives a crystal structure where connected components are Schur Q functions.

In the follow-up paper, M. Gillespie, J. Levinston and K. Purbhoo [GLP20] further studies this crystal structure on skew shifted tableaux, and show how one can act on the reading-word of the tableaux. Furthermore, they identify the highest weight elements in the crystals, which turn out to be shifted Littlewood–Richardson tableaux. With this machinery, they obtain a new proof of the Littlewood–Richardson rule for the Schur Q functions.

See also

There is a lot of more background and references in the Sage manual for crystals.

There are some results on the interaction with crystals and dual RSK here, [Aze06]. Also, http://www.mat.uc.pt/~oazenhas/azenhasmamede.pdf

References