Cyclic Permutations on words, Tableaux and Harmonic Polynomials

Alain Lascoux

mars 1990

=ABSTRACT. — The compatibility of tableaux with cyclic permutations provides a rank poset structure on the set of tableaux with a given evaluation, allowing the embedding of different sets of tableaux into each other. There results a decomposition of these sets into smaller sets, the cardinals of which are multiplicities of isotypic components (for the symmetric group action) either in cohomology rings of flag manifolds or equivalently in spaces of harmonic polynomials.

1. Introduction

It has been known since the work of Young that tableaux provide a way of explicitly describing the irreducible representations of the symmetric group over ℂ. It was soon realized by Littlewood, Robinson, Weyl and others that irreducible characters (that is to say Schur functions) are also given by tableaux ; we prefer to express this by lifting a Schur function into the sum of all tableaux of a given shape inside the free algebra (Th.2.3).

Tableaux are now special words in the free algebra. Cyclic permutations on words induce an operation on tableaux that we call “cyclage” and give a rankposet structure on the set of tableaux with a given evaluation, the rank being an important invariant called the cocharge . Cyclage connects any tableau to a row tableau which can be identified with a monomial in commuting variables (Prop.3.1). Inverting the cyclage lifts computations in the ring of polynomials to the level of tableaux, e.g. it lifts the permutation action of the symmetric group (lemma 4.1). From this one can imbed canonically each of the sets of tableaux with a given evaluation into the set of standard tableaux, obtaining a partition of the set of standard tableaux into disjoint sets that we call atoms (Th.4.2 and 4.4).

The cocharge gives also the Kostka-Foulkes polynomials which are the coefficients in the expansion of Hall-Littlewood polynomials in the basis of Schur functions (Th.5.1) . An interesting consequence of the construction is that the matrix of Kostka-Foulkes polynomials is the product of the incidence matrix (of the lattice of partitions ) by a positive matrix, the entries of which correspond to the atoms (Cor.5.2).

Young introduced tableaux to obtain idempotents in the group algebra of the symmetric group, obtaining also multiplicities and bases of representations with the help of standard tableaux of a given shape. By identifying instead the regular representation with the cohomology ring of the flag manifold, one can further decompose the regular representation, with the elementary components corresponding to the atoms (Th.6.5). Tableaux furthermore provide explicit bases (as free modules) of the cohomology spaces of different flag manifolds (Prop.6.11).

Instead of cohomology rings, following Specht we may take spaces of harmonic polynomials. Cocharge and atoms provide multiplicities of representations for the action of the affine symmetric group (Th.7.4), and provide bases, notably Verma’s basis (section 8).

Section 9 gives additional properties of atoms and shows how to generate them from two-rows tableaux.

The combinatorics of tableaux is a joint work with M.P. Schützenberger and constitutes the more substantial part of this paper, to which I have added a translation into geometrical terms.

2 . The plactic algebra

Let 𝔸^{∗} be the free monoid generated by the alphabet 𝔸 = {a_{1} < a_{2} < ⋯} and ℤ[𝔸^{∗}] the free algebra of 𝔸. The elements of 𝔸^{∗} are words. The degree of a word w is denoted |w|, and its degree in a letter a is denoted |w|_{a}. The image in the ring of polynomials ℤ[𝔸] of a word w is called its evaluation and noted ev(w). We shall also use the exponent notation ev(w) = e^{I}, with I = (|w|_{a_{1}} , |w|_{a_{2}} , |w|_{a_{3}} , …). A word w is standard iff there exists an integer k such that ev(w) = a_{1}a_{2} ⋯ a_{k}.

A word is a row iff it is weakly increasing : w = x_{1}x_{2}x_{3} ⋯, x_{1} ≤ x_{2} ≤ x_{3} ≤ ⋯, x_{i} ∈ 𝔸. The ring ℤ[𝔸] can be imbedded into the free algebra as the free

ℤ-module generated by rows (writing monomials as increasing words). A row w = x_{1}x_{2}x_{3} ⋯ dominates another w′ = x′_{1}x′_{2}x′_{3} ⋯ if |w| ≤ |w′| and x_{1} > x′_{1} , x_{2} > x′_{2} . . ..

Every word admits a unique factorization, called its row-factorization, as a product of a minimal number of rows w = v_{k} ⋯ v_{2}v_{1}. The shape ∥w∥ of w is the sequence of degrees |v_{k}|, …, |v_{1}| of its rows. A word is a tableau iff for its row-factorization w = v_{k} ⋯ v_{2}v_{1}, one has

\{ \begin{matrix}∥w∥ is weakly increasing \\ v_{k} dominates v_{k−1}, …, & v_{2} dominates v_{1} \end{matrix}

In other terms, a word is a tableau iff it is obtained by reading in the appropriate/French way a usual planar Young tableau. Thus the word bcd aabd is a tableau that one can planarly display as _{aabd}^{bcd} .

The Schur function S_{I} of index a partition I is the sum of all tableaux of shape I in the free algebra .

We can see that the product S_{1} · S_{2} is equal to the sum S_{12} + S_{3} , but that it is different from S_{2} · S_{1}. For, after deleting the words in common, we have on the left ∑_{x<y}(yxx + yxy) + ∑_{x<y<z}(yxz + zxy), and on the right ∑_{x<y}(xyx + yyx) + ∑_{x<y<z}(yzx + xzy).

To force equality, one of the principal methods is the following set of elementary relations (due to Knuth), for x < y < z in 𝔸 :

(2.1)  yxx ≡ xyx ; yxy ≡ yyx
(2.2)  yxz ≡ yzx ; zxy ≡ xzy

These relations generate a congruence which is called the plactic congruence and denoted ≡ . This is the same as the algebraic formalization of “Schensted’s construction” which produces, for any word, the only tableau which is congruent to it. The plactic monoid 𝔸^{∗}/ ≡ is the associated quotient of 𝔸^{∗} and its algebra, the plactic ring ℤ[𝔸^{∗}/ ≡].

The ring of symmetric polynomials in 𝔸, ℤ[𝔸]^{𝔖} , is canonically imbedded into the plactic algebra, according to the following theorem (see [L& S1] ) :

Theorem 2.3 . — The submodule of ℤ[𝔸^{∗}/ ≡] generated by the images of the S_{I} is a commutative algebra isomorphic to ℤ[𝔸]^{𝔖}. In other words, one has the following diagram :

ℤ[𝔸^{∗}]  ⟶ ℤ[𝔸^{∗}/ ≡] ⟶ ℤ[𝔸]
↑  ↑  ↑
\begin{cases}F ree module \\ generated by the S_{I} \end{cases}\} ⟶ ℤ[𝔸]^{𝔖}  ⟶^{∼} ℤ[𝔸]^{𝔖}

3 . Cyclic permutations

Let t = xw be a tableau, x being its initial letter. The word wx is congruent to another tableau t′ ≡ wx. If t has at least two rows, then t → t′ is called a cyclage ; the inverse of a cyclage, when it exists, is called a cocyclage. From the Schensted construction it is clear that if t_{1} → t′ and t_{2} → t′ are two cyclages leading to the same tableau, then the shapes of t_{1} and t_{2} are different. Thus, shape is sufficient to differentiate between all the cocyclages of a given tableau. In section 9 , we describe a more general cyclage and show how its properties are related to the Pieri decomposition of the product of a Schur function by an elementary symmetric function.

We need there only the following property, which is proved in [L& S1] :

Proposition 3.1 . — The cyclage induces a rank-poset structure on the set of tableaux with a given evaluation u; the row u is the unique minimal element.

We shall note the above poset T (u), or T (I), for u = a_{1}^{I_{1}}a_{2}^{I_{2}} · · ·. Let us call the rank of a tableau t for this structure the cocharge ν(t), putting ν(u) = 0. An algorithm for computing directly the cocharge is given in [Mac, p.129] (in fact, what is given there is the charge which is the complement of the cocharge). Example 3.2 . — The poset T (321), for the alphabet {a, b, c}, is

Charge  P oset  Cocharge
0  ^{c ; {bb \atop aaa}}  4
↓
1  ^{c ; {b \atop aaab}}  {bb \atop aaac}  {bbc \atop aaa}  3
↓  ↓ ↙
2  {b \atop aaabc}  {bc \atop aaab}  2
↘ ↓
3 {c \atop aaabb} 1
↓
4  _{aaabbc}  0

4. Canonical embeddings of tableaux

There are many linear operations on ℤ[𝔸] which can be extended to the plactic or free algebra, thanks to the cyclage connecting any tableau to a row (prop.3.1).

