An analogue of Jeu de taquin for Littelmann’s crystal paths

Marc A. A. van Leeuwen

Université de Poitiers, Département de Mathématiques, 40 Avenue du Recteur Pineau, 86022 Poitiers, France

            maavl@mathlabo.univ-poitiers.fr
    URL: http://wwwmathlabo.univ-poitiers.fr/~maavl/

ABSTRACT

Littelmann has given a combinatorial model for the characters of representations of semisimple Lie algebras, in terms of certain paths traced in the space of (rational) weights. From it, a description of the decomposition of tensor products can be derived that generalises the Littlewood-Richardson rule (the latter is valid in type A_{n} only). We present a new combinatorial construction that expresses in a bijective manner the symmetry of the tensor product in this path model. In type A_{n}, where there is a correspondence between paths and skew tableaux, this construction is equivalent to Schützenberger’s jeu de taquin; in the general case the construction retains its most crucial properties of symmetry and confluence.

1991 Mathematics Subject Classification: 05E10. Keywords and Phrases: Jeu de taquin, Littlewood-Richardson rule, crystal

graphs, path crystals.

1 Introduction

§1. Introduction. In this note we wish to present a simple construction that appears to arise naturally in the context of Littelmann’s paths. Indeed, we found it while trying to formulate an answer to a question asked (by Alain Lascoux) during a lecture by Littelmann on this subject at the Séminaire Lotharingien; the question was whether one could exhibit combinatorially the symmetry of the tensor product in the formula given, in terms of paths, for tensor product decompositions.

This paper is organised as follows. After recalling some of Littelmann’s notions in §2, we analyse the symmetry of the traditional Littlewood-Richardson rule in §3, and translate the procedure that exhibits the symmetry (which is essentially jeu de taquin) into the language of paths. Then in §4 we extend this construction successively to two broader classes of paths, with instances for other types of groups than A_{n}, namely the classes of m-paths (built from the path models of minuscule representations) and of ψ-paths (incorporating also the path models of quasi-minuscule representations); the latter removes any restrictions on the type of the group or the representation. Finally in §5 we give a construction in the context of arbitrary piecewise linear paths that generalises the earlier constructions; however, we have not (yet) established the essential connection with Littelmann’s root operations for this general construction.

§2. Notations used. We shall assume without explicit reference the notations and results of [Litt2]. We mention in particular the following notations. We denote by X the weight lattice of a complex Lie algebra 𝔤, that for simplicity we shall assume to be finite dimensional and reductive, and by Π the set of piecewise linear paths in the space X_{Q} = X ⊗_{Z} Q of rational weights. All paths are parametrised by the interval [0, 1] ⊆ Q, and start at 0, so that π(0) = 0 for all π ∈ Π, while π(1) denotes the end point of π. For μ ∈ X, the straight path from 0 to μ is denoted by π_{μ}. The reverse or dual path of π ∈ Π is denoted by π^{∗}, and π∗π′ denotes the concatenation of two paths. The set of paths π such that π(t) is dominant for all t ∈ [0, 1], and such that π(1) ∈ X (i.e., it is an integral dominant weight), is denoted by P^{+}. The root operators e_{α} and f_{α} formally act on the free Z-module ZΠ, but since the image of every generator π ∈ Π of that Z-module is either another such generator or 0, we shall consider the root operators as maps Π → Π ∪ {0}. The subset of Π reachable from some π ∈ P^{+} by repeated application of root operators is denoted by B_{π}. To avoid too deeply nested subscripts we shall write e_{i} and f_{i} for the root operators e_{α_{i}} and f_{α_{i}}. For a weight λ, a path π and a simple root α, we shall write ⌊λ + π⌋_{α} for the number min_{t∈[0,1]} ⟨λ + π(t), α^{∨}⟩, or simply ⌊π⌋_{α} if λ = 0; the path π is called λ-dominant if ⌊λ + π⌋_{α} ≥ 0 for all simple roots α.

3 Paths in type A_{n−1}, tableaux, and jeu de taquin

§3. Paths in type A_{n−1}, tableaux, and jeu de taquin. We shall first consider the correspondence between paths in type A_{n−1} and Young tableaux, and the connection between the Littlewood-Richardson rule in terms of paths and the classical one. Then we shall consider the question of symmetry of these rules with respect to the order of the tensorands.

3.1. Paths and Littlewood-Richardson tableaux. Let us first recall the well known correspondence between partitions with at most n parts and dominant integral weights for 𝔤 = 𝔤𝔩_{n}. Let 𝔥 ⊆ 𝔤𝔩_{n} be the Cartan subalgebra consisting of diagonal matrices, and 𝔟 ⊆ 𝔤𝔩_{n} the Borel subalgebgra of upper triangular matrices. For i = 1, …, n let ε_{i} ∈ 𝔥^{∗} be the weight that takes the (i, i) diagonal entry; then the set of simple roots with respect to 𝔟 is { α_{i} | i = 1, …, n − 1 } where α_{i} = ε_{i} − ε_{i+1}, and the set of fundamental weights is { ω_{i} | i = 1, …, n − 1 } where ω_{i} = ∑_{j≤i} ε_{j}. We shall identify any vector λ = (λ_{1}, …, λ_{n}) ∈ Z^{n} with the weight ∑_{i=1}^{n} λ_{i}ε_{i}; since one has ⟨λ, α_{i}^{∨}⟩ = λ_{i} − λ_{i+1}, it follows that this is a dominant integral weight if and only if λ is a partition.

Now we shall define a correspondence between the set Tab_{μ} of semistandard Young tableaux of shape μ, and the set B_{π} for a specific path π = π_{c}(μ) ∈ P^{+}, which is determined as follows. Write μ as a sum of terms ω_{i} (so the term ω_{i} is repeated μ_{i} − μ_{i+1} times) ordered by (weakly) increasing index i, and then replace each ω_{i} by its expression ∑_{j≤i} ε_{j} as a sum of terms ε_{j}, again ordered by increasing index. The path π_{c}(μ) is obtained from the resulting sum by replacing each of the |μ| terms of the form ε_{j} by the corresponding path π_{ε_{j}}, and addition by concatenation. We shall call any path of the form π_{ε_{j_{1}}} ∗ ⋯ ∗ π_{ε_{j_{l}}} an ε-path of length l; such paths are characterised by the sequence j_{1}, …, j_{l} of indices. If f_{i} is applied to an ε-path and the result is not 0, then it changes one segment π_{ε_{i}} into π_{ε_{i+1}}. Therefore any path in B_{π_{c}(μ)} is an ε-path of length |μ|. Inserting its sequence of indices into a Young diagram of shape μ, proceeding by columns from right to left and from top to bottom within each column, one obtains a tableau, and it can be shown that this defines a bijection from B_{π_{c}(μ)} to Tab_{μ}. Note that a subsequence of segments contributing to any one column of length i of the tableau stems from the sequence of segments π_{ε_{j}} corresponding (before application of the f_{α}) to one term ω_{i} in the sum for μ. Remark. In fact one could have used instead of π_{c}(μ) another path π̄_{c}(μ), formed by concatenating straight line paths π_{ω_{i}} corresponding to the terms ω_{i} in the first sum for μ. One then obtains a bijection between B_{π̄_{c}(μ)} and the same set Tab_{μ} of tableaux: every application of f_{α} that does not yield 0 transforms one path segment into another straight segment, of the form π_{ε_{I}} with I an i-element subset of {1, …, n} and ε_{I} = ∑_{j∈I} ε_{j}; that segment corresponds to a column with set of entries I in the Young tableau. Remarkably, Tab_{μ} can even be used to describe in a direct way many other sets B_{π′}, where π′ ∈ P^{+} is an ε-path. For instance, if π_{r}(μ) denotes the ε-path corresponding 3.1 Paths and Littlewood-Richardson tableaux

to the expression μ = ∑_{i=1}^{n} μ_{i}ε_{i} (i.e., with weakly increasing indices), then each path in B_{π_{r}(μ)} is an ε-path whose sequence of indices is obtained by listing the entries of a tableau in Tab_{μ} by rows from right to left. We have given prominence to π_{c}(μ) rather than to π_{r}(μ) because it seems to be the preferred choice for mathematical reasons: the proof that B_{π} corresponds to Tab_{μ} is the easiest for π = π_{c}(μ), and the relation between B_{π_{c}(μ)} and a set of tableaux has analogues in other classical types (see [KaNa]), which is not the case with B_{π_{r}(μ)}. Historically however it is (the set of sequences of indices corresponding to) B_{π_{r}(μ)} that has received more attention: for instance, the fact that the operators e_{α} preserve compatibility with the tableau conditions is already assumed implicitly in [Rob], and proved in [Macd, I (9.6)]. Note also that our choice is not of crucial importance: while the relation between paths and tableaux was instrumental in finding the construction presented below, that construction itself will be formulated in terms of paths, and applicable regardless of any connection of those paths with tableaux.

By the decomposition formula of [Litt2], the multiplicity of the irreducible 𝔤𝔩_{n}-module V_{ν} in the tensor product V_{λ} ⊗ V_{μ} equals the number of λ-dominant paths in B_{π_{c}(μ)} of weight ν − λ, i.e., paths π ∈ B_{π_{c}(μ)} for which the translated path λ + π goes from λ to ν and lies entirely within the dominant chamber. Each segment of λ+π goes from one dominant integral weight to another, so we obtain a sequence of partitions from λ to ν that we shall call the λ-chain of π. If π was derived, as shown above, from T ∈ Tab_{μ}, then its λ-chain can be formed, starting from λ, by traversing T in the order indicated, and for every entry i encountered forming a new partition by adding 1 to part i of the previous partition. If we extend this procedure slightly by filling at each step the square (in row i) added to the Young diagram of the partition with a particular number r, then this will associate to T a Littlewood-Richardson tableaux T′ of shape ν/λ and weight μ (as used in the classical formulation of the Littlewood-Richardson rule). It suffices to specify r: it is the row number in T of the entry i encountered at the current step.