For example, the symmetric group 𝔖(𝔸) acts by permutation on ℤ[𝔸] : a, b, … ⟶ aμ, bμ, … for μ ∈ 𝔖(𝔸) induces a^{I_{a}}b^{I_{b}} ⋯ ⟶ a^{I_{a}μ}b^{I_{b}μ} ⋯ for I ∈ ℕ^{𝔸}.

We have defined more generally in [L & S1] an action of 𝔖(𝔸) on the free algebra :

(w ∈ 𝔸^{∗}, μ ∈ 𝔖(𝔸)) → w^{μ} ∈ 𝔸^{∗} .

This action is compatible with the plactic congruence and with the cyclage, as stated in the following lemma (cf. [L &S1, th.4.6]) :

Lemma 4.1 . — Let v, w be two words, μ be a permutation. Then

i) v ≡ w ⇒ v^{μ} ≡ w^{μ} ,

ii) w is a tableau ⇔ w^{μ} is a tableau ; moreovoer, the shapes of w and w^{μ} are identical,

iii) w = xw′, w^{μ} = yw′′, with x, y ∈ 𝔸 ⇒ (w′x)^{μ} = w′′y .

Given a tableau t and a permutation μ, the tableau t^{μ} is determined by the above lemma. For cycle the tableau to the row : t = t_{0} → t_{1} → ⋯ → t_{k} = ev(t). We obtain t^{μ} by cocyclage, starting from the row (ev(t))^{μ} : t^{μ} ← t_{1}^{μ} ← ⋯ ← t_{k}^{μ}; knowing t_{j+1}^{μ}, we determine t_{j}^{μ} among the different tableaux which cycle to t_{j+1}^{μ} by the condition that its shape equals that of t_{j}.

For example, the symmetric group 𝔖(a, b, c) exchanges the following 6 chains of cyclages :

\begin{matrix}^{c ; {bb \atop aaa}} → _{aaac}^{bb} → _{aaab}^{bc} → _{aaabb}^{c} → _{aaabbc} & ; ^{c ; {bb \atop aab}} → _{aaac}^{bb} → _{aaab}^{bc} → _{aabbb}^{c} → _{aabbbc} ; \\ ^{c ; {bc \atop aaa}} → _{aaac}^{bc} → _{aaab}^{cc} → _{aaabc}^{c} → _{aaabcc} & ; ^{c ; {bc \atop aac}} → _{aacc}^{bc} → _{aabc}^{cc} → _{aabcc}^{c} → _{aabccc} ; \\ ^{c ; {bc \atop abb}} → _{abbc}^{bc} → _{abbb}^{cc} → _{abbbc}^{c} → _{abbbcc} & ; ^{c ; {bc \atop abc}} → _{abcc}^{bc} → _{abbc}^{cc} → _{abbcc}^{c} → _{abbccc} . \end{matrix}

Consider the following transformation φ on words :

“change the letter a which is furthest to the right into a b; if there are no a’ s, send the word to 0 ” .

Let moreover I ∈ ℕ^{𝔸} be such that I_{a} = m > I_{b} = n. It is clear that in this case φ transforms a tableau of evaluation I into a tableau of evaluation I_{a} − 1, I_{b} + 1, I_{c}, … of the same shape, and that φ is compatible with the cyclage. In other words, φ induces an embedding, still denoted φ, of the rank poset T (I_{a}I_{b}I_{c} …) into the rank poset T (I_{a} − 1 I_{b} + 1 I_{c} …), and the image of a cyclage is a cyclage. Combining φ with the action of the symmetric group, we obtain :

Theorem 4.2 . — Let I, J be two partitions : I ≤ J ; Ǐ ∈ ℕ^{𝔸} a permutation of I, J̌ ∈ ℕ^{𝔸} a permutation of J. Then there exists a canonical embedding of the rank poset T (Ǐ) into the rank poset T (J̌).

The embedding of T (Ǐ) into T (1 … 1) is called the standardization and is denoted θ. It should be noticed that θ does not coïncide with the standardization mentionned by [Sche, th.4] obtained by numbering the successive occurrences of a from left to right, then of b, etc. To obtain the theorem, we just need to observe that the order on partitions (decreasing from left to right) is generated by the vector addition I → I + (0 … 0 −1 0 … 0 1 0 …). Therefore there exists at least one sequence of permutations μ, η, …, ζ which provides the required embedding by the composite

T (Ǐ)⟶^{μ}T (Ǐ^{μ})↪^{φ}T (H)⟶^{η}T (Ȟ^{η})↪^{φ} … ↪^{φ}T (J̌^{ζ^{−1}})⟶^{ζ}T (J̌) .

The fact that the embedding is canonical is provided by the compatibility with the cyclage of φ and of the action of 𝔖(𝔸) : given t ∈ T (Ǐ), we cycle it to the row ev(t) ; now the image of t in T (J̌) is obtained by the corresponding cocylages, starting from the row in T (J̌)

For example, the poset T (321) described in 3.2 is isomorphic to T (312). Its image by φ is a subposet of T (222) :

cc ; {bb \atop aa}

↓

c ; {bb \atop aac}

↓

c ; {bc \atop aaa}  c ; {bc \atop aab}  {bb \atop aacc}
↓  ↓ ↙
c ; {b \atop aaac}  {bc \atop aaac}  {bcc \atop aaa}  c ; {b \atop aabc}  {bc \atop aabc}  {bcc \atop aab}
↓  ↓ ↙  ↓  ↓ ↙
{b \atop aaacc}  {cc \atop aaab}  {b \atop aabcc}  {cc \atop aabb}
↘ ↓  ↘ ↓
{c \atop aaabc}  {c \atop aabbc}
↓  ↓
aaabcc  aabbcc
\overbrace{T (312)}  \overbrace{T (222)}

Definition 4.3 . — Given a partition J, the atom A(J) is the poset of standard tableaux

A(J) := θ(T (J)) \ ∪_{I<J} θ(T (I)) ,

i.e. is the poset of standard tableaux which are images of tableaux of evaluation e^{J}, but not images of tableaux of evaluation e^{I} with I < J.

The atomic decomposition of the set of standard tableaux T (1 … 1) pulls back to all the other sets of tableaux and gives :

Theorem 4.4 . — For any partition J, the standardization θ is a bijection between the set T (J) and the disjoint union (on all partitions I ≤ J) of the atoms A(I). The set θ^{−1}(A(J)) is the complement of the canonical images of all the T (I), I < J, in T (J).

For example, the 26 standard tableaux of degree 5 are distributed among the following 7 atoms (with the alphabet {1, …, 5}) :