In fact this procedure defines a correspondence between the squares s of T and the squares t of T′, i.e., a bijection between the squares of the Young diagram of μ and those of the skew diagram ν/λ. This bijection is such that in T the square s contains the row number the corresponding square t, while in T′ the square t contains the row number of s. It follws that T can be reconstructed from T′ by a quite similar procedure. In fact one may consider both T and T′ merely as ways to represent the bijection between squares. The bijections so occurring can be characterised by geometric properties that are contained in the notion of pictures ([Zel1]); using this notion it becomes obvious that for T′ one finds exactly the set of Littlewood-Richardson tableaux of shape ν/λ and weight μ. Pictures provide a very versatile means to study these tableaux, due to the fact that many operations can be defined directly in terms of pictures, see [vLee2] (in that paper the conditions in the definition

3.2 Symmetry of the Littlewood-Richardson rule

of pictures are transposed; in citing results we shall adapt for this difference). Below we shall freely use constructions defined for pictures and their properties; for the convenience of those not acquainted with pictures, we shall also give the translations of those constructions in terms of tableaux. It is worth noting that if one takes T to represent a path π′ ∈ B_{π_{r}(μ)} rather than π ∈ B_{π_{c}(μ)}, then one not only obtains the same set of admissible T (i.e., π is λ-dominant if and only if π′ is), but for each such T the two orders of traversal lead to the same picture (bijection between squares of μ and of ν/λ), and therefore construct the same Littlewood-Richardson tableau T′. The path π′ moreover has the property that its λ-chain gives the standardisation of the semistandard tableau T′, which is not the case with π.

3.2. Symmetry of the Littlewood-Richardson rule. We now turn to the question of exhibiting the symmetry of the tensor product combinatorially in type A_{n−1}, using Littlewood-Richardson tableaux.

We are looking for a bijection between Littlewood-Richardson tableaux of shape ν/λ and weight μ on one side, and Littlewood-Richardson tableaux of shape ν/μ and weight λ on the other side. In terms of pictures such a bijection is fairly easy to construct. There is a unique picture λ → −λ, which may be “glued” to any given picture f: ν/λ → μ, to form a picture f̄: ν → μ ⊎ −λ (the operation ‘⊎’ is “concatenation” of skew diagrams in the anti-diagonal direction, or more precisely of classes of skew diagrams modulo translation in the plane). Then one can apply the Schützenberger algorithm for pictures to obtain a picture S(f̄): ν → λ ⊎ −μ; the image under the inverse picture S(f̄)^{−1} of the factor −μ of the image is necessarily the subdiagram μ of ν, so by restriction of S(f̄) to the complement of this subdiagram we obtain the desired picture ν/μ → λ. The construction is easily seen to be involutive, and hence it defines a bijection between the sets of pictures Pic(ν/λ, μ) and Pic(ν/μ, λ).

In terms of Littlewood-Richardson tableaux such as T′, this construction amounts to the following. The skew tableau of shape ν/λ is extended to a tableau of shape ν by filling each square of λ with minus its distance to the bottom of its column in λ (so the lowest square in each column gets −1, the square above it −2, etc.); the important property of this subtableau of shape λ is that it corresponds under the Schützenberger involution to the “canonical” tableau of shape and weight λ, in which each row i is filled with entries i. One then applies the Schützenberger involution to the full semistandard tableau of shape ν to obtain another such tableau in which the multiset of entries is negated, so that for each of the negative entries in the original tableau (within the Young diagram of λ) one now has a positive entry (at some other place of course), and vice versa; the subtableau of positive entries of the new tableau is a Littlewood-Richardson tableau of shape ν/μ and weight λ.

This algorithm can be simplified, if one recalls that one way to compute the Schützenberger involution applied to a Young tableau Y, is by “inflation”.

3.3 Jeu de taquin for chains of partitions, and for paths

This is done by traversing the entries i of Y in increasing order (as usual processing equal entries from left to right), using them to repeatedly modify a tableau Z, initially empty, as follows: one performs an outward jeu de taquin slide of Z into the square occupied by i in Y, after which the vacated top-left corner of Z is filled with the value −i. Applying this algorithm to the semistandard Young tableau extended from T′, one sees that in a first stage of computation the Schützenberger involution is applied to the subtableau of shape λ; as remarked, the result is the canonical tableau of shape λ. In a second stage outward slides are then applied to this tableau according to T′; the (negative) entries added at the top-left during the second stage can be ignored, since they will be removed from the final result anyway. So the bijection expressing the symmetry of the Littlewood-Richardson rule with respect to the partitions λ and μ describing the tensorands is given by jeu de taquin, rather than by the full Schützenberger algorithm; it is described in the following proposition, whose proof is contained in the reasoning above.

3.2.1. Proposition. A bijection between Littlewood-Richardson tableaux L of shape ν/λ and weight μ and Littlewood-Richardson tableaux M of shape ν/μ and weight λ is given by the following algorithm: the tableau M is obtained from the canonical tableau of shape and weight λ by applying a series of successive outward jeu de taquin slides into the squares of ν/λ, as ordered by increasing entries in L, where squares with equal entries are ordered from left to right. Applying the same algorithm to M (interchanging the values of λ and μ) will reconstruct L.

3.3. Jeu de taquin for chains of partitions, and for paths. We shall now translate the construction above back in terms of paths, which will result in a remarkably simple operation that can be generalised to other types than A_{n−1}. In associating paths with tableaux such as L and M in the proposition above, sequences of partitions are natural intermediate objects: on one hand L is used there only to obtain an ordering of the squares within its shape ν/λ, as represented by its standardisation, which corresponds to a saturated increasing chain of partitions from λ to ν; on the other hand such a chain of partitions is the λ-chain of some ε-path.

As was noted above, the λ-chain of a λ-dominant path π ∈ B_{π_{c}(μ)} does not correspond to the standardisation of the corresponding Littlewood-Richardson tableau T′. We can nevertheless interpret the jeu de taquin process as operating directly on paths, in two ways. One is to pragmatically choose to work with λ-dominant paths in B_{π_{r}(μ)} rather than in B_{π_{c}(μ)}; as remarked above, the λ-chain of such a path does correspond to the standardisation the associated Littlewood-Richardson tableau. More fundamentally, one may observe that T′ really represents a picture ν/λ → μ, which has many specialisations (standard tableaux of shape ν/λ that can be associated with it according to some “reading” of μ); one of these is the standardisation of T′, while the λ-chain of π ∈ B_{π_{c}(μ)} corresponds to another. Moreover, different specialisations of the same picture have the property that when used to determine sequences of jeu de taquin slides, the final effect of any of these sequences of slides on the same initial tableau is identical (this is more generally true for tableaux that are dual equivalent). Therefore, if in proposition 3.2.1 we take for L the Littlewood-Richardson tableau constructed from π ∈ B_{π_{c}(μ)}, then the same tableau M will be computed as in the proposition if we apply slides according to the λ-chain of π, rather than according to the specialisation of L.

We arrive at describing jeu de taquin in terms of chains of partitions. It is not necessary that the initial tableau to which we apply outward slides is a Young tableau; therefore we shall admit chains that start in an arbitrary partition κ. Given a saturated increasing chain of partitions from κ to λ (for instance, with κ = (0), the 0-chain of π_{c}(λ)) corresponding to a (semi)standard tableau C, and a similar chain from λ to ν (the λ-chain of a λ-dominant εpath) corresponding to a tableau L, the question is to describe the chain of partitions corresponding to the skew tableau M resulting from the application of successive outward jeu de taquin slides to C into the squares added in the chain of L. This has been done in [vLee1, §2] (for the Schützenberger algorithm, but it applies also to jeu de taquin), see also [vLee4, §2.1]. The family of partitions λ^{[i,j]}, defined by the fact that λ^{[i,0]}, …, λ^{[i,l]} is the chain corresponding to the tableau obtained after applying i slides to C, satisfies a local condition that allows λ^{[i+1,j]} to be determined when λ^{[i,j]}, λ^{[i,j+1]}, and λ^{[i+1,j+1]} are given:

3.3.1. Rule. One has λ^{[i,j+1]} = λ^{[i+1,j]} if and only if the two squares of λ^{[i+1,j+1]} \ λ^{[i,j]} are adjacent.

Note that in the case that the mentioned squares are non-adjacent, λ^{[i+1,j]} is the unique partition strictly between λ^{[i,j]} and λ^{[i+1,j+1]} that differs from λ^{[i,j+1]}. This rule allows all partitions λ^{[i,j]} to be computed when they are initially given only for pairs (i, j) with i = 0 (by means of C) or j = l (by means of L). The same rule also allows λ^{[i,j+1]} to be determined when λ^{[i,j]}, λ^{[i+1,j]}, and λ^{[i+1,j+1]} are given. This reaffirms that the construction of proposition 3.2.1 is its own inverse. Note that in the proposition we take C to be the canonical tableau of shape λ; this is possible since we know that M must be a Littlewood-Richardson tableau, and therefore be reducible by jeu de taquin to this canonical tableau. In order to define a similar construction in terms of paths however, it will be necessary to explicitly supply data corresponding to C: if we want to construct from a λ-dominant path p ∈ B_{π} a corresponding μ-dominant path p′ (where μ = π(1)), then we must specify the path π′ ∈ P^{+} such that μ ∈ B_{π′}; similiarly the inverse operation requires π to be specified. Therefore the path analogue of the bijection of proposition 3.2.1 will be a bijective correspondence (p, π′) ↔ (p′, π).

We shall now reformulate the rule above in terms of ε-paths. With respect to chains of partitions there are some minor differences. First of all, partitions are limited to those with at most n parts. Second, we are interested primarily in the vertical and horizontal difference vectors v_{i,j} = λ^{[i+1,j]} − λ^{[i,j]} and h_{i,j} = λ^{[i,j+1]} − λ^{[i,j]}, which lie in the set {ε_{1}, …, ε_{n}}, and represent segments of ε-paths; indeed, they are equal to ε_{r} where r is the row number of the square λ^{[i+1,j]} \ λ^{[i,j]} respectively of the square λ^{[i,j+1]} \ λ^{[i,j]}. Now in case the two squares mentioned in rule 3.3.1 are non-adjacent, the square λ^{[i+1,j]} \ λ^{[i,j]} is equal to λ^{[i+1,j+1]} \ λ^{[i,j+1]}, and similarly the square λ^{[i,j+1]} \ λ^{[i,j]} is equal to λ^{[i+1,j+1]} \ λ^{[i+1,j]}; in this case we therefore certainly have v_{i,j} = v_{i,j+1} and (equivalently) h_{i+1,j} = h_{i,j}. These two equalities remain valid in case the squares mentioned in rule 3.3.1 are horizontally adjacent, i.e., they both lie in the same row r, since in that case v_{i,j} = v_{i,j+1} = h_{i+1,j} = h_{i,j} = ε_{r}. Therefore, the only case where v_{i,j} ≠ v_{i,j+1}, and where h_{i+1,j} ≠ h_{i,j}, is when the two squares of λ^{[i+1,j+1]} \ λ^{[i,j]} are vertically adjacent; in that case, if the rows containing these squares are r and r + 1, one has h_{i,j} = ε_{r} = v_{i,j} and v_{i,j+1} = ε_{r+1} = h_{i+1,j}. Given these values of h_{i,j} and v_{i,j+1} (or of v_{i,j} and h_{i+1,j}), the condition that there is indeed vertical adjacency can be expressed as λ_{r}^{[i,j]} = λ_{r+1}^{[i,j]}, or equivalently as ⟨λ^{[i,j]}, α_{r}^{∨}⟩ = 0. Note that with this condition satisfied it would not even be possible to have v_{i,j} = v_{i,j+1}, since that would make ⟨λ^{[i,j+1]}, α_{r}^{∨}⟩ = −1, contradicting the fact that λ^{[i,j+1]} is a partition, and corresponds to a dominant weight. We arrive at the following rule that describes how v_{i,j} and h_{i+1,j} are determined by the values of h_{i,j}, v_{i,j+1} and λ^{[i,j]}.

3.3.2. Rule. One has v_{i,j} = v_{i,j+1} and h_{i+1,j} = h_{i,j}, unless for some r one has h_{i,j} = ε_{r}, v_{i,j+1} = ε_{r+1}, and ⟨λ^{[i,j]}, α_{r}^{∨}⟩ = 0, in which case v_{i,j} = ε_{r} and h_{i+1,j} = ε_{r+1}.

We can now reformulate jeu de taquin in terms of ε-paths. A strict translation of proposition 3.2.1 into this language would give a statement that only applies to ε-paths that correspond to semistandard Young tableaux, but as explained above we remove that restriction by supplying an extra parameter π′. To recover that proposition one should take κ = (0), and π′ equal to the ε-path corresponding to the canonical tableau of shape λ, i.e., to π_{c}(λ) or π_{r}(λ), depending on the chosen correspondence between paths and tableaux.

3.3.3. Construction (jeu de taquin for ε-paths). Let κ, λ, ν be dominant integral weights for 𝔤𝔩_{n}, π′ a κ-dominant ε-path of length l with π′(1) = λ − κ, and p a λ-dominant ε-path of length k with p(1) = ν − λ. We construct a dominant integral weight μ, a κ-dominant ε-path π of length k with π(1) = μ − κ, and a μ-dominant ε-path p′ of length l with p′(1) = ν − μ in the following steps.

∘ Set h_{0,0}, …, h_{0,l−1} according to the sequence of segments of π′, and

v_{0,l}, …, v_{k−1,l} according to the sequence of segments of p; ∘ Set λ^{[0,j]} := κ + ∑_{j′<j} h_{0,j′} for 0 ≤ j ≤ l, and λ^{[i,l]} := λ + ∑_{i′<i} v_{i′,l} for

0 ≤ i ≤ k; ∘ Determine the values h_{i,j} for 0 < i ≤ k and l > j ≥ 0, as well as v_{i,j} for

0 ≤ i < k and l > j ≥ 0 using rule 3.3.2, setting λ^{[i,j+1]} := λ^{[i,j]} + v_{i,j} = λ^{[i+1,j+1]} − h_{i+1,j} after each application of the rule;

∘ Return π = π_{v_{0,0}} ∗ ⋯ ∗ π_{v_{k−1,0}} and p′ = π_{h_{k,0}} ∗ ⋯ ∗ π_{h_{k,l−1}}.

Note that the relations between the parameters of the construction allow all of them to be deduced if κ, π′, and p are given; we shall therefore consider the construction to be parametrised by (κ, π′, p), and to return the pair (π, p′). The following theorem is obvious, both from the symmetry of the construction, and from the fact that that construction is just a reformulation of jeu de taquin.

3.3.4. Theorem (symmetry of jeu de taquin for ε-paths). The construction 3.3.3 is its own inverse: if when applied to (κ, π′, p) it returns (π, p′), then applied to (κ, π, p′) it will return (π′, p). Moreover, it is symmetric with respect to dualisation of paths: when applied to (ν, p^{∗}, π^{′∗}) it will return (p^{′∗}, π^{∗}).

Despite its somewhat technical formulation, the following lemma is just an expression of the trivial fact that jeu de taquin consists of consecutive application of slides: performing inward slides according to a path π′_{2} followed by performing inward slides according to π′_{1} amounts to performing inward slides according to the concatenation π′_{1} ∗ π′_{2}.

3.3.5. Lemma. Let construction 3.3.3 be applicable to (κ, π′, p). If π′ is of the form π′_{1} ∗ π′_{2}, then the construction is applicable to (κ + π′_{1}(1), π′_{2}, p), and calling the result of this application (q, p′_{2}), it is also applicable to (κ, π′_{1}, q); calling the result of this second application (π, p′_{1}), the result of applying the construction to (κ, π′, p) will be (π, p′_{1} ∗ p′_{2}). A similar composition formula holds if p is of the form p_{1} ∗ p_{2}.

The following theorem establishes the fundamental link between jeu de taquin and Littelmans’s root operators e_{α} and f_{α}. It is not an entirely new result: the fact that the definition of e_{α} and f_{α} corresponds to jeu de taquin on tableaux of two rows is well known to experts; a discussion of this relation including a proof of a statement equivalent to the theorem can be found in in [vLee4, §3.1]. We shall give another proof here that is formulated in terms of paths, so that generalisation to other types will be straightforward.

3.3.6. Theorem. In the situation of construction 3.3.3 the path π can be obtained from p by application of a sequence of operators e_{i}, and similarly the path p′ can be obtained from π′ by application of a sequence of operators f_{i}. In particular, if κ = 0, one has p ∈ B_{π} and p′ ∈ B_{π′}.

Proof. By symmetry (theorem 3.3.4) it suffices to prove the first statement (about p and π). By lemma 3.3.5, it will suffice to prove the case where π′ has length 1, which we therefore assume henceforth. In order to proceed by induction on the length of p, it is necessary to strengthen the statement being proved as follows: there exists a sequence of indices i_{1}, …, i_{n} (with n ≥ 0), and a sequence of paths p = p_{n}, p_{n−1}, …, p_{0} = π, such that for j = n, …, 1, one has p_{j−1} = e_{i_{j}}(p_{j}) and ⌊κ + p_{j}⌋_{α_{i_{j}}} = −1 (which shows that p_{j} is not κ-dominant for j > 0). If p is of length 0 we take n = 0 and there is nothing to prove; assume therefore that p has positive length. Let v = λ^{[1,1]} − λ^{[0,1]} in construction 3.3.3, so that we can write p = π_{v} ∗ q; similarly put v′ = λ^{[1,0]} − λ^{[0,0]} and π = π_{v′} ∗ ρ. With κ′ = λ^{[1,0]} we consider the construction applied to (κ′, π_{h_{1,0}}, q), which by lemma 3.3.5 returns (ρ, p′). By the induction hypothesis there exist indices i_{1}, …, i_{m} and paths q = q_{m}, …, q_{0} = ρ with q_{j−1} = e_{i_{j}}(q_{j}) and ⌊κ′ + q_{j}⌋_{α_{i_{j}}} = −1 for 0 < j ≤ m. For j ≤ m we put p_{j} = π_{v′} ∗ q_{j} (so that in particular p_{0} = π). Then for 0 < j ≤ m one has ⌊κ + p_{j}⌋_{α_{i_{j}}} = ⌊κ′ + q_{j}⌋_{α_{i_{j}}} = −1, since the path π_{v′} is κ-dominant with π_{v′}(1) = v′ = κ′ − κ. We see moreover that the minimum taken in the first expression is attained only in the second part of the concatentation p_{j} = π_{v′} ∗ q_{j}; from the definition of e_{i} we therefore have e_{i}(p_{j}) = π_{v′} ∗ e_{j}(q_{j}) = π_{v′} ∗ q_{j−1} = p_{j−1}. Now if v′ = v, we have p = π_{v} ∗ q = π_{v′} ∗ q_{m} = p_{m} so that we take n = m and we are done. Otherwise we are in the exceptional case of rule 3.3.2 for (i, j) = (0, 0), so that π′ = π_{v′} = π_{ε_{r}}, π_{v} = π_{ε_{r+1}}, and ⟨κ, α_{r}^{∨}⟩ = ⟨λ^{[1,1]}, α_{r}^{∨}⟩ = 0 for some r. Since the path q is λ^{[1,1]}-dominant, this implies ⟨q(t), α_{r}^{∨}⟩ ≥ 0 for all t, so that ⌊κ + p⌋_{α_{r}} = −1, which minimum is first attained at the point of concatenation of p = π_{v} ∗ q; consequently, we have by the definition of e_{r} that e_{r}(p) = π_{ε_{r}} ∗ q = π_{v′} ∗ q_{m} = p_{m}. In this case we therefore put n = m+1 and i_{n} = r, and we have established all that needs to be proved.