Cocharge  \underbrace{Atoms}
10  _{54321}
9  _{43215}
8 {_{32514}^{53214}
7 \{32145 {54213 \atop 52413}
6 \{42513 {42135 \atop 24135}  ^{54312}
5 {_{25134}^{52134}  {_{43512}^{43125}
4  _{21345}  {_{35124}^{53124}  _{53412}
3  ^{31245}  ^{34125}  ^{54123}
2  ^{41235}  ^{45123}
1  ^{51234}
0  ^{12345}
A(11111) A(1112) A(122) A(113) A(23) A(14) A(5)

5 . Kostka-Foulkes polynomials

Given a tableau t, we have called cocharge of t the number of cyclages needed to obtain from it the row of the same evaluation. Any set of tableaux T gives rise to a cocharge polynomial ∑_{t∈T} q^{ν(t)}. In particular, for any H ∈ ℕ^{𝔸}, and any partition J, the Kostka-Foulkes polynomial K(H, J) is the sum ∑ q^{ν(t)} taken over all tableaux of evaluation e^{H} and shape J , cf [Mac, p.126]. Kostka-Foulkes polynomials are special Kazhdan-Lusztig polynomials, see [Lus].

The above construction induces a decomposition of Kostka-Foulkes polynomials. For let us denote R(I, J) the cocharge polynomial corresponding to the subset of tableaux of shape J in the atom A(I). The following property is a direct corollary of theorem(4.4) :

Theorem 5.1 . — Let H ∈ ℕ^{𝔸}, let I be the partition obtained by reordering H and J be another partition. Then the Kostka-Foulkes polynomial decompose into the following sum of smaller positive polynomials :

K(H, J) = K(I, J) = ∑_{H≤I} R(H, J)

Corollary 5.2 . — i) Given any triple of partitions I, I′, J : I ≤ I′, then ∑_{H} μ(H)K(H, J), where H runs over the entire interval [I, I′] and μ is the Möbius function of the interval, is a polynomial with positive integral coefficients.

ii) The product of the Kostka matrix by the Möbius matrix is the matrix [R(I, J)]_{I,J} .

For example, for the shape 1223 and all possible evaluations, we have the following K(∗, 1223) and R(∗, 1223) polynomials (writing only their coefficients, 122 ⋯ means 1 + 2q + 2q^{2} + ⋯) :

\underbrace{Evaluation}  \underbrace{K(∗, 1223)}  \underbrace{R(∗, 1223)}
1^{8}  123467888764321  000012456664321
↓  ↓  ↓
1^{6}2  1234554321  0001244321
↓  ↓  ↓
1^{4}22  123331  000121
↓ ↘  ↓ ↘  ↓ ↘
11222 1^{5}3  1221  11111  0011  00111
↓ ↘ ↓  ↓ ↘ ↓  ↓ ↘ ↓
2222 11123  111  11  011  01
↘ ↓  ↘ ↓  ↘ ↓
1223  1  1

For all partitions of weight 6, the matrix of Kostka-Foulkes polynomials can be found in [Mac, p.127] (with charge instead of cocharge). Its product by the Möbius matrix is the following, writing · for 0 entries (lexicographic order on decreasing partitions) :

\begin{matrix}1 & · & · & · & · & · & · & · & · & · & · \\ · & q & · & q^{2} & · & · & q^{3} & · & · & q^{4} & q^{5} \\ · & · & q^{2} & · & · & q^{3} & q^{4} & q^{4} & · & q^{6}+q^{5} & q^{8}+q^{7}+q^{6} \\ · & · & · & q^{3} & · & · & q^{5} + q^{4} & · & · & q^{7}+q^{6}+q^{5} & q^{9}+q^{8}+q^{7}+q^{6} \\ · & · & · & · & q^{3} & · & · & · & q^{5} & q^{6} & q^{9}+q^{7} \\ · & · & · & · & · & q^{4} & q^{5} & q^{5} & q^{6} & q^{8}+2q^{7}+q^{6} & q^{11}+2q^{10}+2q^{9}+2q^{8}+q^{7} \\ · & · & · & · & · & · & q^{6} & · & · & q^{9}+q^{8}+q^{7} & q^{11}+q^{10}+2q^{9}+q^{8}+q^{7} \\ · & · & · & · & · & · & · & q^{6} & · & q^{8} & q^{12}+q^{10}+q^{9} \\ · & · & · & · & · & · & · & · & q^{7} & q^{9}+q^{8} & q^{13}+q^{12}+2q^{11}+q^{10}+q^{9} \\ · & · & · & · & · & · & · & · & · & q^{10} & q^{14}+q^{13}+q^{12}+q^{11} \\ · & · & · & · & · & · & · & · & · & · & q^{15} \end{matrix}

In [L & S2], we gave result 5.2 i) only for intervals of length 2, but in fact, the same proof applies to any interval.

6 . Flag varieties

The ring ℤ[𝔸] is a free ℤ[𝔸]^{𝔖}-module. The natural scalar product on it is, for any pair P, Q of polynomials in ℤ[𝔸],

(6.1)  (P , Q) := ∑_{μ} [P Q / Δ]^{μ}

where Δ is the Vandermonde ∏_{i<j}(a_{i} − a_{j}) .

Many bases of ℤ[𝔸] as a free module are known ; for example, the embedding 𝔖(n − 1) ↪ 𝔖(n) easily gives the basis {e^{I}, I ≤ ρ} with ρ = n − 1 ⋯ 2 1 0 and n = card(𝔸) (cf. [Gro]).

Schubert polynomials are another basis, which has the advantage of being self-adjoint with respect to the scalar product 6.1 (cf. [L& S1). Schubert polynomials correspond to the classes of Schubert varieties when one interprets ℤ[𝔸] as follows :

Lemma 6.2 . — Let n be a positive integer, F(ℂ^{n}) the flag variety for Gl(n), 𝔸 an alphabet of cardinal n. Then the cohomology ring H(F) of F(ℂ^{n}) is isomorphic, as a graded 𝔖(n)-ring, to the quotient of ℤ[𝔸] by the ideal generated by symmetric polynomials in 𝔸 without constant terms.

The scalar product 6.1 induces a scalar product < · | · > on H(F) : for any \overline{P} , \overline{Q} of elements of H(F), let P and Q be any lifts of \overline{P} , \overline{Q} in ℤ[𝔸]. Then

< \overline{P} | \overline{Q} > := (P, Q)^{ξ_{0}}

i.e. the scalar product of \overline{P} , \overline{Q} is equal to the image of (P, Q) by the specialization ξ_{0} : 𝔸 → {0, …, 0}.

More generally, given any partition I of weight n and a corresponding unipotent 𝔲 of Gl(n), one can consider the subvariety F_{𝔲} of F(ℂ^{n}) of flags fixed by 𝔲. One has the following theorem due to De Concini & Procesi [DeC-Pro] ; see proposition 6.11 below for an explicit ℤ-basis and 9.10 for generators of the ideal.

Theorem 6.3 . — The integral cohomology ring of F_{𝔲} is 𝔖(n)-isomorphic to the quotient H_{I} of ℤ[𝔸] by a certain explicit ideal depending only on the partition I corresponding to 𝔲. Moreover, H_{I} is a free ℤ-module.

The ring H_{I} inherits from ℤ[𝔸] a grading. For any partition J, the isotypic component corresponding to J is also graded, and using a formal indeterminate q, one can represent its multiplicity by the polynomial ∑ d_{r}(I, J) q^{r} , where d_{r}(I, J) is the multiplicity of the irreducible character corresponding to J in the homogeneous component of degree r of H(F_{𝔲}) ≃ H_{I}. The full ring corresponds to the maximal partition I = 1 … 1.

Macdonald [Mac, II p.92 and III ex.9] states that

Theorem 6.4 . — Given any pair of partitions I, J, the multiplicity of the character corresponding to J in the cohomology ring H_{I} is equal to the Kostka-Foulkes polynomial K(I, J).

To the natural order on partitions correspond canonical 𝔖(n)-surjections :

I ≥ I′ ⇒ H_{I} ↦ H_{I′}

(see [Hot-Spr] , [DeC-Pro]).

Translating theorem (5.1) , we get the more precise result :

Theorem 6.5 . — Let I be a partition and Ȟ_{I} the intersection of the kernels of all the canonical surjections H_{I} ↦ H_{I′} , I > I′. Then the multiplicity in Ȟ_{I} of the character of 𝔖(n) corresponding to a partition J is equal to the polynomial R(I, J).

Example 6.6 . — The atom A(1122) contains the tableaux 653412 (coch. 7), 534126 (coch. 6) , 346125 (coch.5) and thus Ȟ(1122) is concentrated in degrees 7,6,5, being an irreducible representation of 𝔖(6) in each of these degrees (of respective dimensions 9, 16, 5, corresponding to the partitions 1122, 123, 33 which are the shapes of the three tableaux).

Tableaux provide not only multiplicities, but explicit bases as well of the free modules H_{J}, for the following reason.

Given a partition J, let Y(J) be the set of all words (called Yamanouchi words) congruent to the tableau ⋯ 2^{J_{2}}1^{J_{1}}0^{J_{0}} (we have taken the Arabic alphabet {0, 1, 2, …} ). Let furthermore E(J) be the set of words which are smaller (componentwise) than at least one word in Y(J). Example 6.7 . — Y(122) = {21100, 12100, 21010, 12010, 10210} and E(122) \ Y(122) = {20100, 02100, 11100, 20010, 21000, 02010, 11010, 12000, 00210, 10110, 10200; 01100, 20000, 01010, 02000, 11000, 00110, 00200, 10100, 10010; 10000, 01000, 00100, 00010; 00000}.

Yamanouchi words in Y(J) are bijectively associated to standard tableaux of shape J : taking the successive levels of 1, 2, 3, … in a tableau t, we get a word (which has to be written from right to left) and every Yamanouchi word

is obtained in this way, e.g. 5 {37 \atop 1246} ↔ 1020100 (because 1, 2, 4, 6 are on the bottom row, 3, 7 on the middle one, and 5 on the top row).

Lemma 6.8 . — i) For any pair of partitions I, J : I ≤ J, E(I) ⊆ E(J). ii) For any integer k ≥ 0, and for any I, let E(I, k) be the subset of words

in E(I) beginning with k. Let I^{♯k} be the partition obtained by reordering, if necessary, the sequence … I_{k+1} I_{k} − 1 I_{k−1} … I_{0}. Then E(I^{♯k}) is identical with the set obtained by erasing the first letter of each word in E(I, k).

Proof. i) It is sufficient to compare E(I) and E(J) for a pair of the type

I  = (… m n … n n + 1 …)
J  = (… m + 1 n … n n + 1 …)
{P laces from \atop the right}  ↑h  ↑k

with m < n, because such pairs generate the natural order on partitions. A word w is a Yamanouchi word iff for every factorization w = w′w′′, |w′′|_{0} ≥ |w′′|_{1} ≥ |w′′|_{2} ≥ ⋯ (cf. [L& S1, prop.3.7]). One sees that, given a word w ∈ Y(I), changing the leftmost occurrence of “h − 1” into “h”, the leftmost occurrence of “h − 2” into “h − 1”, …, the leftmost occurrence of “k” into “k + 1”, produces a word v > w which is still a Yamanouchi word. Thus Y(I) ⊂ E(J), which implies that E(I) ⊆ E(J).

ii) Let I = (… m n … n n …)  , with m < n .
↑h  ↑k