4 Jeu de taquin for other types of groups

§4. Jeu de taquin for other types of groups.

Now the stage has been set in type A_{n−1}, we may consider possible generalisations to other types of groups. While the traditional planar form of jeu de taquin does not seem to be easily generalised, the situation is quite different for the formulation in terms of paths, since there are only a few points in the discussion above that are specific for type A_{n−1}, and need replacement for other types. Firstly, one needs a replacement for the set { π_{ε_{i}} | i = 1, …, n } of elementary path segments, and hence for the class of ε-paths; secondly, rule 3.3.2 will need to be adapted to this new class of paths. Once this is done, a counterpart of the construction 3.3.3 can be defined with only the most obvious adaptations. Provided the replacement for rule 3.3.2 preserves its symmetry, the analogue of theorem 3.3.4 will be valid, with an equally simple proof; the analogue of lemma 3.3.5 remains a triviality. Having succeeded so far, we shall have a involutive construction that operates on pairs (p, π′) of paths; then in order that we can use this construction to define, for any paths π, π′ ∈ P^{+} (in the chosen class) with π(1) = μ and π′(1) = λ, a bijective correspondence between λ-dominant paths in B_{π} and μ-dominant paths in B_{π′}, it is essential that the analogue of theorem 3.3.6 holds. Most of its proof will remain valid without modification, but the final argument involving a single configuration governed by (an analogue of) rule 3.3.2 needs to be verified. Each time we establish these points, we obtain a combinatorial analogue of jeu de taquin that shares two of its most fundamental properties: symmetry (theorem 3.3.4) and confluence, i.e., the fact that, for κ = 0, the correspondence p → π is independent of the choice of π′ ∈ P^{+} (this will be a consequence of the analogue of theorem 3.3.6 and the fact that from any path p at most one path π ∈ P^{+} can be obtained by applications of root operators e_{α}). The combinatorial constructions that we shall find have a common generalisation to arbitrary piecewise linear paths, and maybe even to continuous paths; however, in this generality the combinatorial nature of the construction will be lost.

4.1. Minuscule representations and m-paths.

4.1 Minuscule representations and m-paths

Let W be the Weyl group of 𝔤. A non-trivial irreducible representation of 𝔤 is called minuscule if its set of weights forms a single W -orbit; these weights are called minuscule weights. The following representations are minuscule: all fundamental representations in type A_{n}, the natural (defining) representation in types C_{n} and D_{n}, the spin representation in type B_{n}, the half-spin representations in type D_{n}, the two 27-dimensional representations in type E_{6}, and the 56-dimensional representation in type E_{7}; there are no minuscule representations in types G_{2}, F_{4} and E_{8}, since, as the weight lattice coincides with the root lattice in these types, all representations contain the weight 0. For any minuscule weight m and any root α one has ⟨m, α^{∨}⟩ ∈ {−1, 0, 1}, since otherwise m + Zα would intersect the weight system in more than two points. Therefore one has B_{π_{λ}} = { π_{m} | m ∈ W λ } for any dominant minuscule weight λ. This makes the class of paths obtained by concatenation of segments π_{m} for m minuscule a good candidate to replace the class of εpaths. We shall call any concatenation of l segments of the form π_{m}, with m minuscule, an m-path (pun not intended) of length l.

In order to formulate an analogue of rule 3.3.2 for m-paths, we are led to consider the following situation. Let κ, λ and μ be dominant integral weights such that π_{λ−κ} and π_{ν−λ} are m-paths of length 1; the question is to find a dominant weight μ such that π_{μ−κ} can be obtained from π_{ν−λ} by a series of applications of operators e_{α} with ⟨κ, α^{∨}⟩ = 0, and such that the argument π_{v_{i}} to which the operator is applied satisfies ⟨v_{i}, α^{∨}⟩ = −1 (there is a similar condition for the transformation π_{λ−κ} → π_{ν−μ}, which involves operators f_{α}). The main difference with the situation for ε-paths is that, whereas in that case at most one application of e_{r} suffices (which transforms π_{ν−λ} = π_{ε_{r+1}} into π_{μ−κ} = π_{ε_{r}}), a series of applications may be needed for m-paths. This phenomeneon already occurs in type A_{n−1}: if one takes κ = ν = 0, and λ = ω_{i}, so that λ − κ = ω_{i} = ε_{{1,...,i}}, and ν − λ = −ω_{i} = ε_{{i+1,...,n}}, then the only possibility is to have μ = ω_{n−i}, so that μ − κ = ω_{n−i} = ε_{{1,...,n−i}} and ν − μ = −ω_{n−i} = ε_{{n−i+1,...,n}}; the transformation of π_{ε_{{i+1,...,n}}} into π_{ε_{{1,...,n−i}}} requires a total of i(n − i) applications of operators ε_{α} (some operators may be applied more than once, but never twice in succession).

We see in this example that the seqence of operators applied may not be unique (unlike in the proof of theorem 3.3.6), but the final result is. In fact it is not difficult to see that this is true in general. Let S = { i | ⟨κ, α_{i}^{∨}⟩ = ⟨ν, α_{i}^{∨}⟩ = 0 }, and put v_{0} = ν − λ, h_{0} = λ − κ; these are the initial candidates for μ − κ and ν − μ (the sum of these candidates will always be ν − κ). In order that μ be dominant, it is necessary that ⟨μ − κ, α_{i}^{∨}⟩ = ⟨μ − ν, α_{i}^{∨}⟩ ≥ 0 for all i ∈ S. Therefore, while there exists for the current candidates v_{j} and h_{j} for μ − κ and ν − μ an i ∈ S with ⟨v_{j}, α_{i}^{∨}⟩ = ⟨−h_{j}, α_{i}^{∨}⟩ = −1 we choose such an i and replace the candidates by v_{j+1} = s_{α_{i}}(v_{j}) = v_{j} + α_{i} and h_{j+1} = s_{α_{i}}(h_{j}) = h_{j} − α_{i}. After a finite number of steps this process terminates, and we set μ = κ + v_{l} = ν − h_{l} for the final values v_{l}, h_{l}. Writing W_{κ,ν} for the subgroup of W stabilising κ and ν (it is generated by { s_{α_{i}} | i ∈ S }), and dom_{W_{κ,ν}} for the map that sends any weight to the W_{κ,ν}-dominant representative of its W_{κ,ν}-orbit, we clearly have μ − κ = dom_{W_{κ,ν}} (ν − λ) and μ − ν = dom_{W_{κ,ν}} (κ − λ), which shows that these values are independent of the choices made of the indices i. We have achieved ⟨μ, α_{i}^{∨}⟩ ≥ 0 for all i ∈ S; to prove that μ is dominant it suffices to establish the same for i ∉ S. For such i we have ⟨κ, α_{i}^{∨}⟩ ≥ 1 or ⟨ν, α_{i}^{∨}⟩ ≥ 1 (possible both); since ⟨μ − κ, α_{i}^{∨}⟩ and ⟨ν − μ, α_{i}^{∨}⟩ lie in {−1, 0, 1}, either of these inequalities implies ⟨μ, α_{i}^{∨}⟩ ≥ 0. From this description we see that in fact μ = dom_{W} (κ + ν − λ). We can therefore formulate a generalisation of rule 3.3.2 simply as follows.

4.1.1. Rule. λ^{[i+1,j]} = dom_{W} (λ^{[i,j]} + λ^{[i+1,j+1]} − λ^{[i,j+1]}).

4.1.2. Lemma. For fixed values of λ^{[i,j]} and λ^{[i+1,j+1]}, the correspondence between λ^{[i,j+1]} and λ^{[i+1,j]} determined by rule 4.1.1 is symmetrical. Moreover the rule is symmetrical in λ^{[i,j]} and λ^{[i+1,j+1]}.

Proof. From the considerations above it follows that μ = w(κ + ν − λ) for some w ∈ W that fixes κ and ν; this implies λ = w^{−1}(κ + ν − μ), and since λ is dominant, this establishes the first symmetry. The second symmetry is obvious.

As the path segments h_{i,j} and v_{i,j} are absent from the formulation of the rule 4.1.1, we can formulate a construction that is in the spirit of the original formulation of jeu de taquin in term of chains of partitions, in that only a doubly indexed family of partitions is considered. It should be noted however that paths were used to find rule 4.1.1, and they will play a rôle in proofs concerning the construction as well.

4.1.3. Construction (jeu de taquin for m-paths). Let κ, λ, ν be dominant integral weights for 𝔤, π′ a κ-dominant m-path of length l with π′(1) = λ − κ, and p a λ-dominant m-path of length k with p(1) = ν − λ; we assume for each of π′ and p that their segments are traversed at equal speeds. We construct a dominant integral weight μ, a κ-dominant m-path π of length k with π(1) = μ − κ, and a μ-dominant m-path p′ of length l with p′(1) = ν − μ in the following steps.

∘ Set λ^{[0,j]} := κ + π′(j/l) for 0 ≤ j ≤ l, and λ^{[i,l]} := λ + p(i/k) for

0 ≤ i ≤ k; ∘ Determine the values λ^{[i,j]} for 0 < i ≤ k and l > j ≥ 0 using rule 4.1.1; ∘ Return π = π_{v_{1}} ∗⋯∗π_{v_{k}} and p′ = π_{h_{1}} ∗⋯∗π_{h_{l}}, where v_{i} = λ^{[i,0]}−λ^{[i−1,0]}

and h_{j} = λ^{[k,j]} − λ^{[k,j−1]}.

4.1.4. Theorem (symmetry of jeu de taquin for m-paths). The construction 4.1.3 is its own inverse: if when applied to (κ, π′, p) it returns (π, p′), then applied to (κ, π, p′) it will return (π′, p). Moreover, it is symmetric with respect to dualisation of paths: when applied to (ν, p^{∗}, π^{′∗}) it will return (p^{′∗}, π^{∗}).

Proof. This is immediate from lemma 4.1.2.

4.1.5. Lemma. Lemma 3.3.5 remains valid when construction 3.3.3 is replaced by construction 4.1.3.

4.1.6. Theorem. In the situation of construction 4.1.3 the path π can be obtained from p by application of a sequence of operators e_{i}, and similarly the path p′ can be obtained from π′ by application of a sequence of operators f_{i}. In particular, if κ = 0, one has p ∈ B_{π} and p′ ∈ B_{π′}.

4.2 Quasi-minuscule weights and ψ-paths

Proof. The proof of theorem 3.3.6 can be followed literally, with the obvious replacement of references by their counterparts for m-paths, up to and including the proof that e_{i}(p_{j}) = p_{j−1} for 0 < j ≤ m; after that we continue as follows. Let v = v_{0}, …, v_{l} = v′ be the sequence of vectors in the discussion preceding the statement of rule 4.1.1; put n = m + l and p_{n−i} = π_{v_{i}} ∗ q for i = 0, …, l (this agrees with the previous definition of p_{m}, and we have p_{n} = p). It was established there that for all i < l there exists a simple root α such that ⟨κ, α^{∨}⟩ = ⟨λ^{[1,1]}, α^{∨}⟩ = 0, ⟨v_{i}, α^{∨}⟩ = −1, and v_{i+1} = s_{α}(v_{i}), so that π_{v_{i+1}} = e_{α}(π_{v_{i}}). Since the path q is λ^{[1,1]}-dominant we have ⟨q(t), α^{∨}⟩ ≥ 0 for all t, so that ⌊κ + p_{n−i}⌋_{α} = −1, and e_{α}(p_{n−i}) = e_{α}(π_{v_{i}} ∗q) = π_{v_{i+1}} ∗q = p_{n−i−1}; this establishes all that needs to be proved.

4.2. Quasi-minuscule weights and ψ-paths. We can extend the class of paths for which our construction works beyond that of m-paths by allowing path segments that correspond to the weights of representations slightly larger than the minuscule ones, which will in particular allow us to treat paths for groups of the types G_{2}, F_{4}, and E_{8} that do not possess minuscule representations. As we shall see, the extra freedom will lead to a considerable increase in the number of situations that need to be treated.

An irreducible representation is called quasi-minuscule if its set of weights consists of two W -orbits, one of which is {0}; the weights in the other orbit are called quasi-minuscule weights. The orbit of quasi-minuscule weights is contained in the root lattice, and its dominant representative is a minimal non-zero element of the intersection of the dominant chamber with the root lattice; in particular quasi-minuscule weights are roots. One checks easily that for every simple type there is a unique quasi-minuscule representation: this is the adjoint representation for the simply laced types A_{n}, D_{n} and E_{n}, and the representation whose non-zero weights are the short roots for the other types B_{n}, C_{n}, F_{4}, and G_{2} (for type B_{n} this is the natural representation). For similar reasons as mentioned for minuscule weights, one has for any root α and any quasi-minuscule weight m ∉ {−α, α} that ⟨m, α^{∨}⟩ ∈ {−1, 0, 1}. It follows that if λ is a dominant quasi-minuscule weight, then the only paths in B_{π_{λ}} that are not of the form π_{m} for m ∈ W λ are those of the form e_{α}(π_{−α}) = f_{α}(π_{α}) = π_{−α/2} ∗π_{α/2} for the simple roots α occurring in W λ; we shall denote such a path by ψ_{α}. We define a ψ-path of length l to be a concatenation of l segments that occur in the union of the sets B_{π_{λ}} for the dominant weights λ that are either minuscule or quasi-minuscule.

Now we consider the question of extending rule 4.1.1 to deal with any pair of ψ-paths of length 1. As before we consider dominant integral weights κ, λ, ν, and we put S = { i | ⟨κ, α_{i}^{∨}⟩ = ⟨ν, α_{i}^{∨}⟩ = 0 }. Since the paths involved are no longer necessarily linear, it does not suffice to consider just the differences λ − κ and ν − λ; therefore let p and q be ψ-paths of length 1 such that p(1) = ν − λ and q(1) = λ − κ. Our goal is to find paths p′ and q′, obtained from p and q respectively by applications of operators e_{α} and f_{α}, such that μ = κ+p′(1) = ν −q′(1) is dominant, and moreover p′ is κ-dominant and q′ is μ-dominant (this is an extra condition only when p′ or q′ is of the form ψ_{α}).

We consider first the case that both p and q are linear (i.e., not of the form ψ_{α}), which includes the case of m-paths treated above. Like in that case we perform an iteration, but now on a pair of paths, which we initialise by p_{0} = p, q_{0} = q. The iteration is the following one: (∗) As long as there exists for the current pair p_{j}, q_{j} some i ∈ S with

⟨p_{j}(1), α_{i}^{∨}⟩ = ⟨−q_{j}(1), α_{i}^{∨}⟩ = −1, we choose such an i and put p_{j+1} =

e_{α_{i}}(p_{j}) and q_{j+1} = f_{α_{i}}(q_{j}).

All the paths so obtained are linear, since we could only have p_{j+1} = ψ_{α} if α_{i} = α and p_{j} = π_{−α}, which would violate ⟨p_{j}(1), α_{i}^{∨}⟩ = −1. It follows also that this iteration cannot make a transition from negative to positive roots: if any p_{j} is of the form π_{β} for a negative root β, then the same is true for all p_{j}’s; a similar statement holds when p_{j} = π_{β} for a positive root β, and also for the q_{j}’s in place of the p_{j}’s.

If for the final paths p_{k}, q_{k} obtained after the iteration, the weight μ̃ = λ + p_{k}(1) = ν − q_{k}(1) is dominant, then we put p′ = p_{k} and q′ = q_{k}. Otherwise, let i be such that ⟨μ̃, α_{i}^{∨}⟩ < 0. Suppose first that i ∉ S; then since either ⟨κ, α_{i}^{∨}⟩ > 0 or ⟨λ, α_{i}^{∨}⟩ > 0, we must have p_{k} = π_{−α_{i}} or q_{k} = π_{α_{i}} (possibly both). We put p′ = p_{k+1} = e_{α_{i}}(p_{k}) and q′ = q_{k+1} = f_{α_{i}}(q_{k}); since μ = λ + p′(1) = ν − q′(1) is equal to κ or ν, it is dominant, and one has ⟨μ, α_{i}^{∨}⟩ = 1, from which it follows that p′ is κ-dominant and q′ is μ-dominant. Now suppose i ∈ S; since the iteration (∗) has terminated, it must be that ⟨p_{k}(1), α_{i}^{∨}⟩ = −2, so p_{k} = π_{−α_{i}} and q_{k} = π_{α_{i}}. We then put p_{k+1} = q_{k+1} = ψ_{α_{i}} and p_{k+2} = π_{α}, q_{k+2} = π_{−α} (so that p_{j+1} = e_{α_{i}}(p_{j}) and q_{j+1} = f_{α_{i}}(q_{j}) for j = k, k + 1), after which we resume the iteration (∗), and set p′ and q′ respectively to the final paths p_{l}, q_{l} so obtained. From the fact that the iteration cannot make a transition between negative and positive roots it follows that this time μ = λ + p′(1) = ν − q′(1) must be dominant.

Next we consider the case that p = ψ_{α} and q = ψ_{β} for simple roots α, β. If α ≠ β or if α = β and ⟨λ, α^{∨}⟩ > 1 then we put p′ = p and q′ = q, so that μ = κ = λ = ν. If α = β and ⟨κ, α^{∨}⟩ = 1 we put p_{1} = e_{α}(p) = π_{α} and q_{1} = f_{α}(q) = π_{−α} and then perform iteration (∗). We set p′ and q′ respectively to the final paths p_{l}, q_{l} obtained; as in the case above we see that μ = λ + p′(1) = ν − q′(1) is dominant.