Then I^{♯k} = I^{♯h} = (… m n − 1 … n n …). Let w ∈ E(I^{♯h}) and v be any Yamanouchi word in E(I^{♯h}) such that w ≤ v. Then the word hv is Yamanouchi, and thus belongs to Y(I) ; therefore the words hw and kw belong to E(I). Conversely, let kw be a word in E(I), hv any Yamanouchi word in Y(I). Then v belongs to Y(I^{♯h}) and thus w belongs to E(I^{♯h})

Thus, looking back at example 6.6, one has to decompose E(122) into subsets of words beginning by 2, 1, 0 respectively. Erasing then this first letter, one obtains E(122^{♯2}) = {1100, 1010, 0100, 0010, 0000} = E(022) ; E(122^{♯1}) = {2100, 2010, 0210, 2000, 0200, 1100, 1010, 0110, 1000, 0100, 0010, 0000} = E(112) = E(122^{♯0}).

Let M(I) be the free module generated by the {e^{β}, β ∈ E(I)}. Translating lemma 6.8 in terms of modules, and remembering that e^{ijh...} means a^{i}b^{j}c^{h} ⋯, we obtain

Corollary 6.9 . — Let k ≥ 0 be an integer, I be a partition. Then

a^{k}M(I)/a^{k+1}M(I) ≃ M(I^{♯k})

Now geometry provides an induction between the flags in F(ℂ^{n−1}) and F(ℂ^{n}). More precisely, one has the following property which is the key technical point in DeConcini-Procesi’s description of the cohomology of flag varieties ([DeC-Pro, lemma 4.5]) :

Lemma 6.10 . — Let k ≥ 0 be an integer, I a partition. Then

a^{k}H_{I}/a^{k+1}H_{I} ≃ H_{I^{♯k}}

Therefore the spaces H_{I} satisfy the same induction as the modules M(I) and H_{I} ≃ M(I) (as free ℤ-modules) because this is true for the starting point I = 0 ⋯ 0. Combining this with th.6.5, one obtains the following refinement of De Concini-Procesi’s theorem :

Proposition 6.11 . — Let J be a partition. Then H_{J} is a free ℤmodule with basis {e^{β}, β ∈ E(J)}; Ȟ_{J} is a free module with basis {e^{β}, β ∈ E(J) \ ∪_{I<J}E(I)}.

From the explicit basis of H_{J}, one could recover 6.2, 6.3 and 6.4 and give a basis of the ideal mentionned in 6.3. For example, since the set Y(1 ⋯ 1) contains only the word ρ = n − 1 ⋯ 1 0, we recover that H_{1···1} = H(F) is generated as a free ℤ-module by the monomials {e^{β}, β ≤ ρ}.

We can now develop example 6.6 : proposition 6.11 asserts that Ȟ_{1122} admits the basis E(1122) \ {E(222) ∪ E(1113)}. In degree 7, this basis coïncide with Y(1122) = {103210, 130210, 310210, 132010, 312010, 132100, 321010, 312100, 321100}; in degree 6, we have the 16 words which are not Yamanouchi : {102210, 120210, 122010, 122100, 103110, 130110, 310110, 311010, 131010, 131100, 311100, 103200, 130200, 310200, 312000, 132000}. Finally, in degree 5, there are only 5 words which are not dominated by a word in E(222) ∪ E(1113) : {131000, 130100, 130010, 103100, 103010}.

As concerns geometry, we mention that [DeC-Pro] have given another interpretation of the ring H_{I}, proving a conjecture of [Kra] and showing that H_{I} is isomorphic to the coordinate ring of the scheme intersection of the closure of a nilpotent orbit with a maximal torus. A simpler description of the ideal defining H_{I}, due to [Tan], is given in proposition 9.10. A stronger result has been obtained by [Wey] who dealt directly with the ideal of a nilpotent conjugacy class.

7 . Harmonic polynomials

A harmonic polynomial in ℚ[𝔸] is a polynomial which is annihilated by all symmetric derivations (i.e. any symmetric polynomial in the partial derivatives ∂_{a}, a ∈ 𝔸) without constant term.

Since partial derivatives commute, any derivative of a harmonic polynomial is still a harmonic polynomial. Using Taylor’s formula, one can also see that any element (μ, I) of the affine symmetric group : μ ∈ 𝔖(𝔸), I ∈ ℤ^{𝔸}, acting by

{a, b, …} ⟶ {a^{μ} + I_{a} , b^{μ} + I_{b}, …}

preserves the set of harmonic polynomials.

Let V(𝔸) be the ℤ-module of harmonic polynomials. The composite morphism

ℚ ⊗ V(𝔸) ↪ ℚ[𝔸] ⟶ ℚ ⊗ H(F)

is an isomorphism (cf. [Bor]). The product of two harmonic polynomials is not harmonic in general, but it is congruent to one and only one harmonic polynomial modulo the ideal generated by symmetric polynomials without constant term.

There are several canonical surjections ℤ[𝔸] ⟶ V(𝔸). We shall only give two of them, one related to cohomology, the other to the Grothendieck ring.

For any finite ordered set 𝕏 = {x_{1}, x_{2}, …} of elements of ℤ[𝔸], let us write Δ(𝕏) for the Vandermonde ∏_{i<j}(x_{i} − x_{j}).

For any I ∈ ℕ^{𝔸}, denote by ∂^{I} the product of partial derivatives ∂^{I} = ∂_{a}^{I_{a}}∂_{b}^{I_{b}} ⋯ and by Δ^{I} the image of \frac{1}{Δ(ρ)}Δ(𝔸) under ∂^{I}, with ρ = (n−1, …, 1, 0) as above (and thus, Δ(ρ) is the number n−1! n−2! ⋯ 1! 0!).

Lemma 7.1 . — The morphism ϕ : ℤ[𝔸] ⟶ V(𝔸) defined by ϕ(e^{I}) = Δ^{I} factorizes through H(F) and it induces an isomorphism H(F) ≃ V(𝔸). The induced scalar product ≪ ϕ(P), ϕ(Q) ≫:=< P | Q >, with P, Q in H(F) is such that ≪ h̄, Δ^{I} ≫ = ∂^{I}(h̄)(0, …, 0) for any h̄ in V(𝔸) and is such that the ∂^{I} are self -adjoint.

Proof. We shall assume that Δ(𝔸)/Δ(ρ) and that its derivatives generate V(𝔸). Thus ϕ is surjective. The action of the ring of differential operators ℤ[∂_{a}, ∂_{b}, …] on V(𝔸) factorizes through the quotient of this ring by the ideal generated by symmetric operators without constant term ; therefore ϕ factorizes through H(F) and V(𝔸) is generated by the {Δ^{I} : 0 ≤ I ≤ ρ}. Given any homogeneous polynomial P whose image in H(F) is non-zero, there exists at least one monomial e^{I} such that in H(F), e^{I}P ≡ ce^{ρ} with c ≠ 0. Hence the harmonic polynomial ϕ(p) cannot be zero, since its image by ∂^{I} is cϕ(e^{ρ}) ≠ 0.

The operator ∂^{I} is the image of the operator “multiplication by e^{I} ” which is clearly self-adjoint since for any P, Q in H(F), we have

< P | Q > = < P Q | 1 >.

Finally, since ≪ h̄, Δ^{I} ≫ =≪ ∂^{I}(h̄), Δ^{0···0} ≫, it only remains to compute the scalar products of Δ^{0···0} with a basis, e.g. {Δ^{I} : 0 ≤ I ≤ ρ}. But ≪ Δ^{I}, Δ^{0···0} ≫ =< e^{I} | 1 >= 0, except ≪ 1, Δ^{0···0} ≫ = < e^{ρ} | e^{0···0} > = 1. This implies by linearity ≪ h̄, Δ^{0···0} ≫ = h̄(0, …, 0)