We are left with the possibility that exactly one of p and q is linear. We shall only treat the case that this is q, as the other case is symmetric (by interchange of κ and ν and dualisation of the paths); let p = ψ_{α}. If ⟨κ, α^{∨}⟩ > 0, then we put p′ = p and q′ = q, so that μ = κ is dominant and p′ is κ-dominant; we assume henceforth that ⟨κ, α^{∨}⟩ = 0. If q = π_{α} then we put p′ = e_{α}(p) = π_{α} and q′ = f_{α}(q) = ψ_{α}. Otherwise we put p_{1} = e_{α}(p) = π_{α} and q_{1} = f_{α}(q), after which perform iteration (∗), calling the final paths obtained p_{k}, q_{k}. As in the case of linear p and q it is possible that for μ̃ = λ + p_{k}(1) = ν − q_{k}(1) there is some i for which ⟨μ̃, α_{i}^{∨}⟩ < 0, but this time only for i ∉ S and q_{k} = π_{α_{i}}, since p_{k} ≠ π_{−α_{i}}. If this is the case we put p′ = p_{k+1} = e_{α_{i}}(p_{k}) and q′ = q_{k+1} = f_{α_{i}}(q_{k}) = ψ_{α_{i}}, and otherwise (μ̃ is dominant) we put p′ = p_{k} and q′ = q_{k}; both cases are just like the corresponding ones for linear p and q.

This concludes the description of the determination of p′ and q′. We shall now try to formulate the result as concisely as possible. To this end we shall use the fact that μ determines either of p′ and q′ if the path in question is linear, i.e., if μ differs from κ respectively from ν; if not, then the path is of the form ψ_{α}, and it suffices to specify in addition to μ the simple root α. We also simplify the formulation by using the fact that if λ equals either κ or ν, then the other one can be expressed as κ + ν − λ. Since like before the rule stated will be used in a larger construction, we give the weights and path segments in the construction as elements of doubly indexed families. We leave it to the reader to verify that the results computed above satisfy the description below.

4.2.1. Rule. Let κ = λ^{[i,j]}, λ = λ^{[i,j+1]}, ν = λ^{[i+1,j+1]}, p = v_{i,j+1}, and q = h_{i,j}; the weight μ = λ^{[i+1,j]} and the paths p′ = v_{i,j} and q′ = h_{i+1,j} are determined according to the following cases.

(a) If p and q are linear, then μ = dom_{W} (κ + ν − λ); in case μ equals κ or ν, the corresponding path is equal to ψ_{α}, where α = μ−dom_{W_{κ,ν}} (κ+ν−λ).

(b) If ⟨λ, α^{∨}⟩ = 1 and ψ_{α} ∈ {p, q} for some simple root α, and either p = q or ⟨κ + ν − λ, α^{∨}⟩ = 0, then μ = dom_{W} (κ+ν −λ+α); in case μ equals κ or ν, the corresponding path is equal to ψ_{α′}, where α′ = μ−dom_{W_{κ,ν}} (κ+ ν − λ + α).

(c) If ψ_{α} ∈ {p, q} for some simple root α, with ⟨λ, α^{∨}⟩ = 2 and ⟨κ + ν − λ, α^{∨}⟩ = 0, then p′ = q, q′ = p, and μ = λ.

(d) If either {p, q} = {ψ_{α}, ψ_{β}} for simple roots α ≠ β, or ψ_{α} ∈ {p, q} for some simple root α and ⟨κ + ν − λ, α^{∨}⟩ > 0, then p′ = p, q′ = q, and μ = κ + ν − λ.

4.2.2. Lemma. For fixed values of λ^{[i,j]} and λ^{[i+1,j+1]}, the correspondence determined by rule 4.2.1 between λ^{[i,j+1]} and λ^{[i+1,j]}, and between (h_{i,j}, v_{i,j+1}) and (v_{i,j}, h_{i+1,j}), is symmetrical.

Proof. This follows from a careful analysis of the different cases that can arise. In cases (c) and (d) of rule 4.2.1, replacement of λ by the indicated value of μ leads to the same case, and gives back the original value of λ for μ. We may therefore assume that one of cases (a) and (b) applies. Define weights μ_{0}, μ_{1}, μ_{2}, μ_{3} by μ_{0} = κ + ν − λ, μ_{1} = μ_{0} in case (a) and μ_{1} = μ_{0} + α in case (b), μ_{2} = dom_{W_{κ,ν}} (μ_{1}), and μ_{3} = μ; replacing λ by μ, call the corresponding weights λ_{0}, λ_{1}, λ_{2}, λ_{3}. One then proves successively that λ_{i} = κ + ν − μ_{3−i} for i = 0, 1, 2, 3 in a straightforward manner in all the cases, using the details that were given before the statement of rule 4.2.1.

4.2.3. Construction (jeu de taquin for ψ-paths). Let κ, λ, ν be dominant integral weights for 𝔤, π′ a κ-dominant ψ-path of length l with π′(1) = λ − κ, and p a λ-dominant ψ-path of length k with p(1) = ν − λ. We construct a dominant integral weight μ, a κ-dominant ψ-path π of length k with π(1) = μ−κ, and a μ-dominant ψ-path p′ of length l with p′(1) = ν −μ, in the following steps.

∘ Let π′ = h_{0,0} ∗ ⋯ ∗ h_{0,l−1} and p = v_{0,l} ∗ ⋯ ∗ v_{k−1,l}, where the h_{i,j} and

v_{i,j} are ψ-paths of length 1; ∘ Set λ^{[0,j]} := κ+∑_{j′<j} h_{0,j′}(1) for 0 ≤ j ≤ l, and λ^{[i,l]} := λ+∑_{i′<i} v_{i′,l}(1)

for 0 ≤ i ≤ k; ∘ Determine the weights λ^{[i+1,j]} and the paths h_{i+1,j} and v_{i,j} for 0 ≤ i < k

and l > j ≥ 0, using rule 4.2.1; ∘ Return π = v_{0,0} ∗ ⋯ ∗ v_{k−1,0} and p′ = h_{k,0} ∗ ⋯ ∗ h_{k,l−1}.

4.2.4. Theorem (symmetry of jeu de taquin for ψ-paths). The construction 4.2.3 is its own inverse: if when applied to (κ, π′, p) it returns (π, p′), then applied to (κ, π, p′) it will return (π′, p). Moreover, it is symmetric with respect to dualisation of paths: when applied to (ν, p^{∗}, π^{′∗}) it will return (p^{′∗}, π^{∗}).

Proof. This is immediate from lemma 4.2.2.

4.2.5. Lemma. Lemma 3.3.5 remains valid when construction 3.3.3 is replaced by construction 4.2.3.

4.2.6. Theorem. In the situation of construction 4.2.3 the path π can be obtained from p by application of a sequence of operators e_{i}, and similarly the path p′ can be obtained from π′ by application of a sequence of operators f_{i}. In particular, if κ = 0, one has p ∈ B_{π} and p′ ∈ B_{π′}.

Proof. By symmetry (theorem 4.2.4) it suffices to prove the first statement (about p and π). By lemma 4.2.5, it will suffice to prove the case where π′ has length 1, which we therefore assume henceforth. In order to proceed by induction on the length of p, it is necessary to strengthen the statement being proved as follows. There exists a sequence of indices i_{1}, …, i_{n} (with n ≥ 0) and a sequence of paths p = p_{n}, p_{n−1}, …, p_{0} = π, such that for j = n, …, 1, one has e_{i_{j}}(p_{j}) = p_{j−1}, and moreover ⌊κ + p_{j}⌋_{α_{i_{j}}} < 0 except when π′ = ψ_{α} for some simple root α and j = n, in which case one has α_{i_{n}} = α and ⌊κ + p_{j}⌋_{α} = 0. To this we add one more detail: if π′ = ψ_{α} and ⌊κ + p⌋_{α} = 0, then n > 0.

If p is of length 0 we take n = 0 and there is nothing to prove; assume therefore that p has positive length. Let v = v_{0,1} in construction 3.3.3, so that we can write p = v ∗ q; similarly put v′ = v_{0,0} and π = v′ ∗ ρ. Put κ′ = λ^{[1,0]} and λ′ = λ^{[1,1]}; we consider the construction applied to (κ′, h_{1,0}, q), which by lemma 4.2.5 returns (ρ, p′). By the induction hypothesis there exist indices i_{m}, …, i_{1} and paths q = q_{m}, …, q_{0} = ρ with q_{j−1} = e_{i_{j}}(q_{j}) for j = m, …, 1. Let v = v_{0}, …, v_{l} = v′ be the sequence of paths called p_{0}, …, p_{l} in the discussion preceding the statement of rule 4.2.1; put n = m + l. It was established there that for all j < l there exists a simple root α such that v_{j+1} = e_{α}(v_{j}); let the index of this root be i_{n−j}, thus extending our sequence of indices to i_{n}, …, i_{1}. We shall say that we are in the exceptional case if m > 0, l > 0, and h_{1,0} = ψ_{α} for some simple root α; otherwise we are in the regular case. Define a sequence of paths p = p_{n}, …, p_{0} = π as follows: set p_{j} = v_{n−j} ∗ q for n ≥ j > m and p_{j} = v′ ∗ q_{j} for m > j ≥ 0; finally set p_{m} = v′ ∗ q in the regular case, and p_{m} = v_{l−1} ∗ q_{m−1} in the exceptional case.