The images of the different natural bases of ℤ[𝔸] are bases of harmonic polynomials, and pairs of adjoint bases give explicit decompositions in V(𝔸) :

Corollary 7.2 . — Let {P_{I}}, {Q_{I}} be adjoint bases of ℤ[𝔸] as a free ℤ[𝔸]^{𝔖}-module. Then every harmonic polynomial h̄ admits the following decomposition :

h̄ = ∑ ≪ h̄ , ϕ(P_{I}) ≫ ϕ(Q_{I}) .

For example, in the case of 𝔖(3), the basis of Schubert polynomials is {e^{000}, e^{100}, e^{100} + e^{010}, e^{110}, e^{200}, e^{210}}; its adjoint is {−e^{012}, e^{002}, e^{011}, −e^{010} − e^{001}, −e^{001}, e^{000}} (i.e., it is self-adjoint up to sign and reversal of the alphabet, cf. [L& S3] ). Corollary 7.2 implies the following decomposition, writing h̄^{I} for the value of ∂^{I}(h̄) at the point 0, 0, 0 :

(7.3) h̄ = −h̄^{000}Δ^{012} + h̄^{100}Δ^{002} + (h̄^{100} + h̄^{010})Δ^{011} − h̄^{110}(Δ^{010} + Δ^{001}) − h̄^{200}Δ^{001} + h̄^{210}Δ^{000} .

One could also have obtained 7.3 from Taylor formula, using relations between derivatives of an harmonic polynomial (i.e. computing modulo the ideal generated by symmetric differential operators without constant term).

Let us denote ϕ̌ : H(F) ⟶ V(𝔸) the isomorphism defined by ϕ̌(e^{I}) = Δ^{ρ−I}, 0 ≤ I ≤ ρ. Let I be a partition of weight n , J = J_{1} ≥ J_{2} ≥ ⋯ ≥ J_{k} its conjugate and H ∈ ℕ^{n} the vector

\underbrace{(J_{1} + ⋯ J_{k−1}) ⋯ (J_{1} + ⋯ J_{k−1})}_{J_{k}} … \underbrace{(J_{1} + J_{2}) ⋯ (J_{1} + J_{2})}_{J_{3}} \underbrace{J_{1} ⋯ J_{1}}_{J_{2}} \underbrace{0 ⋯ 0}_{J_{1}}

The polynomial h̄_{I} = Δ^{H} is a product of Vandermonde determinants. For example, I = 5221 leads to J = 43111 and H = (4 + 3 + 1 + 1 , 4 + 3 + 1 , 4 + 3 , 4, 4, 4, 0, 0, 0, 0). Therefore, h̄_{5221} = \frac{1}{Δ(ρ)} ∂_{a_{1}}^{9} ∂_{a_{2}}^{8} ∂_{a_{3}}^{7} (∂_{a_{4}}∂_{a_{5}}∂_{a_{6}})^{4} (Δ) = \frac{1}{Δ(210)}Δ(a_{4}, a_{5}, a_{6}) · \frac{1}{Δ(3210)}Δ(a_{7}, a_{8}, a_{9}, a_{10}).

The orbit of h̄_{I} under the symmetric group (resp. affine symmetric group) generates an irreducible (resp. reducible) ℂ-representation of 𝔖 called Specht module (resp. affine Specht module, denoted V_{I}, cf. [Jam-Ker]). Since h̄_{I} = ϕ̌(e^{H}), and since the space H_{I} is generated by the action of the affine symmetric group on the element e^{H} according to proposition 6.11, the two spaces H_{I} and V_{I} are isomorphic under ϕ̌. This allows to translate theorems 6.3 and 6.4 in terms of harmonic polynomials :

Theorem 7.4 . — Let I, J be two partitions. Then

i) The multiplicity in the affine Specht module V_{I} of the character of the symmetric group corresponding to J is equal to the Kostka-Foulkes polynomial K(I, J).

ii) The multiplicity of the character J in the quotient space V_{I} / ∪_{I′<I} V_{I′} is R(I, J).

For example, for 𝔖(6), the atom A(1113) contains only the tableaux 6 5 4 123, 5 46 123, 5 4 1236, 6 4 1235, 46 1235 and 4 12356, the respective cocharges of which are 6, 5, 5, 4, 4, 3. Thus the space V_{1113} / {V_{123} ∪ V_{114}} is of dimension 10 in degree 6, of dimension 16+10 in degree 5, dimension 10+9 in degree 4 and dimension 5 in degree 3.

8 . Verma Bases

Let ℤ[𝔸, 𝔸ˇ ] be the ring of Laurent polynomials in an alphabet 𝔸 of cardinal n, 𝕏 a second alphabet of the same cardinal and ψ : ℤ[𝔸, 𝔸ˇ ] ⟶ V(𝕏) the morphism defined by ψ(e^{I}) = \frac{1}{Δ(ρ)}Δ(𝕏+I) := \frac{1}{Δ(ρ)} ∏_{h<k} ((x_{h}+I_{h})−(x_{k}+I_{k})) (we shall denote this polynomial Δ_{I}). Let moreover ε_{1} be the specialisation 𝔸 ⟶ {1, …, 1} and K(𝔸) be the quotient of ℤ[𝔸, 𝔸ˇ ] by the ideal generated by the {(P − P^{ε_{1}}, P ∈ ℤ[𝔸, 𝔸ˇ ]^{𝔖}}. The ring K(𝔸) can be interpreted as the Grothendieck ring of the flag manifold F(ℂ^{n}).

The morphism ψ satisfies the same type of properties as ϕ (we shall not repeat the proof) :

Lemma 8.1 . — 1) ψ is a surjection which factorizes through K[𝔸] and induces an isomorphism K[𝔸] ≃ V(𝕏).

2) The induced scalar product ≺ , ≻ defined by ≺ ψ(P), ψ(Q) ≻ = (P, Q)^{ε_{1}} is such that the translation 𝕏 → 𝕏 + I is self-adjoint, and such that ≺ h̄, Δ_{I} ≻ = h̄(I) , I ∈ ℤ^{n}.

Adjoint bases of ℤ[𝔸, 𝔸ˇ ] (as a free ℤ[𝔸, 𝔸ˇ ]^{𝔖}- module) furnish explicit decompositions of harmonic polynomials. For example in the case of 𝔖(3) as in 7.3, Schubert polynomials give :

(8.2) h̄ = −h̄(000)Δ_{012} + h̄(100)Δ_{002} + (h̄(100) + h̄(010))Δ_{011} −

h̄(110)(Δ_{010} + Δ_{001}) − h̄(200)Δ_{001} + h̄(210)Δ_{000} .

Verma [Ver] has introduced another basis which is related to the cyclage structure discussed in section 3.

Given a permutation μ ∈ 𝔖(𝔸), considered as the word a_{1}^{μ} a_{2}^{μ} ⋯ a_{n}^{μ} in 𝔸^{∗}, the cocharge vector μC is defined inductively as follows (cf. [Mac], p.129) : attach to a_{1} the index 0 ; if k is attached to a_{j}, then attach k (resp. k + 1) to a_{j+1} if μ has the subword a_{j}a_{j+1} (resp. a_{j+1}a_{j}). The cocharge vector is the vector of the preceeding indices. For example, indexing μ = a_{3}a_{5}a_{1}a_{7}a_{2}a_{6}a_{4}, one obtains (a_{3})_{1}(a_{5})_{2}(a_{1})_{0}(a_{7})_{3}(a_{2})_{0}(a_{6})_{2}(a_{4})_{1} , and thus μC = (1203021). The sum of the components of μC is in fact equal to the cocharge of the tableau congruent to the word μ (cf. [L& S1] ). In the present case, the tableau is a_{7} a_{3}a_{5}a_{6} a_{1}a_{2}a_{4} and its cocharge is 1 + 2 + 0 + 3 + 0 + 2 + 1 = 9.

Verma conjectured (this was proved by Husulkar) that the constant 1 could be expressed as an integral sum of polynomials Δ_{μC} := \frac{1}{Δ(ρ)}Δ(𝕏 + μC) .

More precisely, one has (cf. [Hus]) :

Theorem 8.3 . — The set {Δ_{μC}, μ ∈ 𝔖} is a ℤ-basis of V. There exist harmonic polynomials {h̄_{μ}, μ ∈ 𝔖} such that h̄_{μ}(ηC) = 0, η ≠ μ, and h̄_{μ}(μC) = 1 .