We shall first show that the only possibility to have f_{i_{j}}(v′ ∗q_{j−1}) ≠ v′ ∗q_{i} for 0 < j ≤ m occurs for j = m in the exceptional case, and that we then have f_{i_{m}}(v′∗q_{m−1}) = v_{l−1}∗q_{m−1}; this will establish e_{i_{j}}(p_{j}) = p_{j−1} for j ≤ m. Putting α = α_{i_{j}}, the operator f_{α} will only apply to the left factor of v′ ∗ q_{j−1} if

⌊κ′ + v^{′∗}⌋_{α} < ⌊κ′ + q_{j−1}⌋_{α}.  (1)

Since v^{′∗} is κ′-dominant, the left hand side is non-negative, so (1) can only hold if its right hand side, which equals ⌊κ′ + q_{j}⌋_{α} + 1 since q_{j−1} = e_{α}(q_{j}), is strictly positive; by the induction hypothesis this only happens when h_{1,0} = ψ_{α} and j = m, and the right hand side then equals 1. Therefore the left hand side must be 0, which excludes case (d) of rule 4.2.1, so that we have l > 0 and are in the exceptional case. It can be seen from rule 4.2.1 that h_{1,0} = ψ_{α} and l > 0 imply that α_{i_{m+1}} = α and ⌊κ + v_{l}⌋_{α} = 0; therefore the left hand side of (1) is indeed 0 in this case and f_{α}(v′) = v_{l−1}, so that we have f_{α}(v′ ∗ q_{m−1}) = v_{l−1} ∗ q_{m−1} as claimed.

We proceed to show similarly that the only possibility to have e_{i_{n−j}}(v_{j} ∗ q) ≠ v_{j+1}∗q for 0 ≤ j < l occurs for j = l−1 in the exceptional case, and that we then have e_{i_{m+1}}(v_{l−1} ∗ q) = v_{l−1} ∗ q_{m−1}; this will establish e_{i_{k}}(p_{k}) = p_{k−1} for k > m. Putting α = α_{i_{n−j}}, the operator e_{α} will only apply to the right factor of v_{j} ∗ q if

⌊λ′ + v_{j}^{∗}⌋_{α} > ⌊λ′ + q⌋_{α}.  (2)

Since q is λ′-dominant, the right hand side is non-negative, so (2) can only hold if its left hand side is strictly positive, and in particular ⟨λ′, α^{∨}⟩ > 0. Since we have e_{α}(v_{j}) = v_{j+1}, it can be seen from rule 4.2.1 that we must have j = 0 or j = l − 1; however if j = 0 ≠ l − 1, we would be in case (b) of that rule with v_{0} = v = ψ_{α}, and the left hand side of (2) would be 0, which allows us to conclude j = l − 1. Now whichever of the cases (a), (b), or (c) gives v_{l} = e_{α}(v_{l−1}) with ⟨λ′, α^{∨}⟩ > 0, it also gives h_{1,0} = ψ_{α}, and makes the left hand side of (2) equal to 1. By the induction hypothesis (including the detail added) the right hand side of (2) will now be 0 if and only if m > 0, which means we are in the exceptional case; we then have moreover α_{i_{m}} = α, so that indeed e_{α}(v_{l−1} ∗ q) = v_{l−1} ∗ e_{α}(q) = v_{l−1} ∗ q_{m−1}, as claimed.

5 Generalisation of jeu de taquin to piecewise linear paths

It remains to establish the statements involving ⌊κ+p_{j}⌋_{α_{i_{j}}} needed for the induction. If 0 < j < m, or if j = m in the regular case, one has p_{j} = v′ ∗ q_{j}; as v′ is κ-dominant with v′(1) = κ′ −κ this implies ⌊κ+p_{j}⌋_{α_{i_{j}}} = ⌊κ′ +q_{j}⌋_{α_{i_{j}}}. Everything then follows immediately from the corresponding part of the induction hypothesis (if l = 0 one uses h_{1,0} = π′). This covers all cases with l = 0, so from now on assume l > 0. If m < j < n, or if j = n and π′ is linear, then we have ⌊λ+v_{n−j}⌋_{α_{i_{j}}} < 0 by the construction of the sequence v_{0}, …, v_{l}, and since p_{j} = v_{n−j} ∗ q this implies ⌊λ + p_{j}⌋_{α_{i_{j}}} < 0. If on the other hand π′ = ψ_{α} (so that κ = λ), then we see from cases (b) and (c) of rule 4.2.1 that α_{i_{n}} = α and ⌊κ + v⌋_{α} = 0, which implies ⌊κ + p⌋_{α} = 0 since p is λ-dominant. The only case left is j = m in the exceptional case; put α = α_{i_{m+1}} = α_{i_{m}}, so that h_{1,0} = ψ_{α}. One can show ⌊κ + p_{m}⌋_{α} = −1 in various ways, as the minimum is attained at both sides of the concatenation p_{m} = v_{l−1} ∗ q_{m−1}. For instance, we have seen that ⌊κ + v_{l}⌋_{α} = 0 in this case, which implies ⌊κ + v_{l−1}⌋_{α} = −1 since v_{l} = e_{α}(v_{l−1}). This completes our proof.

§5. Generalisation of jeu de taquin to piecewise linear paths. We shall now generalise the constructions considered so far to a much larger class of paths than that of the ψ-paths, namely for the entire class Π of piecewise linear paths in the space of rational weigths. The rule that describes the construction in the elementary cases will become simpler than rule 4.2.1, and in fact resembles rule 4.1.1, yet we shall see that the global construction contains construction 4.2.3 as a special case. Given this circumstance, it may seem silly that we went through all the complications of the preceding subsection. There is however an important price that we pay for the simplicity and generality of the new construction: it gives us no direct control over integrality, and therefore does not allow a direct connection to be made with the root operators e_{α} and f_{α}.

It turns out that the simplest way to describe the jeu de taquin construction for piecewise linear paths is not using doubly indexed families of paths, or collections of “horizontal” and “vertical” path segments, but using “2dimensional” paths, that is to say, piecewise linear maps f: [0, 1]×[0, 1] → X_{Q} (here piecewise linear means there is a finite triangulation of [0, 1]×[0, 1] such that the restriction of f to each of the triangles is linear). For these maps we do not require (as was done for paths) that they must always “start at 0”, but we shall require that their image is contained in the dominant chamber. Then instead of conditions like rule 4.2.1, we shall impose the following somewhat curious functional equation.

5.1. Rule. For every pair of intervals [s_{0}, s_{1}], [t_{0}, t_{1}] ⊆ [0, 1] such that f is linear on each of the line segments {s_{0}} × [t_{0}, t_{1}] and [s_{0}, s_{1}] × {t_{1}}, one has f(s, t) = dom_{W} (f_{0}(s, t)) for (s, t) ∈ [s_{0}, s_{1}] × [t_{0}, t_{1}], where f_{0} is the linear function given by f_{0}(s, t) = f(s_{0}, t) + f(s, t_{1}) − f(s_{0}, t_{1}).

If we prescribe f on each of the segments {s_{0}} × [t_{0}, t_{1}] and [s_{0}, s_{1}] × {t_{1}} by functions that are linear and everywhere dominant, then f(s, t) = dom_{W} (f_{0}(s, t)) (with f_{0} as in the rule) defines an extension of f to [s_{0}, s_{1}] × [t_{0}, t_{1}] that is piecewise linear and everywhere dominant. In particular this extension determines piecewise linear paths on the edges [s_{0}, s_{1}] × {t_{0}} and {s_{1}} × [t_{0}, t_{1}] of the rectangle [s_{0}, s_{1}] × [t_{0}, t_{1}] opposite to those on which f was prescribed. We shall call this operation of extending f across a rectangle [s_{0}, s_{1}] × [t_{0}, t_{1}] an elementary extension of f. We still need to show that the condition of rule 5.1 is satisfied for any applicable subintervals of [s_{0}, s_{1}] and [t_{0}, t_{1}], so let [s′_{0}, s′_{1}] ⊆ [s_{0}, s_{1}] and [t′_{0}, t′_{1}] ⊆ [t_{0}, t_{1}] be such that f is linear on L_{1} = {s′_{0}} × [t′_{0}, t′_{1}] and on L_{2} = [s′_{0}, s′_{1}] × {t′_{1}}. We first show that the weights f_{0}(s′_{0}, t′_{0}) and f_{0}(s′_{1}, t′_{1}) are not separated by any wall, i.e., that there is no root β (positive or negative) for which the linear functional ϕ(x, y) = ⟨f_{0}(x, y), β^{∨}⟩ has ϕ(s′_{0}, t′_{0}) < 0 and ϕ(s′_{1}, t′_{1}) > 0. If there were such a root β, then ϕ(s′_{0}, t′_{1}) ≠ 0 would contradict the linearity of f either on L_{1} or on L_{2}, whereas ϕ(s′_{0}, t′_{1}) = 0 would imply by linearity that ϕ(s_{0}, t_{0}) < 0 and ϕ(s_{1}, t_{1}) > 0, contradicting the fact that both f_{0}(s_{0}, t_{0}) and f_{0}(s_{1}, t_{1}) are dominant. Therefore, there exists a w ∈ W such that f(s, t) = w(f_{0}(s, t)) on L_{1} ∪ L_{2}. Being linear, f_{0} satisfies f_{0}(s, t) = f_{0}(s′_{0}, t) + f_{0}(s, t′_{1}) − f_{0}(s′_{0}, t′_{1}); hence the validity of rule 5.1 is established by the following computation for (s, t) ∈ [s′_{0}, s′_{1}] × [t′_{0}, t′_{1}]:

f(s, t) = dom_{W} (w(f_{0}(s, t))) = dom_{W} (w(f_{0}(s′_{0}, t) + f_{0}(s, t′_{1}) − f_{0}(s′_{0}, t′_{1})))
= dom_{W} (f(s′_{0}, t) + f(s, t′_{1}) − f(s′_{0}, t′_{1})).

Because of the way the rule is formulated, there is no need for a counterpart of construction 4.2.3: a piecewise linear function f defined on [0, 1]×[0, 1] that satisfies the rule must match any function constructed by repeated elementary extensions from the restriction of f to the edges {0} × [0, 1] and [0, 1] × {1} of the unit square. However, it is not immediately obvious that repeated elementary extensions suffice to cover all of the unit square. To see the difficulty, imagine that every elementary extension would result at each of the opposite edges of the rectangle in a path consisting of two different linear parts; then infinitely many elementary extensions could be applied, but they would fail to define f beyond a certain subset with fractal boundary. We shall show that this cannot happen; to do so we need to consider the directions of the segments of the paths obtained by elementary extension. For a dominant weight λ and weight μ in its orbit W λ, the set { w ∈ W | μ = w(λ) } is a coset in W/W_{λ}, and it does not change when μ is multiplied by a positive scalar. We define this coset to be the direction of π_{μ}, or of any translate of a positive multiple of π_{μ}, and endow W/W_{λ} with the Bruhat order, and the associated length function l. Then the following lemma is an immediate consequence of the definition of elementary extensions.

5.2. Lemma. Let f satisfy rule 5.1 on [s_{0}, s_{1}] × [t_{0}, t_{1}] and be linear on {s_{0}} × [t_{0}, t_{1}] and [s_{0}, s_{1}] × {t_{1}}; let the direction of the path defined by f along [s_{0}, s_{1}] × {t_{1}} be τ, and let the path defined by f along [s_{0}, s_{1}] × {t_{0}} be π_{0} ∗ ⋯ ∗ π_{n} where the π_{i} are linear paths with differenct directions τ_{i}. Then τ ≤ τ_{0} < ⋯ < τ_{n}, and consequently n ≤ l(τ). Similar statements hold for the other two edges.

5.3. Theorem/construction (jeu de taquin for piecewise linear paths). Let κ, λ, ν be dominant integral weights for 𝔤, π′ a κ-dominant piecewise linear path with π′(1) = λ − κ, and p a λ-dominant piecewise linear path with p(1) = ν − λ. There is a unique piecewise linear function f: [0, 1] × [0, 1] → X_{Q} with f(0, t) = κ + π′(t) and f(t, 1) = λ + p(t) for t ∈ [0, 1] that satisfies rule 5.1. Putting μ = f(1, 0), we may define a κdominant piecewise linear path π with π(1) = μ−κ by π(t) = f(t, 0)−κ, and a μ-dominant piecewise linear path p′ with p′(1) = ν −μ by p(t) = f(1, t)−μ.

Proof. We shall show that by repeatedly applying elementary extensions to f we succeed after a finite number of step in finding an extension of f to all of [0, 1]×[0, 1], which is then automatically unique. By a trivial induction on the number of linear segments from which p is concatenated, we may reduce to the case that p is linear. We cannot continue with a similar induction on the number of segments of π′ however; instead we apply induction on the length l(τ) of the direction τ of the path p. For l(τ) = 0, which is equivalent to p ∈ P^{+}, the function f given by f(s, t) = κ + π′(t) + p(s) is everywhere dominant, and is therefore the unique function satisfying the conditions in the theorem. Now suppose l(τ) = l > 0. For each fixed value of l we apply induction on the number of linear segments from which π′ is concatenated. If π′ is linear, elementary extension suffices to define f uniquely on [0, 1]×[0, 1]. Otherwise we apply elementary extension to p and the final linear segment of π′. Let the piecewise linear path obtained at the side opposite to p be p_{0} ∗ ⋯ ∗ p_{n}; let the segment p_{i} give the values of f on [s_{i}, s_{i+1}] × {t_{1}} and have direcion τ_{i} (i = 0, …, n). Because of lemma 5.2 we have l(τ_{0}) ≤ l and l(τ_{i}) < l for i > 0. In case l(τ_{0}) = l we can extend f to [s_{0}, s_{1}] × [0, t_{1}] by induction on the number of segments of π′; for the remaining segments p_{i} (including p_{0} if l(τ_{0}) < l) we can apply the hypothesis of induction with respect to l(τ), and conclude that we can extend f successively to the rectangles [s_{i}, s_{i+1}] × [0, t_{1}]; this defines f uniquely on [0, 1] × [0, 1].

It is not difficult to see that the rules 4.1.1 and 4.2.1 can obtained as instances of construction 5.3; as a consequence, that construction generalises the constructions 4.1.3 and 4.2.3. The symmetries of those constructions are preserved, since one can show with similar arguments as we gave to show that the function obtained by elementary extension satisfies rule 5.1, that the transpose function f′(s, t) = f(t, s) also satisfies that rule.

5.4. Theorem (symmetry of jeu de taquin for piecewise linear paths). If a piecewise linear function f satisfies rule 5.1, then the transpose function f′ defined by f′(s, t) = f(t, s) satisfies that rule as well. In particular, the construction 5.3 is its own inverse: if when applied to (κ, π′, p) it returns (π, p′), then applied to (κ, π, p′) it will return (π′, p). Moreover, construction 5.3 is symmetrical with respect to dualisation of paths: when applied to (ν, p^{∗}, π^{′∗}) it will return (p^{′∗}, π^{∗}).

Since construction 5.3 is does not refer to any integrality condition at all, it is not easy to relate it directly to the root operators e_{α} and f_{α}. It is for instance not true that the paths π and p are related by a sequence of applications of such operators, not even in the case of an elementary extension. What one gets instead is a sequence of applications of fractional powers e_{α}^{x} or f_{α}^{x} of root operators with x ∈ Q; here e_{α}^{x} maps a path p to a References

non-zero value if and only if ⌊p⌋_{α} ≤ −x, in which case one has

e_{α}^{x}(p)(s) = p(s) + max (0, x + ⌊p⌋_{α} − min_{t∈[0,s]} ⟨p(t), α^{∨}⟩) α.

A relation with root operators which seems plausible, and which we hope to establish in further work, can be formulated as follows. Let us call a path p ∈ Π of integral shape if p ∈ B_{π} for some π ∈ P^{+}. Then if κ ∈ X, and if π′ and p are of integral shape, then so are the paths π and p′ obtained from κ, π′, and p by construction 5.3; moreover π can be obtained from p by a sequence of applications of operators e_{α}, and p′ from π′ by applications of operators f_{α}. This would imply in particular that if κ = 0 then p ∈ B_{π} and p′ ∈ B_{π′}, and that the construction defines, for any fixed pair of paths π, π′ ∈ P^{+} with π′(1) = λ and π(1) = μ, a bijection between the λ-dominant paths p ∈ B_{π} and the μ-dominant paths p′ ∈ B_{π′}, with moreover λ + p(1) = μ + p′(1). It would also imply that any class of paths of integral shape, that is closed under the root operators (such as for instance the class of Lakshmibai-Seshadri paths), would also be closed under construction 5.3, which would therefore give rise to a special instance of it, similar to constructions 4.1.3 and 4.2.3.

References.

[KaNa] M. Kashiwara and T. Nakashima, “Crystal graphs for representations of the q-analogue of classical Lie algebras”, Journal of Algebra 165, (1994), 295–345.

[vLee1] M. A. A. van Leeuwen, “The Robinson-Schensted and Schützenberger algorithms, an elementary approach”, Electronic J. of Combinatorics 3 (no. 2), R15, (1996), 32 pp.

[vLee2] M. A. A. van Leeuwen, “Tableau algorithms defined naturally for pictures”, Discrete Mathematics 157, (1996), 321–362.

[vLee3] M. A. A. van Leeuwen, Edge sequences, ribbon tableaux, and an action of affine permutations, Report MAS-R9707, CWI, Amsterdam. To appear in European Journal of Combinatorics.

[vLee4] M. A. A. van Leeuwen, Some bijective correspondences involving domino tableaux, Report MAS-R9708, CWI, Amsterdam.

[Litt1] P. Littelmann, “A Littlewood-Richardson rule for symmetrizable Kac-Moody algebras”, Inventiones mathematicae 116, (1994), 329–346.

[Litt2] P. Littelmann, “Paths and root operators in representation theory”, Annals of Mathematics 142, (1995), 499–525.

[Litt3] P. Littelmann, “A plactic algebra for semisimple Lie algebras”, Advances in Math. 124 (2), (Dec. 1996), 312–331.

[Macd] I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford Mathematical Monographs, Clarendon press, Oxford, 1979.

[Rob] G. de B. Robinson, “On the representations of the symmetric group”, American Journal of Math. 60, (1938), 745–760.

References

[Zel1] A. V. Zelevinsky, “A Generalisation of the Littlewood-Richardson Rule and the Robinson-Schensted-Knuth Correspondence”, Journal of Algebra 69, (1981), 82–94.