The scalar product ≺ , ≻ allows us to interpret the polynomials h̄_{μ}. For any I ∈ ℤ^{n}, write Iω for the reverse vector (I_{n}, …, I_{1}). It is easy to check that the matrix of scalar products (e^{μC}, e^{ηCω}) is triangular, with ±1 on the diagonal (cf. [Hus] for the appropriate order on 𝔖). Thus the set {e^{μC}} is a ℤ-basis of ℤ[𝔸, 𝔸ˇ ] as a free ℤ[𝔸, 𝔸ˇ ]^{𝔖}- module ; it has a certain adjoint basis {P_{μ}, μ ∈ 𝔖}.

Corollary 8.4 . — i) Husulkar’s harmonic polynomials h̄_{μ} are the image under ψ of the polynomials P_{μ}.

ii) 1 = ∑_{μ∈𝔖} (P_{μ})^{ε_{1}} Δ_{μC}

Proof. The condition h̄_{μ}(ηC) = 1 or 0 means precisely that {h̄_{μ}} is adjoint to {Δ_{μC}} with respect to ≺, ≻. This follows from the fact that the scalar product is the image of the natural one on ℤ[𝔸, 𝔸ˇ ] ; assertion i) follows.

In particular, 1 = ∑ ≺ 1, h̄_{μ} ≻ Δ_{μC}. However, for any I in ℤ^{n}, one has ≺ 1, Δ_{I} ≻= 1 = (e^{I})^{ε_{1}}. Therefore, ≺ 1, h̄_{μ} ≻= (P_{μ})^{ε_{1}}

Property ii) explicits Verma’s footnote [Ver, p.669] that the integers ≺ 1, h̄_{μ} ≻ are the degrees of certain T (orus)-modules. Verma writes ch(e^{I}) for the scalar product (e^{I}, 1) and calls “trace ” the specialisation morphism ε_{1}. His starting point was that the polynomial that calls “Weyl polynomial” : I ⟶ Δ(I)/Δ(ρ) (considered as a function of I_{1}, …, I_{n})) gives the dimension of the irreducible representation (of Gl(ℂ^{n})) of highest weight I − ρ whenever I is regular (i.e. I_{1} > I_{2} > ⋯ > I_{n} ≥ 0).

For 𝔖(3), the matrix (e^{μC}, e^{ηC}) is

e^{012}  -1  ·  ·  ·  ·  ·
e^{011}  ·  1  ·  ·  ·  ·
e^{001}  ·  ·  1  ·  ·  ·
e^{101}  ·  ·  ·  -1  ·  ·
e^{010}  ·  ·  ·  ·  -1  ·
e^{000}  ·  ·  ·  ·  ·  1
e^{000}  e^{010}  e^{101}  e^{100}  e^{110}  e^{210}

Therefore, any harmonic polynomial h̄ decomposes as follows :

(8.5) h̄ = h̄(000)Δ_{210} − h̄(010)Δ_{110} − h̄(101)Δ_{100} + h̄(001)Δ_{101}+ h̄(011)Δ_{010} − h̄(012)Δ_{000} .

For 𝔖(4), apart from the diagonal, there are only 4 × 2 non-zero entries in the matrix of scalar products : (e^{0101}, e^{1201}) = −1 , (e^{0210}, e^{0102}) = 1 , (e^{3210}, e^{1021}) = −e^{1111} ⇒ ≺ Δ_{3210}, Δ_{1021} ≻ = −1 ,

(e^{2120}, e^{2012}) = e^{1111} ⇒ ≺ Δ_{2120}, Δ_{2012} ≻ = 1 .

Hence the adjoint basis of the polynomials {Δ_{0000}, Δ_{0010}, Δ_{0100}, Δ_{1000}, Δ_{1100}, Δ_{0110}, Δ_{1001}, Δ_{1010}, Δ_{0101}, Δ_{1011}, Δ_{1101}, Δ_{1110}, Δ_{0210}, Δ_{2010}, Δ_{2100}, Δ_{2110}, Δ_{1201}, Δ_{1210}, Δ_{2101}, Δ_{1021}, Δ_{2102}, Δ_{2120}, Δ_{2210}, Δ_{3210}} is {(Δ_{0123} − Δ_{0101}), −Δ_{0122}, (Δ_{0212} + Δ_{0001}), (Δ_{0010} − Δ_{2012}), (Δ_{1201} − Δ_{0112}), Δ_{0121}, Δ_{1012}, −(Δ_{1021} + Δ_{0000}), −Δ_{0112}, −Δ_{0012}, (Δ_{0102} + Δ_{0111}), (Δ_{1011} − Δ_{0120}), −Δ_{0111}, Δ_{1011}, −Δ_{1101}, −(Δ_{1010} + Δ_{0011}), −Δ_{0101}, Δ_{0110}, Δ_{1001}, Δ_{0011}, −Δ_{0001}, Δ_{0010}, −Δ_{0100}, Δ_{0000}}.

9. Some properties of atoms

More general cyclic permutations than those used in section 3 (we shall nevertheless keep the same word cyclage) furnish a richer structure on the set of tableaux with a given evaluation. This structure is in fact closely related to the Pieri formulae which characterize the ring of symmetric polynomials by giving the product of a Schur function by a complete function. Through the embedding given by theorem 2.3 of ℤ[𝔸]^{𝔖} into the plactic algebra, Pieri formulae become the following lemma ( lemma (3) of Schensted [Sche] and [Schü1]).

Given a positive integer n and a partition I, we denote the set of partitions obtained from the diagram of I by adding (resp. deleting) n boxes, with no two in the same column, by {n ⊗ I} (resp. {I/n}. This set is a distributive lattice and we shall show elsewhere that its properties provide in particular a combinatorial description of the multiplication of Hall-Littlewood polynomials.

Lemma 9.1 . — For any integer n and any partition I, we have

S_{n} · S_{I} ≡ ∑_{J∈{n⊗I}} S_{J} and S_{I} · S_{n} ≡ ∑_{J∈{n⊗I}} S_{J}

Let t be a tableau of shape J, I another partition such that J/I is a single box. Then, according to 9.1, there exist two unique pairs (x, w), (w′, x′), such that x, x′ ∈ 𝔸, that w, w′ are tableaux of shape I and that t ≡ xw , t ≡ w′x′. Definition 9.2 . — Let t be a tableau, xw and vy, x, y ∈ 𝔸, two words congruent to t, and let t′, t′′ be the tableaux t′ ≡ wx , t′′ ≡ yv. Let μ be any permutation such that |t^{μ}|_{a_{1}} ≥ |t^{μ}|_{a_{i}} for any i. Then t → t′ (resp. t → t′′) is an I-cyclage (resp. I-cocyclage) iff x̌ ≠ a_{1} (resp. y̌ ≠ a_{1}) with x̌ the initial letter of (xw)^{μ}, y̌ the final letter of (vy)^{μ}, and I the shape of the tableau congruent to w (resp. v).

In other words, if a_{1} is the most frequent letter in t (so that we can take μ= identity), then any cyclic permutation on the words congruent to t is acceptable as long as the letter which moves is different from a_{1}. For example, let t be the

tableau c ; {bc \atop abc} on the alphabet 𝔸 = \{a, b, c\}; consider the three words congruent to it :

t = \underbrace{c}_{x_{1}} \underbrace{bcabc}_{w_{1}} ≡ \underbrace{c}_{x_{2}} \underbrace{cbcabc}_{w_{2}} ≡ \underbrace{c}_{x_{3}} \underbrace{cbcab}_{w_{3}}

and their images by the permutation μ : {a, b, c} → {c, b, a} :

(x_{1}w_{1})^{μ} = c bbaaa ≡ (x_{2}w_{2})^{μ} = b cbaaa ≡ (x_{3}w_{3})^{μ} = a cbbaa .

Thus, the cyclic permutations c bcabc → bcabc c and c cbabc → cbabc c are two cyclages, but not c cbcab → cbcab c since the word (ccbcab)^{μ} begins by a.

Proposition 3.1 and theorem 4.2 extend to this more general cyclage (cf. [L& S1] ) :

Theorem 9.3 . — i) Let I be a partition. The cyclage induces a rankposet structure on the set of tableaux with evaluation e^{I} (this set is still denoted T (I)) ; the row e^{I} is the unique minimal element.

ii) Let I, J be two partitions : I ≤ J ; Ǐ ∈ ℕ^{𝔸} a permutation of I, J̌ ∈ ℕ^{𝔸} a permutation of J. Then there exists a canonical embedding of the rank poset T (Ǐ) into the rank poset T (J̌).

For the example 3.2, one has only to complete the poset with the extra cyclage

c ; {bb \atop aaa} ⟶ c ; {b \atop aaab} .

We need moreover the special composition of cyclages t = wu ⟶ uw ≡ t′, with u the bottom row of t. We denote by K(t) the tableau t′ congruent to uw and call katabolism the morphisme t → K(t). Katabolism provide an invariant of tableaux. For applying repeatedly Pieri formulae 9.1 (which imply that katabolism is a bijection), one obtains :

Theorem 9.4 . — i) The sequence of shapes {∥K^{i}(t)∥ , i ≥ 0} characterizes t among all the tableaux of the same evaluation.

ii) For any t, the tableau θ(t) is the unique standard tableau s with identical sequence {∥K^{i}(s)∥ , i ≥ 0} = {∥K^{i}(t)∥ , i ≥ 0}.

Example 9.5 . — The image by θ of the sequence of katabolisms

_{abbcdde}^{ce} ⟶ _{abbcddee}^{d} ⟶ _{abbcddde}^{e} ⟶ _{abbcdddee}

is the sequence (taking now as alphabet {1, 2, …})

_{1234568}^{79} ⟶ _{12345679}^{8} ⟶ _{12345678}^{9} ⟶ _{123456789}

Another invariant can also be read on the sequence K^{i}(t). We shall consider here only the case of standard tableaux. The bottom row of a standard tableau s contains a maximal subword of consecutive integers starting with 1, the degree of which is denoted f(s).

Lemma 9.6 . — For any standard tableau s, the sequence f(s), f(K(s) − f(s), f(K^{2}(s) − f(K(s), … is a decreasing partition I. Furthermore s belongs to the atom A(I).

Going back to example 9.5, we obtain for the standard tableau 79 1234568 the sequence 6, 7 − 6, 8 − 7, 9 − 8, 9 − 9, …, i.e. the partition 6111. Therefore this tableau belongs to A(6111).

We can also characterize the tableaux t in T (I), I a partition, such that θ(t) belongs to the atom A(I) ( a, b are the first two letters of 𝔸 and 𝔸_{p} is the alphabet of the first p letters) :

Lemma 9.7 . — i) Let t ∈ T (I). Then θ(t) ∈ A(I) iff for every permutation μ, the restriction of t^{μ} to {a, b}^{∗} is congruent to b^{I_{bμ}}a^{I_{aμ}}.

ii) Let I be a partition, J a permutation of I, p an integer, I′ the partition obtained by reordering (J_{1}, …, J_{p}). Let t be a tableau in T (J), t′ its restriction to 𝔸_{p}^{∗}. Then θ(t) ∈ A(I) implies that θ(t′) ∈ A(I′).

iii) The set of tableaux t ∈ T (I) such that θ(t) ∈ A(I) is closed by cocyclage.

iv) The minimum elements in A(I) are two-row tableaux.

Proof. i) According to 4.2, t is such that θ(t) ∈ A(I) iff there exists no partition J < I such that t belongs to the image of T (J) in T (I). But from the description of the canonical embedding in terms of the morphism φ in 4.2, t belongs to some T (J) iff there exists a permutation μ such that |t^{μ}|_{a} ≥ |t^{μ}|_{b} and the tableau t^{μ} has some occurrence of b in its bottom row. This settles the case where |t^{μ}|_{a} ≥ |t^{μ}|_{b}; otherwise, we take the product of μ by the transposition σ of a, b and notice that the image by σ of the word b^{j}a^{i}, j ≥ i is the word a^{j−i} b^{i} a^{i} ≡ b^{i} a^{j}.

ii) Follows from i), since we have to use only those permutations μ which preserve globally 𝔸_{p}.

iii) Let t → t′ be an H-cyclage of tableaux in T (I). Let μ be any permutation such that |t^{μ}|_{a} ≥ |t^{μ}|_{b}. Then t^{μ} → t^{′μ} is an H-cyclage : t^{μ} ≡ xw, t^{′μ} ≡ wx, where w is a tableau of shape I and x ≠ a. Thus if t^{′μ} has no b in its bottom row, then x ≠ b and the restriction of t^{μ} and t′^{μ} to {a, b}^{∗} are identical. According to criterium i), this ensures that θ(t) ∈ A(I) if θ(t′) ∈ A(I).

iv) Let t be a tableau of shape J and t → t′ be an H − cyclage such that J_{2} = H_{2}. Then for any μ, t^{μ} = xw → wx ≡ t^{′μ} is such that x ≠ a, b. Therefore the restrictions of t^{μ} and t′^{μ} to {a, b}^{∗} coïncide and thus θ(t) ∈ A(I) implies θ(t′) ∈ A(I). If t is a two-row tableau of shape J, then t admits only the (J_{2}−1, J_{1})-cyclage ; if t = b^{m}ua^{n}v, m > 0, then the cyclage t → t′ ≡ b^{m−1}ua^{n}vb is such that t′ as a b in its bottom row, and thus θ(t) ∈ A(I) ⇒ θ(t′) ∉ A(I)

Property iii) shows that to describe atoms, we need only to enumerate the two-row tableaux. Moreover, given a partition I, if we start from the maximal tableau t = ⋯ w_{3}w_{2}w_{1} with w_{k} = (I_{1} + I_{2} + ⋯ I_{k−1} + 1) ⋯ (I_{1} + I_{2} + ⋯ I_{k}) and cycle the left letter of each successive tableau till we get a two-row tableau, then this final tableau (which we shall call canonical) is w_{2}w_{4} ⋯ w_{2k} w_{1}w_{3} · · ·.

The following further simplification shows that we can restrict ourselves to the case of partitions with no parts repeated more than twice, and that in the case that no part is repeated, the atom has only one two-row tableau.

Lemma 9.8 . — i) Let I be a partition, I = 1^{m_{1}}2^{m_{2}} ⋯ k^{m_{k}}. Let ε_{i} = inf(2, m_{i}), n_{i} = m_{i}−ε_{i}, ∀i ≥ 1 and I′ = 0^{p−q}1^{ε_{1}}2^{ε_{2}} ⋯ k^{ε_{k}}, withp = |I′| = ε_{1} + 2ε_{2} + ⋯ + kε_{k}, q = ε_{1} + ⋯ + ε_{k}. Let moreover J = 1^{n_{1}}2^{n_{2}} ⋯ k^{n_{k}} J_{p} ⋯ J_{1}, with J_{p} + ⋯ J_{1} = p. Let finally t ∈ T (J). Then θ(t) ∈ A(I) iff θ(t′) ∈ A(I′), where t′ denotes the restriction of t to the first p letters of 𝔸.

ii) if no part of I is repeated, then A(I) has only one two-row tableau, namely its canonical tableau.

Proof. i) Let t ∈ T (J) be such that θ(t′) ∈ A(I′). Then t′ is the image of a tableau t′_{1} ∈ T (I′) ; denote by t_{1} the tableau obtained from t by changing the subtableau t′ into t′_{1}. According to 9.7i) , to determine to which atom θ(t_{1}) belongs, we have to test the restriction to {a, b}^{∗} of all t_{1}^{μ}, μ ∈ 𝔖(𝔸). In fact we need only to test a subfamily of permutations η such that each pair of parts of I occurs at least once in the set {(|t_{1}^{η}|_{a}, |t_{1}^{η}|_{b})}. Because of the definition of the multiplicities m_{i}, we can suppose that η fixes the letters outside 𝔸_{p} . In other words, η acts only on the subtableau t′_{1}, the restriction of t_{1}^{η} and t′_{1}^{η} to {a, b}^{∗} coïncide and θ(t′_{1}) ∈ A(I′) implies that θ(t_{1}) ∈ A(I).

Conversely, property 9.7ii) shows that θ(t) ∈ A(I) implies that θ(t′) ∈ A(I′). ii) Let t ∈ T (I) be a two-row tableau such that θ(t) ∈ A(I). We know

from proposition 9.7 that for any k the

restriction t′ of t to 𝔸_{k} is such that θ(t′) ∈ A(I′), with I′ = (I_{1}, …, I_{k}). Let k be the smallest integer such that θ(t′) is not canonical. It is equivalent to require that there is at least one occurrence of a_{k} on the bottom (resp. top) row when k is even (resp. odd). Since |t|_{a_{k}} < |t|_{a_{k−1}}, there is also one misplaced a_{k} in the tableau K(t′). Therefore θ(K(t′)) also is not canonical. Since it belongs to the atom A(I′′), with I′′ = (I_{1}+I_{2}, I_{3}, …, I_{k}), the assertion follows by induction on the number of parts

To sum up, atoms are totally characterized by the enumeration of all the non-canonical two-row tableaux for partitions having no part repeated more than twice.

Compact table of all atoms for 𝔖(n), n ≤ 12

alphabet {1,...,9,0,♭,♮}

Atom  Non−canonical T ableaux  Cocharge
A(1223)  {45 \atop 123678}  5
A(1224)  {56 \atop 1234789}  5
A(1225)  {67 \atop 12345890}  5
A(1334)  {567 \atop 1234890♭}  7
A(1226)  {78 \atop 12345690♭}  5
A(12234)  {5670♭♮ \atop 123489}  11
A(2334)  {567♮ \atop 1234890♭}  9
{567 \atop 1234890♭♮}  8
A(1335)  {678 \atop 1234590♭♮}  7
A(1227)  {89 \atop 12345670♭♮}  5

Let us see how to use the table by a concrete example. Take I = 11333 ; reducing the multiplicities of parts to 2 at most, we obtain the partition 1133 which is not in the table. Thus A(1133) has only one two-row tableau, namely 456 8 123 7. Cocycling, we obtain that A(1133) is equal to

_{1237}^{4568} ⟵ ^{7 {456 \atop 1238}} ⟵ ^{8 7 {456 \atop 123}} .

Now according to 9.8, the pull-back of A(11333) in T (3 1^{8}) is exactly the set of all tableaux obtained from the three preceeding ones by shuffling three occurrences of 9. We give below each of these tableaux (written as words) together with their respective images by θ, and their cocharges, taking as alphabet {1, …, 9, 0, ♮} :

Cocharge

{image by θ ⟶ \atop tableau ⟶}  {♮0789456123 \atop 98799456123}  (16)

_{87994561239}^{0789456123♮}  _{98794561239}^{♮0894561237}  (15)
_{79945691238}^{789456♮1230} _{97945691238}^{089456♮1237} _{87945612399}^{0894561237♮} _{97994561238}^{089♮4561237} _{98745612399}^{♮0945612378}  (14)
_{99945681237}^{89♮45601237} _{79456912389}^{89456♮12370} _{97456912389}^{09456♮12378} _{97945612389}^{09♮45612378} _{79945612389}^{89♮45612370} _{87456123999}^{0945612378♮}  (13)
_{99456812379}^{9♮456012378} _{74569123899}^{9456♮123780} _{79456123899}^{9♮456123780} _{97456123899}^{♮9456123780}  (12)
_{94568123799}^{♮4560123789}  _{74561238999}^{9456123780♮}  (11)
{4560123789♮ \atop 45681237999}  (10)

We shall now give a property which allows us to generate atoms by induction on the size of the alphabet.

Let I = (I_{1} ≥ I_{2} ≥ ⋯) be a partition and r an integer such that r ≤ I, let k be the integer such that I_{k} ≥ r > I_{k+1} and denote by I \ r the partition (I_{1}, …, I_{k−1}, I_{k} + I_{k+1} − r , I_{k+2} , …).

Proposition 9.9 . — Let I be a partition, r, n two integers, t a tableau such that θ(t) ∈ A(I) and such that |ev(t)|_{a_{m}} = 0 for m > n, |ev(t)|_{a_{n}} = r. Then the tableau t′ obtained from t by erasing all occurrences of a_{n} is such that θ(t′) belongs to the atom A(I \ r).

We will not give the proof, which reduces by cyclage to a detailed study of two-row tableaux. Note however that in the case where r is a part of I, this property is a corollary of lemma 9.7.

For example, the pull-back of A(4221) in T (1^{6}3) is the set

\{{7 \atop 67} {45 \atop 1237} , 7 6 {45 \atop 12377} ,_{67 {45 \atop 12377}} ,_{6 {45 \atop 123777}} ,_{77 {457 \atop 1236}} ,_{77 {45 \atop 12367}} ,_{7 {457 \atop 12367}} ,_{7 {45 \atop 123677}} ,_{{457 \atop 123677}} ,_{{45 \atop 1236777}}\}

Erasing the “7” , we get the two tableaux 6 {45 \atop 123} , _{{45 \atop 1236}} which belong to the atom A(321), in accordance with the fact that 4221 \ 3 = (4+2−3) 2 1 = 321.

In section 6 we saw that tableaux provide multiplicities of representations, as well as bases, in the cohomology ring H_{I} of the space of flags corresponding to a partition I.

Generators of the ideal defining H_{I} can also be read from tableaux.

For a triple of integers k, r, n : k ≥ r, k + r ≤ n, let τ_{k r n} be the tableau {k+1···k+r \atop 1 ··· k k+r+1··· n} . Using criterium 9.6, we see that τ_{k r n} belongs to the atom A(P (τ_{k r n})), where P (τ_{k r n}) is the following partition of n : P (τ_{k r n}) := (k, r, …, r, n − k − [\frac{n−k}{r}]) and [\frac{n−k}{r}] is the integral part of (n − k)/r. Moreover τ_{k r n} has cocharge n − k.

To the tableau τ_{k r n} we associate the complete function S(τ_{k r n}) := S_{n−k}(𝔸_{r}), with 𝔸_{r} = {a_{1}, …, a_{r}} as before. Given a partition I of n, let 𝔗𝔞𝔟(I) be the set of tableaux τ_{k r n} such that P (τ_{k r n}) ≰ I, and let ℑ𝔡𝔢𝔞𝔩(I) be the ideal of ℤ[𝔸] generated (as a 𝔖(𝔸)−ideal) by the {S(τ), τ ∈ 𝔗𝔞𝔟(I)}. Recall that the order on partitions is defined by the componentwise order on the associated vectors : I → conjugate partition J = (J_{1} ≥ J_{2} ≥ ⋯) → J^{Σ} := (J_{1}, J_{1} + J_{2} − 1, J_{1} + J_{2} + J_{3} − 2, …).

On the other hand, given an integral vector H = (H_{1}, …, H_{p}), let 𝔗𝔞𝔫(H) (due to Tanisaki [Tan]) be the 𝔖(𝔸)−ideal in ℤ[𝔸] generated by {S_{k_{1}}(𝔸_{1}), Sk_{2}(𝔸_{2}), …, S_{k_{p}}(𝔸_{p}) , k_{1} ≥ H_{1}, …, k_{p} ≥ H_{p}}.

Proposition 9.10 . — Let I and J be conjugate partitions. Then the two ideals ℑ𝔡𝔢𝔞𝔩(I) and 𝔗𝔞𝔫(J^{Σ}) coïncide.

Proof. Since order is defined by the vectors J^{Σ}, it is clear that ℑ𝔡𝔢𝔞𝔩(I) can be described by the components of J^{Σ} rather than by the partitions P (τ_{k r n}). We shall just check by an example that the two sets of generators coïncide.

Let I = 864421 and thus J = 65442211 , J^{Σ} = 6 10 13 16 17 18 18 18. The tableau τ_{12,3,25} has cocharge 13 and belongs to the atom A(12 3 3 3 3 1) ; the conjugate of this last partition is 6 5 5 1^{9} which gives the vector 6 11 14 14 … not comparable to J^{Σ}. Thus, P (τ_{12,3,25}) ≰ I. On the other hand, the tableau τ_{13,3,25} has cocharge 12 and belongs to the atom A(13 3 3 3 3) ; the corresponding conjugate partition is 5 5 5 1^{10} giving the vector 5 9 13 13 13 … which is less than J^{Σ}. Therefore, ℑ𝔡𝔢𝔞𝔩(I) contains S_{13}(𝔸_{3}), but not S_{12}(𝔸_{3}), in accordance with the fact that the third component of J^{Σ} is 13

Tanisaki [Tan] uses elementary symmetric functions e_{j} as generators of the ideal, but since e_{j}(𝔸 \ 𝔹) = e_{j}(𝔸) − S_{1}(𝔹)e_{j−1} + S_{2}(𝔹)e_{j−2} − ⋯ + (−1)^{j}S_{j}(𝔹) for any subalphabet 𝔹 of 𝔸, one has e_{j}(a_{1}, …, a_{p}) ≡ (−1)^{j}S_{j}(a_{p+1}, …, a_{n}) modulo the ideal generated by symmetric polynomials in {a_{1}, …, a_{n}} without constant terms : elementary symmetric functions and complete functions are interchangeable.

References

[Bor ] A.BOREL . — Cohomologie des espaces fibrés principaux , Annals of

Math. , t. 57 , 1953, p. 115-207 .

[DeC-Pro ] C. DE CONCINI & C.PROCESI . — Symmetric functions, conjugacy classes

and the flag variety, Invent.Math., t. 64, 1981, p. 203-230. [Gro ] A.GROTHENDIECK . — Sur quelques propriétés fondamentales en théorie

des intersections, Séminaire Chevalley . — Paris, 1958 .

[Hot-Spr] R.HOTTA & T.A.SPRINGER . — A specialization theorem for certain Weyl group representations, Invent.Math., t. 41, 1977, p. 113-127.